donat.nagy updated this revision to Diff 515326.
donat.nagy edited the summary of this revision.
donat.nagy added a comment.
I'm publishing the extended variant of this commit (which I mentioned in
earlier comments).
This generalizes the first version of the commit to check for the
unsigned-vs-negative comparison on both bound checks (and eliminates the code
duplication between the two bound checks by moving their logic into a helper
function), so it will behave similarly to Tomasz's solution (which uses the
indirect "use 0 instead of negative numbers" trick to avoid
unsigned-vs-negative comparisons).
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D148355/new/
https://reviews.llvm.org/D148355
Files:
clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp
clang/test/Analysis/array-bound-v2-constraint-check.c
clang/test/Analysis/out-of-bounds-false-positive.c
Index: clang/test/Analysis/array-bound-v2-constraint-check.c
===================================================================
--- clang/test/Analysis/array-bound-v2-constraint-check.c
+++ 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) {
Index: clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp
+++ 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<NonLoc>(byteOffset));
+ }
NonLoc getByteOffset() const { return byteOffset.castAs<NonLoc>(); }
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<NonLoc, nonloc::ConcreteInt>
getSimplifiedOffsets(NonLoc offset, nonloc::ConcreteInt extent,
SValBuilder &svalBuilder) {
@@ -114,6 +110,38 @@
return std::pair<NonLoc, nonloc::ConcreteInt>(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<ProgramStateRef, ProgramStateRef>
+compareValueToThreshold(ProgramStateRef State, NonLoc Value, NonLoc Threshold,
+ SValBuilder &SVB) {
+ if (auto ConcreteTh = Threshold.getAs<nonloc::ConcreteInt>()) {
+ std::tie(Value, Threshold) = getSimplifiedOffsets(Value, *ConcreteTh, SVB);
+ }
+ if (auto ConcreteTh = Threshold.getAs<nonloc::ConcreteInt>()) {
+ 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<NonLoc> belowThresholdNL = belowThreshold.getAs<NonLoc>())
+ 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<NonLoc> NV = extentBegin.getAs<NonLoc>()) {
- if (auto ConcreteNV = NV->getAs<nonloc::ConcreteInt>()) {
- std::pair<NonLoc, nonloc::ConcreteInt> 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<NonLoc> lowerBoundToCheck = lowerBound.getAs<NonLoc>();
- 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<NonLoc>(Size))
- break;
-
- if (auto ConcreteSize = Size.getAs<nonloc::ConcreteInt>()) {
- std::pair<NonLoc, nonloc::ConcreteInt> simplifiedOffsets =
- getSimplifiedOffsets(rawOffset.getByteOffset(), *ConcreteSize,
- svalBuilder);
- rawOffsetVal = simplifiedOffsets.first;
- Size = simplifiedOffsets.second;
- }
-
- SVal upperbound = svalBuilder.evalBinOpNN(state, BO_GE, rawOffsetVal,
- Size.castAs<NonLoc>(),
- svalBuilder.getConditionType());
-
- std::optional<NonLoc> upperboundToCheck = upperbound.getAs<NonLoc>();
- 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<NonLoc> KnownSize = Size.getAs<NonLoc>()) {
+ 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<TaintBugVisitor>(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);
}
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
