1c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek//== ArrayBoundCheckerV2.cpp ------------------------------------*- C++ -*--==// 2c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// 3c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// The LLVM Compiler Infrastructure 4c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// 5c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// This file is distributed under the University of Illinois Open Source 6c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// License. See LICENSE.TXT for details. 7c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// 8c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek//===----------------------------------------------------------------------===// 9c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// 10c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// This file defines ArrayBoundCheckerV2, which is a path-sensitive check 11c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// which looks for an out-of-bound array element access. 12c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// 13c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek//===----------------------------------------------------------------------===// 14c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 1505357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidis#include "ClangSACheckers.h" 1655fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/AST/CharUnits.h" 1755fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 18ec8605f1d7ec846dbf51047bfd5c56d32d1ff91cArgyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/Checker.h" 1905357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/CheckerManager.h" 2005357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 219b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 228fe83e1df954d72c0f4ffc15d20a5222ec151c21Benjamin Kramer#include "llvm/ADT/SmallString.h" 23a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer#include "llvm/Support/raw_ostream.h" 24c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 25c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenekusing namespace clang; 269ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenekusing namespace ento; 27c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 28c478a1425c055e517169220ea1c1efd857e65f52Ted Kremeneknamespace { 29c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenekclass ArrayBoundCheckerV2 : 30ec8605f1d7ec846dbf51047bfd5c56d32d1ff91cArgyrios Kyrtzidis public Checker<check::Location> { 31651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines mutable std::unique_ptr<BuiltinBug> BT; 32651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 333bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks enum OOB_Kind { OOB_Precedes, OOB_Excedes, OOB_Tainted }; 34c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 358bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek void reportOOB(CheckerContext &C, ProgramStateRef errorState, 3605357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidis OOB_Kind kind) const; 37c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 38c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenekpublic: 39390909c89c98ab1807e15e033a72e975f866fb23Anna Zaks void checkLocation(SVal l, bool isLoad, const Stmt*S, 40390909c89c98ab1807e15e033a72e975f866fb23Anna Zaks CheckerContext &C) const; 41c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek}; 42c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 43c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// FIXME: Eventually replace RegionRawOffset with this class. 44c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenekclass RegionRawOffsetV2 { 45c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenekprivate: 46c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek const SubRegion *baseRegion; 47c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SVal byteOffset; 486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 49c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek RegionRawOffsetV2() 506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : baseRegion(nullptr), byteOffset(UnknownVal()) {} 51c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 52c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenekpublic: 53c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek RegionRawOffsetV2(const SubRegion* base, SVal offset) 54c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek : baseRegion(base), byteOffset(offset) {} 55c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 565251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie NonLoc getByteOffset() const { return byteOffset.castAs<NonLoc>(); } 57c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek const SubRegion *getRegion() const { return baseRegion; } 58c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 598bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek static RegionRawOffsetV2 computeOffset(ProgramStateRef state, 60c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SValBuilder &svalBuilder, 61c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SVal location); 62c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 63c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek void dump() const; 649c378f705405d37f49795d5e915989de774fe11fTed Kremenek void dumpToStream(raw_ostream &os) const; 65c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek}; 66c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 67c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 6882cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenekstatic SVal computeExtentBegin(SValBuilder &svalBuilder, 6982cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek const MemRegion *region) { 7082cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek while (true) 7182cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek switch (region->getKind()) { 7282cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek default: 7382cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek return svalBuilder.makeZeroArrayIndex(); 7482cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek case MemRegion::SymbolicRegionKind: 7582cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek // FIXME: improve this later by tracking symbolic lower bounds 7682cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek // for symbolic regions. 7782cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek return UnknownVal(); 7882cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek case MemRegion::ElementRegionKind: 7982cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek region = cast<SubRegion>(region)->getSuperRegion(); 8082cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek continue; 8182cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek } 8282cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek} 8382cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek 8405357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidisvoid ArrayBoundCheckerV2::checkLocation(SVal location, bool isLoad, 85390909c89c98ab1807e15e033a72e975f866fb23Anna Zaks const Stmt* LoadS, 8605357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidis CheckerContext &checkerContext) const { 87c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 8818c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek // NOTE: Instead of using ProgramState::assumeInBound(), we are prototyping 89c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // some new logic here that reasons directly about memory region extents. 90c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // Once that logic is more mature, we can bring it back to assumeInBound() 91c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // for all clients to use. 92c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // 93c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // The algorithm we are using here for bounds checking is to see if the 94c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // memory access is within the extent of the base region. Since we 95c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // have some flexibility in defining the base region, we can achieve 96c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // various levels of conservatism in our buffer overflow checking. 978bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef state = checkerContext.getState(); 988bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef originalState = state; 99c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 100c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SValBuilder &svalBuilder = checkerContext.getSValBuilder(); 101c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek const RegionRawOffsetV2 &rawOffset = 102c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek RegionRawOffsetV2::computeOffset(state, svalBuilder, location); 103c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 104c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (!rawOffset.getRegion()) 105c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return; 106c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 10782cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek // CHECK LOWER BOUND: Is byteOffset < extent begin? 10882cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek // If so, we are doing a load/store 109c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // before the first valid offset in the memory region. 110c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 11182cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek SVal extentBegin = computeExtentBegin(svalBuilder, rawOffset.getRegion()); 11282cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek 113dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<NonLoc> NV = extentBegin.getAs<NonLoc>()) { 1145251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie SVal lowerBound = 1155251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie svalBuilder.evalBinOpNN(state, BO_LT, rawOffset.getByteOffset(), *NV, 11682cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek svalBuilder.getConditionType()); 117c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 118dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie Optional<NonLoc> lowerBoundToCheck = lowerBound.getAs<NonLoc>(); 11982cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek if (!lowerBoundToCheck) 12082cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek return; 121c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 1228bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef state_precedesLowerBound, state_withinLowerBound; 123651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines std::tie(state_precedesLowerBound, state_withinLowerBound) = 124c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek state->assume(*lowerBoundToCheck); 125c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 12682cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek // Are we constrained enough to definitely precede the lower bound? 12782cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek if (state_precedesLowerBound && !state_withinLowerBound) { 12882cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek reportOOB(checkerContext, state_precedesLowerBound, OOB_Precedes); 12982cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek return; 13082cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek } 131c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 13282cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek // Otherwise, assume the constraint of the lower bound. 13382cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek assert(state_withinLowerBound); 13482cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek state = state_withinLowerBound; 13582cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek } 136c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 137c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek do { 138c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // CHECK UPPER BOUND: Is byteOffset >= extent(baseRegion)? If so, 139c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // we are doing a load/store after the last valid offset. 140c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek DefinedOrUnknownSVal extentVal = 141c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek rawOffset.getRegion()->getExtent(svalBuilder); 1425251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie if (!extentVal.getAs<NonLoc>()) 143c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek break; 144c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 145c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SVal upperbound 146c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek = svalBuilder.evalBinOpNN(state, BO_GE, rawOffset.getByteOffset(), 1475251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie extentVal.castAs<NonLoc>(), 148c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek svalBuilder.getConditionType()); 149c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 150dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie Optional<NonLoc> upperboundToCheck = upperbound.getAs<NonLoc>(); 151c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (!upperboundToCheck) 152c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek break; 153c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 1548bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef state_exceedsUpperBound, state_withinUpperBound; 155651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines std::tie(state_exceedsUpperBound, state_withinUpperBound) = 156c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek state->assume(*upperboundToCheck); 1579b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks 1589b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks // If we are under constrained and the index variables are tainted, report. 1599b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks if (state_exceedsUpperBound && state_withinUpperBound) { 1609b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks if (state->isTainted(rawOffset.getByteOffset())) 1613bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks reportOOB(checkerContext, state_exceedsUpperBound, OOB_Tainted); 1629b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks return; 1639b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks } 164c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 1659b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks // If we are constrained enough to definitely exceed the upper bound, report. 1669b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks if (state_exceedsUpperBound) { 1679b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks assert(!state_withinUpperBound); 168c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek reportOOB(checkerContext, state_exceedsUpperBound, OOB_Excedes); 169c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return; 170c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek } 171c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 172c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek assert(state_withinUpperBound); 173c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek state = state_withinUpperBound; 174c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek } 175c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek while (false); 176c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 177c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (state != originalState) 1780bd6b110e908892d4b5c8671a9f435a1d72ad16aAnna Zaks checkerContext.addTransition(state); 179c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 180c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 181c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenekvoid ArrayBoundCheckerV2::reportOOB(CheckerContext &checkerContext, 1828bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef errorState, 18305357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidis OOB_Kind kind) const { 184c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 185c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek ExplodedNode *errorNode = checkerContext.generateSink(errorState); 186c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (!errorNode) 187c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return; 188c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 189c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (!BT) 190651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines BT.reset(new BuiltinBug(this, "Out-of-bound access")); 191c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 192c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // FIXME: This diagnostics are preliminary. We should get far better 193c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // diagnostics for explaining buffer overruns. 194c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 195f7ccbad5d9949e7ddd1cbef43d482553b811e026Dylan Noblesmith SmallString<256> buf; 196c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek llvm::raw_svector_ostream os(buf); 1973bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks os << "Out of bound memory access "; 1983bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks switch (kind) { 1993bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks case OOB_Precedes: 2003bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks os << "(accessed memory precedes memory block)"; 2013bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks break; 2023bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks case OOB_Excedes: 2033bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks os << "(access exceeds upper limit of memory block)"; 2043bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks break; 2053bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks case OOB_Tainted: 2063bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks os << "(index is tainted)"; 2073bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks break; 2083bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks } 209c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 210785950e59424dca7ce0081bebf13c0acd2c4fff6Jordan Rose checkerContext.emitReport(new BugReport(*BT, os.str(), errorNode)); 211c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 212c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 213c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenekvoid RegionRawOffsetV2::dump() const { 214c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek dumpToStream(llvm::errs()); 215c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 216c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 2179c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid RegionRawOffsetV2::dumpToStream(raw_ostream &os) const { 218c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek os << "raw_offset_v2{" << getRegion() << ',' << getByteOffset() << '}'; 219c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 220c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 221c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 222c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// Lazily computes a value to be used by 'computeOffset'. If 'val' 223c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// is unknown or undefined, we lazily substitute '0'. Otherwise, 224c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// return 'val'. 225c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenekstatic inline SVal getValue(SVal val, SValBuilder &svalBuilder) { 2265251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie return val.getAs<UndefinedVal>() ? svalBuilder.makeArrayIndex(0) : val; 227c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 228c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 229c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// Scale a base value by a scaling factor, and return the scaled 230c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// value as an SVal. Used by 'computeOffset'. 2318bef8238181a30e52dea380789a7e2d760eac532Ted Kremenekstatic inline SVal scaleValue(ProgramStateRef state, 232c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek NonLoc baseVal, CharUnits scaling, 233c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SValBuilder &sb) { 234c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return sb.evalBinOpNN(state, BO_Mul, baseVal, 235c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek sb.makeArrayIndex(scaling.getQuantity()), 236c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek sb.getArrayIndexType()); 237c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 238c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 239c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// Add an SVal to another, treating unknown and undefined values as 240c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// summing to UnknownVal. Used by 'computeOffset'. 2418bef8238181a30e52dea380789a7e2d760eac532Ted Kremenekstatic SVal addValue(ProgramStateRef state, SVal x, SVal y, 242c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SValBuilder &svalBuilder) { 243c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // We treat UnknownVals and UndefinedVals the same here because we 244c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // only care about computing offsets. 245c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (x.isUnknownOrUndef() || y.isUnknownOrUndef()) 246c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return UnknownVal(); 2475251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie 2485251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie return svalBuilder.evalBinOpNN(state, BO_Add, x.castAs<NonLoc>(), 2495251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie y.castAs<NonLoc>(), 250c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek svalBuilder.getArrayIndexType()); 251c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 252c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 253c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek/// Compute a raw byte offset from a base region. Used for array bounds 254c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek/// checking. 2558bef8238181a30e52dea380789a7e2d760eac532Ted KremenekRegionRawOffsetV2 RegionRawOffsetV2::computeOffset(ProgramStateRef state, 256c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SValBuilder &svalBuilder, 257c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SVal location) 258c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek{ 259c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek const MemRegion *region = location.getAsRegion(); 260c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SVal offset = UndefinedVal(); 261c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 262c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek while (region) { 263c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek switch (region->getKind()) { 264c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek default: { 26582cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek if (const SubRegion *subReg = dyn_cast<SubRegion>(region)) { 26682cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek offset = getValue(offset, svalBuilder); 267c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (!offset.isUnknownOrUndef()) 268c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return RegionRawOffsetV2(subReg, offset); 26982cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek } 270c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return RegionRawOffsetV2(); 271c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek } 272c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek case MemRegion::ElementRegionKind: { 273c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek const ElementRegion *elemReg = cast<ElementRegion>(region); 274c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SVal index = elemReg->getIndex(); 2755251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie if (!index.getAs<NonLoc>()) 276c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return RegionRawOffsetV2(); 277c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek QualType elemType = elemReg->getElementType(); 278c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // If the element is an incomplete type, go no further. 279c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek ASTContext &astContext = svalBuilder.getContext(); 280176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines if (elemType->isIncompleteType()) 281c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return RegionRawOffsetV2(); 282c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 283c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // Update the offset. 284c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek offset = addValue(state, 285c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek getValue(offset, svalBuilder), 286c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek scaleValue(state, 2875251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie index.castAs<NonLoc>(), 2889b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks astContext.getTypeSizeInChars(elemType), 2899b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks svalBuilder), 290c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek svalBuilder); 291c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 292c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (offset.isUnknownOrUndef()) 293c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return RegionRawOffsetV2(); 294c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 295c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek region = elemReg->getSuperRegion(); 296c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek continue; 297c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek } 298c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek } 299c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek } 300c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return RegionRawOffsetV2(); 301c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 302c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 30305357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidisvoid ento::registerArrayBoundCheckerV2(CheckerManager &mgr) { 30405357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidis mgr.registerChecker<ArrayBoundCheckerV2>(); 30505357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidis} 306