Author: Balázs Benics Date: 2026-07-13T13:04:17+01:00 New Revision: db28e48d67e3b0c44d88be9ea2d28eca2d239a9a
URL: https://github.com/llvm/llvm-project/commit/db28e48d67e3b0c44d88be9ea2d28eca2d239a9a DIFF: https://github.com/llvm/llvm-project/commit/db28e48d67e3b0c44d88be9ea2d28eca2d239a9a.diff LOG: [analyzer] Smarter range inference for {+,-,*} (#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 Added: Modified: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp clang/test/Analysis/ArrayBound/assumption-reporting.c clang/test/Analysis/bitwise-shift-common.c clang/test/Analysis/constant-folding.c clang/test/Analysis/malloc.c clang/test/Analysis/string.c Removed: ################################################################################ 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 diff erent 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
