[PATCH 02/49] analyzer: internal documentation
David Malcolm
dmalcolm@redhat.com
Sat Nov 16 01:17:00 GMT 2019
gcc/ChangeLog:
* Makefile.in (TEXI_GCCINT_FILES): Add analyzer.texi.
* doc/analyzer.texi: New file.
* doc/gccint.texi ("Static Analyzer") New menu item.
(analyzer.texi): Include it.
---
gcc/Makefile.in | 2 +-
gcc/doc/analyzer.texi | 470 ++++++++++++++++++++++++++++++++++++++++++++++++++
gcc/doc/gccint.texi | 2 +
3 files changed, 473 insertions(+), 1 deletion(-)
create mode 100644 gcc/doc/analyzer.texi
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index c82858f..53d74e2 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -3182,7 +3182,7 @@ TEXI_GCCINT_FILES = gccint.texi gcc-common.texi gcc-vers.texi \
gnu.texi gpl_v3.texi fdl.texi contrib.texi languages.texi \
sourcebuild.texi gty.texi libgcc.texi cfg.texi tree-ssa.texi \
loop.texi generic.texi gimple.texi plugins.texi optinfo.texi \
- match-and-simplify.texi ux.texi poly-int.texi
+ match-and-simplify.texi analyzer.texi ux.texi poly-int.texi
TEXI_GCCINSTALL_FILES = install.texi install-old.texi fdl.texi \
gcc-common.texi gcc-vers.texi
diff --git a/gcc/doc/analyzer.texi b/gcc/doc/analyzer.texi
new file mode 100644
index 0000000..8e7b26f
--- /dev/null
+++ b/gcc/doc/analyzer.texi
@@ -0,0 +1,470 @@
+@c Copyright (C) 2019 Free Software Foundation, Inc.
+@c This is part of the GCC manual.
+@c For copying conditions, see the file gcc.texi.
+@c Contributed by David Malcolm <dmalcolm@redhat.com>.
+
+@node Static Analyzer
+@chapter Static Analyzer
+@cindex analyzer
+@cindex static analysis
+@cindex static analyzer
+
+@menu
+* Analyzer Internals:: Analyzer Internals
+* Debugging the Analyzer:: Useful debugging tips
+@end menu
+
+@node Analyzer Internals
+@section Analyzer Internals
+@cindex analyzer, internals
+@cindex static analyzer, internals
+
+@subsection Overview
+
+The analyzer implementation works on the gimple-SSA representation.
+(I chose this in the hopes of making it easy to work with LTO to
+do whole-program analysis).
+
+The implementation is read-only: it doesn't attempt to change anything,
+just emit warnings.
+
+First, we build a @code{supergraph} which combines the callgraph and all
+of the CFGs into a single directed graph, with both interprocedural and
+intraprocedural edges. The nodes and edges in the supergraph are called
+``supernodes'' and ``superedges'', and often referred to in code as
+@code{snodes} and @code{sedges}. Basic blocks in the CFGs are split at
+interprocedural calls, so there can be more than one supernode per
+basic block. Most statements will be in just one supernode, but a call
+statement can appear in two supernodes: at the end of one for the call,
+and again at the start of another for the return.
+
+The supergraph can be seen using @option{-fdump-analyzer-supergraph}.
+
+We then build an @code{analysis_plan} which walks the callgraph to
+determine which calls might be suitable for being summarized (rather
+than fully explored) and thus in what order to explore the functions.
+
+Next is the heart of the analyzer: we use a worklist to explore state
+within the supergraph, building an "exploded graph".
+Nodes in the exploded graph correspond to <point,@w{ }state> pairs, as in
+ "Precise Interprocedural Dataflow Analysis via Graph Reachability"
+ (Thomas Reps, Susan Horwitz and Mooly Sagiv).
+
+We reuse nodes for <point, state> pairs we've already seen, and avoid
+tracking state too closely, so that (hopefully) we rapidly converge
+on a final exploded graph, and terminate the analysis. We also bail
+out if the number of exploded <end-of-basic-block, state> nodes gets
+larger than a particular multiple of the total number of basic blocks
+(to ensure termination in the face of pathological state-explosion
+cases, or bugs). We also stop exploring a point once we hit a limit
+of states for that point.
+
+We can identify problems directly when processing a <point,@w{ }state>
+instance. For example, if we're finding the successors of
+
+@smallexample
+ <point: before-stmt: "free (ptr);",
+ state: @{"ptr": freed@}>
+@end smallexample
+
+then we can detect a double-free of "ptr". We can then emit a path
+to reach the problem by finding the simplest route through the graph.
+
+Program points in the analysis are much more fine-grained than in the
+CFG and supergraph, with points (and thus potentially exploded nodes)
+for various events, including before individual statements.
+By default the exploded graph merges multiple consecutive statements
+in a supernode into one exploded edge to minimize the size of the
+exploded graph. This can be suppressed via
+@option{-fanalyzer-fine-grained}.
+The fine-grained approach seems to make things simpler and more debuggable
+that other approaches I tried, in that each point is responsible for one
+thing.
+
+Program points in the analysis also have a "call string" identifying the
+stack of callsites below them, so that paths in the exploded graph
+correspond to interprocedurally valid paths: we always return to the
+correct call site, propagating state information accordingly.
+We avoid infinite recursion by stopping the analysis if a callsite
+appears more than @code{analyzer-max-recursion-depth} in a callstring
+(defaulting to 2).
+
+@subsection Graphs
+
+Nodes and edges in the exploded graph are called ``exploded nodes'' and
+``exploded edges'' and often referred to in the code as
+@code{enodes} and @code{eedges} (especially when distinguishing them
+from the @code{snodes} and @code{sedges} in the supergraph).
+
+Each graph numbers its nodes, giving unique identifiers - supernodes
+are referred to throughout dumps in the form @samp{SN': @var{index}} and
+exploded nodes in the form @samp{EN: @var{index}} (e.g. @samp{SN: 2} and
+@samp{EN:29}).
+
+The supergraph can be seen using @option{-fdump-analyzer-supergraph-graph}.
+
+The exploded graph can be seen using @option{-fdump-analyzer-exploded-graph}
+and other dump options. Exploded nodes are color-coded in the .dot output
+based on state-machine states to make it easier to see state changes at
+a glance.
+
+@subsection State Tracking
+
+There's a tension between:
+@itemize @bullet
+@item
+precision of analysis in the straight-line case, vs
+@item
+exponential blow-up in the face of control flow.
+@end itemize
+
+For example, in general, given this CFG:
+
+@smallexample
+ A
+ / \
+ B C
+ \ /
+ D
+ / \
+ E F
+ \ /
+ G
+@end smallexample
+
+we want to avoid differences in state-tracking in B and C from
+leading to blow-up. If we don't prevent state blowup, we end up
+with exponential growth of the exploded graph like this:
+
+@smallexample
+
+ 1:A
+ / \
+ / \
+ / \
+ 2:B 3:C
+ | |
+ 4:D 5:D (2 exploded nodes for D)
+ / \ / \
+ 6:E 7:F 8:E 9:F
+ | | | |
+ 10:G 11:G 12:G 13:G (4 exploded nodes for G)
+
+@end smallexample
+
+Similar issues arise with loops.
+
+To prevent this, we follow various approaches:
+
+@enumerate a
+@item
+state pruning: which tries to discard state that won't be relevant
+later on withing the function.
+This can be disabled via @option{-fno-analyzer-state-purge}.
+
+@item
+state merging. We can try to find the commonality between two
+program_state instances to make a third, simpler program_state.
+We have two strategies here:
+
+ @enumerate
+ @item
+ the worklist keeps new nodes for the same program_point together,
+ and tries to merge them before processing, and thus before they have
+ successors. Hence, in the above, the two nodes for D (4 and 5) reach
+ the front of the worklist together, and we create a node for D with
+ the merger of the incoming states.
+
+ @item
+ try merging with the state of existing enodes for the program_point
+ (which may have already been explored). There will be duplication,
+ but only one set of duplication; subsequent duplicates are more likely
+ to hit the cache. In particular, (hopefully) all merger chains are
+ finite, and so we guarantee termination.
+ This is intended to help with loops: we ought to explore the first
+ iteration, and then have a "subsequent iterations" exploration,
+ which uses a state merged from that of the first, to be more abstract.
+ @end enumerate
+
+We avoid merging pairs of states that have state-machine differences,
+as these are the kinds of differences that are likely to be most
+interesting. So, for example, given:
+
+@smallexample
+ if (condition)
+ ptr = malloc (size);
+ else
+ ptr = local_buf;
+
+ .... do things with 'ptr'
+
+ if (condition)
+ free (ptr);
+
+ ...etc
+@end smallexample
+
+then we end up with an exploded graph that looks like this:
+
+@smallexample
+
+ if (condition)
+ / T \ F
+ --------- ----------
+ / \
+ ptr = malloc (size) ptr = local_buf
+ | |
+ copy of copy of
+ "do things with 'ptr'" "do things with 'ptr'"
+ with ptr: heap-allocated with ptr: stack-allocated
+ | |
+ if (condition) if (condition)
+ | known to be T | known to be F
+ free (ptr); |
+ \ /
+ -----------------------------
+ | ('ptr' is pruned, so states can be merged)
+ etc
+
+@end smallexample
+
+where some duplication has occurred, but only for the places where the
+the different paths are worth exploringly separately.
+
+Merging can be disabled via @option{-fno-analyzer-state-merge}.
+@end enumerate
+
+@subsection Region Model
+
+Part of the state stored at a @code{exploded_node} is a @code{region_model}.
+This is an implementation of the region-based ternary model described in
+@url{http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf,
+"A Memory Model for Static Analysis of C Programs"}
+(Zhongxing Xu, Ted Kremenek, and Jian Zhang).
+
+A @code{region_model} encapsulates a representation of the state of
+memory, with a tree of @code{region} instances, along with their associated
+values. The representation is graph-like because values can be pointers
+to regions. It also stores a constraint_manager, capturing relationships
+between the values.
+
+Because each node in the @code{exploded_graph} has a @code{region_model},
+and each of the latter is graph-like, the @code{exploded_graph} is in some
+ways a graph of graphs.
+
+Here's an example of printing a @code{region_model}, showing the ASCII-art
+used to visualize the region hierarchy (colorized when printing to stderr):
+
+@smallexample
+(gdb) call debug (*this)
+r0: @{kind: 'root', parent: null, sval: null@}
+|-stack: r1: @{kind: 'stack', parent: r0, sval: sv1@}
+| |: sval: sv1: @{poisoned: uninit@}
+| |-frame for 'test': r2: @{kind: 'frame', parent: r1, sval: null, map: @{'ptr_3': r3@}, function: 'test', depth: 0@}
+| | `-'ptr_3': r3: @{kind: 'map', parent: r2, sval: sv3, type: 'void *', map: @{@}@}
+| | |: sval: sv3: @{type: 'void *', unknown@}
+| | |: type: 'void *'
+| `-frame for 'calls_malloc': r4: @{kind: 'frame', parent: r1, sval: null, map: @{'result_3': r7, '_4': r8, '<anonymous>': r5@}, function: 'calls_malloc', depth: 1@}
+| |-'<anonymous>': r5: @{kind: 'map', parent: r4, sval: sv4, type: 'void *', map: @{@}@}
+| | |: sval: sv4: @{type: 'void *', &r6@}
+| | |: type: 'void *'
+| |-'result_3': r7: @{kind: 'map', parent: r4, sval: sv4, type: 'void *', map: @{@}@}
+| | |: sval: sv4: @{type: 'void *', &r6@}
+| | |: type: 'void *'
+| `-'_4': r8: @{kind: 'map', parent: r4, sval: sv4, type: 'void *', map: @{@}@}
+| |: sval: sv4: @{type: 'void *', &r6@}
+| |: type: 'void *'
+`-heap: r9: @{kind: 'heap', parent: r0, sval: sv2@}
+ |: sval: sv2: @{poisoned: uninit@}
+ `-r6: @{kind: 'symbolic', parent: r9, sval: null, map: @{@}@}
+svalues:
+ sv0: @{type: 'size_t', '1024'@}
+ sv1: @{poisoned: uninit@}
+ sv2: @{poisoned: uninit@}
+ sv3: @{type: 'void *', unknown@}
+ sv4: @{type: 'void *', &r6@}
+constraint manager:
+ equiv classes:
+ ec0: @{sv0 == '1024'@}
+ ec1: @{sv4@}
+ constraints:
+@end smallexample
+
+This is the state at the point of returning from @code{calls_malloc} back
+to @code{test} in the following:
+
+@smallexample
+void *
+calls_malloc (void)
+@{
+ void *result = malloc (1024);
+ return result;
+@}
+
+void test (void)
+@{
+ void *ptr = calls_malloc ();
+ /* etc. */
+@}
+@end smallexample
+
+The ``root'' region (``r0'') has a ``stack'' child (``r1''), with two
+children: a frame for @code{test} (``r2''), and a frame for
+@code{calls_malloc} (``r4''). These frame regions have child regions for
+storing their local variables. For example, the return region
+and that of various other regions within the ``calls_malloc'' frame all have
+value ``sv4'', a pointer to a heap-allocated region ``r6''. Within the parent
+frame, @code{ptr_3} has value ``sv3'', an unknown @code{void *}.
+
+@subsection Analyzer Paths
+
+We need to explain to the user what the problem is, and to persuade them
+that there really is a problem. Hence having a @code{diagnostic_path}
+isn't just an incidental detail of the analyzer; it's required.
+
+Paths ought to be:
+@itemize @bullet
+@item
+interprocedurally-valid
+@item
+feasible
+@end itemize
+
+Without state-merging, all paths in the exploded graph are feasible
+(in terms of constraints being satisified).
+With state-merging, paths in the exploded graph can be infeasible.
+
+We collate warnings and only emit them for the simplest path
+e.g. for a bug in a utility function, with lots of routes to calling it,
+we only emit the simplest path (which could be intraprocedural, if
+it can be reproduced without a caller). We apply a check that
+each duplicate warning's shortest path is feasible, rejecting any
+warnings for which the shortest path is infeasible (which could lead to
+false negatives).
+
+We use the shortest feasible path through the exploded_graph (a list of
+edges) to build a @code{diagnostic_path} (a list of events for the
+diagnostic subsystem).
+
+@subsection Limitations
+
+@itemize @bullet
+@item
+Only for C so far
+@item
+The implementation of call summaries is currently very simplistic.
+@item
+Lack of function pointer analysis
+@item
+The region model code creates lots of little mutable objects at each
+@code{region_model} (and thus per @code{exploded_node}) rather than
+sharing immutable objects and having the mutable state in the
+@code{program_state} or @code{region_model}. The latter approach might be
+more efficient, and might avoid dealing with IDs rather than pointers
+(which requires us to impose an ordering to get meaningful equality).
+@item
+The region model code doesn't yet support @code{memcpy}. At the
+gimple-ssa level these have been optimized to statements like this:
+@smallexample
+_10 = MEM <long unsigned int> [(char * @{ref-all@})&c]
+MEM <long unsigned int> [(char * @{ref-all@})&d] = _10;
+@end smallexample
+Perhaps they could be supported via a new @code{compound_svalue} type.
+@item
+There are various other limitations in the region model (grep for TODO/xfail
+in the testsuite).
+@item
+The constraint_manager's implementation of transitivity is currently too
+expensive to enable by default and so must be manually enabled via
+@option{-fanalyzer-transitivity}).
+@item
+The checkers are currently hardcoded and don't allow for user extensibility
+(e.g. adding allocate/release pairs).
+@item
+Although the analyzer's test suite has a proof-of-concept test case for
+LTO, it will crash on anything non-trivial. There are various
+lang-specific things in the analyzer that assume C rather than LTO.
+For example, casts are currently implemented via @code{convert}, and this
+leads to an ICE on LTO. Similarly, SSA names are printed to the user in
+``raw'' form, rather than printing the underlying variable name.
+@end itemize
+
+Some ideas for other checkers
+@itemize @bullet
+@item
+File-descriptor-based APIs
+@item
+Linux kernel internal APIs
+@item
+Signal handling
+@end itemize
+
+@node Debugging the Analyzer
+@section Debugging the Analyzer
+@cindex analyzer, debugging
+@cindex static analyzer, debugging
+
+@subsection Builtins for Debugging the Analyzer
+
+Add:
+@smallexample
+ __analyzer_break ();
+@end smallexample
+to the source being analyzed to trigger a breakpoint in the analyzer when
+that source is reached. By putting a series of these in the source, it's
+much easier to effectively step through the program state as it's analyzed.
+
+@smallexample
+__analyzer_dump ();
+@end smallexample
+
+will dump the copious information about the analyzer's state each time it
+reaches the call in its traversal of the source.
+
+@smallexample
+__analyzer_dump_path ();
+@end smallexample
+
+will emit a placeholder ``note'' diagnostic with a path to that call site,
+if the analyzer finds a feasible path to it.
+
+The builtin @code{__analyzer_dump_exploded_nodes} will dump information
+after analysis on all of the exploded nodes at that program point:
+
+@smallexample
+ __analyzer_dump_exploded_nodes (0);
+@end smallexample
+
+will dump just the number of nodes, and their IDs.
+
+@smallexample
+ __analyzer_dump_exploded_nodes (1);
+@end smallexample
+
+will also dump all of the states within those nodes.
+
+@code{region_model::get_value_by_name} can be used when inserting custom
+debugging code (e.g. adding it @code{region_model::validate} to detect the
+point at which a named variable acquires an unexpected state).
+
+@subsection Other Debugging Techniques
+
+One approach when tracking down where a particular bogus state is
+introduced into the @code{exploded_graph} is to add custom code to
+@code{region_model::validate}.
+
+For example, this custom code breaks with an assertion failure when a
+variable called @code{ptr} acquires a value that's unknown:
+
+@smallexample
+
+ /* Find a variable matching "ptr". */
+ svalue_id sid = get_value_by_name ("ptr");
+ if (!sid.null_p ())
+ @{
+ svalue *sval = get_svalue (sid);
+ gcc_assert (sval->get_kind () != SK_UNKNOWN);
+ @}
+@end smallexample
+
+making it easier to investigate further in a debugger when this occurs.
diff --git a/gcc/doc/gccint.texi b/gcc/doc/gccint.texi
index 99ec005..9dd935d 100644
--- a/gcc/doc/gccint.texi
+++ b/gcc/doc/gccint.texi
@@ -125,6 +125,7 @@ Additional tutorial information is linked to from
* LTO:: Using Link-Time Optimization.
* Match and Simplify:: How to write expression simplification patterns for GIMPLE and GENERIC
+* Static Analyzer:: Working with the static analyzer.
* User Experience Guidelines:: Guidelines for implementing diagnostics and options.
* Funding:: How to help assure funding for free software.
* GNU Project:: The GNU Project and GNU/Linux.
@@ -163,6 +164,7 @@ Additional tutorial information is linked to from
@include plugins.texi
@include lto.texi
@include match-and-simplify.texi
+@include analyzer.texi
@include ux.texi
@include funding.texi
--
1.8.5.3
More information about the Gcc-patches
mailing list