From dd53bdbfdec7a179e8fb38008ab2b397572b3a69 Mon Sep 17 00:00:00 2001 From: Kristof Umann Date: Wed, 14 Aug 2019 12:20:08 +0000 Subject: [PATCH] [analyzer][CFG] Don't track the condition of asserts Well, what is says on the tin I guess! Some more changes: * Move isInevitablySinking() from BugReporter.cpp to CFGBlock's interface * Rename and move findBlockForNode() from BugReporter.cpp to ExplodedNode::getCFGBlock() Differential Revision: https://reviews.llvm.org/D65287 llvm-svn: 368836 --- clang/include/clang/Analysis/CFG.h | 4 + clang/lib/Analysis/CFG.cpp | 65 ++++++ clang/lib/StaticAnalyzer/Core/BugReporter.cpp | 89 +------- .../StaticAnalyzer/Core/BugReporterVisitors.cpp | 52 +++-- clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp | 16 ++ .../track-control-dependency-conditions.cpp | 239 +++++++++++++++++++++ 6 files changed, 365 insertions(+), 100 deletions(-) diff --git a/clang/include/clang/Analysis/CFG.h b/clang/include/clang/Analysis/CFG.h index 277b229..2c38d51 100644 --- a/clang/include/clang/Analysis/CFG.h +++ b/clang/include/clang/Analysis/CFG.h @@ -855,6 +855,10 @@ public: void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; } void setHasNoReturnElement() { HasNoReturnElement = true; } + /// Returns true if the block would eventually end with a sink (a noreturn + /// node). + bool isInevitablySinking() const; + CFGTerminator getTerminator() const { return Terminator; } Stmt *getTerminatorStmt() { return Terminator.getStmt(); } diff --git a/clang/lib/Analysis/CFG.cpp b/clang/lib/Analysis/CFG.cpp index 0ed1e98..b050347 100644 --- a/clang/lib/Analysis/CFG.cpp +++ b/clang/lib/Analysis/CFG.cpp @@ -5652,6 +5652,71 @@ void CFGBlock::printTerminatorJson(raw_ostream &Out, const LangOptions &LO, Out << JsonFormat(TempOut.str(), AddQuotes); } +// Returns true if by simply looking at the block, we can be sure that it +// results in a sink during analysis. This is useful to know when the analysis +// was interrupted, and we try to figure out if it would sink eventually. +// There may be many more reasons why a sink would appear during analysis +// (eg. checkers may generate sinks arbitrarily), but here we only consider +// sinks that would be obvious by looking at the CFG. +static bool isImmediateSinkBlock(const CFGBlock *Blk) { + if (Blk->hasNoReturnElement()) + return true; + + // FIXME: Throw-expressions are currently generating sinks during analysis: + // they're not supported yet, and also often used for actually terminating + // the program. So we should treat them as sinks in this analysis as well, + // at least for now, but once we have better support for exceptions, + // we'd need to carefully handle the case when the throw is being + // immediately caught. + if (std::any_of(Blk->begin(), Blk->end(), [](const CFGElement &Elm) { + if (Optional StmtElm = Elm.getAs()) + if (isa(StmtElm->getStmt())) + return true; + return false; + })) + return true; + + return false; +} + +bool CFGBlock::isInevitablySinking() const { + const CFG &Cfg = *getParent(); + + const CFGBlock *StartBlk = this; + if (isImmediateSinkBlock(StartBlk)) + return true; + + llvm::SmallVector DFSWorkList; + llvm::SmallPtrSet Visited; + + DFSWorkList.push_back(StartBlk); + while (!DFSWorkList.empty()) { + const CFGBlock *Blk = DFSWorkList.back(); + DFSWorkList.pop_back(); + Visited.insert(Blk); + + // If at least one path reaches the CFG exit, it means that control is + // returned to the caller. For now, say that we are not sure what + // happens next. If necessary, this can be improved to analyze + // the parent StackFrameContext's call site in a similar manner. + if (Blk == &Cfg.getExit()) + return false; + + for (const auto &Succ : Blk->succs()) { + if (const CFGBlock *SuccBlk = Succ.getReachableBlock()) { + if (!isImmediateSinkBlock(SuccBlk) && !Visited.count(SuccBlk)) { + // If the block has reachable child blocks that aren't no-return, + // add them to the worklist. + DFSWorkList.push_back(SuccBlk); + } + } + } + } + + // Nothing reached the exit. It can only mean one thing: there's no return. + return true; +} + const Expr *CFGBlock::getLastCondition() const { // If the terminator is a temporary dtor or a virtual base, etc, we can't // retrieve a meaningful condition, bail out. diff --git a/clang/lib/StaticAnalyzer/Core/BugReporter.cpp b/clang/lib/StaticAnalyzer/Core/BugReporter.cpp index faf9481..f5a5140 100644 --- a/clang/lib/StaticAnalyzer/Core/BugReporter.cpp +++ b/clang/lib/StaticAnalyzer/Core/BugReporter.cpp @@ -2716,90 +2716,6 @@ struct FRIEC_WLItem { } // namespace -static const CFGBlock *findBlockForNode(const ExplodedNode *N) { - ProgramPoint P = N->getLocation(); - if (auto BEP = P.getAs()) - return BEP->getBlock(); - - // Find the node's current statement in the CFG. - if (const Stmt *S = PathDiagnosticLocation::getStmt(N)) - return N->getLocationContext()->getAnalysisDeclContext() - ->getCFGStmtMap()->getBlock(S); - - return nullptr; -} - -// Returns true if by simply looking at the block, we can be sure that it -// results in a sink during analysis. This is useful to know when the analysis -// was interrupted, and we try to figure out if it would sink eventually. -// There may be many more reasons why a sink would appear during analysis -// (eg. checkers may generate sinks arbitrarily), but here we only consider -// sinks that would be obvious by looking at the CFG. -static bool isImmediateSinkBlock(const CFGBlock *Blk) { - if (Blk->hasNoReturnElement()) - return true; - - // FIXME: Throw-expressions are currently generating sinks during analysis: - // they're not supported yet, and also often used for actually terminating - // the program. So we should treat them as sinks in this analysis as well, - // at least for now, but once we have better support for exceptions, - // we'd need to carefully handle the case when the throw is being - // immediately caught. - if (std::any_of(Blk->begin(), Blk->end(), [](const CFGElement &Elm) { - if (Optional StmtElm = Elm.getAs()) - if (isa(StmtElm->getStmt())) - return true; - return false; - })) - return true; - - return false; -} - -// Returns true if by looking at the CFG surrounding the node's program -// point, we can be sure that any analysis starting from this point would -// eventually end with a sink. We scan the child CFG blocks in a depth-first -// manner and see if all paths eventually end up in an immediate sink block. -static bool isInevitablySinking(const ExplodedNode *N) { - const CFG &Cfg = N->getCFG(); - - const CFGBlock *StartBlk = findBlockForNode(N); - if (!StartBlk) - return false; - if (isImmediateSinkBlock(StartBlk)) - return true; - - llvm::SmallVector DFSWorkList; - llvm::SmallPtrSet Visited; - - DFSWorkList.push_back(StartBlk); - while (!DFSWorkList.empty()) { - const CFGBlock *Blk = DFSWorkList.back(); - DFSWorkList.pop_back(); - Visited.insert(Blk); - - // If at least one path reaches the CFG exit, it means that control is - // returned to the caller. For now, say that we are not sure what - // happens next. If necessary, this can be improved to analyze - // the parent StackFrameContext's call site in a similar manner. - if (Blk == &Cfg.getExit()) - return false; - - for (const auto &Succ : Blk->succs()) { - if (const CFGBlock *SuccBlk = Succ.getReachableBlock()) { - if (!isImmediateSinkBlock(SuccBlk) && !Visited.count(SuccBlk)) { - // If the block has reachable child blocks that aren't no-return, - // add them to the worklist. - DFSWorkList.push_back(SuccBlk); - } - } - } - } - - // Nothing reached the exit. It can only mean one thing: there's no return. - return true; -} - static BugReport * FindReportInEquivalenceClass(BugReportEquivClass& EQ, SmallVectorImpl &bugReports) { @@ -2851,8 +2767,9 @@ FindReportInEquivalenceClass(BugReportEquivClass& EQ, // to being post-dominated by a sink. This works better when the analysis // is incomplete and we have never reached the no-return function call(s) // that we'd inevitably bump into on this path. - if (isInevitablySinking(errorNode)) - continue; + if (const CFGBlock *ErrorB = errorNode->getCFGBlock()) + if (ErrorB->isInevitablySinking()) + continue; // At this point we know that 'N' is not a sink and it has at least one // successor. Use a DFS worklist to find a non-sink end-of-path node. diff --git a/clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp b/clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp index 8c17a36..43347ed 100644 --- a/clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp +++ b/clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp @@ -1710,18 +1710,6 @@ public: }; } // end of anonymous namespace -static CFGBlock *GetRelevantBlock(const ExplodedNode *Node) { - if (auto SP = Node->getLocationAs()) { - const Stmt *S = SP->getStmt(); - assert(S); - - return const_cast(Node->getLocationContext() - ->getAnalysisDeclContext()->getCFGStmtMap()->getBlock(S)); - } - - return nullptr; -} - static std::shared_ptr constructDebugPieceForTrackedCondition(const Expr *Cond, const ExplodedNode *N, @@ -1742,24 +1730,60 @@ constructDebugPieceForTrackedCondition(const Expr *Cond, (Twine() + "Tracking condition '" + ConditionText + "'").str()); } +static bool isAssertlikeBlock(const CFGBlock *B, ASTContext &Context) { + if (B->succ_size() != 2) + return false; + + const CFGBlock *Then = B->succ_begin()->getReachableBlock(); + const CFGBlock *Else = (B->succ_begin() + 1)->getReachableBlock(); + + if (!Then || !Else) + return false; + + if (Then->isInevitablySinking() != Else->isInevitablySinking()) + return true; + + // For the following condition the following CFG would be built: + // + // -------------> + // / \ + // [B1] -> [B2] -> [B3] -> [sink] + // assert(A && B || C); \ \ + // -----------> [go on with the execution] + // + // It so happens that CFGBlock::getTerminatorCondition returns 'A' for block + // B1, 'A && B' for B2, and 'A && B || C' for B3. Let's check whether we + // reached the end of the condition! + if (const Stmt *ElseCond = Else->getTerminatorCondition()) + if (isa(ElseCond)) { + assert(cast(ElseCond)->isLogicalOp()); + return isAssertlikeBlock(Else, Context); + } + + return false; +} + PathDiagnosticPieceRef TrackControlDependencyCondBRVisitor::VisitNode( const ExplodedNode *N, BugReporterContext &BRC, BugReport &BR) { // We can only reason about control dependencies within the same stack frame. if (Origin->getStackFrame() != N->getStackFrame()) return nullptr; - CFGBlock *NB = GetRelevantBlock(N); + CFGBlock *NB = const_cast(N->getCFGBlock()); // Skip if we already inspected this block. if (!VisitedBlocks.insert(NB).second) return nullptr; - CFGBlock *OriginB = GetRelevantBlock(Origin); + CFGBlock *OriginB = const_cast(Origin->getCFGBlock()); // TODO: Cache CFGBlocks for each ExplodedNode. if (!OriginB || !NB) return nullptr; + if (isAssertlikeBlock(NB, BRC.getASTContext())) + return nullptr; + if (ControlDeps.isControlDependent(OriginB, NB)) { if (const Expr *Condition = NB->getLastCondition()) { // Keeping track of the already tracked conditions on a visitor level diff --git a/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp index 15e8d62..03e813e 100644 --- a/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp @@ -16,6 +16,7 @@ #include "clang/AST/ExprObjC.h" #include "clang/AST/ParentMap.h" #include "clang/AST/Stmt.h" +#include "clang/Analysis/CFGStmtMap.h" #include "clang/Analysis/ProgramPoint.h" #include "clang/Analysis/Support/BumpVector.h" #include "clang/Basic/LLVM.h" @@ -292,6 +293,21 @@ bool ExplodedNode::isTrivial() const { getFirstPred()->succ_size() == 1; } +const CFGBlock *ExplodedNode::getCFGBlock() const { + ProgramPoint P = getLocation(); + if (auto BEP = P.getAs()) + return BEP->getBlock(); + + // Find the node's current statement in the CFG. + if (const Stmt *S = PathDiagnosticLocation::getStmt(this)) + return getLocationContext() + ->getAnalysisDeclContext() + ->getCFGStmtMap() + ->getBlock(S); + + return nullptr; +} + ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L, ProgramStateRef State, bool IsSink, diff --git a/clang/test/Analysis/track-control-dependency-conditions.cpp b/clang/test/Analysis/track-control-dependency-conditions.cpp index 35769f2..b914486 100644 --- a/clang/test/Analysis/track-control-dependency-conditions.cpp +++ b/clang/test/Analysis/track-control-dependency-conditions.cpp @@ -458,3 +458,242 @@ void f(int flag) { } } // end of namespace unimportant_write_before_collapse_point + +namespace dont_track_assertlike_conditions { + +extern void __assert_fail(__const char *__assertion, __const char *__file, + unsigned int __line, __const char *__function) + __attribute__((__noreturn__)); +#define assert(expr) \ + ((expr) ? (void)(0) : __assert_fail(#expr, __FILE__, __LINE__, __func__)) + +int getInt(); + +int cond1; + +void bar() { + cond1 = getInt(); +} + +void f(int flag) { + int *x = 0; // expected-note{{'x' initialized to a null pointer value}} + + flag = getInt(); + + bar(); + assert(cond1); // expected-note{{Assuming 'cond1' is not equal to 0}} + // expected-note@-1{{'?' condition is true}} + + if (flag) // expected-note{{'flag' is not equal to 0}} + // expected-note@-1{{Taking true branch}} + // debug-note@-2{{Tracking condition 'flag'}} + *x = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} + +#undef assert +} // end of namespace dont_track_assertlike_conditions + +namespace dont_track_assertlike_and_conditions { + +extern void __assert_fail(__const char *__assertion, __const char *__file, + unsigned int __line, __const char *__function) + __attribute__((__noreturn__)); +#define assert(expr) \ + ((expr) ? (void)(0) : __assert_fail(#expr, __FILE__, __LINE__, __func__)) + +int getInt(); + +int cond1; +int cond2; + +void bar() { + cond1 = getInt(); + cond2 = getInt(); +} + +void f(int flag) { + int *x = 0; // expected-note{{'x' initialized to a null pointer value}} + + flag = getInt(); + + bar(); + assert(cond1 && cond2); + // expected-note@-1{{Assuming 'cond1' is not equal to 0}} + // expected-note@-2{{Assuming 'cond2' is not equal to 0}} + // expected-note@-3{{'?' condition is true}} + // expected-note@-4{{Left side of '&&' is true}} + + if (flag) // expected-note{{'flag' is not equal to 0}} + // expected-note@-1{{Taking true branch}} + // debug-note@-2{{Tracking condition 'flag'}} + *x = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} + +#undef assert +} // end of namespace dont_track_assertlike_and_conditions + +namespace dont_track_assertlike_or_conditions { + +extern void __assert_fail(__const char *__assertion, __const char *__file, + unsigned int __line, __const char *__function) + __attribute__((__noreturn__)); +#define assert(expr) \ + ((expr) ? (void)(0) : __assert_fail(#expr, __FILE__, __LINE__, __func__)) + +int getInt(); + +int cond1; +int cond2; + +void bar() { + cond1 = getInt(); + cond2 = getInt(); +} + +void f(int flag) { + int *x = 0; // expected-note{{'x' initialized to a null pointer value}} + + flag = getInt(); + + bar(); + assert(cond1 || cond2); + // expected-note@-1{{Assuming 'cond1' is not equal to 0}} + // expected-note@-2{{Left side of '||' is true}} + + if (flag) // expected-note{{'flag' is not equal to 0}} + // expected-note@-1{{Taking true branch}} + // debug-note@-2{{Tracking condition 'flag'}} + *x = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} + +#undef assert +} // end of namespace dont_track_assertlike_or_conditions + +namespace dont_track_assert2like_conditions { + +extern void __assert_fail(__const char *__assertion, __const char *__file, + unsigned int __line, __const char *__function) + __attribute__((__noreturn__)); +#define assert(expr) \ + do { \ + if (!(expr)) \ + __assert_fail(#expr, __FILE__, __LINE__, __func__); \ + } while (0) + +int getInt(); + +int cond1; + +void bar() { + cond1 = getInt(); +} + +void f(int flag) { + int *x = 0; // expected-note{{'x' initialized to a null pointer value}} + + flag = getInt(); + + bar(); + assert(cond1); // expected-note{{Assuming 'cond1' is not equal to 0}} + // expected-note@-1{{Taking false branch}} + // expected-note@-2{{Loop condition is false. Exiting loop}} + + if (flag) // expected-note{{'flag' is not equal to 0}} + // expected-note@-1{{Taking true branch}} + // debug-note@-2{{Tracking condition 'flag'}} + *x = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} + +#undef assert +} // end of namespace dont_track_assert2like_conditions + +namespace dont_track_assert2like_and_conditions { + +extern void __assert_fail(__const char *__assertion, __const char *__file, + unsigned int __line, __const char *__function) + __attribute__((__noreturn__)); +#define assert(expr) \ + do { \ + if (!(expr)) \ + __assert_fail(#expr, __FILE__, __LINE__, __func__); \ + } while (0) + +int getInt(); + +int cond1; +int cond2; + +void bar() { + cond1 = getInt(); + cond2 = getInt(); +} + +void f(int flag) { + int *x = 0; // expected-note{{'x' initialized to a null pointer value}} + + flag = getInt(); + + bar(); + assert(cond1 && cond2); + // expected-note@-1{{Assuming 'cond1' is not equal to 0}} + // expected-note@-2{{Left side of '&&' is true}} + // expected-note@-3{{Assuming the condition is false}} + // expected-note@-4{{Taking false branch}} + // expected-note@-5{{Loop condition is false. Exiting loop}} + + if (flag) // expected-note{{'flag' is not equal to 0}} + // expected-note@-1{{Taking true branch}} + // debug-note@-2{{Tracking condition 'flag'}} + *x = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} + +#undef assert +} // end of namespace dont_track_assert2like_and_conditions + +namespace dont_track_assert2like_or_conditions { + +extern void __assert_fail(__const char *__assertion, __const char *__file, + unsigned int __line, __const char *__function) + __attribute__((__noreturn__)); +#define assert(expr) \ + do { \ + if (!(expr)) \ + __assert_fail(#expr, __FILE__, __LINE__, __func__); \ + } while (0) + +int getInt(); + +int cond1; +int cond2; + +void bar() { + cond1 = getInt(); + cond2 = getInt(); +} + +void f(int flag) { + int *x = 0; // expected-note{{'x' initialized to a null pointer value}} + + flag = getInt(); + + bar(); + assert(cond1 || cond2); + // expected-note@-1{{Assuming 'cond1' is not equal to 0}} + // expected-note@-2{{Left side of '||' is true}} + // expected-note@-3{{Taking false branch}} + // expected-note@-4{{Loop condition is false. Exiting loop}} + + if (flag) // expected-note{{'flag' is not equal to 0}} + // expected-note@-1{{Taking true branch}} + // debug-note@-2{{Tracking condition 'flag'}} + *x = 5; // expected-warning{{Dereference of null pointer}} + // expected-note@-1{{Dereference of null pointer}} +} + +#undef assert +} // end of namespace dont_track_assert2like_or_conditions -- 2.7.4