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 @@ -285,6 +285,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 @@ -99,6 +99,7 @@ RunLoopAutoreleaseLeakChecker.cpp SimpleStreamChecker.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,147 @@ +//===-- 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 +// +//===----------------------------------------------------------------------===// +// +// +// 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/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> { + mutable std::unique_ptr BT; + +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. + const QualType IndexType = Index->getType(); + if (isa(Index->IgnoreParenCasts())) + return; + + // The checker is only interested in ArrayType-s. + const QualType BaseTy = Base->getType(); + if (!BaseTy->isArrayType()) + return; + + const QualType ET = dyn_cast(BaseTy)->getElementType(); + + // Get the maximal value of the index type. + const llvm::APSInt 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 SVal BaseSVal = C.getSVal(Base); + const MemRegion *BaseRegion = BaseSVal.getAsRegion(); + + if (!BaseRegion) + 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, BaseRegion, SVB, ET); + + // 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 NonLoc ConstantOneSVal = SVB.makeIntVal(1, true); + + const SVal NumArrayElemsMinusOne = + SVB.evalBinOp(State, BO_Sub, SizeInElements, ConstantOneSVal, + C.getASTContext().UnsignedLongLongTy); + const SVal TypeCanIndexEveryElement = SVB.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 ExplodedNode *N = C.generateNonFatalErrorNode(); + if (!N) + return; + + // Lazily initialize the BugType. + if (!BT) + BT.reset(new BuiltinBug{ + 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."}); + + // 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 CheckerManager &Mgr) { + 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.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 = 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{{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}} +} 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.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]; +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{{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 + *pr = exactly_4byte_unsigned_range[four_byte_unsigned_index]; // nowarning + *pr = greater_than_4byte_unsigned_range[four_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}} +} + +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}} +}