[StaticAnalyzer] dont show wrong 'garbage value' warning when there is array index out of bounds

[danielmarjamaki]

Summary

Example code:

void f1(int x) {
  int a[20] = {0};
  if (x==25) {}
  if (a[x] == 123) {}  // <- Warning
}

If I don't enable alpha, only core, then Clang writes this misleading FP:

undef.c:5:12: warning: The left operand of '==' is a garbage value

I say it's a FP because the message is wrong. If the message correctly said "array index out of bounds" and pointed out a[x] directly, then it would be TP. This message goes away if alpha is enabled and I believe that is by intention.

Since there is a array-index-out-of-bounds check in alpha I am guessing that the UndefinedBinaryOperatorResult should not report "array index out of bounds". Therefore I remove this warning from this check.

This patch is a experimental work in progress. I would like to know if you think I should modifiy the UndefinedBinaryOperatorResult check or if I should do something in the ExprEngine? Maybe array index out of bounds should not lead to Undef SVal?

With this patch, all the existing tests succeed.

[xazax.hun]

Did you experience any problems with the array out of bounds check lately? In case it was stable on large code-bases and did not give too many false positives, I think it might be worth to move that check out of alpha at the same time, so users who do not turn on alpha checks will not lose any functionality. What do you think?

[danielmarjamaki]

In D28278#639710, @xazax.hun wrote:

Did you experience any problems with the array out of bounds check lately? In case it was stable on large code-bases and did not give too many false positives, I think it might be worth to move that check out of alpha at the same time, so users who do not turn on alpha checks will not lose any functionality. What do you think?

I don't have precise statistics. But these array-index-out-of-bounds messages are often false positives. Fixes are needed in the ExprEngine.

[zaks.anna]

I think it's more valuable to report a warning here even if the error message is not very precise. Marking something as in bounds when we know it's not does not feel right and could lead to inconsistent states down the road.

[danielmarjamaki]

I am not against that the error is shown as long as it's not misleading/wrong. To avoid misleading, in my humble opinion the error message should say "array index out of bounds".

[zaks.anna]

Does the code you added detects array out of bounds cases without false positives? Is it an option to just have this checkers produce a more precise error message in the specific case.

A lot of work will probably need to be done to implement a proper array out of bounds checking and no-one is working on that.

[danielmarjamaki]

In D28278#677905, @zaks.anna wrote:

Does the code you added detects array out of bounds cases without false positives? Is it an option to just have this checkers produce a more precise error message in the specific case.

A lot of work will probably need to be done to implement a proper array out of bounds checking and no-one is working on that.

I don't know.. maybe I can avoid some false positive. Maybe if the left operand seems to be out-of-bounds and the right operand is uninitialized maybe it would be better to complain about the right operand.

It is definitely an option for me to have this checker produce more precise error messages. I believe that will solve my problems.

[danielmarjamaki]

Making the error message more precise.

[zaks.anna]

lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp

76

Please, pull this out into a sub-rutine. Thanks!

[danielmarjamaki]

Fixed review comment. Broke out function.

[zaks.anna]

Thank you!

lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp

     }
 
     if (Ex) {
+      bool ArrayIndexOutOfBounds = false;
+      if (isa<ArraySubscriptExpr>(Ex)) {
+        SVal Loc = state->getSVal(Ex,LCtx);
+        if (Loc.isValid()) {
+          const MemRegion *MR = Loc.castAs<loc::MemRegionVal>().getRegion();
+          if (const ElementRegion *ER = dyn_cast<ElementRegion>(MR)) {
+            DefinedOrUnknownSVal Idx = ER->getIndex().castAs<DefinedOrUnknownSVal>();
+            DefinedOrUnknownSVal NumElements
+              = C.getStoreManager().getSizeInElements(state, ER->getSuperRegion(),
+                ER->getValueType());
+            ProgramStateRef StInBound = state->assumeInBound(Idx, NumElements, true);
+            ProgramStateRef StOutBound = state->assumeInBound(Idx, NumElements, false);
+            if (StOutBound && !StInBound) {
+              ArrayIndexOutOfBounds = true;
+            }
+          }
+        }
+      }
+
       OS << "The " << (isLeft ? "left" : "right")
          << " operand of '"
          << BinaryOperator::getOpcodeStr(B->getOpcode())
          << "' is a garbage value";
+      if (ArrayIndexOutOfBounds)
+        OS << " due to array index out of bounds";
     }
     else {
       // Neither operand was undefined, but the result is undefined.

test/Analysis/uninit-vals-ps.c

   return s.x; // no-warning
 }
 
+void f6(int x) {
+  int a[20];
+  if (x == 25) {}
+  if (a[x] == 123) {} // expected-warning{{The left operand of '==' is a garbage value due to array index out of bounds}}
+}
+
 int ret_uninit() {
   int i;
   int *p = &i;