[Analyzer] Create and handle SymbolCast for pointer to integral conversion

[martong]

Summary

Currently, pointer to integral type casts are not modeled properly in
the symbol tree.
Below

void foo(int *p) {
  12 - (long)p;
}

the resulting symbol for the BinOP is an IntSymExpr. LHS is 12 and the RHS is
&SymRegion{reg_$0<int * p>}.

Even though, the SVal that is created for (long)p is correctly an
LocAsInteger, we loose this information when we build up the symbol tree for
12 - (long)p. To preserve the cast, we have to create a new node in
the symbol tree that represents it: the SymbolCast. This
is what this patch does.

This reverts D115149, except the test cases.

[martong]

clang/lib/StaticAnalyzer/Core/SValBuilder.cpp

417

We should handle LHS as well.

[steakhal]

Many thanks for digging into this @martong. I really enjoyed it!
I also believe that this is the fix for the underlying issue.

I also think the getAsSymbol() should be somewhere where we can create new symbols.

[NoQ]

Oh nice, it's great to see these things moving.

I have a couple observations for your specific approach:

(1) Sounds like you're introducing a symbol (long p) that represents the exact same value as (and is used interchangeably with) &SymRegion{$p} (as long). Ambiguity is generally bad because it means a lot of duplication and missed cornercases.

(2) I think you can run into the same problem with a non-symbolic region which you can't unwrap the same way because there's no symbol to cast:

void foo() {
  int p;
  12 - (long)&p;
}

Maybe we should stick to your approach as strictly superior and eliminate LocAsInteger entirely? In this case the example (2) will work through introducing a new custom symbol SymbolRegionAddress which would look like $addr<int p>. Then add a hard canonicalization rule SymRegion{$addr<R>} = R (symregions around address symbols are ill-formed). Ideally we'd also have to unwrap offsets, i.e. $addr<Element{x, char, $i}> = $addr<x> + $i.

[ASDenysPetrov]

Starting producing SymbolCast you should be careful. It'll be helpfull for you to pay attention on my revisions D105340 and D103096 before doing this. I don't want you walk through the things I fought with. At least we've discussed to introduce a new flag support-symbolic-integer-casts to turn on/off producing the casts.

[ASDenysPetrov]

clang/lib/StaticAnalyzer/Core/SValBuilder.cpp

415–423

IMO this is not the right place for producing SymbolCast because we can meet (type)x-like semantics in a different contexts and expressions.

419–420

According to https://llvm.org/docs/CodingStandards.html#id28

471–478

This can be carried out to the separate revert revision as it is not related to this one directly

[ASDenysPetrov]

clang/lib/StaticAnalyzer/Core/SValBuilder.cpp

420

Please take into account that SVal::getType may return NULL QualType. See function's description.

[NoQ]

clang/lib/StaticAnalyzer/Core/SValBuilder.cpp

420

Yup, SVal::getType() is relatively speculative. It arguably shouldn't be but as of now it is.

In this case though it'll probably always work correctly. Despite the relevant code making relatively little sense:

QualType VisitNonLocLocAsInteger(nonloc::LocAsInteger LI) {
  // Who cares about the pointer type? It's turned into an integer anyway.
  QualType NestedType = Visit(LI.getLoc());

  // Ok, now we suddenly have a failure condition when there's no pointer type
  // even though the pointer type is completely immaterial.
  // It probably never fails in practice though, because there's usually at least some
  // pointer type (void pointer in the worst case, but it's still something).
  if (NestedType.isNull())
    return NestedType;
  
  // See? We can get bit width without pointer type.
  return Context.getIntTypeForBitwidth(LI.getNumBits(),
                                       // Oh I know this one! It's a pointer type. It isn't an integer type at all.
                                       // Whelp I guess "always unsigned" works for us as well as anything else.
                                       // We don't have any information about signedness one way or the other.
                                       NestedType->isSignedIntegerType());
}

[martong]

Thanks for the review guys.

Artem, I agree, that we should remove LocAsInteger. LocaAsInteger is a primitive handling of a specific cast operation (when we cast a pointer to an integer). The integration of LocaAsInteger into the SymExpr hierarchy is problematic as both this patch and its parent shows.

For precision, we should produce a SymbolCast when we evaluate a cast operation of a pointer to an integral type. I agree with Denys, that makeSymExprValNN is probably not the best place to do that. I took Denys' patch D105340 and created a prototype on top of that to create the SymbolCast in SValBuilder::evalCastSubKind(loc::MemRegionVal V,.

void test_param(int *p) {
  long p_as_integer = (long)p;
  clang_analyzer_dump(p);            // expected-warning{{&SymRegion{reg_$0<int * p>}}}
  clang_analyzer_dump(p_as_integer); // expected-warning{{(long) (reg_$0<int * p>)}}

I'd like to upload that soon.

Once we produce the SymbolCasts, then we can start handling them semantically. In my opinion, we should follow these steps:

1. Produce SymbolCasts. This is done in D105340, plus I am going to create another patch for pointer-to-int casts.
2. Handle SymbolCasts for the simplest cases. E.g. when we cast a (64bit width) pointer to a (64bit width unsigned) integer. This requires the foundation for an additional mapping in the ProgramState that can map a base symbol to cast symbols. This would be used in the constraint manager and this mapping must be super efficient.
3. Gradually handle more complex SymbolCast semantics. E.g. a widening cast.
4. Remove LocAsInteger. Produce the SymbolCasts by default and remove the option of ShouldSupportSymbolicIntegerCasts.

Point 2) and 3) are already started in D103096. But again, I think first we have to get the solid foundations with the State and with the ConstraintManager before getting into the more complex implementations of widening.

[martong]

Ah, I forgot to mention one last point:

5. Revert D115149. We should never reach that problematic assertion once we produce the SymbolCasts.

[martong]

I took Denys' patch D105340 and created a prototype on top of that to create the SymbolCast in SValBuilder::evalCastSubKind(loc::MemRegionVal V,

Here is the new (alternative) patch: https://reviews.llvm.org/D117229

clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h

 template <typename ImplClass, typename RetTy = void>
 class FullSValVisitor : public SValVisitor<ImplClass, RetTy>,
                         public SymExprVisitor<ImplClass, RetTy>,
                         public MemRegionVisitor<ImplClass, RetTy> {
 public:
   using SValVisitor<ImplClass, RetTy>::Visit;
   using SymExprVisitor<ImplClass, RetTy>::Visit;
   using MemRegionVisitor<ImplClass, RetTy>::Visit;
+  using Base = FullSValVisitor;
 };
 
 } // end namespace ento
 
 } // end namespace clang
 
 #endif

clang/lib/StaticAnalyzer/Core/SValBuilder.cpp

 }
 
 SVal SValBuilder::makeSymExprValNN(BinaryOperator::Opcode Op,
                                    NonLoc LHS, NonLoc RHS,
                                    QualType ResultTy) {
   SymbolRef symLHS = LHS.getAsSymbol();
   SymbolRef symRHS = RHS.getAsSymbol();
 
+  // FIXME This should be done in getAsSymbol. But then getAsSymbol should be
+  // the member function of SValBuilder (?)
+  if (symRHS)
+    if (auto RLocAsInt = RHS.getAs<nonloc::LocAsInteger>()) {
+      auto FromTy = symRHS->getType();
+      auto ToTy = RLocAsInt->getType(this->Context);
+      symRHS = this->getSymbolManager().getCastSymbol(symRHS, FromTy, ToTy);
+    }
+
   // TODO: When the Max Complexity is reached, we should conjure a symbol
   // instead of generating an Unknown value and propagate the taint info to it.
   const unsigned MaxComp = AnOpts.MaxSymbolComplexity;
 
   if (symLHS && symRHS &&
       (symLHS->computeComplexity() + symRHS->computeComplexity()) <  MaxComp)
     return makeNonLoc(symLHS, Op, symRHS, ResultTy);
 
SVal SValBuilder::evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op,
 
   if (Optional<Loc> LV = lhs.getAs<Loc>()) {
     if (Optional<Loc> RV = rhs.getAs<Loc>())
       return evalBinOpLL(state, op, *LV, *RV, type);
 
     return evalBinOpLN(state, op, *LV, rhs.castAs<NonLoc>(), type);
   }
 
-  if (const Optional<Loc> RV = rhs.getAs<Loc>()) {
-    const auto IsCommutative = [](BinaryOperatorKind Op) {
-      return Op == BO_Mul || Op == BO_Add || Op == BO_And || Op == BO_Xor ||
-             Op == BO_Or;
-    };
+  if (Optional<Loc> RV = rhs.getAs<Loc>()) {
+    // Support pointer arithmetic where the addend is on the left
+    // and the pointer on the right.
 
-    if (IsCommutative(op)) {
-      // Swap operands.
-      return evalBinOpLN(state, op, *RV, lhs.castAs<NonLoc>(), type);
-    }
+    assert(op == BO_Add);
 
-    // If the right operand is a concrete int location then we have nothing
-    // better but to treat it as a simple nonloc.
-    if (auto RV = rhs.getAs<loc::ConcreteInt>()) {
-      const nonloc::ConcreteInt RhsAsLoc = makeIntVal(RV->getValue());
-      return evalBinOpNN(state, op, lhs.castAs<NonLoc>(), RhsAsLoc, type);
-    }
+    // Commute the operands.
+    return evalBinOpLN(state, op, *RV, lhs.castAs<NonLoc>(), type);
   }
 
   return evalBinOpNN(state, op, lhs.castAs<NonLoc>(), rhs.castAs<NonLoc>(),
                      type);
 }
 
 ConditionTruthVal SValBuilder::areEqual(ProgramStateRef state, SVal lhs,
                                         SVal rhs) {

clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

SVal VisitSymbolData(const SymbolData *S) {
       // No cache here.
       if (const llvm::APSInt *I =
               SVB.getKnownValue(State, SVB.makeSymbolVal(S)))
         return Loc::isLocType(S->getType()) ? (SVal)SVB.makeIntLocVal(*I)
                                             : (SVal)SVB.makeIntVal(*I);
       return SVB.makeSymbolVal(S);
     }
 
-    // TODO: Support SymbolCast.
+    SVal VisitSymbolCast(const SymbolCast *Cast) {
+      SVal Castee = Visit(Cast->getOperand());
+      const auto &Context = SVB.getContext();
+      QualType CastTy = Cast->getType();
+
+      // Cast a pointer to an integral type.
+      if (Castee.getAs<Loc>() && !Loc::isLocType(CastTy)) {
+        const unsigned BitWidth = Context.getIntWidth(CastTy);
+        if (Castee.getAsSymbol())
+          return SVB.makeLocAsInteger(Castee.castAs<Loc>(), BitWidth);
+        if (auto X = Castee.getAs<loc::ConcreteInt>())
+          return SVB.makeIntVal(X->getValue());
+        // FIXME other cases?
+      }
+
+      return Base::VisitSymbolCast(Cast);
+    }
 
     SVal VisitSymIntExpr(const SymIntExpr *S) {
       auto I = Cached.find(S);
       if (I != Cached.end())
         return I->second;
 
       SVal LHS = getConstOrVisit(S->getLHS());
       if (isUnchanged(S->getLHS(), LHS))