| blob | 9c7cd98efa5274749f9a1692859ea65ff1b36b8b |
3 <html>
4 <head>
9 </head>
10 <body>
13 <!--#include virtual="menu.html.incl"-->
21 <p>The static analyzer engine performs path-sensitive exploration of the program and
22 relies on a set of checkers to implement the logic for detecting and
23 constructing specific bug reports. Anyone who is interested in implementing their own
24 checker, should check out the Building a Checker in 24 Hours talk
27 and refer to this page for additional information on writing a checker. The static analyzer is a
28 part of the Clang project, so consult <a href="http://clang.llvm.org/hacking.html">Hacking on Clang</a>
30 for developer guidelines and send your questions and proposals to
32 </p>
34 <ul>
37 <ul>
40 </ul></li>
51 </ul>
54 <ul>
57 page.</li>
59 <li>The analyzer source code is located under the Clang source tree:
60 <br><tt>
62 </tt>
66 <li>The analyzer regression tests can be executed from the Clang's build
67 directory:
68 <br><tt>
70 </tt></li>
72 <li>Analyze a file with the specified checker:
73 <br><tt>
75 </tt></li>
77 <li>List the available checkers:
78 <br><tt>
80 </tt></li>
82 <li>See the analyzer help for different output formats, fine tuning, and
83 debug options:
84 <br><tt>
86 </tt></li>
88 </ul>
91 The analyzer core performs symbolic execution of the given program. All the
92 input values are represented with symbolic values; further, the engine deduces
93 the values of all the expressions in the program based on the input symbols
94 and the path. The execution is path sensitive and every possible path through
95 the program is explored. The explored execution traces are represented with
96 <a href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1ExplodedGraph.html">ExplodedGraph</a> object.
97 Each node of the graph is
98 <a href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1ExplodedNode.html">ExplodedNode</a>,
100 <p>
102 represents the corresponding location in the program (or the CFG graph).
105 kind means that the state is the result of purging dead symbols - the
106 analyzer's equivalent of garbage collection.
107 <p>
108 <a href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1ProgramState.html">ProgramState</a>
109 represents abstract state of the program. It consists of:
110 <ul>
112 values
115 </ul>
118 Checkers are not merely passive receivers of the analyzer core changes - they
121 of the state. Each time the analyzer engine explores a new statement, it
122 notifies each checker registered to listen for that statement, giving it an
123 opportunity to either report a bug or modify the state. (As a rule of thumb,
124 the checker itself should be stateless.) The checkers are called one after another
125 in the predefined order; thus, calling all the checkers adds a chain to the
129 During symbolic execution, <a href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1SVal.html">SVal</a>
130 objects are used to represent the semantic evaluation of expressions.
131 They can represent things like concrete
132 integers, symbolic values, or memory locations (which are memory regions).
133 They are a discriminated union of "values", symbolic and otherwise.
134 If a value isn't symbolic, usually that means there is no symbolic
135 information to track. For example, if the value was an integer, such as
136 <tt>42</tt>, it would be a <a href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1nonloc_1_1ConcreteInt.html">ConcreteInt</a>,
137 and the checker doesn't usually need to track any state with the concrete
139 a symbolic value. This happens when the analyzer cannot reason about something
140 (yet). An example is floating point numbers. In such cases, the
141 <tt>SVal</tt> will evaluate to <a href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1UnknownVal.html">UnknownVal</a>.
142 This represents a case that is outside the realm of the analyzer's reasoning
145 symbols or regions.
146 <p>
148 is meant to represent abstract, but named, symbolic value. Symbols represent
149 an actual (immutable) value. We might not know what its specific value is, but
150 we can associate constraints with that value as we analyze a path. For
151 example, we might record that the value of a symbol is greater than
153 <p>
155 <p>
156 <a href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1MemRegion.html">MemRegion</a> is similar to a symbol.
157 It is used to provide a lexicon of how to describe abstract memory. Regions can
158 layer on top of other regions, providing a layered approach to representing memory.
161 be used to represent the memory associated with a specific field of that object.
162 So how do we represent symbolic memory regions? That's what
163 <a href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1SymbolicRegion.html">SymbolicRegion</a>
165 symbol is unique and has a unique name; that symbol names the region.
167 <P>
168 Let's see how the analyzer processes the expressions in the following example:
169 <p>
171 int foo(int x) {
172 int y = x * 2;
173 int z = x;
174 ...
175 }
176 </pre>
177 <p>
192 <br>
194 dance, and create an <tt>SVal</tt> that references the symbol <tt>$0</tt>. Note, two <tt>SVals</tt>
195 might reference the same underlying values.
197 <p>
198 To summarize, MemRegions are unique names for blocks of memory. Symbols are
199 unique names for abstract symbolic values. Some MemRegions represents abstract
200 symbolic chunks of memory, and thus are also based on symbols. SVals are just
201 references to values, and can reference either MemRegions, Symbols, or concrete
202 values (e.g., the number 1).
204 <!--
205 TODO: Add a picture.
206 <br>
207 Symbols<br>
208 FunctionalObjects are used throughout.
209 -->
212 Here are several questions which you should consider when evaluating your
213 checker idea:
214 <ul>
215 <li>Can the check be effectively implemented without path-sensitive
218 <li>How high the false positive rate is going to be? Looking at the occurrences
219 of the issue you want to write a checker for in the existing code bases might
220 give you some ideas. </li>
222 <li>How the current limitations of the analysis will effect the false alarm
223 rate? Currently, the analyzer only reasons about one procedure at a time (no
224 inter-procedural analysis). Also, it uses a simple range tracking based
225 solver to model symbolic execution.</li>
228 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>
229 to get some ideas for new checkers and consider starting with improving/fixing
230 bugs in the existing checkers.</li>
231 </ul>
233 <p>Once an idea for a checker has been chosen, there are two key decisions that
234 need to be made:
235 <ul>
236 <li> Which events the checker should be tracking. This is discussed in more
238 Checker Class Structure</a>.
239 <li> What checker-specific data needs to be stored as part of the program
240 state (if any). This should be minimized as much as possible. More detail about
241 implementing custom program state is given in section <a
243 </ul>
247 All checker implementation files are located in
250 stream APIs, was registered with the analyzer.
251 Similar steps should be followed for a new checker.
252 <ol>
255 <li>The following registration code was added to the implementation file:
257 void ento::registerSimpleStreamChecker(CheckerManager &mgr) {
258 mgr.registerChecker<SimpleStreamChecker>();
259 }
260 </pre>
261 <li>A package was selected for the checker and the checker was defined in the
263 checkers should first be developed as "alpha", and the SimpleStreamChecker
264 performs UNIX API checks, the correct package is "alpha.unix", and the following
267 let ParentPackage = UnixAlpha in {
268 ...
272 ...
273 } // end "alpha.unix"
274 </pre>
276 <li>The source code file was made visible to CMake by adding it to
279 </ol>
281 After adding a new checker to the analyzer, one can verify that the new checker
282 was successfully added by seeing if it appears in the list of available checkers:
289 Checker</a></tt> template class; the template parameter(s) describe the type of
290 events that the checker is interested in processing. The various types of events
291 that are available are described in the file <a
293 CheckerDocumentation.cpp</a>
295 <p> For each event type requested, a corresponding callback function must be
296 defined in the checker class (<a
298 CheckerDocumentation.cpp</a> shows the
299 correct function name and signature for each event type).
302 take action at the following times:
304 <ul>
306 If so, check the parameter being passed.
308 so, process the return value.
309 <li>When values go out of scope, check whether they are still-open file
310 descriptors, and report a bug if so. In addition, remove any information about
311 them from the program state in order to keep the state as small as possible.
313 track them), mark them as such. This prevents false positives in the cases where
314 the analyzer cannot be sure whether the file was closed or not.
315 </ul>
319 <a
321 <a
322 href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1check_1_1DeadSymbols.html">DeadSymbols</a>,
323 and <a
324 href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1check_1_1PointerEscape.html">PointerEscape</a>.
325 The high-level structure of the checker's class is thus:
328 class SimpleStreamChecker : public Checker<check::PreCall,
329 check::PostCall,
330 check::DeadSymbols,
331 check::PointerEscape> {
332 public:
340 ProgramStateRef checkPointerEscape(ProgramStateRef State,
341 const InvalidatedSymbols &Escaped,
342 const CallEvent *Call,
343 PointerEscapeKind Kind) const;
344 };
345 </pre>
349 <p> Checkers often need to keep track of information specific to the checks they
350 perform. However, since checkers have no guarantee about the order in which the
351 program will be explored, or even that all possible paths will be explored, this
352 state information cannot be kept within individual checkers. Therefore, if
353 checkers need to store custom information, they need to add new categories of
355 several macros designed for this purpose. They are:
357 <ul>
358 <li><a
359 href="http://clang.llvm.org/doxygen/ProgramStateTrait_8h.html#ae4cddb54383cd702a045d7c61b009147">REGISTER_TRAIT_WITH_PROGRAMSTATE</a>:
360 Used when the state information is a single value. The methods available for
363 <li><a
364 href="http://clang.llvm.org/doxygen/CheckerContext_8h.html#aa27656fa0ce65b0d9ba12eb3c02e8be9">REGISTER_LIST_WITH_PROGRAMSTATE</a>:
365 Used when the state information is a list of values. The methods available for
368 <li><a
369 href="http://clang.llvm.org/doxygen/CheckerContext_8h.html#ad90f9387b94b344eaaf499afec05f4d1">REGISTER_SET_WITH_PROGRAMSTATE</a>:
370 Used when the state information is a set of values. The methods available for
373 <li><a
374 href="http://clang.llvm.org/doxygen/CheckerContext_8h.html#a6d1893bb8c18543337b6c363c1319fcf">REGISTER_MAP_WITH_PROGRAMSTATE</a>:
375 Used when the state information is a map from a key to a value. The methods
378 </ul>
380 <p>All of these macros take as parameters the name to be used for the custom
381 category of state information and the data type(s) to be used for storage. The
382 data type(s) specified will become the parameter type and/or return type of the
383 methods that manipulate the new category of state information. Each of these
384 methods are templated with the name of the custom data type.
386 <p>For example, a common case is the need to track data associated with a
387 symbolic expression; a map type is the most logical way to implement this. The
388 key for this map will be a pointer to a symbolic expression
390 expression is an integer, then the custom category of state information would be
391 declared as
394 REGISTER_MAP_WITH_PROGRAMSTATE(ExampleDataType, SymbolRef, int)
395 </pre>
397 The data would be accessed with the function
400 ProgramStateRef state;
401 SymbolRef Sym;
402 ...
404 </pre>
406 and set with the function
409 ProgramStateRef state;
410 SymbolRef Sym;
411 int newValue;
412 ...
414 </pre>
416 <p>In addition, the macros define a data type used for storing the data of the
417 new data category; the name of this type is the name of the data category with
419 be passed data type; for the other three macros, this will be a specialized
420 version of the <a
422 <a
424 or <a
427 created would be equivalent to writing the declaration:
431 </pre>
433 <p>These macros will cover a majority of use cases; however, they still have a
434 few limitations. They cannot be used inside namespaces (since they expand to
435 contain top-level namespace references), and the data types that they define
436 cannot be referenced from more than one file.
439 one, functions that modify the state will return a copy of the previous state
440 with the change applied. This updated state must be then provided to the
445 <p> When a checker detects a mistake in the analyzed code, it needs a way to
446 report it to the analyzer core so that it can be displayed. The two classes used
447 to construct this report are <tt><a
449 and <tt><a
451 BugReport</a></tt>.
453 <p>
456 type, and the name of the category of the bug. These are used (e.g.) in the
457 summary page generated by the scan-build tool.
459 <P>
462 <ol>
464 <li>A short descriptive string. This is placed at the location of the bug in
465 the detailed line-by-line output generated by scan-build.
466 <li>The context in which the bug occurred. This includes both the location of
467 the bug in the program and the program's state when the location is reached. These are
469 </ol>
472 as to whether or not analysis can continue along the current path. This decision
473 is based on whether the detected bug is one that would prevent the program under
474 analysis from continuing. For example, leaking of a resource should not stop
475 analysis, as the program can continue to run after the leak. Dereferencing a
476 null pointer, on the other hand, should stop analysis, as there is no way for
477 the program to meaningfully continue after such an error.
482 returned by the most recent call to <a
483 href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1CheckerContext.html#a264f48d97809707049689c37aa35af78">CheckerContext::addTransition</a>.
484 If no transition has been performed during the current callback, the checker should call <a
485 href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1CheckerContext.html#a264f48d97809707049689c37aa35af78">CheckerContext::addTransition()</a>
486 and use the returned node for bug reporting.
488 <p>If analysis can not continue, then the current state should be transitioned
490 performed. This is done by calling the <a
491 href="http://clang.llvm.org/doxygen/classclang_1_1ento_1_1CheckerContext.html#adeea33a5a2bed190210c4a2bb807a6f0">
492 CheckerContext::generateSink</a> function; this function is the same as the
497 <p>
499 by calling <a href = "http://clang.llvm.org/doxygen/classclang_1_1ento_1_1CheckerContext.html#ae7738af2cbfd1d713edec33d3203dff5">CheckerContext::emitReport</a>.
502 Some checks might not require path-sensitivity to be effective. Simple AST walk
503 might be sufficient. If that is the case, consider implementing a Clang
504 compiler warning. On the other hand, a check might not be acceptable as a compiler
505 warning; for example, because of a relatively high false positive rate. In this
510 Every patch should be well tested with Clang regression tests. The checker tests
515 </pre>
518 <ul>
519 <li>
520 While investigating a checker-related issue, instruct the analyzer to only
521 execute a single checker:
522 <br><tt>
524 </tt>
525 </li>
526 <li>
527 To dump AST:
528 <br><tt>
530 </tt>
531 </li>
532 <li>
534 <br><tt>
536 </tt>
537 </li>
538 <li>
539 To see all available debug checkers:
540 <br><tt>
542 </tt>
543 </li>
544 <li>
545 To see which function is failing while processing a large file use
547 </li>
548 <li>
551 in a separate process.
552 </li>
553 <li>
556 execute:
557 <br><tt>
559 </tt>
560 </li>
561 <li>
563 <br><tt>
565 </tt>
566 </li>
567 <li>
569 pass in a SourceManager object, it will also dump the corresponding line in the
570 source code.
571 <br><tt>
573 </tt>
574 </li>
575 <li>
577 <br><tt>
579 (gdb) <b>p C.getPredecessor()->getCodeDecl().getBody()->dump(getContext().getSourceManager())</b>
580 </tt>
581 </li>
582 </ul>
586 Here are some additional resources that are useful when working on the Clang
587 Static Analyzer:
589 <ul>
591 up-to-date documentation about the APIs available in Clang. Relevant entries
592 have been linked throughout this page. Also of use is the
594 from LLVM.
596 cfe-dev mailing list</a>. This is the primary mailing list used for
597 discussion of Clang development (including static code analysis). The
599 a lot of information.
604 and <a
606 are available.
607 </ul>
610 <ul>
612 </ul>
614 </div>
615 </div>
616 </body>
617 </html>