[analyzer] Fix modeling arithmetic

[alexander-shaposhnikov]

Summary

This diff attempts to fix modeling of arithmetic expressions
where pointers are treated as integers (i.e. via C-style / reinterpret casts).
In particular, it resolves https://bugs.llvm.org/show_bug.cgi?id=34309

P.S. Before this change the analyzer incorrectly called
evalBinOpLL(state, op, lhsL, makeLoc(i), resultTy).
Because of passing lhsL we were loosing the information about the previous cast to an integer type
and were treating this as "pointers arithmetic" rather than integers arithmetic.

Test plan: make check-all

[alexfh]

Thank you for the prompt fix!

[NoQ]

I guess we'd need more assertions to catch invalid symbols, will have a look.

lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

375–377

For now this code would return UnknownVal in most cases (pointer is not tainted, or not symbolic, or contains an offset), and still construct an invalid symbol in the rest of the cases (makeSymExprValNN would add the number to the pointer symbol, instead of modelling an offset within the pointed-to region).

Once D35450 finally lands (sorry for the delays...), it'd return UnknownVal less often and crash more often.

376–378

I guess you're trying to address this FIXME i recently added. This is probably the way to go: just take the Loc behind the LocAsInteger, cast it to char * (because pointer type shouldn't affect how much bytes of offset are added, anymore), add your integer to it, pack back into LocAsInteger.

[alexander-shaposhnikov]

lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

375–377

@NoQ - many thanks for the code review!

i assume i might be missing smth, anyway, (replying to this comment and another one below)

>This is probably the way to go: just take the Loc behind the LocAsInteger, cast it to char * (because 
>pointer type shouldn't affect how much bytes of offset are added, anymore), add your integer to it, 
>pack back into LocAsInteger

i'm not sure i understand how that would work here and somehow don't like it.
For example, op can be MultiplicativeOp (i.e. long y = ((long)p) * 13;) extracting the Loc and doing smth with the Loc - doesn't seem to be the right thing (if i understood your suggestion correctly)

>For now this code would return UnknownVal in 
>most cases (pointer is not tainted, or not symbolic, 
>or contains an offset)

that was my understanding what this code should do (return UnknownVal in most cases unless we can reason about the actual (integer) values of LHS,RHS)

[alexander-shaposhnikov]

lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

367

@NoQ , @dcoughlin
while we are looking at this code - just to double check - is this line (363) actually correct ?
Let's take a look at the following example:

bool f(long x, double *p1, double *p2) {
   long y = (long)p1 - (long) p2; 
   // or,alternatively (long)p1 * (long)p2  or (long)p1 / (long)p2
   return y == x;
 }

it looks like again the analyzer will try to use evalBinOpLL and evaluate this as an operation over pointers, while (if my understanding is correct) we should be working with integers here (and yes, in most cases it should return UnknownVal)

[NoQ]

Yeah, LocAsInteger is supported very poorly in most places. We can only get away with it because people rarely cast pointers to integers.

Your reasoning about how LocAsInteger works poorly with eg. multiplication or bitwise operations (consider some sanitizer computing shadow memory) is one of the reasons why i think LocAsInteger should be turned into a special symbol class ("SymbolRegionAddress"), to be able to participate in symbolic expressions. Even if our constraint manager is unable to reason about such expressions, having correct opaque expressions is better than having UnknownVals because at least we can carry constraints on exact same expressions, and also better than conjured symbols because we are sure to assign the same symbol if such expression is computed more than once. Such change would allow us to remove special handling of LocAsInteger in some cases (just treat it as any other symbol), while still performing simplifications where we want. We'd probably be able to collapse addresses of symbolic pointers into SymbolCasts, eg. $addr<element{SymRegion{$x}, 2, char} into (uintptr_t)$x + 2. But all of that is a bigger task, not sure if you want to dig into this much, as it's not necessary to fix the crashes.

lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

367

Yeah, even pointer substraction would be handled incorrectly, because pointer types would be incorrectly taken into account (if only we actually had pointer substraction).

375–377

Yeah, we should still return UnknownVal for now in most cases. I just wanted to point out that addition and substraction can be handled this way. And also that makeSymExprValNN() seems to be unable to handle LocAsInteger arguments correctly, so manual intervention would be necessary anyway. So i think it'd be better to just return UnknownVal directly.

[alexander-shaposhnikov]

Return UnknownVal for non-comparison operations.
Add FIXME (improve modeling of "pointers as integers").

[alexander-shaposhnikov]

updated the patch per suggestion by @NoQ

[NoQ]

Thanks, LGTM!

lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

case nonloc::PointerToMemberKind: {
         default:
           return UnknownVal();
       }
     }
     case nonloc::LocAsIntegerKind: {
       Loc lhsL = lhs.castAs<nonloc::LocAsInteger>().getLoc();
       switch (rhs.getSubKind()) {
         case nonloc::LocAsIntegerKind:
+          // FIXME: at the moment the implementation 
+          // of modeling "pointers as integers" is not complete.
+          if (!BinaryOperator::isComparisonOp(op))
+            return UnknownVal();     
           return evalBinOpLL(state, op, lhsL,
                              rhs.castAs<nonloc::LocAsInteger>().getLoc(),
                              resultTy);
         case nonloc::ConcreteIntKind: {
+          // FIXME: at the moment the implementation 
+          // of modeling "pointers as integers" is not complete.
+          if (!BinaryOperator::isComparisonOp(op))
+            return UnknownVal();
           // Transform the integer into a location and compare.
           // FIXME: This only makes sense for comparisons. If we want to, say,
           // add 1 to a LocAsInteger, we'd better unpack the Loc and add to it,
           // then pack it back into a LocAsInteger.
           llvm::APSInt i = rhs.castAs<nonloc::ConcreteInt>().getValue();
           BasicVals.getAPSIntType(Context.VoidPtrTy).apply(i);
           return evalBinOpLL(state, op, lhsL, makeLoc(i), resultTy);
         }
         default:
           switch (op) {
             case BO_EQ:
               return makeTruthVal(false, resultTy);

test/Analysis/ptr-arith.cpp

 }
 
 unsigned ptrSubtractionNoCrash(char *Begin, char *End) {
   auto N = End - Begin;
   if (Begin)
     return 0;
   return N;
 }
+
+// Bug 34309
+bool ptrAsIntegerSubtractionNoCrash(long x, char *p) {
+  long y = (long)p - 1;
+  return y == x;
+}