llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang Author: None (forall-x) <details> <summary>Changes</summary> This patch addresses a stack overflow in the Clang Static Analyzer when running clang-analyzer-* checks on template-heavy code (e.g., android::ftl::Concat). The fix introduces a GlobalRecursionDepth guard to limit recursion in ProgramState::bindLoc, ExprEngine::processPointerEscapedOnBind, and RegionStoreManager::bind*. It also adds robustness fixes to RegionStoreManager to avoid unsafe casts and properly handle recursion limits. Verified with a new regression test in clang/test/Analysis/ftl-concat-crash.cpp. --- Patch is 20.22 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/184767.diff 5 Files Affected: - (modified) clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h (+2) - (modified) clang/lib/StaticAnalyzer/Core/ExprEngine.cpp (+7) - (modified) clang/lib/StaticAnalyzer/Core/ProgramState.cpp (+3-1) - (modified) clang/lib/StaticAnalyzer/Core/RegionStore.cpp (+147-39) - (added) clang/test/Analysis/ftl-concat-crash.cpp (+63) ``````````diff diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h index d3dd6ca124b7f..8909b5d9e205b 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h @@ -909,6 +909,8 @@ class ScanReachableSymbols { bool scan(const SymExpr *sym); }; +extern thread_local unsigned GlobalRecursionDepth; + } // end ento namespace } // end clang namespace diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 644d57cc6b0d0..fd603cd2e3b8a 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -3624,6 +3624,13 @@ ProgramStateRef ExprEngine::processPointerEscapedOnBind( ProgramStateRef State, ArrayRef<std::pair<SVal, SVal>> LocAndVals, const LocationContext *LCtx, PointerEscapeKind Kind, const CallEvent *Call) { + struct DepthGuard { + DepthGuard() { ++GlobalRecursionDepth; } + ~DepthGuard() { --GlobalRecursionDepth; } + } guard; + if (GlobalRecursionDepth > 1000) { + return State; + } SmallVector<SVal, 8> Escaped; for (const std::pair<SVal, SVal> &LocAndVal : LocAndVals) { // Cases (1) and (2). diff --git a/clang/lib/StaticAnalyzer/Core/ProgramState.cpp b/clang/lib/StaticAnalyzer/Core/ProgramState.cpp index 87485daa6e5c9..9f3c99685e6b7 100644 --- a/clang/lib/StaticAnalyzer/Core/ProgramState.cpp +++ b/clang/lib/StaticAnalyzer/Core/ProgramState.cpp @@ -23,7 +23,9 @@ using namespace clang; using namespace ento; -namespace clang { namespace ento { +namespace clang { namespace ento { + +thread_local unsigned GlobalRecursionDepth = 0; /// Increments the number of times this state is referenced. void ProgramStateRetain(const ProgramState *state) { diff --git a/clang/lib/StaticAnalyzer/Core/RegionStore.cpp b/clang/lib/StaticAnalyzer/Core/RegionStore.cpp index 6ec66298e8c45..08e2955e643d8 100644 --- a/clang/lib/StaticAnalyzer/Core/RegionStore.cpp +++ b/clang/lib/StaticAnalyzer/Core/RegionStore.cpp @@ -40,16 +40,14 @@ using namespace ento; // Representation of binding keys. //===----------------------------------------------------------------------===// + namespace { class BindingKey { public: - enum Kind { - Default = 0x0, - Direct = 0x1, - Symbolic = 0x2, - }; - + enum Kind { Default = 0x0, Direct = 0x1 }; private: + enum { Symbolic = 0x2 }; + llvm::PointerIntPair<const MemRegion *, 2> P; uint64_t Data; @@ -334,15 +332,28 @@ class LimitedRegionBindingsRef : public RegionBindingsRef { public: LimitedRegionBindingsRef(RegionBindingsRef Base, SmallVectorImpl<SVal> &EscapedValuesDuringBind, - std::optional<unsigned> BindingsLeft) + std::optional<unsigned> BindingsLeft, + unsigned RecursionLeft = 1000) : RegionBindingsRef(Base), + RecursionLeft(RecursionLeft), EscapedValuesDuringBind(&EscapedValuesDuringBind), - BindingsLeft(BindingsLeft) {} + BindingsLeft(BindingsLeft) { + } bool hasExhaustedBindingLimit() const { return BindingsLeft.has_value() && BindingsLeft.value() == 0; } + bool hasExhaustedRecursionLimit() const { + return RecursionLeft == 0; + } + + LimitedRegionBindingsRef withRecursionDecreased() const { + return LimitedRegionBindingsRef{ + *this, *EscapedValuesDuringBind, BindingsLeft, + RecursionLeft > 0 ? RecursionLeft - 1 : 0}; + } + LimitedRegionBindingsRef withValuesEscaped(SVal V) const { EscapedValuesDuringBind->push_back(V); return *this; @@ -361,13 +372,14 @@ class LimitedRegionBindingsRef : public RegionBindingsRef { data_type_ref BindingKeyAndValue) const { return LimitedRegionBindingsRef{RegionBindingsRef::commitBindingsToCluster( BaseRegion, BindingKeyAndValue), - *EscapedValuesDuringBind, BindingsLeft}; + *EscapedValuesDuringBind, BindingsLeft, + RecursionLeft}; } LimitedRegionBindingsRef removeCluster(const MemRegion *BaseRegion) const { return LimitedRegionBindingsRef{ RegionBindingsRef::removeCluster(BaseRegion), *EscapedValuesDuringBind, - BindingsLeft}; + BindingsLeft, RecursionLeft}; } LimitedRegionBindingsRef addBinding(BindingKey K, SVal V) const { @@ -386,7 +398,8 @@ class LimitedRegionBindingsRef : public RegionBindingsRef { } return LimitedRegionBindingsRef{RegionBindingsRef::addBinding(K, V), - *EscapedValuesDuringBind, NewBindingsLeft}; + *EscapedValuesDuringBind, NewBindingsLeft, + RecursionLeft}; } LimitedRegionBindingsRef addBinding(const MemRegion *R, BindingKey::Kind k, @@ -394,6 +407,7 @@ class LimitedRegionBindingsRef : public RegionBindingsRef { return addBinding(BindingKey::Make(R, k), V); } + unsigned RecursionLeft; private: SmallVectorImpl<SVal> *EscapedValuesDuringBind; // nonnull std::optional<unsigned> BindingsLeft; @@ -515,7 +529,7 @@ class RegionStoreManager : public StoreManager { ArrayRef<SVal> Values, InvalidatedRegions *TopLevelRegions); - const AnalyzerOptions &getOptions() { + const AnalyzerOptions &getOptions() const { return StateMgr.getOwningEngine().getAnalysisManager().options; } @@ -714,6 +728,11 @@ class RegionStoreManager : public StoreManager { return getBinding(getRegionBindings(S), L, T); } + std::optional<SVal> getUniqueDefaultBinding(RegionBindingsConstRef B, + const TypedValueRegion *R) const; + std::optional<SVal> + getUniqueDefaultBinding(nonloc::LazyCompoundVal LCV) const; + std::optional<SVal> getDefaultBinding(Store S, const MemRegion *R) override { RegionBindingsRef B = getRegionBindings(S); // Default bindings are always applied over a base region so look up the @@ -806,7 +825,8 @@ class RegionStoreManager : public StoreManager { SmallVectorImpl<SVal> &EscapedValuesDuringBind) const { return LimitedRegionBindingsRef( getRegionBindings(store), EscapedValuesDuringBind, - /*BindingsLeft=*/RegionStoreMaxBindingFanOutPlusOne); + /*BindingsLeft=*/RegionStoreMaxBindingFanOutPlusOne, + /*RecursionLeft=*/1000); } void printJson(raw_ostream &Out, Store S, const char *NL = "\n", @@ -2451,8 +2471,7 @@ NonLoc RegionStoreManager::createLazyBinding(RegionBindingsConstRef B, SVal RegionStoreManager::getBindingForStruct(RegionBindingsConstRef B, const TypedValueRegion *R) { - const RecordDecl *RD = - R->getValueType()->castAsCanonical<RecordType>()->getDecl(); + const RecordDecl *RD = R->getValueType()->castAs<RecordType>()->getDecl(); if (!RD->getDefinition()) return UnknownVal(); @@ -2460,6 +2479,11 @@ SVal RegionStoreManager::getBindingForStruct(RegionBindingsConstRef B, // behavior doesn't depend on the struct layout. // This way even an empty struct can carry taint, no matter if creduce drops // the last field member or not. + + // Try to avoid creating a LCV if it would anyways just refer to a single + // default binding. + if (std::optional<SVal> Val = getUniqueDefaultBinding(B, R)) + return *Val; return createLazyBinding(B, R); } @@ -2513,10 +2537,18 @@ StoreRef RegionStoreManager::killBinding(Store ST, Loc L) { LimitedRegionBindingsRef RegionStoreManager::bind(LimitedRegionBindingsConstRef B, Loc L, SVal V) { + + struct DepthGuard { + DepthGuard() { ++GlobalRecursionDepth; } + ~DepthGuard() { --GlobalRecursionDepth; } + } guard; + if (GlobalRecursionDepth > 1000) { + return B.withValuesEscaped(V); + } llvm::TimeTraceScope TimeScope("RegionStoreManager::bind", [&L]() { return locDescr(L); }); - if (B.hasExhaustedBindingLimit()) + if (B.hasExhaustedBindingLimit() || B.hasExhaustedRecursionLimit()) return B.withValuesEscaped(V); // We only care about region locations. @@ -2539,13 +2571,13 @@ RegionStoreManager::bind(LimitedRegionBindingsConstRef B, Loc L, SVal V) { if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) { QualType Ty = TR->getValueType(); if (Ty->isArrayType()) - return bindArray(B, TR, V); + return bindArray(B.withRecursionDecreased(), TR, V); if (Ty->isStructureOrClassType()) - return bindStruct(B, TR, V); + return bindStruct(B.withRecursionDecreased(), TR, V); if (Ty->isVectorType()) - return bindVector(B, TR, V); + return bindVector(B.withRecursionDecreased(), TR, V); if (Ty->isUnionType()) - return bindAggregate(B, TR, V); + return bindAggregate(B.withRecursionDecreased(), TR, V); } assert((!isa<CXXThisRegion>(R) || !B.lookup(R)) && @@ -2619,6 +2651,8 @@ std::optional<LimitedRegionBindingsRef> RegionStoreManager::tryBindSmallArray( return std::nullopt; LimitedRegionBindingsRef NewB = B; + // llvm::errs() << "bindArray: RecursionLeft=" << B.RecursionLeft << "\n"; + llvm::errs() << "bindArray: RecursionLeft=" << B.RecursionLeft << "\n"; for (uint64_t i = 0; i < ArrSize; ++i) { auto Idx = svalBuilder.makeArrayIndex(i); @@ -2636,11 +2670,21 @@ std::optional<LimitedRegionBindingsRef> RegionStoreManager::tryBindSmallArray( LimitedRegionBindingsRef RegionStoreManager::bindArray(LimitedRegionBindingsConstRef B, const TypedValueRegion *R, SVal Init) { + + struct DepthGuard { + DepthGuard() { ++GlobalRecursionDepth; } + ~DepthGuard() { --GlobalRecursionDepth; } + } guard; + if (GlobalRecursionDepth > 1000) { + return B.withValuesEscaped(Init); + } llvm::TimeTraceScope TimeScope("RegionStoreManager::bindArray", [R]() { return R->getDescriptiveName(); }); - if (B.hasExhaustedBindingLimit()) + if (B.hasExhaustedBindingLimit() || B.hasExhaustedRecursionLimit()) return B.withValuesEscaped(Init); + LimitedRegionBindingsRef BDecreased = B.withRecursionDecreased(); + const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType())); QualType ElementTy = AT->getElementType(); std::optional<uint64_t> Size; @@ -2688,11 +2732,11 @@ RegionStoreManager::bindArray(LimitedRegionBindingsConstRef B, const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx); if (ElementTy->isStructureOrClassType()) - NewB = bindStruct(NewB, ER, *VI); + NewB = bindStruct(NewB.withRecursionDecreased(), ER, *VI); else if (ElementTy->isArrayType()) - NewB = bindArray(NewB, ER, *VI); + NewB = bindArray(NewB.withRecursionDecreased(), ER, *VI); else - NewB = bind(NewB, loc::MemRegionVal(ER), *VI); + NewB = bind(NewB.withRecursionDecreased(), loc::MemRegionVal(ER), *VI); } // If the init list is shorter than the array length (or the array has @@ -2707,9 +2751,17 @@ RegionStoreManager::bindArray(LimitedRegionBindingsConstRef B, LimitedRegionBindingsRef RegionStoreManager::bindVector(LimitedRegionBindingsConstRef B, const TypedValueRegion *R, SVal V) { + + struct DepthGuard { + DepthGuard() { ++GlobalRecursionDepth; } + ~DepthGuard() { --GlobalRecursionDepth; } + } guard; + if (GlobalRecursionDepth > 1000) { + return B.withValuesEscaped(V); + } llvm::TimeTraceScope TimeScope("RegionStoreManager::bindVector", [R]() { return R->getDescriptiveName(); }); - if (B.hasExhaustedBindingLimit()) + if (B.hasExhaustedBindingLimit() || B.hasExhaustedRecursionLimit()) return B.withValuesEscaped(V); QualType T = R->getValueType(); @@ -2717,13 +2769,13 @@ RegionStoreManager::bindVector(LimitedRegionBindingsConstRef B, // Handle lazy compound values and symbolic values. if (isa<nonloc::LazyCompoundVal, nonloc::SymbolVal>(V)) - return bindAggregate(B, R, V); + return bindAggregate(B.withRecursionDecreased(), R, V); // We may get non-CompoundVal accidentally due to imprecise cast logic or // that we are binding symbolic struct value. Kill the field values, and if // the value is symbolic go and bind it as a "default" binding. if (!isa<nonloc::CompoundVal>(V)) { - return bindAggregate(B, R, UnknownVal()); + return bindAggregate(B.withRecursionDecreased(), R, UnknownVal()); } QualType ElemType = VT->getElementType(); @@ -2743,21 +2795,59 @@ RegionStoreManager::bindVector(LimitedRegionBindingsConstRef B, const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx); if (ElemType->isArrayType()) - NewB = bindArray(NewB, ER, *VI); + NewB = bindArray(NewB.withRecursionDecreased(), ER, *VI); else if (ElemType->isStructureOrClassType()) - NewB = bindStruct(NewB, ER, *VI); + NewB = bindStruct(NewB.withRecursionDecreased(), ER, *VI); else - NewB = bind(NewB, loc::MemRegionVal(ER), *VI); + NewB = bind(NewB.withRecursionDecreased(), loc::MemRegionVal(ER), *VI); } return NewB; } +std::optional<SVal> +RegionStoreManager::getUniqueDefaultBinding(RegionBindingsConstRef B, + const TypedValueRegion *R) const { + if (R != R->getBaseRegion()) + return std::nullopt; + + const auto *Cluster = B.lookup(R); + if (!Cluster || !llvm::hasSingleElement(*Cluster)) + return std::nullopt; + + const auto [Key, Value] = *Cluster->begin(); + return Key.isDirect() ? std::optional<SVal>{} : Value; +} + +std::optional<SVal> +RegionStoreManager::getUniqueDefaultBinding(nonloc::LazyCompoundVal LCV) const { + auto B = getRegionBindings(LCV.getStore()); + return getUniqueDefaultBinding(B, LCV.getRegion()); +} + std::optional<LimitedRegionBindingsRef> RegionStoreManager::tryBindSmallStruct( LimitedRegionBindingsConstRef B, const TypedValueRegion *R, const RecordDecl *RD, nonloc::LazyCompoundVal LCV) { if (B.hasExhaustedBindingLimit()) return B.withValuesEscaped(LCV); + // If we try to copy a Conjured value representing the value of the whole + // struct, don't try to element-wise copy each field. + // That would unnecessarily bind Derived symbols slicing off the subregion for + // the field from the whole Conjured symbol. + // + // struct Window { int width; int height; }; + // Window getWindow(); <-- opaque fn. + // Window w = getWindow(); <-- conjures a new Window. + // Window w2 = w; <-- trivial copy "w", calling "tryBindSmallStruct" + // + // We should not end up with a new Store for "w2" like this: + // Direct [ 0..31]: Derived{Conj{}, w.width} + // Direct [32..63]: Derived{Conj{}, w.height} + // Instead, we should just bind that Conjured value instead. + if (std::optional<SVal> Val = getUniqueDefaultBinding(LCV)) { + return B.addBinding(BindingKey::Make(R, BindingKey::Default), Val.value()); + } + FieldVector Fields; if (const CXXRecordDecl *Class = dyn_cast<CXXRecordDecl>(RD)) @@ -2802,15 +2892,25 @@ std::optional<LimitedRegionBindingsRef> RegionStoreManager::tryBindSmallStruct( LimitedRegionBindingsRef RegionStoreManager::bindStruct(LimitedRegionBindingsConstRef B, const TypedValueRegion *R, SVal V) { + + struct DepthGuard { + DepthGuard() { ++GlobalRecursionDepth; } + ~DepthGuard() { --GlobalRecursionDepth; } + } guard; + if (GlobalRecursionDepth > 1000) { + return B.withValuesEscaped(V); + } llvm::TimeTraceScope TimeScope("RegionStoreManager::bindStruct", [R]() { return R->getDescriptiveName(); }); - if (B.hasExhaustedBindingLimit()) + if (B.hasExhaustedBindingLimit() || B.hasExhaustedRecursionLimit()) return B.withValuesEscaped(V); QualType T = R->getValueType(); assert(T->isStructureOrClassType()); - const auto *RD = T->castAsRecordDecl(); + const RecordType* RT = T->castAs<RecordType>(); + const RecordDecl *RD = RT->getDecl(); + if (!RD->isCompleteDefinition()) return B; @@ -2819,16 +2919,16 @@ RegionStoreManager::bindStruct(LimitedRegionBindingsConstRef B, V.getAs<nonloc::LazyCompoundVal>()) { if (std::optional NewB = tryBindSmallStruct(B, R, RD, *LCV)) return *NewB; - return bindAggregate(B, R, V); + return bindAggregate(B.withRecursionDecreased(), R, V); } if (isa<nonloc::SymbolVal>(V)) - return bindAggregate(B, R, V); + return bindAggregate(B.withRecursionDecreased(), R, V); // We may get non-CompoundVal accidentally due to imprecise cast logic or // that we are binding symbolic struct value. Kill the field values, and if // the value is symbolic go and bind it as a "default" binding. if (V.isUnknown() || !isa<nonloc::CompoundVal>(V)) - return bindAggregate(B, R, UnknownVal()); + return bindAggregate(B.withRecursionDecreased(), R, UnknownVal()); // The raw CompoundVal is essentially a symbolic InitListExpr: an (immutable) // list of other values. It appears pretty much only when there's an actual @@ -2882,7 +2982,7 @@ RegionStoreManager::bindStruct(LimitedRegionBindingsConstRef B, const CXXBaseObjectRegion *BR = MRMgr.getCXXBaseObjectRegion(BRD, R, /*IsVirtual=*/false); - NewB = bindStruct(NewB, BR, *VI); + NewB = bindStruct(NewB.withRecursionDecreased(), BR, *VI); ++VI; } @@ -2906,9 +3006,9 @@ RegionStoreManager::bindStruct(LimitedRegionBindingsConstRef B, const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R); if (FTy->isArrayType()) - NewB = bindArray(NewB, FR, *VI); + NewB = bindArray(NewB.withRecursionDecreased(), FR, *VI); else if (FTy->isStructureOrClassType()) - NewB = bindStruct(NewB, FR, *VI); + NewB = bindStruct(NewB.withRecursionDecreased(), FR, *VI); else NewB = bind(NewB, loc::MemRegionVal(FR), *VI); ++VI; @@ -2929,9 +3029,17 @@ RegionStoreManager::bindStruct(LimitedRegionBindingsConstRef B, LimitedRegionBindingsRef RegionStoreManager::bindAggregate(LimitedRegionBindingsConstRef B, const TypedRegion *R, SVal Val) { + + struct DepthGuard { + DepthGuard() { ++GlobalRecursionDepth; } + ~DepthGuard() { --GlobalRecursionDepth; } + } guard; + if (GlobalRecursionDepth > 1000) { + return B.withValuesEscaped(Val); + } llvm::TimeTraceScope TimeScope("RegionStoreManager::bindAggregate", [R]() { return R->getDescriptiveName(); }); - if (B.hasExhaustedBindingLimit()) + if (B.hasExhaustedBindingLimit() || B.hasExhaustedRecursionLimit()) return B.withValuesEscaped(Val); // Remove the old bindings, using 'R' as the root of all regions diff --git a/clang/test/Analysis/ftl-concat-crash.cpp b/clang/test/Analysis/ftl-concat-crash.cpp new file mode 100644 index 0000000000000..7e0aa2fe8135b --- /dev/null +++ b/clang/test/Analysis/ftl-concat-crash.cpp @@ -0,0 +1,63 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker=core -verify %s +// expected-no-diagnostics + +typedef unsigned long size_t; + +namespace android { +namespace ftl { + +template <typename T> +struct StaticString { + static constexpr size_t N = 1; + char view[2]; + constexpr StaticString(T) : view{'a', '\0'} {} +}; + +template <size_t N, typename... Ts> +struct Concat; + +template <size_t N, typename T, typename... Ts> +struct Concat<N, T, Ts...> : Concat<N + StaticString<T>::N, Ts...> { + explicit constexpr Concat(T v, Ts... args) { + append(v, args...); + } + +protected: + constexpr Concat() = default; + + constexpr void append(T v, Ts... args) { + StaticString<T> str(v); + this->buffer[this->pos] = str.view[0]; + this->pos++; + + using Base = Concat<N + StaticString<T>::N, Ts...>; + this->Base::append(args...); + } +}; + +template <size_t N> +struct Concat<N> { +protected: + constexpr Concat() : pos(0) {} + constexpr void append() { + buffer[pos] = '\0'; + } + + char buffer[N + 1]; + size_t pos; +}; + +template <typename... Ts> +Concat(Ts&&...) -> Concat<0, Ts.... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/184767 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
