1 @c Copyright (C) 2019 Free Software Foundation, Inc.
2 @c This is part of the GCC manual.
3 @c For copying conditions, see the file gcc.texi.
4 @c Contributed by David Malcolm <dmalcolm@redhat.com>.
7 @chapter Static Analyzer
9 @cindex static analysis
10 @cindex static analyzer
13 * Analyzer Internals:: Analyzer Internals
14 * Debugging the Analyzer:: Useful debugging tips
17 @node Analyzer Internals
18 @section Analyzer Internals
19 @cindex analyzer, internals
20 @cindex static analyzer, internals
24 The analyzer implementation works on the gimple-SSA representation.
25 (I chose this in the hopes of making it easy to work with LTO to
26 do whole-program analysis).
28 The implementation is read-only: it doesn't attempt to change anything,
31 The gimple representation can be seen using @option{-fdump-ipa-analyzer}.
33 If the analyzer ICEs before this is written out, one workaround is to use
34 @option{--param=analyzer-bb-explosion-factor=0} to force the analyzer
35 to bail out after analyzing the first basic block.
38 First, we build a @code{supergraph} which combines the callgraph and all
39 of the CFGs into a single directed graph, with both interprocedural and
40 intraprocedural edges. The nodes and edges in the supergraph are called
41 ``supernodes'' and ``superedges'', and often referred to in code as
42 @code{snodes} and @code{sedges}. Basic blocks in the CFGs are split at
43 interprocedural calls, so there can be more than one supernode per
44 basic block. Most statements will be in just one supernode, but a call
45 statement can appear in two supernodes: at the end of one for the call,
46 and again at the start of another for the return.
48 The supergraph can be seen using @option{-fdump-analyzer-supergraph}.
50 We then build an @code{analysis_plan} which walks the callgraph to
51 determine which calls might be suitable for being summarized (rather
52 than fully explored) and thus in what order to explore the functions.
54 Next is the heart of the analyzer: we use a worklist to explore state
55 within the supergraph, building an "exploded graph".
56 Nodes in the exploded graph correspond to <point,@w{ }state> pairs, as in
57 "Precise Interprocedural Dataflow Analysis via Graph Reachability"
58 (Thomas Reps, Susan Horwitz and Mooly Sagiv).
60 We reuse nodes for <point, state> pairs we've already seen, and avoid
61 tracking state too closely, so that (hopefully) we rapidly converge
62 on a final exploded graph, and terminate the analysis. We also bail
63 out if the number of exploded <end-of-basic-block, state> nodes gets
64 larger than a particular multiple of the total number of basic blocks
65 (to ensure termination in the face of pathological state-explosion
66 cases, or bugs). We also stop exploring a point once we hit a limit
67 of states for that point.
69 We can identify problems directly when processing a <point,@w{ }state>
70 instance. For example, if we're finding the successors of
73 <point: before-stmt: "free (ptr);",
74 state: @{"ptr": freed@}>
77 then we can detect a double-free of "ptr". We can then emit a path
78 to reach the problem by finding the simplest route through the graph.
80 Program points in the analysis are much more fine-grained than in the
81 CFG and supergraph, with points (and thus potentially exploded nodes)
82 for various events, including before individual statements.
83 By default the exploded graph merges multiple consecutive statements
84 in a supernode into one exploded edge to minimize the size of the
85 exploded graph. This can be suppressed via
86 @option{-fanalyzer-fine-grained}.
87 The fine-grained approach seems to make things simpler and more debuggable
88 that other approaches I tried, in that each point is responsible for one
91 Program points in the analysis also have a "call string" identifying the
92 stack of callsites below them, so that paths in the exploded graph
93 correspond to interprocedurally valid paths: we always return to the
94 correct call site, propagating state information accordingly.
95 We avoid infinite recursion by stopping the analysis if a callsite
96 appears more than @code{analyzer-max-recursion-depth} in a callstring
101 Nodes and edges in the exploded graph are called ``exploded nodes'' and
102 ``exploded edges'' and often referred to in the code as
103 @code{enodes} and @code{eedges} (especially when distinguishing them
104 from the @code{snodes} and @code{sedges} in the supergraph).
106 Each graph numbers its nodes, giving unique identifiers - supernodes
107 are referred to throughout dumps in the form @samp{SN': @var{index}} and
108 exploded nodes in the form @samp{EN: @var{index}} (e.g. @samp{SN: 2} and
111 The supergraph can be seen using @option{-fdump-analyzer-supergraph-graph}.
113 The exploded graph can be seen using @option{-fdump-analyzer-exploded-graph}
114 and other dump options. Exploded nodes are color-coded in the .dot output
115 based on state-machine states to make it easier to see state changes at
118 @subsection State Tracking
120 There's a tension between:
123 precision of analysis in the straight-line case, vs
125 exponential blow-up in the face of control flow.
128 For example, in general, given this CFG:
142 we want to avoid differences in state-tracking in B and C from
143 leading to blow-up. If we don't prevent state blowup, we end up
144 with exponential growth of the exploded graph like this:
154 4:D 5:D (2 exploded nodes for D)
158 10:G 11:G 12:G 13:G (4 exploded nodes for G)
162 Similar issues arise with loops.
164 To prevent this, we follow various approaches:
168 state pruning: which tries to discard state that won't be relevant
169 later on withing the function.
170 This can be disabled via @option{-fno-analyzer-state-purge}.
173 state merging. We can try to find the commonality between two
174 program_state instances to make a third, simpler program_state.
175 We have two strategies here:
179 the worklist keeps new nodes for the same program_point together,
180 and tries to merge them before processing, and thus before they have
181 successors. Hence, in the above, the two nodes for D (4 and 5) reach
182 the front of the worklist together, and we create a node for D with
183 the merger of the incoming states.
186 try merging with the state of existing enodes for the program_point
187 (which may have already been explored). There will be duplication,
188 but only one set of duplication; subsequent duplicates are more likely
189 to hit the cache. In particular, (hopefully) all merger chains are
190 finite, and so we guarantee termination.
191 This is intended to help with loops: we ought to explore the first
192 iteration, and then have a "subsequent iterations" exploration,
193 which uses a state merged from that of the first, to be more abstract.
196 We avoid merging pairs of states that have state-machine differences,
197 as these are the kinds of differences that are likely to be most
198 interesting. So, for example, given:
206 .... do things with 'ptr'
214 then we end up with an exploded graph that looks like this:
222 ptr = malloc (size) ptr = local_buf
225 "do things with 'ptr'" "do things with 'ptr'"
226 with ptr: heap-allocated with ptr: stack-allocated
228 if (condition) if (condition)
229 | known to be T | known to be F
232 -----------------------------
233 | ('ptr' is pruned, so states can be merged)
238 where some duplication has occurred, but only for the places where the
239 the different paths are worth exploringly separately.
241 Merging can be disabled via @option{-fno-analyzer-state-merge}.
244 @subsection Region Model
246 Part of the state stored at a @code{exploded_node} is a @code{region_model}.
247 This is an implementation of the region-based ternary model described in
248 @url{http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf,
249 "A Memory Model for Static Analysis of C Programs"}
250 (Zhongxing Xu, Ted Kremenek, and Jian Zhang).
252 A @code{region_model} encapsulates a representation of the state of
253 memory, with a @code{store} recording a binding between @code{region}
254 instances, to @code{svalue} instances. The bindings are organized into
255 clusters, where regions accessible via well-defined pointer arithmetic
256 are in the same cluster. The representation is graph-like because values
257 can be pointers to regions. It also stores a constraint_manager,
258 capturing relationships between the values.
260 Because each node in the @code{exploded_graph} has a @code{region_model},
261 and each of the latter is graph-like, the @code{exploded_graph} is in some
262 ways a graph of graphs.
264 Here's an example of printing a @code{program_state}, showing the
265 @code{region_model} within it, along with state for the @code{malloc}
269 (gdb) call debug (*this)
272 frame (index 0): frame: ‘test’@@1
273 clusters within frame: ‘test’@@1
274 cluster for: ptr_3: &HEAP_ALLOCATED_REGION(12)
275 m_called_unknown_fn: FALSE
280 0x2e89590: &HEAP_ALLOCATED_REGION(12): unchecked ('ptr_3')
283 This is the state at the point of returning from @code{calls_malloc} back
284 to @code{test} in the following:
290 void *result = malloc (1024);
296 void *ptr = calls_malloc ();
301 Within the store, there is the cluster for @code{ptr_3} within the frame
302 for @code{test}, where the whole cluster is bound to a pointer value,
303 pointing at @code{HEAP_ALLOCATED_REGION(12)}. Additionally, this pointer
304 has the @code{unchecked} state for the @code{malloc} state machine
305 indicating it hasn't yet been checked against NULL since the allocation
308 @subsection Analyzer Paths
310 We need to explain to the user what the problem is, and to persuade them
311 that there really is a problem. Hence having a @code{diagnostic_path}
312 isn't just an incidental detail of the analyzer; it's required.
317 interprocedurally-valid
322 Without state-merging, all paths in the exploded graph are feasible
323 (in terms of constraints being satisified).
324 With state-merging, paths in the exploded graph can be infeasible.
326 We collate warnings and only emit them for the simplest path
327 e.g. for a bug in a utility function, with lots of routes to calling it,
328 we only emit the simplest path (which could be intraprocedural, if
329 it can be reproduced without a caller). We apply a check that
330 each duplicate warning's shortest path is feasible, rejecting any
331 warnings for which the shortest path is infeasible (which could lead to
334 We use the shortest feasible @code{exploded_path} through the
335 @code{exploded_graph} (a list of @code{exploded_edge *}) to build a
336 @code{diagnostic_path} (a list of events for the diagnostic subsystem) -
337 specifically a @code{checker_path}.
339 Having built the @code{checker_path}, we prune it to try to eliminate
340 events that aren't relevant, to minimize how much the user has to read.
342 After pruning, we notify each event in the path of its ID and record the
343 IDs of interesting events, allowing for events to refer to other events
344 in their descriptions. The @code{pending_diagnostic} class has various
345 vfuncs to support emitting more precise descriptions, so that e.g.
349 a deref-of-unchecked-malloc diagnostic might use:
351 returning possibly-NULL pointer to 'make_obj' from 'allocator'
353 for a @code{return_event} to make it clearer how the unchecked value moves
354 from callee back to caller
356 a double-free diagnostic might use:
358 second 'free' here; first 'free' was at (3)
360 and a use-after-free might use
362 use after 'free' here; memory was freed at (2)
366 At this point we can emit the diagnostic.
368 @subsection Limitations
374 The implementation of call summaries is currently very simplistic.
376 Lack of function pointer analysis
378 The constraint-handling code assumes reflexivity in some places
379 (that values are equal to themselves), which is not the case for NaN.
380 As a simple workaround, constraints on floating-point values are
383 There are various other limitations in the region model (grep for TODO/xfail
386 The constraint_manager's implementation of transitivity is currently too
387 expensive to enable by default and so must be manually enabled via
388 @option{-fanalyzer-transitivity}).
390 The checkers are currently hardcoded and don't allow for user extensibility
391 (e.g. adding allocate/release pairs).
393 Although the analyzer's test suite has a proof-of-concept test case for
394 LTO, LTO support hasn't had extensive testing. There are various
395 lang-specific things in the analyzer that assume C rather than LTO.
396 For example, SSA names are printed to the user in ``raw'' form, rather
397 than printing the underlying variable name.
400 Some ideas for other checkers
403 File-descriptor-based APIs
405 Linux kernel internal APIs
410 @node Debugging the Analyzer
411 @section Debugging the Analyzer
412 @cindex analyzer, debugging
413 @cindex static analyzer, debugging
415 @subsection Special Functions for Debugging the Analyzer
417 The analyzer recognizes various special functions by name, for use
418 in debugging the analyzer. Declarations can be seen in the testsuite
419 in @file{analyzer-decls.h}. None of these functions are actually
426 to the source being analyzed to trigger a breakpoint in the analyzer when
427 that source is reached. By putting a series of these in the source, it's
428 much easier to effectively step through the program state as it's analyzed.
430 The analyzer handles:
433 __analyzer_describe (0, expr);
436 by emitting a warning describing the 2nd argument (which can be of any
437 type), at a verbosity level given by the 1st argument. This is for use when
438 debugging, and may be of use in DejaGnu tests.
444 will dump the copious information about the analyzer's state each time it
445 reaches the call in its traversal of the source.
448 __analyzer_dump_path ();
451 will emit a placeholder ``note'' diagnostic with a path to that call site,
452 if the analyzer finds a feasible path to it.
454 The builtin @code{__analyzer_dump_exploded_nodes} will emit a warning
455 after analysis containing information on all of the exploded nodes at that
459 __analyzer_dump_exploded_nodes (0);
462 will output the number of ``processed'' nodes, and the IDs of
463 both ``processed'' and ``merger'' nodes, such as:
466 warning: 2 processed enodes: [EN: 56, EN: 58] merger(s): [EN: 54-55, EN: 57, EN: 59]
469 With a non-zero argument
472 __analyzer_dump_exploded_nodes (1);
475 it will also dump all of the states within the ``processed'' nodes.
478 __analyzer_dump_region_model ();
480 will dump the region_model's state to stderr.
483 __analyzer_eval (expr);
485 will emit a warning with text "TRUE", FALSE" or "UNKNOWN" based on the
486 truthfulness of the argument. This is useful for writing DejaGnu tests.
489 @subsection Other Debugging Techniques
491 One approach when tracking down where a particular bogus state is
492 introduced into the @code{exploded_graph} is to add custom code to
493 @code{program_state::validate}.