From 88b939b19ab454ab2d932ef292bbc557abe4431c Mon Sep 17 00:00:00 2001 From: David Malcolm Date: Thu, 7 Apr 2022 08:33:26 -0400 Subject: [PATCH] analyzer: fix leak false +ve with symbolic writes [PR102208] PR analyzer/102208 reports false positives from -Wanalyzer-malloc-leak. The root cause is the analyzer getting confused about symbolic writes that could alias a pointer referencing a malloced buffer. struct st { void *ptr; int arr[10]; }; struct st test (int idx) { struct st s; s.ptr = __builtin_malloc (1024); /* (1) */ s.arr[idx] = 42; /* (2) */ return s; } When removing overlapping bindings at (2), store::remove_overlapping_bindings was failing to pass on the uncertainty_t *, and thus when clobbering the binding of s.ptr, the heap-allocated pointer was not being added to the set of maybe-bound svalues, and thus being treated as leaking. This patch fixes this, so that s.ptr from (1) is treated as maybe-bound after the write at (2), fixing the leak false postive. Doing so requires the store to be smarter about how clobbering happens with various combinations of concrete keys and symbolic keys within concrete clusters and symbolic clusters, so that we don't lose warnings about definite leaks. gcc/analyzer/ChangeLog: PR analyzer/102208 * store.cc (binding_map::remove_overlapping_bindings): Add "always_overlap" param, using it to generalize to the case where we want to remove all bindings. Update "uncertainty" logic to only record maybe-bound values for cases where there is a symbolic write involved. (binding_cluster::mark_region_as_unknown): Split param "reg" into "reg_to_bind" and "reg_for_overlap". (binding_cluster::maybe_get_compound_binding): Pass "false" to binding_map::remove_overlapping_bindings new "always_overlap" param. (binding_cluster::remove_overlapping_bindings): Determine "always_overlap" and pass it to binding_map::remove_overlapping_bindings. (store::set_value): Pass uncertainty to remove_overlapping_bindings call. Update for new param of binding_cluster::mark_region_as_unknown, passing both the base region of the iter_cluster, and the lhs_reg. (store::mark_region_as_unknown): Update for new param of binding_cluster::mark_region_as_unknown, passing "reg" for both. (store::remove_overlapping_bindings): Add param "uncertainty", and pass it on to call to binding_cluster::remove_overlapping_bindings. * store.h (binding_map::remove_overlapping_bindings): Add "always_overlap" param. (binding_cluster::mark_region_as_unknown): Split param "reg" into "reg_to_bind" and "reg_for_overlap". (store::remove_overlapping_bindings): Add param "uncertainty". gcc/testsuite/ChangeLog: PR analyzer/102208 * gcc.dg/analyzer/symbolic-9.c: New test. * gcc.dg/analyzer/torture/leak-pr102308-1.c: New test. * gcc.dg/analyzer/torture/leak-pr102308-2.c: New test. Signed-off-by: David Malcolm --- gcc/analyzer/store.cc | 112 +++++++++--- gcc/analyzer/store.h | 10 +- gcc/testsuite/gcc.dg/analyzer/symbolic-9.c | 197 +++++++++++++++++++++ .../gcc.dg/analyzer/torture/leak-pr102308-1.c | 19 ++ .../gcc.dg/analyzer/torture/leak-pr102308-2.c | 12 ++ 5 files changed, 326 insertions(+), 24 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/analyzer/symbolic-9.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/torture/leak-pr102308-1.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/torture/leak-pr102308-2.c diff --git a/gcc/analyzer/store.cc b/gcc/analyzer/store.cc index 0014633..35f66a4 100644 --- a/gcc/analyzer/store.cc +++ b/gcc/analyzer/store.cc @@ -997,27 +997,61 @@ binding_map::get_overlapping_bindings (const binding_key *key, value: {BITS_WITHIN(bytes 4-7, inner_val: INIT_VAL((*INIT_VAL(p_33(D))).arr))} If UNCERTAINTY is non-NULL, use it to record any svalues that - were removed, as being maybe-bound. */ + were removed, as being maybe-bound. + + If ALWAYS_OVERLAP, then assume that DROP_KEY can overlap anything + in the map, due to one or both of the underlying clusters being + symbolic (but not the same symbolic region). Hence even if DROP_KEY is a + concrete binding it could actually be referring to the same memory as + distinct concrete bindings in the map. Remove all bindings, but + register any svalues with *UNCERTAINTY. */ void binding_map::remove_overlapping_bindings (store_manager *mgr, const binding_key *drop_key, - uncertainty_t *uncertainty) + uncertainty_t *uncertainty, + bool always_overlap) { + /* Get the bindings of interest within this map. */ auto_vec bindings; - get_overlapping_bindings (drop_key, &bindings); + if (always_overlap) + for (auto iter : *this) + bindings.safe_push (iter.first); /* Add all bindings. */ + else + /* Just add overlapping bindings. */ + get_overlapping_bindings (drop_key, &bindings); unsigned i; const binding_key *iter_binding; FOR_EACH_VEC_ELT (bindings, i, iter_binding) { + /* Record any svalues that were removed to *UNCERTAINTY as being + maybe-bound, provided at least some part of the binding is symbolic. + + Specifically, if at least one of the bindings is symbolic, or we + have ALWAYS_OVERLAP for the case where we have possibly aliasing + regions, then we don't know that the svalue has been overwritten, + and should record that to *UNCERTAINTY. + + However, if we have concrete keys accessing within the same symbolic + region, then we *know* that the symbolic region has been overwritten, + so we don't record it to *UNCERTAINTY, as this could be a genuine + leak. */ const svalue *old_sval = get (iter_binding); - if (uncertainty) + if (uncertainty + && (drop_key->symbolic_p () + || iter_binding->symbolic_p () + || always_overlap)) uncertainty->on_maybe_bound_sval (old_sval); /* Begin by removing the old binding. */ m_map.remove (iter_binding); + /* Don't attempt to handle prefixes/suffixes for the + "always_overlap" case; everything's being removed. */ + if (always_overlap) + continue; + /* Now potentially add the prefix and suffix. */ if (const concrete_binding *drop_ckey = drop_key->dyn_cast_concrete_binding ()) @@ -1335,22 +1369,30 @@ binding_cluster::zero_fill_region (store_manager *mgr, const region *reg) fill_region (mgr, reg, zero_sval); } -/* Mark REG within this cluster as being unknown. +/* Mark REG_TO_BIND within this cluster as being unknown. + + Remove any bindings overlapping REG_FOR_OVERLAP. If UNCERTAINTY is non-NULL, use it to record any svalues that - had bindings to them removed, as being maybe-bound. */ + had bindings to them removed, as being maybe-bound. + + REG_TO_BIND and REG_FOR_OVERLAP are the same for + store::mark_region_as_unknown, but are different in + store::set_value's alias handling, for handling the case where + we have a write to a symbolic REG_FOR_OVERLAP. */ void binding_cluster::mark_region_as_unknown (store_manager *mgr, - const region *reg, + const region *reg_to_bind, + const region *reg_for_overlap, uncertainty_t *uncertainty) { - remove_overlapping_bindings (mgr, reg, uncertainty); + remove_overlapping_bindings (mgr, reg_for_overlap, uncertainty); /* Add a default binding to "unknown". */ region_model_manager *sval_mgr = mgr->get_svalue_manager (); const svalue *sval - = sval_mgr->get_or_create_unknown_svalue (reg->get_type ()); - bind (mgr, reg, sval); + = sval_mgr->get_or_create_unknown_svalue (reg_to_bind->get_type ()); + bind (mgr, reg_to_bind, sval); } /* Purge state involving SVAL. */ @@ -1595,7 +1637,7 @@ binding_cluster::maybe_get_compound_binding (store_manager *mgr, it overlaps with offset_concrete_key. */ default_map.remove_overlapping_bindings (mgr, offset_concrete_key, - NULL); + NULL, false); } else if (bound_range.contains_p (reg_range, &subrange)) { @@ -1629,7 +1671,7 @@ binding_cluster::maybe_get_compound_binding (store_manager *mgr, it overlaps with overlap_concrete_key. */ default_map.remove_overlapping_bindings (mgr, overlap_concrete_key, - NULL); + NULL, false); } } else @@ -1652,7 +1694,13 @@ binding_cluster::maybe_get_compound_binding (store_manager *mgr, } /* Remove, truncate, and/or split any bindings within this map that - overlap REG. + could overlap REG. + + If REG's base region or this cluster is symbolic and they're different + base regions, then remove everything in this cluster's map, on the + grounds that REG could be referring to the same memory as anything + in the map. + If UNCERTAINTY is non-NULL, use it to record any svalues that were removed, as being maybe-bound. */ @@ -1663,7 +1711,19 @@ binding_cluster::remove_overlapping_bindings (store_manager *mgr, { const binding_key *reg_binding = binding_key::make (mgr, reg); - m_map.remove_overlapping_bindings (mgr, reg_binding, uncertainty); + const region *cluster_base_reg = get_base_region (); + const region *other_base_reg = reg->get_base_region (); + /* If at least one of the base regions involved is symbolic, and they're + not the same base region, then consider everything in the map as + potentially overlapping with reg_binding (even if it's a concrete + binding and things in the map are concrete - they could be referring + to the same memory when the symbolic base regions are taken into + account). */ + bool always_overlap = (cluster_base_reg != other_base_reg + && (cluster_base_reg->get_kind () == RK_SYMBOLIC + || other_base_reg->get_kind () == RK_SYMBOLIC)); + m_map.remove_overlapping_bindings (mgr, reg_binding, uncertainty, + always_overlap); } /* Attempt to merge CLUSTER_A and CLUSTER_B into OUT_CLUSTER, using @@ -2368,7 +2428,7 @@ store::set_value (store_manager *mgr, const region *lhs_reg, logger *logger = mgr->get_logger (); LOG_SCOPE (logger); - remove_overlapping_bindings (mgr, lhs_reg); + remove_overlapping_bindings (mgr, lhs_reg, uncertainty); rhs_sval = simplify_for_binding (rhs_sval); @@ -2438,8 +2498,14 @@ store::set_value (store_manager *mgr, const region *lhs_reg, lhs_reg->dump_to_pp (pp, true); logger->end_log_line (); } - iter_cluster->mark_region_as_unknown (mgr, iter_base_reg, - uncertainty); + /* Mark all of iter_cluster's iter_base_reg as unknown, + using LHS_REG when considering overlaps, to handle + symbolic vs concrete issues. */ + iter_cluster->mark_region_as_unknown + (mgr, + iter_base_reg, /* reg_to_bind */ + lhs_reg, /* reg_for_overlap */ + uncertainty); break; case tristate::TS_TRUE: @@ -2603,7 +2669,7 @@ store::mark_region_as_unknown (store_manager *mgr, const region *reg, || !base_reg->tracked_p ()) return; binding_cluster *cluster = get_or_create_cluster (base_reg); - cluster->mark_region_as_unknown (mgr, reg, uncertainty); + cluster->mark_region_as_unknown (mgr, reg, reg, uncertainty); } /* Purge state involving SVAL. */ @@ -2826,10 +2892,14 @@ store::get_representative_path_vars (const region_model *model, } /* Remove all bindings overlapping REG within this store, removing - any clusters that become redundant. */ + any clusters that become redundant. + + If UNCERTAINTY is non-NULL, use it to record any svalues that + were removed, as being maybe-bound. */ void -store::remove_overlapping_bindings (store_manager *mgr, const region *reg) +store::remove_overlapping_bindings (store_manager *mgr, const region *reg, + uncertainty_t *uncertainty) { const region *base_reg = reg->get_base_region (); if (binding_cluster **cluster_slot = m_cluster_map.get (base_reg)) @@ -2842,7 +2912,7 @@ store::remove_overlapping_bindings (store_manager *mgr, const region *reg) delete cluster; return; } - cluster->remove_overlapping_bindings (mgr, reg, NULL); + cluster->remove_overlapping_bindings (mgr, reg, uncertainty); } } diff --git a/gcc/analyzer/store.h b/gcc/analyzer/store.h index 89bb352..17485b7 100644 --- a/gcc/analyzer/store.h +++ b/gcc/analyzer/store.h @@ -509,7 +509,8 @@ public: void remove_overlapping_bindings (store_manager *mgr, const binding_key *drop_key, - uncertainty_t *uncertainty); + uncertainty_t *uncertainty, + bool always_overlap); private: void get_overlapping_bindings (const binding_key *key, @@ -574,7 +575,9 @@ public: void purge_region (store_manager *mgr, const region *reg); void fill_region (store_manager *mgr, const region *reg, const svalue *sval); void zero_fill_region (store_manager *mgr, const region *reg); - void mark_region_as_unknown (store_manager *mgr, const region *reg, + void mark_region_as_unknown (store_manager *mgr, + const region *reg_to_bind, + const region *reg_for_overlap, uncertainty_t *uncertainty); void purge_state_involving (const svalue *sval, region_model_manager *sval_mgr); @@ -765,7 +768,8 @@ public: region_model_manager *mgr); private: - void remove_overlapping_bindings (store_manager *mgr, const region *reg); + void remove_overlapping_bindings (store_manager *mgr, const region *reg, + uncertainty_t *uncertainty); tristate eval_alias_1 (const region *base_reg_a, const region *base_reg_b) const; diff --git a/gcc/testsuite/gcc.dg/analyzer/symbolic-9.c b/gcc/testsuite/gcc.dg/analyzer/symbolic-9.c new file mode 100644 index 0000000..54ed30f --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/symbolic-9.c @@ -0,0 +1,197 @@ +#include "analyzer-decls.h" + +struct st +{ + void *ptr[10]; + int arr[10]; +}; + +/* Various combinations of a pair of writes, involving + symbolic vs concrete clusters, with symbolic vs concrete keys + within them. */ + +struct st g; + +/* "ptr" write: fully concrete. */ + +struct st +test_conc_conc_ptr_conc_conc_arr (void) +{ + struct st s; + s.ptr[1] = __builtin_malloc (1024); + __analyzer_describe (0, s.ptr[1]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + s.arr[5] = 42; + __analyzer_describe (0, s.ptr[1]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + __analyzer_describe (0, s.arr[5]); /* { dg-warning "42" } */ + return s; +} + +struct st +test_conc_conc_ptr_conc_sym_arr (int j) +{ + struct st s; + s.ptr[1] = __builtin_malloc (1024); + __analyzer_describe (0, s.ptr[1]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + s.arr[j] = 42; + __analyzer_describe (0, s.ptr[1]); /* { dg-warning "UNKNOWN" } */ + __analyzer_describe (0, s.arr[j]); /* { dg-warning "42" } */ + return s; +} + +struct st +test_conc_conc_ptr_sym_conc_arr (struct st *p) +{ + struct st s; + s.ptr[1] = __builtin_malloc (1024); + __analyzer_describe (0, s.ptr[1]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + p->arr[5] = 42; + __analyzer_describe (0, s.ptr[1]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + __analyzer_describe (0, p->arr[5]); /* { dg-warning "42" } */ + return s; +} + +struct st +test_conc_conc_ptr_sym_sym_arr (struct st *p, int j) +{ + struct st s; + s.ptr[1] = __builtin_malloc (1024); + __analyzer_describe (0, s.ptr[1]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + p->arr[j] = 42; + __analyzer_describe (0, s.ptr[1]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + __analyzer_describe (0, p->arr[j]); /* { dg-warning "42" } */ + return s; +} + +/* "ptr" write: symbolic region, but at concrete offset. */ + +void +test_sym_conc_ptr_conc_conc_arr (struct st *p) +{ + p->ptr[1] = __builtin_malloc (1024); + __analyzer_describe (0, p->ptr[1]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + g.arr[5] = 42; + __analyzer_describe (0, p->ptr[1]); /* { dg-warning "UNKNOWN" } */ + __analyzer_describe (0, g.arr[5]); /* { dg-warning "42" } */ +} + +void +test_sym_conc_ptr_conc_sym_arr (struct st *p, int j) +{ + p->ptr[1] = __builtin_malloc (1024); + __analyzer_describe (0, p->ptr[1]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + g.arr[j] = 42; + __analyzer_describe (0, p->ptr[1]); /* { dg-warning "UNKNOWN" } */ + __analyzer_describe (0, g.arr[j]); /* { dg-warning "42" } */ +} + +void +test_sym_conc_ptr_sym_conc_arr (struct st *p, struct st *q) +{ + p->ptr[1] = __builtin_malloc (1024); + __analyzer_describe (0, p->ptr[1]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + q->arr[5] = 42; + __analyzer_describe (0, p->ptr[1]); /* { dg-warning "UNKNOWN" } */ + __analyzer_describe (0, q->arr[5]); /* { dg-warning "42" } */ +} + +void +test_sym_conc_ptr_sym_sym_arr (struct st *p, struct st *q, int j) +{ + p->ptr[1] = __builtin_malloc (1024); + __analyzer_describe (0, p->ptr[1]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + q->arr[j] = 42; + __analyzer_describe (0, p->ptr[1]); /* { dg-warning "UNKNOWN" } */ + __analyzer_describe (0, q->arr[j]); /* { dg-warning "42" } */ +} + +/* "ptr" write: concrete region, but at symbolic offset. */ + +struct st +test_conc_sym_ptr_conc_conc_arr (int i) +{ + struct st s; + s.ptr[i] = __builtin_malloc (1024); + __analyzer_describe (0, s.ptr[i]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + s.arr[5] = 42; + __analyzer_describe (0, s.ptr[i]); /* { dg-warning "UNKNOWN" } */ + __analyzer_describe (0, s.arr[5]); /* { dg-warning "42" } */ + return s; +} + +struct st +test_conc_sym_ptr_conc_sym_arr (int i, int j) +{ + struct st s; + s.ptr[i] = __builtin_malloc (1024); + __analyzer_describe (0, s.ptr[i]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + s.arr[j] = 42; + __analyzer_describe (0, s.ptr[i]); /* { dg-warning "UNKNOWN" } */ + __analyzer_describe (0, s.arr[j]); /* { dg-warning "42" } */ + return s; +} + +struct st +test_conc_sym_ptr_sym_conc_arr (int i, struct st *p) +{ + struct st s; + s.ptr[i] = __builtin_malloc (1024); + __analyzer_describe (0, s.ptr[i]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + p->arr[5] = 42; + __analyzer_describe (0, s.ptr[i]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + __analyzer_describe (0, p->arr[5]); /* { dg-warning "42" } */ + return s; +} /* { dg-bogus "leak" "PR analyzer/105190" { xfail *-*-* } } */ + +struct st +test_conc_sym_ptr_sym_sym_arr (int i, struct st *p, int j) +{ + struct st s; + s.ptr[i] = __builtin_malloc (1024); + __analyzer_describe (0, s.ptr[i]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + p->arr[j] = 42; + __analyzer_describe (0, s.ptr[i]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + __analyzer_describe (0, p->arr[j]); /* { dg-warning "42" } */ + return s; +} /* { dg-bogus "leak" "PR analyzer/105190" { xfail *-*-* } } */ + +/* "ptr" write: symbolic region, with symbolic offset. */ + +void +test_sym_sym_ptr_conc_conc_arr (struct st *p, int i) +{ + p->ptr[i] = __builtin_malloc (1024); + __analyzer_describe (0, p->ptr[i]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + g.arr[5] = 42; + __analyzer_describe (0, p->ptr[i]); /* { dg-warning "UNKNOWN" } */ + __analyzer_describe (0, g.arr[5]); /* { dg-warning "42" } */ +} + +void +test_sym_sym_ptr_conc_sym_arr (struct st *p, int i, int j) +{ + p->ptr[i] = __builtin_malloc (1024); + __analyzer_describe (0, p->ptr[i]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + g.arr[j] = 42; + __analyzer_describe (0, p->ptr[i]); /* { dg-warning "UNKNOWN" } */ + __analyzer_describe (0, g.arr[j]); /* { dg-warning "42" } */ +} + +void +test_sym_sym_ptr_sym_conc_arr (struct st *p, int i, struct st *q) +{ + p->ptr[i] = __builtin_malloc (1024); + __analyzer_describe (0, p->ptr[i]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + q->arr[5] = 42; + __analyzer_describe (0, p->ptr[i]); /* { dg-warning "UNKNOWN" } */ + __analyzer_describe (0, q->arr[5]); /* { dg-warning "42" } */ +} + +void +test_sym_sym_ptr_sym_sym_arr (struct st *p, int i, struct st *q, int j) +{ + p->ptr[i] = __builtin_malloc (1024); + __analyzer_describe (0, p->ptr[i]); /* { dg-warning "HEAP_ALLOCATED_REGION" } */ + q->arr[j] = 42; + __analyzer_describe (0, p->ptr[i]); /* { dg-warning "UNKNOWN" } */ + __analyzer_describe (0, q->arr[j]); /* { dg-warning "42" } */ +} diff --git a/gcc/testsuite/gcc.dg/analyzer/torture/leak-pr102308-1.c b/gcc/testsuite/gcc.dg/analyzer/torture/leak-pr102308-1.c new file mode 100644 index 0000000..3174716 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/torture/leak-pr102308-1.c @@ -0,0 +1,19 @@ +#include + +struct s { + char *p; + int arr[2]; +}; + +int main(void) { + struct s *s = malloc(sizeof *s); + if (s) { + s->p = malloc(1); + for (int i = 0; i < 2; i++) + s->arr[i] = -1; /* { dg-bogus "leak" } */ + } + if (s) { + free(s->p); + free(s); + } +} diff --git a/gcc/testsuite/gcc.dg/analyzer/torture/leak-pr102308-2.c b/gcc/testsuite/gcc.dg/analyzer/torture/leak-pr102308-2.c new file mode 100644 index 0000000..d65f176 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/torture/leak-pr102308-2.c @@ -0,0 +1,12 @@ +#include +struct s { + char *p; + int arr[1]; +}; +int main(void) { + struct s s; + s.p = malloc(1); + for (int i = 0; i < 1; i++) + s.arr[i] = -1; /* { dg-bogus "leak" } */ + free(s.p); +} -- 2.7.4