From 004f2c07b6d3fa543f0fe86c55a7b3c227de2bb6 Mon Sep 17 00:00:00 2001 From: David Malcolm Date: Fri, 21 Feb 2020 19:25:40 -0500 Subject: analyzer: eliminate irrelevant control-flow edges from paths Paths emitted by the analyzer can be quite verbose at the default of -fanalyzer-verbosity=2. Consider the double-free in this example: #include int foo (); int bar (); void test (int a, int b, int c) { void *p = malloc (1024); while (a) foo (); if (b) foo (); else bar (); if (c) free (p); free (p); } Previously, the analyzer would emit a checker_path containing all control-flow information on the exploded_path leading to the double-free: test.c: In function 'test': test.c:17:3: warning: double-'free' of 'p' [CWE-415] [-Wanalyzer-double-free] 17 | free (p); | ^~~~~~~~ 'test': events 1-9 | | 8 | void *p = malloc (1024); | | ^~~~~~~~~~~~~ | | | | | (1) allocated here | 9 | while (a) | | ~ | | | | | (2) following 'false' branch (when 'a == 0')... | 10 | foo (); | 11 | if (b) | | ~ | | | | | (3) ...to here | | (4) following 'false' branch (when 'b == 0')... |...... | 14 | bar (); | | ~~~~~~ | | | | | (5) ...to here | 15 | if (c) | | ~ | | | | | (6) following 'true' branch (when 'c != 0')... | 16 | free (p); | | ~~~~~~~~ | | | | | (7) ...to here | | (8) first 'free' here | 17 | free (p); | | ~~~~~~~~ | | | | | (9) second 'free' here; first 'free' was at (8) | despite the fact that only the "if (c)" is relevant to triggering the double-free. This patch implements pruning of control flow events at -fanalyzer-verbosity=2, based on reachability information within the exploded_graph. The diagnostic_manager pre-computes reachability information about which exploded_nodes can reach the exploded_node of the diagnostic, and uses this to prune irrelvent control flow edges. The patch also adds a -fanalyzer-verbosity=3 to preserve these edges, so that the "show me everything" debugging level becomes -fanalyzer-verbosity=4. With these changes, the "while (a)" and "if (b)" edges are pruned from the above example, leading to: test.c: In function 'test': test.c:17:3: warning: double-'free' of 'p' [CWE-415] [-Wanalyzer-double-free] 17 | free (p); | ^~~~~~~~ 'test': events 1-5 | | 8 | void *p = malloc (1024); | | ^~~~~~~~~~~~~ | | | | | (1) allocated here |...... | 15 | if (c) | | ~ | | | | | (2) following 'true' branch (when 'c != 0')... | 16 | free (p); | | ~~~~~~~~ | | | | | (3) ...to here | | (4) first 'free' here | 17 | free (p); | | ~~~~~~~~ | | | | | (5) second 'free' here; first 'free' was at (4) | The above example is gcc.dg/analyzer/edges-2.c. gcc/analyzer/ChangeLog: * checker-path.cc (superedge_event::should_filter_p): Update filter for empty descriptions to cover verbosity level 3 as well as 2. * diagnostic-manager.cc: Include "analyzer/reachability.h". (class path_builder): New class. (diagnostic_manager::emit_saved_diagnostic): Create a path_builder and pass it to build_emission_path, rather passing eg; similarly for add_events_for_eedge and ext_state. (diagnostic_manager::build_emission_path): Replace "eg" param with a path_builder, pass it to add_events_for_eedge. (diagnostic_manager::add_events_for_eedge): Replace ext_state param with path_builder; pass it to add_events_for_superedge. (diagnostic_manager::significant_edge_p): New. (diagnostic_manager::add_events_for_superedge): Add path_builder param. Reject insignificant edges at verbosity levels below 3. (diagnostic_manager::prune_for_sm_diagnostic): Update highest verbosity level to 4. * diagnostic-manager.h (class path_builder): New forward decl. (diagnostic_manager::build_emission_path): Replace "eg" param with a path_builder. (diagnostic_manager::add_events_for_eedge): Replace ext_state param with path_builder. (diagnostic_manager::significant_edge_p): New. (diagnostic_manager::add_events_for_superedge): Add path_builder param. * reachability.h: New file. gcc/ChangeLog: * doc/invoke.texi (-fanalyzer-verbosity=): "2" only shows significant control flow events; add a "3" which shows all control flow events; the old "3" becomes "4". gcc/testsuite/ChangeLog: * gcc.dg/analyzer/analyzer-verbosity-2a.c: New test. * gcc.dg/analyzer/analyzer-verbosity-3.c: New test, based on analyzer-verbosity-2.c * gcc.dg/analyzer/analyzer-verbosity-3a.c: New test. * gcc.dg/analyzer/edges-1.c: New test. * gcc.dg/analyzer/edges-2.c: New test. * gcc.dg/analyzer/file-paths-1.c: Add -fanalyzer-verbosity=3. --- gcc/analyzer/ChangeLog | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) (limited to 'gcc/analyzer/ChangeLog') diff --git a/gcc/analyzer/ChangeLog b/gcc/analyzer/ChangeLog index d7db6ab..bc70e88 100644 --- a/gcc/analyzer/ChangeLog +++ b/gcc/analyzer/ChangeLog @@ -1,3 +1,32 @@ +2020-02-24 David Malcolm + + * checker-path.cc (superedge_event::should_filter_p): Update + filter for empty descriptions to cover verbosity level 3 as well + as 2. + * diagnostic-manager.cc: Include "analyzer/reachability.h". + (class path_builder): New class. + (diagnostic_manager::emit_saved_diagnostic): Create a path_builder + and pass it to build_emission_path, rather passing eg; similarly + for add_events_for_eedge and ext_state. + (diagnostic_manager::build_emission_path): Replace "eg" param + with a path_builder, pass it to add_events_for_eedge. + (diagnostic_manager::add_events_for_eedge): Replace ext_state + param with path_builder; pass it to add_events_for_superedge. + (diagnostic_manager::significant_edge_p): New. + (diagnostic_manager::add_events_for_superedge): Add path_builder + param. Reject insignificant edges at verbosity levels below 3. + (diagnostic_manager::prune_for_sm_diagnostic): Update highest + verbosity level to 4. + * diagnostic-manager.h (class path_builder): New forward decl. + (diagnostic_manager::build_emission_path): Replace "eg" param + with a path_builder. + (diagnostic_manager::add_events_for_eedge): Replace ext_state + param with path_builder. + (diagnostic_manager::significant_edge_p): New. + (diagnostic_manager::add_events_for_superedge): Add path_builder + param. + * reachability.h: New file. + 2020-02-18 David Malcolm PR analyzer/93692 -- cgit v1.1