[cfe-dev] Static Analyzer Rocks Hard

[Ted Kremenek]

On Jun 18, 2008, at 3:35 PM, Matthew Jimenez wrote:

> Thanks for the awesome work put into the static analyzer. With it I  
> was able to find a pretty decent number of memory leaks and dead- 
> store that made me think, "why the hell did we think that was a good  
> idea in the first place?"
> I've not run it against everything I can, but I am very impressed  
> with it so far.

Hi Matthew,

It's great to hear that you are already getting some mileage out of  
the tool.  It's still an early stage tool, and we'll continue to  
aggressively work on making it better (and catch more bugs!)

> I have found one false positive in my code that might be a good  
> candidate to ignore, although I might consider changing my code  
> anyway.
> I wrote a test case based on some of the idea behind it (attached).
> It can be tested with `scan-build -o . ccc-analyzer -c -o test.o  
> test.m`

This is an interesting test case.  I'm not certain what you thought  
was the salient points I was suppose to notice, but here's my  
observations:

1) The branch condition:

         if ([self isAllowed:rid]) {

should always be true because:

   - (BOOL) isAllowed: (id) obj
   {
      return YES;
   }

In my output from scan-build, however, the reported path to the memory  
leak indicates a case where the false branch is taken (which is not  
possible).

The reason for the analyzer reporting this infeasible path is because  
right now the analysis doesn't do any inter-procedural analysis.  This  
is a known limitation.  We're planning on implementing inter- 
procedural analysis in stages; in general inter-procedural analysis  
requires a fair amount of boilerplate infrastructure so that we can  
reason about the definitions of functions/methods across translation  
units.

I should mention that the reported leak manifests even if you replace  
the condition with "1" (making the branch unconditional):

    if (1) {

So, while the analyzer does indeed report a false path, the falseness  
of the path has nothing to do with the warning itself.

2) The memory leak has to do with the following snippet of code:

             if (!sql) {
                 sql = [[NSMutableString alloc]  
initWithString:@"select * from random_table where rid in (?"];
                 args = [[NSMutableArray alloc] init];
             } else {
                 [sql appendString:@", ?"];
             }
             [args addObject:rid];

What happens is that "sql" is assigned an object (which the analyzer  
assumes could be NULL if "alloc" failed), and then "args" is assigned  
an object (which also could be NULL).  When we do another iteration of  
the loop, the new value of "sql" is compared against null:

   if (!sql) { ...

The analyzer, believing that the value could be NULL or a valid  
object, believes that the true branch is feasible (which it  
technically is).  We then allocate a new value to store to sql, and  
then allocate a new value to store to args.  At this point "args" is  
overwritten, which the analyzer believes could be a valid object that  
was allocated on the previous loop iteration.  So, technically there  
is a leak here.

In reality, this leak probably wouldn't happen.  If "sql" was assigned  
a NULL value because "alloc" failed, chances are that the allocation  
to "args" also failed because memory allocation failures are  
correlated.  Thus at the end of the basic block for the true branch of  
"if (!sql)" we really should have the following possibilities:

   (a) both sql and args are null  (allocation failed first for sql,  
then args)
   (b) sql is not null, but args is null (allocation succeeded for  
sql, but failed for args)
   (c) neither sql or args are null (allocation succeeded in both cases)

If we assume that these are the only possibilities (and not a fourth  
possibility, where allocation failed for sql but succeeded for args),  
then there is no leak.

Is this the false positive that you were thinking about?  If so, this  
extra reasoning about correlated allocation failures is something that  
could be implemented fairly easily in the static analyzer (and I would  
be happy to do it).

Thanks for the feedback!

Cheers,
Ted