1 @c Copyright (C) 2019-2023 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{https://www.researchgate.net/publication/221430855_A_Memory_Model_for_Static_Analysis_of_C_Programs,
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 satisfied).
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).
331 We thus want to find the shortest feasible path through the exploded
332 graph from the origin to the exploded node at which the diagnostic was
333 saved. Unfortunately, if we simply find the shortest such path and
334 check if it's feasible we might falsely reject the diagnostic, as there
335 might be a longer path that is feasible. Examples include the cases
336 where the diagnostic requires us to go at least once around a loop for a
337 later condition to be satisfied, or where for a later condition to be
338 satisfied we need to enter a suite of code that the simpler path skips.
340 We attempt to find the shortest feasible path to each diagnostic by
341 first constructing a ``trimmed graph'' from the exploded graph,
342 containing only those nodes and edges from which there are paths to
343 the target node, and using Dijkstra's algorithm to order the trimmed
344 nodes by minimal distance to the target.
346 We then use a worklist to iteratively build a ``feasible graph''
347 (actually a tree), capturing the pertinent state along each path, in
348 which every path to a ``feasible node'' is feasible by construction,
349 restricting ourselves to the trimmed graph to ensure we stay on target,
350 and ordering the worklist so that the first feasible path we find to the
351 target node is the shortest possible path. Hence we start by trying the
352 shortest possible path, but if that fails, we explore progressively
353 longer paths, eventually trying iterations through loops. The
354 exploration is captured in the feasible_graph, which can be dumped as a
355 .dot file via @option{-fdump-analyzer-feasibility} to visualize the
356 exploration. The indices of the feasible nodes show the order in which
357 they were created. We effectively explore the tree of feasible paths in
358 order of shortest path until we either find a feasible path to the
359 target node, or hit a limit and give up.
361 This is something of a brute-force approach, but the trimmed graph
362 hopefully keeps the complexity manageable.
364 This algorithm can be disabled (for debugging purposes) via
365 @option{-fno-analyzer-feasibility}, which simply uses the shortest path,
366 and notes if it is infeasible.
368 The above gives us a shortest feasible @code{exploded_path} through the
369 @code{exploded_graph} (a list of @code{exploded_edge *}). We use this
370 @code{exploded_path} to build a @code{diagnostic_path} (a list of
371 @strong{events} for the diagnostic subsystem) - specifically a
374 Having built the @code{checker_path}, we prune it to try to eliminate
375 events that aren't relevant, to minimize how much the user has to read.
377 After pruning, we notify each event in the path of its ID and record the
378 IDs of interesting events, allowing for events to refer to other events
379 in their descriptions. The @code{pending_diagnostic} class has various
380 vfuncs to support emitting more precise descriptions, so that e.g.
384 a deref-of-unchecked-malloc diagnostic might use:
386 returning possibly-NULL pointer to 'make_obj' from 'allocator'
388 for a @code{return_event} to make it clearer how the unchecked value moves
389 from callee back to caller
391 a double-free diagnostic might use:
393 second 'free' here; first 'free' was at (3)
395 and a use-after-free might use
397 use after 'free' here; memory was freed at (2)
401 At this point we can emit the diagnostic.
403 @subsection Limitations
409 The implementation of call summaries is currently very simplistic.
411 Lack of function pointer analysis
413 The constraint-handling code assumes reflexivity in some places
414 (that values are equal to themselves), which is not the case for NaN.
415 As a simple workaround, constraints on floating-point values are
418 There are various other limitations in the region model (grep for TODO/xfail
421 The constraint_manager's implementation of transitivity is currently too
422 expensive to enable by default and so must be manually enabled via
423 @option{-fanalyzer-transitivity}).
425 The checkers are currently hardcoded and don't allow for user extensibility
426 (e.g. adding allocate/release pairs).
428 Although the analyzer's test suite has a proof-of-concept test case for
429 LTO, LTO support hasn't had extensive testing. There are various
430 lang-specific things in the analyzer that assume C rather than LTO.
431 For example, SSA names are printed to the user in ``raw'' form, rather
432 than printing the underlying variable name.
435 @node Debugging the Analyzer
436 @section Debugging the Analyzer
437 @cindex analyzer, debugging
438 @cindex static analyzer, debugging
440 When debugging the analyzer I normally use all of these options
448 -wrapper gdb,--args \
449 -fdump-analyzer-stderr \
450 -fanalyzer-fine-grained \
451 -fdump-ipa-analyzer=stderr
457 @item @code{./xgcc -B.}
458 is the usual way to invoke a self-built GCC from within the @file{BUILDDIR/gcc}
462 so that the driver (@code{./xgcc}) invokes @code{cc1}, but doesn't bother
463 running the assembler or linker (since the analyzer runs inside @code{cc1}).
465 @item @code{-fanalyzer}
466 enables the analyzer, obviously.
468 @item @code{-wrapper gdb,--args}
469 invokes @code{cc1} under the debugger so that I can debug @code{cc1} and
470 set breakpoints and step through things.
472 @item @code{-fdump-analyzer-stderr}
473 so that the logging interface is enabled and goes to stderr, which often
474 gives valuable context into what's happening when stepping through the
477 @item @code{-fanalyzer-fine-grained}
478 which splits the effect of every statement into its own
479 exploded_node, rather than the default (which tries to combine
480 successive stmts to reduce the size of the exploded_graph). This makes
481 it easier to see exactly where a particular change happens.
483 @item @code{-fdump-ipa-analyzer=stderr}
484 which dumps the GIMPLE IR seen by the analyzer pass to stderr
488 Other useful options:
491 @item @code{-fdump-analyzer-exploded-graph}
492 which dumps a @file{SRC.eg.dot} GraphViz file that I can look at (with
495 @item @code{-fdump-analyzer-exploded-nodes-2}
496 which dumps a @file{SRC.eg.txt} file containing the full @code{exploded_graph}.
500 Assuming that you have the
501 @uref{https://gcc-newbies-guide.readthedocs.io/en/latest/debugging.html,,python support scripts for gdb}
502 installed, you can use:
505 (gdb) break-on-saved-diagnostic
508 to put a breakpoint at the place where a diagnostic is saved during
509 @code{exploded_graph} exploration, to see where a particular diagnostic
513 (gdb) break-on-diagnostic
516 to put a breakpoint at the place where diagnostics are actually emitted.
518 @subsection Special Functions for Debugging the Analyzer
520 The analyzer recognizes various special functions by name, for use
521 in debugging the analyzer, and for use in DejaGnu tests.
523 The declarations of these functions can be seen in the testsuite
524 in @file{analyzer-decls.h}. None of these functions are actually
525 implemented in terms of code, merely as @code{known_function} subclasses
526 (in @file{gcc/analyzer/kf-analyzer.cc}).
530 @item __analyzer_break
535 to the source being analyzed to trigger a breakpoint in the analyzer when
536 that source is reached. By putting a series of these in the source, it's
537 much easier to effectively step through the program state as it's analyzed.
539 @item __analyzer_describe
540 The analyzer handles:
543 __analyzer_describe (0, expr);
546 by emitting a warning describing the 2nd argument (which can be of any
547 type), at a verbosity level given by the 1st argument. This is for use when
548 debugging, and may be of use in DejaGnu tests.
550 @item __analyzer_dump
555 will dump the copious information about the analyzer's state each time it
556 reaches the call in its traversal of the source.
558 @item __analyzer_dump_capacity
560 extern void __analyzer_dump_capacity (const void *ptr);
563 will emit a warning describing the capacity of the base region of
564 the region pointed to by the 1st argument.
566 @item __analyzer_dump_escaped
568 extern void __analyzer_dump_escaped (void);
571 will emit a warning giving the number of decls that have escaped on this
572 analysis path, followed by a comma-separated list of their names,
573 in alphabetical order.
575 @item __analyzer_dump_path
577 __analyzer_dump_path ();
580 will emit a placeholder ``note'' diagnostic with a path to that call site,
581 if the analyzer finds a feasible path to it. This can be useful for
582 writing DejaGnu tests for constraint-tracking and feasibility checking.
584 @item __analyzer_dump_exploded_nodes
585 For every callsite to @code{__analyzer_dump_exploded_nodes} the analyzer
586 will emit a warning after it finished the analysis containing information
587 on all of the exploded nodes at that program point.
590 __analyzer_dump_exploded_nodes (0);
593 will output the number of ``processed'' nodes, and the IDs of
594 both ``processed'' and ``merger'' nodes, such as:
597 warning: 2 processed enodes: [EN: 56, EN: 58] merger(s): [EN: 54-55, EN: 57, EN: 59]
600 With a non-zero argument
603 __analyzer_dump_exploded_nodes (1);
606 it will also dump all of the states within the ``processed'' nodes.
608 @item __analyzer_dump_named_constant
609 When the analyzer sees a call to @code{__analyzer_dump_named_constant} it
610 will emit a warning describing what is known about the value of a given
611 named constant, for parts of the analyzer that interact with target
617 __analyzer_dump_named_constant ("O_RDONLY");
620 might lead to the analyzer emitting the warning:
623 warning: named constant 'O_RDONLY' has value '1'
626 @item __analyzer_dump_region_model
628 __analyzer_dump_region_model ();
630 will dump the region_model's state to stderr.
632 @item __analyzer_dump_state
634 __analyzer_dump_state ("malloc", ptr);
637 will emit a warning describing the state of the 2nd argument
638 (which can be of any type) with respect to the state machine with
639 a name matching the 1st argument (which must be a string literal).
640 This is for use when debugging, and may be of use in DejaGnu tests.
642 @item __analyzer_eval
644 __analyzer_eval (expr);
646 will emit a warning with text "TRUE", FALSE" or "UNKNOWN" based on the
647 truthfulness of the argument. This is useful for writing DejaGnu tests.
649 @item __analyzer_get_unknown_ptr
651 __analyzer_get_unknown_ptr ();
653 will obtain an unknown @code{void *}.
655 @item __analyzer_get_strlen
657 __analyzer_get_strlen (buf);
659 will emit a warning if PTR doesn't point to a null-terminated string.
660 TODO: eventually get the strlen of the buffer (without the
661 optimizer touching it).
665 @subsection Other Debugging Techniques
667 To compare two different exploded graphs, try
668 @code{-fdump-analyzer-exploded-nodes-2 -fdump-noaddr -fanalyzer-fine-grained}.
669 This will dump a @file{SRC.eg.txt} file containing the full
670 @code{exploded_graph}. I use @code{diff -u50 -p} to compare two different
671 such files (e.g. before and after a patch) to find the first place where the
672 two graphs diverge. The option @option{-fdump-noaddr} will suppress
673 printing pointers withihn the dumps (which would otherwise hide the real
674 differences with irrelevent churn).
676 The option @option{-fdump-analyzer-json} will dump both the supergraph
677 and the exploded graph in compressed JSON form.
679 One approach when tracking down where a particular bogus state is
680 introduced into the @code{exploded_graph} is to add custom code to
681 @code{program_state::validate}.
683 The debug function @code{region::is_named_decl_p} can be used when debugging,
684 such as for assertions and conditional breakpoints. For example, when
685 tracking down a bug in handling a decl called @code{yy_buffer_stack}, I
688 gcc_assert (!m_base_region->is_named_decl_p ("yy_buffer_stack"));
690 to @code{binding_cluster::mark_as_escaped} to trap a point where
691 @code{yy_buffer_stack} was mistakenly being treated as having escaped.