BoolAssignmentChecker.cpp revision 651f13cea278ec967336033dd032faef0e9fc2ec
16f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org//== BoolAssignmentChecker.cpp - Boolean assignment checker -----*- C++ -*--==// 26f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// 36f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// The LLVM Compiler Infrastructure 46f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// 56f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// This file is distributed under the University of Illinois Open Source 66f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// License. See LICENSE.TXT for details. 76f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// 86f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org//===----------------------------------------------------------------------===// 96f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// 106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// This defines BoolAssignmentChecker, a builtin check in ExprEngine that 116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// performs checks for assignment of non-Boolean values to Boolean variables. 126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org// 136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org//===----------------------------------------------------------------------===// 146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "ClangSACheckers.h" 166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "clang/StaticAnalyzer/Core/Checker.h" 186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "clang/StaticAnalyzer/Core/CheckerManager.h" 196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgusing namespace clang; 226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgusing namespace ento; 236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgnamespace { 256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org class BoolAssignmentChecker : public Checker< check::Bind > { 266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org mutable std::unique_ptr<BuiltinBug> BT; 276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org void emitReport(ProgramStateRef state, CheckerContext &C) const; 286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org public: 296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org void checkBind(SVal loc, SVal val, const Stmt *S, CheckerContext &C) const; 306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org }; 316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} // end anonymous namespace 326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgvoid BoolAssignmentChecker::emitReport(ProgramStateRef state, 346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org CheckerContext &C) const { 356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (ExplodedNode *N = C.addTransition(state)) { 366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (!BT) 376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org BT.reset(new BuiltinBug(this, "Assignment of a non-Boolean value")); 386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org C.emitReport(new BugReport(*BT, BT->getDescription(), N)); 396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic bool isBooleanType(QualType Ty) { 436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (Ty->isBooleanType()) // C++ or C99 446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return true; 456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (const TypedefType *TT = Ty->getAs<TypedefType>()) 476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return TT->getDecl()->getName() == "BOOL" || // Objective-C 486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org TT->getDecl()->getName() == "_Bool" || // stdbool.h < C99 496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org TT->getDecl()->getName() == "Boolean"; // MacTypes.h 506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return false; 526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgvoid BoolAssignmentChecker::checkBind(SVal loc, SVal val, const Stmt *S, 556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org CheckerContext &C) const { 566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // We are only interested in stores into Booleans. 586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const TypedValueRegion *TR = 596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org dyn_cast_or_null<TypedValueRegion>(loc.getAsRegion()); 606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (!TR) 626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org QualType valTy = TR->getValueType(); 656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (!isBooleanType(valTy)) 676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Get the value of the right-hand side. We only care about values 706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // that are defined (UnknownVals and UndefinedVals are handled by other 716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // checkers). 726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org Optional<DefinedSVal> DV = val.getAs<DefinedSVal>(); 736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (!DV) 746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Check if the assigned value meets our criteria for correctness. It must 776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // be a value that is either 0 or 1. One way to check this is to see if 786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // the value is possibly < 0 (for a negative value) or greater than 1. 796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ProgramStateRef state = C.getState(); 806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org SValBuilder &svalBuilder = C.getSValBuilder(); 816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ConstraintManager &CM = C.getConstraintManager(); 826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // First, ensure that the value is >= 0. 846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org DefinedSVal zeroVal = svalBuilder.makeIntVal(0, valTy); 856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org SVal greaterThanOrEqualToZeroVal = 866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org svalBuilder.evalBinOp(state, BO_GE, *DV, zeroVal, 876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org svalBuilder.getConditionType()); 886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org Optional<DefinedSVal> greaterThanEqualToZero = 906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org greaterThanOrEqualToZeroVal.getAs<DefinedSVal>(); 916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (!greaterThanEqualToZero) { 936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // The SValBuilder cannot construct a valid SVal for this condition. 946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // This means we cannot properly reason about it. 956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ProgramStateRef stateLT, stateGE; 996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org std::tie(stateGE, stateLT) = CM.assumeDual(state, *greaterThanEqualToZero); 1006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // Is it possible for the value to be less than zero? 1026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (stateLT) { 1036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // It is possible for the value to be less than zero. We only 1046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // want to emit a warning, however, if that value is fully constrained. 1056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // If it it possible for the value to be >= 0, then essentially the 1066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // value is underconstrained and there is nothing left to be done. 1076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (!stateGE) 1086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org emitReport(stateLT, C); 1096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // In either case, we are done. 1116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 1126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // If we reach here, it must be the case that the value is constrained 1156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org // to only be >= 0. 1166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org assert(stateGE == state); 1176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 118 // At this point we know that the value is >= 0. 119 // Now check to ensure that the value is <= 1. 120 DefinedSVal OneVal = svalBuilder.makeIntVal(1, valTy); 121 SVal lessThanEqToOneVal = 122 svalBuilder.evalBinOp(state, BO_LE, *DV, OneVal, 123 svalBuilder.getConditionType()); 124 125 Optional<DefinedSVal> lessThanEqToOne = 126 lessThanEqToOneVal.getAs<DefinedSVal>(); 127 128 if (!lessThanEqToOne) { 129 // The SValBuilder cannot construct a valid SVal for this condition. 130 // This means we cannot properly reason about it. 131 return; 132 } 133 134 ProgramStateRef stateGT, stateLE; 135 std::tie(stateLE, stateGT) = CM.assumeDual(state, *lessThanEqToOne); 136 137 // Is it possible for the value to be greater than one? 138 if (stateGT) { 139 // It is possible for the value to be greater than one. We only 140 // want to emit a warning, however, if that value is fully constrained. 141 // If it is possible for the value to be <= 1, then essentially the 142 // value is underconstrained and there is nothing left to be done. 143 if (!stateLE) 144 emitReport(stateGT, C); 145 146 // In either case, we are done. 147 return; 148 } 149 150 // If we reach here, it must be the case that the value is constrained 151 // to only be <= 1. 152 assert(stateLE == state); 153} 154 155void ento::registerBoolAssignmentChecker(CheckerManager &mgr) { 156 mgr.registerChecker<BoolAssignmentChecker>(); 157} 158