[analyzer] RangeConstraintManager: Apply constraint ranges of bitwise operations

[Charusso]

Summary

We do not support evaluating bitwise operations, so that when we check for
their results being null we create a new assumption whether the current new
symbol is null or non-null. If we are on the non-null assumption's branch
we need to check the left-hand side operand's constraint range informations:

• It if contradicts with the forming new constraint ranges then we create a null state as it is an impossible condition.
• Otherwise we need to remove the nullability from its ranges as we know that it cannot be null on that branch (except bitwise OR).

[NoQ]

Aha, great, the overall structure of the code is correct!

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

477

Let's do some math.

Suppose $x is in range [2, 3]. In this case the true range for $x & 1 is [0, 1] (because 2 & 1 == 0 and 3 & 1 == 1).

The range for $x & 8 would be [0, 0].

The range for $x | 8 would be [10, 11].

The range for $x << 1 would be [4, 4], [6, 6].

The range for $x >> 1 would be [0, 1].

None of these ranges are contained within [2, 3]. In fact, none of them even contain either 2 or 3. However, when you intersect the resulting range with [2, 3], you make sure that the resulting range is contained within [2, 3]. I don't think that's correct.

487–488

You're only taking a single segment out of the range. The range may be a union of multiple segments. You should intersect with the whole range instead.

[Charusso]

• Restrict the generic contradiction-based range evaluation to only affect that left-hand side operands which constraint range are concrete zero.

[Charusso]

In D65239#1599889, @NoQ wrote:

Aha, great, the overall structure of the code is correct!

Thanks! Now it is more formal. The only problem it does not change anything on LLVM reports, where we are working with the test_non_null_lhs_range_to_null_result_feasible test case.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

477

I have added a test case to see how bad our evaluation at the moment. That is why I saw that we are just narrowing ranges and the contradiction only could happen at concrete zero range based.

[NoQ]

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

512

Instead of "we know that the value is null", we should write "we don't know that the value is non-null". I.e. if we're not sure, we must still do an early return.

523

This loop doesn't make sense. When your expression looks like (((a + b) + c) + d) & (e + f), you don't want to iterate separately over a, b, c, d, e, f; but that's what this loop would do. You should only look at the LHS and the RHS. If you want to descend further, do so recursively, so that to keep track of the overall structure of the symbolic expression as you're traversing it, rather than traversing sub-expressions in an essentially random order.

clang/test/Analysis/bitwise-ranges.cpp

21 ↗

(On Diff #211956)

This test accidentally tests debug prints. We don't want to test debug prints here. I suggest:

clang_analyzer_eval(X >= 2 && X <= 3); // expected-warning{{TRUE}}

[Charusso]

• Fix.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

512

Oh, fail. Thanks!

523

It is rather sequential in the bitwise world, but I think if you would look only at the LHS SymExpr, it should be enough. Also I would like to avoid extra overhead, that symbols() business was large enough. Thanks!

[NoQ]

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

519

I suspect we have problems with bitwise OR here, which (unlike other bitwise/shift ops) may be true when the LHS is 0.

clang/test/Analysis/bitwise-ranges.cpp

16 ↗

(On Diff #212440)

The LHS of || is always false here, regardless of the value of A or constraints on it. This test tests something strange.

24 ↗

(On Diff #212440)

The LHS of || is equivalent to C == 1.

28 ↗

(On Diff #212440)

This check is trivially true regardless of the value of D or constraints on it.

32 ↗

(On Diff #212440)

Same here.

[Charusso]

• Fix.

[Charusso]

In overall I wanted to keep the [A, B] shape of the tests, but now they are more precise, thanks!

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

519

Whoops, thanks!

clang/test/Analysis/bitwise-ranges.cpp

28 ↗

(On Diff #212440)

Hm, yes. I felt like D equals to E, but that test fails, so I have just removed them.

[NoQ]

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

504–505

I recommend making this method non-static, so that not to have to pass BV and F around.

526

If there's no current range in the map, it doesn't mean that there's no current range at all. Instead it means that the symbol is completely unconstrained and its range is equal to the whole domain of the type's possible values. You should use RangeConstraintManager::getRange() instead to retrieve the "default" range for the symbol. It would also always exist, so no need to check.

533

Aaand at this point you might as well call applyBitwiseRanges() recursively. Or even call assume() recursively. This will be the better way to implement your loop idea, because now it's gonna be correct on all recursion depth levels.

clang/include/clang/AST/Expr.h

public:
   static bool isAdditiveOp(Opcode Opc) { return Opc == BO_Add || Opc==BO_Sub; }
   bool isAdditiveOp() const { return isAdditiveOp(getOpcode()); }
   static bool isShiftOp(Opcode Opc) { return Opc == BO_Shl || Opc == BO_Shr; }
   bool isShiftOp() const { return isShiftOp(getOpcode()); }
 
   static bool isBitwiseOp(Opcode Opc) { return Opc >= BO_And && Opc <= BO_Or; }
   bool isBitwiseOp() const { return isBitwiseOp(getOpcode()); }
 
+  static bool isBitwiseOrShiftOp(Opcode Opc) {
+    return isBitwiseOp(Opc) || isShiftOp(Opc);
+  }
+  bool isBitwiseOrShiftOp() const { return isBitwiseOrShiftOp(getOpcode()); }
+
   static bool isRelationalOp(Opcode Opc) { return Opc >= BO_LT && Opc<=BO_GE; }
   bool isRelationalOp() const { return isRelationalOp(getOpcode()); }
 
   static bool isEqualityOp(Opcode Opc) { return Opc == BO_EQ || Opc == BO_NE; }
   bool isEqualityOp() const { return isEqualityOp(getOpcode()); }
 
   static bool isComparisonOp(Opcode Opc) { return Opc >= BO_Cmp && Opc<=BO_NE; }
   bool isComparisonOp() const { return isComparisonOp(getOpcode()); }

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

 
 public:
   RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower,
                      llvm::APSInt Upper) const;
   RangeSet Intersect(BasicValueFactory &BV, Factory &F,
                      const RangeSet &Other) const;
   RangeSet Negate(BasicValueFactory &BV, Factory &F) const;
 
+  void print() const { print(llvm::errs()); }
   void print(raw_ostream &os) const;
 
   bool operator==(const RangeSet &other) const {
     return ranges == other.ranges;
   }
 };
 
 

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

static RangeSet assumeNonZero(
   APSIntType IntType = BV.getAPSIntType(Sym->getType());
   return Domain.Intersect(BV, F, ++IntType.getZeroValue(),
       --IntType.getZeroValue());
 }
 
 /// Apply implicit constraints for bitwise OR- and AND-.
 /// For unsigned types, bitwise OR with a constant always returns
 /// a value greater-or-equal than the constant, and bitwise AND
-/// returns a value less-or-equal then the constant.
+/// returns a value less-or-equal than the constant.
+/// Also apply the previously applied constraint range information of the
+/// left-hand side operand of \p SIE in order to prevent false assumptions.
 ///
-/// Pattern matches the expression \p Sym against those rule,
+/// Pattern matches the expression \p SIE against those rules,
 /// and applies the required constraints.
-/// \p Input Previously established expression range set
-static RangeSet applyBitwiseConstraints(
+/// \p Result Previously established expression range set
+static RangeSet applyBitwiseConstraints(ProgramStateRef State,
                                         BasicValueFactory &BV,
-    RangeSet::Factory &F,
-    RangeSet Input,
-    const SymIntExpr* SIE) {
+                                        RangeSet::Factory &F, RangeSet Result,
+                                        const SymIntExpr *SIE) {
   QualType T = SIE->getType();
   bool IsUnsigned = T->isUnsignedIntegerType();
   const llvm::APSInt &RHS = SIE->getRHS();
   const llvm::APSInt &Zero = BV.getAPSIntType(T).getZeroValue();
   BinaryOperator::Opcode Operator = SIE->getOpcode();
 
   // For unsigned types, the output of bitwise-or is bigger-or-equal than RHS.
   if (Operator == BO_Or && IsUnsigned)
-    return Input.Intersect(BV, F, RHS, BV.getMaxValue(T));
+    return Result.Intersect(BV, F, RHS, BV.getMaxValue(T));
 
   // Bitwise-or with a non-zero constant is always non-zero.
   if (Operator == BO_Or && RHS != Zero)
-    return assumeNonZero(BV, F, SIE, Input);
+    return assumeNonZero(BV, F, SIE, Result);
 
   // For unsigned types, or positive RHS,
   // bitwise-and output is always smaller-or-equal than RHS (assuming two's
   // complement representation of signed types).
   if (Operator == BO_And && (IsUnsigned || RHS >= Zero))
-    return Input.Intersect(BV, F, BV.getMinValue(T), RHS);
+    Result = Result.Intersect(BV, F, BV.getMinValue(T), RHS);
+
+  // For all of the bitwise operations,
+  // if they remain in that 'SymIntExpr' form that means we cannot evaluate the
+  // operation properly and they remain range-based. At this point we would
+  // introduce a completely new 'RangeSet' with new assumptions and we would
+  // forget about the previous constraint range information of the left-hand
+  // side operand of 'SIE'. Here we apply the previously applied range to the
+  // current range by intersecting them to prevent false assumptions.
+  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
+  if (const RangeSet *PreviousRS = Constraints.lookup(SIE->getLHS())) {
+    if (!PreviousRS->isEmpty()) {
+      RangeSet::iterator I = PreviousRS->begin();
+      Result = Result.Intersect(BV, F, I->From(), I->To());
+    }
+  }
 
-  return Input;
+  return Result;
 }
 
 RangeSet RangeConstraintManager::getRange(ProgramStateRef State,
                                           SymbolRef Sym) {
   ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym);
 
   // If Sym is a difference of symbols A - B, then maybe we have range set
   // stored for B - A.
   BasicValueFactory &BV = getBasicVals();
   const RangeSet *R = getRangeForMinusSymbol(State, Sym);
 
   // If we have range set stored for both A - B and B - A then calculate the
   // effective range set by intersecting the range set for A - B and the
   // negated range set of B - A.
   if (V && R)
     return V->Intersect(BV, F, R->Negate(BV, F));
   if (V)
     return *V;
   if (R)
     return R->Negate(BV, F);
 
   // Lazily generate a new RangeSet representing all possible values for the
   // given symbol type.
   QualType T = Sym->getType();
 
   RangeSet Result(F, BV.getMinValue(T), BV.getMaxValue(T));
 
   // References are known to be non-zero.
   if (T->isReferenceType())
     return assumeNonZero(BV, F, Sym, Result);
 
   // Known constraints on ranges of bitwise expressions.
-  if (const SymIntExpr* SIE = dyn_cast<SymIntExpr>(Sym))
-    return applyBitwiseConstraints(BV, F, Result, SIE);
+  if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(Sym))
+    if (BinaryOperator::isBitwiseOrShiftOp(SIE->getOpcode()))
+      return applyBitwiseConstraints(State, BV, F, Result, SIE);
 
   return Result;
 }
 
 // FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to
 //        obtain the negated symbolic expression instead of constructing the
 //        symbol manually. This will allow us to support finding ranges of not
 //        only negated SymSymExpr-type expressions, but also of other, simpler
 //        expressions which we currently do not know how to negate.
 const RangeSet*
 RangeConstraintManager::getRangeForMinusSymbol(ProgramStateRef State,
                                                SymbolRef Sym) {
   if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
     if (SSE->getOpcode() == BO_Sub) {

clang/test/Analysis/bitwise-nullability.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core -verify %s
+
+// expected-no-diagnostics:
+// We do not support evaluating bitwise operations, so that when we check for
+// their results being null previously we did a state-split because it is a
+// fresh new symbol and it could be null and non-null as well. The problem was
+// the left-hand side operand of the operation already has constraint range
+// informations which could contradicts with the current new assumption.
+// From now we apply the constraint range informations of the left-hand side
+// operand in order to prevent false assumptions.
+
+typedef unsigned long long uint64_t;
+
+void test_narrowing_down_range(uint64_t Magic) {
+  uint64_t MaskedMagic = Magic & (0xffffffffffffffffULL >> 13);
+
+  if (Magic) {
+    // no-warning: 'Assuming 'Magic' is 0' was here.
+    return;
+  }
+
+  if (MaskedMagic) {
+    // no-warning: 'Assuming 'MaskedMagic' is not equal to 0' was here.
+    (void)(1 / Magic);
+  }
+}