[prev in list] [next in list] [prev in thread] [next in thread]
List: gcc-bugs
Subject: [Bug analyzer/95006] RFE: Reimplement -Wanalyzer-use-of-uninitialized-value
From: "cvs-commit at gcc dot gnu.org via Gcc-bugs" <gcc-bugs () gcc ! gnu ! org>
Date: 2021-06-30 14:28:01
Message-ID: bug-95006-4-WIlDdBCGc7 () http ! gcc ! gnu ! org/bugzilla/
[Download RAW message or body]
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95006
--- Comment #1 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by David Malcolm <dmalcolm@gcc.gnu.org>:
https://gcc.gnu.org/g:e61ffa201403e3814a43b176883e176716b1492f
commit r12-1931-ge61ffa201403e3814a43b176883e176716b1492f
Author: David Malcolm <dmalcolm@redhat.com>
Date: Wed Jun 30 09:39:04 2021 -0400
analyzer: eliminate enum binding_key [PR95006]
I rewrote the way the analyzer's region_model tracks the state of memory
in GCC 11 (in 808f4dfeb3a95f50f15e71148e5c1067f90a126d), which
introduced a store with a binding_map class, mapping binding keys to
symbolic values.
The GCC 11 implementation of binding keys has an enum binding_kind,
which can be "default" vs "direct"; the idea being that direct
bindings take priority over default bindings, where the latter could
be used to represent e.g. a zero-fill of a buffer, and the former
expresses those subregions that have since been touched.
This doesn't work well: it doesn't express the idea of filling
different subregions with different values, or a memset that only
touches part of a buffer, leading to numerous XFAILs in the memset
test cases (and elsewhere).
As preparatory work towards tracking uninitialized values, this patch
eliminates the enum binding_kind, so that all bindings have
equal weight; the order in which they happen is all that matters.
If a write happens which partially overwrites an existing binding,
the new code can partially overwrite a binding, potentially punching a
hole so that an existing binding is split into two parts.
The patch adds some new classes:
- a new "bits_within_svalue" symbolic value to support extracting
parts of an existing value when its binding is partially clobbered
- a new "repeated_svalue" symbolic value to better express filling
a region with repeated copies of a symbolic value (e.g. constant
zero)
- a new "sized_region" region to express accessing a subregion
with a symbolic size in bytes
and it rewrites e.g. how memset is implemented, so that we can precisely
track which bits in a region have not been touched.
That said, the patch doesn't actually implement "uninitialized" values;
I'm saving that for a followup.
gcc/analyzer/ChangeLog:
PR analyzer/95006
* analyzer.h (class repeated_svalue): New forward decl.
(class bits_within_svalue): New forward decl.
(class sized_region): New forward decl.
(get_field_at_bit_offset): New forward decl.
* engine.cc (exploded_graph::get_or_create_node): Validate the
merged state.
(exploded_graph::maybe_process_run_of_before_supernode_enodes):
Validate the states at each stage.
* program-state.cc (program_state::validate): Validate
m_region_model.
* region-model-impl-calls.cc (region_model::impl_call_memset):
Replace special-case logic for handling constant sizes with
a call to fill_region of a sized_region with the given fill value.
* region-model-manager.cc (maybe_undo_optimize_bit_field_compare):
Drop DK_direct.
(region_model_manager::maybe_fold_sub_svalue): Fold element-based
subregions of an initial value into initial values of an element.
Fold subvalues of repeated svalues.
(region_model_manager::maybe_fold_repeated_svalue): New.
(region_model_manager::get_or_create_repeated_svalue): New.
(get_bit_range_for_field): New.
(get_byte_range_for_field): New.
(get_field_at_byte_range): New.
(region_model_manager::maybe_fold_bits_within_svalue): New.
(region_model_manager::get_or_create_bits_within): New.
(region_model_manager::get_sized_region): New.
(region_model_manager::log_stats): Update for addition of
m_repeated_values_map, m_bits_within_values_map, and
m_sized_regions.
* region-model.cc (region_model::validate): New.
(region_model::on_assignment): Drop enum binding_kind.
(region_model::get_initial_value_for_global): Likewise.
(region_model::get_rvalue_for_bits): Replace body with call to
get_or_create_bits_within.
(region_model::get_capacity): Handle RK_SIZED.
(region_model::set_value): Drop enum binding_kind.
(region_model::fill_region): New.
(region_model::get_representative_path_var_1): Handle RK_SIZED.
* region-model.h (visitor::visit_repeated_svalue): New.
(visitor::visit_bits_within_svalue): New.
(region_model_manager::get_or_create_repeated_svalue): New decl.
(region_model_manager::get_or_create_bits_within): New decl.
(region_model_manager::get_sized_region): New decl.
(region_model_manager::maybe_fold_repeated_svalue): New decl.
(region_model_manager::maybe_fold_bits_within_svalue): New decl.
(region_model_manager::repeated_values_map_t): New typedef.
(region_model_manager::m_repeated_values_map): New field.
(region_model_manager::bits_within_values_map_t): New typedef.
(region_model_manager::m_bits_within_values_map): New field.
(region_model_manager::m_sized_regions): New field.
(region_model::fill_region): New decl.
* region.cc (region::get_base_region): Handle RK_SIZED.
(region::base_region_p): Likewise.
(region::get_byte_size_sval): New.
(get_field_at_bit_offset): Make non-static.
(region::calc_offset): Move implementation of cases to
get_relative_concrete_offset vfunc implementations. Handle
RK_SIZED.
(region::get_relative_concrete_offset): New.
(decl_region::get_svalue_for_initializer): Drop enum binding_kind.
(field_region::get_relative_concrete_offset): New, from
region::calc_offset.
(element_region::get_relative_concrete_offset): Likewise.
(offset_region::get_relative_concrete_offset): Likewise.
(sized_region::accept): New.
(sized_region::dump_to_pp): New.
(sized_region::get_byte_size): New.
(sized_region::get_bit_size): New.
* region.h (enum region_kind): Add RK_SIZED.
(region::dyn_cast_sized_region): New.
(region::get_byte_size): Make virtual.
(region::get_bit_size): Likewise.
(region::get_byte_size_sval): New decl.
(region::get_relative_concrete_offset): New decl.
(field_region::get_relative_concrete_offset): New decl.
(element_region::get_relative_concrete_offset): Likewise.
(offset_region::get_relative_concrete_offset): Likewise.
(class sized_region): New.
* store.cc (binding_kind_to_string): Delete.
(binding_key::make): Drop enum binding_kind.
(binding_key::dump_to_pp): Delete.
(binding_key::cmp_ptrs): Drop enum binding_kind.
(bit_range::contains_p): New.
(byte_range::dump): New.
(byte_range::contains_p): New.
(byte_range::cmp): New.
(concrete_binding::dump_to_pp): Drop enum binding_kind.
(concrete_binding::cmp_ptr_ptr): Likewise.
(symbolic_binding::dump_to_pp): Likewise.
(symbolic_binding::cmp_ptr_ptr): Likewise.
(binding_map::apply_ctor_val_to_range): Likewise.
(binding_map::apply_ctor_pair_to_child_region): Likewise.
(binding_map::get_overlapping_bindings): New.
(binding_map::remove_overlapping_bindings): New.
(binding_cluster::validate): New.
(binding_cluster::bind): Drop enum binding_kind.
(binding_cluster::bind_compound_sval): Likewise.
(binding_cluster::purge_region): Likewise.
(binding_cluster::zero_fill_region): Reimplement in terms of...
(binding_cluster::fill_region): New.
(binding_cluster::mark_region_as_unknown): Drop enum binding_kind.
(binding_cluster::get_binding): Likewise.
(binding_cluster::get_binding_recursive): Likewise.
(binding_cluster::get_any_binding): Likewise.
(binding_cluster::maybe_get_compound_binding): Reimplement.
(binding_cluster::get_overlapping_bindings): Delete.
(binding_cluster::remove_overlapping_bindings): Reimplement in
terms of binding_map::remove_overlapping_bindings.
(binding_cluster::can_merge_p): Update for removal of
enum binding_kind.
(binding_cluster::on_unknown_fncall): Drop enum binding_kind.
(binding_cluster::maybe_get_simple_value): Likewise.
(store_manager::get_concrete_binding): Likewise.
(store_manager::get_symbolic_binding): Likewise.
(store::validate): New.
(store::set_value): Drop enum binding_kind.
(store::zero_fill_region): Reimplement in terms of...
(store::fill_region): New.
(selftest::test_binding_key_overlap): Drop enum binding_kind.
* store.h (enum binding_kind): Delete.
(binding_kind_to_string): Delete decl.
(binding_key::make): Drop enum binding_kind.
(binding_key::dump_to_pp): Make pure virtual.
(binding_key::get_kind): Delete.
(binding_key::mark_deleted): Delete.
(binding_key::mark_empty): Delete.
(binding_key::is_deleted): Delete.
(binding_key::is_empty): Delete.
(binding_key::binding_key): Delete.
(binding_key::impl_hash): Delete.
(binding_key::impl_eq): Delete.
(binding_key::m_kind): Delete.
(bit_range::get_last_bit_offset): New.
(bit_range::contains_p): New.
(byte_range::contains_p): New.
(byte_range::operator==): New.
(byte_range::get_start_byte_offset): New.
(byte_range::get_next_byte_offset): New.
(byte_range::get_last_byte_offset): New.
(byte_range::as_bit_range): New.
(byte_range::cmp): New.
(concrete_binding::concrete_binding): Drop enum binding_kind.
(concrete_binding::hash): Likewise.
(concrete_binding::operator==): Likewise.
(concrete_binding::mark_deleted): New.
(concrete_binding::mark_empty): New.
(concrete_binding::is_deleted): New.
(concrete_binding::is_empty): New.
(default_hash_traits<ana::concrete_binding>::empty_zero_p): Make
false.
(symbolic_binding::symbolic_binding): Drop enum binding_kind.
(symbolic_binding::hash): Likewise.
(symbolic_binding::operator==): Likewise.
(symbolic_binding::mark_deleted): New.
(symbolic_binding::mark_empty): New.
(symbolic_binding::is_deleted): New.
(symbolic_binding::is_empty): New.
(binding_map::remove_overlapping_bindings): New decl.
(binding_map::get_overlapping_bindings): New decl.
(binding_cluster::validate): New decl.
(binding_cluster::bind): Drop enum binding_kind.
(binding_cluster::fill_region): New decl.
(binding_cluster::get_binding): Drop enum binding_kind.
(binding_cluster::get_binding_recursive): Likewise.
(binding_cluster::get_overlapping_bindings): Delete.
(store::validate): New decl.
(store::set_value): Drop enum binding_kind.
(store::fill_region): New decl.
(store_manager::get_concrete_binding): Drop enum binding_kind.
(store_manager::get_symbolic_binding): Likewise.
* svalue.cc (svalue::cmp_ptr): Handle SK_REPEATED and
SK_BITS_WITHIN.
(svalue::extract_bit_range): New.
(svalue::maybe_fold_bits_within): New.
(constant_svalue::maybe_fold_bits_within): New.
(unknown_svalue::maybe_fold_bits_within): New.
(unaryop_svalue::maybe_fold_bits_within): New.
(repeated_svalue::repeated_svalue): New.
(repeated_svalue::dump_to_pp): New.
(repeated_svalue::accept): New.
(repeated_svalue::all_zeroes_p): New.
(repeated_svalue::maybe_fold_bits_within): New.
(bits_within_svalue::bits_within_svalue): New.
(bits_within_svalue::dump_to_pp): New.
(bits_within_svalue::maybe_fold_bits_within): New.
(bits_within_svalue::accept): New.
(bits_within_svalue::implicitly_live_p): New.
(compound_svalue::maybe_fold_bits_within): New.
* svalue.h (enum svalue_kind): Add SK_REPEATED and SK_BITS_WITHIN.
(svalue::dyn_cast_repeated_svalue): New.
(svalue::dyn_cast_bits_within_svalue): New.
(svalue::extract_bit_range): New decl.
(svalue::maybe_fold_bits_within): New vfunc decl.
(region_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
(region_svalue::key_t::is_empty): Likewise.
(default_hash_traits<region_svalue::key_t>::empty_zero_p): Make
false.
(constant_svalue::maybe_fold_bits_within): New.
(unknown_svalue::maybe_fold_bits_within): New.
(poisoned_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
(poisoned_svalue::key_t::is_empty): Likewise.
(default_hash_traits<poisoned_svalue::key_t>::empty_zero_p): Make
false.
(setjmp_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
(setjmp_svalue::key_t::is_empty): Likewise.
(default_hash_traits<setjmp_svalue::key_t>::empty_zero_p): Make
false.
(unaryop_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
(unaryop_svalue::key_t::is_empty): Likewise.
(unaryop_svalue::maybe_fold_bits_within): New.
(default_hash_traits<unaryop_svalue::key_t>::empty_zero_p): Make
false.
(binop_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
(binop_svalue::key_t::is_empty): Likewise.
(default_hash_traits<binop_svalue::key_t>::empty_zero_p): Make
false.
(sub_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
(sub_svalue::key_t::is_empty): Likewise.
(default_hash_traits<sub_svalue::key_t>::empty_zero_p): Make
false.
(class repeated_svalue): New.
(is_a_helper <const repeated_svalue *>::test): New.
(struct default_hash_traits<repeated_svalue::key_t>): New.
(class bits_within_svalue): New.
(is_a_helper <const bits_within_svalue *>::test): New.
(struct default_hash_traits<bits_within_svalue::key_t>): New.
(widening_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
(widening_svalue::key_t::is_empty): Likewise.
(default_hash_traits<widening_svalue::key_t>::empty_zero_p): Make
false.
(compound_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
(compound_svalue::key_t::is_empty): Likewise.
(compound_svalue::maybe_fold_bits_within): New.
(default_hash_traits<compound_svalue::key_t>::empty_zero_p): Make
false.
gcc/testsuite/ChangeLog:
PR analyzer/95006
* gcc.dg/analyzer/clobbers-1.c: New test.
* gcc.dg/analyzer/clobbers-2.c: New test.
* gcc.dg/analyzer/data-model-1.c (test_26): Mark xfail as fixed.
(test_28): Likewise.
(test_52): Likewise. Add coverage for end of buffer.
* gcc.dg/analyzer/explode-1.c: Add leak warning.
* gcc.dg/analyzer/memset-1.c (test_3): Mark xfail as fixed.
(test_4): Use char. Mark xfail as fixed.
(test_6b): New.
(test_7): Mark xfail as fixed. Add coverage for start of buffer.
(test_8): New.
(test_9): New.
* gcc.dg/analyzer/memset-CVE-2017-18549-1.c: New test.
* gcc.dg/analyzer/symbolic-8.c: New test.
Signed-off-by: David Malcolm <dmalcolm@redhat.com>=
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic