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