From c4b8f3730a80025192fdb485ad2535c165340e41 Mon Sep 17 00:00:00 2001 From: David Malcolm Date: Thu, 20 Jan 2022 09:51:50 -0500 Subject: [PATCH] analyzer: reject ((i + 1 > 0) && (i < 0)) for integers [PR94362] PR analyzer/94362 reports a false positive from -Wanalyzer-null-dereference seen when analyzing OpenSSL. The root cause is that the analyzer's path feasibility checker erroneously considers this to be feasible: (R + 1 > 0) && (R < 0) for int R (the return value from sk_EVP_PKEY_ASN1_METHOD_num), whereas it's not satisfiable for any int R. This patch makes the constraint manager try harder to reject such combinations of conditions, fixing the false positive; perhaps in the longer term we ought to use an SMT solver. gcc/analyzer/ChangeLog: PR analyzer/94362 * constraint-manager.cc (bound::ensure_closed): Convert param to enum bound_kind. (range::constrained_to_single_element): Likewise. (range::add_bound): New. (constraint_manager::add_constraint): Handle SVAL + OFFSET compared to a constant. (constraint_manager::get_ec_bounds): Rewrite in terms of range::add_bound. (constraint_manager::eval_condition): Reject if range::add_bound fails. (selftest::test_constant_comparisons): Add test coverage for various impossible combinations of integer comparisons. * constraint-manager.h (enum bound_kind): New. (struct bound): Likewise. (bound::ensure_closed): Convert to param to enum bound_kind. (struct range): Convert to... (class range): ...this, making fields private. (range::add_bound): New decls. * region-model.cc (region_model::add_constraint): Fail if constraint_manager::add_constraint fails. gcc/testsuite/ChangeLog: PR analyzer/94362 * gcc.dg/analyzer/pr94362-1.c: New test. * gcc.dg/analyzer/pr94362-2.c: New test. Signed-off-by: David Malcolm --- gcc/analyzer/constraint-manager.cc | 172 ++++++++++++++++++++++++++++-- gcc/analyzer/constraint-manager.h | 15 ++- gcc/analyzer/region-model.cc | 5 +- gcc/testsuite/gcc.dg/analyzer/pr94362-1.c | 60 +++++++++++ gcc/testsuite/gcc.dg/analyzer/pr94362-2.c | 42 ++++++++ 5 files changed, 281 insertions(+), 13 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/analyzer/pr94362-1.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/pr94362-2.c diff --git a/gcc/analyzer/constraint-manager.cc b/gcc/analyzer/constraint-manager.cc index 568e715..7c4a85b 100644 --- a/gcc/analyzer/constraint-manager.cc +++ b/gcc/analyzer/constraint-manager.cc @@ -117,7 +117,7 @@ minus_one (tree cst) closed one. */ void -bound::ensure_closed (bool is_upper) +bound::ensure_closed (enum bound_kind bound_kind) { if (!m_closed) { @@ -125,7 +125,7 @@ bound::ensure_closed (bool is_upper) For example, convert 3 < x into 4 <= x, and convert x < 5 into x <= 4. */ gcc_assert (CONSTANT_CLASS_P (m_constant)); - m_constant = fold_build2 (is_upper ? MINUS_EXPR : PLUS_EXPR, + m_constant = fold_build2 (bound_kind == BK_UPPER ? MINUS_EXPR : PLUS_EXPR, TREE_TYPE (m_constant), m_constant, integer_one_node); gcc_assert (CONSTANT_CLASS_P (m_constant)); @@ -205,8 +205,8 @@ range::constrained_to_single_element () return NULL_TREE; /* Convert any open bounds to closed bounds. */ - m_lower_bound.ensure_closed (false); - m_upper_bound.ensure_closed (true); + m_lower_bound.ensure_closed (BK_LOWER); + m_upper_bound.ensure_closed (BK_UPPER); // Are they equal? tree comparison = fold_binary (EQ_EXPR, boolean_type_node, @@ -301,6 +301,80 @@ range::above_upper_bound (tree rhs_const) const m_upper_bound.m_constant).is_true (); } +/* Attempt to add B to the bound of the given kind of this range. + Return true if feasible; false if infeasible. */ + +bool +range::add_bound (bound b, enum bound_kind bound_kind) +{ + b.ensure_closed (bound_kind); + + switch (bound_kind) + { + default: + gcc_unreachable (); + case BK_LOWER: + /* Discard redundant bounds. */ + if (m_lower_bound.m_constant) + { + m_lower_bound.ensure_closed (BK_LOWER); + if (!tree_int_cst_lt (b.m_constant, + m_lower_bound.m_constant)) + return true; + } + m_lower_bound = b; + break; + case BK_UPPER: + /* Discard redundant bounds. */ + if (m_upper_bound.m_constant) + { + m_upper_bound.ensure_closed (BK_UPPER); + if (tree_int_cst_le (b.m_constant, + m_upper_bound.m_constant)) + return true; + } + m_upper_bound = b; + break; + } + if (m_lower_bound.m_constant + && m_upper_bound.m_constant) + { + m_lower_bound.ensure_closed (BK_LOWER); + m_upper_bound.ensure_closed (BK_UPPER); + + /* Reject LOWER <= V <= UPPER when LOWER > UPPER. */ + if (!tree_int_cst_le (m_lower_bound.m_constant, + m_upper_bound.m_constant)) + return false; + } + return true; +} + +/* Attempt to add (RANGE OP RHS_CONST) as a bound to this range. + Return true if feasible; false if infeasible. */ + +bool +range::add_bound (enum tree_code op, tree rhs_const) +{ + switch (op) + { + default: + return true; + case LT_EXPR: + /* "V < RHS_CONST" */ + return add_bound (bound (rhs_const, false), BK_UPPER); + case LE_EXPR: + /* "V <= RHS_CONST" */ + return add_bound (bound (rhs_const, true), BK_UPPER); + case GE_EXPR: + /* "V >= RHS_CONST" */ + return add_bound (bound (rhs_const, true), BK_LOWER); + case GT_EXPR: + /* "V > RHS_CONST" */ + return add_bound (bound (rhs_const, false), BK_LOWER); + } +} + /* struct bounded_range. */ bounded_range::bounded_range (const_tree lower, const_tree upper) @@ -1718,6 +1792,27 @@ constraint_manager::add_constraint (const svalue *lhs, return false; } + /* If adding + (SVAL + OFFSET) > CST, + then that can imply: + SVAL > (CST - OFFSET). */ + if (const binop_svalue *lhs_binop = lhs->dyn_cast_binop_svalue ()) + if (tree rhs_cst = rhs->maybe_get_constant ()) + if (tree offset = lhs_binop->get_arg1 ()->maybe_get_constant ()) + if ((op == GT_EXPR || op == LT_EXPR + || op == GE_EXPR || op == LE_EXPR) + && lhs_binop->get_op () == PLUS_EXPR) + { + tree offset_of_cst = fold_build2 (MINUS_EXPR, TREE_TYPE (rhs_cst), + rhs_cst, offset); + const svalue *implied_lhs = lhs_binop->get_arg0 (); + enum tree_code implied_op = op; + const svalue *implied_rhs + = m_mgr->get_or_create_constant_svalue (offset_of_cst); + if (!add_constraint (implied_lhs, implied_op, implied_rhs)) + return false; + } + add_unknown_constraint (lhs_ec_id, op, rhs_ec_id); return true; } @@ -2241,12 +2336,12 @@ constraint_manager::get_ec_bounds (equiv_class_id ec_id) const case CONSTRAINT_LT: /* We have "EC_ID < OTHER_CST". */ - result.m_upper_bound = bound (other_cst, false); + result.add_bound (bound (other_cst, false), BK_UPPER); break; case CONSTRAINT_LE: /* We have "EC_ID <= OTHER_CST". */ - result.m_upper_bound = bound (other_cst, true); + result.add_bound (bound (other_cst, true), BK_UPPER); break; } } @@ -2263,13 +2358,13 @@ constraint_manager::get_ec_bounds (equiv_class_id ec_id) const case CONSTRAINT_LT: /* We have "OTHER_CST < EC_ID" i.e. "EC_ID > OTHER_CST". */ - result.m_lower_bound = bound (other_cst, false); + result.add_bound (bound (other_cst, false), BK_LOWER); break; case CONSTRAINT_LE: /* We have "OTHER_CST <= EC_ID" i.e. "EC_ID >= OTHER_CST". */ - result.m_lower_bound = bound (other_cst, true); + result.add_bound (bound (other_cst, true), BK_LOWER); break; } } @@ -2350,7 +2445,15 @@ constraint_manager::eval_condition (equiv_class_id lhs_ec, /* Look at existing bounds on LHS_EC. */ range lhs_bounds = get_ec_bounds (lhs_ec); - return lhs_bounds.eval_condition (op, rhs_const); + tristate result = lhs_bounds.eval_condition (op, rhs_const); + if (result.is_known ()) + return result; + + /* Also reject if range::add_bound fails. */ + if (!lhs_bounds.add_bound (op, rhs_const)) + return tristate (false); + + return tristate::unknown (); } /* Evaluate the condition LHS OP RHS, without modifying this @@ -3452,6 +3555,7 @@ test_transitivity () static void test_constant_comparisons () { + tree int_1 = build_int_cst (integer_type_node, 1); tree int_3 = build_int_cst (integer_type_node, 3); tree int_4 = build_int_cst (integer_type_node, 4); tree int_5 = build_int_cst (integer_type_node, 5); @@ -3462,6 +3566,8 @@ test_constant_comparisons () tree a = build_global_decl ("a", integer_type_node); tree b = build_global_decl ("b", integer_type_node); + tree a_plus_one = build2 (PLUS_EXPR, integer_type_node, a, int_1); + /* Given a >= 1024, then a <= 1023 should be impossible. */ { region_model_manager mgr; @@ -3562,6 +3668,54 @@ test_constant_comparisons () ASSERT_CONDITION_UNKNOWN (model, f, EQ_EXPR, float_4); ASSERT_CONDITION_UNKNOWN (model, f, EQ_EXPR, int_4); } + + /* "a > 3 && a <= 3" should be impossible. */ + { + region_model_manager mgr; + region_model model (&mgr); + ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3); + ADD_UNSAT_CONSTRAINT (model, a, LE_EXPR, int_3); + } + + /* "(a + 1) > 3 && a < 3" should be impossible. */ + { + region_model_manager mgr; + { + region_model model (&mgr); + ADD_SAT_CONSTRAINT (model, a_plus_one, GT_EXPR, int_3); + ADD_UNSAT_CONSTRAINT (model, a, LT_EXPR, int_3); + } + { + region_model model (&mgr); + ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_3); + ADD_UNSAT_CONSTRAINT (model, a_plus_one, GT_EXPR, int_3); + } + } + + /* "3 < a < 4" should be impossible for integer a. */ + { + region_model_manager mgr; + { + region_model model (&mgr); + ADD_SAT_CONSTRAINT (model, int_3, LT_EXPR, a); + ADD_UNSAT_CONSTRAINT (model, a, LT_EXPR, int_4); + } + { + region_model model (&mgr); + ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_4); + ADD_UNSAT_CONSTRAINT (model, int_3, LT_EXPR, a); + } + { + region_model model (&mgr); + ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3); + ADD_UNSAT_CONSTRAINT (model, int_4, GT_EXPR, a); + } + { + region_model model (&mgr); + ADD_SAT_CONSTRAINT (model, int_4, GT_EXPR, a); + ADD_UNSAT_CONSTRAINT (model, a, GT_EXPR, int_3); + } + } } /* Verify various lower-level implementation details about diff --git a/gcc/analyzer/constraint-manager.h b/gcc/analyzer/constraint-manager.h index e93fa7f..f67c764 100644 --- a/gcc/analyzer/constraint-manager.h +++ b/gcc/analyzer/constraint-manager.h @@ -25,6 +25,12 @@ namespace ana { class constraint_manager; +enum bound_kind +{ + BK_LOWER, + BK_UPPER +}; + /* One of the end-points of a range. */ struct bound @@ -33,7 +39,7 @@ struct bound bound (tree constant, bool closed) : m_constant (constant), m_closed (closed) {} - void ensure_closed (bool is_upper); + void ensure_closed (enum bound_kind bound_kind); const char * get_relation_as_str () const; @@ -44,8 +50,9 @@ struct bound /* A range of values, used for determining if a value has been constrained to just one possible constant value. */ -struct range +class range { +public: range () : m_lower_bound (), m_upper_bound () {} range (const bound &lower, const bound &upper) : m_lower_bound (lower), m_upper_bound (upper) {} @@ -60,6 +67,10 @@ struct range bool below_lower_bound (tree rhs_const) const; bool above_upper_bound (tree rhs_const) const; + bool add_bound (bound b, enum bound_kind bound_kind); + bool add_bound (enum tree_code op, tree rhs_const); + +private: bound m_lower_bound; bound m_upper_bound; }; diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc index b58d089..f6b7f98 100644 --- a/gcc/analyzer/region-model.cc +++ b/gcc/analyzer/region-model.cc @@ -2801,8 +2801,9 @@ region_model::add_constraint (const svalue *lhs, if (add_constraints_from_binop (lhs, op, rhs, &out, ctxt)) return out; - /* Store the constraint. */ - m_constraints->add_constraint (lhs, op, rhs); + /* Attempt to store the constraint. */ + if (!m_constraints->add_constraint (lhs, op, rhs)) + return false; /* Notify the context, if any. This exists so that the state machines in a program_state can be notified about the condition, and so can diff --git a/gcc/testsuite/gcc.dg/analyzer/pr94362-1.c b/gcc/testsuite/gcc.dg/analyzer/pr94362-1.c new file mode 100644 index 0000000..1302ced --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/pr94362-1.c @@ -0,0 +1,60 @@ +/* { dg-additional-options "-Wno-analyzer-too-complex" } */ +/* TODO: remove the need for -Wno-analyzer-too-complex. */ + +typedef struct evp_pkey_asn1_method_st EVP_PKEY_ASN1_METHOD; +typedef struct engine_st ENGINE; +struct stack_st_EVP_PKEY_ASN1_METHOD; +struct evp_pkey_asn1_method_st { + unsigned long pkey_flags; +}; + +const EVP_PKEY_ASN1_METHOD *ENGINE_pkey_asn1_find_str(ENGINE **pe, + const char *str, int len); +extern int +sk_EVP_PKEY_ASN1_METHOD_num(const struct stack_st_EVP_PKEY_ASN1_METHOD *sk); +extern const EVP_PKEY_ASN1_METHOD * +sk_EVP_PKEY_ASN1_METHOD_value(const struct stack_st_EVP_PKEY_ASN1_METHOD *sk, + int idx); +extern const EVP_PKEY_ASN1_METHOD hmac_asn1_meth; +static const EVP_PKEY_ASN1_METHOD *standard_methods[] = {&hmac_asn1_meth}; +static struct stack_st_EVP_PKEY_ASN1_METHOD *app_methods = ((void *)0); + +int EVP_PKEY_asn1_get_count(void) { + int num = (sizeof(standard_methods) / sizeof((standard_methods)[0])); + if (app_methods) + num += sk_EVP_PKEY_ASN1_METHOD_num(app_methods); + return num; +} + +const EVP_PKEY_ASN1_METHOD *EVP_PKEY_asn1_get0(int idx) { + int num = (sizeof(standard_methods) / sizeof((standard_methods)[0])); + if (idx < 0) + return ((void *)0); + if (idx < num) + return standard_methods[idx]; + idx -= num; + return sk_EVP_PKEY_ASN1_METHOD_value(app_methods, idx); +} + +const EVP_PKEY_ASN1_METHOD *EVP_PKEY_asn1_find_str(ENGINE **pe, const char *str, + int len) { + int i; + const EVP_PKEY_ASN1_METHOD *ameth = ((void *)0); + + if (pe) { + ENGINE *e; + ameth = ENGINE_pkey_asn1_find_str(&e, str, len); + if (ameth) { + *pe = e; + return ameth; + } + *pe = ((void *)0); + } + for (i = EVP_PKEY_asn1_get_count(); i-- > 0;) { + ameth = EVP_PKEY_asn1_get0(i); + if (ameth->pkey_flags & 0x1) + continue; + return ameth; + } + return ((void *)0); +} diff --git a/gcc/testsuite/gcc.dg/analyzer/pr94362-2.c b/gcc/testsuite/gcc.dg/analyzer/pr94362-2.c new file mode 100644 index 0000000..301d2ed --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/pr94362-2.c @@ -0,0 +1,42 @@ +/* Verify that we consider various paths to be impossible, + using functions to thwart early optimizations. */ + +#include "analyzer-decls.h" + +void test_1 (int idx) +{ + if (idx > 0) + if (idx - 1 < 0) + __analyzer_dump_path (); /* { dg-bogus "" } */ +} + +static int called_by_test_1a (int idx) +{ + return idx - 1; +} + +void test_1a (int idx) +{ + if (idx > 0) + if (called_by_test_1a (idx) < 0) + __analyzer_dump_path (); /* { dg-bogus "" } */ +} + +void test_2 (int idx) +{ + if (idx + 1 > 0) + if (idx < 0) + __analyzer_dump_path (); /* { dg-bogus "" } */ +} + +static int called_by_test_2a (int idx) +{ + return idx + 1; +} + +void test_2a (int idx) +{ + if (called_by_test_2a (idx) > 0) + if (idx < 0) + __analyzer_dump_path (); /* { dg-bogus "" } */ +} -- 2.7.4