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 <dmalcolm@redhat.com>
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 @@
closed one. */
void
-bound::ensure_closed (bool is_upper)
+bound::ensure_closed (enum bound_kind bound_kind)
{
if (!m_closed)
{
@@ -125,7 +125,7 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
/* 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 @@
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 @@
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 @@
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 @@
class constraint_manager;
+enum bound_kind
+{
+ BK_LOWER,
+ BK_UPPER
+};
+
/* One of the end-points of a range. */
struct bound
@@ -33,7 +39,7 @@
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 @@
/* 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 @@
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 @@
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 "" } */
+}
