donat.nagy created this revision.
donat.nagy added reviewers: steakhal, NoQ, gamesh411, Szelethus.
donat.nagy added a project: clang-tools-extra.
Herald added subscribers: manas, ASDenysPetrov, martong, dkrupp,
mikhail.ramalho, a.sidorin, szepet, baloghadamsoftware, xazax.hun.
Herald added a project: All.
donat.nagy requested review of this revision.
Herald added a project: clang.
Herald added a subscriber: cfe-commits.
This simple commit introduces a separate code path for a certain situation that
was handled incorrectly by the prototype checker alpha.security.ArrayBoundV2.
This issue was already known and marked by a "FIXME" testcase which is now
adapted to except the correct behavior.
Note that although the visible symptom of this issue was an overflow error, the
actual problem was in the underflow handler logic:
(0) The testcase introduces with a five-element array "char a[5]" and an
unknown argument "size_t len"; then evaluates "a[len+1]".
(1) The underflow check tries to determine whether "len+1 < 0" holds.
(2) This inequality is rearranged to "len < -1".
(3) evalBinOpNN() evaluates this with the schematics of C/C++ and converts -1
to the size_t value SIZE_MAX.
(4) The engine concludes that len == SIZE_MAX, because otherwise we'd have an
underflow here.
(5) The overflow check tries to determine whether "len+1 >= 5".
(6) This inequality is rearranged to "len >= 4".
(7) The engine substitutes len == SIZE_MAX and reports that we have an overflow.
Repository:
rG LLVM Github Monorepo
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
@@ -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<NonLoc, nonloc::ConcreteInt>
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<NonLoc> NV = extentBegin.getAs<NonLoc>()) {
+ bool TriviallySatisfied = false;
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());
+ if (auto ConcreteNV = NV->getAs<nonloc::ConcreteInt>()) {
+ 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<NonLoc> lowerBoundToCheck = lowerBound.getAs<NonLoc>();
+ if (!lowerBoundToCheck)
+ return;
- std::optional<NonLoc> lowerBoundToCheck = lowerBound.getAs<NonLoc>();
- 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<NonLoc>(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) {
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
