24#include "llvm/ADT/SmallString.h"
25#include "llvm/Support/raw_ostream.h"
33class ArrayBoundCheckerV2 :
34 public Checker<check::Location> {
35 mutable std::unique_ptr<BuiltinBug> BT;
37 enum OOB_Kind { OOB_Precedes, OOB_Excedes, OOB_Tainted };
40 std::unique_ptr<BugReporterVisitor> Visitor =
nullptr)
const;
43 void checkLocation(
SVal l,
bool isLoad,
const Stmt*S,
48class RegionRawOffsetV2 {
54 : baseRegion(nullptr), byteOffset(
UnknownVal()) {}
58 : baseRegion(base), byteOffset(offset) {}
61 const SubRegion *getRegion()
const {
return baseRegion; }
68 void dumpToStream(raw_ostream &os)
const;
75 if (SR->
getKind() == MemRegion::UnknownSpaceRegionKind)
85static std::pair<NonLoc, nonloc::ConcreteInt>
89 if (SymVal && SymVal->isExpression()) {
90 if (
const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SymVal->getSymbol())) {
91 llvm::APSInt constant =
93 switch (SIE->getOpcode()) {
97 if ((extent.
getValue() % constant) != 0)
98 return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent);
114 return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent);
117void ArrayBoundCheckerV2::checkLocation(
SVal location,
bool isLoad,
133 const RegionRawOffsetV2 &rawOffset =
134 RegionRawOffsetV2::computeOffset(state, svalBuilder, location);
136 if (!rawOffset.getRegion())
139 NonLoc rawOffsetVal = rawOffset.getByteOffset();
147 if (std::optional<NonLoc> NV = extentBegin.
getAs<
NonLoc>()) {
149 std::pair<NonLoc, nonloc::ConcreteInt> simplifiedOffsets =
152 rawOffsetVal = simplifiedOffsets.first;
153 *NV = simplifiedOffsets.second;
156 SVal lowerBound = svalBuilder.
evalBinOpNN(state, BO_LT, rawOffsetVal, *NV,
159 std::optional<NonLoc> lowerBoundToCheck = lowerBound.
getAs<
NonLoc>();
160 if (!lowerBoundToCheck)
164 std::tie(state_precedesLowerBound, state_withinLowerBound) =
165 state->assume(*lowerBoundToCheck);
168 if (state_precedesLowerBound && !state_withinLowerBound) {
169 reportOOB(checkerContext, state_precedesLowerBound, OOB_Precedes);
174 assert(state_withinLowerBound);
175 state = state_withinLowerBound;
181 const MemRegion *MR = rawOffset.getRegion();
183 if (!isa<NonLoc>(Size))
187 std::pair<NonLoc, nonloc::ConcreteInt> simplifiedOffsets =
190 rawOffsetVal = simplifiedOffsets.first;
191 Size = simplifiedOffsets.second;
198 std::optional<NonLoc> upperboundToCheck = upperbound.
getAs<
NonLoc>();
199 if (!upperboundToCheck)
203 std::tie(state_exceedsUpperBound, state_withinUpperBound) =
204 state->assume(*upperboundToCheck);
207 if (state_exceedsUpperBound && state_withinUpperBound) {
208 SVal ByteOffset = rawOffset.getByteOffset();
210 reportOOB(checkerContext, state_exceedsUpperBound, OOB_Tainted,
211 std::make_unique<TaintBugVisitor>(ByteOffset));
214 }
else if (state_exceedsUpperBound) {
217 assert(!state_withinUpperBound);
218 reportOOB(checkerContext, state_exceedsUpperBound, OOB_Excedes);
222 assert(state_withinUpperBound);
223 state = state_withinUpperBound;
230void ArrayBoundCheckerV2::reportOOB(
232 std::unique_ptr<BugReporterVisitor> Visitor)
const {
239 BT.reset(
new BuiltinBug(
this,
"Out-of-bound access"));
245 llvm::raw_svector_ostream os(buf);
246 os <<
"Out of bound memory access ";
249 os <<
"(accessed memory precedes memory block)";
252 os <<
"(access exceeds upper limit of memory block)";
255 os <<
"(index is tainted)";
259 auto BR = std::make_unique<PathSensitiveBugReport>(*BT, os.str(), errorNode);
260 BR->addVisitor(std::move(Visitor));
265LLVM_DUMP_METHOD
void RegionRawOffsetV2::dump()
const {
266 dumpToStream(llvm::errs());
269void RegionRawOffsetV2::dumpToStream(raw_ostream &os)
const {
270 os <<
"raw_offset_v2{" << getRegion() <<
',' << getByteOffset() <<
'}';
307RegionRawOffsetV2 RegionRawOffsetV2::computeOffset(
ProgramStateRef state,
317 if (
const SubRegion *subReg = dyn_cast<SubRegion>(region)) {
318 offset =
getValue(offset, svalBuilder);
320 return RegionRawOffsetV2(subReg, offset);
322 return RegionRawOffsetV2();
324 case MemRegion::ElementRegionKind: {
327 if (!isa<NonLoc>(index))
328 return RegionRawOffsetV2();
333 return RegionRawOffsetV2();
345 return RegionRawOffsetV2();
352 return RegionRawOffsetV2();
359bool ento::shouldRegisterArrayBoundCheckerV2(
const CheckerManager &mgr) {
static SVal getValue(SVal val, SValBuilder &svalBuilder)
static SVal addValue(ProgramStateRef state, SVal x, SVal y, SValBuilder &svalBuilder)
static SVal scaleValue(ProgramStateRef state, NonLoc baseVal, CharUnits scaling, SValBuilder &sb)
static std::pair< NonLoc, nonloc::ConcreteInt > getSimplifiedOffsets(NonLoc offset, nonloc::ConcreteInt extent, SValBuilder &svalBuilder)
static SVal computeExtentBegin(SValBuilder &svalBuilder, const MemRegion *region)
static void dump(llvm::raw_ostream &OS, StringRef FunctionName, ArrayRef< CounterExpression > Expressions, ArrayRef< CounterMappingRegion > Regions)
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
CharUnits getTypeSizeInChars(QualType T) const
Return the size of the specified (complete) type T, in characters.
CharUnits - This is an opaque type for sizes expressed in character units.
QuantityType getQuantity() const
getQuantity - Get the raw integer representation of this quantity.
A (possibly-)qualified type.
Stmt - This represents one statement.
bool isIncompleteType(NamedDecl **Def=nullptr) const
Types are partitioned into 3 broad categories (C99 6.2.5p1): object types, function types,...
A record of the "type" of an APSInt, used for conversions.
llvm::APSInt convert(const llvm::APSInt &Value) const LLVM_READONLY
Convert and return a new APSInt with the given value, but this type's bit width and signedness.
Template implementation for all binary symbolic expressions.
SValBuilder & getSValBuilder()
const ProgramStateRef & getState() const
ExplodedNode * addTransition(ProgramStateRef State=nullptr, const ProgramPointTag *Tag=nullptr)
Generates a new transition in the program state graph (ExplodedGraph).
ExplodedNode * generateErrorNode(ProgramStateRef State=nullptr, const ProgramPointTag *Tag=nullptr)
Generate a transition to a node that will be used to report an error.
void emitReport(std::unique_ptr< BugReport > R)
Emit the diagnostics report.
CHECKER * registerChecker(AT &&... Args)
Used to register checkers.
ElementRegion is used to represent both array elements and casts.
QualType getElementType() const
MemRegion - The root abstract class for all memory regions.
LLVM_ATTRIBUTE_RETURNS_NONNULL const MemSpaceRegion * getMemorySpace() const
MemSpaceRegion - A memory region that represents a "memory space"; for example, the set of global var...
NonLoc makeArrayIndex(uint64_t idx)
ASTContext & getContext()
nonloc::ConcreteInt makeIntVal(const IntegerLiteral *integer)
QualType getArrayIndexType() const
virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy)=0
Create a new value which represents a binary expression with two non- location operands.
QualType getConditionType() const
NonLoc makeZeroArrayIndex()
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
bool isUnknownOrUndef() const
std::optional< T > getAs() const
Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.
const MemRegion * getAsRegion() const
T castAs() const
Convert to the specified SVal type, asserting that this SVal is of the desired type.
SubRegion - A region that subsets another larger region.
LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getSuperRegion() const
Value representing integer constant.
const llvm::APSInt & getValue() const
Represents symbolic expression that isn't a location.
bool isTainted(ProgramStateRef State, const Stmt *S, const LocationContext *LCtx, TaintTagType Kind=TaintTagGeneric)
Check if the statement has a tainted value in the given state.
DefinedOrUnknownSVal getDynamicExtent(ProgramStateRef State, const MemRegion *MR, SValBuilder &SVB)
@ C
Languages that the frontend can parse and compile.