/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //== ArrayBoundCheckerV2.cpp ------------------------------------*- C++ -*--==// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // |
10 | | // This file defines ArrayBoundCheckerV2, which is a path-sensitive check |
11 | | // which looks for an out-of-bound array element access. |
12 | | // |
13 | | //===----------------------------------------------------------------------===// |
14 | | |
15 | | #include "ClangSACheckers.h" |
16 | | #include "clang/AST/CharUnits.h" |
17 | | #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" |
18 | | #include "clang/StaticAnalyzer/Core/Checker.h" |
19 | | #include "clang/StaticAnalyzer/Core/CheckerManager.h" |
20 | | #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" |
21 | | #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" |
22 | | #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" |
23 | | #include "llvm/ADT/SmallString.h" |
24 | | #include "llvm/Support/raw_ostream.h" |
25 | | |
26 | | using namespace clang; |
27 | | using namespace ento; |
28 | | |
29 | | namespace { |
30 | | class ArrayBoundCheckerV2 : |
31 | | public Checker<check::Location> { |
32 | | mutable std::unique_ptr<BuiltinBug> BT; |
33 | | |
34 | | enum OOB_Kind { OOB_Precedes, OOB_Excedes, OOB_Tainted }; |
35 | | |
36 | | void reportOOB(CheckerContext &C, ProgramStateRef errorState, |
37 | | OOB_Kind kind) const; |
38 | | |
39 | | public: |
40 | | void checkLocation(SVal l, bool isLoad, const Stmt*S, |
41 | | CheckerContext &C) const; |
42 | | }; |
43 | | |
44 | | // FIXME: Eventually replace RegionRawOffset with this class. |
45 | | class RegionRawOffsetV2 { |
46 | | private: |
47 | | const SubRegion *baseRegion; |
48 | | SVal byteOffset; |
49 | | |
50 | | RegionRawOffsetV2() |
51 | 0 | : baseRegion(nullptr), byteOffset(UnknownVal()) {} |
52 | | |
53 | | public: |
54 | | RegionRawOffsetV2(const SubRegion* base, SVal offset) |
55 | 509 | : baseRegion(base), byteOffset(offset) {} |
56 | | |
57 | 1.47k | NonLoc getByteOffset() const { return byteOffset.castAs<NonLoc>(); } |
58 | 1.51k | const SubRegion *getRegion() const { return baseRegion; } |
59 | | |
60 | | static RegionRawOffsetV2 computeOffset(ProgramStateRef state, |
61 | | SValBuilder &svalBuilder, |
62 | | SVal location); |
63 | | |
64 | | void dump() const; |
65 | | void dumpToStream(raw_ostream &os) const; |
66 | | }; |
67 | | } |
68 | | |
69 | | static SVal computeExtentBegin(SValBuilder &svalBuilder, |
70 | 509 | const MemRegion *region) { |
71 | 509 | const MemSpaceRegion *SR = region->getMemorySpace(); |
72 | 509 | if (SR->getKind() == MemRegion::UnknownSpaceRegionKind) |
73 | 19 | return UnknownVal(); |
74 | 509 | else |
75 | 490 | return svalBuilder.makeZeroArrayIndex(); |
76 | 0 | } |
77 | | |
78 | | // TODO: once the constraint manager is smart enough to handle non simplified |
79 | | // symbolic expressions remove this function. Note that this can not be used in |
80 | | // the constraint manager as is, since this does not handle overflows. It is |
81 | | // safe to assume, however, that memory offsets will not overflow. |
82 | | static std::pair<NonLoc, nonloc::ConcreteInt> |
83 | | getSimplifiedOffsets(NonLoc offset, nonloc::ConcreteInt extent, |
84 | 965 | SValBuilder &svalBuilder) { |
85 | 965 | Optional<nonloc::SymbolVal> SymVal = offset.getAs<nonloc::SymbolVal>(); |
86 | 965 | if (SymVal && 965 SymVal->isExpression()32 ) { |
87 | 19 | if (const SymIntExpr *SIE19 = dyn_cast<SymIntExpr>(SymVal->getSymbol())) { |
88 | 17 | llvm::APSInt constant = |
89 | 17 | APSIntType(extent.getValue()).convert(SIE->getRHS()); |
90 | 17 | switch (SIE->getOpcode()) { |
91 | 15 | case BO_Mul: |
92 | 15 | // The constant should never be 0 here, since it the result of scaling |
93 | 15 | // based on the size of a type which is never 0. |
94 | 15 | if ((extent.getValue() % constant) != 0) |
95 | 0 | return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent); |
96 | 15 | else |
97 | 15 | return getSimplifiedOffsets( |
98 | 15 | nonloc::SymbolVal(SIE->getLHS()), |
99 | 15 | svalBuilder.makeIntVal(extent.getValue() / constant), |
100 | 15 | svalBuilder); |
101 | 0 | case BO_Add: |
102 | 0 | return getSimplifiedOffsets( |
103 | 0 | nonloc::SymbolVal(SIE->getLHS()), |
104 | 0 | svalBuilder.makeIntVal(extent.getValue() - constant), svalBuilder); |
105 | 2 | default: |
106 | 2 | break; |
107 | 950 | } |
108 | 950 | } |
109 | 19 | } |
110 | 950 | |
111 | 950 | return std::pair<NonLoc, nonloc::ConcreteInt>(offset, extent); |
112 | 950 | } |
113 | | |
114 | | void ArrayBoundCheckerV2::checkLocation(SVal location, bool isLoad, |
115 | | const Stmt* LoadS, |
116 | 509 | CheckerContext &checkerContext) const { |
117 | 509 | |
118 | 509 | // NOTE: Instead of using ProgramState::assumeInBound(), we are prototyping |
119 | 509 | // some new logic here that reasons directly about memory region extents. |
120 | 509 | // Once that logic is more mature, we can bring it back to assumeInBound() |
121 | 509 | // for all clients to use. |
122 | 509 | // |
123 | 509 | // The algorithm we are using here for bounds checking is to see if the |
124 | 509 | // memory access is within the extent of the base region. Since we |
125 | 509 | // have some flexibility in defining the base region, we can achieve |
126 | 509 | // various levels of conservatism in our buffer overflow checking. |
127 | 509 | ProgramStateRef state = checkerContext.getState(); |
128 | 509 | ProgramStateRef originalState = state; |
129 | 509 | |
130 | 509 | SValBuilder &svalBuilder = checkerContext.getSValBuilder(); |
131 | 509 | const RegionRawOffsetV2 &rawOffset = |
132 | 509 | RegionRawOffsetV2::computeOffset(state, svalBuilder, location); |
133 | 509 | |
134 | 509 | if (!rawOffset.getRegion()) |
135 | 0 | return; |
136 | 509 | |
137 | 509 | NonLoc rawOffsetVal = rawOffset.getByteOffset(); |
138 | 509 | |
139 | 509 | // CHECK LOWER BOUND: Is byteOffset < extent begin? |
140 | 509 | // If so, we are doing a load/store |
141 | 509 | // before the first valid offset in the memory region. |
142 | 509 | |
143 | 509 | SVal extentBegin = computeExtentBegin(svalBuilder, rawOffset.getRegion()); |
144 | 509 | |
145 | 509 | if (Optional<NonLoc> NV509 = extentBegin.getAs<NonLoc>()) { |
146 | 490 | if (NV->getAs<nonloc::ConcreteInt>()490 ) { |
147 | 490 | std::pair<NonLoc, nonloc::ConcreteInt> simplifiedOffsets = |
148 | 490 | getSimplifiedOffsets(rawOffset.getByteOffset(), |
149 | 490 | NV->castAs<nonloc::ConcreteInt>(), |
150 | 490 | svalBuilder); |
151 | 490 | rawOffsetVal = simplifiedOffsets.first; |
152 | 490 | *NV = simplifiedOffsets.second; |
153 | 490 | } |
154 | 490 | |
155 | 490 | SVal lowerBound = svalBuilder.evalBinOpNN(state, BO_LT, rawOffsetVal, *NV, |
156 | 490 | svalBuilder.getConditionType()); |
157 | 490 | |
158 | 490 | Optional<NonLoc> lowerBoundToCheck = lowerBound.getAs<NonLoc>(); |
159 | 490 | if (!lowerBoundToCheck) |
160 | 0 | return; |
161 | 490 | |
162 | 490 | ProgramStateRef state_precedesLowerBound, state_withinLowerBound; |
163 | 490 | std::tie(state_precedesLowerBound, state_withinLowerBound) = |
164 | 490 | state->assume(*lowerBoundToCheck); |
165 | 490 | |
166 | 490 | // Are we constrained enough to definitely precede the lower bound? |
167 | 490 | if (state_precedesLowerBound && 490 !state_withinLowerBound17 ) { |
168 | 12 | reportOOB(checkerContext, state_precedesLowerBound, OOB_Precedes); |
169 | 12 | return; |
170 | 12 | } |
171 | 478 | |
172 | 478 | // Otherwise, assume the constraint of the lower bound. |
173 | 490 | assert(state_withinLowerBound); |
174 | 478 | state = state_withinLowerBound; |
175 | 478 | } |
176 | 509 | |
177 | 497 | do 497 { |
178 | 497 | // CHECK UPPER BOUND: Is byteOffset >= extent(baseRegion)? If so, |
179 | 497 | // we are doing a load/store after the last valid offset. |
180 | 497 | DefinedOrUnknownSVal extentVal = |
181 | 497 | rawOffset.getRegion()->getExtent(svalBuilder); |
182 | 497 | if (!extentVal.getAs<NonLoc>()) |
183 | 2 | break; |
184 | 495 | |
185 | 495 | if (495 extentVal.getAs<nonloc::ConcreteInt>()495 ) { |
186 | 460 | std::pair<NonLoc, nonloc::ConcreteInt> simplifiedOffsets = |
187 | 460 | getSimplifiedOffsets(rawOffset.getByteOffset(), |
188 | 460 | extentVal.castAs<nonloc::ConcreteInt>(), |
189 | 460 | svalBuilder); |
190 | 460 | rawOffsetVal = simplifiedOffsets.first; |
191 | 460 | extentVal = simplifiedOffsets.second; |
192 | 460 | } |
193 | 495 | |
194 | 495 | SVal upperbound = svalBuilder.evalBinOpNN(state, BO_GE, rawOffsetVal, |
195 | 495 | extentVal.castAs<NonLoc>(), |
196 | 495 | svalBuilder.getConditionType()); |
197 | 495 | |
198 | 495 | Optional<NonLoc> upperboundToCheck = upperbound.getAs<NonLoc>(); |
199 | 495 | if (!upperboundToCheck) |
200 | 0 | break; |
201 | 495 | |
202 | 495 | ProgramStateRef state_exceedsUpperBound, state_withinUpperBound; |
203 | 495 | std::tie(state_exceedsUpperBound, state_withinUpperBound) = |
204 | 495 | state->assume(*upperboundToCheck); |
205 | 495 | |
206 | 495 | // If we are under constrained and the index variables are tainted, report. |
207 | 495 | if (state_exceedsUpperBound && 495 state_withinUpperBound25 ) { |
208 | 11 | if (state->isTainted(rawOffset.getByteOffset())11 ) { |
209 | 5 | reportOOB(checkerContext, state_exceedsUpperBound, OOB_Tainted); |
210 | 5 | return; |
211 | 5 | } |
212 | 484 | } else if (484 state_exceedsUpperBound484 ) { |
213 | 14 | // If we are constrained enough to definitely exceed the upper bound, |
214 | 14 | // report. |
215 | 14 | assert(!state_withinUpperBound); |
216 | 14 | reportOOB(checkerContext, state_exceedsUpperBound, OOB_Excedes); |
217 | 14 | return; |
218 | 14 | } |
219 | 476 | |
220 | 495 | assert(state_withinUpperBound); |
221 | 476 | state = state_withinUpperBound; |
222 | 476 | } |
223 | 476 | while (false); |
224 | 497 | |
225 | 478 | if (478 state != originalState478 ) |
226 | 6 | checkerContext.addTransition(state); |
227 | 509 | } |
228 | | |
229 | | void ArrayBoundCheckerV2::reportOOB(CheckerContext &checkerContext, |
230 | | ProgramStateRef errorState, |
231 | 31 | OOB_Kind kind) const { |
232 | 31 | |
233 | 31 | ExplodedNode *errorNode = checkerContext.generateErrorNode(errorState); |
234 | 31 | if (!errorNode) |
235 | 0 | return; |
236 | 31 | |
237 | 31 | if (31 !BT31 ) |
238 | 3 | BT.reset(new BuiltinBug(this, "Out-of-bound access")); |
239 | 31 | |
240 | 31 | // FIXME: This diagnostics are preliminary. We should get far better |
241 | 31 | // diagnostics for explaining buffer overruns. |
242 | 31 | |
243 | 31 | SmallString<256> buf; |
244 | 31 | llvm::raw_svector_ostream os(buf); |
245 | 31 | os << "Out of bound memory access "; |
246 | 31 | switch (kind) { |
247 | 12 | case OOB_Precedes: |
248 | 12 | os << "(accessed memory precedes memory block)"; |
249 | 12 | break; |
250 | 14 | case OOB_Excedes: |
251 | 14 | os << "(access exceeds upper limit of memory block)"; |
252 | 14 | break; |
253 | 5 | case OOB_Tainted: |
254 | 5 | os << "(index is tainted)"; |
255 | 5 | break; |
256 | 31 | } |
257 | 31 | |
258 | 31 | checkerContext.emitReport( |
259 | 31 | llvm::make_unique<BugReport>(*BT, os.str(), errorNode)); |
260 | 31 | } |
261 | | |
262 | 0 | LLVM_DUMP_METHOD void RegionRawOffsetV2::dump() const { |
263 | 0 | dumpToStream(llvm::errs()); |
264 | 0 | } |
265 | | |
266 | 0 | void RegionRawOffsetV2::dumpToStream(raw_ostream &os) const { |
267 | 0 | os << "raw_offset_v2{" << getRegion() << ',' << getByteOffset() << '}'; |
268 | 0 | } |
269 | | |
270 | | |
271 | | // Lazily computes a value to be used by 'computeOffset'. If 'val' |
272 | | // is unknown or undefined, we lazily substitute '0'. Otherwise, |
273 | | // return 'val'. |
274 | 588 | static inline SVal getValue(SVal val, SValBuilder &svalBuilder) { |
275 | 588 | return val.getAs<UndefinedVal>() ? svalBuilder.makeArrayIndex(0)509 : val79 ; |
276 | 588 | } |
277 | | |
278 | | // Scale a base value by a scaling factor, and return the scaled |
279 | | // value as an SVal. Used by 'computeOffset'. |
280 | | static inline SVal scaleValue(ProgramStateRef state, |
281 | | NonLoc baseVal, CharUnits scaling, |
282 | 79 | SValBuilder &sb) { |
283 | 79 | return sb.evalBinOpNN(state, BO_Mul, baseVal, |
284 | 79 | sb.makeArrayIndex(scaling.getQuantity()), |
285 | 79 | sb.getArrayIndexType()); |
286 | 79 | } |
287 | | |
288 | | // Add an SVal to another, treating unknown and undefined values as |
289 | | // summing to UnknownVal. Used by 'computeOffset'. |
290 | | static SVal addValue(ProgramStateRef state, SVal x, SVal y, |
291 | 79 | SValBuilder &svalBuilder) { |
292 | 79 | // We treat UnknownVals and UndefinedVals the same here because we |
293 | 79 | // only care about computing offsets. |
294 | 79 | if (x.isUnknownOrUndef() || 79 y.isUnknownOrUndef()79 ) |
295 | 0 | return UnknownVal(); |
296 | 79 | |
297 | 79 | return svalBuilder.evalBinOpNN(state, BO_Add, x.castAs<NonLoc>(), |
298 | 79 | y.castAs<NonLoc>(), |
299 | 79 | svalBuilder.getArrayIndexType()); |
300 | 79 | } |
301 | | |
302 | | /// Compute a raw byte offset from a base region. Used for array bounds |
303 | | /// checking. |
304 | | RegionRawOffsetV2 RegionRawOffsetV2::computeOffset(ProgramStateRef state, |
305 | | SValBuilder &svalBuilder, |
306 | | SVal location) |
307 | 509 | { |
308 | 509 | const MemRegion *region = location.getAsRegion(); |
309 | 509 | SVal offset = UndefinedVal(); |
310 | 509 | |
311 | 588 | while (region588 ) { |
312 | 588 | switch (region->getKind()) { |
313 | 509 | default: { |
314 | 509 | if (const SubRegion *subReg509 = dyn_cast<SubRegion>(region)) { |
315 | 509 | offset = getValue(offset, svalBuilder); |
316 | 509 | if (!offset.isUnknownOrUndef()) |
317 | 509 | return RegionRawOffsetV2(subReg, offset); |
318 | 0 | } |
319 | 0 | return RegionRawOffsetV2(); |
320 | 0 | } |
321 | 79 | case MemRegion::ElementRegionKind: { |
322 | 79 | const ElementRegion *elemReg = cast<ElementRegion>(region); |
323 | 79 | SVal index = elemReg->getIndex(); |
324 | 79 | if (!index.getAs<NonLoc>()) |
325 | 0 | return RegionRawOffsetV2(); |
326 | 79 | QualType elemType = elemReg->getElementType(); |
327 | 79 | // If the element is an incomplete type, go no further. |
328 | 79 | ASTContext &astContext = svalBuilder.getContext(); |
329 | 79 | if (elemType->isIncompleteType()) |
330 | 0 | return RegionRawOffsetV2(); |
331 | 79 | |
332 | 79 | // Update the offset. |
333 | 79 | offset = addValue(state, |
334 | 79 | getValue(offset, svalBuilder), |
335 | 79 | scaleValue(state, |
336 | 79 | index.castAs<NonLoc>(), |
337 | 79 | astContext.getTypeSizeInChars(elemType), |
338 | 79 | svalBuilder), |
339 | 79 | svalBuilder); |
340 | 79 | |
341 | 79 | if (offset.isUnknownOrUndef()) |
342 | 0 | return RegionRawOffsetV2(); |
343 | 79 | |
344 | 79 | region = elemReg->getSuperRegion(); |
345 | 79 | continue; |
346 | 79 | } |
347 | 588 | } |
348 | 588 | } |
349 | 0 | return RegionRawOffsetV2(); |
350 | 509 | } |
351 | | |
352 | 5 | void ento::registerArrayBoundCheckerV2(CheckerManager &mgr) { |
353 | 5 | mgr.registerChecker<ArrayBoundCheckerV2>(); |
354 | 5 | } |