https://github.com/steakhal created
https://github.com/llvm/llvm-project/pull/209048
SymbolicRangeInferrer previously fell back to the full range of the result type
for BO_Add, BO_Sub and BO_Mul, discarding any constraints known about the
operands.
This caused a false positive in optin.taint.TaintedAlloc: a bounded tainted
value multiplied by a constant
(e.g. `malloc(groups * sizeof(gid_t))` with `groups` bounded) was treated as
unbounded whenever the multiplication was done in a wide (e.g. 64-bit size_t)
type, because the operand's range was lost. A 32-bit multiplication
accidentally avoided the warning only because the narrow result type already
bounds the value below SIZE_MAX/4. Fixes #173113
---
With `inferFromCorners` we compute the smallest and largest possible outcome of
the two range sets for `LHS {+,-,*} RHS`. If fails for some reason, it falls
back to the previous behavior and takes [MIN, MAX] for type T - the most
conservative range.
This patch also covers some pre-existing FIXMEs in the tests. I didn't evaluate
this change - however, I think it's harmless.
Assisted-by: Claude Opus 4.8
From b92b45a502804516d002595da0168378f7b38eaf Mon Sep 17 00:00:00 2001
From: Balazs Benics <[email protected]>
Date: Sun, 12 Jul 2026 20:36:59 +0100
Subject: [PATCH] [analyzer] Smarter range inference for {+,-,*}
SymbolicRangeInferrer previously fell back to the full range of the
result type for BO_Add, BO_Sub and BO_Mul, discarding any constraints
known about the operands.
This caused a false positive in optin.taint.TaintedAlloc:
a bounded tainted value multiplied by a constant
(e.g. `malloc(groups * sizeof(gid_t))` with `groups` bounded)
was treated as unbounded whenever the multiplication was done in a wide
(e.g. 64-bit size_t) type, because the operand's range was lost. A
32-bit multiplication accidentally avoided the warning only because the
narrow result type already bounds the value below SIZE_MAX/4.
Fixes #173113
---
With `inferFromCorners` we compute the smallest and largest possible
outcome of the two range sets for `LHS {+,-,*} RHS`.
If fails for some reason, it falls back to the previous behavior and
takes [MIN, MAX] for type T - the most conservative range.
This patch also covers some pre-existing FIXMEs in the tests.
I didn't evaluate this change - however, I think it's harmless.
Assisted-by: Claude Opus 4.8
---
.../Core/RangeConstraintManager.cpp | 75 +++++++++++
.../ArrayBound/assumption-reporting.c | 16 ++-
clang/test/Analysis/bitwise-shift-common.c | 12 +-
clang/test/Analysis/constant-folding.c | 123 +++++++++++++++++-
clang/test/Analysis/malloc.c | 21 +++
clang/test/Analysis/string.c | 5 +-
6 files changed, 233 insertions(+), 19 deletions(-)
diff --git a/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
b/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
index 0719820aa085e..5c09163b36be9 100644
--- a/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ b/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -1393,6 +1393,54 @@ class SymbolicRangeInferrer
return infer(T);
}
+ /// Infer the range of an additive or multiplicative binary operator from the
+ /// ranges of its operands.
+ RangeSet inferFromCorners(BinaryOperator::Opcode Op, Range LHS, Range RHS,
+ QualType T) {
+ const bool IsUnsigned = T->isUnsignedIntegerOrEnumerationType();
+
+ auto Eval = [&](const llvm::APSInt &L,
+ const llvm::APSInt &R) -> std::optional<llvm::APSInt> {
+ bool Overflow = false;
+ llvm::APInt Result;
+ switch (Op) {
+ case BO_Add:
+ Result = IsUnsigned ? L.uadd_ov(R, Overflow) : L.sadd_ov(R, Overflow);
+ break;
+ case BO_Sub:
+ Result = IsUnsigned ? L.usub_ov(R, Overflow) : L.ssub_ov(R, Overflow);
+ break;
+ case BO_Mul:
+ Result = IsUnsigned ? L.umul_ov(R, Overflow) : L.smul_ov(R, Overflow);
+ break;
+ default:
+ llvm_unreachable("only +, - and * are handled here");
+ }
+ if (Overflow)
+ return std::nullopt;
+ return llvm::APSInt(Result, IsUnsigned);
+ };
+
+ // Fold over the four corners of the [LHS] x [RHS] rectangle, computing
each
+ // one lazily and merging it into the running [Min, Max].
+ std::optional<llvm::APSInt> Min, Max;
+ for (const llvm::APSInt &L : {LHS.From(), LHS.To()}) {
+ for (const llvm::APSInt &R : {RHS.From(), RHS.To()}) {
+ std::optional<llvm::APSInt> Corner = Eval(L, R);
+ // A disengaged corner means the operation overflowed the result type,
+ // so the true result may wrap around and we cannot bound it.
+ if (!Corner.has_value())
+ return infer(T);
+ if (!Min || Corner.value() < *Min)
+ Min = Corner;
+ if (!Max || Corner.value() > *Max)
+ Max = Corner;
+ }
+ }
+ return RangeSet{RangeFactory, ValueFactory.getValue(Min.value()),
+ ValueFactory.getValue(Max.value())};
+ }
+
/// Return a symmetrical range for the given range and type.
///
/// If T is signed, return the smallest range [-x..x] that covers the
original
@@ -1841,6 +1889,27 @@ RangeSet
SymbolicRangeInferrer::VisitBinaryOperator<BO_Rem>(Range LHS,
return {RangeFactory, ValueFactory.getValue(Min),
ValueFactory.getValue(Max)};
}
+template <>
+RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Add>(Range LHS,
+ Range RHS,
+ QualType T) {
+ return inferFromCorners(BO_Add, LHS, RHS, T);
+}
+
+template <>
+RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Sub>(Range LHS,
+ Range RHS,
+ QualType T) {
+ return inferFromCorners(BO_Sub, LHS, RHS, T);
+}
+
+template <>
+RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Mul>(Range LHS,
+ Range RHS,
+ QualType T) {
+ return inferFromCorners(BO_Mul, LHS, RHS, T);
+}
+
RangeSet SymbolicRangeInferrer::VisitBinaryOperator(RangeSet LHS,
BinaryOperator::Opcode Op,
RangeSet RHS, QualType T) {
@@ -1859,6 +1928,12 @@ RangeSet
SymbolicRangeInferrer::VisitBinaryOperator(RangeSet LHS,
return VisitBinaryOperator<BO_And>(LHS, RHS, T);
case BO_Rem:
return VisitBinaryOperator<BO_Rem>(LHS, RHS, T);
+ case BO_Add:
+ return VisitBinaryOperator<BO_Add>(LHS, RHS, T);
+ case BO_Sub:
+ return VisitBinaryOperator<BO_Sub>(LHS, RHS, T);
+ case BO_Mul:
+ return VisitBinaryOperator<BO_Mul>(LHS, RHS, T);
default:
return infer(T);
}
diff --git a/clang/test/Analysis/ArrayBound/assumption-reporting.c
b/clang/test/Analysis/ArrayBound/assumption-reporting.c
index bffd5d9bc35b5..6ae2a31f22873 100644
--- a/clang/test/Analysis/ArrayBound/assumption-reporting.c
+++ b/clang/test/Analysis/ArrayBound/assumption-reporting.c
@@ -139,10 +139,12 @@ int assumingConvertedToIntP(struct foo f, int arg) {
// result type of the subscript operator.
int a = ((int*)(f.a))[arg];
// expected-note@-1 {{Assuming index is non-negative and less than 2, the
number of 'int' elements in 'f.a'}}
- // However, if the extent of the memory region is not divisible by the
- // element size, the checker measures the offset and extent in bytes.
+ // The extent of 'f.b' (5 bytes) is not divisible by the element size, so in
+ // general the checker would measure the offset and extent in bytes. Here
+ // 'arg' was already constrained to [0, 1] by the access above, so the range
+ // inferrer proves that the byte offset arg*4 is within [0, 5) and no
+ // assumption note is emitted.
int b = ((int*)(f.b))[arg];
- // expected-note@-1 {{Assuming byte offset is less than 5, the extent of
'f.b'}}
int c = TenElements[arg-2];
// expected-warning@-1 {{Out of bound access to memory preceding
'TenElements'}}
// expected-note@-2 {{Access of 'TenElements' at a negative index}}
@@ -160,10 +162,10 @@ int assumingPlainOffset(struct foo f, int arg) {
return 0;
int b = ((int*)(f.b))[arg];
- // expected-note@-1 {{Assuming byte offset is non-negative and less than 5,
the extent of 'f.b'}}
- // FIXME: this should be {{Assuming offset is non-negative}}
- // but the current simplification algorithm doesn't realize that arg <= 1
- // implies that the byte offset arg*4 will be less than 5.
+ // expected-note@-1 {{Assuming index is non-negative}}
+ // Since 'arg' is known to be < 2, the range inferrer proves that the byte
+ // offset arg*4 will be less than 5, so only the lower bound needs to be
+ // assumed here (this used to also require assuming the byte offset was < 5).
int c = TenElements[arg+10];
// expected-warning@-1 {{Out of bound access to memory after the end of
'TenElements'}}
diff --git a/clang/test/Analysis/bitwise-shift-common.c
b/clang/test/Analysis/bitwise-shift-common.c
index 5f37d9976263a..c5a9f4bcdde3c 100644
--- a/clang/test/Analysis/bitwise-shift-common.c
+++ b/clang/test/Analysis/bitwise-shift-common.c
@@ -95,15 +95,11 @@ int too_large_right_operand_compound(unsigned short arg) {
// Note: this would be valid code with an 'unsigned int' because
// unsigned addition is allowed to overflow.
clang_analyzer_value(32+arg);
- // expected-warning@-1 {{32s:{ [-2147483648, 2147483647] }}
- // expected-note@-2 {{32s:{ [-2147483648, 2147483647] }}
+ // expected-warning@-1 {{32s:{ [32, 65567] }}
+ // expected-note@-2 {{32s:{ [32, 65567] }}
return 1 << (32 + arg);
// expected-warning@-1 {{Left shift overflows the capacity of 'int'}}
- // expected-note@-2 {{The result of left shift is undefined because the
right operand is not smaller than 32, the capacity of 'int'}}
- // FIXME: this message should be
- // {{The result of left shift is undefined because the right operand is
>= 32, not smaller than 32, the capacity of 'int'}}
- // but for some reason neither the new logic, nor debug.ExprInspection and
- // clang_analyzer_value reports this range information.
+ // expected-note@-2 {{The result of left shift is undefined because the
right operand is >= 32, not smaller than 32, the capacity of 'int'}}
}
// TEST STATE UPDATES
@@ -116,7 +112,7 @@ void state_update(char a, int *p) {
// expected-note@-1 {{Assuming right operand of bit shift is non-negative
but less than 32}}
*p += 1 << (a + 32);
// expected-warning@-1 {{Left shift overflows the capacity of 'int'}}
- // expected-note@-2 {{The result of left shift is undefined because the
right operand is not smaller than 32, the capacity of 'int'}}
+ // expected-note@-2 {{The result of left shift is undefined because the
right operand is >= 32, not smaller than 32, the capacity of 'int'}}
}
void state_update_2(char a, int *p) {
diff --git a/clang/test/Analysis/constant-folding.c
b/clang/test/Analysis/constant-folding.c
index 620adcd82c66b..a8eb8e83776ff 100644
--- a/clang/test/Analysis/constant-folding.c
+++ b/clang/test/Analysis/constant-folding.c
@@ -1,10 +1,12 @@
-// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -verify
-analyzer-config eagerly-assume=false %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection \
+// RUN: -triple x86_64-pc-linux-gnu -verify -analyzer-config
eagerly-assume=false %s
#define UINT_MAX (~0U)
#define INT_MAX (int)(UINT_MAX & (UINT_MAX >> 1))
#define INT_MIN (int)(UINT_MAX & ~(UINT_MAX >> 1))
void clang_analyzer_eval(int);
+void clang_analyzer_value(int);
// There should be no warnings unless otherwise indicated.
@@ -428,3 +430,122 @@ void testDisequalityRules(unsigned int u1, unsigned int
u2, unsigned int u3,
clang_analyzer_eval(ush != ssh); // expected-warning{{FALSE}}
}
}
+
+void arith_mul_signed_spanning_zero(int x) {
+ if (x < -3 || x > 5)
+ return;
+ clang_analyzer_value(x); // expected-warning{{32s:{ [-3, 5] }}}
+ clang_analyzer_value(x * 2); // expected-warning{{32s:{ [-6, 10] }}}
+}
+
+void arith_mul_negative_multiplier(int x) {
+ if (x < 2 || x > 5)
+ return;
+ clang_analyzer_value(x); // expected-warning{{32s:{ [2, 5] }}}
+ // A negative multiplier flips the order of the corner products.
+ clang_analyzer_value(x * -3); // expected-warning{{32s:{ [-15, -6] }}}
+}
+
+void arith_mul_two_symbols_spanning_zero(int x, int y) {
+ if (x < -3 || x > 5)
+ return;
+ if (y < -2 || y > 4)
+ return;
+ clang_analyzer_value(x); // expected-warning{{32s:{ [-3, 5] }}}
+ clang_analyzer_value(y); // expected-warning{{32s:{ [-2, 4] }}}
+ // Both operands span zero, so the extremes come from different corners.
+ clang_analyzer_value(x * y); // expected-warning{{32s:{ [-12, 20] }}}
+}
+
+void arith_add_bounded(int x) {
+ if (x < 10 || x > 20)
+ return;
+ clang_analyzer_value(x); // expected-warning{{32s:{ [10, 20] }}}
+ clang_analyzer_value(x + 5); // expected-warning{{32s:{ [15, 25] }}}
+}
+
+void arith_unsigned_sub_no_wraparound(unsigned u, unsigned v) {
+ if (u < 20 || u > 30)
+ return;
+ if (v > 5)
+ return;
+ clang_analyzer_value(u); // expected-warning{{32u:{ [20, 30] }}}
+ clang_analyzer_value(v); // expected-warning{{32u:{ [0, 5] }}}
+ // The subtraction cannot wrap here.
+ clang_analyzer_value(u - v); // expected-warning{{32u:{ [15, 30] }}}
+}
+
+void arith_unsigned_sub_wraparound(unsigned u, unsigned v) {
+ if (u > 5)
+ return;
+ if (v > 10)
+ return;
+ clang_analyzer_value(u); // expected-warning{{32u:{ [0, 5] }}}
+ clang_analyzer_value(v); // expected-warning{{32u:{ [0, 10] }}}
+ // u - v can wrap around (e.g. 0u - 10u), so the result must stay the full
+ // unsigned range -- narrowing it here would be unsound.
+ clang_analyzer_value(u - v); // expected-warning{{32u:{ [0, 4294967295] }}}
+}
+
+void arith_signed_mul_overflow(int x) {
+ if (x < 100000 || x > 200000)
+ return;
+ clang_analyzer_value(x); // expected-warning{{32s:{ [100000,
200000] }}}
+ // x * 100000 overflows 'int', so we conservatively fall back to the full
range.
+ clang_analyzer_value(x * 100000); // expected-warning{{32s:{ [-2147483648,
2147483647] }}}
+}
+
+void arith_mul_64bit_bounded(unsigned long long u) {
+ if (u > 100)
+ return;
+ clang_analyzer_value(u); // expected-warning{{64u:{ [0, 100] }}}
+ // Wide (64-bit) operands must be handled without widening.
+ clang_analyzer_value(u * 8); // expected-warning{{64u:{ [0, 800] }}}
+}
+
+void arith_mul_int_min_no_assert(int x) {
+ if (x > INT_MIN + 2)
+ return;
+ clang_analyzer_value(x); // expected-warning{{32s:{ [-2147483648,
-2147483646] }}}
+ // The corner INT_MIN * -1 overflows, so this must fall back to the full
range
+ // rather than asserting inside smul_ov.
+ clang_analyzer_value(x * -1); // expected-warning{{32s:{ [-2147483648,
2147483647] }}}
+}
+
+void arith_mul_int128_bounded(unsigned __int128 x) {
+ if (x > 100)
+ return;
+ clang_analyzer_value(x); // expected-warning{{128u:{ [0, 100] }}}
+ // 128-bit operands must not trip a bit-width assertion.
+ clang_analyzer_value(x * 8); // expected-warning{{128u:{ [0, 800] }}}
+}
+
+void arith_mul_bitint111_bounded(unsigned _BitInt(111) x) {
+ if (x > 100)
+ return;
+ clang_analyzer_value(x); // expected-warning{{111u:{ [0, 100] }}}
+ // 111-bit operands must not trip a bit-width assertion.
+ clang_analyzer_value(x * 8); // expected-warning{{111u:{ [0, 800] }}}
+}
+
+void arith_mul_bitint333_bounded(unsigned _BitInt(333) x) {
+ if (x > 100)
+ return;
+ clang_analyzer_value(x); // expected-warning{{333u:{ [0, 100] }}}
+ // 333-bit operands must not trip a bit-width assertion.
+ clang_analyzer_value(x * 8); // expected-warning{{333u:{ [0, 800] }}}
+}
+
+
+void arith_mul_gappy_over_approximation(int x) {
+ if (x < -3 || x > 5)
+ return;
+ if (x == 1)
+ return;
+ clang_analyzer_value(x); // expected-warning{{32s:{ [-3, 0], [2, 5] }}}
+ // The inference coarsens the gappy range to [-3, 5] before multiplying,
which
+ // stays a sound over-approximation: the coarse result contains every
feasible
+ // product of x * 4.
+ clang_analyzer_value(x * 4); // expected-warning{{32s:{ [-12, 20] }}}
+}
+
diff --git a/clang/test/Analysis/malloc.c b/clang/test/Analysis/malloc.c
index a75144f041de0..4ee09d9022bee 100644
--- a/clang/test/Analysis/malloc.c
+++ b/clang/test/Analysis/malloc.c
@@ -73,6 +73,27 @@ void t3(void) {
free(p);
}
+void t3_mul_bounded(void) {
+ size_t size = 0;
+ scanf("%zu", &size);
+ if (65536 < size)
+ return;
+ // A bounded tainted size stays bounded after multiplication by a constant,
+ // so the product cannot reach a dangerous magnitude. The 64-bit size_t
+ // product must not warn (used to be a false positive because the range of
+ // the multiplication was not inferred from its operands).
+ int *p = malloc(size * sizeof(int)); // No warning expected as the product
is bound
+ free(p);
+}
+
+void t3_mul_unbounded(void) {
+ size_t size = 0;
+ scanf("%zu", &size);
+ // Without a bound the product is still attacker-controlled and can overflow.
+ int *p = malloc(size * sizeof(int)); // expected-warning{{malloc is called
with a tainted (potentially attacker controlled) value}}
+ free(p);
+}
+
void t4(void) {
size_t size = 0;
int *p = malloc(sizeof(int));
diff --git a/clang/test/Analysis/string.c b/clang/test/Analysis/string.c
index 9d2458332b723..ba0b1829a690b 100644
--- a/clang/test/Analysis/string.c
+++ b/clang/test/Analysis/string.c
@@ -246,9 +246,8 @@ void strlen_symbolic_offset(unsigned x) {
const char *str = "abcd";
if (x < 1 || x > 3)
return;
- // FIXME: these should be TRUE
- clang_analyzer_eval(strlen(str + x) >= 1); // expected-warning{{UNKNOWN}}
- clang_analyzer_eval(strlen(str + x) <= 3); // expected-warning{{UNKNOWN}}
+ clang_analyzer_eval(strlen(str + x) >= 1); // expected-warning{{TRUE}}
+ clang_analyzer_eval(strlen(str + x) <= 3); // expected-warning{{TRUE}}
if (x != 1)
return;
clang_analyzer_eval(strlen(str + x) == 3); // expected-warning{{TRUE}}
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
