[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

476

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.

486–487

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

476

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

496

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.

507

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

22

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

496

Oh, fail. Thanks!

507

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

503

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

17

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

25

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

29

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

33

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

503

Whoops, thanks!

clang/test/Analysis/bitwise-ranges.cpp

29

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

488–489

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

510

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.

517

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(raw_ostream &os) const;
+  LLVM_DUMP_METHOD void dump() const { print(llvm::errs()); }
 
   bool operator==(const RangeSet &other) const {
     return ranges == other.ranges;
   }
 };
 
 
 class ConstraintRange {};

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

if (Operator == BO_Or && RHS != Zero)
     return assumeNonZero(BV, F, SIE, Input);
 
   // 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);
 
   return Input;
 }
 
+// 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 range 'RS' then it returns a null
+//   state as it is an impossible condition.
+// - Otherwise it removes the nullability from its ranges as we know that it
+//   cannot be null on that branch (except bitwise OR).
+static ProgramStateRef applyBitwiseRanges(ProgramStateRef State,
+                                          BasicValueFactory &BV,
+                                          RangeSet::Factory &F, RangeSet RS,
+                                          SymbolRef Sym) {
+  if (RS.isEmpty())
+    return State;
+
+  // If we cannot be sure whether the value is non-null, do nothing.
+  const llvm::APSInt &Zero = BV.getAPSIntType(Sym->getType()).getZeroValue();
+  if (!RS.Intersect(BV, F, Zero, Zero).isEmpty())
+    return State;
+
+  const SymIntExpr *SIE = dyn_cast<SymIntExpr>(Sym);
+  if (!SIE)
+    return State;
+
+  // Bitwise OR could be null.
+  BinaryOperator::Opcode Op = SIE->getOpcode();
+  if (!BinaryOperator::isBitwiseOrShiftOp(Op) || Op == BO_Or)
+    return State;
+
+  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
+  const SymExpr *CurrentSym = SIE->getLHS();
+  if (const RangeSet *CurrentRS = Constraints.lookup(CurrentSym)) {
+    const RangeSet NewRS = assumeNonZero(BV, F, CurrentSym, *CurrentRS);
+
+    // If the 'NewRS' is not empty it means the 'CurrentSym' is not assumed
+    // to be concrete zero, so it does not contradicts with the non-null
+    // assumption and we could apply the new constraint ranges.
+    if (!NewRS.isEmpty()) {
+      State = State->set<ConstraintRange>(CurrentSym, NewRS);
+    } else {
+      return nullptr;
+    }
+  }
+
+  return State;
+}
+
 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);
RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym,
   llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment;
   llvm::APSInt Upper = Lower;
   --Lower;
   ++Upper;
 
   // [Int-Adjustment+1, Int-Adjustment-1]
   // Notice that the lower bound is greater than the upper bound.
   RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower);
+
+  if (!(St = applyBitwiseRanges(St, getBasicVals(), F, New, Sym)))
+    return nullptr;
+
   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
 }
 
 ProgramStateRef
 RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym,
                                     const llvm::APSInt &Int,
                                     const llvm::APSInt &Adjustment) {
   // Before we do any real work, see if the value can even show up.
   APSIntType AdjustmentType(Adjustment);
   if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
     return nullptr;
 
   // [Int-Adjustment, Int-Adjustment]
   llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
   RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt);
+
+  if (!(St = applyBitwiseRanges(St, getBasicVals(), F, New, Sym)))
+    return nullptr;
+
   return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
 }
 
 RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St,
                                                SymbolRef Sym,
                                                const llvm::APSInt &Int,
                                                const llvm::APSInt &Adjustment) {
   // Before we do any real work, see if the value can even show up.

clang/test/Analysis/bitwise-nullability.cpp

+// RUN: %clang_analyze_cc1 \
+// RUN:  -analyzer-checker=core \
+// RUN:  -analyzer-output=text -verify %s
+
+typedef unsigned long long uint64_t;
+
+void test_null_lhs_range_to_non_null_result_infeasible(uint64_t Magic) {
+  uint64_t MaskedMagic = Magic & (0xffffffffffffffffULL >> 13);
+
+  if (Magic) {
+    // no-note: 'Assuming 'Magic' is 0' was here.
+    return;
+  }
+
+  if (MaskedMagic) {
+    // no-note: 'Assuming 'MaskedMagic' is not equal to 0' was here.
+    (void)(1 / Magic); // no-warning
+  }
+}
+
+void test_non_null_lhs_range_to_null_result_feasible(uint64_t Magic) {
+  uint64_t MaskedMagic = Magic & (0xffffffffffffffffULL >> 13);
+
+  if (!Magic) {
+    // expected-note@-1 {{Assuming 'Magic' is not equal to 0}}
+    // expected-note@-2 {{Taking false branch}}
+    return;
+  }
+
+  if (!MaskedMagic) {
+    // expected-note@-1 {{Assuming 'MaskedMagic' is 0}}
+    // expected-note@-2 {{Taking true branch}}
+    (void)(1 / !Magic);
+    // expected-note@-1 {{'Magic' is not equal to 0}}
+    // expected-note@-2 {{Division by zero}}
+    // expected-warning@-3 {{Division by zero}}
+  }
+}

clang/test/Analysis/bitwise-ranges.cpp

+// RUN: %clang_analyze_cc1 \
+// RUN:  -analyzer-checker=core,debug.ExprInspection \
+// RUN:  -verify %s
+
+void clang_analyzer_eval(int);
+
+void test_range(unsigned int X) {
+  if (X < 2 || X > 3)
+    return;
+
+  clang_analyzer_eval(X >= 2 && X <= 3);
+  // expected-warning@-1 {{TRUE}}
+
+  // We have no non-null constraint range information available for 'A'.
+  unsigned int A = X | 8;
+  clang_analyzer_eval(A == 0);
+  // expected-warning@-1 {{FALSE}}
+
+  unsigned int B = X & 8;
+  clang_analyzer_eval((B >= 1 && B <= 8) || B == 0);
+  // expected-warning@-1 {{TRUE}}
+
+  unsigned int C = X & 1;
+  clang_analyzer_eval(C == 1 || C == 0);
+  // expected-warning@-1 {{TRUE}}
+
+  void(X / 0);
+  // expected-warning@-1 {{division by zero is undefined}}
+  // expected-warning@-2 {{Division by zero}}
+}