diff --git a/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td b/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td --- a/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td +++ b/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -613,6 +613,12 @@ Dependencies<[IteratorModeling]>, Documentation; +def SufficientSizeArrayIndexingChecker : Checker<"SufficientSizeArrayIndexing">, + HelpText<"Checks for indexing of an array, where the type of the index is " + "not sufficiently large to cover the possible index range of the " + "whole array.">, + Documentation; + } // end: "alpha.cplusplus" diff --git a/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt b/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt --- a/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt +++ b/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt @@ -88,6 +88,7 @@ RunLoopAutoreleaseLeakChecker.cpp SimpleStreamChecker.cpp SmartPtrModeling.cpp + SufficientSizeArrayIndexingChecker.cpp StackAddrEscapeChecker.cpp StdLibraryFunctionsChecker.cpp StreamChecker.cpp diff --git a/clang/lib/StaticAnalyzer/Checkers/SufficientSizeArrayIndexingChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/SufficientSizeArrayIndexingChecker.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/StaticAnalyzer/Checkers/SufficientSizeArrayIndexingChecker.cpp @@ -0,0 +1,165 @@ +// SufficientSizeArrayIndexingChecker.cpp ---------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This checker checks for indexing an array with integer types that are not +// sufficiently large in size to cover the array. +// +//===----------------------------------------------------------------------===// + +#include "clang/AST/TypeOrdering.h" +#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" +#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" +#include "clang/StaticAnalyzer/Core/Checker.h" +#include "clang/StaticAnalyzer/Core/CheckerManager.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" + +using namespace clang; +using namespace clang::ento; + +namespace { +class SufficientSizeArrayIndexingChecker + : public Checker> { + mutable llvm::DenseMap BugTypeCache; + BugType &GetBugTypeForType(const QualType T) const; + +public: + void checkPreStmt(const ArraySubscriptExpr *ASE, CheckerContext &C) const; +}; +} // end anonymous namespace + +/** + * Helper method to get the cached BugType for the QualType used for indexing. + * In case of a cache miss create the corresponding BugType, and cache it in + * case we encounter it later on. + */ +BugType & +SufficientSizeArrayIndexingChecker::GetBugTypeForType(const QualType T) const { + auto BT = BugTypeCache.find(T); + // If we have already encountered the type, the BugType is cached. + if (BT != BugTypeCache.end()) + return BT->getSecond(); + // Store the BugType into the cache. + BugTypeCache.insert(std::make_pair( + T, + BuiltinBug{this, (Twine("Indexing array with type '") + T.getAsString() + + "' cannot cover the whole range of the array's " + "index set, which may result in memory waste in form " + "of unindexable elements. " + "Consider using a type with greater maximum " + "value.") + .str() + .c_str()})); + return BugTypeCache.find(T)->getSecond(); +} + +/** + * Main entrypoint of the checker. The checker analyzes array indexing + * operations (expression of type ArraySubscriptExpr), and tries to determine + * the maximum possible value of the indexing type. Then it tries to reason + * about wheter this maximum is big enough to actually access every element of + * the array. To determine the size of the array, symbolic execution is used. + * This way, dynamically allocated arrays can also be checked. + */ +void SufficientSizeArrayIndexingChecker::checkPreStmt( + const ArraySubscriptExpr *ASE, CheckerContext &C) const { + const auto *Base = ASE->getBase(); + const auto *Index = ASE->getIdx(); + const auto IndexType = Index->getType(); + // Should not warn on literal index expressions. + if (dyn_cast(Index->IgnoreParenCasts())) + return; + // Get the maximal value of the index type. + const auto MaxIndexValue = + llvm::APSInt::getMaxValue(C.getASTContext().getIntWidth(IndexType), + IndexType->isUnsignedIntegerType()); + const nonloc::ConcreteInt MaxIndexValueSVal(MaxIndexValue); + // Get the symbolic representation of the array. This is needed to reason + // about the underlying memory regions. + const auto BaseSVal = C.getSVal(Base); + // Try to get the memory region associated with the base of the + // ArraySubscriptExpr. + const auto *BaseMemRegion = BaseSVal.getAsRegion(); + // If no memory is associated with the expression the checker exits early. + if (!BaseMemRegion) + return; + // In order to get the extent try to cast the regions to SubRegion type. + const auto *BaseSubRegion = dyn_cast(BaseMemRegion); + if (!BaseSubRegion) + return; + // Get the memory region of the whole array, because BaseMemRegion only + // contains the first element. + const auto *SuperMemRegion = BaseSubRegion->getSuperRegion(); + // If the parent region is the same as the base we definitely do not have an + // array indexing situation. + if (BaseMemRegion == SuperMemRegion) + return; + const auto *SuperSubRegion = dyn_cast(SuperMemRegion); + // The checker has to access the extent of both the sub and the superregion. + if (!SuperSubRegion) + return; + const auto State = C.getState(); + auto &SValBuilder = C.getSValBuilder(); + // Try to reason about the number of elements in the array. + // RegionStore has a getSizeInElements method which assumes the value too + // eagerly, so this leaner, and more general implementation is used instead. + const auto BaseRegionSize = BaseSubRegion->getExtent(SValBuilder); + const auto SuperRegionSize = SuperSubRegion->getExtent(SValBuilder); + const auto SizeInElements = + SValBuilder.evalBinOp(State, BO_Div, SuperRegionSize, BaseRegionSize, + C.getASTContext().getSizeType()); + if (!SizeInElements.isConstant()) + return; + // The criterium for correctness is: the size of the array minus one should be + // lesser than or equal to the maximum positive value of the indextype. + // Symbolic execution is used all the way to ensure maximal coverage of + // possible cases. + const auto Constant1SVal = SValBuilder.makeIntVal(1, true); + const auto NumArrayElemsMinusOne = + SValBuilder.evalBinOp(State, BO_Sub, SizeInElements, Constant1SVal, + C.getASTContext().UnsignedLongLongTy); + if (NumArrayElemsMinusOne.isUnknownOrUndef()) + return; + const auto TypeCanIndexEveryElement = SValBuilder.evalBinOp( + State, BO_LE, NumArrayElemsMinusOne, MaxIndexValueSVal, IndexType); + // Determine wheter we can reason about the value of the constructed symbolic + // expression. + if (TypeCanIndexEveryElement.isUnknownOrUndef()) + return; + // Make an assumption on both possibilities, namely that the size + // of the array minus one is smaller than the maximum value of the index type + // (meaning that for every element there exists an index through which it can + // be accessed), and the alternative, that it is greater of equal. + const auto AssumptionPair = + State->assume(TypeCanIndexEveryElement.castAs()); + // To avoid false positives the checker is conservative when considering the + // possibily of correct indexing. If the there is a chance that the indexing + // can be correct or the incorrect case is not certain, there will be no + // warning emitted. + if (AssumptionPair.first && !AssumptionPair.second) + return; + // The analysis can continue onward even if an error was found. + const auto *N = C.generateNonFatalErrorNode(); + if (!N) + return; + // Get the cached BugType, its message is specific to the index type. + auto &BT = GetBugTypeForType(IndexType); + // Report the error. + auto R = std::make_unique(BT, BT.getDescription(), N); + R->addRange(Index->getSourceRange()); + C.emitReport(std::move(R)); +} + +void ento::registerSufficientSizeArrayIndexingChecker(CheckerManager &Mgr) { + Mgr.registerChecker(); +} + +bool ento::shouldRegisterSufficientSizeArrayIndexingChecker( + const LangOptions &LO) { + return true; +} diff --git a/clang/test/Analysis/sufficient-size-array-indexing-32bit.c b/clang/test/Analysis/sufficient-size-array-indexing-32bit.c new file mode 100644 --- /dev/null +++ b/clang/test/Analysis/sufficient-size-array-indexing-32bit.c @@ -0,0 +1,140 @@ +// RUN: %clang_analyze_cc1 -triple i386 -analyzer-checker=core,alpha.cplusplus.SufficientSizeArrayIndexing %s -verify + +#include "Inputs/system-header-simulator.h" + +const unsigned long long one_byte_signed_max = (1ULL << 7) - 1; +const unsigned long long two_byte_signed_max = (1ULL << 15) - 1; +const unsigned long long four_byte_signed_max = (1ULL << 31) - 1; + +const unsigned long long one_byte_unsigned_max = (1ULL << 8) - 1; +const unsigned long long two_byte_unsigned_max = (1ULL << 16) - 1; +const unsigned long long four_byte_unsigned_max = (1ULL << 32) - 1; + +char smaller_than_1byte_signed_range[one_byte_signed_max]; +char exactly_1byte_signed_range[one_byte_signed_max + 1]; +char greater_than_1byte_signed_range[one_byte_signed_max + 2]; + +char smaller_than_2byte_signed_range[two_byte_signed_max]; +char exactly_2byte_signed_range[two_byte_signed_max + 1]; +char greater_than_2byte_signed_range[two_byte_signed_max + 2]; + +char smaller_than_4byte_signed_range[four_byte_signed_max]; +char exactly_4byte_signed_range[four_byte_signed_max + 1]; +char greater_than_4byte_signed_range[four_byte_signed_max + 2]; + +char smaller_than_1byte_unsigned_range[one_byte_unsigned_max]; +char exactly_1byte_unsigned_range[one_byte_unsigned_max + 1]; +char greater_than_1byte_unsigned_range[one_byte_unsigned_max + 2]; + +char smaller_than_2byte_unsigned_range[two_byte_unsigned_max]; +char exactly_2byte_unsigned_range[two_byte_unsigned_max + 1]; +char greater_than_2byte_unsigned_range[two_byte_unsigned_max + 2]; + +char smaller_than_4byte_unsigned_range[four_byte_unsigned_max]; + +const char one_byte_signed_index = 1; // sizeof(char) == 1 +const short two_byte_signed_index = 1; // sizeof(short) == 2 +const int four_byte_signed_index = 1; // sizeof(int) == 4 + +const unsigned char one_byte_unsigned_index = 1; +const unsigned short two_byte_unsigned_index = 1; +const unsigned int four_byte_unsigned_index = 1; + +void ignore_literal_indexing() { + char a = exactly_4byte_signed_range[32]; // nowarning +} + +void ignore_literal_indexing_with_parens() { + char a = exactly_4byte_signed_range[(32)]; // nowarning +} + +void range_check_one_byte_index() { + char r; + char *pr = &r; + *pr = smaller_than_1byte_signed_range[one_byte_signed_index]; // nowarning + *pr = exactly_1byte_signed_range[one_byte_signed_index]; // nowarning + *pr = greater_than_1byte_signed_range[one_byte_signed_index]; // expected-warning{{Indexing array with type 'char' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} + *pr = smaller_than_1byte_unsigned_range[one_byte_unsigned_index]; // nowarning + *pr = exactly_1byte_unsigned_range[one_byte_unsigned_index]; // nowarning + *pr = greater_than_1byte_unsigned_range[one_byte_unsigned_index]; // expected-warning{{Indexing array with type 'unsigned char' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} +} + +void range_check_two_byte_index() { + char r; + char *pr = &r; + *pr = smaller_than_2byte_signed_range[two_byte_signed_index]; // nowarning + *pr = exactly_2byte_signed_range[two_byte_signed_index]; // nowarning + *pr = greater_than_2byte_signed_range[two_byte_signed_index]; // expected-warning{{Indexing array with type 'short' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} + *pr = smaller_than_2byte_unsigned_range[two_byte_unsigned_index]; // nowarning + *pr = exactly_2byte_unsigned_range[two_byte_unsigned_index]; // nowarning + *pr = greater_than_2byte_unsigned_range[two_byte_unsigned_index]; // expected-warning{{Indexing array with type 'unsigned short' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} +} + +void range_check_four_byte_index() { + char r; + char *pr = &r; + *pr = smaller_than_4byte_signed_range[four_byte_signed_index]; // nowarning + *pr = exactly_4byte_signed_range[four_byte_signed_index]; // nowarning + *pr = greater_than_4byte_signed_range[four_byte_signed_index]; // expected-warning{{Indexing array with type 'int' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} + *pr = smaller_than_4byte_unsigned_range[four_byte_unsigned_index]; // nowarning +} + +char *f(int choice) { + switch (choice) { + case 0: + return smaller_than_4byte_signed_range; + case 1: + return exactly_4byte_signed_range; + case 2: + return greater_than_4byte_signed_range; + default: + return NULL; + } +} + +void test_symbolic_index_handling() { + char c; + c = (f(0)[four_byte_signed_index]); // nowarning + c = (f(1)[four_byte_signed_index]); // nowarning + c = (f(2)[four_byte_signed_index]); // expected-warning{{Indexing array with type 'int' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} +} + +void test_symbolic_index_handling2(int choice) { + char c; + if (choice < 2) { + if (choice >= 1) { + c = f(choice)[four_byte_signed_index]; // nowarnining // the value is one or two, f returns an array that is correct in size + } + } +} + +void test_symbolic_index_handling3(int choice) { + char c; + if (choice < 3) { + if (choice > 1) { + c = f(choice)[four_byte_signed_index]; // expected-warning{{Indexing array with type 'int' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} + } + } +} + +void test_symbolic_index_handling4(int choice) { + char c; + c = f(choice)[four_byte_signed_index]; // expected-warning{{Indexing array with type 'int' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} +} + +void test_multi_dimensions1() { + static int array[100][100][100]; + unsigned char i1 = 1, i2 = 2, i3 = 3; + int x = array[i1][i2][i3]; // nowarning +} + +void test_multi_dimensions2() { + static int array1[300][10]; + static int array2[10][300]; + static int array3[300][300]; + unsigned char i1 = 1, i2 = 2; + int x; + x = array1[i1][i2]; // expected-warning{{Indexing array with type 'unsigned char' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} + x = array2[i1][i2]; // expected-warning{{Indexing array with type 'unsigned char' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} + x = array3[i1][i2]; // expected-warning{{Indexing array with type 'unsigned char' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} expected-warning{{Indexing array with type 'unsigned char' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} +} diff --git a/clang/test/Analysis/sufficient-size-array-indexing-64bit.c b/clang/test/Analysis/sufficient-size-array-indexing-64bit.c new file mode 100644 --- /dev/null +++ b/clang/test/Analysis/sufficient-size-array-indexing-64bit.c @@ -0,0 +1,127 @@ +// RUN: %clang_analyze_cc1 -triple x86_64 -analyzer-checker=core,alpha.cplusplus.SufficientSizeArrayIndexing %s -verify + +#include "Inputs/system-header-simulator.h" + +const unsigned long long one_byte_signed_max = (1ULL << 7) - 1; +const unsigned long long two_byte_signed_max = (1ULL << 15) - 1; +const unsigned long long four_byte_signed_max = (1ULL << 31) - 1; + +const unsigned long long one_byte_unsigned_max = (1ULL << 8) - 1; +const unsigned long long two_byte_unsigned_max = (1ULL << 16) - 1; +const unsigned long long four_byte_unsigned_max = (1ULL << 32) - 1; + +char smaller_than_1byte_signed_range[one_byte_signed_max]; +char exactly_1byte_signed_range[one_byte_signed_max + 1]; +char greater_than_1byte_signed_range[one_byte_signed_max + 2]; + +char smaller_than_2byte_signed_range[two_byte_signed_max]; +char exactly_2byte_signed_range[two_byte_signed_max + 1]; +char greater_than_2byte_signed_range[two_byte_signed_max + 2]; + +char smaller_than_4byte_signed_range[four_byte_signed_max]; +char exactly_4byte_signed_range[four_byte_signed_max + 1]; +char greater_than_4byte_signed_range[four_byte_signed_max + 2]; + +char smaller_than_1byte_unsigned_range[one_byte_unsigned_max]; +char exactly_1byte_unsigned_range[one_byte_unsigned_max + 1]; +char greater_than_1byte_unsigned_range[one_byte_unsigned_max + 2]; + +char smaller_than_2byte_unsigned_range[two_byte_unsigned_max]; +char exactly_2byte_unsigned_range[two_byte_unsigned_max + 1]; +char greater_than_2byte_unsigned_range[two_byte_unsigned_max + 2]; + +char smaller_than_4byte_unsigned_range[four_byte_unsigned_max]; +char exactly_4byte_unsigned_range[four_byte_unsigned_max + 1]; +char greater_than_4byte_unsigned_range[four_byte_unsigned_max + 2]; + +const char one_byte_signed_index = 1; // sizeof(char) == 1 +const short two_byte_signed_index = 1; // sizeof(short) == 2 +const int four_byte_signed_index = 1; // sizeof(int) == 4 + +const unsigned char one_byte_unsigned_index = 1; +const unsigned short two_byte_unsigned_index = 1; +const unsigned int four_byte_unsigned_index = 1; + +void ignore_literal_indexing() { + char a = exactly_4byte_unsigned_range[32]; // nowarning +} + +void ignore_literal_indexing_with_parens() { + char a = exactly_4byte_unsigned_range[(32)]; // nowarning +} + +void range_check_one_byte_index() { + char r; + char *pr = &r; + *pr = smaller_than_1byte_signed_range[one_byte_signed_index]; // nowarning + *pr = exactly_1byte_signed_range[one_byte_signed_index]; // nowarning + *pr = greater_than_1byte_signed_range[one_byte_signed_index]; // expected-warning{{Indexing array with type 'char' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} + *pr = smaller_than_1byte_unsigned_range[one_byte_unsigned_index]; // nowarning + *pr = exactly_1byte_unsigned_range[one_byte_unsigned_index]; // nowarning + *pr = greater_than_1byte_unsigned_range[one_byte_unsigned_index]; // expected-warning{{Indexing array with type 'unsigned char' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} +} + +void range_check_two_byte_index() { + char r; + char *pr = &r; + *pr = smaller_than_2byte_signed_range[two_byte_signed_index]; // nowarning + *pr = exactly_2byte_signed_range[two_byte_signed_index]; // nowarning + *pr = greater_than_2byte_signed_range[two_byte_signed_index]; // expected-warning{{Indexing array with type 'short' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} + *pr = smaller_than_2byte_unsigned_range[two_byte_unsigned_index]; // nowarning + *pr = exactly_2byte_unsigned_range[two_byte_unsigned_index]; // nowarning + *pr = greater_than_2byte_unsigned_range[two_byte_unsigned_index]; // expected-warning{{Indexing array with type 'unsigned short' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} +} + +void range_check_four_byte_index() { + char r; + char *pr = &r; + *pr = smaller_than_4byte_signed_range[four_byte_signed_index]; // nowarning + *pr = exactly_4byte_signed_range[four_byte_signed_index]; // nowarning + *pr = greater_than_4byte_signed_range[four_byte_signed_index]; // expected-warning{{Indexing array with type 'int' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} + *pr = smaller_than_4byte_unsigned_range[four_byte_unsigned_index]; // nowarning + *pr = exactly_4byte_unsigned_range[four_byte_unsigned_index]; // nowarning + *pr = greater_than_4byte_unsigned_range[four_byte_unsigned_index]; // expected-warning{{Indexing array with type 'unsigned int' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} +} + +char *f(int choice) { + switch (choice) { + case 0: + return smaller_than_4byte_signed_range; + case 1: + return exactly_4byte_signed_range; + case 2: + return greater_than_4byte_signed_range; + default: + return NULL; + } +} + +void test_symbolic_index_handling() { + char c; + c = (f(0)[four_byte_signed_index]); // nowarning + c = (f(1)[four_byte_signed_index]); // nowarning + c = (f(2)[four_byte_signed_index]); // expected-warning{{Indexing array with type 'int' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} +} + +void test_symbolic_index_handling2(int choice) { + char c; + if (choice < 2) { + if (choice >= 1) { + c = f(choice)[four_byte_signed_index]; // nowarnining // the value is one or two, f returns an array that is correct in size + } + } +} + +void test_symbolic_index_handling3(int choice) { + char c; + if (choice < 3) { + if (choice > 1) { + c = f(choice)[four_byte_signed_index]; // expected-warning{{Indexing array with type 'int' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} + } + } +} + +void test_symbolic_index_handling4(int choice) { + char c; + c = f(choice)[four_byte_signed_index]; // expected-warning{{Indexing array with type 'int' cannot cover the whole range of the array's index set, which may result in memory waste in form of unindexable elements. Consider using a type with greater maximum value}} +}