1 @c Copyright (C) 2019-2021 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/~xzx/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
332 false negatives). This check can be suppressed (for debugging purposes)
333 using @option{-fno-analyzer-feasibility}.
335 We use the shortest feasible @code{exploded_path} through the
336 @code{exploded_graph} (a list of @code{exploded_edge *}) to build a
337 @code{diagnostic_path} (a list of events for the diagnostic subsystem) -
338 specifically a @code{checker_path}.
340 Having built the @code{checker_path}, we prune it to try to eliminate
341 events that aren't relevant, to minimize how much the user has to read.
343 After pruning, we notify each event in the path of its ID and record the
344 IDs of interesting events, allowing for events to refer to other events
345 in their descriptions. The @code{pending_diagnostic} class has various
346 vfuncs to support emitting more precise descriptions, so that e.g.
350 a deref-of-unchecked-malloc diagnostic might use:
352 returning possibly-NULL pointer to 'make_obj' from 'allocator'
354 for a @code{return_event} to make it clearer how the unchecked value moves
355 from callee back to caller
357 a double-free diagnostic might use:
359 second 'free' here; first 'free' was at (3)
361 and a use-after-free might use
363 use after 'free' here; memory was freed at (2)
367 At this point we can emit the diagnostic.
369 @subsection Limitations
375 The implementation of call summaries is currently very simplistic.
377 Lack of function pointer analysis
379 The constraint-handling code assumes reflexivity in some places
380 (that values are equal to themselves), which is not the case for NaN.
381 As a simple workaround, constraints on floating-point values are
384 There are various other limitations in the region model (grep for TODO/xfail
387 The constraint_manager's implementation of transitivity is currently too
388 expensive to enable by default and so must be manually enabled via
389 @option{-fanalyzer-transitivity}).
391 The checkers are currently hardcoded and don't allow for user extensibility
392 (e.g. adding allocate/release pairs).
394 Although the analyzer's test suite has a proof-of-concept test case for
395 LTO, LTO support hasn't had extensive testing. There are various
396 lang-specific things in the analyzer that assume C rather than LTO.
397 For example, SSA names are printed to the user in ``raw'' form, rather
398 than printing the underlying variable name.
401 Some ideas for other checkers
404 File-descriptor-based APIs
406 Linux kernel internal APIs
411 @node Debugging the Analyzer
412 @section Debugging the Analyzer
413 @cindex analyzer, debugging
414 @cindex static analyzer, debugging
416 @subsection Special Functions for Debugging the Analyzer
418 The analyzer recognizes various special functions by name, for use
419 in debugging the analyzer. Declarations can be seen in the testsuite
420 in @file{analyzer-decls.h}. None of these functions are actually
427 to the source being analyzed to trigger a breakpoint in the analyzer when
428 that source is reached. By putting a series of these in the source, it's
429 much easier to effectively step through the program state as it's analyzed.
431 The analyzer handles:
434 __analyzer_describe (0, expr);
437 by emitting a warning describing the 2nd argument (which can be of any
438 type), at a verbosity level given by the 1st argument. This is for use when
439 debugging, and may be of use in DejaGnu tests.
445 will dump the copious information about the analyzer's state each time it
446 reaches the call in its traversal of the source.
449 __analyzer_dump_path ();
452 will emit a placeholder ``note'' diagnostic with a path to that call site,
453 if the analyzer finds a feasible path to it.
455 The builtin @code{__analyzer_dump_exploded_nodes} will emit a warning
456 after analysis containing information on all of the exploded nodes at that
460 __analyzer_dump_exploded_nodes (0);
463 will output the number of ``processed'' nodes, and the IDs of
464 both ``processed'' and ``merger'' nodes, such as:
467 warning: 2 processed enodes: [EN: 56, EN: 58] merger(s): [EN: 54-55, EN: 57, EN: 59]
470 With a non-zero argument
473 __analyzer_dump_exploded_nodes (1);
476 it will also dump all of the states within the ``processed'' nodes.
479 __analyzer_dump_region_model ();
481 will dump the region_model's state to stderr.
484 __analyzer_eval (expr);
486 will emit a warning with text "TRUE", FALSE" or "UNKNOWN" based on the
487 truthfulness of the argument. This is useful for writing DejaGnu tests.
490 @subsection Other Debugging Techniques
492 The option @option{-fdump-analyzer-json} will dump both the supergraph
493 and the exploded graph in compressed JSON form.
495 One approach when tracking down where a particular bogus state is
496 introduced into the @code{exploded_graph} is to add custom code to
497 @code{program_state::validate}.