Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / external / clang / 22d4fb9d687ad38e7a0ee74f58abd65db84fa436 / . / www / analyzer / checker_dev_manual.html
blob: 6fbc1683ae2181ad1dcab6bfabf2e0b63d08c8e1 [file] [log] [blame]
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
3<html>
4<head>
5 <title>Checker Developer Manual</title>
6 <link type="text/css" rel="stylesheet" href="menu.css" />
7 <link type="text/css" rel="stylesheet" href="content.css" />
8 <script type="text/javascript" src="scripts/menu.js"></script>
9</head>
10<body>
11
12<div id="page">
13<!--#include virtual="menu.html.incl"-->
14
15<div id="content">
16
17<h1><font color=red>This Page Is Under Construction</font></h1>
18
19<h1>Checker Developer Manual</h1>
20
21<p>The static analyzer engine performs symbolic execution of the program and
22relies on a set of checkers to implement the logic for detecting and
23constructing bug reports. This page provides hints and guidelines for anyone
24who is interested in implementing their own checker. The static analyzer is a
25part of the Clang project, so consult <a href="http://clang.llvm.org/hacking.html">Hacking on Clang</a>
26and <a href="http://llvm.org/docs/ProgrammersManual.html">LLVM Programmer's Manual</a>
27for general developer guidelines and information. </p>
28
29 <ul>
30 <li><a href="#start">Getting Started</a></li>
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]31 <li><a href="#analyzer">Analyzer Overview</a></li>
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]32 <li><a href="#idea">Idea for a Checker</a></li>
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]33 <li><a href="#registration">Checker Registration</a></li>
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]34 <li><a href="#skeleton">Checker Skeleton</a></li>
35 <li><a href="#node">Exploded Node</a></li>
36 <li><a href="#bugs">Bug Reports</a></li>
37 <li><a href="#ast">AST Visitors</a></li>
38 <li><a href="#testing">Testing</a></li>
39 <li><a href="#commands">Useful Commands</a></li>
40 </ul>
41
42<h2 id=start>Getting Started</h2>
43 <ul>
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]44 <li>To check out the source code and build the project, follow steps 1-4 of
45 the <a href="http://clang.llvm.org/get_started.html">Clang Getting Started</a>
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]46 page.</li>
47
48 <li>The analyzer source code is located under the Clang source tree:
49 <br><tt>
50 $ <b>cd llvm/tools/clang</b>
51 </tt>
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]52 <br>See: <tt>include/clang/StaticAnalyzer</tt>, <tt>lib/StaticAnalyzer</tt>,
53 <tt>test/Analysis</tt>.</li>
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]54
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]55 <li>The analyzer regression tests can be executed from the Clang's build
56 directory:
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]57 <br><tt>
58 $ <b>cd ../../../; cd build/tools/clang; TESTDIRS=Analysis make test</b>
59 </tt></li>
60
61 <li>Analyze a file with the specified checker:
62 <br><tt>
63 $ <b>clang -cc1 -analyze -analyzer-checker=core.DivideZero test.c</b>
64 </tt></li>
65
66 <li>List the available checkers:
67 <br><tt>
68 $ <b>clang -cc1 -analyzer-checker-help</b>
69 </tt></li>
70
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]71 <li>See the analyzer help for different output formats, fine tuning, and
72 debug options:
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]73 <br><tt>
74 $ <b>clang -cc1 -help | grep "analyzer"</b>
75 </tt></li>
76
77 </ul>
78
79<h2 id=analyzer>Static Analyzer Overview</h2>
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]80 The analyzer core performs symbolic execution of the given program. All the
81 input values are represented with symbolic values; further, the engine deduces
82 the values of all the expressions in the program based on the input symbols
83 and the path. The execution is path sensitive and every possible path through
84 the program is explored. The explored execution traces are represented with
85 <a href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1ExplodedGraph.html">ExplidedGraph</a> object.
86 Each node of the graph is
87 <a href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1ExplodedNode.html">ExplodedNode</a>,
88 which consists of a <tt>ProgramPoint</tt> and a <tt>ProgramState</tt>.
89 <p>
90 <a href="http://clang.llvm.org/doxygen/classclang_1_1ProgramPoint.html">ProgramPoint</a>
91 represents the corresponding location in the program (or the CFG graph).
92 <tt>ProgramPoint</tt> is also used to record additional information on
93 when/how the state was added. For example, <tt>PostPurgeDeadSymbolsKind</tt>
94 kind means that the state is the result of purging dead symbols - the
95 analyzer's equivalent of garbage collection.
96 <p>
97 <a href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1ProgramState.html">ProgramState</a>
98 represents abstract state of the program. It consists of:
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]99 <ul>
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]100 <li><tt>Environment</tt> - a mapping from source code expressions to symbolic
101 values
102 <li><tt>Store</tt> - a mapping from memory locations to symbolic values
103 <li><tt>GenericDataMap</tt> - constraints on symbolic values
104 </ul>
105
Anna Zaks22d4fb92011-12-07 19:04:24 +0000[diff] [blame^]106 <h3>Interaction with Checkers</h3>
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]107 Checkers are not merely passive receivers of the analyzer core changes - they
108 actively participate in the <tt>ProgramState</tt> construction through the
109 <tt>GenericDataMap</tt> which can be used to store the checker-defined part
110 of the state. Each time the analyzer engine explores a new statement, it
111 notifies each checker registered to listen for that statement, giving it an
112 opportunity to either report a bug or modify the state. (As a rule of thumb,
113 the checker itself should be stateless.) The checkers are called one after another
114 in the predefined order; thus, calling all the checkers adds a chain to the
115 <tt>ExplodedGraph</tt>.
Anna Zaks22d4fb92011-12-07 19:04:24 +0000[diff] [blame^]116
117 <h3>Representing Values</h3>
118 During symbolic execution, <a href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1SVal.html">SVal</a>
119 objects are used to represent the semantic evaluation of expressions. They can
120 represent things like concrete integers, symbolic values, or memory locations
121 (which are memory regions). They are a discriminated union of "values",
122 symbolic and otherwise.
123 <p>
124 <a href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1SymExpr.html">SymExpr</a> (symbol)
125 is meant to represent abstract, but named, symbolic value.
126 Symbolic values can have constraints associated with them. Symbols represent
127 an actual (immutable) value. We might not know what its specific value is, but
128 we can associate constraints with that value as we analyze a path.
129 <p>
130
131 <a href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1MemRegion.html">MemRegion</a> is similar to a symbol.
132 It is used to provide a lexicon of how to describe abstract memory. Regions can
133 layer on top of other regions, providing a layered approach to representing memory.
134 For example, a struct object on the stack might be represented by a <tt>VarRegion</tt>,
135 but a <tt>FieldRegion</tt> which is a subregion of the <tt>VarRegion</tt> could
136 be used to represent the memory associated with a specific field of that object.
137 So how do we represent symbolic memory regions? That's what <a href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1SymbolicRegion.html">SymbolicRegion</a>
138 is for. It is a <tt>MemRegion</tt> that has an associated symbol. Since the
139 symbol is unique and has a unique name; that symbol names the region.
140 <p>
141 Let's see how the analyzer processes the expressions in the following example:
142 <p>
143 <pre class="code_example">
144 int foo(int x) {
145 int y = x * 2;
146 int z = x;
147 ...
148 }
149 </pre>
150 <p>
151Let's look at how <tt>x*2</tt> gets evaluated. When <tt>x</tt> is evaluated,
152we first construct an <tt>SVal</tt> that represents the lvalue of <tt>x</tt>, in
153this case it is an <tt>SVal</tt> that references the <tt>MemRegion</tt> for <tt>x</tt>.
154Afterwards, when we do the lvalue-to-rvalue conversion, we get a new <tt>SVal</tt>,
155which references the value <b>currently bound</b> to <tt>x</tt>. That value is
156symbolic; it's whatever <tt>x</tt> was bound to at the start of the function.
157Let's call that symbol <tt>$0</tt>. Similarly, we evaluate the expression for <tt>2</tt>,
158and get an <tt>SVal</tt> that references the concrete number <tt>2</tt>. When
159we evaluate <tt>x*2</tt>, we take the two <tt>SVals</tt> of the subexpressions,
160and create a new <tt>SVal</tt> that represents their multiplication (which in
161this case is a new symbolic expression, which we might call <tt>$1</tt>). When we
162evaluate the assignment to <tt>y</tt>, we again compute its lvalue (a <tt>MemRegion</tt>),
163and then bind the <tt>SVal</tt> for the RHS (which references the symbolic value <tt>$1</tt>)
164to the <tt>MemRegion</tt> in the symbolic store.
165<br>
166The second line is similar. When we evaluate <tt>x</tt> again, we do the same
167dance, and create an <tt>SVal</tt> that references the symbol <tt>$0</tt>. Note, two <tt>SVals</tt>
168might reference the same underlying values.
169
170<p>
171To summarize, MemRegions are unique names for blocks of memory. Symbols are
172unique names for abstract symbolic values. Some MemRegions represents abstract
173symbolic chunks of memory, and thus are also based on symbols. SVals are just
174references to values, and can reference either MemRegions, Symbols, or concrete
175values (e.g., the number 1).
176
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]177 <!--
178 TODO: Add a picture.
179 <br>
180 Symbols<br>
181 FunctionalObjects are used throughout.
182 -->
183<h2 id=idea>Idea for a Checker</h2>
184 Here are several questions which you should consider when evaluating your
185 checker idea:
186 <ul>
187 <li>Can the check be effectively implemented without path-sensitive
188 analysis? See <a href="#ast">AST Visitors</a>.</li>
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]189
190 <li>How high the false positive rate is going to be? Looking at the occurrences
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]191 of the issue you want to write a checker for in the existing code bases might
192 give you some ideas. </li>
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]193
194 <li>How the current limitations of the analysis will effect the false alarm
195 rate? Currently, the analyzer only reasons about one procedure at a time (no
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]196 inter-procedural analysis). Also, it uses a simple range tracking based
197 solver to model symbolic execution.</li>
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]198
199 <li>Consult the <a href="http://llvm.org/bugs/buglist.cgi?query_format=advanced&bug_status=NEW&bug_status=REOPENED&version=trunk&component=Static%20Analyzer&product=clang">Bugzilla database</a>
200 to get some ideas for new checkers and consider starting with improving/fixing
201 bugs in the existing checkers.</li>
202 </ul>
203
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]204<h2 id=registration>Checker Registration</h2>
205 All checker implementation files are located in <tt>clang/lib/StaticAnalyzer/Checkers</tt>
206 folder. Follow the steps below to register a new checker with the analyzer.
207<ol>
208 <li>Create a new checker implementation file, for example <tt>./lib/StaticAnalyzer/Checkers/NewChecker.cpp</tt>
209<pre class="code_example">
210using namespace clang;
211using namespace ento;
212
213namespace {
214class NewChecker: public Checker< check::PreStmt<CallExpr> > {
215public:
216 void checkPreStmt(const CallExpr *CE, CheckerContext &Ctx) const {}
217}
218}
219void ento::registerNewChecker(CheckerManager &mgr) {
220 mgr.registerChecker<NewChecker>();
221}
222</pre>
223
224<li>Pick the package name for your checker and add the registration code to
225<tt>./lib/StaticAnalyzer/Checkers/Checkers.td</tt>. Note, all checkers should
226first be developed as experimental. Suppose our new checker performs security
227related checks, then we should add the following lines under
228<tt>SecurityExperimental</tt> package:
229<pre class="code_example">
230let ParentPackage = SecurityExperimental in {
231...
232def NewChecker : Checker<"NewChecker">,
233 HelpText<"This text should give a short description of the checks performed.">,
234 DescFile<"NewChecker.cpp">;
235...
236} // end "security.experimental"
237</pre>
238
239<li>Make the source code file visible to CMake by adding it to
240<tt>./lib/StaticAnalyzer/Checkers/CMakeLists.txt</tt>.
241
242<li>Compile and see your checker in the list of available checkers by running:<br>
243<tt><b>$clang -cc1 -analyzer-checker-help</b></tt>
244</ol>
245
246
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]247<h2 id=skeleton>Checker Skeleton</h2>
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]248 There are two main decisions you need to make:
249 <ul>
Anna Zaks22d4fb92011-12-07 19:04:24 +0000[diff] [blame^]250 <li> Which events the checker should be tracking.
251 See <a href="http://clang.llvm.org/doxygen/classento_1_1CheckerDocumentation.html">CheckerDocumentation</a>
252 for the list of available checker callbacks.</li>
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]253 <li> What data you want to store as part of the checker-specific program
254 state. Try to minimize the checker state as much as possible. </li>
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]255 </ul>
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]256
257<h2 id=bugs>Bug Reports</h2>
258
259<h2 id=ast>AST Visitors</h2>
260 Some checks might not require path-sensitivity to be effective. Simple AST walk
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]261 might be sufficient. If that is the case, consider implementing a Clang
262 compiler warning. On the other hand, a check might not be acceptable as a compiler
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]263 warning; for example, because of a relatively high false positive rate. In this
264 situation, AST callbacks <tt><b>checkASTDecl</b></tt> and
265 <tt><b>checkASTCodeBody</b></tt> are your best friends.
266
267<h2 id=testing>Testing</h2>
268 Every patch should be well tested with Clang regression tests. The checker tests
269 live in <tt>clang/test/Analysis</tt> folder. To run all of the analyzer tests,
270 execute the following from the <tt>clang</tt> build directory:
271 <pre class="code">
272 $ <b>TESTDIRS=Analysis make test</b>
273 </pre>
274
275<h2 id=commands>Useful Commands/Debugging Hints</h2>
276<ul>
277<li>
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]278While investigating a checker-related issue, instruct the analyzer to only
279execute a single checker:
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]280<br><tt>
281$ <b>clang -cc1 -analyze -analyzer-checker=osx.KeychainAPI test.c</b>
282</tt>
283</li>
284<li>
285To dump AST:
286<br><tt>
287$ <b>clang -cc1 -ast-dump test.c</b>
288</tt>
289</li>
290<li>
291To view/dump CFG use <tt>debug.ViewCFG</tt> or <tt>debug.DumpCFG</tt> checkers:
292<br><tt>
293$ <b>clang -cc1 -analyze -analyzer-checker=debug.ViewCFG test.c</b>
294</tt>
295</li>
296<li>
297To see all available debug checkers:
298<br><tt>
299$ <b>clang -cc1 -analyzer-checker-help | grep "debug"</b>
300</tt>
301</li>
302<li>
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]303To see which function is failing while processing a large file use
304<tt>-analyzer-display-progress</tt> option.
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]305</li>
306<li>
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]307While debugging execute <tt>clang -cc1 -analyze -analyzer-checker=core</tt>
308instead of <tt>clang --analyze</tt>, as the later would call the compiler
309in a separate process.
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]310</li>
311<li>
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]312To view <tt>ExplodedGraph</tt> (the state graph explored by the analyzer) while
313debugging, goto a frame that has <tt>clang::ento::ExprEngine</tt> object and
314execute:
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]315<br><tt>
316(gdb) <b>p ViewGraph(0)</b>
317</tt>
318</li>
319<li>
Anna Zaks464ef2e2011-11-07 05:36:29 +0000[diff] [blame]320To see <tt>clang::Expr</tt> while debugging use the following command. If you
321pass in a SourceManager object, it will also dump the corresponding line in the
322source code.
Anna Zaksd67fc492011-11-02 17:49:20 +0000[diff] [blame]323<br><tt>
324(gdb) <b>p E->dump()</b>
325</tt>
326</li>
327<li>
328To dump AST of a method that the current <tt>ExplodedNode</tt> belongs to:
329<br><tt>
330(gdb) <b>p ENode->getCodeDecl().getBody()->dump(getContext().getSourceManager())</b>
331</tt>
332</li>
333</ul>
334
335</div>
336</div>
337</body>
338</html>