From dd986cc9989f665370cef0917ba8ba3b4871e3e6 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Thu, 7 May 2009 00:45:33 +0000 Subject: [PATCH] Add preliminary support for enhancing null-pointer dereference diagnostics. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@71135 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Analysis/PathSensitive/BugReporter.h | 21 ++- lib/Analysis/BugReporter.cpp | 100 ++++++----- lib/Analysis/GRExprEngineInternalChecks.cpp | 165 +++++++++++++++++- 3 files changed, 224 insertions(+), 62 deletions(-) diff --git a/include/clang/Analysis/PathSensitive/BugReporter.h b/include/clang/Analysis/PathSensitive/BugReporter.h index 99cbfd844b..90fd9d8ebf 100644 --- a/include/clang/Analysis/PathSensitive/BugReporter.h +++ b/include/clang/Analysis/PathSensitive/BugReporter.h @@ -50,7 +50,7 @@ public: virtual ~BugReporterVisitor(); virtual PathDiagnosticPiece* VisitNode(const ExplodedNode* N, const ExplodedNode* PrevN, - BugReporterContext& BR) = 0; + BugReporterContext& BRC) = 0; virtual bool isOwnedByReporterContext() { return true; } }; @@ -115,7 +115,7 @@ public: } // FIXME: Perhaps move this into a subclass. - virtual PathDiagnosticPiece* getEndPath(BugReporterContext& BR, + virtual PathDiagnosticPiece* getEndPath(BugReporterContext& BRC, const ExplodedNode* N); /// getLocation - Return the "definitive" location of the reported bug. @@ -130,15 +130,10 @@ public: virtual PathDiagnosticPiece* VisitNode(const ExplodedNode* N, const ExplodedNode* PrevN, - BugReporterContext& BR); - - /* - virtual PathDiagnosticPiece* VisitNode(const ExplodedNode* N, - const ExplodedNode* PrevN, - const ExplodedGraph& G, - BugReporterContext& BR, - NodeResolver& NR); - */ + BugReporterContext& BR); + + virtual void registerInitialVisitors(BugReporterContext& BRC, + const ExplodedNode* N) {} }; //===----------------------------------------------------------------------===// @@ -424,6 +419,10 @@ public: return BR.getStateManager(); } + ValueManager& getValueManager() { + return getStateManager().getValueManager(); + } + ASTContext& getASTContext() { return BR.getContext(); } diff --git a/lib/Analysis/BugReporter.cpp b/lib/Analysis/BugReporter.cpp index 36dc6b75ee..23de85709a 100644 --- a/lib/Analysis/BugReporter.cpp +++ b/lib/Analysis/BugReporter.cpp @@ -710,10 +710,12 @@ static void GenerateMinimalPathDiagnostic(PathDiagnostic& PD, } } - for (BugReporterContext::visitor_iterator I = PDB.visitor_begin(), - E = PDB.visitor_end(); I!=E; ++I) { - if (PathDiagnosticPiece* p = (*I)->VisitNode(N, NextNode, PDB)) - PD.push_front(p); + if (NextNode) { + for (BugReporterContext::visitor_iterator I = PDB.visitor_begin(), + E = PDB.visitor_end(); I!=E; ++I) { + if (PathDiagnosticPiece* p = (*I)->VisitNode(N, NextNode, PDB)) + PD.push_front(p); + } } if (const PostStmt* PS = dyn_cast(&P)) { @@ -1052,53 +1054,58 @@ static void GenerateExtensivePathDiagnostic(PathDiagnostic& PD, NextNode = GetPredecessorNode(N); ProgramPoint P = N->getLocation(); - // Block edges. - if (const BlockEdge *BE = dyn_cast(&P)) { - const CFGBlock &Blk = *BE->getSrc(); - const Stmt *Term = Blk.getTerminator(); - - if (Term) - EB.addContext(Term); - - // Are we jumping to the head of a loop? Add a special diagnostic. - if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) { - - PathDiagnosticLocation L(Loop, PDB.getSourceManager()); - PathDiagnosticEventPiece *p = - new PathDiagnosticEventPiece(L, - "Looping back to the head of the loop"); + do { + // Block edges. + if (const BlockEdge *BE = dyn_cast(&P)) { + const CFGBlock &Blk = *BE->getSrc(); + const Stmt *Term = Blk.getTerminator(); - EB.addEdge(p->getLocation(), true); - PD.push_front(p); - - if (!Term) { - const CompoundStmt *CS = NULL; - if (const ForStmt *FS = dyn_cast(Loop)) - CS = dyn_cast(FS->getBody()); - else if (const WhileStmt *WS = dyn_cast(Loop)) - CS = dyn_cast(WS->getBody()); - - if (CS) - EB.rawAddEdge(PathDiagnosticLocation(CS->getRBracLoc(), - PDB.getSourceManager())); + if (Term) + EB.addContext(Term); + + // Are we jumping to the head of a loop? Add a special diagnostic. + if (const Stmt *Loop = BE->getSrc()->getLoopTarget()) { + + PathDiagnosticLocation L(Loop, PDB.getSourceManager()); + PathDiagnosticEventPiece *p = + new PathDiagnosticEventPiece(L, + "Looping back to the head of the loop"); + + EB.addEdge(p->getLocation(), true); + PD.push_front(p); + + if (!Term) { + const CompoundStmt *CS = NULL; + if (const ForStmt *FS = dyn_cast(Loop)) + CS = dyn_cast(FS->getBody()); + else if (const WhileStmt *WS = dyn_cast(Loop)) + CS = dyn_cast(WS->getBody()); + + if (CS) + EB.rawAddEdge(PathDiagnosticLocation(CS->getRBracLoc(), + PDB.getSourceManager())); + } } + + break; } - - continue; - } - if (const BlockEntrance *BE = dyn_cast(&P)) { - if (const Stmt* S = BE->getFirstStmt()) { - if (IsControlFlowExpr(S)) { - // Add the proper context for '&&', '||', and '?'. - EB.addContext(S); - } - else - EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); - } + if (const BlockEntrance *BE = dyn_cast(&P)) { + if (const Stmt* S = BE->getFirstStmt()) { + if (IsControlFlowExpr(S)) { + // Add the proper context for '&&', '||', and '?'. + EB.addContext(S); + } + else + EB.addExtendedContext(PDB.getEnclosingStmtLocation(S).asStmt()); + } + break; + } + } while (0); + + if (!NextNode) continue; - } for (BugReporterContext::visitor_iterator I = PDB.visitor_begin(), E = PDB.visitor_end(); I!=E; ++I) { @@ -1506,7 +1513,8 @@ void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD, PD.push_back(Piece); else return; - + + R->registerInitialVisitors(PDB, N); switch (PDB.getGenerationScheme()) { case PathDiagnosticClient::Extensive: diff --git a/lib/Analysis/GRExprEngineInternalChecks.cpp b/lib/Analysis/GRExprEngineInternalChecks.cpp index a40eff8fc4..541282da3e 100644 --- a/lib/Analysis/GRExprEngineInternalChecks.cpp +++ b/lib/Analysis/GRExprEngineInternalChecks.cpp @@ -14,6 +14,7 @@ #include "clang/Analysis/PathSensitive/BugReporter.h" #include "clang/Analysis/PathSensitive/GRExprEngine.h" +#include "clang/Analysis/PathDiagnostic.h" #include "clang/Basic/SourceManager.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/raw_ostream.h" @@ -34,11 +35,29 @@ ExplodedNode* GetNode(GRExprEngine::undef_arg_iterator I) { return I->first; } +//===----------------------------------------------------------------------===// +// Forward declarations for bug reporter visitors. +//===----------------------------------------------------------------------===// + +static void registerTrackNullValue(BugReporterContext& BRC, + const ExplodedNode* N); + //===----------------------------------------------------------------------===// // Bug Descriptions. //===----------------------------------------------------------------------===// namespace { + +class VISIBILITY_HIDDEN BuiltinBugReport : public BugReport { +public: + BuiltinBugReport(BugType& bt, const char* desc, + const ExplodedNode *n) + : BugReport(bt, desc, n) {} + + void registerInitialVisitors(BugReporterContext& BRC, + const ExplodedNode* N); +}; + class VISIBILITY_HIDDEN BuiltinBug : public BugType { GRExprEngine &Eng; protected: @@ -54,13 +73,25 @@ public: void FlushReports(BugReporter& BR) { FlushReportsImpl(BR, Eng); } - template - void Emit(BugReporter& BR, ITER I, ITER E) { - for (; I != E; ++I) BR.EmitReport(new BugReport(*this, desc.c_str(), - GetNode(I))); - } + virtual void registerInitialVisitors(BugReporterContext& BRC, + const ExplodedNode* N, + BuiltinBugReport *R) {} + + template void Emit(BugReporter& BR, ITER I, ITER E); }; + +template +void BuiltinBug::Emit(BugReporter& BR, ITER I, ITER E) { + for (; I != E; ++I) BR.EmitReport(new BuiltinBugReport(*this, desc.c_str(), + GetNode(I))); +} + +void BuiltinBugReport::registerInitialVisitors(BugReporterContext& BRC, + const ExplodedNode* N) { + static_cast(getBugType()).registerInitialVisitors(BRC, N, this); +} + class VISIBILITY_HIDDEN NullDeref : public BuiltinBug { public: NullDeref(GRExprEngine* eng) @@ -69,6 +100,12 @@ public: void FlushReportsImpl(BugReporter& BR, GRExprEngine& Eng) { Emit(BR, Eng.null_derefs_begin(), Eng.null_derefs_end()); } + + void registerInitialVisitors(BugReporterContext& BRC, + const ExplodedNode* N, + BuiltinBugReport *R) { + registerTrackNullValue(BRC, N); + } }; class VISIBILITY_HIDDEN NilReceiverStructRet : public BugType { @@ -483,6 +520,124 @@ public: }; } // end anonymous namespace +//===----------------------------------------------------------------------===// +// Definitions for bug reporter visitors. +//===----------------------------------------------------------------------===// + +namespace { +class VISIBILITY_HIDDEN TrackConstraintBRVisitor : public BugReporterVisitor { + SVal Constraint; + const bool Assumption; + bool isSatisfied; +public: + TrackConstraintBRVisitor(SVal constraint, bool assumption) + : Constraint(constraint), Assumption(assumption), isSatisfied(false) {} + + PathDiagnosticPiece* VisitNode(const ExplodedNode* N, + const ExplodedNode* PrevN, + BugReporterContext& BRC) { + if (isSatisfied) + return NULL; + + // Check if in the previous state it was feasible for this constraint + // to *not* be true. + + GRStateManager &StateMgr = BRC.getStateManager(); + bool isFeasible = false; + if (StateMgr.Assume(PrevN->getState(), Constraint, !Assumption, + isFeasible)) { + assert(isFeasible); // Eventually we don't need 'isFeasible'. + + isSatisfied = true; + + // As a sanity check, make sure that the negation of the constraint + // was infeasible in the current state. If it is feasible, we somehow + // missed the transition point. + isFeasible = false; + if (StateMgr.Assume(N->getState(), Constraint, !Assumption, + isFeasible)) { + assert(isFeasible); + return NULL; + } + + // We found the transition point for the constraint. We now need to + // pretty-print the constraint. (work-in-progress) + std::string sbuf; + llvm::raw_string_ostream os(sbuf); + + if (isa(Constraint)) { + os << "Assuming pointer value is "; + os << (Assumption ? "non-NULL" : "NULL"); + } + + if (os.str().empty()) + return NULL; + + // FIXME: Refactor this into BugReporterContext. + Stmt *S = 0; + ProgramPoint P = N->getLocation(); + + if (BlockEdge *BE = dyn_cast(&P)) { + CFGBlock *BSrc = BE->getSrc(); + S = BSrc->getTerminatorCondition(); + } + else if (PostStmt *PS = dyn_cast(&P)) { + S = PS->getStmt(); + } + + if (!S) + return NULL; + + // Construct a new PathDiagnosticPiece. + PathDiagnosticLocation L(S, BRC.getSourceManager()); + return new PathDiagnosticEventPiece(L, os.str()); + } + + return NULL; + } +}; +} // end anonymous namespace + +static void registerTrackConstraint(BugReporterContext& BRC, SVal Constraint, + bool Assumption) { + BRC.addVisitor(new TrackConstraintBRVisitor(Constraint, Assumption)); +} + +static void registerTrackNullValue(BugReporterContext& BRC, + const ExplodedNode* N) { + + ProgramPoint P = N->getLocation(); + PostStmt *PS = dyn_cast(&P); + + if (!PS) + return; + + Stmt *S = PS->getStmt(); + + if (ArraySubscriptExpr *AE = dyn_cast(S)) { + S = AE->getBase(); + } + + SVal V = BRC.getStateManager().GetSValAsScalarOrLoc(N->getState(), S); + + // Uncomment this to find cases where we aren't properly getting the + // base value that was dereferenced. + // assert(!V.isUnknownOrUndef()); + + // For now just track when a symbolic value became null. + if (loc::MemRegionVal *L = dyn_cast(&V)) { + const SubRegion *R = cast(L->getRegion()); + while (R && !isa(R)) { + R = dyn_cast(R->getSuperRegion()); + } + + if (R) { + assert(isa(R)); + registerTrackConstraint(BRC, loc::MemRegionVal(R), false); + } + } +} + //===----------------------------------------------------------------------===// // Check registration. //===----------------------------------------------------------------------===// -- 2.40.0