[cfe-dev] Static Analyzer Rocks Hard

[Matthew Jimenez]

On Jun 19, 2008, at 1:46 PM, Ted Kremenek wrote:

>
> 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

Ah, sorry about that. This first case was unintended. The thought was  
to show a reason the array may need filtering.
I probably should have put a comment into isAllowed: indicating it  
might not always be the case; perhaps the method might be implemented  
differently in a subclass.

>
>
> 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).
>

Yes, this was what I was thinking, however I am unsure how I feel  
about it.
Obviously any case where the allocation or initialization fail here  
would cause the code to misbehave, and this is something I had not  
taken into full consideration.
Asserting the values after allocating them causes the analyzer to not  
report any problems, but that might be overkill.

Perhaps what I'm more interested in are flags for the analyzer for  
assumptions it may be allowed to make.
Normal behavior assuming allocation is always working and a flag to  
assume allocation could fail (or perhaps the reverse).
Although, too many such flags might also be quite bad.

Thoughts?
-Matthew