[analyzer] Improve underflow handling in ArrayBoundV2

[donat.nagy]

Summary

This minor change ensures that underflow errors are reported on arrays that are in unknown space but have well-defined size.

As a concrete example, the following test case did not produce a warning previously, but will produce a warning after this patch:

typedef struct {
  int id;
  char name[256];
} user_t;

user_t *get_symbolic_user(void);
char test_underflow_symbolic_2() {
  user_t *user = get_symbolic_user();
  return user->name[-1];
}

[donat.nagy]

Note: this commit is split off from the larger commit https://reviews.llvm.org/D150446, which combined this simple improvement with other, more complex changes that had problematic side-effects.

[donat.nagy]

I'll try to upload results on open source projects, probably on Tuesday (I'm on vacation on Monday).

[gamesh411]

Seems like a straightforward extension, LGTM.

[steakhal]

Looks safe and good. I'm interested in the diff though.
Let me know once you have the results.
I wanna have a look before we land this.

clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

184

Such as the MallocChecker.

clang/test/Analysis/out-of-bounds.c

176

Try not to introduce unrelated hunks, as it might introduce more conflicts for downstream users than absolutely necessary.

[donat.nagy]

I didn't upload the test results yet because right now there is some incompatibility between our local fork and the upstream. There is ongoing work to fix this (by rebasing our fork), but until it's done I can't use our automated tools to run the analysis with revisions that are close to the upstream main branch.

[donat.nagy]

The results on open-source projects are depressing, but acceptable. This checker is looking for a serious defect, so it doesn't find any true positives on stable releases; however it produces a steady trickle of false positives because the Clang SA engine regularly misinterprets complicated code. As the only effect of this patch is that it allows this checker to analyze more situations, it introduces no true positives and a manageable amount of false positives (on average ~1/project).

Table of raw results:

memcached	New reports	Lost reports	no change
tmux	New reports	Lost reports	no change
twin	New reports	Lost reports	no change
vim	New reports	Lost reports	no change
openssl	New reports	Lost reports	no change
sqlite	New reports	Lost reports	no change
ffmpeg	New reports	Lost reports	four new reports (probably FPs), two of them are from the same macro
postgres	New reports	Lost reports	two new false positives
tinyxml2	New reports	Lost reports	no change
libwebm	New reports	Lost reports	no change
xerces	New reports	Lost reports	no change
bitcoin	New reports	Lost reports	no change
protobuf	New reports	Lost reports	seven new FPs, but six of them are caused by incorrect config of our CI
qtbase	New reports	Lost reports	one new FP and one new result of UndefinedBinaryOperatorResult
contour	New reports	Lost reports	no change

(In protobuf, our CI misconfigures the build, so the preprocessor handles an assert-like macro incorrectly and six of the seven new false positives are on "assume that this assertion fails, but we continue to execute the code" branches. On qtbase I don't understand why did the UndefinedBinaryOperatorResult report appear [perhaps unpredictable changes of graph traversal?] but it's technically a true positive.)

[donat.nagy]

A (somewhat delayed) ping to @steakhal because you asked me to tell you when I have the results. (I'm writing this only because I don't know whether you have seen the table that I uploaded on Friday.)

[steakhal]

Thanks!

[steakhal]

Hold on, make sure this is clang-format compliant before committing.
(Check buildkite)

[donat.nagy]

Yup, there was a superfluous line break that was corrected by git clang-format; thanks for bringing it to my attention. As this is a very trivial change, I'll merge the fixed commit directly, without uploading it into Phabricator.

clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

201–202

This will be a single line in the commit that I'll merge.

clang/lib/StaticAnalyzer/Checkers/ArrayBoundCheckerV2.cpp

void ArrayBoundCheckerV2::checkLocation(SVal location, bool isLoad,
   SValBuilder &svalBuilder = checkerContext.getSValBuilder();
   const std::optional<RegionRawOffsetV2> &RawOffset =
       RegionRawOffsetV2::computeOffset(state, svalBuilder, location);
 
   if (!RawOffset)
     return;
 
   NonLoc ByteOffset = RawOffset->getByteOffset();
+  const SubRegion *Reg = RawOffset->getRegion();
 
   // CHECK LOWER BOUND
-  const MemSpaceRegion *SR = RawOffset->getRegion()->getMemorySpace();
-  if (!llvm::isa<UnknownSpaceRegion>(SR)) {
-    // A pointer to UnknownSpaceRegion may point to the middle of
-    // an allocated region.
-
+  const MemSpaceRegion *Space = Reg->getMemorySpace();
+  if (!(isa<SymbolicRegion>(Reg) && isa<UnknownSpaceRegion>(Space))) {
+    // A symbolic region in unknown space represents an unknown pointer that
+    // may point into the middle of an array, so we don't look for underflows.
+    // Both conditions are significant because we want to check underflows in
+    // symbolic regions on the heap (which may be introduced by checkers like
+    // MallocChecker that call SValBuilder::getConjuredHeapSymbolVal()) and
+    // non-symbolic regions (e.g. a field subregion of a symbolic region) in
+    // unknown space.
     auto [state_precedesLowerBound, state_withinLowerBound] =
         compareValueToThreshold(state, ByteOffset,
                                 svalBuilder.makeZeroArrayIndex(), svalBuilder);
 
     if (state_precedesLowerBound && !state_withinLowerBound) {
       // We know that the index definitely precedes the lower bound.
       reportOOB(checkerContext, state_precedesLowerBound, OOB_Precedes);
       return;
     }
 
     if (state_withinLowerBound)
       state = state_withinLowerBound;
   }
 
   // CHECK UPPER BOUND
-  DefinedOrUnknownSVal Size =
-      getDynamicExtent(state, RawOffset->getRegion(), svalBuilder);
+  DefinedOrUnknownSVal Size = getDynamicExtent(state, Reg, svalBuilder);
   if (auto KnownSize = Size.getAs<NonLoc>()) {
     auto [state_withinUpperBound, state_exceedsUpperBound] =
         compareValueToThreshold(state, ByteOffset, *KnownSize, svalBuilder);
 
     if (state_exceedsUpperBound) {
       if (!state_withinUpperBound) {
         // We know that the index definitely exceeds the upper bound.
         reportOOB(checkerContext, state_exceedsUpperBound, OOB_Excedes);

clang/test/Analysis/out-of-bounds.c

void test_assume_after_access(unsigned long x) {
   int buf[100];
   buf[x] = 1;
   clang_analyzer_eval(x <= 99); // expected-warning{{TRUE}}
 }
 
 // Don't warn when indexing below the start of a symbolic region's whose
 // base extent we don't know.
 int *get_symbolic(void);
-void test_index_below_symboloc(void) {
+void test_underflow_symbolic(void) {
   int *buf = get_symbolic();
   buf[-1] = 0; // no-warning;
 }
 
+// But warn if we understand the internal memory layout of a symbolic region.
+typedef struct {
+  int id;
+  char name[256];
+} user_t;
+
+user_t *get_symbolic_user(void);
+char test_underflow_symbolic_2() {
+  user_t *user = get_symbolic_user();
+  return user->name[-1]; // expected-warning{{Out of bound memory access}}
+}
+
 void test_incomplete_struct(void) {
   extern struct incomplete incomplete;
   int *p = (int *)&incomplete;
   p[1] = 42; // no-warning
 }
 
 void test_extern_void(void) {
   extern void v;
   int *p = (int *)&v;
   p[1] = 42; // no-warning
 }
 
 void test_assume_after_access2(unsigned long x) {
   char buf[100];
   buf[x] = 1;
   clang_analyzer_eval(x <= 99); // expected-warning{{TRUE}}
 }