https://github.com/NagyDonat created
https://github.com/llvm/llvm-project/pull/213957
Building on my recent commit 25d51a8156da0845928e2fc09bb2736507fc5adf this
commit moves the general-purpose bounds checking logic from
ArrayBoundChecker.cpp to the new files BoundsChecking.{cpp,h}.
This new library currently only serves the needs of `security.ArrayBound`, but
it will be gradually expanded, generalized and used to bring other bounds
checking checkers out of alpha stage.
The code is moved without modifications, except for the removal of a TODO note
that asks for moving the code into a separate library.
From 129627687a2c054cbb589fa09104f2d7c81db475 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]>
Date: Tue, 4 Aug 2026 14:48:14 +0200
Subject: [PATCH] [NFC][analyzer] Introduce the BoundsChecking library
Building on my recent commit 25d51a8156da0845928e2fc09bb2736507fc5adf
this commit moves the general-purpose bounds checking logic from
ArrayBoundChecker.cpp to the new files BoundsChecking.{cpp,h}.
This new library currently only serves the needs of
`security.ArrayBound`, but it will be gradually expanded, generalized
and used to bring other bounds checking checkers out of alpha stage.
The code is moved without modifications, except for the removal of a
TODO note that asks for moving the code into a separate library.
---
.../StaticAnalyzer/Checkers/BoundsChecking.h | 105 +++++++
.../Checkers/ArrayBoundChecker.cpp | 295 +-----------------
.../Checkers/BoundsChecking.cpp | 231 ++++++++++++++
.../StaticAnalyzer/Checkers/CMakeLists.txt | 1 +
.../lib/StaticAnalyzer/Checkers/BUILD.gn | 1 +
5 files changed, 339 insertions(+), 294 deletions(-)
create mode 100644 clang/include/clang/StaticAnalyzer/Checkers/BoundsChecking.h
create mode 100644 clang/lib/StaticAnalyzer/Checkers/BoundsChecking.cpp
diff --git a/clang/include/clang/StaticAnalyzer/Checkers/BoundsChecking.h
b/clang/include/clang/StaticAnalyzer/Checkers/BoundsChecking.h
new file mode 100644
index 0000000000000..3e9a639e36cef
--- /dev/null
+++ b/clang/include/clang/StaticAnalyzer/Checkers/BoundsChecking.h
@@ -0,0 +1,105 @@
+//===- BoundsChecking.h - Bounds checking related APIs ----------*- C++
-*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM
Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This header declares 'checkBounds', a function that compares memory offsets
+// (that may be symbolic) and uses heuristical workarounds to provide more
+// accurate results than directly calling evalBinOp or assumeInBound.
+//
+// As of now, this logic only supports the needs of `security.ArrayBound`, but
+// in the future it will be generalized and applied in all checkers that
+// perform bounds checking (to bring them out of `alpha` stage).
+//
+// TODO: This header should be extended by other utilities (e.g. message
+// formatting tools) that are relevant for multiple bounds checking checkers.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_STATICANALYZER_CHECKERS_BOUNDSCHECKING_H
+#define LLVM_CLANG_STATICANALYZER_CHECKERS_BOUNDSCHECKING_H
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include <optional>
+
+namespace clang::ento::bounds {
+
+struct CheckFlags {
+ unsigned CheckUnderflow : 1;
+ unsigned OffsetObviouslyNonnegative : 1;
+ unsigned AcceptPastTheEnd : 1;
+};
+
+class CheckResult;
+
+/// Checks the validity of accessing a memory region with extent \p Extent at
+/// offset \p Offset. The \p Flags influence the semantics of the check, in
+/// particular if `AcceptPastTheEnd` is true, then Offset == Extent is also
+/// accepted as valid.
+CheckResult checkBounds(ProgramStateRef State, SValBuilder &SVB, NonLoc Offset,
+ std::optional<NonLoc> Extent, CheckFlags Flags);
+
+class CheckResult {
+public:
+ /// When true, the bounds check noticed that the value of an unsigned
+ /// expression is constrained to negative values (because the analyzer
+ /// skipped the modeling of a cast expression). This execution path must be
+ /// discarded because it does not represent a real possibility.
+ /// FIXME: This hack is currently needed to filter out many ugly false
+ /// positives; but it should be removed when we fix cast modeling.
+ bool isCorruptedState() const { return IsCorruptedState; }
+
+ /// When true, the checked offset may be in bounds.
+ /// As an exceptional case, this is also true for idiomatic expressions that
+ /// define a past-the-end pointer (and do not dereference it).
+ bool mayBeInBounds() const { return static_cast<bool>(InBoundsState); }
+
+ /// When true, the checked offset may be negative.
+ bool mayUnderflow() const { return MayUnderflow; }
+ /// When true, the checked offset may be >= the extent of the region.
+ /// As an exceptional case, this is also false for idiomatic expressions that
+ /// define a past-the-end pointer (and do not dereference it).
+ bool mayOverflow() const { return ExtentIfMayOverflow.has_value(); }
+ /// When true, the checked offset may be out of bounds.
+ bool mayBeInvalid() const { return MayUnderflow || ExtentIfMayOverflow; }
+
+ /// Returns the offset of the accessed location from the beginning of the
+ /// accessd region.
+ NonLoc getOffset() const { return Offset; }
+
+ /// Returns the extent of the accessed region if it is relevant (because the
+ /// offset may overflow it), otherwise returns std::nullopt.
+ std::optional<NonLoc> getExtentIfMayOverflow() const {
+ return ExtentIfMayOverflow;
+ }
+
+ /// Returns the program state that should be used for continuing the analysis
+ /// after this bounds check. This returns null if mayBeInBounds() is false,
in
+ /// that case the state before the check should be used in the error node.
+ /// Note that we also have a valid state in the exception case when the
+ /// 'access' calculates the past-the-end pointer without dereferencing it.
+ ProgramStateRef getInBoundsState() const { return InBoundsState; }
+
+ friend CheckResult checkBounds(ProgramStateRef State, SValBuilder &SVB,
+ NonLoc Offset, std::optional<NonLoc> Extent,
+ CheckFlags Flags);
+
+private:
+ // Offset of the accessed location, measured from the start of the region.
+ // TODO: As of now, the offset and the extent are always measured in bytes,
+ // but we will probably need to allow other size units in the future.
+ const NonLoc Offset;
+
+ explicit CheckResult(NonLoc Offs) : Offset(Offs) {}
+
+ bool IsCorruptedState = false;
+ bool MayUnderflow = false;
+ std::optional<NonLoc> ExtentIfMayOverflow = std::nullopt;
+ ProgramStateRef InBoundsState = nullptr;
+};
+
+} // namespace clang::ento::bounds
+
+#endif // LLVM_CLANG_STATICANALYZER_CHECKERS_BOUNDSCHECKING_H
diff --git a/clang/lib/StaticAnalyzer/Checkers/ArrayBoundChecker.cpp
b/clang/lib/StaticAnalyzer/Checkers/ArrayBoundChecker.cpp
index 460b1020b0e1b..d8f2e19d41ddc 100644
--- a/clang/lib/StaticAnalyzer/Checkers/ArrayBoundChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/ArrayBoundChecker.cpp
@@ -13,6 +13,7 @@
#include "clang/AST/CharUnits.h"
#include "clang/AST/ParentMapContext.h"
+#include "clang/StaticAnalyzer/Checkers/BoundsChecking.h"
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
#include "clang/StaticAnalyzer/Checkers/Taint.h"
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
@@ -115,87 +116,6 @@ class SizeUnit {
}
};
-} // anonymous namespace
-
-namespace clang::ento::bounds {
-
-struct CheckFlags {
- unsigned CheckUnderflow : 1;
- unsigned OffsetObviouslyNonnegative : 1;
- unsigned AcceptPastTheEnd : 1;
-};
-
-class CheckResult;
-
-/// Checks the validity of accessing a memory region with extent \p Extent at
-/// offset \p Offset. The \p Flags influence the semantics of the check, in
-/// particular if `AcceptPastTheEnd` is true, then Offset == Extent is also
-/// accepted as valid.
-CheckResult checkBounds(ProgramStateRef State, SValBuilder &SVB, NonLoc Offset,
- std::optional<NonLoc> Extent, CheckFlags Flags);
-
-class CheckResult {
-public:
- /// When true, the bounds check noticed that the value of an unsigned
- /// expression is constrained to negative values (because the analyzer
- /// skipped the modeling of a cast expression). This execution path must be
- /// discarded because it does not represent a real possibility.
- /// FIXME: This hack is currently needed to filter out many ugly false
- /// positives; but it should be removed when we fix cast modeling.
- bool isCorruptedState() const { return IsCorruptedState; }
-
- /// When true, the checked offset may be in bounds.
- /// As an exceptional case, this is also true for idiomatic expressions that
- /// define a past-the-end pointer (and do not dereference it).
- bool mayBeInBounds() const { return static_cast<bool>(InBoundsState); }
-
- /// When true, the checked offset may be negative.
- bool mayUnderflow() const { return MayUnderflow; }
- /// When true, the checked offset may be >= the extent of the region.
- /// As an exceptional case, this is also false for idiomatic expressions that
- /// define a past-the-end pointer (and do not dereference it).
- bool mayOverflow() const { return ExtentIfMayOverflow.has_value(); }
- /// When true, the checked offset may be out of bounds.
- bool mayBeInvalid() const { return MayUnderflow || ExtentIfMayOverflow; }
-
- /// Returns the offset of the accessed location from the beginning of the
- /// accessd region.
- NonLoc getOffset() const { return Offset; }
-
- /// Returns the extent of the accessed region if it is relevant (because the
- /// offset may overflow it), otherwise returns std::nullopt.
- std::optional<NonLoc> getExtentIfMayOverflow() const {
- return ExtentIfMayOverflow;
- }
-
- /// Returns the program state that should be used for continuing the analysis
- /// after this bounds check. This returns null if mayBeInBounds() is false,
in
- /// that case the state before the check should be used in the error node.
- /// Note that we also have a valid state in the exception case when the
- /// 'access' calculates the past-the-end pointer without dereferencing it.
- ProgramStateRef getInBoundsState() const { return InBoundsState; }
-
- friend CheckResult checkBounds(ProgramStateRef State, SValBuilder &SVB,
- NonLoc Offset, std::optional<NonLoc> Extent,
- CheckFlags Flags);
-
-private:
- // Offset of the accessed location, measured from the start of the region.
- // TODO: As of now, the offset and the extent are always measured in bytes,
- // but we will probably need to allow other size units in the future.
- const NonLoc Offset;
-
- explicit CheckResult(NonLoc Offs) : Offset(Offs) {}
-
- bool IsCorruptedState = false;
- bool MayUnderflow = false;
- std::optional<NonLoc> ExtentIfMayOverflow = std::nullopt;
- ProgramStateRef InBoundsState = nullptr;
-};
-
-} // namespace clang::ento::bounds
-
-namespace {
/// Strings that will be passed to the parameters 'desc' and 'fullDesc' of the
/// constructor of 'PathSensitiveBugReport'.
struct BugDescription {
@@ -337,124 +257,6 @@ computeOffset(ProgramStateRef State, SValBuilder &SVB,
SVal Location) {
return std::nullopt;
}
-// NOTE: This function is the "heart" of this checker. It simplifies
-// inequalities with transformations that are valid (and very elementary) in
-// pure mathematics, but become invalid if we use them in C++ number model
-// where the calculations may overflow.
-// Due to the overflow issues I think it's impossible (or at least not
-// practical) to integrate this kind of simplification into the resolution of
-// arbitrary inequalities (i.e. the code of `evalBinOp`); but this function
-// produces valid results when the calculations are handling memory offsets
-// and every value is well below SIZE_MAX.
-// TODO: This algorithm should be moved to a central location where it's
-// available for other checkers that need to compare memory offsets.
-// NOTE: the simplification preserves the order of the two operands in a
-// mathematical sense, but it may change the result produced by a C++
-// comparison operator (and the automatic type conversions).
-// For example, consider a comparison "X+1 < 0", where the LHS is stored as a
-// size_t and the RHS is stored in an int. (As size_t is unsigned, this
-// comparison is false for all values of "X".) However, the simplification may
-// turn it into "X < -1", which is still always false in a mathematical sense,
-// but can produce a true result when evaluated by `evalBinOp` (which follows
-// the rules of C++ and casts -1 to SIZE_MAX).
-static std::pair<NonLoc, nonloc::ConcreteInt>
-getSimplifiedOffsets(NonLoc offset, nonloc::ConcreteInt extent,
- SValBuilder &svalBuilder) {
- const llvm::APSInt &extentVal = extent.getValue();
- std::optional<nonloc::SymbolVal> SymVal = offset.getAs<nonloc::SymbolVal>();
- if (SymVal && SymVal->isExpression()) {
- if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SymVal->getSymbol())) {
- llvm::APSInt constant = APSIntType(extentVal).convert(SIE->getRHS());
- switch (SIE->getOpcode()) {
- case BO_Mul:
- // The constant should never be 0 here, becasue multiplication by zero
- // is simplified by the engine.
- if ((extentVal % constant) != 0)
- return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent);
- else
- return getSimplifiedOffsets(
- nonloc::SymbolVal(SIE->getLHS()),
- svalBuilder.makeIntVal(extentVal / constant), svalBuilder);
- case BO_Add:
- return getSimplifiedOffsets(
- nonloc::SymbolVal(SIE->getLHS()),
- svalBuilder.makeIntVal(extentVal - constant), svalBuilder);
- default:
- break;
- }
- }
- }
-
- return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent);
-}
-
-static bool isNegative(SValBuilder &SVB, ProgramStateRef State, NonLoc Value) {
- const llvm::APSInt *MaxV = SVB.getMaxValue(State, Value);
- return MaxV && MaxV->isNegative();
-}
-
-static bool isUnsigned(SValBuilder &SVB, NonLoc Value) {
- QualType T = Value.getType(SVB.getContext());
- return T->isUnsignedIntegerType();
-}
-
-// 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.
-// If the optional argument CheckEquality is true, then use BO_EQ instead of
-// the default BO_LT after consistently applying the same simplification steps.
-static std::pair<ProgramStateRef, ProgramStateRef>
-compareValueToThreshold(ProgramStateRef State, NonLoc Value, NonLoc Threshold,
- SValBuilder &SVB, bool CheckEquality = false) {
- if (auto ConcreteThreshold = Threshold.getAs<nonloc::ConcreteInt>()) {
- std::tie(Value, Threshold) =
- getSimplifiedOffsets(Value, *ConcreteThreshold, SVB);
- }
-
- // We want to perform a _mathematical_ comparison between the numbers `Value`
- // and `Threshold`; but `evalBinOpNN` evaluates a C/C++ operator that may
- // perform automatic conversions. For example the number -1 is less than the
- // number 1000, but -1 < `1000ull` will evaluate to `false` because the `int`
- // -1 is converted to ULONGLONG_MAX.
- // To avoid automatic conversions, we evaluate the "obvious" cases without
- // calling `evalBinOpNN`:
- if (isNegative(SVB, State, Value) && isUnsigned(SVB, Threshold)) {
- if (CheckEquality) {
- // negative_value == unsigned_threshold is always false
- return {nullptr, State};
- }
- // negative_value < unsigned_threshold is always true
- return {State, nullptr};
- }
- if (isUnsigned(SVB, Value) && isNegative(SVB, State, Threshold)) {
- // unsigned_value == negative_threshold and
- // unsigned_value < negative_threshold are both always false
- return {nullptr, State};
- }
- // FIXME: These special cases are sufficient for handling real-world
- // comparisons, but in theory there could be contrived situations where
- // automatic conversion of a symbolic value (which can be negative and can be
- // positive) leads to incorrect results.
- // NOTE: We NEED to use the `evalBinOpNN` call in the "common" case, because
- // we want to ensure that assumptions coming from this precondition and
- // assumptions coming from regular C/C++ operator calls are represented by
- // constraints on the same symbolic expression. A solution that would
- // evaluate these "mathematical" comparisons through a separate pathway would
- // be a step backwards in this sense.
-
- const BinaryOperatorKind OpKind = CheckEquality ? BO_EQ : BO_LT;
- auto BelowThreshold =
- SVB.evalBinOpNN(State, OpKind, Value, Threshold, SVB.getConditionType())
- .getAs<NonLoc>();
-
- if (BelowThreshold)
- return State->assume(*BelowThreshold);
-
- return {nullptr, nullptr};
-}
-
static std::string getRegionName(const MemSpaceRegion *Space,
const SubRegion *Region) {
if (std::string RegName = Region->getDescriptiveName(); !RegName.empty())
@@ -720,101 +522,6 @@ void ArrayBoundChecker::handleAccessExpr(const Expr *E,
C.addTransition(Res.getInBoundsState(), T);
}
-bounds::CheckResult bounds::checkBounds(ProgramStateRef State, SValBuilder
&SVB,
- NonLoc Offset,
- std::optional<NonLoc> Extent,
- bounds::CheckFlags Flags) {
-
- bounds::CheckResult Res(Offset);
-
- // CHECK LOWER BOUND
- if (Flags.CheckUnderflow) {
- auto [PrecedesLowerBound, WithinLowerBound] =
- compareValueToThreshold(State, Offset, SVB.makeZeroArrayIndex(), SVB);
-
- if (PrecedesLowerBound) {
- // The analyzer thinks that the offset may be invalid (negative)...
- if (Flags.OffsetObviouslyNonnegative) {
- // ...but the offset is obviously non-negative (clear array subscript
- // with an unsigned index), so we're in a buggy situation.
-
- // TODO: Currently the analyzer ignores many casts (e.g. signed ->
- // unsigned casts), so it can easily reach states where it will load a
- // signed (and negative) value from an unsigned variable. This sanity
- // check is a duct tape "solution" that silences most of the ugly false
- // positives that are caused by this buggy behavior. Note that this is
- // not a complete solution: this cannot silence reports where pointer
- // arithmetic complicates the picture and cannot ensure modeling of the
- // "unsigned index is positive with highest bit set" cases which are
- // "usurped" by the nonsense "unsigned index is negative" case.
- // For more information about this topic, see the umbrella ticket
- // https://github.com/llvm/llvm-project/issues/39492
- // TODO: Remove this hack once 'SymbolCast's are modeled properly.
-
- if (!WithinLowerBound) {
- // The state is completely nonsense -- let's just sink it!
- Res.IsCorruptedState = true;
- return Res;
- }
- // Otherwise continue on the 'WithinLowerBound' branch where the
- // unsigned index _is_ non-negative. Don't mention this assumption as a
- // note tag, because it would just confuse the users!
- } else {
- Res.MayUnderflow = true;
-
- if (!WithinLowerBound) {
- // ...and it cannot be valid (>= 0), so report an error.
- return Res;
- }
- }
- }
-
- // Actually update the state. The "if" only fails in the extremely unlikely
- // case when compareValueToThreshold returns {nullptr, nullptr} because
- // evalBinOpNN fails to evaluate the less-than operator.
- if (WithinLowerBound)
- State = WithinLowerBound;
- }
-
- // CHECK UPPER BOUND
- if (Extent) {
- // In a situation where both underflow and overflow are possible (but the
- // index is either tainted or known to be invalid), the logic of this
- // checker will first assume that the offset is non-negative, and then
- // (with this additional assumption) it will detect an overflow error.
- // In this situation the warning message should mention both possibilities.
-
- auto [WithinUpperBound, ExceedsUpperBound] =
- compareValueToThreshold(State, Offset, *Extent, SVB);
-
- if (ExceedsUpperBound) {
- // The offset may be invalid (>= Size)...
- Res.ExtentIfMayOverflow = Extent;
-
- if (!WithinUpperBound) {
- // ...and it cannot be within bounds, so report an error, unless we can
- // definitely determine that this is an idiomatic `&array[size]`
- // expression that calculates the past-the-end pointer.
- if (Flags.AcceptPastTheEnd) {
- auto [EqualsToThreshold, NotEqualToThreshold] =
- compareValueToThreshold(State, Offset, *Extent, SVB,
- /*CheckEquality=*/true);
- if (EqualsToThreshold && !NotEqualToThreshold) {
- Res.ExtentIfMayOverflow = std::nullopt;
- Res.InBoundsState = EqualsToThreshold;
- }
- }
- return Res;
- }
- }
- if (WithinUpperBound)
- State = WithinUpperBound;
- }
-
- Res.InBoundsState = State;
- return Res;
-}
-
void ArrayBoundChecker::markPartsInteresting(PathSensitiveBugReport &BR,
ProgramStateRef ErrorState,
NonLoc Val, bool MarkTaint) {
diff --git a/clang/lib/StaticAnalyzer/Checkers/BoundsChecking.cpp
b/clang/lib/StaticAnalyzer/Checkers/BoundsChecking.cpp
new file mode 100644
index 0000000000000..f114da2313819
--- /dev/null
+++ b/clang/lib/StaticAnalyzer/Checkers/BoundsChecking.cpp
@@ -0,0 +1,231 @@
+//===- BoundsChecking.cpp - Bounds checking related APIs --------*- C++
-*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM
Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements 'checkBounds', a function that compares memory offsets
+// (that may be symbolic) and uses heuristical workarounds to provide more
+// accurate results than the 'naive' evalBinOp calls.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/StaticAnalyzer/Checkers/BoundsChecking.h"
+#include "clang/StaticAnalyzer/Checkers/Taint.h"
+
+using namespace clang;
+using namespace ento;
+using namespace bounds;
+
+// NOTE: This function is the "heart" of this algorithm. It simplifies
+// inequalities with transformations that are valid (and very elementary) in
+// pure mathematics, but become invalid if we use them in C++ number model
+// where the calculations may overflow.
+// Due to the overflow issues I think it's impossible (or at least not
+// practical) to integrate this kind of simplification into the resolution of
+// arbitrary inequalities (i.e. the code of `evalBinOp`); but this function
+// produces valid results when the calculations are handling memory offsets
+// and every value is well below SIZE_MAX.
+// NOTE: the simplification preserves the order of the two operands in a
+// mathematical sense, but it may change the result produced by a C++
+// comparison operator (and the automatic type conversions).
+// For example, consider a comparison "X+1 < 0", where the LHS is stored as a
+// size_t and the RHS is stored in an int. (As size_t is unsigned, this
+// comparison is false for all values of "X".) However, the simplification may
+// turn it into "X < -1", which is still always false in a mathematical sense,
+// but can produce a true result when evaluated by `evalBinOp` (which follows
+// the rules of C++ and casts -1 to SIZE_MAX).
+static std::pair<NonLoc, nonloc::ConcreteInt>
+getSimplifiedOffsets(NonLoc offset, nonloc::ConcreteInt extent,
+ SValBuilder &svalBuilder) {
+ const llvm::APSInt &extentVal = extent.getValue();
+ std::optional<nonloc::SymbolVal> SymVal = offset.getAs<nonloc::SymbolVal>();
+ if (SymVal && SymVal->isExpression()) {
+ if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SymVal->getSymbol())) {
+ llvm::APSInt constant = APSIntType(extentVal).convert(SIE->getRHS());
+ switch (SIE->getOpcode()) {
+ case BO_Mul:
+ // The constant should never be 0 here, becasue multiplication by zero
+ // is simplified by the engine.
+ if ((extentVal % constant) != 0)
+ return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent);
+ else
+ return getSimplifiedOffsets(
+ nonloc::SymbolVal(SIE->getLHS()),
+ svalBuilder.makeIntVal(extentVal / constant), svalBuilder);
+ case BO_Add:
+ return getSimplifiedOffsets(
+ nonloc::SymbolVal(SIE->getLHS()),
+ svalBuilder.makeIntVal(extentVal - constant), svalBuilder);
+ default:
+ break;
+ }
+ }
+ }
+
+ return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent);
+}
+
+static bool isNegative(SValBuilder &SVB, ProgramStateRef State, NonLoc Value) {
+ const llvm::APSInt *MaxV = SVB.getMaxValue(State, Value);
+ return MaxV && MaxV->isNegative();
+}
+
+static bool isUnsigned(SValBuilder &SVB, NonLoc Value) {
+ QualType T = Value.getType(SVB.getContext());
+ return T->isUnsignedIntegerType();
+}
+
+// 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.
+// If the optional argument CheckEquality is true, then use BO_EQ instead of
+// the default BO_LT after consistently applying the same simplification steps.
+static std::pair<ProgramStateRef, ProgramStateRef>
+compareValueToThreshold(ProgramStateRef State, NonLoc Value, NonLoc Threshold,
+ SValBuilder &SVB, bool CheckEquality = false) {
+ if (auto ConcreteThreshold = Threshold.getAs<nonloc::ConcreteInt>()) {
+ std::tie(Value, Threshold) =
+ getSimplifiedOffsets(Value, *ConcreteThreshold, SVB);
+ }
+
+ // We want to perform a _mathematical_ comparison between the numbers `Value`
+ // and `Threshold`; but `evalBinOpNN` evaluates a C/C++ operator that may
+ // perform automatic conversions. For example the number -1 is less than the
+ // number 1000, but -1 < `1000ull` will evaluate to `false` because the `int`
+ // -1 is converted to ULONGLONG_MAX.
+ // To avoid automatic conversions, we evaluate the "obvious" cases without
+ // calling `evalBinOpNN`:
+ if (isNegative(SVB, State, Value) && isUnsigned(SVB, Threshold)) {
+ if (CheckEquality) {
+ // negative_value == unsigned_threshold is always false
+ return {nullptr, State};
+ }
+ // negative_value < unsigned_threshold is always true
+ return {State, nullptr};
+ }
+ if (isUnsigned(SVB, Value) && isNegative(SVB, State, Threshold)) {
+ // unsigned_value == negative_threshold and
+ // unsigned_value < negative_threshold are both always false
+ return {nullptr, State};
+ }
+ // FIXME: These special cases are sufficient for handling real-world
+ // comparisons, but in theory there could be contrived situations where
+ // automatic conversion of a symbolic value (which can be negative and can be
+ // positive) leads to incorrect results.
+ // NOTE: We NEED to use the `evalBinOpNN` call in the "common" case, because
+ // we want to ensure that assumptions coming from this precondition and
+ // assumptions coming from regular C/C++ operator calls are represented by
+ // constraints on the same symbolic expression. A solution that would
+ // evaluate these "mathematical" comparisons through a separate pathway would
+ // be a step backwards in this sense.
+
+ const BinaryOperatorKind OpKind = CheckEquality ? BO_EQ : BO_LT;
+ auto BelowThreshold =
+ SVB.evalBinOpNN(State, OpKind, Value, Threshold, SVB.getConditionType())
+ .getAs<NonLoc>();
+
+ if (BelowThreshold)
+ return State->assume(*BelowThreshold);
+
+ return {nullptr, nullptr};
+}
+
+bounds::CheckResult bounds::checkBounds(ProgramStateRef State, SValBuilder
&SVB,
+ NonLoc Offset,
+ std::optional<NonLoc> Extent,
+ bounds::CheckFlags Flags) {
+
+ bounds::CheckResult Res(Offset);
+
+ // CHECK LOWER BOUND
+ if (Flags.CheckUnderflow) {
+ auto [PrecedesLowerBound, WithinLowerBound] =
+ compareValueToThreshold(State, Offset, SVB.makeZeroArrayIndex(), SVB);
+
+ if (PrecedesLowerBound) {
+ // The analyzer thinks that the offset may be invalid (negative)...
+ if (Flags.OffsetObviouslyNonnegative) {
+ // ...but the offset is obviously non-negative (clear array subscript
+ // with an unsigned index), so we're in a buggy situation.
+
+ // TODO: Currently the analyzer ignores many casts (e.g. signed ->
+ // unsigned casts), so it can easily reach states where it will load a
+ // signed (and negative) value from an unsigned variable. This sanity
+ // check is a duct tape "solution" that silences most of the ugly false
+ // positives that are caused by this buggy behavior. Note that this is
+ // not a complete solution: this cannot silence reports where pointer
+ // arithmetic complicates the picture and cannot ensure modeling of the
+ // "unsigned index is positive with highest bit set" cases which are
+ // "usurped" by the nonsense "unsigned index is negative" case.
+ // For more information about this topic, see the umbrella ticket
+ // https://github.com/llvm/llvm-project/issues/39492
+ // TODO: Remove this hack once 'SymbolCast's are modeled properly.
+
+ if (!WithinLowerBound) {
+ // The state is completely nonsense -- let's just sink it!
+ Res.IsCorruptedState = true;
+ return Res;
+ }
+ // Otherwise continue on the 'WithinLowerBound' branch where the
+ // unsigned index _is_ non-negative. Don't mention this assumption as a
+ // note tag, because it would just confuse the users!
+ } else {
+ Res.MayUnderflow = true;
+
+ if (!WithinLowerBound) {
+ // ...and it cannot be valid (>= 0), so report an error.
+ return Res;
+ }
+ }
+ }
+
+ // Actually update the state. The "if" only fails in the extremely unlikely
+ // case when compareValueToThreshold returns {nullptr, nullptr} because
+ // evalBinOpNN fails to evaluate the less-than operator.
+ if (WithinLowerBound)
+ State = WithinLowerBound;
+ }
+
+ // CHECK UPPER BOUND
+ if (Extent) {
+ // In a situation where both underflow and overflow are possible (but the
+ // index is either tainted or known to be invalid), the logic of this
+ // checker will first assume that the offset is non-negative, and then
+ // (with this additional assumption) it will detect an overflow error.
+ // In this situation the warning message should mention both possibilities.
+
+ auto [WithinUpperBound, ExceedsUpperBound] =
+ compareValueToThreshold(State, Offset, *Extent, SVB);
+
+ if (ExceedsUpperBound) {
+ // The offset may be invalid (>= Size)...
+ Res.ExtentIfMayOverflow = Extent;
+
+ if (!WithinUpperBound) {
+ // ...and it cannot be within bounds, so report an error, unless we can
+ // definitely determine that this is an idiomatic `&array[size]`
+ // expression that calculates the past-the-end pointer.
+ if (Flags.AcceptPastTheEnd) {
+ auto [EqualsToThreshold, NotEqualToThreshold] =
+ compareValueToThreshold(State, Offset, *Extent, SVB,
+ /*CheckEquality=*/true);
+ if (EqualsToThreshold && !NotEqualToThreshold) {
+ Res.ExtentIfMayOverflow = std::nullopt;
+ Res.InBoundsState = EqualsToThreshold;
+ }
+ }
+ return Res;
+ }
+ }
+ if (WithinUpperBound)
+ State = WithinUpperBound;
+ }
+
+ Res.InBoundsState = State;
+ return Res;
+}
diff --git a/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt
b/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt
index dca37257d8ffa..f136bd5434113 100644
--- a/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt
+++ b/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt
@@ -13,6 +13,7 @@ add_clang_library(clangStaticAnalyzerCheckers
BitwiseShiftChecker.cpp
BlockInCriticalSectionChecker.cpp
BoolAssignmentChecker.cpp
+ BoundsChecking.cpp
BuiltinFunctionChecker.cpp
CStringChecker.cpp
CStringSyntaxChecker.cpp
diff --git a/llvm/utils/gn/secondary/clang/lib/StaticAnalyzer/Checkers/BUILD.gn
b/llvm/utils/gn/secondary/clang/lib/StaticAnalyzer/Checkers/BUILD.gn
index f4b40a96f5c89..f048acd18d904 100644
--- a/llvm/utils/gn/secondary/clang/lib/StaticAnalyzer/Checkers/BUILD.gn
+++ b/llvm/utils/gn/secondary/clang/lib/StaticAnalyzer/Checkers/BUILD.gn
@@ -22,6 +22,7 @@ static_library("Checkers") {
"BitwiseShiftChecker.cpp",
"BlockInCriticalSectionChecker.cpp",
"BoolAssignmentChecker.cpp",
+ "BoundsChecking.cpp",
"BuiltinFunctionChecker.cpp",
"CStringChecker.cpp",
"CStringSyntaxChecker.cpp",
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
