[Analyzer] Crash fix for alpha.cplusplus.IteratorRange

[baloghadamsoftware]

Summary

If the non-iterator side of an iterator operation +, +=, - or -= is UndefinedVal an assertions happens. This small fix prevents this.

[baloghadamsoftware]

Unfortunately, I could not create test for it. It is extremely rare that the Analyzer creates an UndefinedVal. I had the following output:

1.	<eof> parser at end of file
2.	While analyzing stack: 
	#0 Calling llvm::object::BindRebaseSegInfo::BindRebaseSegInfo at line /usr/include/c++/7/bits/unique_ptr.h:821:34
	#1 Calling std::make_unique at line 4094
	#2 Calling llvm::object::MachOObjectFile::bindTable at line 4115
	#3 Calling llvm::object::MachOObjectFile::weakBindTable
3.	/home/edmbalo/llvm-project/llvm/lib/Object/MachOObjectFile.cpp:4004:28: Error evaluating statement
4.	/home/edmbalo/llvm-project/llvm/lib/Object/MachOObjectFile.cpp:4004:28: Error evaluating statement

I was analyzing llvm/lib/Object/MachOObjectFile.cpp with all the iterator-related checkers enabled.

[Szelethus]

Yeah, this looks straightforward, but how come you didn't manage to get a small test case? creduce gave up?

[steakhal]

LGTM

In D85424#2199471, @baloghadamsoftware wrote:

Unfortunately, I could not create test for it. It is extremely rare that the Analyzer creates an UndefinedVal.

You can work around the issue by creating a unit-test instead.
In that test, you could create a custom checker, which returns the required Undefined SVal of your desired type.

We need a test to approve this change.

[NoQ]

Tests? (edit: ok, i see, you have trouble reducing the test. yes, we absolutely need a test, please finish with creduce/delta.)

There should be no UndefinedVals in function arguments unless you disable core checkers (which isn't supported).

[baloghadamsoftware]

In D85424#2203329, @NoQ wrote:

Tests? (edit: ok, i see, you have trouble reducing the test. yes, we absolutely need a test, please finish with creduce/delta.)

I will not commit it without tests, even if someone accepts it. We are working on it using creduce.

There should be no UndefinedVals in function arguments unless you disable core checkers (which isn't supported).

Hmm, then it means that instead of this patch we should investigate why the argument is UndefinedVal and fix the issue there. All the core checkers are enabled, of course.

[NoQ]

clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp

228

Well, it looks like your value is not necessarily a function argument. The undefined value checker only catches undefined values passed as arguments directly.

[gamesh411]

CReduce did not manage to produce any meaningful result after a week worth of runtime (more than ~2000 lines of code still remaining after reduction). We could track this down by tracing the ExprEngine code that assigns the Undefined SVal but that seems a huge effort as well. That could be done by debugging the SVal-assigning statements, and setting conditional breakpoints (ie. only break when the value is Undefined). When a breakpoint is hit, we could dump the statement that triggered it and try to reason about the conditions at that point. I also recommend using the rr tool as it allows you to use fixed pointer values while debugging.

[steakhal]

In D85424#2247598, @gamesh411 wrote:

CReduce did not manage to produce any meaningful result after a week worth of runtime (more than ~2000 lines of code still remaining after reduction). We could track this down by tracing the ExprEngine code that assigns the Undefined SVal but that seems a huge effort as well. That could be done by debugging the SVal-assigning statements, and setting conditional breakpoints (ie. only break when the value is Undefined). When a breakpoint is hit, we could dump the statement that triggered it and try to reason about the conditions at that point. I also recommend using the rr tool as it allows you to use fixed pointer values while debugging.

I'm volunteering. I did some debugging lately, I would give a shot catching this.

[steakhal]

OK, after a few hours of debugging, the test code simplifies to this:

// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange -analyzer-config aggressive-binary-operation-simplification=true %s -verify

void foo(int x) {
  int uninit;
  x - uninit; // will-crash
}

The investigation showed that the IteratorRangeChecker::verifyRandomIncrOrDecr will get an Undefined sval for this example, resulting in a crash.
How should I continue this?

[baloghadamsoftware]

Test added. Thank you for the test @steakhal!

[baloghadamsoftware]

In D85424#2258886, @steakhal wrote:

void foo(int x) {

int uninit;
x - uninit; // will-crash

}

This is not even related to the iterators. We could check first whether LHS is an iterator and early exit if not. However, that does not help, the checker crashes if we try to add or subtract an unitialized value to/from an iterator.

[NoQ]

Uh-oh, so you're saying that you're actively modeling every single operator + and - on every single integer in the program even when they don't represent any iterators at all? How can a raw integer be an iterator to begin with, given that you can't dereference an integer? Is this caused by D82185? Can you defend against such situations by checking that the operand is a pointer before doing any operations?

As of now it sounds like the function quits pretty quickly because it doesn't find an old iterator position for that integer but i'm pretty worried about us doing weird things because we're not checking our types regularly enough.

clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp

227

This code, as per my usual concern, is pretty questionable. A Loc may be both the iterator lvalue or the iterator rvalue and you can't figure this out by looking at the value. The information on which the decision to perform this dereference is based should be communicated through a different channel.

232

This comment is probably unnecessary.

clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp

 }
 
 void IteratorRangeChecker::verifyRandomIncrOrDecr(CheckerContext &C,
                                                   OverloadedOperatorKind Op,
                                                   SVal LHS, SVal RHS) const {
   auto State = C.getState();
 
   auto Value = RHS;
   if (auto ValAsLoc = RHS.getAs<Loc>()) {
     Value = State->getRawSVal(*ValAsLoc);
   }
 
-  if (Value.isUnknown())
+  if (Value.isUnknownOrUndef())
     return;
 
   // Incremention or decremention by 0 is never a bug.
   if (isZero(State, Value.castAs<NonLoc>()))
     return;
 
   // The result may be the past-end iterator of the container, but any other
   // out of range position is undefined behaviour
   auto StateAfter = advancePosition(State, LHS, Op, Value);

clang/test/Analysis/iterator-range.cpp

void postfix_minus_assign_2_begin_ptr_iterator(
   i -= 2; // expected-warning{{Iterator decremented ahead of its valid range}}
           // expected-note@-1{{Iterator decremented ahead of its valid range}}
 }
 
 void ptr_iter_diff(cont_with_ptr_iterator<S> &c) {
   auto i0 = c.begin(), i1 = c.end();
   ptrdiff_t len = i1 - i0; // no-crash
 }
+
+int uninit_var(int n) {
+  int uninit; // expected-note{{'uninit' declared without an initial value}}
+  return n - uninit; // no-crash
+  // expected-warning@-1 {{The right operand of '-' is a garbage value}}
+  // expected-note@-2 {{The right operand of '-' is a garbage value}}
+}