1b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes//== BoolAssignmentChecker.cpp - Boolean assignment checker -----*- C++ -*--==// 2b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes// 3b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes// The LLVM Compiler Infrastructure 4b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes// 5b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes// This file is distributed under the University of Illinois Open Source 6b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes// License. See LICENSE.TXT for details. 7b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes// 8b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes//===----------------------------------------------------------------------===// 9b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes// 10b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes// This defines BoolAssignmentChecker, a builtin check in ExprEngine that 11b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes// performs checks for assignment of non-Boolean values to Boolean variables. 12b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes// 13b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes//===----------------------------------------------------------------------===// 14b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 15b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes#include "ClangSACheckers.h" 16b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes#include "clang/StaticAnalyzer/Core/Checker.h" 17b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes#include "clang/StaticAnalyzer/Core/CheckerManager.h" 18b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 19b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 20b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 21b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostesusing namespace clang; 22b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostesusing namespace ento; 23b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 24b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostesnamespace { 25b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes class BoolAssignmentChecker : public Checker< check::Bind > { 26b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes mutable llvm::OwningPtr<BuiltinBug> BT; 27b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes void emitReport(ProgramStateRef state, CheckerContext &C) const; 28b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes public: 29b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes void checkBind(SVal loc, SVal val, const Stmt *S, CheckerContext &C) const; 30b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes }; 31b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes} // end anonymous namespace 32b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 33b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostesvoid BoolAssignmentChecker::emitReport(ProgramStateRef state, 34b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes CheckerContext &C) const { 35b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes if (ExplodedNode *N = C.addTransition(state)) { 36b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes if (!BT) 37b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes BT.reset(new BuiltinBug("Assignment of a non-Boolean value")); 38b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes C.EmitReport(new BugReport(*BT, BT->getDescription(), N)); 39b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes } 40b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes} 41b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 42b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostesstatic bool isBooleanType(QualType Ty) { 43b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes if (Ty->isBooleanType()) // C++ or C99 44b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes return true; 45b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 46b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes if (const TypedefType *TT = Ty->getAs<TypedefType>()) 47b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes return TT->getDecl()->getName() == "BOOL" || // Objective-C 48b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes TT->getDecl()->getName() == "_Bool" || // stdbool.h < C99 49b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes TT->getDecl()->getName() == "Boolean"; // MacTypes.h 50b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 51b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes return false; 52b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes} 53b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 54b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostesvoid BoolAssignmentChecker::checkBind(SVal loc, SVal val, const Stmt *S, 55b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes CheckerContext &C) const { 56b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 57b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // We are only interested in stores into Booleans. 58b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes const TypedValueRegion *TR = 59b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes dyn_cast_or_null<TypedValueRegion>(loc.getAsRegion()); 60b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 61b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes if (!TR) 62b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes return; 63b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 64b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes QualType valTy = TR->getValueType(); 65b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 66b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes if (!isBooleanType(valTy)) 67b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes return; 68b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 69b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // Get the value of the right-hand side. We only care about values 70b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // that are defined (UnknownVals and UndefinedVals are handled by other 71b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // checkers). 72b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes const DefinedSVal *DV = dyn_cast<DefinedSVal>(&val); 73b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes if (!DV) 74b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes return; 75b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 76b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // Check if the assigned value meets our criteria for correctness. It must 77b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // be a value that is either 0 or 1. One way to check this is to see if 78b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // the value is possibly < 0 (for a negative value) or greater than 1. 79b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes ProgramStateRef state = C.getState(); 80b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes SValBuilder &svalBuilder = C.getSValBuilder(); 81b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes ConstraintManager &CM = C.getConstraintManager(); 82b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 83b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // First, ensure that the value is >= 0. 84b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes DefinedSVal zeroVal = svalBuilder.makeIntVal(0, valTy); 85b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes SVal greaterThanOrEqualToZeroVal = 86b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes svalBuilder.evalBinOp(state, BO_GE, *DV, zeroVal, 87b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes svalBuilder.getConditionType()); 88b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 89b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes DefinedSVal *greaterThanEqualToZero = 90b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes dyn_cast<DefinedSVal>(&greaterThanOrEqualToZeroVal); 91b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 92b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes if (!greaterThanEqualToZero) { 93b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // The SValBuilder cannot construct a valid SVal for this condition. 94b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // This means we cannot properly reason about it. 95b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes return; 96b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes } 97b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 98b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes ProgramStateRef stateLT, stateGE; 99b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes llvm::tie(stateGE, stateLT) = CM.assumeDual(state, *greaterThanEqualToZero); 100b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 101b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // Is it possible for the value to be less than zero? 102b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes if (stateLT) { 103b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // It is possible for the value to be less than zero. We only 104b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // want to emit a warning, however, if that value is fully constrained. 105b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // If it it possible for the value to be >= 0, then essentially the 106b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // value is underconstrained and there is nothing left to be done. 107b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes if (!stateGE) 108b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes emitReport(stateLT, C); 109b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 110b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // In either case, we are done. 111b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes return; 112b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes } 113b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 114b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // If we reach here, it must be the case that the value is constrained 115b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // to only be >= 0. 116b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes assert(stateGE == state); 117b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 118b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // At this point we know that the value is >= 0. 119b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // Now check to ensure that the value is <= 1. 120b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes DefinedSVal OneVal = svalBuilder.makeIntVal(1, valTy); 121b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes SVal lessThanEqToOneVal = 122b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes svalBuilder.evalBinOp(state, BO_LE, *DV, OneVal, 123b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes svalBuilder.getConditionType()); 124b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 125b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes DefinedSVal *lessThanEqToOne = 126b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes dyn_cast<DefinedSVal>(&lessThanEqToOneVal); 127b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 128b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes if (!lessThanEqToOne) { 129b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // The SValBuilder cannot construct a valid SVal for this condition. 130b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // This means we cannot properly reason about it. 131b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes return; 132b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes } 133b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 134b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes ProgramStateRef stateGT, stateLE; 135b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes llvm::tie(stateLE, stateGT) = CM.assumeDual(state, *lessThanEqToOne); 136b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 137b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // Is it possible for the value to be greater than one? 138b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes if (stateGT) { 139b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // It is possible for the value to be greater than one. We only 140b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // want to emit a warning, however, if that value is fully constrained. 141b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // If it is possible for the value to be <= 1, then essentially the 142b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // value is underconstrained and there is nothing left to be done. 143b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes if (!stateLE) 144b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes emitReport(stateGT, C); 145b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 146b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // In either case, we are done. 147b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes return; 148b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes } 149b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 150b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // If we reach here, it must be the case that the value is constrained 151b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes // to only be <= 1. 152b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes assert(stateLE == state); 153b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes} 154b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes 155b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostesvoid ento::registerBoolAssignmentChecker(CheckerManager &mgr) { 156b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes mgr.registerChecker<BoolAssignmentChecker>(); 157b141b285d17934a08d1cb0f5f0a5a4d65b2caab2Ryan Govostes} 158