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 @@ -287,6 +287,12 @@ Dependencies<[StackAddrEscapeBase]>, 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; + def PthreadLockBase : Checker<"PthreadLockBase">, HelpText<"Helper registering multiple checks.">, Documentation, 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 @@ -100,6 +100,7 @@ SimpleStreamChecker.cpp SmartPtrChecker.cpp SmartPtrModeling.cpp + SufficientSizeArrayIndexingChecker.cpp StackAddrEscapeChecker.cpp StdLibraryFunctionsChecker.cpp STLAlgorithmModeling.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,129 @@ +//===-- SufficientSizeArrayIndexingChecker.cpp --------------------*- C++ -*--// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This checker checks for indexing an array with integer types that are not +// sufficiently large in size to cover the array. +// +//===----------------------------------------------------------------------===// + +#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" +#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h" + +using namespace clang; +using namespace clang::ento; + +namespace { +class SufficientSizeArrayIndexingChecker + : public Checker> { + const BugType InsuffcientIndexRange{ + this, + "Index type 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", + categories::LogicError}; + +public: + void checkPreStmt(const ArraySubscriptExpr *ASE, CheckerContext &C) const; +}; +} // end anonymous namespace + +/** + * 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 Expr *Base = ASE->getBase(); + const Expr *Index = ASE->getIdx(); + + // Should not warn on literal index expressions. + if (isa(Index->IgnoreParenCasts())) + return; + + // Get the symbolic representation of the array. This is needed to reason + // about the underlying memory regions. + const SVal BaseSVal = C.getSVal(Base); + const ElementRegion *FirstElement = + dyn_cast_or_null(BaseSVal.getAsRegion()); + + if (!FirstElement) + return; + + const ProgramStateRef State = C.getState(); + SValBuilder &SVB = C.getSValBuilder(); + + // Try to reason about the number of elements in the array. + const DefinedOrUnknownSVal SizeInElements = + getDynamicElementCount(State, FirstElement->getSuperRegion(), SVB, + FirstElement->getElementType()); + + // Get the maximal value of the index type. + const QualType IndexType = Index->getType(); + const llvm::APSInt MaxIndex = + SVB.getBasicValueFactory().getMaxValue(IndexType); + const nonloc::ConcreteInt MaxIndexValue{MaxIndex}; + + // 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. + const NonLoc ConstantOne = SVB.makeIntVal(1, true); + + // SizeInElements - 1 + const SVal SizeInElementsMinusOne = SVB.evalBinOp( + State, BO_Sub, SizeInElements, ConstantOne, SVB.getArrayIndexType()); + + // SizeInElements - 1 <= MaxIndex + const SVal TypeCanIndexEveryElement = + SVB.evalBinOp(State, BO_LE, SizeInElementsMinusOne, MaxIndexValue, + SVB.getConditionType()); + + 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, there will be no warning emitted. + if (AssumptionPair.first) + return; + + // The analysis can continue onward even if an error was found. + const ExplodedNode *N = C.generateNonFatalErrorNode(); + if (!N) + return; + + // Report the error. + auto R = std::make_unique( + InsuffcientIndexRange, InsuffcientIndexRange.getDescription(), N); + R->addRange(ASE->getSourceRange()); + // Mark the array expression interesting. + R->markInteresting(FirstElement->getSuperRegion()); + C.emitReport(std::move(R)); +} + +void ento::registerSufficientSizeArrayIndexingChecker(CheckerManager &Mgr) { + Mgr.registerChecker(); +} + +bool ento::shouldRegisterSufficientSizeArrayIndexingChecker( + const CheckerManager &Mgr) { + return true; +} diff --git a/clang/test/Analysis/sufficient-size-array-indexing.c b/clang/test/Analysis/sufficient-size-array-indexing.c new file mode 100644 --- /dev/null +++ b/clang/test/Analysis/sufficient-size-array-indexing.c @@ -0,0 +1,198 @@ +// RUN: %clang_analyze_cc1 -triple i386 -analyzer-checker=core,alpha.core.SufficientSizeArrayIndexing %s -verify +// RUN: %clang_analyze_cc1 -triple x86_64 -analyzer-checker=core,alpha.core.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; + a = smaller_than_1byte_signed_range[1]; // nowarning + a = exactly_1byte_signed_range[1]; // nowarning + a = greater_than_1byte_signed_range[1]; // nowarning + a = smaller_than_2byte_signed_range[1]; // nowarning + a = exactly_2byte_signed_range[1]; // nowarning + a = greater_than_2byte_signed_range[1]; // nowarning + a = smaller_than_4byte_signed_range[1]; // nowarning + a = exactly_4byte_signed_range[1]; // nowarning + a = greater_than_4byte_signed_range[1]; // nowarning + + a = smaller_than_1byte_unsigned_range[1]; // nowarning + a = exactly_1byte_unsigned_range[1]; // nowarning + a = greater_than_1byte_unsigned_range[1]; // nowarning + a = smaller_than_2byte_unsigned_range[1]; // nowarning + a = exactly_2byte_unsigned_range[1]; // nowarning + a = greater_than_2byte_unsigned_range[1]; // nowarning + a = smaller_than_4byte_unsigned_range[1]; // nowarning +} + +void ignore_literal_indexing_with_parens() { + char a; + a = smaller_than_1byte_signed_range[(1)]; // nowarning + a = exactly_1byte_signed_range[(1)]; // nowarning + a = greater_than_1byte_signed_range[(1)]; // nowarning + a = smaller_than_2byte_signed_range[(1)]; // nowarning + a = exactly_2byte_signed_range[(1)]; // nowarning + a = greater_than_2byte_signed_range[(1)]; // nowarning + a = smaller_than_4byte_signed_range[(1)]; // nowarning + a = exactly_4byte_signed_range[(1)]; // nowarning + a = greater_than_4byte_signed_range[(1)]; // nowarning + + a = smaller_than_1byte_unsigned_range[(1)]; // nowarning + a = exactly_1byte_unsigned_range[(1)]; // nowarning + a = greater_than_1byte_unsigned_range[(1)]; // nowarning + a = smaller_than_2byte_unsigned_range[(1)]; // nowarning + a = exactly_2byte_unsigned_range[(1)]; // nowarning + a = greater_than_2byte_unsigned_range[(1)]; // nowarning + a = smaller_than_4byte_unsigned_range[(1)]; // nowarning +} + +void non_literal_but_compile_time_const_indexing() { + char a; + a = smaller_than_1byte_signed_range[(unsigned char)(1 + 1)]; // nowarning + a = exactly_1byte_signed_range[(unsigned char)(1 + 1)]; // nowarning + a = greater_than_1byte_signed_range[(unsigned char)(1 + 1)]; // nowarning // note that because of signed range and unsiged index type this case is fine as opposed to the 3rd case below + a = smaller_than_2byte_signed_range[(unsigned char)(1 + 1)]; // expected-warning{{Index type 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}} + a = exactly_2byte_signed_range[(unsigned char)(1 + 1)]; // expected-warning{{Index type 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}} + a = greater_than_2byte_signed_range[(unsigned char)(1 + 1)]; // expected-warning{{Index type 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}} + a = smaller_than_4byte_signed_range[(unsigned char)(1 + 1)]; // expected-warning{{Index type 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}} + a = exactly_4byte_signed_range[(unsigned char)(1 + 1)]; // expected-warning{{Index type 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}} + a = greater_than_4byte_signed_range[(unsigned char)(1 + 1)]; // expected-warning{{Index type 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}} + + a = smaller_than_1byte_unsigned_range[(unsigned char)(1 + 1)]; // nowarning + a = exactly_1byte_unsigned_range[(unsigned char)(1 + 1)]; // nowarning + a = greater_than_1byte_unsigned_range[(unsigned char)(1 + 1)]; // expected-warning{{Index type 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}} + a = smaller_than_2byte_unsigned_range[(unsigned char)(1 + 1)]; // expected-warning{{Index type 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}} + a = exactly_2byte_unsigned_range[(unsigned char)(1 + 1)]; // expected-warning{{Index type 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}} + a = greater_than_2byte_unsigned_range[(unsigned char)(1 + 1)]; // expected-warning{{Index type 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}} + a = smaller_than_4byte_unsigned_range[(unsigned char)(1 + 1)]; // expected-warning{{Index type 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_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{{Index type 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{{Index type 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{{Index type 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{{Index type 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{{Index type 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{{Index type 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{{Index type 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{{Index type 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{{Index type 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{{Index type 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{{Index type 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@-1{{Index type 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}} + // in case of array3, both levels of indexing are triggering a diagnostic +}