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>. 5 6@node Static Analyzer 7@chapter Static Analyzer 8@cindex analyzer 9@cindex static analysis 10@cindex static analyzer 11 12@menu 13* Analyzer Internals:: Analyzer Internals 14* Debugging the Analyzer:: Useful debugging tips 15@end menu 16 17@node Analyzer Internals 18@section Analyzer Internals 19@cindex analyzer, internals 20@cindex static analyzer, internals 21 22@subsection Overview 23 24The analyzer implementation works on the gimple-SSA representation. 25(I chose this in the hopes of making it easy to work with LTO to 26do whole-program analysis). 27 28The implementation is read-only: it doesn't attempt to change anything, 29just emit warnings. 30 31The gimple representation can be seen using @option{-fdump-ipa-analyzer}. 32 33First, we build a @code{supergraph} which combines the callgraph and all 34of the CFGs into a single directed graph, with both interprocedural and 35intraprocedural edges. The nodes and edges in the supergraph are called 36``supernodes'' and ``superedges'', and often referred to in code as 37@code{snodes} and @code{sedges}. Basic blocks in the CFGs are split at 38interprocedural calls, so there can be more than one supernode per 39basic block. Most statements will be in just one supernode, but a call 40statement can appear in two supernodes: at the end of one for the call, 41and again at the start of another for the return. 42 43The supergraph can be seen using @option{-fdump-analyzer-supergraph}. 44 45We then build an @code{analysis_plan} which walks the callgraph to 46determine which calls might be suitable for being summarized (rather 47than fully explored) and thus in what order to explore the functions. 48 49Next is the heart of the analyzer: we use a worklist to explore state 50within the supergraph, building an "exploded graph". 51Nodes in the exploded graph correspond to <point,@w{ }state> pairs, as in 52 "Precise Interprocedural Dataflow Analysis via Graph Reachability" 53 (Thomas Reps, Susan Horwitz and Mooly Sagiv). 54 55We reuse nodes for <point, state> pairs we've already seen, and avoid 56tracking state too closely, so that (hopefully) we rapidly converge 57on a final exploded graph, and terminate the analysis. We also bail 58out if the number of exploded <end-of-basic-block, state> nodes gets 59larger than a particular multiple of the total number of basic blocks 60(to ensure termination in the face of pathological state-explosion 61cases, or bugs). We also stop exploring a point once we hit a limit 62of states for that point. 63 64We can identify problems directly when processing a <point,@w{ }state> 65instance. For example, if we're finding the successors of 66 67@smallexample 68 <point: before-stmt: "free (ptr);", 69 state: @{"ptr": freed@}> 70@end smallexample 71 72then we can detect a double-free of "ptr". We can then emit a path 73to reach the problem by finding the simplest route through the graph. 74 75Program points in the analysis are much more fine-grained than in the 76CFG and supergraph, with points (and thus potentially exploded nodes) 77for various events, including before individual statements. 78By default the exploded graph merges multiple consecutive statements 79in a supernode into one exploded edge to minimize the size of the 80exploded graph. This can be suppressed via 81@option{-fanalyzer-fine-grained}. 82The fine-grained approach seems to make things simpler and more debuggable 83that other approaches I tried, in that each point is responsible for one 84thing. 85 86Program points in the analysis also have a "call string" identifying the 87stack of callsites below them, so that paths in the exploded graph 88correspond to interprocedurally valid paths: we always return to the 89correct call site, propagating state information accordingly. 90We avoid infinite recursion by stopping the analysis if a callsite 91appears more than @code{analyzer-max-recursion-depth} in a callstring 92(defaulting to 2). 93 94@subsection Graphs 95 96Nodes and edges in the exploded graph are called ``exploded nodes'' and 97``exploded edges'' and often referred to in the code as 98@code{enodes} and @code{eedges} (especially when distinguishing them 99from the @code{snodes} and @code{sedges} in the supergraph). 100 101Each graph numbers its nodes, giving unique identifiers - supernodes 102are referred to throughout dumps in the form @samp{SN': @var{index}} and 103exploded nodes in the form @samp{EN: @var{index}} (e.g. @samp{SN: 2} and 104@samp{EN:29}). 105 106The supergraph can be seen using @option{-fdump-analyzer-supergraph-graph}. 107 108The exploded graph can be seen using @option{-fdump-analyzer-exploded-graph} 109and other dump options. Exploded nodes are color-coded in the .dot output 110based on state-machine states to make it easier to see state changes at 111a glance. 112 113@subsection State Tracking 114 115There's a tension between: 116@itemize @bullet 117@item 118precision of analysis in the straight-line case, vs 119@item 120exponential blow-up in the face of control flow. 121@end itemize 122 123For example, in general, given this CFG: 124 125@smallexample 126 A 127 / \ 128 B C 129 \ / 130 D 131 / \ 132 E F 133 \ / 134 G 135@end smallexample 136 137we want to avoid differences in state-tracking in B and C from 138leading to blow-up. If we don't prevent state blowup, we end up 139with exponential growth of the exploded graph like this: 140 141@smallexample 142 143 1:A 144 / \ 145 / \ 146 / \ 147 2:B 3:C 148 | | 149 4:D 5:D (2 exploded nodes for D) 150 / \ / \ 151 6:E 7:F 8:E 9:F 152 | | | | 153 10:G 11:G 12:G 13:G (4 exploded nodes for G) 154 155@end smallexample 156 157Similar issues arise with loops. 158 159To prevent this, we follow various approaches: 160 161@enumerate a 162@item 163state pruning: which tries to discard state that won't be relevant 164later on withing the function. 165This can be disabled via @option{-fno-analyzer-state-purge}. 166 167@item 168state merging. We can try to find the commonality between two 169program_state instances to make a third, simpler program_state. 170We have two strategies here: 171 172 @enumerate 173 @item 174 the worklist keeps new nodes for the same program_point together, 175 and tries to merge them before processing, and thus before they have 176 successors. Hence, in the above, the two nodes for D (4 and 5) reach 177 the front of the worklist together, and we create a node for D with 178 the merger of the incoming states. 179 180 @item 181 try merging with the state of existing enodes for the program_point 182 (which may have already been explored). There will be duplication, 183 but only one set of duplication; subsequent duplicates are more likely 184 to hit the cache. In particular, (hopefully) all merger chains are 185 finite, and so we guarantee termination. 186 This is intended to help with loops: we ought to explore the first 187 iteration, and then have a "subsequent iterations" exploration, 188 which uses a state merged from that of the first, to be more abstract. 189 @end enumerate 190 191We avoid merging pairs of states that have state-machine differences, 192as these are the kinds of differences that are likely to be most 193interesting. So, for example, given: 194 195@smallexample 196 if (condition) 197 ptr = malloc (size); 198 else 199 ptr = local_buf; 200 201 .... do things with 'ptr' 202 203 if (condition) 204 free (ptr); 205 206 ...etc 207@end smallexample 208 209then we end up with an exploded graph that looks like this: 210 211@smallexample 212 213 if (condition) 214 / T \ F 215 --------- ---------- 216 / \ 217 ptr = malloc (size) ptr = local_buf 218 | | 219 copy of copy of 220 "do things with 'ptr'" "do things with 'ptr'" 221 with ptr: heap-allocated with ptr: stack-allocated 222 | | 223 if (condition) if (condition) 224 | known to be T | known to be F 225 free (ptr); | 226 \ / 227 ----------------------------- 228 | ('ptr' is pruned, so states can be merged) 229 etc 230 231@end smallexample 232 233where some duplication has occurred, but only for the places where the 234the different paths are worth exploringly separately. 235 236Merging can be disabled via @option{-fno-analyzer-state-merge}. 237@end enumerate 238 239@subsection Region Model 240 241Part of the state stored at a @code{exploded_node} is a @code{region_model}. 242This is an implementation of the region-based ternary model described in 243@url{http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf, 244"A Memory Model for Static Analysis of C Programs"} 245(Zhongxing Xu, Ted Kremenek, and Jian Zhang). 246 247A @code{region_model} encapsulates a representation of the state of 248memory, with a tree of @code{region} instances, along with their associated 249values. The representation is graph-like because values can be pointers 250to regions. It also stores a constraint_manager, capturing relationships 251between the values. 252 253Because each node in the @code{exploded_graph} has a @code{region_model}, 254and each of the latter is graph-like, the @code{exploded_graph} is in some 255ways a graph of graphs. 256 257Here's an example of printing a @code{region_model}, showing the ASCII-art 258used to visualize the region hierarchy (colorized when printing to stderr): 259 260@smallexample 261(gdb) call debug (*this) 262r0: @{kind: 'root', parent: null, sval: null@} 263|-stack: r1: @{kind: 'stack', parent: r0, sval: sv1@} 264| |: sval: sv1: @{poisoned: uninit@} 265| |-frame for 'test': r2: @{kind: 'frame', parent: r1, sval: null, map: @{'ptr_3': r3@}, function: 'test', depth: 0@} 266| | `-'ptr_3': r3: @{kind: 'map', parent: r2, sval: sv3, type: 'void *', map: @{@}@} 267| | |: sval: sv3: @{type: 'void *', unknown@} 268| | |: type: 'void *' 269| `-frame for 'calls_malloc': r4: @{kind: 'frame', parent: r1, sval: null, map: @{'result_3': r7, '_4': r8, '<anonymous>': r5@}, function: 'calls_malloc', depth: 1@} 270| |-'<anonymous>': r5: @{kind: 'map', parent: r4, sval: sv4, type: 'void *', map: @{@}@} 271| | |: sval: sv4: @{type: 'void *', &r6@} 272| | |: type: 'void *' 273| |-'result_3': r7: @{kind: 'map', parent: r4, sval: sv4, type: 'void *', map: @{@}@} 274| | |: sval: sv4: @{type: 'void *', &r6@} 275| | |: type: 'void *' 276| `-'_4': r8: @{kind: 'map', parent: r4, sval: sv4, type: 'void *', map: @{@}@} 277| |: sval: sv4: @{type: 'void *', &r6@} 278| |: type: 'void *' 279`-heap: r9: @{kind: 'heap', parent: r0, sval: sv2@} 280 |: sval: sv2: @{poisoned: uninit@} 281 `-r6: @{kind: 'symbolic', parent: r9, sval: null, map: @{@}@} 282svalues: 283 sv0: @{type: 'size_t', '1024'@} 284 sv1: @{poisoned: uninit@} 285 sv2: @{poisoned: uninit@} 286 sv3: @{type: 'void *', unknown@} 287 sv4: @{type: 'void *', &r6@} 288constraint manager: 289 equiv classes: 290 ec0: @{sv0 == '1024'@} 291 ec1: @{sv4@} 292 constraints: 293@end smallexample 294 295This is the state at the point of returning from @code{calls_malloc} back 296to @code{test} in the following: 297 298@smallexample 299void * 300calls_malloc (void) 301@{ 302 void *result = malloc (1024); 303 return result; 304@} 305 306void test (void) 307@{ 308 void *ptr = calls_malloc (); 309 /* etc. */ 310@} 311@end smallexample 312 313The ``root'' region (``r0'') has a ``stack'' child (``r1''), with two 314children: a frame for @code{test} (``r2''), and a frame for 315@code{calls_malloc} (``r4''). These frame regions have child regions for 316storing their local variables. For example, the return region 317and that of various other regions within the ``calls_malloc'' frame all have 318value ``sv4'', a pointer to a heap-allocated region ``r6''. Within the parent 319frame, @code{ptr_3} has value ``sv3'', an unknown @code{void *}. 320 321@subsection Analyzer Paths 322 323We need to explain to the user what the problem is, and to persuade them 324that there really is a problem. Hence having a @code{diagnostic_path} 325isn't just an incidental detail of the analyzer; it's required. 326 327Paths ought to be: 328@itemize @bullet 329@item 330interprocedurally-valid 331@item 332feasible 333@end itemize 334 335Without state-merging, all paths in the exploded graph are feasible 336(in terms of constraints being satisified). 337With state-merging, paths in the exploded graph can be infeasible. 338 339We collate warnings and only emit them for the simplest path 340e.g. for a bug in a utility function, with lots of routes to calling it, 341we only emit the simplest path (which could be intraprocedural, if 342it can be reproduced without a caller). We apply a check that 343each duplicate warning's shortest path is feasible, rejecting any 344warnings for which the shortest path is infeasible (which could lead to 345false negatives). 346 347We use the shortest feasible @code{exploded_path} through the 348@code{exploded_graph} (a list of @code{exploded_edge *}) to build a 349@code{diagnostic_path} (a list of events for the diagnostic subsystem) - 350specifically a @code{checker_path}. 351 352Having built the @code{checker_path}, we prune it to try to eliminate 353events that aren't relevant, to minimize how much the user has to read. 354 355After pruning, we notify each event in the path of its ID and record the 356IDs of interesting events, allowing for events to refer to other events 357in their descriptions. The @code{pending_diagnostic} class has various 358vfuncs to support emitting more precise descriptions, so that e.g. 359 360@itemize @bullet 361@item 362a deref-of-unchecked-malloc diagnostic might use: 363@smallexample 364 returning possibly-NULL pointer to 'make_obj' from 'allocator' 365@end smallexample 366for a @code{return_event} to make it clearer how the unchecked value moves 367from callee back to caller 368@item 369a double-free diagnostic might use: 370@smallexample 371 second 'free' here; first 'free' was at (3) 372@end smallexample 373and a use-after-free might use 374@smallexample 375 use after 'free' here; memory was freed at (2) 376@end smallexample 377@end itemize 378 379At this point we can emit the diagnostic. 380 381@subsection Limitations 382 383@itemize @bullet 384@item 385Only for C so far 386@item 387The implementation of call summaries is currently very simplistic. 388@item 389Lack of function pointer analysis 390@item 391The constraint-handling code assumes reflexivity in some places 392(that values are equal to themselves), which is not the case for NaN. 393As a simple workaround, constraints on floating-point values are 394currently ignored. 395@item 396The region model code creates lots of little mutable objects at each 397@code{region_model} (and thus per @code{exploded_node}) rather than 398sharing immutable objects and having the mutable state in the 399@code{program_state} or @code{region_model}. The latter approach might be 400more efficient, and might avoid dealing with IDs rather than pointers 401(which requires us to impose an ordering to get meaningful equality). 402@item 403The region model code doesn't yet support @code{memcpy}. At the 404gimple-ssa level these have been optimized to statements like this: 405@smallexample 406_10 = MEM <long unsigned int> [(char * @{ref-all@})&c] 407MEM <long unsigned int> [(char * @{ref-all@})&d] = _10; 408@end smallexample 409Perhaps they could be supported via a new @code{compound_svalue} type. 410@item 411There are various other limitations in the region model (grep for TODO/xfail 412in the testsuite). 413@item 414The constraint_manager's implementation of transitivity is currently too 415expensive to enable by default and so must be manually enabled via 416@option{-fanalyzer-transitivity}). 417@item 418The checkers are currently hardcoded and don't allow for user extensibility 419(e.g. adding allocate/release pairs). 420@item 421Although the analyzer's test suite has a proof-of-concept test case for 422LTO, LTO support hasn't had extensive testing. There are various 423lang-specific things in the analyzer that assume C rather than LTO. 424For example, SSA names are printed to the user in ``raw'' form, rather 425than printing the underlying variable name. 426@end itemize 427 428Some ideas for other checkers 429@itemize @bullet 430@item 431File-descriptor-based APIs 432@item 433Linux kernel internal APIs 434@item 435Signal handling 436@end itemize 437 438@node Debugging the Analyzer 439@section Debugging the Analyzer 440@cindex analyzer, debugging 441@cindex static analyzer, debugging 442 443@subsection Special Functions for Debugging the Analyzer 444 445The analyzer recognizes various special functions by name, for use 446in debugging the analyzer. Declarations can be seen in the testsuite 447in @file{analyzer-decls.h}. None of these functions are actually 448implemented. 449 450Add: 451@smallexample 452 __analyzer_break (); 453@end smallexample 454to the source being analyzed to trigger a breakpoint in the analyzer when 455that source is reached. By putting a series of these in the source, it's 456much easier to effectively step through the program state as it's analyzed. 457 458@smallexample 459__analyzer_dump (); 460@end smallexample 461 462will dump the copious information about the analyzer's state each time it 463reaches the call in its traversal of the source. 464 465@smallexample 466__analyzer_dump_path (); 467@end smallexample 468 469will emit a placeholder ``note'' diagnostic with a path to that call site, 470if the analyzer finds a feasible path to it. 471 472The builtin @code{__analyzer_dump_exploded_nodes} will emit a warning 473after analysis containing information on all of the exploded nodes at that 474program point: 475 476@smallexample 477 __analyzer_dump_exploded_nodes (0); 478@end smallexample 479 480will output the number of ``processed'' nodes, and the IDs of 481both ``processed'' and ``merger'' nodes, such as: 482 483@smallexample 484warning: 2 processed enodes: [EN: 56, EN: 58] merger(s): [EN: 54-55, EN: 57, EN: 59] 485@end smallexample 486 487With a non-zero argument 488 489@smallexample 490 __analyzer_dump_exploded_nodes (1); 491@end smallexample 492 493it will also dump all of the states within the ``processed'' nodes. 494 495@smallexample 496 __analyzer_dump_region_model (); 497@end smallexample 498will dump the region_model's state to stderr. 499 500@smallexample 501__analyzer_eval (expr); 502@end smallexample 503will emit a warning with text "TRUE", FALSE" or "UNKNOWN" based on the 504truthfulness of the argument. This is useful for writing DejaGnu tests. 505 506 507@subsection Other Debugging Techniques 508 509One approach when tracking down where a particular bogus state is 510introduced into the @code{exploded_graph} is to add custom code to 511@code{region_model::validate}. 512 513For example, this custom code (added to @code{region_model::validate}) 514breaks with an assertion failure when a variable called @code{ptr} 515acquires a value that's unknown, using 516@code{region_model::get_value_by_name} to locate the variable 517 518@smallexample 519 /* Find a variable matching "ptr". */ 520 svalue_id sid = get_value_by_name ("ptr"); 521 if (!sid.null_p ()) 522 @{ 523 svalue *sval = get_svalue (sid); 524 gcc_assert (sval->get_kind () != SK_UNKNOWN); 525 @} 526@end smallexample 527 528making it easier to investigate further in a debugger when this occurs. 529