ProgramState.cpp revision 327952
1100364Smarkm//= ProgramState.cpp - Path-Sensitive "State" for tracking values --*- C++ -*--= 212099Sjoerg// 312099Sjoerg// The LLVM Compiler Infrastructure 412099Sjoerg// 512099Sjoerg// This file is distributed under the University of Illinois Open Source 612099Sjoerg// License. See LICENSE.TXT for details. 712099Sjoerg// 812099Sjoerg//===----------------------------------------------------------------------===// 912099Sjoerg// 1012099Sjoerg// This file implements ProgramState and ProgramStateManager. 1112099Sjoerg// 1212099Sjoerg//===----------------------------------------------------------------------===// 1312099Sjoerg 1412099Sjoerg#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 1512099Sjoerg#include "clang/Analysis/CFG.h" 1612099Sjoerg#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 1712099Sjoerg#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 1812099Sjoerg#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h" 1912099Sjoerg#include "clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h" 2012099Sjoerg#include "llvm/Support/raw_ostream.h" 2112099Sjoerg 2212099Sjoergusing namespace clang; 2312099Sjoergusing namespace ento; 2412099Sjoerg 2512099Sjoergnamespace clang { namespace ento { 2612099Sjoerg/// Increments the number of times this state is referenced. 2712099Sjoerg 2812099Sjoergvoid ProgramStateRetain(const ProgramState *state) { 2912099Sjoerg ++const_cast<ProgramState*>(state)->refCount; 3012099Sjoerg} 3112099Sjoerg 3212099Sjoerg/// Decrement the number of times this state is referenced. 3312099Sjoergvoid ProgramStateRelease(const ProgramState *state) { 3491592Smarkm assert(state->refCount > 0); 3591592Smarkm ProgramState *s = const_cast<ProgramState*>(state); 36100364Smarkm if (--s->refCount == 0) { 3712099Sjoerg ProgramStateManager &Mgr = s->getStateManager(); 3891592Smarkm Mgr.StateSet.RemoveNode(s); 3912099Sjoerg s->~ProgramState(); 4012099Sjoerg Mgr.freeStates.push_back(s); 4112099Sjoerg } 4212099Sjoerg} 43148723Sstefanf}} 4412099Sjoerg 4512099SjoergProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env, 4612099Sjoerg StoreRef st, GenericDataMap gdm) 4712099Sjoerg : stateMgr(mgr), 4812099Sjoerg Env(env), 4912099Sjoerg store(st.getStore()), 5012099Sjoerg GDM(gdm), 5112099Sjoerg refCount(0) { 5212099Sjoerg stateMgr->getStoreManager().incrementReferenceCount(store); 5312099Sjoerg} 5412099Sjoerg 5512099SjoergProgramState::ProgramState(const ProgramState &RHS) 5612099Sjoerg : llvm::FoldingSetNode(), 5712099Sjoerg stateMgr(RHS.stateMgr), 5812099Sjoerg Env(RHS.Env), 5912099Sjoerg store(RHS.store), 6012099Sjoerg GDM(RHS.GDM), 6112099Sjoerg refCount(0) { 6291592Smarkm stateMgr->getStoreManager().incrementReferenceCount(store); 6312099Sjoerg} 6412099Sjoerg 6512099SjoergProgramState::~ProgramState() { 6612099Sjoerg if (store) 6712099Sjoerg stateMgr->getStoreManager().decrementReferenceCount(store); 6891592Smarkm} 6912099Sjoerg 7012099SjoergProgramStateManager::ProgramStateManager(ASTContext &Ctx, 7112099Sjoerg StoreManagerCreator CreateSMgr, 7212099Sjoerg ConstraintManagerCreator CreateCMgr, 7312099Sjoerg llvm::BumpPtrAllocator &alloc, 7412099Sjoerg SubEngine *SubEng) 7512099Sjoerg : Eng(SubEng), EnvMgr(alloc), GDMFactory(alloc), 7612099Sjoerg svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)), 7712099Sjoerg CallEventMgr(new CallEventManager(alloc)), Alloc(alloc) { 7812099Sjoerg StoreMgr = (*CreateSMgr)(*this); 7912099Sjoerg ConstraintMgr = (*CreateCMgr)(*this, SubEng); 8012099Sjoerg} 8112099Sjoerg 8212099Sjoerg 8391592SmarkmProgramStateManager::~ProgramStateManager() { 8412099Sjoerg for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end(); 8591592Smarkm I!=E; ++I) 8612099Sjoerg I->second.second(I->second.first); 8712099Sjoerg} 8812099Sjoerg 8912099SjoergProgramStateRef 9091592SmarkmProgramStateManager::removeDeadBindings(ProgramStateRef state, 9112099Sjoerg const StackFrameContext *LCtx, 9212099Sjoerg SymbolReaper& SymReaper) { 9312099Sjoerg 9412099Sjoerg // This code essentially performs a "mark-and-sweep" of the VariableBindings. 9512099Sjoerg // The roots are any Block-level exprs and Decls that our liveness algorithm 9612099Sjoerg // tells us are live. We then see what Decls they may reference, and keep 9712099Sjoerg // those around. This code more than likely can be made faster, and the 9812099Sjoerg // frequency of which this method is called should be experimented with 9912099Sjoerg // for optimum performance. 10080284Sobrien ProgramState NewState = *state; 10180284Sobrien 10212099Sjoerg NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state); 10380284Sobrien 10480284Sobrien // Clean up the store. 10512099Sjoerg StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx, 10612099Sjoerg SymReaper); 10712099Sjoerg NewState.setStore(newStore); 10812099Sjoerg SymReaper.setReapedStore(newStore); 10912099Sjoerg 11012099Sjoerg ProgramStateRef Result = getPersistentState(NewState); 11112099Sjoerg return ConstraintMgr->removeDeadBindings(Result, SymReaper); 11212099Sjoerg} 11312099Sjoerg 11412099SjoergProgramStateRef ProgramState::bindLoc(Loc LV, 11512099Sjoerg SVal V, 11612099Sjoerg const LocationContext *LCtx, 11712099Sjoerg bool notifyChanges) const { 11812099Sjoerg ProgramStateManager &Mgr = getStateManager(); 11912099Sjoerg ProgramStateRef newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(), 12012099Sjoerg LV, V)); 12112099Sjoerg const MemRegion *MR = LV.getAsRegion(); 12212099Sjoerg if (MR && Mgr.getOwningEngine() && notifyChanges) 12312099Sjoerg return Mgr.getOwningEngine()->processRegionChange(newState, MR, LCtx); 12491592Smarkm 12512099Sjoerg return newState; 12612099Sjoerg} 12712099Sjoerg 12812099SjoergProgramStateRef ProgramState::bindDefault(SVal loc, 12912099Sjoerg SVal V, 13012099Sjoerg const LocationContext *LCtx) const { 13112099Sjoerg ProgramStateManager &Mgr = getStateManager(); 13212099Sjoerg const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion(); 13312099Sjoerg const StoreRef &newStore = Mgr.StoreMgr->BindDefault(getStore(), R, V); 13412099Sjoerg ProgramStateRef new_state = makeWithStore(newStore); 13512099Sjoerg return Mgr.getOwningEngine() ? 136228992Suqs Mgr.getOwningEngine()->processRegionChange(new_state, R, LCtx) : 13712099Sjoerg new_state; 13812099Sjoerg} 13912099Sjoerg 14012099Sjoergtypedef ArrayRef<const MemRegion *> RegionList; 14112099Sjoergtypedef ArrayRef<SVal> ValueList; 14212099Sjoerg 14312099SjoergProgramStateRef 14412099SjoergProgramState::invalidateRegions(RegionList Regions, 14512099Sjoerg const Expr *E, unsigned Count, 14612099Sjoerg const LocationContext *LCtx, 14712099Sjoerg bool CausedByPointerEscape, 14812099Sjoerg InvalidatedSymbols *IS, 14912099Sjoerg const CallEvent *Call, 15012099Sjoerg RegionAndSymbolInvalidationTraits *ITraits) const { 15112099Sjoerg SmallVector<SVal, 8> Values; 15212099Sjoerg for (RegionList::const_iterator I = Regions.begin(), 15312099Sjoerg End = Regions.end(); I != End; ++I) 15412099Sjoerg Values.push_back(loc::MemRegionVal(*I)); 15512099Sjoerg 15612099Sjoerg return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape, 15712099Sjoerg IS, ITraits, Call); 15812099Sjoerg} 15912099Sjoerg 16012099SjoergProgramStateRef 16112099SjoergProgramState::invalidateRegions(ValueList Values, 16212099Sjoerg const Expr *E, unsigned Count, 16312099Sjoerg const LocationContext *LCtx, 16412099Sjoerg bool CausedByPointerEscape, 16591592Smarkm InvalidatedSymbols *IS, 16691592Smarkm const CallEvent *Call, 16791592Smarkm RegionAndSymbolInvalidationTraits *ITraits) const { 16812099Sjoerg 16912099Sjoerg return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape, 17091592Smarkm IS, ITraits, Call); 17112099Sjoerg} 17212099Sjoerg 17312099SjoergProgramStateRef 17412099SjoergProgramState::invalidateRegionsImpl(ValueList Values, 17580284Sobrien const Expr *E, unsigned Count, 17680284Sobrien const LocationContext *LCtx, 17712099Sjoerg bool CausedByPointerEscape, 17812099Sjoerg InvalidatedSymbols *IS, 17912099Sjoerg RegionAndSymbolInvalidationTraits *ITraits, 18012099Sjoerg const CallEvent *Call) const { 18112099Sjoerg ProgramStateManager &Mgr = getStateManager(); 18212099Sjoerg SubEngine* Eng = Mgr.getOwningEngine(); 18321786Salex 18412099Sjoerg InvalidatedSymbols Invalidated; 18512099Sjoerg if (!IS) 18612099Sjoerg IS = &Invalidated; 18712099Sjoerg 18812099Sjoerg RegionAndSymbolInvalidationTraits ITraitsLocal; 18912099Sjoerg if (!ITraits) 19012099Sjoerg ITraits = &ITraitsLocal; 19112099Sjoerg 19212099Sjoerg if (Eng) { 19312099Sjoerg StoreManager::InvalidatedRegions TopLevelInvalidated; 19412099Sjoerg StoreManager::InvalidatedRegions Invalidated; 19512099Sjoerg const StoreRef &newStore 19612099Sjoerg = Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call, 19712099Sjoerg *IS, *ITraits, &TopLevelInvalidated, 19812099Sjoerg &Invalidated); 19912099Sjoerg 20091592Smarkm ProgramStateRef newState = makeWithStore(newStore); 20112099Sjoerg 20212099Sjoerg if (CausedByPointerEscape) { 20312099Sjoerg newState = Eng->notifyCheckersOfPointerEscape(newState, IS, 204100364Smarkm TopLevelInvalidated, 20512099Sjoerg Invalidated, Call, 206206424Srdivacky *ITraits); 20712099Sjoerg } 20812099Sjoerg 209100364Smarkm return Eng->processRegionChanges(newState, IS, TopLevelInvalidated, 210100364Smarkm Invalidated, LCtx, Call); 211100364Smarkm } 212100364Smarkm 21312099Sjoerg const StoreRef &newStore = 214100364Smarkm Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call, 215100364Smarkm *IS, *ITraits, nullptr, nullptr); 21612099Sjoerg return makeWithStore(newStore); 21712099Sjoerg} 21812099Sjoerg 21912099SjoergProgramStateRef ProgramState::killBinding(Loc LV) const { 22012099Sjoerg assert(!LV.getAs<loc::MemRegionVal>() && "Use invalidateRegion instead."); 221210088Semaste 22212099Sjoerg Store OldStore = getStore(); 22312099Sjoerg const StoreRef &newStore = 22412099Sjoerg getStateManager().StoreMgr->killBinding(OldStore, LV); 22512099Sjoerg 22612099Sjoerg if (newStore.getStore() == OldStore) 22712099Sjoerg return this; 22812099Sjoerg 22912099Sjoerg return makeWithStore(newStore); 23012099Sjoerg} 23112099Sjoerg 23212099SjoergProgramStateRef 23312099SjoergProgramState::enterStackFrame(const CallEvent &Call, 23412099Sjoerg const StackFrameContext *CalleeCtx) const { 23512099Sjoerg const StoreRef &NewStore = 23691592Smarkm getStateManager().StoreMgr->enterStackFrame(getStore(), Call, CalleeCtx); 23712099Sjoerg return makeWithStore(NewStore); 23812099Sjoerg} 23912099Sjoerg 24012099SjoergSVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const { 24112099Sjoerg // We only want to do fetches from regions that we can actually bind 24212099Sjoerg // values. For example, SymbolicRegions of type 'id<...>' cannot 24312099Sjoerg // have direct bindings (but their can be bindings on their subregions). 24412099Sjoerg if (!R->isBoundable()) 24512099Sjoerg return UnknownVal(); 24612099Sjoerg 24712099Sjoerg if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) { 24812099Sjoerg QualType T = TR->getValueType(); 24991592Smarkm if (Loc::isLocType(T) || T->isIntegralOrEnumerationType()) 25012099Sjoerg return getSVal(R); 25112099Sjoerg } 25212099Sjoerg 25312099Sjoerg return UnknownVal(); 25412099Sjoerg} 25512099Sjoerg 25680284SobrienSVal ProgramState::getSVal(Loc location, QualType T) const { 25780284Sobrien SVal V = getRawSVal(cast<Loc>(location), T); 25812099Sjoerg 25912099Sjoerg // If 'V' is a symbolic value that is *perfectly* constrained to 26091592Smarkm // be a constant value, use that value instead to lessen the burden 26112099Sjoerg // on later analysis stages (so we have less symbolic values to reason 26212099Sjoerg // about). 26312099Sjoerg // We only go into this branch if we can convert the APSInt value we have 26412099Sjoerg // to the type of T, which is not always the case (e.g. for void). 26591592Smarkm if (!T.isNull() && (T->isIntegralOrEnumerationType() || Loc::isLocType(T))) { 26612099Sjoerg if (SymbolRef sym = V.getAsSymbol()) { 26791592Smarkm if (const llvm::APSInt *Int = getStateManager() 26812099Sjoerg .getConstraintManager() 26980284Sobrien .getSymVal(this, sym)) { 27080284Sobrien // FIXME: Because we don't correctly model (yet) sign-extension 27180284Sobrien // and truncation of symbolic values, we need to convert 27212099Sjoerg // the integer value to the correct signedness and bitwidth. 27312099Sjoerg // 27412099Sjoerg // This shows up in the following: 27512099Sjoerg // 27612099Sjoerg // char foo(); 27712099Sjoerg // unsigned x = foo(); 27812099Sjoerg // if (x == 54) 27991592Smarkm // ... 28012099Sjoerg // 28191592Smarkm // The symbolic value stored to 'x' is actually the conjured 28212099Sjoerg // symbol for the call to foo(); the type of that symbol is 'char', 28312099Sjoerg // not unsigned. 28412099Sjoerg const llvm::APSInt &NewV = getBasicVals().Convert(T, *Int); 28512099Sjoerg 28612099Sjoerg if (V.getAs<Loc>()) 28712099Sjoerg return loc::ConcreteInt(NewV); 28812099Sjoerg else 28991592Smarkm return nonloc::ConcreteInt(NewV); 29012099Sjoerg } 29191592Smarkm } 29212099Sjoerg } 29312099Sjoerg 29412099Sjoerg return V; 29512099Sjoerg} 29691592Smarkm 29712099SjoergProgramStateRef ProgramState::BindExpr(const Stmt *S, 29891592Smarkm const LocationContext *LCtx, 29912099Sjoerg SVal V, bool Invalidate) const{ 30012099Sjoerg Environment NewEnv = 30112099Sjoerg getStateManager().EnvMgr.bindExpr(Env, EnvironmentEntry(S, LCtx), V, 30212099Sjoerg Invalidate); 30312099Sjoerg if (NewEnv == Env) 30412099Sjoerg return this; 30512099Sjoerg 30612099Sjoerg ProgramState NewSt = *this; 30712099Sjoerg NewSt.Env = NewEnv; 30812099Sjoerg return getStateManager().getPersistentState(NewSt); 30991592Smarkm} 31012099Sjoerg 31191592SmarkmProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx, 31212099Sjoerg DefinedOrUnknownSVal UpperBound, 31312099Sjoerg bool Assumption, 31412099Sjoerg QualType indexTy) const { 31512099Sjoerg if (Idx.isUnknown() || UpperBound.isUnknown()) 31612099Sjoerg return this; 31712099Sjoerg 31812099Sjoerg // Build an expression for 0 <= Idx < UpperBound. 31991592Smarkm // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed. 32012099Sjoerg // FIXME: This should probably be part of SValBuilder. 32191592Smarkm ProgramStateManager &SM = getStateManager(); 32212099Sjoerg SValBuilder &svalBuilder = SM.getSValBuilder(); 32312099Sjoerg ASTContext &Ctx = svalBuilder.getContext(); 32412099Sjoerg 32512099Sjoerg // Get the offset: the minimum value of the array index type. 32691592Smarkm BasicValueFactory &BVF = svalBuilder.getBasicValueFactory(); 32712099Sjoerg // FIXME: This should be using ValueManager::ArrayindexTy...somehow. 32812099Sjoerg if (indexTy.isNull()) 32991592Smarkm indexTy = Ctx.IntTy; 33012099Sjoerg nonloc::ConcreteInt Min(BVF.getMinValue(indexTy)); 33191592Smarkm 33212099Sjoerg // Adjust the index. 33312099Sjoerg SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add, 33412099Sjoerg Idx.castAs<NonLoc>(), Min, indexTy); 33512099Sjoerg if (newIdx.isUnknownOrUndef()) 33612099Sjoerg return this; 33712099Sjoerg 33812099Sjoerg // Adjust the upper bound. 33912099Sjoerg SVal newBound = 34012099Sjoerg svalBuilder.evalBinOpNN(this, BO_Add, UpperBound.castAs<NonLoc>(), 34191592Smarkm Min, indexTy); 34212099Sjoerg 34312099Sjoerg if (newBound.isUnknownOrUndef()) 34412099Sjoerg return this; 34512099Sjoerg 34612099Sjoerg // Build the actual comparison. 34712099Sjoerg SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, newIdx.castAs<NonLoc>(), 34812099Sjoerg newBound.castAs<NonLoc>(), Ctx.IntTy); 34912099Sjoerg if (inBound.isUnknownOrUndef()) 35012099Sjoerg return this; 35112099Sjoerg 35212099Sjoerg // Finally, let the constraint manager take care of it. 35312099Sjoerg ConstraintManager &CM = SM.getConstraintManager(); 35412099Sjoerg return CM.assume(this, inBound.castAs<DefinedSVal>(), Assumption); 35512099Sjoerg} 35691592Smarkm 35712099SjoergConditionTruthVal ProgramState::isNull(SVal V) const { 35891592Smarkm if (V.isZeroConstant()) 35912099Sjoerg return true; 36012099Sjoerg 36112099Sjoerg if (V.isConstant()) 36212099Sjoerg return false; 36312099Sjoerg 36412099Sjoerg SymbolRef Sym = V.getAsSymbol(/* IncludeBaseRegion */ true); 36512099Sjoerg if (!Sym) 366 return ConditionTruthVal(); 367 368 return getStateManager().ConstraintMgr->isNull(this, Sym); 369} 370 371ProgramStateRef ProgramStateManager::getInitialState(const LocationContext *InitLoc) { 372 ProgramState State(this, 373 EnvMgr.getInitialEnvironment(), 374 StoreMgr->getInitialStore(InitLoc), 375 GDMFactory.getEmptyMap()); 376 377 return getPersistentState(State); 378} 379 380ProgramStateRef ProgramStateManager::getPersistentStateWithGDM( 381 ProgramStateRef FromState, 382 ProgramStateRef GDMState) { 383 ProgramState NewState(*FromState); 384 NewState.GDM = GDMState->GDM; 385 return getPersistentState(NewState); 386} 387 388ProgramStateRef ProgramStateManager::getPersistentState(ProgramState &State) { 389 390 llvm::FoldingSetNodeID ID; 391 State.Profile(ID); 392 void *InsertPos; 393 394 if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos)) 395 return I; 396 397 ProgramState *newState = nullptr; 398 if (!freeStates.empty()) { 399 newState = freeStates.back(); 400 freeStates.pop_back(); 401 } 402 else { 403 newState = (ProgramState*) Alloc.Allocate<ProgramState>(); 404 } 405 new (newState) ProgramState(State); 406 StateSet.InsertNode(newState, InsertPos); 407 return newState; 408} 409 410ProgramStateRef ProgramState::makeWithStore(const StoreRef &store) const { 411 ProgramState NewSt(*this); 412 NewSt.setStore(store); 413 return getStateManager().getPersistentState(NewSt); 414} 415 416void ProgramState::setStore(const StoreRef &newStore) { 417 Store newStoreStore = newStore.getStore(); 418 if (newStoreStore) 419 stateMgr->getStoreManager().incrementReferenceCount(newStoreStore); 420 if (store) 421 stateMgr->getStoreManager().decrementReferenceCount(store); 422 store = newStoreStore; 423} 424 425//===----------------------------------------------------------------------===// 426// State pretty-printing. 427//===----------------------------------------------------------------------===// 428 429void ProgramState::print(raw_ostream &Out, 430 const char *NL, const char *Sep) const { 431 // Print the store. 432 ProgramStateManager &Mgr = getStateManager(); 433 Mgr.getStoreManager().print(getStore(), Out, NL, Sep); 434 435 // Print out the environment. 436 Env.print(Out, NL, Sep); 437 438 // Print out the constraints. 439 Mgr.getConstraintManager().print(this, Out, NL, Sep); 440 441 // Print checker-specific data. 442 Mgr.getOwningEngine()->printState(Out, this, NL, Sep); 443} 444 445void ProgramState::printDOT(raw_ostream &Out) const { 446 print(Out, "\\l", "\\|"); 447} 448 449LLVM_DUMP_METHOD void ProgramState::dump() const { 450 print(llvm::errs()); 451} 452 453void ProgramState::printTaint(raw_ostream &Out, 454 const char *NL, const char *Sep) const { 455 TaintMapImpl TM = get<TaintMap>(); 456 457 if (!TM.isEmpty()) 458 Out <<"Tainted Symbols:" << NL; 459 460 for (TaintMapImpl::iterator I = TM.begin(), E = TM.end(); I != E; ++I) { 461 Out << I->first << " : " << I->second << NL; 462 } 463} 464 465void ProgramState::dumpTaint() const { 466 printTaint(llvm::errs()); 467} 468 469//===----------------------------------------------------------------------===// 470// Generic Data Map. 471//===----------------------------------------------------------------------===// 472 473void *const* ProgramState::FindGDM(void *K) const { 474 return GDM.lookup(K); 475} 476 477void* 478ProgramStateManager::FindGDMContext(void *K, 479 void *(*CreateContext)(llvm::BumpPtrAllocator&), 480 void (*DeleteContext)(void*)) { 481 482 std::pair<void*, void (*)(void*)>& p = GDMContexts[K]; 483 if (!p.first) { 484 p.first = CreateContext(Alloc); 485 p.second = DeleteContext; 486 } 487 488 return p.first; 489} 490 491ProgramStateRef ProgramStateManager::addGDM(ProgramStateRef St, void *Key, void *Data){ 492 ProgramState::GenericDataMap M1 = St->getGDM(); 493 ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data); 494 495 if (M1 == M2) 496 return St; 497 498 ProgramState NewSt = *St; 499 NewSt.GDM = M2; 500 return getPersistentState(NewSt); 501} 502 503ProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) { 504 ProgramState::GenericDataMap OldM = state->getGDM(); 505 ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key); 506 507 if (NewM == OldM) 508 return state; 509 510 ProgramState NewState = *state; 511 NewState.GDM = NewM; 512 return getPersistentState(NewState); 513} 514 515bool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) { 516 bool wasVisited = !visited.insert(val.getCVData()).second; 517 if (wasVisited) 518 return true; 519 520 StoreManager &StoreMgr = state->getStateManager().getStoreManager(); 521 // FIXME: We don't really want to use getBaseRegion() here because pointer 522 // arithmetic doesn't apply, but scanReachableSymbols only accepts base 523 // regions right now. 524 const MemRegion *R = val.getRegion()->getBaseRegion(); 525 return StoreMgr.scanReachableSymbols(val.getStore(), R, *this); 526} 527 528bool ScanReachableSymbols::scan(nonloc::CompoundVal val) { 529 for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I) 530 if (!scan(*I)) 531 return false; 532 533 return true; 534} 535 536bool ScanReachableSymbols::scan(const SymExpr *sym) { 537 for (SymExpr::symbol_iterator SI = sym->symbol_begin(), 538 SE = sym->symbol_end(); 539 SI != SE; ++SI) { 540 bool wasVisited = !visited.insert(*SI).second; 541 if (wasVisited) 542 continue; 543 544 if (!visitor.VisitSymbol(*SI)) 545 return false; 546 } 547 548 return true; 549} 550 551bool ScanReachableSymbols::scan(SVal val) { 552 if (Optional<loc::MemRegionVal> X = val.getAs<loc::MemRegionVal>()) 553 return scan(X->getRegion()); 554 555 if (Optional<nonloc::LazyCompoundVal> X = 556 val.getAs<nonloc::LazyCompoundVal>()) 557 return scan(*X); 558 559 if (Optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>()) 560 return scan(X->getLoc()); 561 562 if (SymbolRef Sym = val.getAsSymbol()) 563 return scan(Sym); 564 565 if (const SymExpr *Sym = val.getAsSymbolicExpression()) 566 return scan(Sym); 567 568 if (Optional<nonloc::CompoundVal> X = val.getAs<nonloc::CompoundVal>()) 569 return scan(*X); 570 571 return true; 572} 573 574bool ScanReachableSymbols::scan(const MemRegion *R) { 575 if (isa<MemSpaceRegion>(R)) 576 return true; 577 578 bool wasVisited = !visited.insert(R).second; 579 if (wasVisited) 580 return true; 581 582 if (!visitor.VisitMemRegion(R)) 583 return false; 584 585 // If this is a symbolic region, visit the symbol for the region. 586 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 587 if (!visitor.VisitSymbol(SR->getSymbol())) 588 return false; 589 590 // If this is a subregion, also visit the parent regions. 591 if (const SubRegion *SR = dyn_cast<SubRegion>(R)) { 592 const MemRegion *Super = SR->getSuperRegion(); 593 if (!scan(Super)) 594 return false; 595 596 // When we reach the topmost region, scan all symbols in it. 597 if (isa<MemSpaceRegion>(Super)) { 598 StoreManager &StoreMgr = state->getStateManager().getStoreManager(); 599 if (!StoreMgr.scanReachableSymbols(state->getStore(), SR, *this)) 600 return false; 601 } 602 } 603 604 // Regions captured by a block are also implicitly reachable. 605 if (const BlockDataRegion *BDR = dyn_cast<BlockDataRegion>(R)) { 606 BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(), 607 E = BDR->referenced_vars_end(); 608 for ( ; I != E; ++I) { 609 if (!scan(I.getCapturedRegion())) 610 return false; 611 } 612 } 613 614 return true; 615} 616 617bool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const { 618 ScanReachableSymbols S(this, visitor); 619 return S.scan(val); 620} 621 622bool ProgramState::scanReachableSymbols(const SVal *I, const SVal *E, 623 SymbolVisitor &visitor) const { 624 ScanReachableSymbols S(this, visitor); 625 for ( ; I != E; ++I) { 626 if (!S.scan(*I)) 627 return false; 628 } 629 return true; 630} 631 632bool ProgramState::scanReachableSymbols(const MemRegion * const *I, 633 const MemRegion * const *E, 634 SymbolVisitor &visitor) const { 635 ScanReachableSymbols S(this, visitor); 636 for ( ; I != E; ++I) { 637 if (!S.scan(*I)) 638 return false; 639 } 640 return true; 641} 642 643ProgramStateRef ProgramState::addTaint(const Stmt *S, 644 const LocationContext *LCtx, 645 TaintTagType Kind) const { 646 if (const Expr *E = dyn_cast_or_null<Expr>(S)) 647 S = E->IgnoreParens(); 648 649 return addTaint(getSVal(S, LCtx), Kind); 650} 651 652ProgramStateRef ProgramState::addTaint(SVal V, 653 TaintTagType Kind) const { 654 SymbolRef Sym = V.getAsSymbol(); 655 if (Sym) 656 return addTaint(Sym, Kind); 657 658 // If the SVal represents a structure, try to mass-taint all values within the 659 // structure. For now it only works efficiently on lazy compound values that 660 // were conjured during a conservative evaluation of a function - either as 661 // return values of functions that return structures or arrays by value, or as 662 // values of structures or arrays passed into the function by reference, 663 // directly or through pointer aliasing. Such lazy compound values are 664 // characterized by having exactly one binding in their captured store within 665 // their parent region, which is a conjured symbol default-bound to the base 666 // region of the parent region. 667 if (auto LCV = V.getAs<nonloc::LazyCompoundVal>()) { 668 if (Optional<SVal> binding = getStateManager().StoreMgr->getDefaultBinding(*LCV)) { 669 if (SymbolRef Sym = binding->getAsSymbol()) 670 return addPartialTaint(Sym, LCV->getRegion(), Kind); 671 } 672 } 673 674 const MemRegion *R = V.getAsRegion(); 675 return addTaint(R, Kind); 676} 677 678ProgramStateRef ProgramState::addTaint(const MemRegion *R, 679 TaintTagType Kind) const { 680 if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R)) 681 return addTaint(SR->getSymbol(), Kind); 682 return this; 683} 684 685ProgramStateRef ProgramState::addTaint(SymbolRef Sym, 686 TaintTagType Kind) const { 687 // If this is a symbol cast, remove the cast before adding the taint. Taint 688 // is cast agnostic. 689 while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym)) 690 Sym = SC->getOperand(); 691 692 ProgramStateRef NewState = set<TaintMap>(Sym, Kind); 693 assert(NewState); 694 return NewState; 695} 696 697ProgramStateRef ProgramState::addPartialTaint(SymbolRef ParentSym, 698 const SubRegion *SubRegion, 699 TaintTagType Kind) const { 700 // Ignore partial taint if the entire parent symbol is already tainted. 701 if (contains<TaintMap>(ParentSym) && *get<TaintMap>(ParentSym) == Kind) 702 return this; 703 704 // Partial taint applies if only a portion of the symbol is tainted. 705 if (SubRegion == SubRegion->getBaseRegion()) 706 return addTaint(ParentSym, Kind); 707 708 const TaintedSubRegions *SavedRegs = get<DerivedSymTaint>(ParentSym); 709 TaintedSubRegions Regs = 710 SavedRegs ? *SavedRegs : stateMgr->TSRFactory.getEmptyMap(); 711 712 Regs = stateMgr->TSRFactory.add(Regs, SubRegion, Kind); 713 ProgramStateRef NewState = set<DerivedSymTaint>(ParentSym, Regs); 714 assert(NewState); 715 return NewState; 716} 717 718bool ProgramState::isTainted(const Stmt *S, const LocationContext *LCtx, 719 TaintTagType Kind) const { 720 if (const Expr *E = dyn_cast_or_null<Expr>(S)) 721 S = E->IgnoreParens(); 722 723 SVal val = getSVal(S, LCtx); 724 return isTainted(val, Kind); 725} 726 727bool ProgramState::isTainted(SVal V, TaintTagType Kind) const { 728 if (const SymExpr *Sym = V.getAsSymExpr()) 729 return isTainted(Sym, Kind); 730 if (const MemRegion *Reg = V.getAsRegion()) 731 return isTainted(Reg, Kind); 732 return false; 733} 734 735bool ProgramState::isTainted(const MemRegion *Reg, TaintTagType K) const { 736 if (!Reg) 737 return false; 738 739 // Element region (array element) is tainted if either the base or the offset 740 // are tainted. 741 if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg)) 742 return isTainted(ER->getSuperRegion(), K) || isTainted(ER->getIndex(), K); 743 744 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg)) 745 return isTainted(SR->getSymbol(), K); 746 747 if (const SubRegion *ER = dyn_cast<SubRegion>(Reg)) 748 return isTainted(ER->getSuperRegion(), K); 749 750 return false; 751} 752 753bool ProgramState::isTainted(SymbolRef Sym, TaintTagType Kind) const { 754 if (!Sym) 755 return false; 756 757 // Traverse all the symbols this symbol depends on to see if any are tainted. 758 for (SymExpr::symbol_iterator SI = Sym->symbol_begin(), SE =Sym->symbol_end(); 759 SI != SE; ++SI) { 760 if (!isa<SymbolData>(*SI)) 761 continue; 762 763 if (const TaintTagType *Tag = get<TaintMap>(*SI)) { 764 if (*Tag == Kind) 765 return true; 766 } 767 768 if (const SymbolDerived *SD = dyn_cast<SymbolDerived>(*SI)) { 769 // If this is a SymbolDerived with a tainted parent, it's also tainted. 770 if (isTainted(SD->getParentSymbol(), Kind)) 771 return true; 772 773 // If this is a SymbolDerived with the same parent symbol as another 774 // tainted SymbolDerived and a region that's a sub-region of that tainted 775 // symbol, it's also tainted. 776 if (const TaintedSubRegions *Regs = 777 get<DerivedSymTaint>(SD->getParentSymbol())) { 778 const TypedValueRegion *R = SD->getRegion(); 779 for (auto I : *Regs) { 780 // FIXME: The logic to identify tainted regions could be more 781 // complete. For example, this would not currently identify 782 // overlapping fields in a union as tainted. To identify this we can 783 // check for overlapping/nested byte offsets. 784 if (Kind == I.second && 785 (R == I.first || R->isSubRegionOf(I.first))) 786 return true; 787 } 788 } 789 } 790 791 // If memory region is tainted, data is also tainted. 792 if (const SymbolRegionValue *SRV = dyn_cast<SymbolRegionValue>(*SI)) { 793 if (isTainted(SRV->getRegion(), Kind)) 794 return true; 795 } 796 797 // If this is a SymbolCast from a tainted value, it's also tainted. 798 if (const SymbolCast *SC = dyn_cast<SymbolCast>(*SI)) { 799 if (isTainted(SC->getOperand(), Kind)) 800 return true; 801 } 802 } 803 804 return false; 805} 806 807