SValBuilder.cpp revision 5251abea41b446c26e3239c8dd6c7edea6fc335d
1// SValBuilder.cpp - Basic class for all SValBuilder implementations -*- C++ -*- 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines SValBuilder, the base class for all (complete) SValBuilder 11// implementations. 12// 13//===----------------------------------------------------------------------===// 14 15#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 16#include "clang/AST/DeclCXX.h" 17#include "clang/AST/ExprCXX.h" 18#include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h" 19#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 20#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 21#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 22 23using namespace clang; 24using namespace ento; 25 26//===----------------------------------------------------------------------===// 27// Basic SVal creation. 28//===----------------------------------------------------------------------===// 29 30void SValBuilder::anchor() { } 31 32DefinedOrUnknownSVal SValBuilder::makeZeroVal(QualType type) { 33 if (Loc::isLocType(type)) 34 return makeNull(); 35 36 if (type->isIntegerType()) 37 return makeIntVal(0, type); 38 39 // FIXME: Handle floats. 40 // FIXME: Handle structs. 41 return UnknownVal(); 42} 43 44NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, 45 const llvm::APSInt& rhs, QualType type) { 46 // The Environment ensures we always get a persistent APSInt in 47 // BasicValueFactory, so we don't need to get the APSInt from 48 // BasicValueFactory again. 49 assert(lhs); 50 assert(!Loc::isLocType(type)); 51 return nonloc::SymbolVal(SymMgr.getSymIntExpr(lhs, op, rhs, type)); 52} 53 54NonLoc SValBuilder::makeNonLoc(const llvm::APSInt& lhs, 55 BinaryOperator::Opcode op, const SymExpr *rhs, 56 QualType type) { 57 assert(rhs); 58 assert(!Loc::isLocType(type)); 59 return nonloc::SymbolVal(SymMgr.getIntSymExpr(lhs, op, rhs, type)); 60} 61 62NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, 63 const SymExpr *rhs, QualType type) { 64 assert(lhs && rhs); 65 assert(!Loc::isLocType(type)); 66 return nonloc::SymbolVal(SymMgr.getSymSymExpr(lhs, op, rhs, type)); 67} 68 69NonLoc SValBuilder::makeNonLoc(const SymExpr *operand, 70 QualType fromTy, QualType toTy) { 71 assert(operand); 72 assert(!Loc::isLocType(toTy)); 73 return nonloc::SymbolVal(SymMgr.getCastSymbol(operand, fromTy, toTy)); 74} 75 76SVal SValBuilder::convertToArrayIndex(SVal val) { 77 if (val.isUnknownOrUndef()) 78 return val; 79 80 // Common case: we have an appropriately sized integer. 81 if (llvm::Optional<nonloc::ConcreteInt> CI = 82 val.getAs<nonloc::ConcreteInt>()) { 83 const llvm::APSInt& I = CI->getValue(); 84 if (I.getBitWidth() == ArrayIndexWidth && I.isSigned()) 85 return val; 86 } 87 88 return evalCastFromNonLoc(val.castAs<NonLoc>(), ArrayIndexTy); 89} 90 91nonloc::ConcreteInt SValBuilder::makeBoolVal(const CXXBoolLiteralExpr *boolean){ 92 return makeTruthVal(boolean->getValue()); 93} 94 95DefinedOrUnknownSVal 96SValBuilder::getRegionValueSymbolVal(const TypedValueRegion* region) { 97 QualType T = region->getValueType(); 98 99 if (!SymbolManager::canSymbolicate(T)) 100 return UnknownVal(); 101 102 SymbolRef sym = SymMgr.getRegionValueSymbol(region); 103 104 if (Loc::isLocType(T)) 105 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 106 107 return nonloc::SymbolVal(sym); 108} 109 110DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *symbolTag, 111 const Expr *expr, 112 const LocationContext *LCtx, 113 unsigned count) { 114 QualType T = expr->getType(); 115 return conjureSymbolVal(symbolTag, expr, LCtx, T, count); 116} 117 118DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *symbolTag, 119 const Expr *expr, 120 const LocationContext *LCtx, 121 QualType type, 122 unsigned count) { 123 if (!SymbolManager::canSymbolicate(type)) 124 return UnknownVal(); 125 126 SymbolRef sym = SymMgr.conjureSymbol(expr, LCtx, type, count, symbolTag); 127 128 if (Loc::isLocType(type)) 129 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 130 131 return nonloc::SymbolVal(sym); 132} 133 134 135DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const Stmt *stmt, 136 const LocationContext *LCtx, 137 QualType type, 138 unsigned visitCount) { 139 if (!SymbolManager::canSymbolicate(type)) 140 return UnknownVal(); 141 142 SymbolRef sym = SymMgr.conjureSymbol(stmt, LCtx, type, visitCount); 143 144 if (Loc::isLocType(type)) 145 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 146 147 return nonloc::SymbolVal(sym); 148} 149 150DefinedOrUnknownSVal 151SValBuilder::getConjuredHeapSymbolVal(const Expr *E, 152 const LocationContext *LCtx, 153 unsigned VisitCount) { 154 QualType T = E->getType(); 155 assert(Loc::isLocType(T)); 156 assert(SymbolManager::canSymbolicate(T)); 157 158 SymbolRef sym = SymMgr.conjureSymbol(E, LCtx, T, VisitCount); 159 return loc::MemRegionVal(MemMgr.getSymbolicHeapRegion(sym)); 160} 161 162DefinedSVal SValBuilder::getMetadataSymbolVal(const void *symbolTag, 163 const MemRegion *region, 164 const Expr *expr, QualType type, 165 unsigned count) { 166 assert(SymbolManager::canSymbolicate(type) && "Invalid metadata symbol type"); 167 168 SymbolRef sym = 169 SymMgr.getMetadataSymbol(region, expr, type, count, symbolTag); 170 171 if (Loc::isLocType(type)) 172 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 173 174 return nonloc::SymbolVal(sym); 175} 176 177DefinedOrUnknownSVal 178SValBuilder::getDerivedRegionValueSymbolVal(SymbolRef parentSymbol, 179 const TypedValueRegion *region) { 180 QualType T = region->getValueType(); 181 182 if (!SymbolManager::canSymbolicate(T)) 183 return UnknownVal(); 184 185 SymbolRef sym = SymMgr.getDerivedSymbol(parentSymbol, region); 186 187 if (Loc::isLocType(T)) 188 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 189 190 return nonloc::SymbolVal(sym); 191} 192 193DefinedSVal SValBuilder::getFunctionPointer(const FunctionDecl *func) { 194 return loc::MemRegionVal(MemMgr.getFunctionTextRegion(func)); 195} 196 197DefinedSVal SValBuilder::getBlockPointer(const BlockDecl *block, 198 CanQualType locTy, 199 const LocationContext *locContext) { 200 const BlockTextRegion *BC = 201 MemMgr.getBlockTextRegion(block, locTy, locContext->getAnalysisDeclContext()); 202 const BlockDataRegion *BD = MemMgr.getBlockDataRegion(BC, locContext); 203 return loc::MemRegionVal(BD); 204} 205 206/// Return a memory region for the 'this' object reference. 207loc::MemRegionVal SValBuilder::getCXXThis(const CXXMethodDecl *D, 208 const StackFrameContext *SFC) { 209 return loc::MemRegionVal(getRegionManager(). 210 getCXXThisRegion(D->getThisType(getContext()), SFC)); 211} 212 213/// Return a memory region for the 'this' object reference. 214loc::MemRegionVal SValBuilder::getCXXThis(const CXXRecordDecl *D, 215 const StackFrameContext *SFC) { 216 const Type *T = D->getTypeForDecl(); 217 QualType PT = getContext().getPointerType(QualType(T, 0)); 218 return loc::MemRegionVal(getRegionManager().getCXXThisRegion(PT, SFC)); 219} 220 221//===----------------------------------------------------------------------===// 222 223SVal SValBuilder::makeSymExprValNN(ProgramStateRef State, 224 BinaryOperator::Opcode Op, 225 NonLoc LHS, NonLoc RHS, 226 QualType ResultTy) { 227 if (!State->isTainted(RHS) && !State->isTainted(LHS)) 228 return UnknownVal(); 229 230 const SymExpr *symLHS = LHS.getAsSymExpr(); 231 const SymExpr *symRHS = RHS.getAsSymExpr(); 232 // TODO: When the Max Complexity is reached, we should conjure a symbol 233 // instead of generating an Unknown value and propagate the taint info to it. 234 const unsigned MaxComp = 10000; // 100000 28X 235 236 if (symLHS && symRHS && 237 (symLHS->computeComplexity() + symRHS->computeComplexity()) < MaxComp) 238 return makeNonLoc(symLHS, Op, symRHS, ResultTy); 239 240 if (symLHS && symLHS->computeComplexity() < MaxComp) 241 if (llvm::Optional<nonloc::ConcreteInt> rInt = 242 RHS.getAs<nonloc::ConcreteInt>()) 243 return makeNonLoc(symLHS, Op, rInt->getValue(), ResultTy); 244 245 if (symRHS && symRHS->computeComplexity() < MaxComp) 246 if (llvm::Optional<nonloc::ConcreteInt> lInt = 247 LHS.getAs<nonloc::ConcreteInt>()) 248 return makeNonLoc(lInt->getValue(), Op, symRHS, ResultTy); 249 250 return UnknownVal(); 251} 252 253 254SVal SValBuilder::evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, 255 SVal lhs, SVal rhs, QualType type) { 256 257 if (lhs.isUndef() || rhs.isUndef()) 258 return UndefinedVal(); 259 260 if (lhs.isUnknown() || rhs.isUnknown()) 261 return UnknownVal(); 262 263 if (llvm::Optional<Loc> LV = lhs.getAs<Loc>()) { 264 if (llvm::Optional<Loc> RV = rhs.getAs<Loc>()) 265 return evalBinOpLL(state, op, *LV, *RV, type); 266 267 return evalBinOpLN(state, op, *LV, rhs.castAs<NonLoc>(), type); 268 } 269 270 if (llvm::Optional<Loc> RV = rhs.getAs<Loc>()) { 271 // Support pointer arithmetic where the addend is on the left 272 // and the pointer on the right. 273 assert(op == BO_Add); 274 275 // Commute the operands. 276 return evalBinOpLN(state, op, *RV, lhs.castAs<NonLoc>(), type); 277 } 278 279 return evalBinOpNN(state, op, lhs.castAs<NonLoc>(), rhs.castAs<NonLoc>(), 280 type); 281} 282 283DefinedOrUnknownSVal SValBuilder::evalEQ(ProgramStateRef state, 284 DefinedOrUnknownSVal lhs, 285 DefinedOrUnknownSVal rhs) { 286 return evalBinOp(state, BO_EQ, lhs, rhs, Context.IntTy) 287 .castAs<DefinedOrUnknownSVal>(); 288} 289 290/// Recursively check if the pointer types are equal modulo const, volatile, 291/// and restrict qualifiers. Also, assume that all types are similar to 'void'. 292/// Assumes the input types are canonical. 293static bool shouldBeModeledWithNoOp(ASTContext &Context, QualType ToTy, 294 QualType FromTy) { 295 while (Context.UnwrapSimilarPointerTypes(ToTy, FromTy)) { 296 Qualifiers Quals1, Quals2; 297 ToTy = Context.getUnqualifiedArrayType(ToTy, Quals1); 298 FromTy = Context.getUnqualifiedArrayType(FromTy, Quals2); 299 300 // Make sure that non cvr-qualifiers the other qualifiers (e.g., address 301 // spaces) are identical. 302 Quals1.removeCVRQualifiers(); 303 Quals2.removeCVRQualifiers(); 304 if (Quals1 != Quals2) 305 return false; 306 } 307 308 // If we are casting to void, the 'From' value can be used to represent the 309 // 'To' value. 310 if (ToTy->isVoidType()) 311 return true; 312 313 if (ToTy != FromTy) 314 return false; 315 316 return true; 317} 318 319// FIXME: should rewrite according to the cast kind. 320SVal SValBuilder::evalCast(SVal val, QualType castTy, QualType originalTy) { 321 castTy = Context.getCanonicalType(castTy); 322 originalTy = Context.getCanonicalType(originalTy); 323 if (val.isUnknownOrUndef() || castTy == originalTy) 324 return val; 325 326 // For const casts, casts to void, just propagate the value. 327 if (!castTy->isVariableArrayType() && !originalTy->isVariableArrayType()) 328 if (shouldBeModeledWithNoOp(Context, Context.getPointerType(castTy), 329 Context.getPointerType(originalTy))) 330 return val; 331 332 // Check for casts from pointers to integers. 333 if (castTy->isIntegerType() && Loc::isLocType(originalTy)) 334 return evalCastFromLoc(val.castAs<Loc>(), castTy); 335 336 // Check for casts from integers to pointers. 337 if (Loc::isLocType(castTy) && originalTy->isIntegerType()) { 338 if (llvm::Optional<nonloc::LocAsInteger> LV = 339 val.getAs<nonloc::LocAsInteger>()) { 340 if (const MemRegion *R = LV->getLoc().getAsRegion()) { 341 StoreManager &storeMgr = StateMgr.getStoreManager(); 342 R = storeMgr.castRegion(R, castTy); 343 return R ? SVal(loc::MemRegionVal(R)) : UnknownVal(); 344 } 345 return LV->getLoc(); 346 } 347 return dispatchCast(val, castTy); 348 } 349 350 // Just pass through function and block pointers. 351 if (originalTy->isBlockPointerType() || originalTy->isFunctionPointerType()) { 352 assert(Loc::isLocType(castTy)); 353 return val; 354 } 355 356 // Check for casts from array type to another type. 357 if (originalTy->isArrayType()) { 358 // We will always decay to a pointer. 359 val = StateMgr.ArrayToPointer(val.castAs<Loc>()); 360 361 // Are we casting from an array to a pointer? If so just pass on 362 // the decayed value. 363 if (castTy->isPointerType() || castTy->isReferenceType()) 364 return val; 365 366 // Are we casting from an array to an integer? If so, cast the decayed 367 // pointer value to an integer. 368 assert(castTy->isIntegerType()); 369 370 // FIXME: Keep these here for now in case we decide soon that we 371 // need the original decayed type. 372 // QualType elemTy = cast<ArrayType>(originalTy)->getElementType(); 373 // QualType pointerTy = C.getPointerType(elemTy); 374 return evalCastFromLoc(val.castAs<Loc>(), castTy); 375 } 376 377 // Check for casts from a region to a specific type. 378 if (const MemRegion *R = val.getAsRegion()) { 379 // Handle other casts of locations to integers. 380 if (castTy->isIntegerType()) 381 return evalCastFromLoc(loc::MemRegionVal(R), castTy); 382 383 // FIXME: We should handle the case where we strip off view layers to get 384 // to a desugared type. 385 if (!Loc::isLocType(castTy)) { 386 // FIXME: There can be gross cases where one casts the result of a function 387 // (that returns a pointer) to some other value that happens to fit 388 // within that pointer value. We currently have no good way to 389 // model such operations. When this happens, the underlying operation 390 // is that the caller is reasoning about bits. Conceptually we are 391 // layering a "view" of a location on top of those bits. Perhaps 392 // we need to be more lazy about mutual possible views, even on an 393 // SVal? This may be necessary for bit-level reasoning as well. 394 return UnknownVal(); 395 } 396 397 // We get a symbolic function pointer for a dereference of a function 398 // pointer, but it is of function type. Example: 399 400 // struct FPRec { 401 // void (*my_func)(int * x); 402 // }; 403 // 404 // int bar(int x); 405 // 406 // int f1_a(struct FPRec* foo) { 407 // int x; 408 // (*foo->my_func)(&x); 409 // return bar(x)+1; // no-warning 410 // } 411 412 assert(Loc::isLocType(originalTy) || originalTy->isFunctionType() || 413 originalTy->isBlockPointerType() || castTy->isReferenceType()); 414 415 StoreManager &storeMgr = StateMgr.getStoreManager(); 416 417 // Delegate to store manager to get the result of casting a region to a 418 // different type. If the MemRegion* returned is NULL, this expression 419 // Evaluates to UnknownVal. 420 R = storeMgr.castRegion(R, castTy); 421 return R ? SVal(loc::MemRegionVal(R)) : UnknownVal(); 422 } 423 424 return dispatchCast(val, castTy); 425} 426