gamesh411 updated this revision to Diff 275678.
gamesh411 added a comment.
modernize the memory modeling code, still WIP
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D69318/new/
https://reviews.llvm.org/D69318
Files:
clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt
clang/lib/StaticAnalyzer/Checkers/SufficientSizeArrayIndexingChecker.cpp
clang/test/Analysis/sufficient-size-array-indexing-32bit.c
clang/test/Analysis/sufficient-size-array-indexing-64bit.c
Index: clang/test/Analysis/sufficient-size-array-indexing-64bit.c
===================================================================
--- /dev/null
+++ 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}}
+}
Index: clang/test/Analysis/sufficient-size-array-indexing-32bit.c
===================================================================
--- /dev/null
+++ 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}}
+}
Index: clang/lib/StaticAnalyzer/Checkers/SufficientSizeArrayIndexingChecker.cpp
===================================================================
--- /dev/null
+++ 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<check::PreStmt<ArraySubscriptExpr>> {
+ mutable std::unique_ptr<BugType> 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<IntegerLiteral>(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<ArrayType>(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<DefinedSVal>());
+
+ // 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<PathSensitiveBugReport>(*BT, BT->getDescription(), N);
+ R->addRange(Index->getSourceRange());
+ C.emitReport(std::move(R));
+}
+
+void ento::registerSufficientSizeArrayIndexingChecker(CheckerManager &Mgr) {
+ Mgr.registerChecker<SufficientSizeArrayIndexingChecker>();
+}
+
+bool ento::shouldRegisterSufficientSizeArrayIndexingChecker(
+ const CheckerManager &Mgr) {
+ return true;
+}
Index: clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt
===================================================================
--- clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt
+++ clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt
@@ -99,6 +99,7 @@
RunLoopAutoreleaseLeakChecker.cpp
SimpleStreamChecker.cpp
SmartPtrModeling.cpp
+ SufficientSizeArrayIndexingChecker.cpp
StackAddrEscapeChecker.cpp
StdLibraryFunctionsChecker.cpp
STLAlgorithmModeling.cpp
Index: clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
===================================================================
--- clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
+++ clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
@@ -285,6 +285,12 @@
Dependencies<[StackAddrEscapeBase]>,
Documentation<HasAlphaDocumentation>;
+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<NotDocumented>;
+
def PthreadLockBase : Checker<"PthreadLockBase">,
HelpText<"Helper registering multiple checks.">,
Documentation<NotDocumented>,
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
