[analyzer] Add SufficientSizeArrayIndexingChecker

[gamesh411]

Summary

Checks for indexing situations, where an array is indexed with a
variable of type not sufficiently large to cover the whole range of the
arrays possible index set. This check is uses path-sensitivity in order
to reason about the possible size of the array being checked.

[gamesh411]

Please feel free to add more reviewers.

[Szelethus]

In D69318#1718220, @gamesh411 wrote:

Please feel free to add more reviewers.

Here you go!

[NoQ]

I suspect that with this check by choosing path-sensitivity you gain less than you lose. That is, checking how the array pointer is passed around may be nice, but if you sacrificed that, you could have turned this check into a compiler warning which would have had an effect on much larger audience.

clang/include/clang/StaticAnalyzer/Checkers/Checkers.td

749

What makes this checker C++-specific? All your tests are in plain C.

clang/lib/StaticAnalyzer/Checkers/SufficientSizeArrayIndexingChecker.cpp

94

This is always true (we should probably tell SVal.getAsRegion() to return a const SubRegion *).

101

This never happens. The chain of superregions never has loops; it is always finite.

104

This deserves comments on what kinds of regions do you expect to see here. Do i understand correctly that you expect BaseMemRegion to be an ElementRegion and its superregion to be the whole array? 'Cause the former is super unobvious and most likely shouldn't be that way.

154–156

I recommend also adding trackExpressionValue() for the array expression. In your "symbolic index handling" tests it would hopefully* allow you to see the execution path within f() as part of the report, which is essential.

__
*If it doesn't work out of the box, it's most likely a bug in trackExpressionValue(). But generally such tracking needs to be implemented in order to move the checker out of alpha, because path-sensitive reports are worthless when you don't see visitor notes on all the interesting events on the path.

[NoQ]

clang/lib/StaticAnalyzer/Checkers/SufficientSizeArrayIndexingChecker.cpp

43

The whole point of bug types is to remain the same regardless of the specific message. They're more like a category. Please use only one bug type for the whole checker (unless you really find different categories of bugs).

[steakhal]

clang/lib/StaticAnalyzer/Checkers/SufficientSizeArrayIndexingChecker.cpp

76

Shoudn't we use isa<> if we don't use the resulting pointer?

127

I think its better to stay consistent regards naming.
Use either number literals expressing numeric values, or spell out its name.
I would prefer the latter like: ConstantOne with type SVal.

[gamesh411]

change license

[gamesh411]

move to core.alpha

[gamesh411]

make single bug-type
fix checker registration

[gamesh411]

modernize the memory modeling code, still WIP

[gamesh411]

fix detection logic
fix license header
add missing warning to test

[gamesh411]

clang/lib/StaticAnalyzer/Checkers/SufficientSizeArrayIndexingChecker.cpp

43

I have removed the whole BugType factory think, that was really stupid in retrospect.

104

I feel a bit more familiar now with the infrastructure now, and I used getDynamicElementCount as it now an available utility. Thanks for the comments, they were helpful for discovering how things work! :D

[gamesh411]

clang/include/clang/StaticAnalyzer/Checkers/Checkers.td

749

Very true, I have moved to core.alpha.

[gamesh411]

The checker has been updated, the comments and the logic polished. I would still take a stab at this being a ClangSa checker (as opposed to being a Tidy check). What do you think?

[balazske]

clang/lib/StaticAnalyzer/Checkers/SufficientSizeArrayIndexingChecker.cpp

27

The bug type can be initialized here:
BT{this, "...", "..."}
How did this compile with only one text argument to constructor? I think the first is a short name of the bug, second is a category that is not omittable. The text that is used here should be passed to the BugReport. BugType::getDescription returns the "name" of the bug that is the first argument. But I am not sure what matters from these texts, the code design looks confusing.

50

if (isa<IntegerLiteral>(Index)) should be used. IntegerLiteral is a subclass of Expr, not a QualType.

72

I would use SVB.getBasicValueFactory().getMaxValue(IndexType) to get the max value.

82

SValBuilder::getArrayIndexType should be better than the UnsignedLongLongTy.

86

I think SVB.getConditionType() should be used for condition result.

121

I am not sure if this markInteresting call is correct.

clang/test/Analysis/sufficient-size-array-indexing-32bit.c

37

I do not know if it is safe to make such assumptions about sizeof.

[gamesh411]

clang/lib/StaticAnalyzer/Checkers/SufficientSizeArrayIndexingChecker.cpp

27

I think because it is initialized with a BuiltinBug, which must be a subclass of BugType. I don't really know what should be preferable nowadays, as this code was actually written more than a year ago. Thanks for pointing out that it can be initialized there, I think lazy initialization seems not that important with this particular checker.

50

The way I have structured the code is very misleading, sorry for that, I will move the type extraction if lower, where it is actually used.

72

Good point, thanks for pointing out such a method existed in BasicValueFactory!

82

Seems reasonable :)

86

I will use that, thanks.

121

What I wanted to do conceptually is to mark the array itself interesting. I am however not sure whether this is the best way. I will try this and FirstElement itself and maybe look at whether there are some additional notes emitted along the way.

clang/test/Analysis/sufficient-size-array-indexing-32bit.c

37

You are definitely right! However it is common as per:
https://en.cppreference.com/w/cpp/language/types#Data_models

Data models

The choices made by each implementation about the sizes of the fundamental types are collectively known as data model. Four data models found wide acceptance:

32 bit systems:

        LP32 or 2/4/4 (int is 16-bit, long and pointer are 32-bit) 

            Win16 API 

        ILP32 or 4/4/4 (int, long, and pointer are 32-bit); 

            Win32 API
            Unix and Unix-like systems (Linux, macOS) 

64 bit systems:

        LLP64 or 4/4/8 (int and long are 32-bit, pointer is 64-bit) 

            Win64 API 

        LP64 or 4/8/8 (int is 32-bit, long and pointer are 64-bit) 

            Unix and Unix-like systems (Linux, macOS) 

Other models are very rare. For example, ILP64 (8/8/8: int, long, and pointer are 64-bit) only appeared in some early 64-bit Unix systems (e.g. Unicos on Cray).

Only ILP32 has 16 bit ints.
Next idea would be to use fixed-width integer types from cstdint. But tests should not use system headers, and there are mentions in test files to int32_t, howevery they are just typedefs for int. And I think we maintaining a whole standard library headers is a bit too much a hassle.

[gamesh411]

apply review suggestions

[balazske]

clang/lib/StaticAnalyzer/Checkers/SufficientSizeArrayIndexingChecker.cpp

27

I had even a plan to remove the BuiltinBug because it looks confusing and does not add real value. New checkers should use BugType.

50

Probably function SVB.getConstantVal can be used to test if there is a (compile-time) constant passed to the index. But it may be value of a (const) variable.

clang/test/Analysis/sufficient-size-array-indexing-32bit.c

37

Still it would be good to check if the test passes on all the buildbots.

49

Does this work in [32 + 1] case?

107

choice can be here only 1. If it could be 1 or 2 we should get no warning because the array size may be good or bad. But to test that it is enough that choice can have any value, like in test_symbolic_index_handling4.

121

Here "is a chance that indexing is correct". So no warning should occur?

clang/test/Analysis/sufficient-size-array-indexing-64bit.c

2

I could not find difference between this and the previous test file (except the multi-dimensional arrays are omitted). It would be better to have a single test file without repetition. (Multiple RUN lines in a single file should work).

[gamesh411]

I am now experimenting with the suggestions. The other issues are on the worklist. Thanks for these so far.

clang/lib/StaticAnalyzer/Checkers/SufficientSizeArrayIndexingChecker.cpp

50

Yes, that is a design question, should the checker warn if the index is not a literal but a const variable like:

constexpr char SpecialIndex = 12;
int Array[300] = make_array();
Array[SpecialIndex]; // should we warn in this case? because now we do,
                     // as the indexing expression is not a literal.

clang/test/Analysis/sufficient-size-array-indexing-32bit.c

37

I'm afraid we can only test that by committing, as there is no other way to submit a build-job ( not that I am aware of, any information in that regard is welcome :) ).

49

It should, I will add a case for it.

107

Yes, this test is a bit redundant, should I remove it in your opinion?

[gamesh411]

move tests to one file

[gamesh411]

extend test cases
add comments to non-obvious cases

[gamesh411]

clang/test/Analysis/sufficient-size-array-indexing-32bit.c

121

I think as there is a branch where it is provably wrong, this is correct. It is just not obvious from the diag message which branch is taken, and consequently which array is being indexed. I think there is no way to address this from inside the checker.

clang/include/clang/StaticAnalyzer/Checkers/Checkers.td

HelpText<"Check for cases where the dynamic and the static type of an object "
            "are unrelated.">,
   Documentation<HasAlphaDocumentation>;
 
 def StackAddrAsyncEscapeChecker : Checker<"StackAddressAsyncEscape">,
   HelpText<"Check that addresses to stack memory do not escape the function">,
   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>,
   Hidden;
 
 def C11LockChecker : Checker<"C11Lock">,
   HelpText<"Simple lock -> unlock checker">,
   Dependencies<[PthreadLockBase]>,
def IteratorRangeChecker : Checker<"IteratorRange">,
   Documentation<HasAlphaDocumentation>;
 
 def MismatchedIteratorChecker : Checker<"MismatchedIterator">,
   HelpText<"Check for use of iterators of different containers where iterators "
            "of the same container are expected">,
   Dependencies<[IteratorModeling]>,
   Documentation<HasAlphaDocumentation>;
 
 } // end: "alpha.cplusplus"
 
 
 //===----------------------------------------------------------------------===//
 // Valist checkers.
 //===----------------------------------------------------------------------===//
 
 let ParentPackage = Valist in {
 

clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   RetainCountChecker/RetainCountChecker.cpp
   RetainCountChecker/RetainCountDiagnostics.cpp
   ReturnPointerRangeChecker.cpp
   ReturnUndefChecker.cpp
   ReturnValueChecker.cpp
   RunLoopAutoreleaseLeakChecker.cpp
   SimpleStreamChecker.cpp
   SmartPtrModeling.cpp
+  SufficientSizeArrayIndexingChecker.cpp
   StackAddrEscapeChecker.cpp
   StdLibraryFunctionsChecker.cpp
   STLAlgorithmModeling.cpp
   StreamChecker.cpp
   Taint.cpp
   TaintTesterChecker.cpp
   TestAfterDivZeroChecker.cpp
   TraversalChecker.cpp

clang/lib/StaticAnalyzer/Checkers/SufficientSizeArrayIndexingChecker.cpp

+//===-- 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<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;
+
+  // 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<ElementRegion>(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 llvm::APSInt MaxIndex =
+      llvm::APSInt::getMaxValue(C.getASTContext().getIntWidth(IndexType),
+                                IndexType->isUnsignedIntegerType());
+  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,
+                    C.getASTContext().UnsignedLongLongTy);
+
+  // SizeInElements - 1 <= MaxIndex
+  const SVal TypeCanIndexEveryElement = SVB.evalBinOp(
+      State, BO_LE, SizeInElementsMinusOne, MaxIndexValue, IndexType);
+
+  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, 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;
+
+  // 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(ASE->getSourceRange());
+  // Mark the array expression interesting.
+  R->markInteresting(FirstElement->getSuperRegion());
+  C.emitReport(std::move(R));
+}
+
+void ento::registerSufficientSizeArrayIndexingChecker(CheckerManager &Mgr) {
+  Mgr.registerChecker<SufficientSizeArrayIndexingChecker>();
+}
+
+bool ento::shouldRegisterSufficientSizeArrayIndexingChecker(
+    const CheckerManager &Mgr) {
+  return true;
+}

clang/test/Analysis/sufficient-size-array-indexing-32bit.c

+// 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}}
+                      // 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}}
+}

clang/test/Analysis/sufficient-size-array-indexing-64bit.c

+// 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}}
+}