[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 ↗

(On Diff #89540)

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

[danielmarjamaki]

Fixed review comment. Broke out function.

[zaks.anna]

Thank you!

cfe/trunk/lib/StaticAnalyzer/Checkers/UndefResultChecker.cpp

class UndefResultChecker
 
   mutable std::unique_ptr<BugType> BT;
 
 public:
   void checkPostStmt(const BinaryOperator *B, CheckerContext &C) const;
 };
 } // end anonymous namespace
 
+static bool isArrayIndexOutOfBounds(CheckerContext &C, const Expr *Ex) {
+  ProgramStateRef state = C.getState();
+  const LocationContext *LCtx = C.getLocationContext();
+
+  if (!isa<ArraySubscriptExpr>(Ex))
+    return false;
+
+  SVal Loc = state->getSVal(Ex, LCtx);
+  if (!Loc.isValid())
+    return false;
+
+  const MemRegion *MR = Loc.castAs<loc::MemRegionVal>().getRegion();
+  const ElementRegion *ER = dyn_cast<ElementRegion>(MR);
+  if (!ER)
+    return false;
+
+  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);
+  return StOutBound && !StInBound;
+}
+
 void UndefResultChecker::checkPostStmt(const BinaryOperator *B,
                                        CheckerContext &C) const {
   ProgramStateRef state = C.getState();
   const LocationContext *LCtx = C.getLocationContext();
   if (state->getSVal(B, LCtx).isUndef()) {
 
     // Do not report assignments of uninitialized values inside swap functions.
     // This should allow to swap partially uninitialized structs
else if (state->getSVal(B->getRHS(), LCtx).isUndef()) {
       isLeft = false;
     }
 
     if (Ex) {
       OS << "The " << (isLeft ? "left" : "right")
          << " operand of '"
          << BinaryOperator::getOpcodeStr(B->getOpcode())
          << "' is a garbage value";
+      if (isArrayIndexOutOfBounds(C, Ex))
+        OS << " due to array index out of bounds";
     }
     else {
       // Neither operand was undefined, but the result is undefined.
       OS << "The result of the '"
          << BinaryOperator::getOpcodeStr(B->getOpcode())
          << "' expression is undefined";
     }
     auto report = llvm::make_unique<BugReport>(*BT, OS.str(), N);

cfe/trunk/test/Analysis/uninit-vals-ps.c

 struct f5_struct { int x; };
 void f5_aux(struct f5_struct* s);
 int f5(void) {
   struct f5_struct s;
   f5_aux(&s);
   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;
   return *p;  // expected-warning{{Undefined or garbage value returned to caller}}
 }
 
 // <rdar://problem/6451816>
 typedef unsigned char Boolean;