[analyzer] false positive in loop?

Hi guys,

Does this chunk of code represent a false positive? it warns a double free. I’m being too ambitious?

// Does a walk through the list looking for even numbers. If any,

// it frees obj parameter.

static void walkthrough(IntegerList list, char* obj) {

for (int i = 0; i<list.getSize(); i++) {

int number = list.at(i);

if (number % 2 == 0){

free(obj); ← Attempt to release free memory

}

}

}

// Tell if the list has at least one even number.

bool hasEvenNumbers(IntegerList list) {

for (int i = 0; i<list.getSize(); i++) {

int number = list.at(i);

if (number % 2 == 0){

return true;

}

}

return false;

}

void loopExample(IntegerList list){

char* obj = (char*)malloc(sizeof(char));

free(obj); ← First free statement.

if (!hasEvenNumbers(list)){

walkthrough(list, obj);

}

else {

std::cout << “The list has at least one even number!” << std::endl;

}

}

Thanks!

Hi guys,

Does this chunk of code represent a false positive? it warns a double
free. I'm being too ambitious?

// Does a walk through the list looking for even numbers. If any,

// it frees obj parameter.

static void walkthrough(IntegerList list, char* obj) {

for (int i = 0; i<list.getSize(); i++) {

int number = list.at(i);

if (number % 2 == 0){

free(obj); <- Attempt to release free memory

If execution ever reaches here ^,

     }

   }

}

// Tell if the list has at least one even number.

bool hasEvenNumbers(IntegerList list) {

for (int i = 0; i<list.getSize(); i++) {

int number = list.at(i);

if (number % 2 == 0){

returntrue;

     }

   }

returnfalse;

}

void loopExample(IntegerList list){

char* obj = (char*)malloc(sizeof(char));

free(obj); <- First free statement.

it must have passed through here ^... Meaning, if the second statement is ever executed, it is always a double free.

Jon

Hi Jonathan,

Thanks for helping me out with this. My question pointed to whether the analyzer can learn (or not) that the only way the program executes the free statement in the method ‘walkthrough’ is when the list passed on as a parameter has at least one even number. But in the caller, we are making sure that if the list indeed has even numbers, the if condition (in loopExample method) should have taken us to the false branch.

If hasEvenNumbers returns false, it means there is no even number on the list, does the analyzer not store that constraints on the symbols associated to the element of the list? If this information is available in walkthrough we could invalidate those paths that make the “number % 2 == 0” condition true, which takes us to the free statement.

Am I doing anything wrong here? Makes sense?

I think this case is of an actual false positive:

(1) Our constraint solver (RangeConstraintManager) is very simple and doesn't yet handle constraints like "x is odd" properly. Not quite sure, in fact maybe at least adding a "== 0" range on the SymIntExpr "x % 2" should have helped, why don't we do at least that? I'd have had a look.

(2) If IntegerList::at() is not inlined properly (doesn't have its body available for analysis), then the analyzer would not realize that the symbol checked in hasEvenNumbers() is the same symbol that is checked in walkthrough(); at() may return a different value, and blindly assuming this value to be the same (eg. assuming all unknown functions to be pure) would make things a lot worse. This is a more complicated work of supporting (evalCall'ing or BodyFarm'ing) STL containers, assuming IntegerList is a typedef for some std::list<int>, or if you use custom containers, then you need to have a checker to support them, or inter-unit analysis may be of use if the body of container methods is in fact available, just in another translation unit.

Hi Artem,

Thank you for your help. The definition of the list is available in the current translation unit, but I was able to turn off the warning changing the variable list to be a pointer, and using concrete values for the condition of the iteration instead of “i < list.getSize*()*”. As I understand, loops, by default, unroll a fixed amount of times when the condition is symbolic, defining like a symbolic offset. Do we keep any reasoning about this symbolic offset? if the iteration unroll say 4 times, and the condition is “int i = 0; i<list.getSize()**; i++”, maybe I will expected the variable i to have the concrete values 0, 1, 2 and 3 at a time. Is this thought wrong?

When the list is passed on by value, even when using concrete values for the condition, the analyzer reports the bug. Why could it be happening? Maybe because of the same thing happening in the symbolic iteration of the copy constructor.

The list definition is pretty simple:

class IntegerList {

private:

int* ptr;

int size;

int maxCapacity;

public:

IntegerList(int maxCapacity){

ptr = new int[maxCapacity];

this->maxCapacity = maxCapacity;

this->size = 0;

}

~IntegerList(){free(ptr);}

IntegerList(const IntegerList& IL){

ptr = new int[IL.size];

for (int i = 0 ; i < IL.size; i++){

ptr[i] = IL.at(i);

}

size = IL.size;

maxCapacity = IL.maxCapacity;

}

int getSize() const {return size;}

int at(int pos) const {return (pos>=0 && pos<size)?ptr[pos]:-1;}

void add(int elem){

if (size < maxCapacity){

ptr[size]=elem;

size++;

}

}

};

Had a closer look.

The false positive is not occuring while analyzing loopExample(); it's occuring while analyzing walkthrough() as a top-level function. You should have noticed it when looking at the reported path (eg. in html report, see attached file; i'm also attaching the raw source code).

So at a glance, it's a topological-sort problem. Let's go a bit deeper though:

   $ clang --analyze test.cpp -Xanalyzer -analyzer-display-progress
   ANALYZE (Syntax): test.cpp IntegerList
   ANALYZE (Syntax): test.cpp ~IntegerList
   ANALYZE (Syntax): test.cpp IntegerList
   ANALYZE (Syntax): test.cpp getSize
   ANALYZE (Syntax): test.cpp at
   ANALYZE (Syntax): test.cpp walkthrough
   ANALYZE (Syntax): test.cpp hasEvenNumbers
   ANALYZE (Syntax): test.cpp loopExample
   ANALYZE (Path, Inline_Regular): test.cpp loopExample
   ANALYZE (Path, Inline_Regular): test.cpp walkthrough
   ANALYZE (Path, Inline_Regular): test.cpp IntegerList
   ANALYZE (Path, Inline_Regular): test.cpp ~IntegerList
   ANALYZE (Path, Inline_Regular): test.cpp IntegerList
   test.cpp:37:7: warning: Attempt to free released memory
         free(obj);
         ^~~~~~~~~
   test.cpp:56:5: warning: Use of memory after it is freed
       walkthrough(list, obj);
       ^~~~~~~~~~~~~~~~~~~~~~
   2 warnings generated.

What we see there is that walkthrough() is truly analyzed as a top-level function. However, we shouldn't be analyzing this function as top-level, as it was already inlined during analysis of loopExample() (regardless of the fix proposed in http://reviews.llvm.org/D15410 , this case accidentally works correctly).

Now, was it? No, in fact, it wasn't inlined during analysis of loopExample(). Because there's another warning on line 56, thrown *before* the call (on PreStmt<CallExpr>). This warning generates a sink, and analysis of walkthrough() doesn't even start. So the analyzer decides to have a look at walkthrough separately, and notices that it would double-free the given pointer if at least two numbers in the list are even, which is, at least, a vacuous truth.

IMHO follow-up:
(1) Sinks are often evil, and this particular sink is certainly misplaced, as the error of sending a dead pointer to a function is not fatal(?)
(2) Perhaps we shouldn't be analyzing static (anonymous-namespaced, etc.) functions as top-level at all(?) This still needs to check functions exported as callbacks, probably.
(3) The code, i think, still has non-fatal problems, i'd prefer to refactor any code that relies on passing dead pointers around or inobviously freeing the same pointer multiple times depending on complicated computations, and i don't think it's really all that bad that the static analyzer warns here, though the warning is a bit unobvious.
(4) Probably add note: diagnostics to the console diagnostic printer, so that people who don't use HTML diagnostics (or scan-build) had a chance to notice that we also provide a path to look at? We may add it as a -cc1 option disabled by default but enabled by --analyze, so that tests didn't break too much.

report-f1a447.html (13.1 KB)

test.cpp (1.19 KB)