What does Coverity/clang static analysis actually do?

[Brad Roberts]

Walter Bright wrote:
> Brad Roberts wrote:
>> 1) Rich flow control.  They go well beyond what's typically done by
>> compiliers during their optimization passes.  They tend to be
>> whole-code in scope and actually DO the parts that are hard, like
>> cross expression variable value tracking similar to a couple examples
>> in this thread.  Function boundaries are no obstacle to them.  The
>> only obstacle is where source isn't provided.
> 
> Modern compiler optimizers (including dmc and dmd) DO do
> cross-expression variable tracking. They just don't often do it
> inter-function (called inter-procedural analysis) because of time and
> memory constraints, not that it is technically more difficult.

Exactly my point.. compilers tend to make the opposite trade off that tools like
Coverity do.  Not that compilers can't or don't.  They just usually do a small
subset of what is possible in the grander sense of 'possible'.

> C and C++ do have some issues with inter-procedural analysis because the
> compiler view of them, at heart, is single file. D is much more
> conducive to that because the compiler sees an arbitrarily large part of
> the source code, and can obviously see all of it if the user so desires.

Neither c nor c++ as languages are _required_ to do single file compilation.
That's just what most compilers do.  In fact, gcc/g++ have been capable of doing
whole-app compilation for a couple years now -- though not many people use it
that way as far as I can tell.  See also, exact same issue as above.. it's a
trade off.

>> 2) Due to working with whole source bases, the UI for managing the
>> data produced is critical to overall usability.  A lot of time goes
>> into making it easy to manage the output.. both for single runs and
>> for cross-run flow of data.  Some examples:
>>
>>    * suppression of false positives, 
> 
> I'd rather do a better job and not have false positives.

Of course you would.. everyone would.  It's a meaningless statement since no one
would ever contradict it with any seriousness.  At the risk of repeating
myself.. same tradeoffs again.

>>    * graphing of issue trends
> 
> That's a crock <g>.

Uh, whatever.  Most of the rest of us humans respond much better to pictures and
trends than to raw numbers.  Show me some visual indication of the quality of my
code (ignoring the arguments about the validity of such graphs) and I can pretty
much guarantee that I'll work to improve that measure.  Nearly everyone I've
ever worked with behaves similarly.. once they agree that the statistic being
measured is useful.  One of the best examples is percent of code covered by unit
tests.  The same applies to number of non-false positive issues discovered
through static analysis.

A specific case of this:  At informix we had a step in our build process that
ran lint (yes, it's ancient, but this was a decade ago and the practice was at
least a decade old before I got there).  Any new warnings weren't tolerated.
The build automatically reported any delta over the previous build.  It was
standard practice and kept the code pretty darned clean.

>>    * categorization of issue types
> 
> I'm not convinced that is of critical value.

You don't need to be.  You view too many things in black/white terms.

>> 3) Rule creation.  The core engine usually generates some digested
>> dataset upon rules are evaluated.  The systems come with a builtin set
>> that do the sorts of things already talked about.  In addition they
>> come with the ability to develop new rules specific to your
>> application and business needs.  For example:
>>
>>    * tracking of taint from user data
>>    * what data is acceptable to log to files (for example NOT
>> credit-cards)
> 
> There have been several proposals for user-defined attributes for types,
> I think that is better than having some external rule file.

Again, this is where trade offs come in.  If it can be done cheaply enough to
warrant being done during compilation and is accurate enough in small scoped
analysis.. yay.  But sometimes you still want to do things that take more time
and more completely.

>> 4) They're expected to be slower than compilation, so it's ok to do
>> things that are computationally prohibitive to do during compilation
>> cycles.
> 
> I agree.
> 
>> ----
>>
>> I've seen these tools detect some amazing subtle bugs in c and c++
>> code.  They're particularly handy in messy code.   They can help find
>> memory leaks where the call graphs are arbitrarily obscure.  Sites
>> where NULL pointers are passed into a function that dereferences
>> without a null check even when the call graph has many layers.
> 
> Once you get the data flow analysis equations right, they'll detect it
> every time regardless of how subtle or layered the call graph is.
> 
>> Yes, rigid contract systems and richer type systems can help reduce
>> the need for some of these sorts of checks, but as we all know,
>> there's tradeoffs.
>>
>>
>> That help?
> 
> Yes, very much. In particular, I wasn't sure coverity did
> inter-procedural analysis.

That's essentially all it does, if you boil away all the other interesting stuff
layered on top of that core, but it does it very well and with a lot of tooling
around it.

Later,
Brad