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 @@ -54,8 +54,11 @@ : baseRegion(nullptr), byteOffset(UnknownVal()) {} public: - RegionRawOffsetV2(const SubRegion* base, SVal offset) - : baseRegion(base), byteOffset(offset) {} + RegionRawOffsetV2(const SubRegion *base, SVal offset) + : baseRegion(base), byteOffset(offset) { + if (baseRegion) + assert(llvm::isa(byteOffset)); + } NonLoc getByteOffset() const { return byteOffset.castAs(); } const SubRegion *getRegion() const { return baseRegion; } @@ -69,19 +72,12 @@ }; } -static SVal computeExtentBegin(SValBuilder &svalBuilder, - const MemRegion *region) { - const MemSpaceRegion *SR = region->getMemorySpace(); - if (SR->getKind() == MemRegion::UnknownSpaceRegionKind) - return UnknownVal(); - else - return svalBuilder.makeZeroArrayIndex(); -} - // TODO: once the constraint manager is smart enough to handle non simplified // 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: callers of this function need to be aware of the effects of overflows +// and signed<->unsigned conversions! static std::pair getSimplifiedOffsets(NonLoc offset, nonloc::ConcreteInt extent, SValBuilder &svalBuilder) { @@ -114,6 +110,38 @@ return std::pair(offset, extent); } +// Evaluate the comparison Value < Threshold with the help of the custom +// simplification algorithm defined for this checker. Return a pair of states, +// where the first one corresponds to "value below threshold" and the second +// corresponds to "value at or above threshold". Returns {nullptr, nullptr} in +// the case when the evaluation fails. +static std::pair +compareValueToThreshold(ProgramStateRef State, NonLoc Value, NonLoc Threshold, + SValBuilder &SVB) { + if (auto ConcreteTh = Threshold.getAs()) { + std::tie(Value, Threshold) = getSimplifiedOffsets(Value, *ConcreteTh, SVB); + } + if (auto ConcreteTh = Threshold.getAs()) { + QualType T = Value.getType(SVB.getContext()); + if (T->isUnsignedIntegerType() && ConcreteTh->getValue().isNegative()) { + // In this case we reduced the bound check to a comparison of the form + // (symbol or value with unsigned type) < (negative number) + // which is always false. We are handling these cases separately because + // evalBinOpNN can perform a signed->unsigned conversion that turns the + // negative number into a huge positive value and leads to wildly + // inaccurate conclusions. + return {nullptr, State}; + } + } + SVal belowThreshold = + SVB.evalBinOpNN(State, BO_LT, Value, Threshold, SVB.getConditionType()); + + if (std::optional belowThresholdNL = belowThreshold.getAs()) + return State->assume(*belowThresholdNL); + + return {nullptr, nullptr}; +} + void ArrayBoundCheckerV2::checkLocation(SVal location, bool isLoad, const Stmt* LoadS, CheckerContext &checkerContext) const { @@ -136,93 +164,56 @@ if (!rawOffset.getRegion()) return; - 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. + // At this point we know that rawOffset is not default-constructed so we may + // call this: + NonLoc ByteOffset = rawOffset.getByteOffset(); - SVal extentBegin = computeExtentBegin(svalBuilder, rawOffset.getRegion()); - - if (std::optional NV = extentBegin.getAs()) { - 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()); - - std::optional lowerBoundToCheck = lowerBound.getAs(); - if (!lowerBoundToCheck) - return; + // CHECK LOWER BOUND + const MemSpaceRegion *SR = rawOffset.getRegion()->getMemorySpace(); + if (SR->getKind() != MemRegion::UnknownSpaceRegionKind) { + // a pointer to UnknownSpaceRegionKind may point to the middle of + // an allocated region ProgramStateRef state_precedesLowerBound, state_withinLowerBound; std::tie(state_precedesLowerBound, state_withinLowerBound) = - state->assume(*lowerBoundToCheck); + compareValueToThreshold(state, ByteOffset, + svalBuilder.makeZeroArrayIndex(), svalBuilder); - // Are we constrained enough to definitely precede the lower bound? if (state_precedesLowerBound && !state_withinLowerBound) { + // We know that the index definitely precedes the lower bound reportOOB(checkerContext, state_precedesLowerBound, OOB_Precedes); return; } - // Otherwise, assume the constraint of the lower bound. - assert(state_withinLowerBound); - state = state_withinLowerBound; + if (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. - const MemRegion *MR = rawOffset.getRegion(); - DefinedOrUnknownSVal Size = getDynamicExtent(state, MR, svalBuilder); - if (!isa(Size)) - break; - - if (auto ConcreteSize = Size.getAs()) { - std::pair simplifiedOffsets = - getSimplifiedOffsets(rawOffset.getByteOffset(), *ConcreteSize, - svalBuilder); - rawOffsetVal = simplifiedOffsets.first; - Size = simplifiedOffsets.second; - } - - SVal upperbound = svalBuilder.evalBinOpNN(state, BO_GE, rawOffsetVal, - Size.castAs(), - svalBuilder.getConditionType()); - - std::optional upperboundToCheck = upperbound.getAs(); - if (!upperboundToCheck) - break; - - ProgramStateRef state_exceedsUpperBound, state_withinUpperBound; - std::tie(state_exceedsUpperBound, state_withinUpperBound) = - state->assume(*upperboundToCheck); - - // If we are under constrained and the index variables are tainted, report. - if (state_exceedsUpperBound && state_withinUpperBound) { - SVal ByteOffset = rawOffset.getByteOffset(); + // CHECK UPPER BOUND + DefinedOrUnknownSVal Size = + getDynamicExtent(state, rawOffset.getRegion(), svalBuilder); + if (std::optional KnownSize = Size.getAs()) { + ProgramStateRef state_withinUpperBound, state_exceedsUpperBound; + std::tie(state_withinUpperBound, state_exceedsUpperBound) = + compareValueToThreshold(state, ByteOffset, *KnownSize, svalBuilder); + + if (state_exceedsUpperBound) { + if (!state_withinUpperBound) { + // We know that the index definitely exceeds the upper bound + reportOOB(checkerContext, state_exceedsUpperBound, OOB_Excedes); + return; + } if (isTainted(state, ByteOffset)) { + // Both cases are possible, but the index is tainted, so report reportOOB(checkerContext, state_exceedsUpperBound, OOB_Tainted, std::make_unique(ByteOffset)); return; } - } else if (state_exceedsUpperBound) { - // If we are constrained enough to definitely exceed the upper bound, - // report. - assert(!state_withinUpperBound); - reportOOB(checkerContext, state_exceedsUpperBound, OOB_Excedes); - return; } - assert(state_withinUpperBound); - state = state_withinUpperBound; + if (state_withinUpperBound) + state = state_withinUpperBound; } - while (false); checkerContext.addTransition(state); } 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) {