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