1 //===- CoreEngine.h - Path-Sensitive Dataflow Engine ------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines a generic engine for intraprocedural, path-sensitive, 11 // dataflow analysis via graph reachability. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H 16 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H 17 18 #include "clang/AST/Stmt.h" 19 #include "clang/Analysis/AnalysisDeclContext.h" 20 #include "clang/Analysis/CFG.h" 21 #include "clang/Analysis/ProgramPoint.h" 22 #include "clang/Basic/LLVM.h" 23 #include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" 24 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 25 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" 26 #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" 27 #include "llvm/ADT/SmallVector.h" 28 #include "llvm/Support/Casting.h" 29 #include <cassert> 30 #include <memory> 31 #include <utility> 32 #include <vector> 33 34 namespace clang { 35 36 class AnalyzerOptions; 37 class CXXBindTemporaryExpr; 38 class Expr; 39 class LabelDecl; 40 41 namespace ento { 42 43 class FunctionSummariesTy; 44 class SubEngine; 45 46 //===----------------------------------------------------------------------===// 47 /// CoreEngine - Implements the core logic of the graph-reachability 48 /// analysis. It traverses the CFG and generates the ExplodedGraph. 49 /// Program "states" are treated as opaque void pointers. 50 /// The template class CoreEngine (which subclasses CoreEngine) 51 /// provides the matching component to the engine that knows the actual types 52 /// for states. Note that this engine only dispatches to transfer functions 53 /// at the statement and block-level. The analyses themselves must implement 54 /// any transfer function logic and the sub-expression level (if any). 55 class CoreEngine { 56 friend class CommonNodeBuilder; 57 friend class EndOfFunctionNodeBuilder; 58 friend class ExprEngine; 59 friend class IndirectGotoNodeBuilder; 60 friend class NodeBuilder; 61 friend struct NodeBuilderContext; 62 friend class SwitchNodeBuilder; 63 64 public: 65 using BlocksExhausted = 66 std::vector<std::pair<BlockEdge, const ExplodedNode *>>; 67 68 using BlocksAborted = 69 std::vector<std::pair<const CFGBlock *, const ExplodedNode *>>; 70 71 private: 72 SubEngine &SubEng; 73 74 /// G - The simulation graph. Each node is a (location,state) pair. 75 mutable ExplodedGraph G; 76 77 /// WList - A set of queued nodes that need to be processed by the 78 /// worklist algorithm. It is up to the implementation of WList to decide 79 /// the order that nodes are processed. 80 std::unique_ptr<WorkList> WList; 81 82 /// BCounterFactory - A factory object for created BlockCounter objects. 83 /// These are used to record for key nodes in the ExplodedGraph the 84 /// number of times different CFGBlocks have been visited along a path. 85 BlockCounter::Factory BCounterFactory; 86 87 /// The locations where we stopped doing work because we visited a location 88 /// too many times. 89 BlocksExhausted blocksExhausted; 90 91 /// The locations where we stopped because the engine aborted analysis, 92 /// usually because it could not reason about something. 93 BlocksAborted blocksAborted; 94 95 /// The information about functions shared by the whole translation unit. 96 /// (This data is owned by AnalysisConsumer.) 97 FunctionSummariesTy *FunctionSummaries; 98 99 void generateNode(const ProgramPoint &Loc, 100 ProgramStateRef State, 101 ExplodedNode *Pred); 102 103 void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred); 104 void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred); 105 void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred); 106 107 void HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred); 108 109 void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred); 110 111 void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B, 112 ExplodedNode *Pred); 113 void HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE, 114 const CFGBlock *B, ExplodedNode *Pred); 115 116 /// Handle conditional logic for running static initializers. 117 void HandleStaticInit(const DeclStmt *DS, const CFGBlock *B, 118 ExplodedNode *Pred); 119 120 private: 121 ExplodedNode *generateCallExitBeginNode(ExplodedNode *N, 122 const ReturnStmt *RS); 123 124 public: 125 /// Construct a CoreEngine object to analyze the provided CFG. 126 CoreEngine(SubEngine &subengine, 127 FunctionSummariesTy *FS, 128 AnalyzerOptions &Opts); 129 130 CoreEngine(const CoreEngine &) = delete; 131 CoreEngine &operator=(const CoreEngine &) = delete; 132 133 /// getGraph - Returns the exploded graph. getGraph()134 ExplodedGraph &getGraph() { return G; } 135 136 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of 137 /// steps. Returns true if there is still simulation state on the worklist. 138 bool ExecuteWorkList(const LocationContext *L, unsigned Steps, 139 ProgramStateRef InitState); 140 141 /// Returns true if there is still simulation state on the worklist. 142 bool ExecuteWorkListWithInitialState(const LocationContext *L, 143 unsigned Steps, 144 ProgramStateRef InitState, 145 ExplodedNodeSet &Dst); 146 147 /// Dispatch the work list item based on the given location information. 148 /// Use Pred parameter as the predecessor state. 149 void dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc, 150 const WorkListUnit& WU); 151 152 // Functions for external checking of whether we have unfinished work wasBlockAborted()153 bool wasBlockAborted() const { return !blocksAborted.empty(); } wasBlocksExhausted()154 bool wasBlocksExhausted() const { return !blocksExhausted.empty(); } hasWorkRemaining()155 bool hasWorkRemaining() const { return wasBlocksExhausted() || 156 WList->hasWork() || 157 wasBlockAborted(); } 158 159 /// Inform the CoreEngine that a basic block was aborted because 160 /// it could not be completely analyzed. addAbortedBlock(const ExplodedNode * node,const CFGBlock * block)161 void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) { 162 blocksAborted.push_back(std::make_pair(block, node)); 163 } 164 getWorkList()165 WorkList *getWorkList() const { return WList.get(); } 166 blocks_exhausted_begin()167 BlocksExhausted::const_iterator blocks_exhausted_begin() const { 168 return blocksExhausted.begin(); 169 } 170 blocks_exhausted_end()171 BlocksExhausted::const_iterator blocks_exhausted_end() const { 172 return blocksExhausted.end(); 173 } 174 blocks_aborted_begin()175 BlocksAborted::const_iterator blocks_aborted_begin() const { 176 return blocksAborted.begin(); 177 } 178 blocks_aborted_end()179 BlocksAborted::const_iterator blocks_aborted_end() const { 180 return blocksAborted.end(); 181 } 182 183 /// Enqueue the given set of nodes onto the work list. 184 void enqueue(ExplodedNodeSet &Set); 185 186 /// Enqueue nodes that were created as a result of processing 187 /// a statement onto the work list. 188 void enqueue(ExplodedNodeSet &Set, const CFGBlock *Block, unsigned Idx); 189 190 /// enqueue the nodes corresponding to the end of function onto the 191 /// end of path / work list. 192 void enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS); 193 194 /// Enqueue a single node created as a result of statement processing. 195 void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx); 196 }; 197 198 // TODO: Turn into a calss. 199 struct NodeBuilderContext { 200 const CoreEngine &Eng; 201 const CFGBlock *Block; 202 const LocationContext *LC; 203 NodeBuilderContextNodeBuilderContext204 NodeBuilderContext(const CoreEngine &E, const CFGBlock *B, ExplodedNode *N) 205 : Eng(E), Block(B), LC(N->getLocationContext()) { assert(B); } 206 207 /// Return the CFGBlock associated with this builder. getBlockNodeBuilderContext208 const CFGBlock *getBlock() const { return Block; } 209 210 /// Returns the number of times the current basic block has been 211 /// visited on the exploded graph path. blockCountNodeBuilderContext212 unsigned blockCount() const { 213 return Eng.WList->getBlockCounter().getNumVisited( 214 LC->getStackFrame(), 215 Block->getBlockID()); 216 } 217 }; 218 219 /// \class NodeBuilder 220 /// This is the simplest builder which generates nodes in the 221 /// ExplodedGraph. 222 /// 223 /// The main benefit of the builder is that it automatically tracks the 224 /// frontier nodes (or destination set). This is the set of nodes which should 225 /// be propagated to the next step / builder. They are the nodes which have been 226 /// added to the builder (either as the input node set or as the newly 227 /// constructed nodes) but did not have any outgoing transitions added. 228 class NodeBuilder { 229 virtual void anchor(); 230 231 protected: 232 const NodeBuilderContext &C; 233 234 /// Specifies if the builder results have been finalized. For example, if it 235 /// is set to false, autotransitions are yet to be generated. 236 bool Finalized; 237 238 bool HasGeneratedNodes = false; 239 240 /// The frontier set - a set of nodes which need to be propagated after 241 /// the builder dies. 242 ExplodedNodeSet &Frontier; 243 244 /// Checks if the results are ready. checkResults()245 virtual bool checkResults() { 246 return Finalized; 247 } 248 hasNoSinksInFrontier()249 bool hasNoSinksInFrontier() { 250 for (const auto I : Frontier) 251 if (I->isSink()) 252 return false; 253 return true; 254 } 255 256 /// Allow subclasses to finalize results before result_begin() is executed. finalizeResults()257 virtual void finalizeResults() {} 258 259 ExplodedNode *generateNodeImpl(const ProgramPoint &PP, 260 ProgramStateRef State, 261 ExplodedNode *Pred, 262 bool MarkAsSink = false); 263 264 public: 265 NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 266 const NodeBuilderContext &Ctx, bool F = true) C(Ctx)267 : C(Ctx), Finalized(F), Frontier(DstSet) { 268 Frontier.Add(SrcNode); 269 } 270 271 NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 272 const NodeBuilderContext &Ctx, bool F = true) C(Ctx)273 : C(Ctx), Finalized(F), Frontier(DstSet) { 274 Frontier.insert(SrcSet); 275 assert(hasNoSinksInFrontier()); 276 } 277 278 virtual ~NodeBuilder() = default; 279 280 /// Generates a node in the ExplodedGraph. generateNode(const ProgramPoint & PP,ProgramStateRef State,ExplodedNode * Pred)281 ExplodedNode *generateNode(const ProgramPoint &PP, 282 ProgramStateRef State, 283 ExplodedNode *Pred) { 284 return generateNodeImpl(PP, State, Pred, false); 285 } 286 287 /// Generates a sink in the ExplodedGraph. 288 /// 289 /// When a node is marked as sink, the exploration from the node is stopped - 290 /// the node becomes the last node on the path and certain kinds of bugs are 291 /// suppressed. generateSink(const ProgramPoint & PP,ProgramStateRef State,ExplodedNode * Pred)292 ExplodedNode *generateSink(const ProgramPoint &PP, 293 ProgramStateRef State, 294 ExplodedNode *Pred) { 295 return generateNodeImpl(PP, State, Pred, true); 296 } 297 getResults()298 const ExplodedNodeSet &getResults() { 299 finalizeResults(); 300 assert(checkResults()); 301 return Frontier; 302 } 303 304 using iterator = ExplodedNodeSet::iterator; 305 306 /// Iterators through the results frontier. begin()307 iterator begin() { 308 finalizeResults(); 309 assert(checkResults()); 310 return Frontier.begin(); 311 } 312 end()313 iterator end() { 314 finalizeResults(); 315 return Frontier.end(); 316 } 317 getContext()318 const NodeBuilderContext &getContext() { return C; } hasGeneratedNodes()319 bool hasGeneratedNodes() { return HasGeneratedNodes; } 320 takeNodes(const ExplodedNodeSet & S)321 void takeNodes(const ExplodedNodeSet &S) { 322 for (const auto I : S) 323 Frontier.erase(I); 324 } 325 takeNodes(ExplodedNode * N)326 void takeNodes(ExplodedNode *N) { Frontier.erase(N); } addNodes(const ExplodedNodeSet & S)327 void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); } addNodes(ExplodedNode * N)328 void addNodes(ExplodedNode *N) { Frontier.Add(N); } 329 }; 330 331 /// \class NodeBuilderWithSinks 332 /// This node builder keeps track of the generated sink nodes. 333 class NodeBuilderWithSinks: public NodeBuilder { 334 void anchor() override; 335 336 protected: 337 SmallVector<ExplodedNode*, 2> sinksGenerated; 338 ProgramPoint &Location; 339 340 public: NodeBuilderWithSinks(ExplodedNode * Pred,ExplodedNodeSet & DstSet,const NodeBuilderContext & Ctx,ProgramPoint & L)341 NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet, 342 const NodeBuilderContext &Ctx, ProgramPoint &L) 343 : NodeBuilder(Pred, DstSet, Ctx), Location(L) {} 344 345 ExplodedNode *generateNode(ProgramStateRef State, 346 ExplodedNode *Pred, 347 const ProgramPointTag *Tag = nullptr) { 348 const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location); 349 return NodeBuilder::generateNode(LocalLoc, State, Pred); 350 } 351 352 ExplodedNode *generateSink(ProgramStateRef State, ExplodedNode *Pred, 353 const ProgramPointTag *Tag = nullptr) { 354 const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location); 355 ExplodedNode *N = NodeBuilder::generateSink(LocalLoc, State, Pred); 356 if (N && N->isSink()) 357 sinksGenerated.push_back(N); 358 return N; 359 } 360 getSinks()361 const SmallVectorImpl<ExplodedNode*> &getSinks() const { 362 return sinksGenerated; 363 } 364 }; 365 366 /// \class StmtNodeBuilder 367 /// This builder class is useful for generating nodes that resulted from 368 /// visiting a statement. The main difference from its parent NodeBuilder is 369 /// that it creates a statement specific ProgramPoint. 370 class StmtNodeBuilder: public NodeBuilder { 371 NodeBuilder *EnclosingBldr; 372 373 public: 374 /// Constructs a StmtNodeBuilder. If the builder is going to process 375 /// nodes currently owned by another builder(with larger scope), use 376 /// Enclosing builder to transfer ownership. 377 StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 378 const NodeBuilderContext &Ctx, 379 NodeBuilder *Enclosing = nullptr) NodeBuilder(SrcNode,DstSet,Ctx)380 : NodeBuilder(SrcNode, DstSet, Ctx), EnclosingBldr(Enclosing) { 381 if (EnclosingBldr) 382 EnclosingBldr->takeNodes(SrcNode); 383 } 384 385 StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 386 const NodeBuilderContext &Ctx, 387 NodeBuilder *Enclosing = nullptr) NodeBuilder(SrcSet,DstSet,Ctx)388 : NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) { 389 if (EnclosingBldr) 390 for (const auto I : SrcSet) 391 EnclosingBldr->takeNodes(I); 392 } 393 394 ~StmtNodeBuilder() override; 395 396 using NodeBuilder::generateNode; 397 using NodeBuilder::generateSink; 398 399 ExplodedNode *generateNode(const Stmt *S, 400 ExplodedNode *Pred, 401 ProgramStateRef St, 402 const ProgramPointTag *tag = nullptr, 403 ProgramPoint::Kind K = ProgramPoint::PostStmtKind){ 404 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, 405 Pred->getLocationContext(), tag); 406 return NodeBuilder::generateNode(L, St, Pred); 407 } 408 409 ExplodedNode *generateSink(const Stmt *S, 410 ExplodedNode *Pred, 411 ProgramStateRef St, 412 const ProgramPointTag *tag = nullptr, 413 ProgramPoint::Kind K = ProgramPoint::PostStmtKind){ 414 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K, 415 Pred->getLocationContext(), tag); 416 return NodeBuilder::generateSink(L, St, Pred); 417 } 418 }; 419 420 /// BranchNodeBuilder is responsible for constructing the nodes 421 /// corresponding to the two branches of the if statement - true and false. 422 class BranchNodeBuilder: public NodeBuilder { 423 const CFGBlock *DstT; 424 const CFGBlock *DstF; 425 426 bool InFeasibleTrue; 427 bool InFeasibleFalse; 428 429 void anchor() override; 430 431 public: BranchNodeBuilder(ExplodedNode * SrcNode,ExplodedNodeSet & DstSet,const NodeBuilderContext & C,const CFGBlock * dstT,const CFGBlock * dstF)432 BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, 433 const NodeBuilderContext &C, 434 const CFGBlock *dstT, const CFGBlock *dstF) 435 : NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF), 436 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) { 437 // The branch node builder does not generate autotransitions. 438 // If there are no successors it means that both branches are infeasible. 439 takeNodes(SrcNode); 440 } 441 BranchNodeBuilder(const ExplodedNodeSet & SrcSet,ExplodedNodeSet & DstSet,const NodeBuilderContext & C,const CFGBlock * dstT,const CFGBlock * dstF)442 BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, 443 const NodeBuilderContext &C, 444 const CFGBlock *dstT, const CFGBlock *dstF) 445 : NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF), 446 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) { 447 takeNodes(SrcSet); 448 } 449 450 ExplodedNode *generateNode(ProgramStateRef State, bool branch, 451 ExplodedNode *Pred); 452 getTargetBlock(bool branch)453 const CFGBlock *getTargetBlock(bool branch) const { 454 return branch ? DstT : DstF; 455 } 456 markInfeasible(bool branch)457 void markInfeasible(bool branch) { 458 if (branch) 459 InFeasibleTrue = true; 460 else 461 InFeasibleFalse = true; 462 } 463 isFeasible(bool branch)464 bool isFeasible(bool branch) { 465 return branch ? !InFeasibleTrue : !InFeasibleFalse; 466 } 467 }; 468 469 class IndirectGotoNodeBuilder { 470 CoreEngine& Eng; 471 const CFGBlock *Src; 472 const CFGBlock &DispatchBlock; 473 const Expr *E; 474 ExplodedNode *Pred; 475 476 public: IndirectGotoNodeBuilder(ExplodedNode * pred,const CFGBlock * src,const Expr * e,const CFGBlock * dispatch,CoreEngine * eng)477 IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 478 const Expr *e, const CFGBlock *dispatch, CoreEngine* eng) 479 : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {} 480 481 class iterator { 482 friend class IndirectGotoNodeBuilder; 483 484 CFGBlock::const_succ_iterator I; 485 iterator(CFGBlock::const_succ_iterator i)486 iterator(CFGBlock::const_succ_iterator i) : I(i) {} 487 488 public: 489 iterator &operator++() { ++I; return *this; } 490 bool operator!=(const iterator &X) const { return I != X.I; } 491 getLabel()492 const LabelDecl *getLabel() const { 493 return cast<LabelStmt>((*I)->getLabel())->getDecl(); 494 } 495 getBlock()496 const CFGBlock *getBlock() const { 497 return *I; 498 } 499 }; 500 begin()501 iterator begin() { return iterator(DispatchBlock.succ_begin()); } end()502 iterator end() { return iterator(DispatchBlock.succ_end()); } 503 504 ExplodedNode *generateNode(const iterator &I, 505 ProgramStateRef State, 506 bool isSink = false); 507 getTarget()508 const Expr *getTarget() const { return E; } 509 getState()510 ProgramStateRef getState() const { return Pred->State; } 511 getLocationContext()512 const LocationContext *getLocationContext() const { 513 return Pred->getLocationContext(); 514 } 515 }; 516 517 class SwitchNodeBuilder { 518 CoreEngine& Eng; 519 const CFGBlock *Src; 520 const Expr *Condition; 521 ExplodedNode *Pred; 522 523 public: SwitchNodeBuilder(ExplodedNode * pred,const CFGBlock * src,const Expr * condition,CoreEngine * eng)524 SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, 525 const Expr *condition, CoreEngine* eng) 526 : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} 527 528 class iterator { 529 friend class SwitchNodeBuilder; 530 531 CFGBlock::const_succ_reverse_iterator I; 532 iterator(CFGBlock::const_succ_reverse_iterator i)533 iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} 534 535 public: 536 iterator &operator++() { ++I; return *this; } 537 bool operator!=(const iterator &X) const { return I != X.I; } 538 bool operator==(const iterator &X) const { return I == X.I; } 539 getCase()540 const CaseStmt *getCase() const { 541 return cast<CaseStmt>((*I)->getLabel()); 542 } 543 getBlock()544 const CFGBlock *getBlock() const { 545 return *I; 546 } 547 }; 548 begin()549 iterator begin() { return iterator(Src->succ_rbegin()+1); } end()550 iterator end() { return iterator(Src->succ_rend()); } 551 getSwitch()552 const SwitchStmt *getSwitch() const { 553 return cast<SwitchStmt>(Src->getTerminator()); 554 } 555 556 ExplodedNode *generateCaseStmtNode(const iterator &I, 557 ProgramStateRef State); 558 559 ExplodedNode *generateDefaultCaseNode(ProgramStateRef State, 560 bool isSink = false); 561 getCondition()562 const Expr *getCondition() const { return Condition; } 563 getState()564 ProgramStateRef getState() const { return Pred->State; } 565 getLocationContext()566 const LocationContext *getLocationContext() const { 567 return Pred->getLocationContext(); 568 } 569 }; 570 571 } // namespace ento 572 573 } // namespace clang 574 575 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H 576