Mercurial > hg > CbC > CbC_gcc
comparison gcc/doc/analyzer.texi @ 145:1830386684a0
gcc-9.2.0
author | anatofuz |
---|---|
date | Thu, 13 Feb 2020 11:34:05 +0900 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
131:84e7813d76e9 | 145:1830386684a0 |
---|---|
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 | |
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). | |
27 | |
28 The implementation is read-only: it doesn't attempt to change anything, | |
29 just emit warnings. | |
30 | |
31 The gimple representation can be seen using @option{-fdump-ipa-analyzer}. | |
32 | |
33 First, we build a @code{supergraph} which combines the callgraph and all | |
34 of the CFGs into a single directed graph, with both interprocedural and | |
35 intraprocedural 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 | |
38 interprocedural calls, so there can be more than one supernode per | |
39 basic block. Most statements will be in just one supernode, but a call | |
40 statement can appear in two supernodes: at the end of one for the call, | |
41 and again at the start of another for the return. | |
42 | |
43 The supergraph can be seen using @option{-fdump-analyzer-supergraph}. | |
44 | |
45 We then build an @code{analysis_plan} which walks the callgraph to | |
46 determine which calls might be suitable for being summarized (rather | |
47 than fully explored) and thus in what order to explore the functions. | |
48 | |
49 Next is the heart of the analyzer: we use a worklist to explore state | |
50 within the supergraph, building an "exploded graph". | |
51 Nodes 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 | |
55 We reuse nodes for <point, state> pairs we've already seen, and avoid | |
56 tracking state too closely, so that (hopefully) we rapidly converge | |
57 on a final exploded graph, and terminate the analysis. We also bail | |
58 out if the number of exploded <end-of-basic-block, state> nodes gets | |
59 larger than a particular multiple of the total number of basic blocks | |
60 (to ensure termination in the face of pathological state-explosion | |
61 cases, or bugs). We also stop exploring a point once we hit a limit | |
62 of states for that point. | |
63 | |
64 We can identify problems directly when processing a <point,@w{ }state> | |
65 instance. 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 | |
72 then we can detect a double-free of "ptr". We can then emit a path | |
73 to reach the problem by finding the simplest route through the graph. | |
74 | |
75 Program points in the analysis are much more fine-grained than in the | |
76 CFG and supergraph, with points (and thus potentially exploded nodes) | |
77 for various events, including before individual statements. | |
78 By default the exploded graph merges multiple consecutive statements | |
79 in a supernode into one exploded edge to minimize the size of the | |
80 exploded graph. This can be suppressed via | |
81 @option{-fanalyzer-fine-grained}. | |
82 The fine-grained approach seems to make things simpler and more debuggable | |
83 that other approaches I tried, in that each point is responsible for one | |
84 thing. | |
85 | |
86 Program points in the analysis also have a "call string" identifying the | |
87 stack of callsites below them, so that paths in the exploded graph | |
88 correspond to interprocedurally valid paths: we always return to the | |
89 correct call site, propagating state information accordingly. | |
90 We avoid infinite recursion by stopping the analysis if a callsite | |
91 appears more than @code{analyzer-max-recursion-depth} in a callstring | |
92 (defaulting to 2). | |
93 | |
94 @subsection Graphs | |
95 | |
96 Nodes 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 | |
99 from the @code{snodes} and @code{sedges} in the supergraph). | |
100 | |
101 Each graph numbers its nodes, giving unique identifiers - supernodes | |
102 are referred to throughout dumps in the form @samp{SN': @var{index}} and | |
103 exploded nodes in the form @samp{EN: @var{index}} (e.g. @samp{SN: 2} and | |
104 @samp{EN:29}). | |
105 | |
106 The supergraph can be seen using @option{-fdump-analyzer-supergraph-graph}. | |
107 | |
108 The exploded graph can be seen using @option{-fdump-analyzer-exploded-graph} | |
109 and other dump options. Exploded nodes are color-coded in the .dot output | |
110 based on state-machine states to make it easier to see state changes at | |
111 a glance. | |
112 | |
113 @subsection State Tracking | |
114 | |
115 There's a tension between: | |
116 @itemize @bullet | |
117 @item | |
118 precision of analysis in the straight-line case, vs | |
119 @item | |
120 exponential blow-up in the face of control flow. | |
121 @end itemize | |
122 | |
123 For 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 | |
137 we want to avoid differences in state-tracking in B and C from | |
138 leading to blow-up. If we don't prevent state blowup, we end up | |
139 with 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 | |
157 Similar issues arise with loops. | |
158 | |
159 To prevent this, we follow various approaches: | |
160 | |
161 @enumerate a | |
162 @item | |
163 state pruning: which tries to discard state that won't be relevant | |
164 later on withing the function. | |
165 This can be disabled via @option{-fno-analyzer-state-purge}. | |
166 | |
167 @item | |
168 state merging. We can try to find the commonality between two | |
169 program_state instances to make a third, simpler program_state. | |
170 We 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 | |
191 We avoid merging pairs of states that have state-machine differences, | |
192 as these are the kinds of differences that are likely to be most | |
193 interesting. 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 | |
209 then 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 | |
233 where some duplication has occurred, but only for the places where the | |
234 the different paths are worth exploringly separately. | |
235 | |
236 Merging can be disabled via @option{-fno-analyzer-state-merge}. | |
237 @end enumerate | |
238 | |
239 @subsection Region Model | |
240 | |
241 Part of the state stored at a @code{exploded_node} is a @code{region_model}. | |
242 This 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 | |
247 A @code{region_model} encapsulates a representation of the state of | |
248 memory, with a tree of @code{region} instances, along with their associated | |
249 values. The representation is graph-like because values can be pointers | |
250 to regions. It also stores a constraint_manager, capturing relationships | |
251 between the values. | |
252 | |
253 Because each node in the @code{exploded_graph} has a @code{region_model}, | |
254 and each of the latter is graph-like, the @code{exploded_graph} is in some | |
255 ways a graph of graphs. | |
256 | |
257 Here's an example of printing a @code{region_model}, showing the ASCII-art | |
258 used to visualize the region hierarchy (colorized when printing to stderr): | |
259 | |
260 @smallexample | |
261 (gdb) call debug (*this) | |
262 r0: @{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: @{@}@} | |
282 svalues: | |
283 sv0: @{type: 'size_t', '1024'@} | |
284 sv1: @{poisoned: uninit@} | |
285 sv2: @{poisoned: uninit@} | |
286 sv3: @{type: 'void *', unknown@} | |
287 sv4: @{type: 'void *', &r6@} | |
288 constraint manager: | |
289 equiv classes: | |
290 ec0: @{sv0 == '1024'@} | |
291 ec1: @{sv4@} | |
292 constraints: | |
293 @end smallexample | |
294 | |
295 This is the state at the point of returning from @code{calls_malloc} back | |
296 to @code{test} in the following: | |
297 | |
298 @smallexample | |
299 void * | |
300 calls_malloc (void) | |
301 @{ | |
302 void *result = malloc (1024); | |
303 return result; | |
304 @} | |
305 | |
306 void test (void) | |
307 @{ | |
308 void *ptr = calls_malloc (); | |
309 /* etc. */ | |
310 @} | |
311 @end smallexample | |
312 | |
313 The ``root'' region (``r0'') has a ``stack'' child (``r1''), with two | |
314 children: a frame for @code{test} (``r2''), and a frame for | |
315 @code{calls_malloc} (``r4''). These frame regions have child regions for | |
316 storing their local variables. For example, the return region | |
317 and that of various other regions within the ``calls_malloc'' frame all have | |
318 value ``sv4'', a pointer to a heap-allocated region ``r6''. Within the parent | |
319 frame, @code{ptr_3} has value ``sv3'', an unknown @code{void *}. | |
320 | |
321 @subsection Analyzer Paths | |
322 | |
323 We need to explain to the user what the problem is, and to persuade them | |
324 that there really is a problem. Hence having a @code{diagnostic_path} | |
325 isn't just an incidental detail of the analyzer; it's required. | |
326 | |
327 Paths ought to be: | |
328 @itemize @bullet | |
329 @item | |
330 interprocedurally-valid | |
331 @item | |
332 feasible | |
333 @end itemize | |
334 | |
335 Without state-merging, all paths in the exploded graph are feasible | |
336 (in terms of constraints being satisified). | |
337 With state-merging, paths in the exploded graph can be infeasible. | |
338 | |
339 We collate warnings and only emit them for the simplest path | |
340 e.g. for a bug in a utility function, with lots of routes to calling it, | |
341 we only emit the simplest path (which could be intraprocedural, if | |
342 it can be reproduced without a caller). We apply a check that | |
343 each duplicate warning's shortest path is feasible, rejecting any | |
344 warnings for which the shortest path is infeasible (which could lead to | |
345 false negatives). | |
346 | |
347 We 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) - | |
350 specifically a @code{checker_path}. | |
351 | |
352 Having built the @code{checker_path}, we prune it to try to eliminate | |
353 events that aren't relevant, to minimize how much the user has to read. | |
354 | |
355 After pruning, we notify each event in the path of its ID and record the | |
356 IDs of interesting events, allowing for events to refer to other events | |
357 in their descriptions. The @code{pending_diagnostic} class has various | |
358 vfuncs to support emitting more precise descriptions, so that e.g. | |
359 | |
360 @itemize @bullet | |
361 @item | |
362 a deref-of-unchecked-malloc diagnostic might use: | |
363 @smallexample | |
364 returning possibly-NULL pointer to 'make_obj' from 'allocator' | |
365 @end smallexample | |
366 for a @code{return_event} to make it clearer how the unchecked value moves | |
367 from callee back to caller | |
368 @item | |
369 a double-free diagnostic might use: | |
370 @smallexample | |
371 second 'free' here; first 'free' was at (3) | |
372 @end smallexample | |
373 and 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 | |
379 At this point we can emit the diagnostic. | |
380 | |
381 @subsection Limitations | |
382 | |
383 @itemize @bullet | |
384 @item | |
385 Only for C so far | |
386 @item | |
387 The implementation of call summaries is currently very simplistic. | |
388 @item | |
389 Lack of function pointer analysis | |
390 @item | |
391 The constraint-handling code assumes reflexivity in some places | |
392 (that values are equal to themselves), which is not the case for NaN. | |
393 As a simple workaround, constraints on floating-point values are | |
394 currently ignored. | |
395 @item | |
396 The region model code creates lots of little mutable objects at each | |
397 @code{region_model} (and thus per @code{exploded_node}) rather than | |
398 sharing immutable objects and having the mutable state in the | |
399 @code{program_state} or @code{region_model}. The latter approach might be | |
400 more efficient, and might avoid dealing with IDs rather than pointers | |
401 (which requires us to impose an ordering to get meaningful equality). | |
402 @item | |
403 The region model code doesn't yet support @code{memcpy}. At the | |
404 gimple-ssa level these have been optimized to statements like this: | |
405 @smallexample | |
406 _10 = MEM <long unsigned int> [(char * @{ref-all@})&c] | |
407 MEM <long unsigned int> [(char * @{ref-all@})&d] = _10; | |
408 @end smallexample | |
409 Perhaps they could be supported via a new @code{compound_svalue} type. | |
410 @item | |
411 There are various other limitations in the region model (grep for TODO/xfail | |
412 in the testsuite). | |
413 @item | |
414 The constraint_manager's implementation of transitivity is currently too | |
415 expensive to enable by default and so must be manually enabled via | |
416 @option{-fanalyzer-transitivity}). | |
417 @item | |
418 The checkers are currently hardcoded and don't allow for user extensibility | |
419 (e.g. adding allocate/release pairs). | |
420 @item | |
421 Although the analyzer's test suite has a proof-of-concept test case for | |
422 LTO, LTO support hasn't had extensive testing. There are various | |
423 lang-specific things in the analyzer that assume C rather than LTO. | |
424 For example, SSA names are printed to the user in ``raw'' form, rather | |
425 than printing the underlying variable name. | |
426 @end itemize | |
427 | |
428 Some ideas for other checkers | |
429 @itemize @bullet | |
430 @item | |
431 File-descriptor-based APIs | |
432 @item | |
433 Linux kernel internal APIs | |
434 @item | |
435 Signal 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 | |
445 The analyzer recognizes various special functions by name, for use | |
446 in debugging the analyzer. Declarations can be seen in the testsuite | |
447 in @file{analyzer-decls.h}. None of these functions are actually | |
448 implemented. | |
449 | |
450 Add: | |
451 @smallexample | |
452 __analyzer_break (); | |
453 @end smallexample | |
454 to the source being analyzed to trigger a breakpoint in the analyzer when | |
455 that source is reached. By putting a series of these in the source, it's | |
456 much easier to effectively step through the program state as it's analyzed. | |
457 | |
458 @smallexample | |
459 __analyzer_dump (); | |
460 @end smallexample | |
461 | |
462 will dump the copious information about the analyzer's state each time it | |
463 reaches the call in its traversal of the source. | |
464 | |
465 @smallexample | |
466 __analyzer_dump_path (); | |
467 @end smallexample | |
468 | |
469 will emit a placeholder ``note'' diagnostic with a path to that call site, | |
470 if the analyzer finds a feasible path to it. | |
471 | |
472 The builtin @code{__analyzer_dump_exploded_nodes} will emit a warning | |
473 after analysis containing information on all of the exploded nodes at that | |
474 program point: | |
475 | |
476 @smallexample | |
477 __analyzer_dump_exploded_nodes (0); | |
478 @end smallexample | |
479 | |
480 will output the number of ``processed'' nodes, and the IDs of | |
481 both ``processed'' and ``merger'' nodes, such as: | |
482 | |
483 @smallexample | |
484 warning: 2 processed enodes: [EN: 56, EN: 58] merger(s): [EN: 54-55, EN: 57, EN: 59] | |
485 @end smallexample | |
486 | |
487 With a non-zero argument | |
488 | |
489 @smallexample | |
490 __analyzer_dump_exploded_nodes (1); | |
491 @end smallexample | |
492 | |
493 it will also dump all of the states within the ``processed'' nodes. | |
494 | |
495 @smallexample | |
496 __analyzer_dump_region_model (); | |
497 @end smallexample | |
498 will dump the region_model's state to stderr. | |
499 | |
500 @smallexample | |
501 __analyzer_eval (expr); | |
502 @end smallexample | |
503 will emit a warning with text "TRUE", FALSE" or "UNKNOWN" based on the | |
504 truthfulness of the argument. This is useful for writing DejaGnu tests. | |
505 | |
506 | |
507 @subsection Other Debugging Techniques | |
508 | |
509 One approach when tracking down where a particular bogus state is | |
510 introduced into the @code{exploded_graph} is to add custom code to | |
511 @code{region_model::validate}. | |
512 | |
513 For example, this custom code (added to @code{region_model::validate}) | |
514 breaks with an assertion failure when a variable called @code{ptr} | |
515 acquires 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 | |
528 making it easier to investigate further in a debugger when this occurs. |