[cfe-dev] Building Integer Set Library (ISL) Codebase with Clang Static Analyzer | Results

[Malhar Thakkar via cfe-dev]

Hello everyone,

As part of my GSoC project
<https://summerofcode.withgoogle.com/projects/#4884807304609792>, 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 positives 395
True positives 148
Not sure 37
Total 580
*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 positives 323
Use-after-free false positives 38
Use-after-release-false positives 31
Bad release false positives 3
Total false positives 395
*Leaks:*
Leaks (Total = 323)
obj_free() false positives 213
obj_cow() false positives 41
explicit free false positives 24
Impossible execution path 1
function pointer false positives 44
Total leak false positives 323

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 positives 72
*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
ᐧ
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20170626/5ae4e2df/attachment.html>