142 lines · plain
1//===----------------------------------------------------------------------===//2// Clang Static Analyzer3//===----------------------------------------------------------------------===//4 5= Library Structure =6 7The analyzer library has two layers: a (low-level) static analysis8engine (ExprEngine.cpp and friends), and some static checkers9(*Checker.cpp). The latter are built on top of the former via the10Checker and CheckerVisitor interfaces (Checker.h and11CheckerVisitor.h). The Checker interface is designed to be minimal12and simple for checker writers, and attempts to isolate them from much13of the gore of the internal analysis engine.14 15= How It Works =16 17The analyzer is inspired by several foundational research papers ([1],18[2]). (FIXME: kremenek to add more links)19 20In a nutshell, the analyzer is basically a source code simulator that21traces out possible paths of execution. The state of the program22(values of variables and expressions) is encapsulated by the state23(ProgramState). A location in the program is called a program point24(ProgramPoint), and the combination of state and program point is a25node in an exploded graph (ExplodedGraph). The term "exploded" comes26from exploding the control-flow edges in the control-flow graph (CFG).27 28Conceptually the analyzer does a reachability analysis through the29ExplodedGraph. We start at a root node, which has the entry program30point and initial state, and then simulate transitions by analyzing31individual expressions. The analysis of an expression can cause the32state to change, resulting in a new node in the ExplodedGraph with an33updated program point and an updated state. A bug is found by hitting34a node that satisfies some "bug condition" (basically a violation of a35checking invariant).36 37The analyzer traces out multiple paths by reasoning about branches and38then bifurcating the state: on the true branch the conditions of the39branch are assumed to be true and on the false branch the conditions40of the branch are assumed to be false. Such "assumptions" create41constraints on the values of the program, and those constraints are42recorded in the ProgramState object (and are manipulated by the43ConstraintManager). If assuming the conditions of a branch would44cause the constraints to be unsatisfiable, the branch is considered45infeasible and that path is not taken. This is how we get46path-sensitivity. We reduce exponential blow-up by caching nodes. If47a new node with the same state and program point as an existing node48would get generated, the path "caches out" and we simply reuse the49existing node. Thus the ExplodedGraph is not a DAG; it can contain50cycles as paths loop back onto each other and cache out.51 52ProgramState and ExplodedNodes are basically immutable once created. Once53one creates a ProgramState, you need to create a new one to get a new54ProgramState. This immutability is key since the ExplodedGraph represents55the behavior of the analyzed program from the entry point. To56represent these efficiently, we use functional data structures (e.g.,57ImmutableMaps) which share data between instances.58 59Finally, individual Checkers work by also manipulating the analysis60state. The analyzer engine talks to them via a visitor interface.61For example, the PreVisitCallExpr() method is called by ExprEngine62to tell the Checker that we are about to analyze a CallExpr, and the63checker is asked to check for any preconditions that might not be64satisfied. The checker can do nothing, or it can generate a new65ProgramState and ExplodedNode which contains updated checker state. If it66finds a bug, it can tell the BugReporter object about the bug,67providing it an ExplodedNode which is the last node in the path that68triggered the problem.69 70= Notes about C++ =71 72Since now constructors are seen before the variable that is constructed73in the CFG, we create a temporary object as the destination region that74is constructed into. See ExprEngine::VisitCXXConstructExpr().75 76In ExprEngine::processCallExit(), we always bind the object region to the77evaluated CXXConstructExpr. Then in VisitDeclStmt(), we compute the78corresponding lazy compound value if the variable is not a reference, and79bind the variable region to the lazy compound value. If the variable80is a reference, just use the object region as the initializer value.81 82Before entering a C++ method (or ctor/dtor), the 'this' region is bound83to the object region. In ctors, we synthesize 'this' region with84CXXRecordDecl*, which means we do not use type qualifiers. In methods, we85synthesize 'this' region with CXXMethodDecl*, which has getThisType()86taking type qualifiers into account. It does not matter we use qualified87'this' region in one method and unqualified 'this' region in another88method, because we only need to ensure the 'this' region is consistent89when we synthesize it and create it directly from CXXThisExpr in a single90method call.91 92= Working on the Analyzer =93 94If you are interested in bringing up support for C++ expressions, the95best place to look is the visitation logic in ExprEngine, which96handles the simulation of individual expressions. There are plenty of97examples there of how other expressions are handled.98 99If you are interested in writing checkers, look at the Checker and100CheckerVisitor interfaces (Checker.h and CheckerVisitor.h). Also look101at the files named *Checker.cpp for examples on how you can implement102these interfaces.103 104= Debugging the Analyzer =105 106There are some useful command-line options for debugging. For example:107 108$ clang -cc1 -help | grep analyze109 -analyze-function <value>110 -analyzer-display-progress111 -analyzer-viz-egraph-graphviz112 ...113 114The first allows you to specify only analyzing a specific function.115The second prints to the console what function is being analyzed. The116third generates a graphviz dot file of the ExplodedGraph. This is117extremely useful when debugging the analyzer and viewing the118simulation results.119 120Of course, viewing the CFG (Control-Flow Graph) is also useful:121 122$ clang -cc1 -analyzer-checker-help-developer123 124 -analyzer-checker=debug.DumpCFG Display Control-Flow Graphs125 -analyzer-checker=debug.ViewCFG View Control-Flow Graphs using GraphViz126(outdated below?)127 -cfg-add-implicit-dtors Add C++ implicit destructors to CFGs for all analyses128 -cfg-add-initializers Add C++ initializers to CFGs for all analyses129 -unoptimized-cfg Generate unoptimized CFGs for all analyses130 131debug.DumpCFG dumps a textual representation of the CFG to the console, and132debug.ViewCFG creates a GraphViz representation.133 134= References =135 136[1] Precise interprocedural dataflow analysis via graph reachability,137 T Reps, S Horwitz, and M Sagiv, POPL '95,138 http://portal.acm.org/citation.cfm?id=199462139 140[2] A memory model for static analysis of C programs, Z Xu, T141 Kremenek, and J Zhang, http://lcs.ios.ac.cn/~xzx/memmodel.pdf142