Author: Balázs Kéri Date: 2020-05-19T09:44:46+02:00 New Revision: 51bb2128ef03985fddf2a84f17d3276f4ae2c6ad
URL: https://github.com/llvm/llvm-project/commit/51bb2128ef03985fddf2a84f17d3276f4ae2c6ad DIFF: https://github.com/llvm/llvm-project/commit/51bb2128ef03985fddf2a84f17d3276f4ae2c6ad.diff LOG: [Analyzer][VLASizeChecker] Check for VLA size overflow. Summary: Variable-length array (VLA) should have a size that fits into a size_t value. According to the standard: "std::size_t can store the maximum size of a theoretically possible object of any type (including array)" (this is applied to C too). The size expression is evaluated at the definition of the VLA type even if this is a typedef. The evaluation of the size expression in itself might cause problems if it overflows. Reviewers: Szelethus, baloghadamsoftware, martong, gamesh411 Reviewed By: Szelethus, martong, gamesh411 Subscribers: whisperity, 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/D79330 Added: clang/test/Analysis/vla-overflow.c Modified: clang/lib/StaticAnalyzer/Checkers/VLASizeChecker.cpp Removed: ################################################################################ diff --git a/clang/lib/StaticAnalyzer/Checkers/VLASizeChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/VLASizeChecker.cpp index 3bd2520f013a..de487042fb8a 100644 --- a/clang/lib/StaticAnalyzer/Checkers/VLASizeChecker.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/VLASizeChecker.cpp @@ -34,24 +34,24 @@ class VLASizeChecker : public Checker<check::PreStmt<DeclStmt>, check::PreStmt<UnaryExprOrTypeTraitExpr>> { mutable std::unique_ptr<BugType> BT; - enum VLASize_Kind { VLA_Garbage, VLA_Zero, VLA_Tainted, VLA_Negative }; + enum VLASize_Kind { + VLA_Garbage, + VLA_Zero, + VLA_Tainted, + VLA_Negative, + VLA_Overflow + }; /// Check a VLA for validity. - /// Every dimension of the array is checked for validity, and - /// dimension sizes are collected into 'VLASizes'. 'VLALast' is set to the - /// innermost VLA that was encountered. - /// In "int vla[x][2][y][3]" this will be the array for index "y" (with type - /// int[3]). 'VLASizes' contains 'x', '2', and 'y'. Returns null or a new - /// state where the size is validated for every dimension. - ProgramStateRef checkVLA(CheckerContext &C, ProgramStateRef State, - const VariableArrayType *VLA, - const VariableArrayType *&VLALast, - llvm::SmallVector<const Expr *, 2> &VLASizes) const; - - /// Check one VLA dimension for validity. + /// Every dimension of the array and the total size is checked for validity. /// Returns null or a new state where the size is validated. - ProgramStateRef checkVLASize(CheckerContext &C, ProgramStateRef State, - const Expr *SizeE) const; + /// 'ArraySize' will contain SVal that refers to the total size (in char) + /// of the array. + ProgramStateRef checkVLA(CheckerContext &C, ProgramStateRef State, + const VariableArrayType *VLA, SVal &ArraySize) const; + /// Check a single VLA index size expression for validity. + ProgramStateRef checkVLAIndexSize(CheckerContext &C, ProgramStateRef State, + const Expr *SizeE) const; void reportBug(VLASize_Kind Kind, const Expr *SizeE, ProgramStateRef State, CheckerContext &C, @@ -64,20 +64,25 @@ class VLASizeChecker }; } // end anonymous namespace -ProgramStateRef -VLASizeChecker::checkVLA(CheckerContext &C, ProgramStateRef State, - const VariableArrayType *VLA, - const VariableArrayType *&VLALast, - llvm::SmallVector<const Expr *, 2> &VLASizes) const { +ProgramStateRef VLASizeChecker::checkVLA(CheckerContext &C, + ProgramStateRef State, + const VariableArrayType *VLA, + SVal &ArraySize) const { assert(VLA && "Function should be called with non-null VLA argument."); - VLALast = nullptr; + const VariableArrayType *VLALast = nullptr; + llvm::SmallVector<const Expr *, 2> VLASizes; + // Walk over the VLAs for every dimension until a non-VLA is found. // There is a VariableArrayType for every dimension (fixed or variable) until // the most inner array that is variably modified. + // Dimension sizes are collected into 'VLASizes'. 'VLALast' is set to the + // innermost VLA that was encountered. + // In "int vla[x][2][y][3]" this will be the array for index "y" (with type + // int[3]). 'VLASizes' contains 'x', '2', and 'y'. while (VLA) { const Expr *SizeE = VLA->getSizeExpr(); - State = checkVLASize(C, State, SizeE); + State = checkVLAIndexSize(C, State, SizeE); if (!State) return nullptr; VLASizes.push_back(SizeE); @@ -87,12 +92,61 @@ VLASizeChecker::checkVLA(CheckerContext &C, ProgramStateRef State, assert(VLALast && "Array should have at least one variably-modified dimension."); + ASTContext &Ctx = C.getASTContext(); + SValBuilder &SVB = C.getSValBuilder(); + CanQualType SizeTy = Ctx.getSizeType(); + uint64_t SizeMax = + SVB.getBasicValueFactory().getMaxValue(SizeTy).getZExtValue(); + + // Get the element size. + CharUnits EleSize = Ctx.getTypeSizeInChars(VLALast->getElementType()); + NonLoc ArrSize = + SVB.makeIntVal(EleSize.getQuantity(), SizeTy).castAs<NonLoc>(); + + // Try to calculate the known real size of the array in KnownSize. + uint64_t KnownSize = 0; + if (const llvm::APSInt *KV = SVB.getKnownValue(State, ArrSize)) + KnownSize = KV->getZExtValue(); + + for (const Expr *SizeE : VLASizes) { + auto SizeD = C.getSVal(SizeE).castAs<DefinedSVal>(); + // Convert the array length to size_t. + NonLoc IndexLength = + SVB.evalCast(SizeD, SizeTy, SizeE->getType()).castAs<NonLoc>(); + // Multiply the array length by the element size. + SVal Mul = SVB.evalBinOpNN(State, BO_Mul, ArrSize, IndexLength, SizeTy); + if (auto MulNonLoc = Mul.getAs<NonLoc>()) + ArrSize = *MulNonLoc; + else + // Extent could not be determined. + return State; + + if (const llvm::APSInt *IndexLVal = SVB.getKnownValue(State, IndexLength)) { + // Check if the array size will overflow. + // Size overflow check does not work with symbolic expressions because a + // overflow situation can not be detected easily. + uint64_t IndexL = IndexLVal->getZExtValue(); + assert(IndexL > 0 && "Index length should have been checked for zero."); + if (KnownSize <= SizeMax / IndexL) { + KnownSize *= IndexL; + } else { + // Array size does not fit into size_t. + reportBug(VLA_Overflow, SizeE, State, C); + return nullptr; + } + } else { + KnownSize = 0; + } + } + + ArraySize = ArrSize; + return State; } -ProgramStateRef VLASizeChecker::checkVLASize(CheckerContext &C, - ProgramStateRef State, - const Expr *SizeE) const { +ProgramStateRef VLASizeChecker::checkVLAIndexSize(CheckerContext &C, + ProgramStateRef State, + const Expr *SizeE) const { SVal SizeV = C.getSVal(SizeE); if (SizeV.isUndef()) { @@ -140,7 +194,7 @@ ProgramStateRef VLASizeChecker::checkVLASize(CheckerContext &C, std::tie(StateNeg, StatePos) = CM.assumeDual(State, *LessThanZeroDVal); if (StateNeg && !StatePos) { - reportBug(VLA_Negative, SizeE, State, C); // FIXME: StateNeg ? + reportBug(VLA_Negative, SizeE, State, C); return nullptr; } State = StatePos; @@ -177,6 +231,9 @@ void VLASizeChecker::reportBug( case VLA_Negative: os << "has negative size"; break; + case VLA_Overflow: + os << "has too large size"; + break; } auto report = std::make_unique<PathSensitiveBugReport>(*BT, os.str(), N); @@ -209,53 +266,36 @@ void VLASizeChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const { return; // Check the VLA sizes for validity. - llvm::SmallVector<const Expr *, 2> VLASizes; - const VariableArrayType *VLALast = nullptr; - State = checkVLA(C, State, VLA, VLALast, VLASizes); + SVal ArraySize; + + State = checkVLA(C, State, VLA, ArraySize); if (!State) return; - if (!VD) + auto ArraySizeNL = ArraySize.getAs<NonLoc>(); + if (!ArraySizeNL) { + // Array size could not be determined but state may contain new assumptions. + C.addTransition(State); return; + } // 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. - CanQualType SizeTy = Ctx.getSizeType(); - // Get the element size. - CharUnits EleSize = Ctx.getTypeSizeInChars(VLALast->getElementType()); - NonLoc ArraySize = - SVB.makeIntVal(EleSize.getQuantity(), SizeTy).castAs<NonLoc>(); - - for (const Expr *SizeE : VLASizes) { - auto SizeD = C.getSVal(SizeE).castAs<DefinedSVal>(); - // Convert the array length to size_t. - NonLoc IndexLength = - SVB.evalCast(SizeD, SizeTy, SizeE->getType()).castAs<NonLoc>(); - // Multiply the array length by the element size. - SVal Mul = SVB.evalBinOpNN(State, BO_Mul, ArraySize, IndexLength, SizeTy); - if (auto MulNonLoc = Mul.getAs<NonLoc>()) { - ArraySize = *MulNonLoc; - } else { - // Extent could not be determined. - // The state was probably still updated by the validation checks. - C.addTransition(State); - return; - } - } - - // Finally, assume that the array's size matches the given size. - const LocationContext *LC = C.getLocationContext(); - DefinedOrUnknownSVal DynSize = - getDynamicSize(State, State->getRegion(VD, LC), SVB); + if (VD) { + // Assume that the array's size matches the region size. + const LocationContext *LC = C.getLocationContext(); + DefinedOrUnknownSVal DynSize = + getDynamicSize(State, State->getRegion(VD, LC), SVB); - DefinedOrUnknownSVal SizeIsKnown = SVB.evalEQ(State, DynSize, ArraySize); - State = State->assume(SizeIsKnown, true); + DefinedOrUnknownSVal SizeIsKnown = SVB.evalEQ(State, DynSize, *ArraySizeNL); + State = State->assume(SizeIsKnown, true); - // Assume should not fail at this point. - assert(State); + // Assume should not fail at this point. + assert(State); + } // Remember our assumptions! C.addTransition(State); @@ -271,17 +311,15 @@ void VLASizeChecker::checkPreStmt(const UnaryExprOrTypeTraitExpr *UETTE, if (!UETTE->isArgumentType()) return; - const VariableArrayType *VLA = - C.getASTContext().getAsVariableArrayType(UETTE->getTypeOfArgument()); + const VariableArrayType *VLA = C.getASTContext().getAsVariableArrayType( + UETTE->getTypeOfArgument().getCanonicalType()); // Ensure that the type is a VLA. if (!VLA) return; ProgramStateRef State = C.getState(); - - llvm::SmallVector<const Expr *, 2> VLASizes; - const VariableArrayType *VLALast = nullptr; - State = checkVLA(C, State, VLA, VLALast, VLASizes); + SVal ArraySize; + State = checkVLA(C, State, VLA, ArraySize); if (!State) return; diff --git a/clang/test/Analysis/vla-overflow.c b/clang/test/Analysis/vla-overflow.c new file mode 100644 index 000000000000..8c9c626bc04c --- /dev/null +++ b/clang/test/Analysis/vla-overflow.c @@ -0,0 +1,25 @@ +// RUN: %clang_analyze_cc1 -triple x86_64-pc-linux-gnu -analyzer-checker=core -verify %s + +typedef unsigned long size_t; +#define BIGINDEX 65536U + +size_t check_VLA_overflow_sizeof(unsigned int x) { + if (x == BIGINDEX) { + // We expect here that size_t is a 64 bit value. + // Size of this array should be the first to overflow. + size_t s = sizeof(char[x][x][x][x]); // expected-warning{{Declared variable-length array (VLA) has too large size [core.VLASize]}} + return s; + } + return 0; +} + +void check_VLA_overflow_typedef() { + unsigned int x = BIGINDEX; + typedef char VLA[x][x][x][x]; // expected-warning{{Declared variable-length array (VLA) has too large size [core.VLASize]}} +} + +void check_VLA_no_overflow() { + unsigned int x = BIGINDEX; + typedef char VLA[x][x][x][x - 1]; + typedef char VLA1[0xffffffffu]; +} _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
