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