//===- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ----------===// // // 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 defines a meta-engine for path-sensitive dataflow analysis that // is built on CoreEngine, but provides the boilerplate to execute transfer // functions and build the ExplodedGraph at the expression level. // //===----------------------------------------------------------------------===// #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" #include "PrettyStackTraceLocationContext.h" #include "clang/AST/ASTContext.h" #include "clang/AST/Decl.h" #include "clang/AST/DeclBase.h" #include "clang/AST/DeclCXX.h" #include "clang/AST/DeclObjC.h" #include "clang/AST/Expr.h" #include "clang/AST/ExprCXX.h" #include "clang/AST/ExprObjC.h" #include "clang/AST/ParentMap.h" #include "clang/AST/PrettyPrinter.h" #include "clang/AST/Stmt.h" #include "clang/AST/StmtCXX.h" #include "clang/AST/StmtObjC.h" #include "clang/AST/Type.h" #include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/ConstructionContext.h" #include "clang/Analysis/ProgramPoint.h" #include "clang/Basic/IdentifierTable.h" #include "clang/Basic/JsonSupport.h" #include "clang/Basic/LLVM.h" #include "clang/Basic/LangOptions.h" #include "clang/Basic/PrettyStackTrace.h" #include "clang/Basic/SourceLocation.h" #include "clang/Basic/SourceManager.h" #include "clang/Basic/Specifiers.h" #include "clang/StaticAnalyzer/Core/AnalyzerOptions.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" #include "clang/StaticAnalyzer/Core/CheckerManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h" #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" #include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h" #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h" #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" #include "llvm/ADT/APSInt.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/ImmutableMap.h" #include "llvm/ADT/ImmutableSet.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Support/Casting.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/DOTGraphTraits.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/GraphWriter.h" #include "llvm/Support/SaveAndRestore.h" #include "llvm/Support/raw_ostream.h" #include <cassert> #include <cstdint> #include <memory> #include <optional> #include <string> #include <tuple> #include <utility> #include <vector> usingnamespaceclang; usingnamespaceento; #define DEBUG_TYPE … STATISTIC(NumRemoveDeadBindings, "The # of times RemoveDeadBindings is called"); STATISTIC(NumMaxBlockCountReached, "The # of aborted paths due to reaching the maximum block count in " "a top level function"); STATISTIC(NumMaxBlockCountReachedInInlined, "The # of aborted paths due to reaching the maximum block count in " "an inlined function"); STATISTIC(NumTimesRetriedWithoutInlining, "The # of times we re-evaluated a call without inlining"); //===----------------------------------------------------------------------===// // Internal program state traits. //===----------------------------------------------------------------------===// namespace { // When modeling a C++ constructor, for a variety of reasons we need to track // the location of the object for the duration of its ConstructionContext. // ObjectsUnderConstruction maps statements within the construction context // to the object's location, so that on every such statement the location // could have been retrieved. /// ConstructedObjectKey is used for being able to find the path-sensitive /// memory region of a freshly constructed object while modeling the AST node /// that syntactically represents the object that is being constructed. /// Semantics of such nodes may sometimes require access to the region that's /// not otherwise present in the program state, or to the very fact that /// the construction context was present and contained references to these /// AST nodes. class ConstructedObjectKey { … }; } // namespace ObjectsUnderConstructionMap; REGISTER_TRAIT_WITH_PROGRAMSTATE(…) // This trait is responsible for storing the index of the element that is to be // constructed in the next iteration. As a result a CXXConstructExpr is only // stored if it is array type. Also the index is the index of the continuous // memory region, which is important for multi-dimensional arrays. E.g:: int // arr[2][2]; assume arr[1][1] will be the next element under construction, so // the index is 3. IndexOfElementToConstructMap; REGISTER_TRAIT_WITH_PROGRAMSTATE(…) // This trait is responsible for holding our pending ArrayInitLoopExprs. // It pairs the LocationContext and the initializer CXXConstructExpr with // the size of the array that's being copy initialized. PendingInitLoopMap; REGISTER_TRAIT_WITH_PROGRAMSTATE(…) PendingArrayDestructionMap; REGISTER_TRAIT_WITH_PROGRAMSTATE(…) //===----------------------------------------------------------------------===// // Engine construction and deletion. //===----------------------------------------------------------------------===// static const char* TagProviderName = …; ExprEngine::ExprEngine(cross_tu::CrossTranslationUnitContext &CTU, AnalysisManager &mgr, SetOfConstDecls *VisitedCalleesIn, FunctionSummariesTy *FS, InliningModes HowToInlineIn) : … { … } //===----------------------------------------------------------------------===// // Utility methods. //===----------------------------------------------------------------------===// ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) { … } ProgramStateRef ExprEngine::createTemporaryRegionIfNeeded( ProgramStateRef State, const LocationContext *LC, const Expr *InitWithAdjustments, const Expr *Result, const SubRegion **OutRegionWithAdjustments) { … } ProgramStateRef ExprEngine::setIndexOfElementToConstruct( ProgramStateRef State, const CXXConstructExpr *E, const LocationContext *LCtx, unsigned Idx) { … } std::optional<unsigned> ExprEngine::getPendingInitLoop(ProgramStateRef State, const CXXConstructExpr *E, const LocationContext *LCtx) { … } ProgramStateRef ExprEngine::removePendingInitLoop(ProgramStateRef State, const CXXConstructExpr *E, const LocationContext *LCtx) { … } ProgramStateRef ExprEngine::setPendingInitLoop(ProgramStateRef State, const CXXConstructExpr *E, const LocationContext *LCtx, unsigned Size) { … } std::optional<unsigned> ExprEngine::getIndexOfElementToConstruct(ProgramStateRef State, const CXXConstructExpr *E, const LocationContext *LCtx) { … } ProgramStateRef ExprEngine::removeIndexOfElementToConstruct(ProgramStateRef State, const CXXConstructExpr *E, const LocationContext *LCtx) { … } std::optional<unsigned> ExprEngine::getPendingArrayDestruction(ProgramStateRef State, const LocationContext *LCtx) { … } ProgramStateRef ExprEngine::setPendingArrayDestruction( ProgramStateRef State, const LocationContext *LCtx, unsigned Idx) { … } ProgramStateRef ExprEngine::removePendingArrayDestruction(ProgramStateRef State, const LocationContext *LCtx) { … } ProgramStateRef ExprEngine::addObjectUnderConstruction(ProgramStateRef State, const ConstructionContextItem &Item, const LocationContext *LC, SVal V) { … } std::optional<SVal> ExprEngine::getObjectUnderConstruction(ProgramStateRef State, const ConstructionContextItem &Item, const LocationContext *LC) { … } ProgramStateRef ExprEngine::finishObjectConstruction(ProgramStateRef State, const ConstructionContextItem &Item, const LocationContext *LC) { … } ProgramStateRef ExprEngine::elideDestructor(ProgramStateRef State, const CXXBindTemporaryExpr *BTE, const LocationContext *LC) { … } ProgramStateRef ExprEngine::cleanupElidedDestructor(ProgramStateRef State, const CXXBindTemporaryExpr *BTE, const LocationContext *LC) { … } bool ExprEngine::isDestructorElided(ProgramStateRef State, const CXXBindTemporaryExpr *BTE, const LocationContext *LC) { … } bool ExprEngine::areAllObjectsFullyConstructed(ProgramStateRef State, const LocationContext *FromLC, const LocationContext *ToLC) { … } //===----------------------------------------------------------------------===// // Top-level transfer function logic (Dispatcher). //===----------------------------------------------------------------------===// /// evalAssume - Called by ConstraintManager. Used to call checker-specific /// logic for handling assumptions on symbolic values. ProgramStateRef ExprEngine::processAssume(ProgramStateRef state, SVal cond, bool assumption) { … } ProgramStateRef ExprEngine::processRegionChanges(ProgramStateRef state, const InvalidatedSymbols *invalidated, ArrayRef<const MemRegion *> Explicits, ArrayRef<const MemRegion *> Regions, const LocationContext *LCtx, const CallEvent *Call) { … } static void printObjectsUnderConstructionJson(raw_ostream &Out, ProgramStateRef State, const char *NL, const LocationContext *LCtx, unsigned int Space = 0, bool IsDot = false) { … } static void printIndicesOfElementsToConstructJson( raw_ostream &Out, ProgramStateRef State, const char *NL, const LocationContext *LCtx, unsigned int Space = 0, bool IsDot = false) { … } static void printPendingInitLoopJson(raw_ostream &Out, ProgramStateRef State, const char *NL, const LocationContext *LCtx, unsigned int Space = 0, bool IsDot = false) { … } static void printPendingArrayDestructionsJson(raw_ostream &Out, ProgramStateRef State, const char *NL, const LocationContext *LCtx, unsigned int Space = 0, bool IsDot = false) { … } /// A helper function to generalize program state trait printing. /// The function invokes Printer as 'Printer(Out, State, NL, LC, Space, IsDot, /// std::forward<Args>(args)...)'. \n One possible type for Printer is /// 'void()(raw_ostream &, ProgramStateRef, const char *, const LocationContext /// *, unsigned int, bool, ...)' \n \param Trait The state trait to be printed. /// \param Printer A void function that prints Trait. /// \param Args An additional parameter pack that is passed to Print upon /// invocation. template <typename Trait, typename Printer, typename... Args> static void printStateTraitWithLocationContextJson( raw_ostream &Out, ProgramStateRef State, const LocationContext *LCtx, const char *NL, unsigned int Space, bool IsDot, const char *jsonPropertyName, Printer printer, Args &&...args) { … } void ExprEngine::printJson(raw_ostream &Out, ProgramStateRef State, const LocationContext *LCtx, const char *NL, unsigned int Space, bool IsDot) const { … } void ExprEngine::processEndWorklist() { … } void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred, unsigned StmtIdx, NodeBuilderContext *Ctx) { … } static bool shouldRemoveDeadBindings(AnalysisManager &AMgr, const Stmt *S, const ExplodedNode *Pred, const LocationContext *LC) { … } void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out, const Stmt *ReferenceStmt, const LocationContext *LC, const Stmt *DiagnosticStmt, ProgramPoint::Kind K) { … } const ProgramPointTag *ExprEngine::cleanupNodeTag() { … } void ExprEngine::ProcessStmt(const Stmt *currStmt, ExplodedNode *Pred) { … } void ExprEngine::ProcessLoopExit(const Stmt* S, ExplodedNode *Pred) { … } void ExprEngine::ProcessInitializer(const CFGInitializer CFGInit, ExplodedNode *Pred) { … } std::pair<ProgramStateRef, uint64_t> ExprEngine::prepareStateForArrayDestruction(const ProgramStateRef State, const MemRegion *Region, const QualType &ElementTy, const LocationContext *LCtx, SVal *ElementCountVal) { … } void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D, ExplodedNode *Pred) { … } void ExprEngine::ProcessNewAllocator(const CXXNewExpr *NE, ExplodedNode *Pred) { … } void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor, ExplodedNode *Pred, ExplodedNodeSet &Dst) { … } void ExprEngine::ProcessDeleteDtor(const CFGDeleteDtor Dtor, ExplodedNode *Pred, ExplodedNodeSet &Dst) { … } void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D, ExplodedNode *Pred, ExplodedNodeSet &Dst) { … } void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D, ExplodedNode *Pred, ExplodedNodeSet &Dst) { … } void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D, ExplodedNode *Pred, ExplodedNodeSet &Dst) { … } void ExprEngine::processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE, NodeBuilderContext &BldCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF) { … } void ExprEngine::VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *BTE, ExplodedNodeSet &PreVisit, ExplodedNodeSet &Dst) { … } ProgramStateRef ExprEngine::escapeValues(ProgramStateRef State, ArrayRef<SVal> Vs, PointerEscapeKind K, const CallEvent *Call) const { … } void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, ExplodedNodeSet &DstTop) { … } bool ExprEngine::replayWithoutInlining(ExplodedNode *N, const LocationContext *CalleeLC) { … } /// Block entrance. (Update counters). void ExprEngine::processCFGBlockEntrance(const BlockEdge &L, NodeBuilderWithSinks &nodeBuilder, ExplodedNode *Pred) { … } //===----------------------------------------------------------------------===// // Branch processing. //===----------------------------------------------------------------------===// /// RecoverCastedSymbol - A helper function for ProcessBranch that is used /// to try to recover some path-sensitivity for casts of symbolic /// integers that promote their values (which are currently not tracked well). /// This function returns the SVal bound to Condition->IgnoreCasts if all the // cast(s) did was sign-extend the original value. static SVal RecoverCastedSymbol(ProgramStateRef state, const Stmt *Condition, const LocationContext *LCtx, ASTContext &Ctx) { … } #ifndef NDEBUG static const Stmt *getRightmostLeaf(const Stmt *Condition) { while (Condition) { const auto *BO = dyn_cast<BinaryOperator>(Condition); if (!BO || !BO->isLogicalOp()) { return Condition; } Condition = BO->getRHS()->IgnoreParens(); } return nullptr; } #endif // Returns the condition the branch at the end of 'B' depends on and whose value // has been evaluated within 'B'. // In most cases, the terminator condition of 'B' will be evaluated fully in // the last statement of 'B'; in those cases, the resolved condition is the // given 'Condition'. // If the condition of the branch is a logical binary operator tree, the CFG is // optimized: in that case, we know that the expression formed by all but the // rightmost leaf of the logical binary operator tree must be true, and thus // the branch condition is at this point equivalent to the truth value of that // rightmost leaf; the CFG block thus only evaluates this rightmost leaf // expression in its final statement. As the full condition in that case was // not evaluated, and is thus not in the SVal cache, we need to use that leaf // expression to evaluate the truth value of the condition in the current state // space. static const Stmt *ResolveCondition(const Stmt *Condition, const CFGBlock *B) { … } ObjCForLctxPair; REGISTER_MAP_WITH_PROGRAMSTATE(…) … ProgramStateRef ExprEngine::setWhetherHasMoreIteration( ProgramStateRef State, const ObjCForCollectionStmt *O, const LocationContext *LC, bool HasMoreIteraton) { … } ProgramStateRef ExprEngine::removeIterationState(ProgramStateRef State, const ObjCForCollectionStmt *O, const LocationContext *LC) { … } bool ExprEngine::hasMoreIteration(ProgramStateRef State, const ObjCForCollectionStmt *O, const LocationContext *LC) { … } /// Split the state on whether there are any more iterations left for this loop. /// Returns a (HasMoreIteration, HasNoMoreIteration) pair, or std::nullopt when /// the acquisition of the loop condition value failed. static std::optional<std::pair<ProgramStateRef, ProgramStateRef>> assumeCondition(const Stmt *Condition, ExplodedNode *N) { … } void ExprEngine::processBranch(const Stmt *Condition, NodeBuilderContext& BldCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF) { … } /// The GDM component containing the set of global variables which have been /// previously initialized with explicit initializers. REGISTER_TRAIT_WITH_PROGRAMSTATE(…) … void ExprEngine::processStaticInitializer(const DeclStmt *DS, NodeBuilderContext &BuilderCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF) { … } /// processIndirectGoto - Called by CoreEngine. Used to generate successor /// nodes by processing the 'effects' of a computed goto jump. void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) { … } void ExprEngine::processBeginOfFunction(NodeBuilderContext &BC, ExplodedNode *Pred, ExplodedNodeSet &Dst, const BlockEdge &L) { … } /// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path /// nodes when the control reaches the end of a function. void ExprEngine::processEndOfFunction(NodeBuilderContext& BC, ExplodedNode *Pred, const ReturnStmt *RS) { … } /// ProcessSwitch - Called by CoreEngine. Used to generate successor /// nodes by processing the 'effects' of a switch statement. void ExprEngine::processSwitch(SwitchNodeBuilder& builder) { … } //===----------------------------------------------------------------------===// // Transfer functions: Loads and stores. //===----------------------------------------------------------------------===// void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, ExplodedNode *Pred, ExplodedNodeSet &Dst) { … } /// VisitArrayInitLoopExpr - Transfer function for array init loop. void ExprEngine::VisitArrayInitLoopExpr(const ArrayInitLoopExpr *Ex, ExplodedNode *Pred, ExplodedNodeSet &Dst) { … } /// VisitArraySubscriptExpr - Transfer function for array accesses void ExprEngine::VisitArraySubscriptExpr(const ArraySubscriptExpr *A, ExplodedNode *Pred, ExplodedNodeSet &Dst){ … } /// VisitMemberExpr - Transfer function for member expressions. void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred, ExplodedNodeSet &Dst) { … } void ExprEngine::VisitAtomicExpr(const AtomicExpr *AE, ExplodedNode *Pred, ExplodedNodeSet &Dst) { … } // A value escapes in four possible cases: // (1) We are binding to something that is not a memory region. // (2) We are binding to a MemRegion that does not have stack storage. // (3) We are binding to a top-level parameter region with a non-trivial // destructor. We won't see the destructor during analysis, but it's there. // (4) We are binding to a MemRegion with stack storage that the store // does not understand. ProgramStateRef ExprEngine::processPointerEscapedOnBind( ProgramStateRef State, ArrayRef<std::pair<SVal, SVal>> LocAndVals, const LocationContext *LCtx, PointerEscapeKind Kind, const CallEvent *Call) { … } ProgramStateRef ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, SVal Loc, SVal Val, const LocationContext *LCtx) { … } ProgramStateRef ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State, const InvalidatedSymbols *Invalidated, ArrayRef<const MemRegion *> ExplicitRegions, const CallEvent *Call, RegionAndSymbolInvalidationTraits &ITraits) { … } /// evalBind - Handle the semantics of binding a value to a specific location. /// This method is used by evalStore and (soon) VisitDeclStmt, and others. void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, ExplodedNode *Pred, SVal location, SVal Val, bool atDeclInit, const ProgramPoint *PP) { … } /// evalStore - Handle the semantics of a store via an assignment. /// @param Dst The node set to store generated state nodes /// @param AssignE The assignment expression if the store happens in an /// assignment. /// @param LocationE The location expression that is stored to. /// @param state The current simulation state /// @param location The location to store the value /// @param Val The value to be stored void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, const Expr *LocationE, ExplodedNode *Pred, ProgramStateRef state, SVal location, SVal Val, const ProgramPointTag *tag) { … } void ExprEngine::evalLoad(ExplodedNodeSet &Dst, const Expr *NodeEx, const Expr *BoundEx, ExplodedNode *Pred, ProgramStateRef state, SVal location, const ProgramPointTag *tag, QualType LoadTy) { … } void ExprEngine::evalLocation(ExplodedNodeSet &Dst, const Stmt *NodeEx, const Stmt *BoundEx, ExplodedNode *Pred, ProgramStateRef state, SVal location, bool isLoad) { … } std::pair<const ProgramPointTag *, const ProgramPointTag*> ExprEngine::geteagerlyAssumeBinOpBifurcationTags() { … } void ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst, ExplodedNodeSet &Src, const Expr *Ex) { … } void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred, ExplodedNodeSet &Dst) { … } void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred, ExplodedNodeSet &Dst) { … } //===----------------------------------------------------------------------===// // Visualization. //===----------------------------------------------------------------------===// namespace llvm { template<> struct DOTGraphTraits<ExplodedGraph*> : public DefaultDOTGraphTraits { … }; } // namespace llvm void ExprEngine::ViewGraph(bool trim) { … } void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode *> Nodes) { … } std::string ExprEngine::DumpGraph(bool trim, StringRef Filename) { … } std::string ExprEngine::DumpGraph(ArrayRef<const ExplodedNode *> Nodes, StringRef Filename) { … } void *ProgramStateTrait<ReplayWithoutInlining>::GDMIndex() { … } void ExprEngine::anchor() { … }
Codebase Browser
llvm