From 37ac1c19bed7b7d22e9312dfa61e7a4506ed4e49 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bal=C3=A1zs=20K=C3=A9ri?= <1.int32@gmail.com> Date: Tue, 14 Apr 2020 09:20:22 +0200 Subject: [PATCH] [Analyzer][VLASize] Support multi-dimensional arrays. Summary: Check the size constraints for every (variable) dimension of the array. Try to compute array size by multiplying size for every dimension. Reviewers: Szelethus, martong, baloghadamsoftware, gamesh411 Reviewed By: Szelethus, martong Subscribers: rnkovacs, xazax.hun, baloghadamsoftware, szepet, a.sidorin, mikhail.ramalho, Szelethus, donat.nagy, dkrupp, gamesh411, Charusso, martong, ASDenysPetrov, cfe-commits Tags: #clang Differential Revision: https://reviews.llvm.org/D77305 --- .../lib/StaticAnalyzer/Checkers/VLASizeChecker.cpp | 178 +++++++++++++-------- clang/test/Analysis/vla.c | 44 ++++- 2 files changed, 150 insertions(+), 72 deletions(-) diff --git a/clang/lib/StaticAnalyzer/Checkers/VLASizeChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/VLASizeChecker.cpp index 21e8b96..0c7961a 100644 --- a/clang/lib/StaticAnalyzer/Checkers/VLASizeChecker.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/VLASizeChecker.cpp @@ -34,6 +34,9 @@ class VLASizeChecker : public Checker< check::PreStmt > { mutable std::unique_ptr BT; enum VLASize_Kind { VLA_Garbage, VLA_Zero, VLA_Tainted, VLA_Negative }; + ProgramStateRef checkVLASize(CheckerContext &C, ProgramStateRef State, + const Expr *SizeE) const; + void reportBug(VLASize_Kind Kind, const Expr *SizeE, ProgramStateRef State, CheckerContext &C, std::unique_ptr Visitor = nullptr) const; @@ -43,6 +46,65 @@ public: }; } // end anonymous namespace +ProgramStateRef VLASizeChecker::checkVLASize(CheckerContext &C, + ProgramStateRef State, + const Expr *SizeE) const { + SVal SizeV = C.getSVal(SizeE); + + if (SizeV.isUndef()) { + reportBug(VLA_Garbage, SizeE, State, C); + return nullptr; + } + + // See if the size value is known. It can't be undefined because we would have + // warned about that already. + if (SizeV.isUnknown()) + return nullptr; + + // Check if the size is tainted. + if (isTainted(State, SizeV)) { + reportBug(VLA_Tainted, SizeE, nullptr, C, + std::make_unique(SizeV)); + return nullptr; + } + + // Check if the size is zero. + DefinedSVal SizeD = SizeV.castAs(); + + ProgramStateRef StateNotZero, StateZero; + std::tie(StateNotZero, StateZero) = State->assume(SizeD); + + if (StateZero && !StateNotZero) { + reportBug(VLA_Zero, SizeE, StateZero, C); + return nullptr; + } + + // From this point on, assume that the size is not zero. + State = StateNotZero; + + // Check if the size is negative. + SValBuilder &SVB = C.getSValBuilder(); + + QualType SizeTy = SizeE->getType(); + DefinedOrUnknownSVal Zero = SVB.makeZeroVal(SizeTy); + + SVal LessThanZeroVal = SVB.evalBinOp(State, BO_LT, SizeD, Zero, SizeTy); + if (Optional LessThanZeroDVal = + LessThanZeroVal.getAs()) { + ConstraintManager &CM = C.getConstraintManager(); + ProgramStateRef StatePos, StateNeg; + + std::tie(StateNeg, StatePos) = CM.assumeDual(State, *LessThanZeroDVal); + if (StateNeg && !StatePos) { + reportBug(VLA_Negative, SizeE, State, C); // FIXME: StateNeg ? + return nullptr; + } + State = StatePos; + } + + return State; +} + void VLASizeChecker::reportBug( VLASize_Kind Kind, const Expr *SizeE, ProgramStateRef State, CheckerContext &C, std::unique_ptr Visitor) const { @@ -89,98 +151,72 @@ void VLASizeChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const { return; ASTContext &Ctx = C.getASTContext(); + SValBuilder &SVB = C.getSValBuilder(); + ProgramStateRef State = C.getState(); + const VariableArrayType *VLA = Ctx.getAsVariableArrayType(VD->getType()); if (!VLA) return; - // FIXME: Handle multi-dimensional VLAs. - const Expr *SE = VLA->getSizeExpr(); - ProgramStateRef state = C.getState(); - SVal sizeV = C.getSVal(SE); - - if (sizeV.isUndef()) { - reportBug(VLA_Garbage, SE, state, C); - return; - } - - // See if the size value is known. It can't be undefined because we would have - // warned about that already. - if (sizeV.isUnknown()) - return; - - // Check if the size is tainted. - if (isTainted(state, sizeV)) { - reportBug(VLA_Tainted, SE, nullptr, C, - std::make_unique(sizeV)); - return; - } - - // Check if the size is zero. - DefinedSVal sizeD = sizeV.castAs(); - - ProgramStateRef stateNotZero, stateZero; - std::tie(stateNotZero, stateZero) = state->assume(sizeD); - - if (stateZero && !stateNotZero) { - reportBug(VLA_Zero, SE, stateZero, C); - return; - } - - // From this point on, assume that the size is not zero. - state = stateNotZero; + llvm::SmallVector VLASizes; + const VariableArrayType *VLALast = nullptr; + // Walk over the VLAs for every dimension until a non-VLA is found. + // Collect the sizes in VLASizes, put the most inner VLA to `VLALast`. + // In "vla[x][2][y][3]" this will be the array for index "y". + // There is a VariableArrayType for every dimension (here "x", "2", "y") + // until a non-vla is found. + while (VLA) { + const Expr *SizeE = VLA->getSizeExpr(); + State = checkVLASize(C, State, SizeE); + if (!State) + return; + VLASizes.push_back(SizeE); + VLALast = VLA; + VLA = Ctx.getAsVariableArrayType(VLA->getElementType()); + }; + assert(VLALast && + "Array should have at least one variably-modified dimension."); // VLASizeChecker is responsible for defining the extent of the array being // declared. We do this by multiplying the array length by the element size, // then matching that with the array region's extent symbol. - // Check if the size is negative. - SValBuilder &svalBuilder = C.getSValBuilder(); - - QualType Ty = SE->getType(); - DefinedOrUnknownSVal Zero = svalBuilder.makeZeroVal(Ty); - - SVal LessThanZeroVal = svalBuilder.evalBinOp(state, BO_LT, sizeD, Zero, Ty); - if (Optional LessThanZeroDVal = - LessThanZeroVal.getAs()) { - ConstraintManager &CM = C.getConstraintManager(); - ProgramStateRef StatePos, StateNeg; - - std::tie(StateNeg, StatePos) = CM.assumeDual(state, *LessThanZeroDVal); - if (StateNeg && !StatePos) { - reportBug(VLA_Negative, SE, state, C); + CanQualType SizeTy = Ctx.getSizeType(); + // Get the element size. + CharUnits EleSize = Ctx.getTypeSizeInChars(VLALast->getElementType()); + NonLoc ArraySize = + SVB.makeIntVal(EleSize.getQuantity(), SizeTy).castAs(); + + for (const Expr *SizeE : VLASizes) { + auto SizeD = C.getSVal(SizeE).castAs(); + // Convert the array length to size_t. + NonLoc IndexLength = + SVB.evalCast(SizeD, SizeTy, SizeE->getType()).castAs(); + // Multiply the array length by the element size. + SVal Mul = SVB.evalBinOpNN(State, BO_Mul, ArraySize, IndexLength, SizeTy); + if (auto MulNonLoc = Mul.getAs()) { + ArraySize = *MulNonLoc; + } else { + // Extent could not be determined. + // The state was probably still updated by the validation checks. + C.addTransition(State); return; } - state = StatePos; } - // Convert the array length to size_t. - QualType SizeTy = Ctx.getSizeType(); - NonLoc ArrayLength = - svalBuilder.evalCast(sizeD, SizeTy, SE->getType()).castAs(); - - // Get the element size. - CharUnits EleSize = Ctx.getTypeSizeInChars(VLA->getElementType()); - SVal EleSizeVal = svalBuilder.makeIntVal(EleSize.getQuantity(), SizeTy); - - // Multiply the array length by the element size. - SVal ArraySizeVal = svalBuilder.evalBinOpNN( - state, BO_Mul, ArrayLength, EleSizeVal.castAs(), SizeTy); - // Finally, assume that the array's size matches the given size. const LocationContext *LC = C.getLocationContext(); DefinedOrUnknownSVal DynSize = - getDynamicSize(state, state->getRegion(VD, LC), svalBuilder); + getDynamicSize(State, State->getRegion(VD, LC), SVB); - DefinedOrUnknownSVal ArraySize = ArraySizeVal.castAs(); - DefinedOrUnknownSVal sizeIsKnown = - svalBuilder.evalEQ(state, DynSize, ArraySize); - state = state->assume(sizeIsKnown, true); + DefinedOrUnknownSVal SizeIsKnown = SVB.evalEQ(State, DynSize, ArraySize); + State = State->assume(SizeIsKnown, true); // Assume should not fail at this point. - assert(state); + assert(State); // Remember our assumptions! - C.addTransition(state); + C.addTransition(State); } void ento::registerVLASizeChecker(CheckerManager &mgr) { diff --git a/clang/test/Analysis/vla.c b/clang/test/Analysis/vla.c index eb06c24..f163e49 100644 --- a/clang/test/Analysis/vla.c +++ b/clang/test/Analysis/vla.c @@ -1,4 +1,8 @@ -// RUN: %clang_analyze_cc1 -analyzer-checker=core -verify %s +// RUN: %clang_analyze_cc1 -analyzer-checker=core -analyzer-checker=debug.ExprInspection -verify %s + +typedef unsigned long size_t; +size_t clang_analyzer_getExtent(void *); +void clang_analyzer_eval(int); // Zero-sized VLAs. void check_zero_sized_VLA(int x) { @@ -84,3 +88,41 @@ void check_negative_sized_VLA_11(int x) { if (x > 0) check_negative_sized_VLA_11_sub(x); } + +// Multi-dimensional arrays. + +void check_zero_sized_VLA_multi1(int x) { + if (x) + return; + + int vla[10][x]; // expected-warning{{Declared variable-length array (VLA) has zero size}} +} + +void check_zero_sized_VLA_multi2(int x, int y) { + if (x) + return; + + int vla[y][x]; // expected-warning{{Declared variable-length array (VLA) has zero size}} +} + +// Check the extent. + +void check_VLA_extent() { + int x = 3; + + int vla1[x]; + clang_analyzer_eval(clang_analyzer_getExtent(&vla1) == x * sizeof(int)); + // expected-warning@-1{{TRUE}} + + int vla2[x][2]; + clang_analyzer_eval(clang_analyzer_getExtent(&vla2) == x * 2 * sizeof(int)); + // expected-warning@-1{{TRUE}} + + int vla2m[2][x]; + clang_analyzer_eval(clang_analyzer_getExtent(&vla2m) == 2 * x * sizeof(int)); + // expected-warning@-1{{TRUE}} + + int vla3m[2][x][4]; + clang_analyzer_eval(clang_analyzer_getExtent(&vla3m) == 2 * x * 4 * sizeof(int)); + // expected-warning@-1{{TRUE}} +} -- 2.7.4