clang 17.0.0git
ArrayBoundCheckerV2.cpp
Go to the documentation of this file.
1//== ArrayBoundCheckerV2.cpp ------------------------------------*- C++ -*--==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines ArrayBoundCheckerV2, which is a path-sensitive check
10// which looks for an out-of-bound array element access.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/AST/CharUnits.h"
24#include "llvm/ADT/SmallString.h"
25#include "llvm/Support/raw_ostream.h"
26#include <optional>
27
28using namespace clang;
29using namespace ento;
30using namespace taint;
31
32namespace {
33class ArrayBoundCheckerV2 :
34 public Checker<check::Location> {
35 mutable std::unique_ptr<BuiltinBug> BT;
36
37 enum OOB_Kind { OOB_Precedes, OOB_Excedes, OOB_Tainted };
38
39 void reportOOB(CheckerContext &C, ProgramStateRef errorState, OOB_Kind kind,
40 std::unique_ptr<BugReporterVisitor> Visitor = nullptr) const;
41
42public:
43 void checkLocation(SVal l, bool isLoad, const Stmt*S,
44 CheckerContext &C) const;
45};
46
47// FIXME: Eventually replace RegionRawOffset with this class.
48class RegionRawOffsetV2 {
49private:
50 const SubRegion *baseRegion;
51 SVal byteOffset;
52
53 RegionRawOffsetV2()
54 : baseRegion(nullptr), byteOffset(UnknownVal()) {}
55
56public:
57 RegionRawOffsetV2(const SubRegion* base, SVal offset)
58 : baseRegion(base), byteOffset(offset) {}
59
60 NonLoc getByteOffset() const { return byteOffset.castAs<NonLoc>(); }
61 const SubRegion *getRegion() const { return baseRegion; }
62
63 static RegionRawOffsetV2 computeOffset(ProgramStateRef state,
64 SValBuilder &svalBuilder,
65 SVal location);
66
67 void dump() const;
68 void dumpToStream(raw_ostream &os) const;
69};
70}
71
73 const MemRegion *region) {
74 const MemSpaceRegion *SR = region->getMemorySpace();
75 if (SR->getKind() == MemRegion::UnknownSpaceRegionKind)
76 return UnknownVal();
77 else
78 return svalBuilder.makeZeroArrayIndex();
79}
80
81// TODO: once the constraint manager is smart enough to handle non simplified
82// symbolic expressions remove this function. Note that this can not be used in
83// the constraint manager as is, since this does not handle overflows. It is
84// safe to assume, however, that memory offsets will not overflow.
85static std::pair<NonLoc, nonloc::ConcreteInt>
87 SValBuilder &svalBuilder) {
88 std::optional<nonloc::SymbolVal> SymVal = offset.getAs<nonloc::SymbolVal>();
89 if (SymVal && SymVal->isExpression()) {
90 if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SymVal->getSymbol())) {
91 llvm::APSInt constant =
92 APSIntType(extent.getValue()).convert(SIE->getRHS());
93 switch (SIE->getOpcode()) {
94 case BO_Mul:
95 // The constant should never be 0 here, since it the result of scaling
96 // based on the size of a type which is never 0.
97 if ((extent.getValue() % constant) != 0)
98 return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent);
99 else
101 nonloc::SymbolVal(SIE->getLHS()),
102 svalBuilder.makeIntVal(extent.getValue() / constant),
103 svalBuilder);
104 case BO_Add:
106 nonloc::SymbolVal(SIE->getLHS()),
107 svalBuilder.makeIntVal(extent.getValue() - constant), svalBuilder);
108 default:
109 break;
110 }
111 }
112 }
113
114 return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent);
115}
116
117void ArrayBoundCheckerV2::checkLocation(SVal location, bool isLoad,
118 const Stmt* LoadS,
119 CheckerContext &checkerContext) const {
120
121 // NOTE: Instead of using ProgramState::assumeInBound(), we are prototyping
122 // some new logic here that reasons directly about memory region extents.
123 // Once that logic is more mature, we can bring it back to assumeInBound()
124 // for all clients to use.
125 //
126 // The algorithm we are using here for bounds checking is to see if the
127 // memory access is within the extent of the base region. Since we
128 // have some flexibility in defining the base region, we can achieve
129 // various levels of conservatism in our buffer overflow checking.
130 ProgramStateRef state = checkerContext.getState();
131
132 SValBuilder &svalBuilder = checkerContext.getSValBuilder();
133 const RegionRawOffsetV2 &rawOffset =
134 RegionRawOffsetV2::computeOffset(state, svalBuilder, location);
135
136 if (!rawOffset.getRegion())
137 return;
138
139 NonLoc rawOffsetVal = rawOffset.getByteOffset();
140
141 // CHECK LOWER BOUND: Is byteOffset < extent begin?
142 // If so, we are doing a load/store
143 // before the first valid offset in the memory region.
144
145 SVal extentBegin = computeExtentBegin(svalBuilder, rawOffset.getRegion());
146
147 if (std::optional<NonLoc> NV = extentBegin.getAs<NonLoc>()) {
148 if (auto ConcreteNV = NV->getAs<nonloc::ConcreteInt>()) {
149 std::pair<NonLoc, nonloc::ConcreteInt> simplifiedOffsets =
150 getSimplifiedOffsets(rawOffset.getByteOffset(), *ConcreteNV,
151 svalBuilder);
152 rawOffsetVal = simplifiedOffsets.first;
153 *NV = simplifiedOffsets.second;
154 }
155
156 SVal lowerBound = svalBuilder.evalBinOpNN(state, BO_LT, rawOffsetVal, *NV,
157 svalBuilder.getConditionType());
158
159 std::optional<NonLoc> lowerBoundToCheck = lowerBound.getAs<NonLoc>();
160 if (!lowerBoundToCheck)
161 return;
162
163 ProgramStateRef state_precedesLowerBound, state_withinLowerBound;
164 std::tie(state_precedesLowerBound, state_withinLowerBound) =
165 state->assume(*lowerBoundToCheck);
166
167 // Are we constrained enough to definitely precede the lower bound?
168 if (state_precedesLowerBound && !state_withinLowerBound) {
169 reportOOB(checkerContext, state_precedesLowerBound, OOB_Precedes);
170 return;
171 }
172
173 // Otherwise, assume the constraint of the lower bound.
174 assert(state_withinLowerBound);
175 state = state_withinLowerBound;
176 }
177
178 do {
179 // CHECK UPPER BOUND: Is byteOffset >= size(baseRegion)? If so,
180 // we are doing a load/store after the last valid offset.
181 const MemRegion *MR = rawOffset.getRegion();
182 DefinedOrUnknownSVal Size = getDynamicExtent(state, MR, svalBuilder);
183 if (!isa<NonLoc>(Size))
184 break;
185
186 if (auto ConcreteSize = Size.getAs<nonloc::ConcreteInt>()) {
187 std::pair<NonLoc, nonloc::ConcreteInt> simplifiedOffsets =
188 getSimplifiedOffsets(rawOffset.getByteOffset(), *ConcreteSize,
189 svalBuilder);
190 rawOffsetVal = simplifiedOffsets.first;
191 Size = simplifiedOffsets.second;
192 }
193
194 SVal upperbound = svalBuilder.evalBinOpNN(state, BO_GE, rawOffsetVal,
195 Size.castAs<NonLoc>(),
196 svalBuilder.getConditionType());
197
198 std::optional<NonLoc> upperboundToCheck = upperbound.getAs<NonLoc>();
199 if (!upperboundToCheck)
200 break;
201
202 ProgramStateRef state_exceedsUpperBound, state_withinUpperBound;
203 std::tie(state_exceedsUpperBound, state_withinUpperBound) =
204 state->assume(*upperboundToCheck);
205
206 // If we are under constrained and the index variables are tainted, report.
207 if (state_exceedsUpperBound && state_withinUpperBound) {
208 SVal ByteOffset = rawOffset.getByteOffset();
209 if (isTainted(state, ByteOffset)) {
210 reportOOB(checkerContext, state_exceedsUpperBound, OOB_Tainted,
211 std::make_unique<TaintBugVisitor>(ByteOffset));
212 return;
213 }
214 } else if (state_exceedsUpperBound) {
215 // If we are constrained enough to definitely exceed the upper bound,
216 // report.
217 assert(!state_withinUpperBound);
218 reportOOB(checkerContext, state_exceedsUpperBound, OOB_Excedes);
219 return;
220 }
221
222 assert(state_withinUpperBound);
223 state = state_withinUpperBound;
224 }
225 while (false);
226
227 checkerContext.addTransition(state);
228}
229
230void ArrayBoundCheckerV2::reportOOB(
231 CheckerContext &checkerContext, ProgramStateRef errorState, OOB_Kind kind,
232 std::unique_ptr<BugReporterVisitor> Visitor) const {
233
234 ExplodedNode *errorNode = checkerContext.generateErrorNode(errorState);
235 if (!errorNode)
236 return;
237
238 if (!BT)
239 BT.reset(new BuiltinBug(this, "Out-of-bound access"));
240
241 // FIXME: This diagnostics are preliminary. We should get far better
242 // diagnostics for explaining buffer overruns.
243
245 llvm::raw_svector_ostream os(buf);
246 os << "Out of bound memory access ";
247 switch (kind) {
248 case OOB_Precedes:
249 os << "(accessed memory precedes memory block)";
250 break;
251 case OOB_Excedes:
252 os << "(access exceeds upper limit of memory block)";
253 break;
254 case OOB_Tainted:
255 os << "(index is tainted)";
256 break;
257 }
258
259 auto BR = std::make_unique<PathSensitiveBugReport>(*BT, os.str(), errorNode);
260 BR->addVisitor(std::move(Visitor));
261 checkerContext.emitReport(std::move(BR));
262}
263
264#ifndef NDEBUG
265LLVM_DUMP_METHOD void RegionRawOffsetV2::dump() const {
266 dumpToStream(llvm::errs());
267}
268
269void RegionRawOffsetV2::dumpToStream(raw_ostream &os) const {
270 os << "raw_offset_v2{" << getRegion() << ',' << getByteOffset() << '}';
271}
272#endif
273
274// Lazily computes a value to be used by 'computeOffset'. If 'val'
275// is unknown or undefined, we lazily substitute '0'. Otherwise,
276// return 'val'.
277static inline SVal getValue(SVal val, SValBuilder &svalBuilder) {
278 return val.isUndef() ? svalBuilder.makeZeroArrayIndex() : val;
279}
280
281// Scale a base value by a scaling factor, and return the scaled
282// value as an SVal. Used by 'computeOffset'.
283static inline SVal scaleValue(ProgramStateRef state,
284 NonLoc baseVal, CharUnits scaling,
285 SValBuilder &sb) {
286 return sb.evalBinOpNN(state, BO_Mul, baseVal,
287 sb.makeArrayIndex(scaling.getQuantity()),
288 sb.getArrayIndexType());
289}
290
291// Add an SVal to another, treating unknown and undefined values as
292// summing to UnknownVal. Used by 'computeOffset'.
294 SValBuilder &svalBuilder) {
295 // We treat UnknownVals and UndefinedVals the same here because we
296 // only care about computing offsets.
297 if (x.isUnknownOrUndef() || y.isUnknownOrUndef())
298 return UnknownVal();
299
300 return svalBuilder.evalBinOpNN(state, BO_Add, x.castAs<NonLoc>(),
301 y.castAs<NonLoc>(),
302 svalBuilder.getArrayIndexType());
303}
304
305/// Compute a raw byte offset from a base region. Used for array bounds
306/// checking.
307RegionRawOffsetV2 RegionRawOffsetV2::computeOffset(ProgramStateRef state,
308 SValBuilder &svalBuilder,
309 SVal location)
310{
311 const MemRegion *region = location.getAsRegion();
312 SVal offset = UndefinedVal();
313
314 while (region) {
315 switch (region->getKind()) {
316 default: {
317 if (const SubRegion *subReg = dyn_cast<SubRegion>(region)) {
318 offset = getValue(offset, svalBuilder);
319 if (!offset.isUnknownOrUndef())
320 return RegionRawOffsetV2(subReg, offset);
321 }
322 return RegionRawOffsetV2();
323 }
324 case MemRegion::ElementRegionKind: {
325 const ElementRegion *elemReg = cast<ElementRegion>(region);
326 SVal index = elemReg->getIndex();
327 if (!isa<NonLoc>(index))
328 return RegionRawOffsetV2();
329 QualType elemType = elemReg->getElementType();
330 // If the element is an incomplete type, go no further.
331 ASTContext &astContext = svalBuilder.getContext();
332 if (elemType->isIncompleteType())
333 return RegionRawOffsetV2();
334
335 // Update the offset.
336 offset = addValue(state,
337 getValue(offset, svalBuilder),
338 scaleValue(state,
339 index.castAs<NonLoc>(),
340 astContext.getTypeSizeInChars(elemType),
341 svalBuilder),
342 svalBuilder);
343
344 if (offset.isUnknownOrUndef())
345 return RegionRawOffsetV2();
346
347 region = elemReg->getSuperRegion();
348 continue;
349 }
350 }
351 }
352 return RegionRawOffsetV2();
353}
354
355void ento::registerArrayBoundCheckerV2(CheckerManager &mgr) {
356 mgr.registerChecker<ArrayBoundCheckerV2>();
357}
358
359bool ento::shouldRegisterArrayBoundCheckerV2(const CheckerManager &mgr) {
360 return true;
361}
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 ...
Definition: ASTContext.h:182
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.
Definition: CharUnits.h:38
QuantityType getQuantity() const
getQuantity - Get the raw integer representation of this quantity.
Definition: CharUnits.h:185
A (possibly-)qualified type.
Definition: Type.h:736
Stmt - This represents one statement.
Definition: Stmt.h:72
bool isIncompleteType(NamedDecl **Def=nullptr) const
Types are partitioned into 3 broad categories (C99 6.2.5p1): object types, function types,...
Definition: Type.cpp:2259
A record of the "type" of an APSInt, used for conversions.
Definition: APSIntType.h:19
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.
Definition: APSIntType.h:48
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.
Definition: MemRegion.h:1189
QualType getElementType() const
Definition: MemRegion.h:1213
NonLoc getIndex() const
Definition: MemRegion.h:1209
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:95
LLVM_ATTRIBUTE_RETURNS_NONNULL const MemSpaceRegion * getMemorySpace() const
Definition: MemRegion.cpp:1277
Kind getKind() const
Definition: MemRegion.h:173
MemSpaceRegion - A memory region that represents a "memory space"; for example, the set of global var...
Definition: MemRegion.h:204
NonLoc makeArrayIndex(uint64_t idx)
Definition: SValBuilder.h:263
ASTContext & getContext()
Definition: SValBuilder.h:136
nonloc::ConcreteInt makeIntVal(const IntegerLiteral *integer)
Definition: SValBuilder.h:269
QualType getArrayIndexType() const
Definition: SValBuilder.h:145
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
Definition: SValBuilder.h:141
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
Definition: SVals.h:72
bool isUndef() const
Definition: SVals.h:128
bool isUnknownOrUndef() const
Definition: SVals.h:132
std::optional< T > getAs() const
Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.
Definition: SVals.h:103
const MemRegion * getAsRegion() const
Definition: SVals.cpp:120
T castAs() const
Convert to the specified SVal type, asserting that this SVal is of the desired type.
Definition: SVals.h:99
SubRegion - A region that subsets another larger region.
Definition: MemRegion.h:442
LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getSuperRegion() const
Definition: MemRegion.h:455
Value representing integer constant.
Definition: SVals.h:329
const llvm::APSInt & getValue() const
Definition: SVals.h:333
Represents symbolic expression that isn't a location.
Definition: SVals.h:304
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.
Definition: Taint.cpp:147
DefinedOrUnknownSVal getDynamicExtent(ProgramStateRef State, const MemRegion *MR, SValBuilder &SVB)
@ C
Languages that the frontend can parse and compile.