UndefBranchChecker.cpp revision ba5fb5a955c896815c439289fc51c03cf0635129
10835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu//=== UndefBranchChecker.cpp -----------------------------------*- C++ -*--===// 20835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu// 30835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu// The LLVM Compiler Infrastructure 40835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu// 50835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu// This file is distributed under the University of Illinois Open Source 60835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu// License. See LICENSE.TXT for details. 70835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu// 80835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu//===----------------------------------------------------------------------===// 90835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu// 100835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu// This file defines UndefBranchChecker, which checks for undefined branch 110835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu// condition. 120835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu// 130835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu//===----------------------------------------------------------------------===// 140835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu 150835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu#include "GRExprEngineInternalChecks.h" 160835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu#include "clang/Analysis/PathSensitive/Checker.h" 170835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu 180835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xuusing namespace clang; 190835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu 200835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xunamespace { 210835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu 22ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnamclass UndefBranchChecker : public Checker { 230835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu BuiltinBug *BT; 24f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 25ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnam struct FindUndefExpr { 26f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu GRStateManager& VM; 27f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu const GRState* St; 28f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 29f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu FindUndefExpr(GRStateManager& V, const GRState* S) : VM(V), St(S) {} 30f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 31f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu Expr* FindExpr(Expr* Ex) { 32f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu if (!MatchesCriteria(Ex)) 33f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu return 0; 34f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 35f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu for (Stmt::child_iterator I=Ex->child_begin(), E=Ex->child_end();I!=E;++I) 36f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu if (Expr* ExI = dyn_cast_or_null<Expr>(*I)) { 37f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu Expr* E2 = FindExpr(ExI); 38f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu if (E2) return E2; 39f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu } 40f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 41f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu return Ex; 42f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu } 43f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 44f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu bool MatchesCriteria(Expr* Ex) { return St->getSVal(Ex).isUndef(); } 45f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu }; 46f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 470835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xupublic: 480835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu UndefBranchChecker() : BT(0) {} 490835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu static void *getTag(); 500835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu void VisitBranchCondition(GRBranchNodeBuilder &Builder, GRExprEngine &Eng, 510835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu Stmt *Condition, void *tag); 520835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu}; 530835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu 540835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu} 550835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu 560835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xuvoid clang::RegisterUndefBranchChecker(GRExprEngine &Eng) { 570835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu Eng.registerCheck(new UndefBranchChecker()); 580835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu} 590835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu 600835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xuvoid *UndefBranchChecker::getTag() { 610835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu static int x; 620835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu return &x; 630835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu} 640835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu 650835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xuvoid UndefBranchChecker::VisitBranchCondition(GRBranchNodeBuilder &Builder, 660835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu GRExprEngine &Eng, 670835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu Stmt *Condition, void *tag) { 680835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu const GRState *state = Builder.getState(); 690835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu SVal X = state->getSVal(Condition); 700835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu if (X.isUndef()) { 710835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu ExplodedNode *N = Builder.generateNode(state, true); 720835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu if (N) { 730835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu N->markAsSink(); 740835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu if (!BT) 75998c133a3b1cd0c34c52907f3ec2798e0dde7e0eTed Kremenek BT = new BuiltinBug("Branch condition evaluates to a garbage value"); 76f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 77f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // What's going on here: we want to highlight the subexpression of the 78f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // condition that is the most likely source of the "uninitialized 79f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // branch condition." We do a recursive walk of the condition's 80f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // subexpressions and roughly look for the most nested subexpression 81f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // that binds to Undefined. We then highlight that expression's range. 82f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu BlockEdge B = cast<BlockEdge>(N->getLocation()); 83f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu Expr* Ex = cast<Expr>(B.getSrc()->getTerminatorCondition()); 84f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu assert (Ex && "Block must have a terminator."); 85f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 86f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // Get the predecessor node and check if is a PostStmt with the Stmt 87f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // being the terminator condition. We want to inspect the state 88f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // of that node instead because it will contain main information about 89f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // the subexpressions. 90f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu assert (!N->pred_empty()); 91f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 92f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // Note: any predecessor will do. They should have identical state, 93f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // since all the BlockEdge did was act as an error sink since the value 94f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // had to already be undefined. 95f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu ExplodedNode *PrevN = *N->pred_begin(); 96f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu ProgramPoint P = PrevN->getLocation(); 97f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu const GRState* St = N->getState(); 98f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 99f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu if (PostStmt* PS = dyn_cast<PostStmt>(&P)) 100f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu if (PS->getStmt() == Ex) 101f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu St = PrevN->getState(); 102f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 103f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu FindUndefExpr FindIt(Eng.getStateManager(), St); 104f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu Ex = FindIt.FindExpr(Ex); 105616cf051d45b9e5294da36aaa40b09d79a9eddc4Ted Kremenek 106616cf051d45b9e5294da36aaa40b09d79a9eddc4Ted Kremenek // Emit the bug report. 107616cf051d45b9e5294da36aaa40b09d79a9eddc4Ted Kremenek EnhancedBugReport *R = new EnhancedBugReport(*BT, BT->getDescription(),N); 108616cf051d45b9e5294da36aaa40b09d79a9eddc4Ted Kremenek R->addVisitorCreator(bugreporter::registerTrackNullOrUndefValue, Ex); 109f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu R->addRange(Ex->getSourceRange()); 110f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 1110835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu Eng.getBugReporter().EmitReport(R); 1120835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu } 1130835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu 1140835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu Builder.markInfeasible(true); 1150835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu Builder.markInfeasible(false); 1160835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu } 1170835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu} 118