UndefBranchChecker.cpp revision f236b6503a4dbc44c1fccb8756bd57c9d0efdf05
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//=== UndefBranchChecker.cpp -----------------------------------*- C++ -*--===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file defines UndefBranchChecker, which checks for undefined branch 11e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch// condition. 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 13868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)//===----------------------------------------------------------------------===// 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "ClangSACheckers.h" 16b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)#include "clang/StaticAnalyzer/Core/Checker.h" 17cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)#include "clang/StaticAnalyzer/Core/CheckerManager.h" 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 19e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 20e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch 21c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdochusing namespace clang; 22c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdochusing namespace ento; 23c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch 24c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdochnamespace { 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class UndefBranchChecker : public Checker<check::BranchCondition> { 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mutable llvm::OwningPtr<BuiltinBug> BT; 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 29c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) struct FindUndefExpr { 30c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const ProgramState *St; 31c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 32c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) FindUndefExpr(const ProgramState *S) : St(S) {} 33a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 34a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch const Expr *FindExpr(const Expr *Ex) { 35a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch if (!MatchesCriteria(Ex)) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 38a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch for (Stmt::const_child_iterator I = Ex->child_begin(), 39a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch E = Ex->child_end();I!=E;++I) 40a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch if (const Expr *ExI = dyn_cast_or_null<Expr>(*I)) { 41a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch const Expr *E2 = FindExpr(ExI); 42a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch if (E2) return E2; 43a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch } 44a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 45a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch return Ex; 46a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch } 47a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 48a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch bool MatchesCriteria(const Expr *Ex) { return St->getSVal(Ex).isUndef(); } 49a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch }; 50a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 51a02191e04bc25c4935f804f2c080ae28663d096dBen Murdochpublic: 52a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch void checkBranchCondition(const Stmt *Condition, CheckerContext &Ctx) const; 53a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch}; 54a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 55a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch} 56a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 57a02191e04bc25c4935f804f2c080ae28663d096dBen Murdochvoid UndefBranchChecker::checkBranchCondition(const Stmt *Condition, 58a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch CheckerContext &Ctx) const { 59a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch SVal X = Ctx.getState()->getSVal(Condition); 60a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch if (X.isUndef()) { 61a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // Generate a sink node, which implicitly marks both outgoing branches as 62a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // infeasible. 63a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch ExplodedNode *N = Ctx.generateSink(); 64a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch if (N) { 65a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch if (!BT) 66a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch BT.reset( 67a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch new BuiltinBug("Branch condition evaluates to a garbage value")); 68a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 69a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // What's going on here: we want to highlight the subexpression of the 70a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // condition that is the most likely source of the "uninitialized 71a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // branch condition." We do a recursive walk of the condition's 72a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // subexpressions and roughly look for the most nested subexpression 73a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // that binds to Undefined. We then highlight that expression's range. 74a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 75a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // Get the predecessor node and check if is a PostStmt with the Stmt 76a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // being the terminator condition. We want to inspect the state 77a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // of that node instead because it will contain main information about 78a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // the subexpressions. 79a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 80a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // Note: any predecessor will do. They should have identical state, 81a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // since all the BlockEdge did was act as an error sink since the value 82a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch // had to already be undefined. 83a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch assert (!N->pred_empty()); 84a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch const Expr *Ex = cast<Expr>(Condition); 85a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch ExplodedNode *PrevN = *N->pred_begin(); 86a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch ProgramPoint P = PrevN->getLocation(); 87a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch const ProgramState *St = N->getState(); 88a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 89a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch if (PostStmt *PS = dyn_cast<PostStmt>(&P)) 90a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch if (PS->getStmt() == Ex) 91a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch St = PrevN->getState(); 92a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch 93a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch FindUndefExpr FindIt(St); 94a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch Ex = FindIt.FindExpr(Ex); 95558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch 96558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch // Emit the bug report. 97558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch BugReport *R = new BugReport(*BT, BT->getDescription(), N); 98558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch R->addVisitor(bugreporter::getTrackNullOrUndefValueVisitor(N, Ex)); 99558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch R->addRange(Ex->getSourceRange()); 100eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 101eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch Ctx.EmitReport(R); 102cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 103e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch } 104c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch} 105c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch 106cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)void ento::registerUndefBranchChecker(CheckerManager &mgr) { 107c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch mgr.registerChecker<UndefBranchChecker>(); 108c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch} 109c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch