| |||||||||||||
Caveat: GCC-based analysis unreliable for Free SoftwareCaveat: GCC-based analysis unreliable for Free SoftwarePosted Jan 26, 2010 5:13 UTC (Tue) by pjm (subscriber, #2080)Parent article: LCA: Static analysis with GCC plugins
The article fails to point out an important limitation of using a gcc plugin (or other gcc output) for static analysis: the analysis result is only valid for *this build*, and is not in general valid even for different builds for the same platform, and certainly not guaranteed for when other people build the software from source with a different compiler.
For example, different compilation options can lead to different __builtin_constant_p results (and hence different code paths and different analysis results); and obviously different #include file contents or different architectures can lead to different analysis results.
This isn't a mere theoretical concern: an example that's already bitten the Mozilla folk is a bug caused by argument evaluation order being unspecified in C[*1], and indeed differing in practice among platforms of interest to Mozilla.
This limitation may be fine for proprietary software and other projects where most users use original-developer-supplied binaries, whereas most open-source projects must take gcc-based analysis results with a grain of salt.
That's not to say that gcc-based static analysis isn't useful for source-based projects (and Mozilla use it despite being aware of the limitation): it can still point to cases where a bad thing (buffer overflow or whatever) is possible, but it can't show that something is impossible. Thus, for example, it can't with certainty say that a section of code is dead code.
[*1] Ref: Section Function calls in the C99 spec, para #10.
(Log in to post comments)
Caveat: GCC-based analysis unreliable for Free Software Posted Jan 26, 2010 11:06 UTC (Tue) by marcH (subscriber, #57642) [Link]
> an example that's already bitten the Mozilla folk is a bug caused by argument evaluation order being unspecified in C[*1], and indeed differing in practice among platforms of interest to Mozilla.
Surely you can plug into gcc parser while ignoring gcc's evaluation order? And consider all possible orders in your analysis.
By the way two different results are also allowed for this:
Caveat: GCC-based analysis unreliable for Free Software Posted Jan 26, 2010 11:54 UTC (Tue) by pjm (subscriber, #2080) [Link]
(i) If I understand the suggestion correctly, then the results would still be specific to a single preprocessor output. Making an analysis valid for all possible <stdio.h> etc. contents involves much more work. Though I'll grant that making an analysis specific to a single set of preprocessor outputs is better than making an analysis specific to a single build.
(ii) By using less of gcc, there's more work for the analysis code to do. For example, you need to work out what all the valid evaluation orders are, and all the possibilities for other things unspecified in C. Which brings us to:
(iii) x-- * x++ is actually undefined rather than unspecified[*1], so it would be a bug for such code to exist at all; but yes, there are many things that the C spec describes as being unspecified (i.e. having more than one allowable behaviour).
[*1] Ref: Section Expressions in the C99 spec, para #2. Or para #3 of section Expressions in the C++ spec, if we're talking about C++ code such as Mozilla.
Caveat: GCC-based analysis unreliable for Free Software Posted Jan 26, 2010 12:54 UTC (Tue) by marcH (subscriber, #57642) [Link]
> If I understand the suggestion correctly, then the results would still be specific to a single preprocessor output.
Yes, I was only commenting on the evaluation order example. I feel like this specific example does not really make shine your argument.
> By using less of gcc, there's more work for the analysis code to do. For example, you need to work out what all the valid evaluation orders are, and all the possibilities for other things unspecified in C.
Yes. But I do not think you can seriously escape from working out all the possible evaluation orders, can you? Apart from switching to a better specified language (or to one discouraging side-effects). Because even gcc could change its evaluation order from one release to the next.
> x-- * x++; is actually undefined rather than unspecified[*1]
Oups, sorry. It is also too convoluted. So maybe this one is unspecified but defined:
( x++ ) * x
Caveat: GCC-based analysis unreliable for Free Software Posted Jan 26, 2010 14:14 UTC (Tue) by pjm (subscriber, #2080) [Link]
> But I do not think you can seriously escape from working out all the possible [behaviours of unspecified constructs], can you?
We should clarify that one needn't explicitly enumerate the possible behaviours, but yes, the fact that there are many valid behaviours for a given set of .c/.cc files is ultimately why analysis using gcc plugins doesn't in general give reliable results for Free Software (in the sense more precisely described in my initial post).
Caveat: GCC-based analysis unreliable for Free Software Posted Jan 26, 2010 21:22 UTC (Tue) by paulj (subscriber, #341) [Link]
A static analyser should be able to warn just fine about multiple stores to
objects in the same sequence point (aliases excepted). Such code is inherently buggy.
Caveat: GCC-based analysis unreliable for Free Software Posted Jan 26, 2010 22:16 UTC (Tue) by Azazel (subscriber, #3724) [Link]
> > x-- * x++; is actually undefined rather than unspecified[*1]
> > Oups, sorry. It is also too convoluted. So maybe this one is unspecified but defined: > > ( x++ ) * x
Also undefined, I believe. Consider:
x++ * x
is equivalent to:
tmp = x
However, C and C++ do not guarantee the order in which the last two occur, so the
tmp * tmp
or
tmp * (tmp + 1)
or something else entirely (e.g., nasal daemons) if the compiler is clever
Az.
Caveat: GCC-based analysis unreliable for Free Software Posted Jan 26, 2010 23:11 UTC (Tue) by marcH (subscriber, #57642) [Link]
> tmp * tmp
> or > tmp * (tmp + 1) > or > something else entirely
I think it is NOT "something else entirely", but either the first or the second. This is what I meant by "unspecified but defined".
Caveat: GCC-based analysis unreliable for Free Software Posted Jan 28, 2010 4:35 UTC (Thu) by BenHutchings (subscriber, #37955) [Link]
Evaluation of an expression that involves reading and writing the same memory location, or writing to it twice, has undefined behaviour, except where (1) a single operation combines reading and writing (e.g. ++) (2) the two operations are ordered by a 'sequence point'. (Note that 'sequence points' are not actually points in a sequence, but define a partial ordering relation.)
Caveat: GCC-based analysis unreliable for Free Software Posted Jan 28, 2010 9:59 UTC (Thu) by marcH (subscriber, #57642) [Link]
My bad, I trusted Paragraph 7.12 "Order of evaluation" in Harbison and Steele's venerable "C Reference manual". Quoting it:
> but the effect will be as if it chose one argument, evaluated fully, then chose another argument, > [...] > similar holds for binary expressions
Search "but the effect will", page 254 in: http://www.careferencemanual.com/errata.htm
Anyway I doubt there is any good reason to ever throw a side-effect into a larger expression. I find this discussion entertaining, but actually relevant to bad programmers only.
Caveat: GCC-based analysis unreliable for Free Software Posted Jan 27, 2010 16:19 UTC (Wed) by jzbiciak (✭ supporter ✭, #5246) [Link] (ii) By using less of gcc, there's more work for the analysis code to do. For example, you need to work out what all the valid evaluation orders are, You just need to scan the list once and work out if any of the arguments have side effects. If two arguments have side effects on objects that may alias (and I imagine you can consult GCC's alias analysis to get a "YES/MAYBE/NO" answer), throw a warning. That doesn't require generating and analyzing all N! potential orderings among N arguments. It just requires an O(M2) loop to check pairwise for all pairs, where M is the number arguments with side effects. M is generally rather small, too. And I'd hope GCC has functions to help you find the arguments with side effects.
Caveat: GCC-based analysis unreliable for Free Software Posted Jan 28, 2010 0:15 UTC (Thu) by marcH (subscriber, #57642) [Link]
> If two arguments have side effects on objects that may alias throw a warning.
I think a warning should be thrown even if just one argument has a side-effect on any other.
But to be honest a side-effect in argument passing should not even pass code reviews in the first place. Any side-effect deserves at least a (practically free) temporary variable.
Caveat: GCC-based analysis unreliable for Free Software Posted Jan 28, 2010 16:20 UTC (Thu) by jzbiciak (✭ supporter ✭, #5246) [Link] I think a warning should be thrown even if just one argument has a side-effect on any other. You know, that's closer to what I really meant. I guess I got in a hurry and didn't completely think through what I was suggesting. Basically, if any argument looks like it could potentially modify any other argument, flag it. But to be honest a side-effect in argument passing should not even pass code reviews in the first place. Any side-effect deserves at least a (practically free) temporary variable. I agree. There was a similar (but not identical) situation that bit me once when porting DOOM to one of our DSPs at work for a demo. In the case of DOOM, it wasn't argument order to a function call, but rather order of evaluation of terms in an expression. The weird behavior I was seeing was that the built-in demo (which serves as something like a test case) wouldn't run correctly because the player and/or bad guys wouldn't take exactly the same course they did when the demo was recorded. The DOOM engine is supposed to be deterministic--if you run through the course in exactly the same way every time, then everything should behave identically. DOOM has a "random number" function (P_Random()) that just returns the next unsigned byte out of a table of random bytes, keeping a pointer to which one is next. It resets this pointer at the start of the game. This allows the engine to ask for a "random" number and get a deterministic stream each time. That function was fine. The problem was with how it was being called. There were several places in the code where the engine wanted a signed random number that had more of a triangular distribution. To get that, it would do this: P_Random()-P_Random() That idiom appears about a dozen places in the code. You can guess what happened. GCC would make the two function calls in left-to-right order. Our DSP's compiler, however, made them in right-to-left order. *d'oh* Same class of problem (getting burned by side effects where order isn't defined), just a different manifestation. It was this particular case I had in mind when I made my original comment. That said, your point is still quite valid. foo(x, ++x) is no better than foo(++x, ++x).
Caveat: GCC-based analysis unreliable for Free Software Posted Jan 27, 2010 7:10 UTC (Wed) by njs (guest, #40338) [Link]
Anyway, AFAICT a lot of what they want to do isn't fancy provably correct elimination of dead code, etc., but "simple" rewriting (e.g., to tear out pointless abstraction layers), where just getting a real AST is enough to get started (though macros etc. will still make your life real interesting).
|
|||||||||||||