UndefBranchChecker.cpp revision 6bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89
1b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org//=== UndefBranchChecker.cpp -----------------------------------*- C++ -*--===// 2b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org// 3b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org// The LLVM Compiler Infrastructure 4b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org// 5b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org// This file is distributed under the University of Illinois Open Source 6b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org// License. See LICENSE.TXT for details. 7b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org// 8b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org//===----------------------------------------------------------------------===// 9b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org// 10b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org// This file defines UndefBranchChecker, which checks for undefined branch 11b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org// condition. 12b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org// 13b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org//===----------------------------------------------------------------------===// 14b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 15b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org#include "ClangSACheckers.h" 16b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 17b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org#include "clang/StaticAnalyzer/Core/Checker.h" 18b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org#include "clang/StaticAnalyzer/Core/CheckerManager.h" 19b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 20b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 21b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.orgusing namespace clang; 22b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.orgusing namespace ento; 23b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 24b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.orgnamespace { 25b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 26b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.orgclass UndefBranchChecker : public Checker<check::BranchCondition> { 27b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org mutable std::unique_ptr<BuiltinBug> BT; 28b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 29b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org struct FindUndefExpr { 30b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ProgramStateRef St; 31b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org const LocationContext *LCtx; 32b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 33b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org FindUndefExpr(ProgramStateRef S, const LocationContext *L) 34b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org : St(S), LCtx(L) {} 35b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 36b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org const Expr *FindExpr(const Expr *Ex) { 37471ae72f18e7b23a96b245dbd508386fe139449cpbos@webrtc.org if (!MatchesCriteria(Ex)) 38b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org return nullptr; 39b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 40b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org for (Stmt::const_child_iterator I = Ex->child_begin(), 41b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org E = Ex->child_end();I!=E;++I) 42b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org if (const Expr *ExI = dyn_cast_or_null<Expr>(*I)) { 43b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org const Expr *E2 = FindExpr(ExI); 44b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org if (E2) return E2; 45b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 46b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 47b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org return Ex; 48b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 49b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 50ca7a9a2696d2f73f543241093c4faeb4c608678cpbos@webrtc.org bool MatchesCriteria(const Expr *Ex) { 51b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org return St->getSVal(Ex, LCtx).isUndef(); 52b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 53b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org }; 54b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 55b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.orgpublic: 56b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org void checkBranchCondition(const Stmt *Condition, CheckerContext &Ctx) const; 57b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org}; 58b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 59b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org} 60b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 61b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.orgvoid UndefBranchChecker::checkBranchCondition(const Stmt *Condition, 62b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org CheckerContext &Ctx) const { 63b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org SVal X = Ctx.getState()->getSVal(Condition, Ctx.getLocationContext()); 64b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org if (X.isUndef()) { 65b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Generate a sink node, which implicitly marks both outgoing branches as 66b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // infeasible. 67b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org ExplodedNode *N = Ctx.generateSink(); 68b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org if (N) { 69b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org if (!BT) 70b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org BT.reset(new BuiltinBug( 71b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org this, "Branch condition evaluates to a garbage value")); 72b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 73b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // What's going on here: we want to highlight the subexpression of the 74b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // condition that is the most likely source of the "uninitialized 75b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // branch condition." We do a recursive walk of the condition's 76b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // subexpressions and roughly look for the most nested subexpression 77b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // that binds to Undefined. We then highlight that expression's range. 78b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 79b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Get the predecessor node and check if is a PostStmt with the Stmt 80b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // being the terminator condition. We want to inspect the state 81b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // of that node instead because it will contain main information about 82b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // the subexpressions. 83fec6b6e5999edec8c90efae54357f1aae6a4c7ddsolenberg@webrtc.org 84fec6b6e5999edec8c90efae54357f1aae6a4c7ddsolenberg@webrtc.org // Note: any predecessor will do. They should have identical state, 85fec6b6e5999edec8c90efae54357f1aae6a4c7ddsolenberg@webrtc.org // since all the BlockEdge did was act as an error sink since the value 86fec6b6e5999edec8c90efae54357f1aae6a4c7ddsolenberg@webrtc.org // had to already be undefined. 87fec6b6e5999edec8c90efae54357f1aae6a4c7ddsolenberg@webrtc.org assert (!N->pred_empty()); 88fec6b6e5999edec8c90efae54357f1aae6a4c7ddsolenberg@webrtc.org const Expr *Ex = cast<Expr>(Condition); 89fec6b6e5999edec8c90efae54357f1aae6a4c7ddsolenberg@webrtc.org ExplodedNode *PrevN = *N->pred_begin(); 90fec6b6e5999edec8c90efae54357f1aae6a4c7ddsolenberg@webrtc.org ProgramPoint P = PrevN->getLocation(); 91fec6b6e5999edec8c90efae54357f1aae6a4c7ddsolenberg@webrtc.org ProgramStateRef St = N->getState(); 92b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 93b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org if (Optional<PostStmt> PS = P.getAs<PostStmt>()) 94b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org if (PS->getStmt() == Ex) 95b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org St = PrevN->getState(); 96b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 97b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org FindUndefExpr FindIt(St, Ctx.getLocationContext()); 98b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org Ex = FindIt.FindExpr(Ex); 99b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org 100b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org // Emit the bug report. 101b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org BugReport *R = new BugReport(*BT, BT->getDescription(), N); 102b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org bugreporter::trackNullOrUndefValue(N, Ex, *R); 103b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org R->addRange(Ex->getSourceRange()); 1043b89e10f31160da35b408fd00cb8f89d2b08862dpbos@webrtc.org 105b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org Ctx.emitReport(R); 106b015cbede88899f67a53fbbe581b02ce8e32794andrew@webrtc.org } 107 } 108} 109 110void ento::registerUndefBranchChecker(CheckerManager &mgr) { 111 mgr.registerChecker<UndefBranchChecker>(); 112} 113