diff --git a/clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp b/clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp --- a/clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp @@ -11,6 +11,7 @@ // //===----------------------------------------------------------------------===// +#include "clang/AST/ASTContext.h" #include "clang/AST/CharUnits.h" #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" #include "clang/StaticAnalyzer/Checkers/Taint.h" @@ -82,6 +83,9 @@ // symbolic expressions remove this function. Note that this can not be used in // the constraint manager as is, since this does not handle overflows. It is // safe to assume, however, that memory offsets will not overflow. +// NOTE: this is a "naive" simplification that does not consider the effects +// of overflows and signed<->unsigned conversions. Callers of this function +// need to be aware of these corner cases! static std::pair getSimplifiedOffsets(NonLoc offset, nonloc::ConcreteInt extent, SValBuilder &svalBuilder) { @@ -139,45 +143,62 @@ NonLoc rawOffsetVal = rawOffset.getByteOffset(); // CHECK LOWER BOUND: Is byteOffset < extent begin? - // If so, we are doing a load/store - // before the first valid offset in the memory region. + // If so, we are doing a load/store before the first valid offset in the + // memory region. SVal extentBegin = computeExtentBegin(svalBuilder, rawOffset.getRegion()); if (std::optional NV = extentBegin.getAs()) { + bool TriviallySatisfied = false; if (auto ConcreteNV = NV->getAs()) { std::pair simplifiedOffsets = getSimplifiedOffsets(rawOffset.getByteOffset(), *ConcreteNV, svalBuilder); rawOffsetVal = simplifiedOffsets.first; *NV = simplifiedOffsets.second; - } - SVal lowerBound = svalBuilder.evalBinOpNN(state, BO_LT, rawOffsetVal, *NV, - svalBuilder.getConditionType()); + if (auto ConcreteNV = NV->getAs()) { + QualType T = rawOffsetVal.getType(svalBuilder.getContext()); + TriviallySatisfied = + T->isUnsignedIntegerType() && ConcreteNV->getValue().isNegative(); + } + } + if (TriviallySatisfied) { + // In this case we reduced the check for underflow to a comparison like + // (symbol or value with unsigned type) < (negative number) + // which clearly implies that underflow is impossible. However, we need + // to handle this case separately because evaluating this comparison with + // evalBinOpNN can perform a signed->unsigned conversion that turns the + // negative number into a huge positive value and leads to wildly + // inaccurate conclusions. + ; // we have nothing to do in this case + } else { + SVal lowerBound = svalBuilder.evalBinOpNN(state, BO_LT, rawOffsetVal, *NV, + svalBuilder.getConditionType()); + + std::optional lowerBoundToCheck = lowerBound.getAs(); + if (!lowerBoundToCheck) + return; - std::optional lowerBoundToCheck = lowerBound.getAs(); - if (!lowerBoundToCheck) - return; + ProgramStateRef state_precedesLowerBound, state_withinLowerBound; + std::tie(state_precedesLowerBound, state_withinLowerBound) = + state->assume(*lowerBoundToCheck); - ProgramStateRef state_precedesLowerBound, state_withinLowerBound; - std::tie(state_precedesLowerBound, state_withinLowerBound) = - state->assume(*lowerBoundToCheck); + // Are we constrained enough to definitely precede the lower bound? + if (state_precedesLowerBound && !state_withinLowerBound) { + reportOOB(checkerContext, state_precedesLowerBound, OOB_Precedes); + return; + } - // Are we constrained enough to definitely precede the lower bound? - if (state_precedesLowerBound && !state_withinLowerBound) { - reportOOB(checkerContext, state_precedesLowerBound, OOB_Precedes); - return; + // Otherwise, assume the constraint of the lower bound. + assert(state_withinLowerBound); + state = state_withinLowerBound; } - - // Otherwise, assume the constraint of the lower bound. - assert(state_withinLowerBound); - state = state_withinLowerBound; } do { - // CHECK UPPER BOUND: Is byteOffset >= size(baseRegion)? If so, - // we are doing a load/store after the last valid offset. + // CHECK UPPER BOUND: Is byteOffset >= size(baseRegion)? + // If so, we are doing a load/store after the last valid offset. const MemRegion *MR = rawOffset.getRegion(); DefinedOrUnknownSVal Size = getDynamicExtent(state, MR, svalBuilder); if (!isa(Size)) @@ -201,7 +222,7 @@ ProgramStateRef state_exceedsUpperBound, state_withinUpperBound; std::tie(state_exceedsUpperBound, state_withinUpperBound) = - state->assume(*upperboundToCheck); + state->assume(*upperboundToCheck); // If we are under constrained and the index variables are tainted, report. if (state_exceedsUpperBound && state_withinUpperBound) { diff --git a/clang/test/Analysis/out-of-bounds-false-positive.c b/clang/test/Analysis/array-bound-v2-constraint-check.c rename from clang/test/Analysis/out-of-bounds-false-positive.c rename to clang/test/Analysis/array-bound-v2-constraint-check.c --- a/clang/test/Analysis/out-of-bounds-false-positive.c +++ b/clang/test/Analysis/array-bound-v2-constraint-check.c @@ -8,12 +8,11 @@ const char a[] = "abcd"; // extent: 5 bytes void symbolic_size_t_and_int0(size_t len) { - // FIXME: Should not warn for this. - (void)a[len + 1]; // expected-warning {{Out of bound memory access}} + (void)a[len + 1]; // no-warning // We infered that the 'len' must be in a specific range to make the previous indexing valid. // len: [0,3] - clang_analyzer_eval(len <= 3); // expected - warning {{TRUE}} - clang_analyzer_eval(len <= 2); // expected - warning {{UNKNOWN}} + clang_analyzer_eval(len <= 3); // expected-warning {{TRUE}} + clang_analyzer_eval(len <= 2); // expected-warning {{UNKNOWN}} } void symbolic_size_t_and_int1(size_t len) {