llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT-->
@llvm/pr-subscribers-clang-static-analyzer-1
Author: Donát Nagy (NagyDonat)
<details>
<summary>Changes</summary>
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.
---
Patch is 31.68 KiB, truncated to 20.00 KiB below, full version:
https://github.com/llvm/llvm-project/pull/213957.diff
5 Files Affected:
- (added) clang/include/clang/StaticAnalyzer/Checkers/BoundsChecking.h (+105)
- (modified) clang/lib/StaticAnalyzer/Checkers/ArrayBoundChecker.cpp (+1-294)
- (added) clang/lib/StaticAnalyzer/Checkers/BoundsChecking.cpp (+231)
- (modified) clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt (+1)
- (modified) llvm/utils/gn/secondary/clang/lib/StaticAnalyzer/Checkers/BUILD.gn
(+1)
``````````diff
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..f11...
[truncated]
``````````
</details>
https://github.com/llvm/llvm-project/pull/213957
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
