Building Integer Set Library (ISL) Codebase with Clang Static Analyzer | Results

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Building Integer Set Library (ISL) Codebase with Clang Static Analyzer | Results

Adam Cieszkiel via cfe-dev
Hello everyone,

As part of my GSoC project, I ran the ISL (Integer Set Library) codebase through Clang Static Analyzer which by its checker for reference counting (checking for improper memory management) called RetainCountChecker produced the following diagnostics.

Results of building the ISL codebase with scan-build:
False positives395
True positives148
Not sure37
Total580

Note: Most of the true positives (121 to be exact) arise due to missing annotations in the declarations of various functions.

Types of false positives:
Leak false positives323
Use-after-free false positives38
Use-after-release-false positives31
Bad release false positives3
Total false positives395

Leaks:

Leaks(Total = 323)
obj_free() false positives213
obj_cow() false positives41
explicit free false positives24
Impossible execution path1
function pointer false positives44
Total leak false positives323


As you can see from the stats mentioned above, most of the leak false positives are due to functions of the type obj_free() where obj is some ISL object like isl_basic_map, isl_basic_set, isl_map, etc. 

The explanations of these false positives are given below.


obj_free()

#define __isl_give __attribute__((cf_returns_retained))

#define __isl_take __attribute__((cf_consumed))


__isl_null obj *obj_free(__isl_take obj *o)

{

if (!o)

return NULL;

 

if (--o->ref > 0)

return NULL; // Leak warning for ‘o’.

 

// Freeing the fields of 'o'

free(o);

 

return NULL;

}



__isl_give obj *foo(__isl_take obj *o){

return obj_free(o);

}


__isl_give obj *bar(__isl_take obj *o);

 

__isl_give obj *dummy(__isl_take obj *o) {

o = bar(o); // Reference count of 'o' = +1 after calling 'bar'

o = foo(o);

return o;

}


In the above example, consider the analysis to start from 'dummy'.
When the reference counted object 'o' is passed to foo and eventually to obj_free(), in the second 'if' condition inside obj_free(), although the reference count is decremented (according to ISL's convention), the analyzer interprets it as just a change in some field of 'o' and then raises a leak warning.

Along another path in obj_free(), the explicit use of 'free(o)' also raises a leak warning since free() does not decrement the reference count of 'o'. I have labelled them as 'explicit free false positives'. These explicit free false positives are encountered mainly in the case of character pointers and isl_dim_map pointers as they are the only ones who are always freed using free() in the ISL codebase.


obj_cow()
In case definition of obj_cow() can be accessed by the analyzer, similar to obj_free(), leak warnings are raised as obj_cow() don't deallocate an object per se instead just the reference counters are altered.


#define __isl_give __attribute__((cf_returns_retained))

#define __isl_take __attribute__((cf_consumed))


__isl_give obj *obj_dup(__isl_keep obj *passed_leak_warning_obj) {

// Some code which does not deallocate passed_leak_warning_obj

}

 

__isl_give obj *obj_cow(__isl_take obj *passed_leak_warning_obj) {

if(!passed_leak_warning_obj)

return NULL;

if(passed_leak_warning_obj->ref == 1)

return passed_leak_warning_obj;

passed_leak_warning_obj->ref--;

return obj_dup(passed_leak_warning_obj);

}

 

__isl_give obj *foo(some arguments) {

obj *leak_warning_obj;

leak_warning_obj = some_function_returning_isl_give_pointer(some_parameters); // retain count = +1

leak_warning_obj = obj_cow(leak_warning_obj);

// Now, the use of leak_warning_obj raises a leak warning about it.

}


In the above example, assume that the analysis starts from the function foo. When leak_warning_obj obtained with a retain count of +1 is passed to obj_cow(), it is not consumed so to speak which leads the analyzer to raise a leak warning.

Function pointers
Now, there are two different kind of usages of function pointers which lead to leak false positives.

Case 1
Consider a function ‘bar’ whose pointer is a field of 'some_obj' and is accessible inside a function ‘foo’. If an object in foo (obtained as an __isl_give) pointer is passed to ‘bar’ which takes this object with an __isl_take annotation, it still raises a leak warning for that object.


#define __isl_give __attribute__((cf_returns_retained))

#define __isl_take __attribute__((cf_consumed))


__isl_give obj *foo(some_arguments) {

abc *obj2 = some_function_returning_isl_give_pointer(some_parameters);

some_obj->bar(obj2); // Leak warning for obj2

// Some code

}


Case 2

The below type of false positives are raised only when the clang's static analyzer starts analysis from such functions. Now, the analyzer has no idea about 'fn' whatsoever and hence, it raises a leak warning for 'o'. Had the analyzer entered 'foo' from some other function, it would know what 'fn' was and wouldn't have raised a leak warning for 'o'.

#define __isl_give __attribute__((cf_returns_retained))

#define __isl_take __attribute__((cf_consumed))


__isl_give obj *foo(__isl_give (*fn)(__isl_take obj *o), __isl_take obj *o) {

o = some_function_returning_an_isl_give_pointer();

o = fn(o); // Leak warning for ‘o’

return o;

}




Use-after-free/Use-after-release/Bad-release:
Use-after-free/Use-after-release/Bad-release false positives(Total = 72)
obj_copy() false positives72

obj_copy()


#define __isl_give __attribute__((cf_returns_retained))

#define __isl_take __attribute__((cf_consumed))


__isl_give isl_basic_map *bar(__isl_take isl_basic_map *bmap);

 

__isl_give isl_basic_map *isl_basic_map_dup(__isl_keep isl_basic_map *bmap);

 

__isl_give isl_basic_map *isl_basic_map_copy(__isl_keep isl_basic_map *bmap)

{

if (!bmap)

return NULL;

 

if (ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL)) {

bmap->ref++;

return bmap;

}

bmap = isl_basic_map_dup(bmap);

if (bmap)

ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);

return bmap;

}


__isl_give isl_basic_map *foo(__isl_take isl_basic_map *bmap) {

isl_basic_map *temp;

isl_basic_map *temp2 = bmap;

bmap = isl_basic_map_reverse(bmap);

temp = bar(isl_basic_map_copy(bmap));

isl_basic_map_free(bmap); // Use-after-release warning for ‘bmap’

return temp;

}


In the above example, as the analyzer has access to isl_basic_map_copy(), it analyses its body as well only to find that 'bmap' and the object returned from isl_basic_map_copy(bmap) point to the same memory location. Hence, when the copy is passed inside 'bar', the original 'bmap' is released which raises the 'use-after-release' warning for 'bmap' when it returns from 'bar'.


False Negatives
Now, let's take a look at some of the mistakes which are overlooked by the analyzer.

Callee-side Parameter Checking
Currently, callee side checking of annotations on parameters is not performed. For example, the current RetainCountChecker doesn’t warn if an object passed with __isl_take is not freed in a function. Also, the current checker doesn’t warn if an object passed with __isl_keep is further passed with an __isl_take argument to some function. Consider the following examples.


#define __isl_give __attribute__((cf_returns_retained))

#define __isl_take __attribute__((cf_consumed))


__isl_give isl_basic_set *foo(__isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2){

bset2 = isl_basic_set_cow(bset2);

return bset2; // No leak warning for bset1 is raised here.

}

 

__isl_give isl_basic_set *bar(__isl_keep isl_basic_set *bset1){

return isl_basic_set_free(bset1); // No bad release warning for bset1 is raised here.

}


Returning a Reference Counted Object After Passing it to a Function as an __isl_take Object.
Example


#define __isl_give __attribute__((cf_returns_retained))

#define __isl_take __attribute__((cf_consumed))


__isl_null isl_basic_map *isl_basic_map_free(__isl_take isl_basic_map *bmap);


__isl_give isl_basic_map *dummy(__isl_keep isl_basic_map *bmap) {

isl_basic_map *temp = isl_basic_map_copy(bmap);

isl_basic_map_free(temp);

return temp; // No use-after-release warning raised here.

}


Note 1: The above kind of false negatives occur only when the definition of function to which it is passed as an __isl_take argument (isl_basic_map_free() in this case) is not present in the same file as the one being analyzed. The visibility of obj_free() leads to the analyzer following the path in obj_free() where an explicit free() is called and then Clang Static Analyzer’s MallocChecker raises a use-after-free warning.

 

Note 2: If temp were passed passed to some other function as an __isl_take argument rather than returning it from ‘dummy’, it would’ve produced a ‘use-after-release’ warning like it should.






I am currently in talk with my mentors, Dr. Devin Coughlin, Dr. Sven Verdoolaege and Dr. Alexandre Isoard to come up with a good solution to fix the aforementioned false positives and false negatives.

According to them, and I agree, coming up with a solution for function pointers is probably the most difficult task.


Let me know your thoughts on the same.


Thank you.



Regards,
Malhar Thakkar

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Loading...