ArrayBoundCheckerV2.cpp revision f7ccbad5d9949e7ddd1cbef43d482553b811e026
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" 16ec8605f1d7ec846dbf51047bfd5c56d32d1ff91cArgyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/Checker.h" 1705357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/CheckerManager.h" 1805357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 199b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 209b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 21c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek#include "clang/AST/CharUnits.h" 228fe83e1df954d72c0f4ffc15d20a5222ec151c21Benjamin Kramer#include "llvm/ADT/SmallString.h" 2300bd44d5677783527d7517c1ffe45e4d75a0f56fBenjamin Kramer#include "llvm/ADT/STLExtras.h" 24c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 25c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenekusing namespace clang; 269ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenekusing namespace ento; 27c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 28c478a1425c055e517169220ea1c1efd857e65f52Ted Kremeneknamespace { 29c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenekclass ArrayBoundCheckerV2 : 30ec8605f1d7ec846dbf51047bfd5c56d32d1ff91cArgyrios Kyrtzidis public Checker<check::Location> { 316f42b62b6194f53bcbc349f5d17388e1936535d7Dylan Noblesmith mutable OwningPtr<BuiltinBug> BT; 32c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 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; 48c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 49c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek RegionRawOffsetV2() 50c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek : baseRegion(0), byteOffset(UnknownVal()) {} 51c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 52c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenekpublic: 53c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek RegionRawOffsetV2(const SubRegion* base, SVal offset) 54c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek : baseRegion(base), byteOffset(offset) {} 55c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 56c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek NonLoc getByteOffset() const { return cast<NonLoc>(byteOffset); } 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 11382cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek if (isa<NonLoc>(extentBegin)) { 11482cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek SVal lowerBound 11582cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek = svalBuilder.evalBinOpNN(state, BO_LT, rawOffset.getByteOffset(), 11682cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek cast<NonLoc>(extentBegin), 11782cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek svalBuilder.getConditionType()); 118c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 11982cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek NonLoc *lowerBoundToCheck = dyn_cast<NonLoc>(&lowerBound); 12082cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek if (!lowerBoundToCheck) 12182cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek return; 122c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 1238bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef state_precedesLowerBound, state_withinLowerBound; 12482cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek llvm::tie(state_precedesLowerBound, state_withinLowerBound) = 125c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek state->assume(*lowerBoundToCheck); 126c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 12782cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek // Are we constrained enough to definitely precede the lower bound? 12882cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek if (state_precedesLowerBound && !state_withinLowerBound) { 12982cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek reportOOB(checkerContext, state_precedesLowerBound, OOB_Precedes); 13082cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek return; 13182cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek } 132c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 13382cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek // Otherwise, assume the constraint of the lower bound. 13482cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek assert(state_withinLowerBound); 13582cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek state = state_withinLowerBound; 13682cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek } 137c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 138c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek do { 139c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // CHECK UPPER BOUND: Is byteOffset >= extent(baseRegion)? If so, 140c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // we are doing a load/store after the last valid offset. 141c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek DefinedOrUnknownSVal extentVal = 142c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek rawOffset.getRegion()->getExtent(svalBuilder); 143c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (!isa<NonLoc>(extentVal)) 144c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek break; 145c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 146c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SVal upperbound 147c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek = svalBuilder.evalBinOpNN(state, BO_GE, rawOffset.getByteOffset(), 148c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek cast<NonLoc>(extentVal), 149c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek svalBuilder.getConditionType()); 150c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 151c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek NonLoc *upperboundToCheck = dyn_cast<NonLoc>(&upperbound); 152c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (!upperboundToCheck) 153c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek break; 154c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 1558bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef state_exceedsUpperBound, state_withinUpperBound; 156c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek llvm::tie(state_exceedsUpperBound, state_withinUpperBound) = 157c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek state->assume(*upperboundToCheck); 1589b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks 1599b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks // If we are under constrained and the index variables are tainted, report. 1609b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks if (state_exceedsUpperBound && state_withinUpperBound) { 1619b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks if (state->isTainted(rawOffset.getByteOffset())) 1623bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks reportOOB(checkerContext, state_exceedsUpperBound, OOB_Tainted); 1639b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks return; 1649b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks } 165c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 1669b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks // If we are constrained enough to definitely exceed the upper bound, report. 1679b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks if (state_exceedsUpperBound) { 1689b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks assert(!state_withinUpperBound); 169c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek reportOOB(checkerContext, state_exceedsUpperBound, OOB_Excedes); 170c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return; 171c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek } 172c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 173c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek assert(state_withinUpperBound); 174c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek state = state_withinUpperBound; 175c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek } 176c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek while (false); 177c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 178c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (state != originalState) 1790bd6b110e908892d4b5c8671a9f435a1d72ad16aAnna Zaks checkerContext.addTransition(state); 180c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 181c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 182c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenekvoid ArrayBoundCheckerV2::reportOOB(CheckerContext &checkerContext, 1838bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef errorState, 18405357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidis OOB_Kind kind) const { 185c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 186c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek ExplodedNode *errorNode = checkerContext.generateSink(errorState); 187c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (!errorNode) 188c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return; 189c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 190c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (!BT) 19105357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidis BT.reset(new BuiltinBug("Out-of-bound access")); 192c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 193c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // FIXME: This diagnostics are preliminary. We should get far better 194c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // diagnostics for explaining buffer overruns. 195c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 196f7ccbad5d9949e7ddd1cbef43d482553b811e026Dylan Noblesmith SmallString<256> buf; 197c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek llvm::raw_svector_ostream os(buf); 1983bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks os << "Out of bound memory access "; 1993bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks switch (kind) { 2003bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks case OOB_Precedes: 2013bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks os << "(accessed memory precedes memory block)"; 2023bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks break; 2033bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks case OOB_Excedes: 2043bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks os << "(access exceeds upper limit of memory block)"; 2053bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks break; 2063bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks case OOB_Tainted: 2073bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks os << "(index is tainted)"; 2083bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks break; 2093bfd6d701ee297bd062967e11400daae51b36eb2Anna Zaks } 210c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 211e172e8b9e7fc67d7d03589af7e92fe777afcf33aAnna Zaks checkerContext.EmitReport(new BugReport(*BT, os.str(), errorNode)); 212c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 213c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 214c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenekvoid RegionRawOffsetV2::dump() const { 215c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek dumpToStream(llvm::errs()); 216c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 217c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 2189c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid RegionRawOffsetV2::dumpToStream(raw_ostream &os) const { 219c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek os << "raw_offset_v2{" << getRegion() << ',' << getByteOffset() << '}'; 220c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 221c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 222c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// FIXME: Merge with the implementation of the same method in Store.cpp 223c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenekstatic bool IsCompleteType(ASTContext &Ctx, QualType Ty) { 224c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (const RecordType *RT = Ty->getAs<RecordType>()) { 225c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek const RecordDecl *D = RT->getDecl(); 226c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (!D->getDefinition()) 227c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return false; 228c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek } 229c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 230c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return true; 231c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 232c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 233c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 234c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// Lazily computes a value to be used by 'computeOffset'. If 'val' 235c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// is unknown or undefined, we lazily substitute '0'. Otherwise, 236c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// return 'val'. 237c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenekstatic inline SVal getValue(SVal val, SValBuilder &svalBuilder) { 238c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return isa<UndefinedVal>(val) ? svalBuilder.makeArrayIndex(0) : val; 239c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 240c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 241c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// Scale a base value by a scaling factor, and return the scaled 242c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// value as an SVal. Used by 'computeOffset'. 2438bef8238181a30e52dea380789a7e2d760eac532Ted Kremenekstatic inline SVal scaleValue(ProgramStateRef state, 244c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek NonLoc baseVal, CharUnits scaling, 245c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SValBuilder &sb) { 246c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return sb.evalBinOpNN(state, BO_Mul, baseVal, 247c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek sb.makeArrayIndex(scaling.getQuantity()), 248c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek sb.getArrayIndexType()); 249c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 250c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 251c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// Add an SVal to another, treating unknown and undefined values as 252c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek// summing to UnknownVal. Used by 'computeOffset'. 2538bef8238181a30e52dea380789a7e2d760eac532Ted Kremenekstatic SVal addValue(ProgramStateRef state, SVal x, SVal y, 254c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SValBuilder &svalBuilder) { 255c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // We treat UnknownVals and UndefinedVals the same here because we 256c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // only care about computing offsets. 257c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (x.isUnknownOrUndef() || y.isUnknownOrUndef()) 258c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return UnknownVal(); 259c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 260c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return svalBuilder.evalBinOpNN(state, BO_Add, 261c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek cast<NonLoc>(x), cast<NonLoc>(y), 262c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek svalBuilder.getArrayIndexType()); 263c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 264c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 265c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek/// Compute a raw byte offset from a base region. Used for array bounds 266c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek/// checking. 2678bef8238181a30e52dea380789a7e2d760eac532Ted KremenekRegionRawOffsetV2 RegionRawOffsetV2::computeOffset(ProgramStateRef state, 268c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SValBuilder &svalBuilder, 269c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SVal location) 270c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek{ 271c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek const MemRegion *region = location.getAsRegion(); 272c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SVal offset = UndefinedVal(); 273c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 274c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek while (region) { 275c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek switch (region->getKind()) { 276c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek default: { 27782cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek if (const SubRegion *subReg = dyn_cast<SubRegion>(region)) { 27882cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek offset = getValue(offset, svalBuilder); 279c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (!offset.isUnknownOrUndef()) 280c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return RegionRawOffsetV2(subReg, offset); 28182cfc6849204b07e80f8ac71e33247f7df760032Ted Kremenek } 282c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return RegionRawOffsetV2(); 283c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek } 284c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek case MemRegion::ElementRegionKind: { 285c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek const ElementRegion *elemReg = cast<ElementRegion>(region); 286c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek SVal index = elemReg->getIndex(); 287c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (!isa<NonLoc>(index)) 288c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return RegionRawOffsetV2(); 289c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek QualType elemType = elemReg->getElementType(); 290c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // If the element is an incomplete type, go no further. 291c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek ASTContext &astContext = svalBuilder.getContext(); 292c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (!IsCompleteType(astContext, elemType)) 293c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return RegionRawOffsetV2(); 294c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 295c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek // Update the offset. 296c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek offset = addValue(state, 297c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek getValue(offset, svalBuilder), 298c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek scaleValue(state, 2999b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks cast<NonLoc>(index), 3009b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks astContext.getTypeSizeInChars(elemType), 3019b0970f2c7fdc070b18e113f0bbd96e7f77b4f54Anna Zaks svalBuilder), 302c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek svalBuilder); 303c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 304c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek if (offset.isUnknownOrUndef()) 305c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return RegionRawOffsetV2(); 306c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 307c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek region = elemReg->getSuperRegion(); 308c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek continue; 309c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek } 310c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek } 311c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek } 312c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek return RegionRawOffsetV2(); 313c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek} 314c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 315c478a1425c055e517169220ea1c1efd857e65f52Ted Kremenek 31605357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidisvoid ento::registerArrayBoundCheckerV2(CheckerManager &mgr) { 31705357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidis mgr.registerChecker<ArrayBoundCheckerV2>(); 31805357018b2e5e66559ad0ce2147dc1db9af42b9dArgyrios Kyrtzidis} 319