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 15cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis#include "ClangSACheckers.h" 1655fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 17ec8605f1d7ec846dbf51047bfd5c56d32d1ff91cArgyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/Checker.h" 18cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/CheckerManager.h" 19cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 200835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu 210835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xuusing namespace clang; 229ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenekusing namespace ento; 230835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu 240835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xunamespace { 250835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu 26ec8605f1d7ec846dbf51047bfd5c56d32d1ff91cArgyrios Kyrtzidisclass UndefBranchChecker : public Checker<check::BranchCondition> { 27651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines mutable std::unique_ptr<BuiltinBug> BT; 28f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 29ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnam struct FindUndefExpr { 308bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef St; 315eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek const LocationContext *LCtx; 32f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 338bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek FindUndefExpr(ProgramStateRef S, const LocationContext *L) 345eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek : St(S), LCtx(L) {} 35f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 369c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *FindExpr(const Expr *Ex) { 37f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu if (!MatchesCriteria(Ex)) 386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 39f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 4003509aea098772644bf4662dc1c88634818ceeccZhongxing Xu for (Stmt::const_child_iterator I = Ex->child_begin(), 4103509aea098772644bf4662dc1c88634818ceeccZhongxing Xu E = Ex->child_end();I!=E;++I) 429c378f705405d37f49795d5e915989de774fe11fTed Kremenek if (const Expr *ExI = dyn_cast_or_null<Expr>(*I)) { 439c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Expr *E2 = FindExpr(ExI); 44f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu if (E2) return E2; 45f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu } 46f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 47f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu return Ex; 48f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu } 49f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 505eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek bool MatchesCriteria(const Expr *Ex) { 515eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek return St->getSVal(Ex, LCtx).isUndef(); 525eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek } 53f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu }; 54f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 550835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xupublic: 56f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks void checkBranchCondition(const Stmt *Condition, CheckerContext &Ctx) const; 570835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu}; 580835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu 590835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu} 600835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu 61cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidisvoid UndefBranchChecker::checkBranchCondition(const Stmt *Condition, 62f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks CheckerContext &Ctx) const { 635eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek SVal X = Ctx.getState()->getSVal(Condition, Ctx.getLocationContext()); 640835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu if (X.isUndef()) { 65cd656cab3fa3dd4b0c974c6ae1c0e60880b18c22Anna Zaks // Generate a sink node, which implicitly marks both outgoing branches as 66cd656cab3fa3dd4b0c974c6ae1c0e60880b18c22Anna Zaks // infeasible. 67f236b6503a4dbc44c1fccb8756bd57c9d0efdf05Anna Zaks ExplodedNode *N = Ctx.generateSink(); 680835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu if (N) { 690835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu if (!BT) 70651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BT.reset(new BuiltinBug( 71651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines this, "Branch condition evaluates to a garbage value")); 72f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 73f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // What's going on here: we want to highlight the subexpression of the 74f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // condition that is the most likely source of the "uninitialized 75f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // branch condition." We do a recursive walk of the condition's 76f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // subexpressions and roughly look for the most nested subexpression 77f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // that binds to Undefined. We then highlight that expression's range. 78f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 79f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // Get the predecessor node and check if is a PostStmt with the Stmt 80f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // being the terminator condition. We want to inspect the state 81f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // of that node instead because it will contain main information about 82f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // the subexpressions. 83f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 84f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // Note: any predecessor will do. They should have identical state, 85f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // since all the BlockEdge did was act as an error sink since the value 86f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu // had to already be undefined. 879c81bc2763dc37f78f357be339a6376402aad537Anna Zaks assert (!N->pred_empty()); 889c81bc2763dc37f78f357be339a6376402aad537Anna Zaks const Expr *Ex = cast<Expr>(Condition); 89f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu ExplodedNode *PrevN = *N->pred_begin(); 90f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu ProgramPoint P = PrevN->getLocation(); 918bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef St = N->getState(); 92f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 937a95de68c093991047ed8d339479ccad51b88663David Blaikie if (Optional<PostStmt> PS = P.getAs<PostStmt>()) 94f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu if (PS->getStmt() == Ex) 95f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu St = PrevN->getState(); 96f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 975eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek FindUndefExpr FindIt(St, Ctx.getLocationContext()); 98f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu Ex = FindIt.FindExpr(Ex); 99616cf051d45b9e5294da36aaa40b09d79a9eddc4Ted Kremenek 100616cf051d45b9e5294da36aaa40b09d79a9eddc4Ted Kremenek // Emit the bug report. 10150bbc165b063155cc23c360deb7b865502e068e2Anna Zaks BugReport *R = new BugReport(*BT, BT->getDescription(), N); 102a1f81bb0e55749a1414b1b5124bb83b9052ff2acJordan Rose bugreporter::trackNullOrUndefValue(N, Ex, *R); 103f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu R->addRange(Ex->getSourceRange()); 104f155dbf901b77f0faa90a48670c0bdae7fbdea2dZhongxing Xu 105785950e59424dca7ce0081bebf13c0acd2c4fff6Jordan Rose Ctx.emitReport(R); 1060835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu } 1070835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu } 1080835e4cccfef3ea5346962722b79484f6b3ca602Zhongxing Xu} 109cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis 110cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidisvoid ento::registerUndefBranchChecker(CheckerManager &mgr) { 111cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis mgr.registerChecker<UndefBranchChecker>(); 112cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis} 113