================ @@ -0,0 +1,326 @@ +//===- NullTerminatedChecker.cpp - Check null_terminated params -*- 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 defines NullTerminatedChecker, which checks for arguments treated as +// buffers that are expected to be null-terminated (ends with a zero-valued +// element). A constant-size array is considered null-terminated if any of its +// elements may be zero on the current path. +// +// Parameters are marked as expecting null-terminated buffers using: +// __attribute__((annotate("null_terminated"))) +// +//===----------------------------------------------------------------------===// + +#include "clang/AST/Attr.h" +#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" +#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" +#include "clang/StaticAnalyzer/Core/Checker.h" +#include "clang/StaticAnalyzer/Core/CheckerManager.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" +#include "llvm/ADT/SmallBitVector.h" + +using namespace clang; +using namespace ento; + +namespace { +class NullTerminatedChecker : public Checker<check::PreCall> { +public: + // TODO: region-store-max-binding-fanout defaults to 128, meaning a single + // bind only covers that many elements. The 1024 option here is only truly + // respected when the array is built by separate bind operations, e.g., + // the case of straight-line writes: + // + // int a[500]; + // a[0] = val; + // a[1] = val; + // ... + // a[499] = val; + int MaxArraySize = 1024; + + void checkPreCall(const CallEvent &Call, CheckerContext &C) const; + +private: + const BugType BT{this, "Array not null-terminated", "API"}; + + /// Return true if the parameter has annotate("null_terminated"). + static bool isNullTerminatedParam(const ParmVarDecl *Param); + + /// Return true if any element in [0, \p ArraySize) can be zero. + bool mayContainZeroElement(ProgramStateRef State, SValBuilder &SVB, + QualType EltTy, uint64_t ArraySize, + const TypedValueRegion *Arr) const; +}; + +/// Return true if we can't prove \p Val is non-zero on the current path. +bool mayBeZero(ProgramStateRef State, SVal Val) { + // Unknown or undefined: can't reason either way. + auto DV = Val.getAs<DefinedSVal>(); + if (!DV) + return true; + + // Try the fast lookup first (much cheaper than assuming condition for + // concrete values). + ConditionTruthVal IsZero = State->isNull(*DV); + if (IsZero.isConstrainedFalse()) + return false; + if (IsZero.isConstrainedTrue()) + return true; + + // For an atomic symbol, the solver won't do any better than the preceding + // check, so we cannot prove anything further (hence it may be zero). + SymbolRef Sym = DV->getAsSymbol(/*IncludeBaseRegion=*/true); + if (Sym && isa<SymbolData>(Sym)) + return true; + + // Worst case: ask the solver if the value can be zero. + assert(!DV->isConstant() && + "Constants should have been handled by the fast path"); + return static_cast<bool>(State->assume(*DV, /*Assumption=*/false)); +} + +/// Load element \p Idx of the array \p Arr from the store. This is relatively +/// expensive since we are essentially asking the analyzer to work out a value +/// (rather than just read a preexisting binding), so this should be a last +/// resort call. +SVal loadElement(ProgramStateRef State, SValBuilder &SVB, QualType EltTy, + uint64_t Idx, const TypedValueRegion *Arr) { + SVal EltAddr = + State->getLValue(EltTy, SVB.makeArrayIndex(Idx), loc::MemRegionVal(Arr)); + if (auto EltLoc = EltAddr.getAs<Loc>()) + return State->getSVal(*EltLoc); + return UnknownVal(); +} + +/// Map the direct bindings of a memory cluster onto the elements of one array, +/// looking for an element that may be zero. +class ElementBindingScanner : public StoreManager::ClusterBindingsHandler { + ProgramStateRef State; + ASTContext &Ctx; + /// The region the offset of the array is relative to. + const MemRegion *OffsetRegion; + /// Offset of the array within \c OffsetRegion, in bits. + uint64_t ArrOffset; + uint64_t EltBits; + + /// Elements that have a direct binding. + llvm::SmallBitVector Covered; + /// A binding overlaps an element without us knowing which part of it. + bool Imprecise = false; + /// An element that has a direct binding may be zero. + bool FoundPossibleZero = false; + +public: + ElementBindingScanner(ProgramStateRef State, ASTContext &Ctx, + RegionOffset ArrOffset, uint64_t EltBits, + uint64_t ArraySize) + : State(State), Ctx(Ctx), OffsetRegion(ArrOffset.getRegion()), + ArrOffset(ArrOffset.getOffset()), EltBits(EltBits), Covered(ArraySize) { + } + + bool foundPossibleZero() const { return FoundPossibleZero; } + bool isImprecise() const { return Imprecise; } + bool hasElementWithoutBinding() const { return !Covered.all(); } + bool hasBinding(uint64_t Idx) const { return Covered[Idx]; } + + /// Check a binding to see if we can reason about elements in the array. + /// Return true if we should keep checking/iterating over the rest of the + /// bindings in the cluster. + bool handleBinding(StoreManager &, Store, const MemRegion *Region, + std::optional<uint64_t> BitOffset, + StoreManager::BindingKind Kind, SVal Val) override { + // Skip default bindings: we can't tell which elements this applies to, + // which will end up getting loaded later on, so safe to skip. + if (Kind == StoreManager::BindingKind::Default) + return true; + + // Skip symbolic offsets: we can't map the location to an index. But the + // write would drop existing overlapping concrete bindings anyway, which + // would then load as unknown, so skipping is sound. Bailing entirely + // (returning false) would skip bindings for sibling objects (e.g., writes + // to `s.b[i]` should not make `s.a` unknown), so we skip. + if (!BitOffset) + return true; + + // Skip bindings not measured from the array's own offset because the + // offsets aren't comparable. + if (Region != OffsetRegion) + return true; + + // The binding belongs to another object within the cluster, so there's + // nothing to learn here. + if (*BitOffset < ArrOffset) + return true; // Precedes the array + uint64_t Rel = *BitOffset - ArrOffset; + uint64_t Idx = Rel / EltBits; + if (Idx >= Covered.size()) + return true; // Follows the array + + // Bail when the offset is either not element-aligned, or when the width + // doesn't match element size (e.g., writing a char into an int array on + // x86). + if (Rel % EltBits != 0 || getBindingWidth(Val) != EltBits) { + Imprecise = true; + return false; + } + + Covered.set(Idx); + if (mayBeZero(State, Val)) { + FoundPossibleZero = true; + return false; + } + return true; + } + +private: + /// Return the number of bits the value of a binding occupies, if known. + std::optional<uint64_t> getBindingWidth(SVal Val) const { + QualType T = Val.getType(Ctx); + if (T.isNull() || T->isFunctionType() || T->isIncompleteType()) + return std::nullopt; + return Ctx.getTypeSize(T); + } +}; +} // namespace + +bool NullTerminatedChecker::isNullTerminatedParam(const ParmVarDecl *Param) { + return llvm::any_of(Param->specific_attrs<AnnotateAttr>(), + [](const AnnotateAttr *Ann) { + return Ann->getAnnotation() == "null_terminated"; + }); +} + +bool NullTerminatedChecker::mayContainZeroElement( + ProgramStateRef State, SValBuilder &SVB, QualType EltTy, uint64_t ArraySize, + const TypedValueRegion *Arr) const { + ASTContext &Ctx = State->getStateManager().getContext(); + + // Bindings are keyed by an offset from the base region of the cluster, so we + // need the offset of the array itself to map them onto its elements. + RegionOffset Offset = Arr->getAsOffset(); + if (!Offset.getRegion() || Offset.hasSymbolicOffset()) + return true; + uint64_t EltBits = Ctx.getTypeSize(EltTy); + if (EltBits == 0) + return true; + + ElementBindingScanner Scanner(State, Ctx, Offset, EltBits, ArraySize); + State->getStateManager().getStoreManager().iterClusterBindings( + State->getStore(), Offset.getRegion()->getBaseRegion(), Scanner); + + if (Scanner.foundPossibleZero() || Scanner.isImprecise()) + return true; + if (!Scanner.hasElementWithoutBinding()) + return false; + + // The remaining elements are either covered by a default binding or + // uninitialized. Iterate backwards, starting at the end of the array, since + // terminators are usually closer to the end. + for (uint64_t I = ArraySize; I-- > 0;) { + if (Scanner.hasBinding(I)) + continue; + if (mayBeZero(State, loadElement(State, SVB, EltTy, I, Arr))) + return true; + } + return false; +} + +void NullTerminatedChecker::checkPreCall(const CallEvent &Call, + CheckerContext &C) const { + const auto *FD = dyn_cast_or_null<FunctionDecl>(Call.getDecl()); + if (!FD) + return; + + ProgramStateRef State = C.getState(); + SValBuilder &SVB = C.getSValBuilder(); + ASTContext &Ctx = C.getASTContext(); + + unsigned NumParams = FD->getNumParams(); + unsigned NumArgs = Call.getNumArgs(); + + // The call to min handles the case when |NumParams| != |NumArgs|. + for (unsigned I = 0, N = std::min(NumParams, NumArgs); I < N; ++I) { ---------------- NagyDonat wrote:
Be very careful with this loop: unfortunately there is no guarantee that the `I`th parameter in the declaration corresponds to the `I`th argument in the call. For example check out the class [CXXMemberOperatorCall](https://github.com/llvm/llvm-project/blob/6b04339b88eb5e7f47233be197e6ba816f52d730/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h#L841) which overrides the methods `getASTArgumentIndex` and `getAdjustedParameterIndex` to signify that there is an off-by-one difference. You will probably need to use one of these methods to implement this `for` loop correctly. I know that this case probably won't appear in real-world code, but it is still better to handle it. (Also, please add a testcase for it.) https://github.com/llvm/llvm-project/pull/188128 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
