<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">22.05.2018 04:35, George Karpenkov
пишет:<br>
</div>
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<div class="">Hi Alexey,</div>
<div class=""><br class="">
</div>
<div class="">As classics say, "Any sufficiently
complicated C or Fortran program contains an ad-hoc,
informally-specified, bug-ridden, slow implementation of half
of Common Lisp.”</div>
</blockquote>
Yes, <a class="moz-txt-link-freetext" href="https://xkcd.com/297/">https://xkcd.com/297/</a> is what I was always thinking while
writing new AST matchers. Time-honored tradition :)<br>
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com">
<div class=""><br class="">
</div>
<div class="">Jokes aside, I think the concept and what you are
doing is great,</div>
<div class="">and we could certainly benefit from declarative
matchers.</div>
<div class="">However, I think the actual implementation and the
set of matchers and predicates would require quite a bit of
bikeshedding.</div>
</blockquote>
Sure. If we need this stuff - the design details are subject for
discussion and change.<br>
<br>
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com">
<div class=""><br class="">
</div>
<div class="">Are you familiar with similar works in this area?</div>
<div class="">E.g. Oracle has a Soufflé project doing a similar
task: <a href="http://souffle-lang.org" class=""
moz-do-not-send="true">http://souffle-lang.org</a>.</div>
<div class="">They have found achieving high performance very
challenging, and IIRC they resort to generating C++ code from
the declaratively described matcher.</div>
</blockquote>
My goal was not to achieve extreme performance but not to hurt
analyzer's performance too much. Don't know how far I am from this
target, unfortunately.<br>
<br>
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com">
<div class="">Maybe we would have to do the same in tablegen
spirit.</div>
<div class=""><br class="">
</div>
<div class="">I’m sure there are more such works in the
literature.</div>
</blockquote>
Yes, I know about some researches in this area, but thank you
anyway!<br>
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com">
<div class=""><br class="">
</div>
<div class="">
<div>
<blockquote type="cite" class="">
<div class="">On May 16, 2018, at 4:37 PM, Alexey Sidorin
via cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org"
class="" moz-do-not-send="true">cfe-dev@lists.llvm.org</a>>
wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<div class="">Hello everyone,<br class="">
<br class="">
I'd like to share some results of my investigation
targeted on improvement of Clang Static Analyzer checker
API. You can find some previous conversation on this
topic here: <a
href="http://clang-developers.42468.n3.nabble.com/analyzer-RFC-Design-idea-separate-modelling-from-checking-td4059122.html"
class="" moz-do-not-send="true">http://clang-developers.42468.n3.nabble.com/analyzer-RFC-Design-idea-separate-modelling-from-checking-td4059122.html</a>.
In my investigation, I tried to solve a particular
problem of building a checker without generating new
nodes.<br class="">
</div>
</div>
</blockquote>
<div><br class="">
</div>
<div>I agree that this is a worthy goal.</div>
<br class="">
<blockquote type="cite" class="">
<div class="">
<div class=""><br class="">
--------- Introduction and design goals ---------<br
class="">
<br class="">
In brief, I tried to use matchers-like API to make CSA
checkers look like this:<br class="">
<br class="">
StatementMatcher NotChdir =<br class="">
callExpr(unless(callee(functionDecl(hasName("::chdir")))));<br
class="">
Finder.addMatcher(<br class="">
hasSequence(<br class="">
postStmt(hasStatement(<br class="">
callExpr(callee(functionDecl(hasName("::chroot")))))),<br
class="">
unless(stmtPoint(hasStatement(callExpr(<br
class="">
callee(functionDecl(hasName("::chdir"))),<br
class="">
hasArgument(0,
hasValue(stringRegion(refersString("/")))))))),<br
class="">
explodedNode(anyOf(postStmt(hasStatement(NotChdir)),<br
class="">
callEnter(hasCallExpr(NotChdir))))<br class="">
.bind("bug_node")),<br class="">
&Callback);<br class="">
Finder.match(G);<br class="">
</div>
</div>
</blockquote>
<div><br class="">
</div>
<div>Bikeshedding: I think it’s much better for the sequence
matcher to run from start to end,</div>
<div>since that’s how we think about the execution of a
program.</div>
</div>
</div>
</blockquote>
Not sure that I understand completely what do you mean. The nodes
are written in the same sequence as they should be on the path in
ExplodedGraph.<br>
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com">
<div class="">
<div><br class="">
<blockquote type="cite" class="">
<div class="">
<div class=""><br class="">
and I have managed to make some simple working examples.<br
class="">
<br class="">
The entire diff can be found here: <a
href="https://github.com/a-sid/clang/commit/9a0b1d1d9b3cf41b551a663f041f54d5427aa72f"
class="" moz-do-not-send="true">https://github.com/a-sid/clang/commit/9a0b1d1d9b3cf41b551a663f041f54d5427aa72f</a><br
class="">
The code itself: <a
href="https://github.com/a-sid/clang/tree/a4" class=""
moz-do-not-send="true">https://github.com/a-sid/clang/tree/a4</a><br
class="">
<br class="">
There are several reasons why I have tried this
approach.<br class="">
<br class="">
1. AST Matchers are already extensively used API for AST
checking. They are available both in Clang-Tidy and CSA.
And I wanted to use existing functionality as much as
possible. So, I decided to extend an existing API to
make its usage seamless across different kinds of
checks: path-sensitive, AST-based and CFG-based.<br
class="">
<br class="">
2. AST matchers effectively help clients to avoid a lot
of checking of dyn_cast results. This feature not only
makes them more convenient but also more safe because,
in my experience, forgetting a nullptr/None check is a
pretty common mistake for checker writers.<br class="">
<br class="">
3. Testing of AST matchers don't require writing C++
code - it can be done interactively with clang-query
tool. And I believe that we need similar functionality
for CSA as well.<br class="">
</div>
</div>
</blockquote>
<div><br class="">
</div>
<div>Moreover, new matchers could be written without modifying
clang. I wonder if we should support some kind of a plugin
infrastructure which support matchers</div>
<div>defined in a text file, e.g. something along the lines
of:</div>
<div><br class="">
</div>
<div>clang -cc1 —analyze -analyzer-checker=core,mymatcher
-analyzer-load-declarative-checker=mymatcher.txt</div>
</div>
</div>
</blockquote>
I planned to reuse dynamic matchers infrastructure and clang-query
for this. clang-query is a command-line tool but there shouldn't be
too much difference where the matcher string we parse comes from.
The problem here is that, AFAIR, using callbacks with dynamic
matchers is impossible. Still it is a very cool tool for quick
matcher prototyping.<br>
<br>
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com">
<div class="">
<div><br class="">
<blockquote type="cite" class="">
<div class="">
<div class=""><br class="">
I didn't want to replace existing checker API. Instead,
I tried to make new possibilities usable independently
or together with existing.<br class="">
<br class="">
--------- Design and implementation ---------<br
class="">
<br class="">
The implementation consisted of a number of steps.<br
class="">
<br class="">
1. Allow matching nodes of path-sensitive graph like
usual AST nodes. To make this possible, three actions
were needed:<br class="">
1.1. ASTTypeTraits and DynTypedNode were extended to
support path-sensitive nodes: ExplodedNode,
ProgramState, SVal, SymExpr, etc. The implementation
with graph node support is moved into a separate class
(ASTGraphTypeTraits) in ento namespace to resolve cyclic
dependencies (they are still exist, unfortunately, but
are header-only, so we can build the PoC).<br class="">
1.2. Some additions to AST matchers were made to add
support for new kinds of nodes.<br class="">
1.3. To make MatchFinder able to query specific options
not supported by pure AST, it was augmented with
"Contexts". A matcher that needs to query the
path-sensitive engine asks the Finder for the required
Context which provides specific helper functions.<br
class="">
<br class="">
As the result of this step, we are able to write
matchers like expr(hasArgument(0,
hasValue(stringRegion(refersString("/"))))).<br class="">
<br class="">
2. Create an engine for graph exploration and matching.<br
class="">
Unlike normal AST matchers, hasSequence is a
path-sensitive matcher. It is launched against
ExplodedGraph. These matchers are handled by
GraphMatchFinder object. While searching a graph, it
collects matches. Each match contains a pointer to the
corresponding matcher and State ID of this match. The
way how matches are translated from one state ID to
another is determined by matcher operators.<br class="">
<br class="">
For example, SequenceVariadicOperator, which is the
base of hasSequence() matcher, has "positive" and
"negative" sub-matches. Each positive matcher has its
corresponding State ID. In order to advance to the next
State ID, a node being matched should match all
"negative" matchers before the next "positive" matchers
and the next "positive" matcher itself. Failure in
matching "negative" matcher discards the match.<br
class="">
<br class="">
The role of GraphMatchFinder is similar to
MatchFinder: it is only responsible for graph
exploration and keeping bound nodes and matchers.<br
class="">
<br class="">
3. Manage bound nodes.<br class="">
While matching a single graph node, BoundNodes from
AST MatchFinder are used. AST matchers for
path-sensitive nodes support bindings out-of-the-box.
However, the situation with graph matching is a bit
different. For graph matching, we have another system of
bound nodes. Each graph node has a related map of bounds
aka GDMTy (yes, the name is not a coincidence). GDMTy is
a mapping from match ID to BoundNodesMap which, in part,
is effectively a map from std::string to DynTypedNodes.
This look pretty much like how GDM is organized in
ExplodedGraph, just without one level of indirection (it
can be added, though).<br class="">
<br class="">
MatchFinder contexts should allow support of their own
bindings. This is how equalsBoundNode() matcher works
for path-sensitive nodes: it just queries all available
contexts for the binding.<br class="">
<br class="">
Finally, I have managed to make two checkers work in
this way: ChrootChecker (which is present in the
introduction) and TestAfterDivZeroChecker. Both them can
be found in ChrootCheckerV2.cpp and
TestAfterDivZeroCheckerV2.cpp correspondingly. They act
like normal checkers: produce warnings and use visitors.
The main difference is that they cannot generate sinks
and use checkEndAnalysis callback. The code of these
checkers can be found here:<br class="">
<br class="">
<a
href="https://github.com/a-sid/clang/blob/a4/lib/StaticAnalyzer/Checkers/ChrootCheckerV2.cpp"
class="" moz-do-not-send="true">https://github.com/a-sid/clang/blob/a4/lib/StaticAnalyzer/Checkers/ChrootCheckerV2.cpp</a><br
class="">
<a class="moz-txt-link-freetext" href="https://github.com/a-sid/clang/blob/a4/lib/StaticAnalyzer/Checkers/TestAfterDivZeroCheckerV2.cpp">https://github.com/a-sid/clang/blob/a4/lib/StaticAnalyzer/Checkers/TestAfterDivZeroCheckerV2.cpp</a><br
class="">
<br class="">
<br class="">
-------- Some features --------<br class="">
<br class="">
1.The design of bindings has an interesting consequence:
it enables the dynamic introspection of GDM which was
pretty hard before. (Hello alpha renaming?)<br class="">
2. Nothing prevents matchers to be used with existing
checker API for simplifying conditional checking inside
callbacks. The matchers are not planned as the
replacement for the current API, but look like a nice
complementary part.<br class="">
3. Implicit conversion of Matcher<ProgramPoint> to
Matcher<ExplodedNode> and Matcher<SymExpr ||
MemRegion> to Matcher<SVal> for writing shorter
code.<br class="">
<br class="">
-------- Not implemented/not checked yet --------<br
class="">
I tried to keep the PoC as minimal as possible. As the
result, some features are not implemented yet, but I
believe they can be added.<br class="">
1. Usage of matchers inside checker callbacks<br
class="">
This is not exactly unimplemented, but is still
untested.<br class="">
2. Dynamic matchers (clang-query interface)<br class="">
In addition to work for supporting dynamic nodes (I
don't know how many efforts it can take), we need to
enable matching against AST nodes, not graph. But it
doesn't look as a problem, we can just make matchers
polymorphic.<br class="">
3. Binding to successfully matched paths is not
implemented yet - only bindings to separate nodes. I
wonder if we need path bindings at all.<br class="">
4. Some corner cases are still FIXMEs: single-node
sequences, for example.<br class="">
5. GDM is not based on immutable data structures like it
is done in CSA - it is just an STL map. Its performance
can be poor (full copy on every new node), but I don't
think that changing it to use immutable structures is
hard.<br class="">
6. Matching on-the-fly<br class="">
GraphMatchFinder should support on-the-fly matching
during ExplodedGraph building. For this support, we
should just call its advance() method each time a new
node is created. However, this possibility wasn't
checked yet.<br class="">
7. Matching CFG and CallGraph isn't implemented because
it was considered to be far out of simple PoC.<br
class="">
8. Only sequential matching is available now, and I
didn't try to implement other operators yet. So,
implementing a checker similar to PthreadLock can be
tricky or even impossible for now.<br class="">
<br class="">
-------- Known and potential issues --------<br class="">
From matchers' side:<br class="">
1. Some tests don't pass because they rely on the
checker ability to generate sink nodes. Our matchers
cannot do it by design so tests don't pass.<br class="">
</div>
</div>
</blockquote>
<div><br class="">
</div>
<div>Actually I would disagree with this one: I think it would
be better to support that, since many errors are considered
fatal.</div>
<div>(but that of course would require running the checkers on
a stream of events, rather than on the already constructed
graph)</div>
</div>
</div>
</blockquote>
As I answered to Artem, this is technically possible (but still
undesirable, I think) because matchers fire their given callbacks on
match, and callbacks are much less limited in their possibilities.<br>
<br>
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com">
<div class="">
<div><br class="">
<blockquote type="cite" class="">
<div class="">
<div class="">2. Representing checker bindings as a map
can be less effective than storing data in structures. I
didn't measure the overhead, so I cannot give any
numbers.<br class="">
3. Matchers are called on every node independently of
its type. This is not what CheckerManager does. I wonder
if this detail can affect performance as well.<br
class="">
</div>
</div>
</blockquote>
<div><br class="">
</div>
<div>I would guess it would affect it hugely, and getting the
performance right would be the biggest challenge for
declarative matchers.</div>
</div>
</div>
</blockquote>
That's sad. I'll try to measure the overhead but I'm not sure I'll
be able to do it soon.<br>
<br>
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com">
<div class="">
<div><br class="">
<blockquote type="cite" class="">
<div class="">
<div class="">4. Problems with cyclic dependencies.
clangStaticAnalyzer has a dependency on
clangASTMatchers, therefore, clangASTMatchers cannot
depend on clangStaticAnalyzer. However, if we want
ASTMatchers to support static analyzer data structures,
there should be a backward dependency. Now this
dependency is header-only.<br class="">
5. Code duplication. This is mostly fine for a sandbox
but needs to be reduced.<br class="">
<br class="">
From analyzer's side:<br class="">
1. Many events are not reflected in the final
ExplodedGraph. For example, checkers can receive
PointerEscape event, but the event itself will not be
recorded in the ExplodedGraph - only changes made by
checkers will. That's also true for Stmt nodes: I
noticed same issues with PostCondition. This makes
matching a bit harder. Should we add some information
into ExplodedGraph?<br class="">
2. (Minor) Some static analyzer data structures don't
support traditional LLVM casting methods (dyn_cast, isa)
because they lack classof() method. I have fixed this
internally and will put a patch on review soon.<br
class="">
<br class="">
-------- Conclusion --------<br class="">
Finally, there is a graph matching engine supporting
basic functionality and two checkers using it. I
apologize for not starting the discussion earlier, but I
just wasn't sure that the approach will work. Is anybody
interested to have this stuff in upstream (maybe,
changed or improved)? If yes, I'll be happy to
contribute this work patch-by-patch and continue its
improvement. If no - well, I had enough fun playing with
it.<br class="">
<br class="">
_______________________________________________<br
class="">
cfe-dev mailing list<br class="">
<a href="mailto:cfe-dev@lists.llvm.org" class=""
moz-do-not-send="true">cfe-dev@lists.llvm.org</a><br
class="">
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a><br
class="">
</div>
</div>
</blockquote>
</div>
<br class="">
</div>
</blockquote>
<p><br>
</p>
</body>
</html>