10 ms·
CompCert: A formally verified optimizing C compiler
- soup10 12y ago"CompCert typically runs twice as fast as the code generated by GCC without optimizations." Lol, That's like saying you run faster than Usain Bolt when he's walking.
- lifthrasiir 12y agoThere are certain applications that fear the breakage due to the compiler optimization. (Compilers are prone to break, for your information. They are really complex applications after all.) CompCert has a fully verified optimization engine comparable to (I guess) GCC's -O2, so that really is an improvement.
- pascal_cuoq 12y agoIt doesn't get close to “gcc -O2” (the page says within 20% of “gcc -O3”). It is only the most useful optimizations that are implemented in CompCert, at perhaps an implementation cost of one PhD thesis per optimization pass. But that is still better than no optimizations in contexts where none of the optimizations from an off-the-shelf's compiler could be trusted, as discussed in this thread.
- deleted 12y ago[deleted]
- lifthrasiir 12y agoYeah, -O2 was my wild guess and in the reality the figure may vary a lot. I think that it is quite great anyway.
- sklogic 12y agohttp://www.irisa.fr/celtique/ext/compcertSSA/ http://www.irisa.fr/celtique/ext/compcertSSA/ may bring in a whole bunch of optimisations nearly for free. We'll see...
- eruquen 12y agoThere is on-going research on more modular frameworks that allow for faster implementation of optimizations. One of them is [1]. I worked on that project and implemented (and proved correct) several optimizations within just weeks. This is not industry-ready stuff, though. [1] http://www.mpi-sws.org/~neis/pils/ http://www.mpi-sws.org/~neis/pils/
- duaneb 12y ago> an implementation cost of one PhD thesis per optimization pass. This strikes me as a little much. This kind of proof requires insight, yes, but it's hardly the level of a thesis, it hardly requires innovation to demonstrate. Just exhaustiveness.
- sanxiyn 12y agoSince GCC optimizations can miscompile, target audience ("safety-critical and mission-critical software written in C and meeting high levels of assurance", aka Airbus) is currently using GCC without optimizations. So it is a fair comparison for that case, since they can now enable proven-correct optimizations.
- craftit 12y agoInteresting they are using it without optimisations. The compilers is used far more with optimisations, so those code paths are actually far better tested. I have heard of cases where bugs only appear in unoptimised code.
- andrewchambers 12y agoI don't think this is really true. Generally all optimization passes are run upon the unoptimized version, hence ALL code paths first pass through the -O0 machinery. Besides, they seem to manually inspect the assembly output themselves for the final production build.
- craftit 12y agoBut the code path is first pass + optimisation gives correct code. That doesn't guarantee the first pass generates correct code. I believe there were bugs along those lines at one stage, though I admit they are rare. I've not had to track down a compiler bug in quite a few years.
- justincormack 12y agoIt is not because those code paths are better tested, it is because people's code is not actually quite correct. eg something declared cost is not const unless the compiler evaluates it at compile time.
- edwintorok 12y agoThat may be true as long as you use the same compiler versions as the developer used when writing/testing their code. But then someone decides to deploy that code on an (old and) stable version of Linux with old(er) GCC version and things break. For example ClamAV used to break quite often when built with older compiler versions, in the end we had to add runtime tests to configure based on testcases from the GCC bugzilla to make sure people are not using a "stable" and broken compiler. GCC 4.1.0 and 4.1.1 were particularly bad versions http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27603 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27603 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26763 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26763 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28045 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28045 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37573 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37573 https://bugzilla.clamav.net/show_bug.cgi?id=670 https://bugzilla.clamav.net/show_bug.cgi?id=670 You might think that you could still use -O2 and selectively turn off optimizations that are known to cause trouble (i.e. -fno-strict-aliasing), but there are cases where turning off that optimization exposes bugs in other optimization passes and a compiler that would be otherwise good at -O2 would break at "-O2 -fno-strict-aliasing": https://bugs.gentoo.org/show_bug.cgi?id=275928#c29 https://bugs.gentoo.org/show_bug.cgi?id=275928#c29 https://bugzilla.clamav.net/show_bug.cgi?id=1581 https://bugzilla.clamav.net/show_bug.cgi?id=1581
- pascal_cuoq 12y agoYou are right, but this sentence makes sense in the context for which CompCert is intended. The requirements of the DO-178 standard for aeronautics, for instance, are such that the choice for compiling safety-critical C code that runs within the aircraft is basically between either: - the equivalent of “gcc -O0”, that is, an off-the-shelf compiler with no optimization so that source-level constructs can be mapped to assembly constructs and vice versa, or - CompCert with optimizations, because the soundness of the optimizations can be justified to a level of formality such that it matters less to be able to trace assembly to source. A source without much detail, but the best I can find within 5 minutes of googling: http://projects.laas.fr/IFSE/FMF/J3/slides/P05_Jean_Souyiris.pdf http://projects.laas.fr/IFSE/FMF/J3/slides/P05_Jean_Souyiris...
- ngrilly 12y agoThis is probably a Philistine question, but how do we make sure the proof -- that CompCert works as intended -- itself is correct? In mathematics and science, it happens all the time that someone finds a mistake in a proof years later after its first publication.
- arcatek 12y agoIn science it may happen because everything is based on a lot of assumptions, themselves based on our physical perception of the world, which may be proved wrong later in time. Are mathematics subject to this kind of flaws ? There is a very restricted set of axioms, and almost everything else is based on formal proofs.
- Drakim 12y agoSurely the implementation of the mathematics may be subject to errors, just like any implementation of anything? There is nothing that is so perfect that humans cannot err while applying it.
- scscsc 12y agoIt is true that there might be errors in anything. However, this is mitigated by having only a very small core that checks the proofs. Basically if there if a wrong proof goes through, there must be an error in the core (which was checked by many people and is very small).
- vertex-four 12y agoYou have to translate between the English spec and the computer-readable proof, and surely it's relatively easy to mess that up in some way and end up proving the wrong thing.
- qznc 12y agoThe C spec and x86 assembly are two very well known specs.
- Tomte 12y agoAlthough there seem to have been parts of it that hadn't been formally verified: "Using Csmith, we found previously unknown bugs in unproved parts of CompCert—bugs that cause this compiler to silently produce incorrect code." (http://www.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf http://www.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf) The CompCert homepage tells us that the same authors did a study in the same year (2011) without finding any wrong-code errors. But even if they hadn't; I'd still be excited about CompCert demonstrating that this level of verification is indeed possible. Because then verifying the unverified parts would probably be just as feasible, given enough resources.
- jbapple 12y agoThe Csmith paper notes two types of errors found in CompCert: front-end errors and a misunderstanding of PPC semantics. The former type of bug was apparently due to a part of the compiler that wasn't verified at the time. According to the Csmith paper, " This bug and five others like it were in CompCert’s unverified front-end code. Partly in response to these bug reports, the main CompCert developer expanded the verified portion of CompCert to include C’s integer promotions and other tricky implicit casts." Additionally, the CompCert team produced a validated parser which they discussed in their ESOP 2012 paper, "Validating LR(1) Parsers" The second type of bug (misunderstanding the semantics of the target architecture) is, as far as I know, impossible to avoid. Any verification project can end up with a true proof of the wrong theorem!
- DanWaterworth 12y ago> The second type of bug (misunderstanding the semantics of the target architecture) is, as far as I know, impossible to avoid. Any verification project can end up with a true proof of the wrong theorem! Indeed. However, although it's impossible to avoid, you can still take steps to make it less likely. When you formally verify code, you are showing that a program has a particular specification. If you want to eliminate errors in your specification, you should aim to make it as simple as possible, so that people with domain knowledge (in this case, people with a correct understanding of PPC) would be able to tell whether your specification is correct.
- nathell 12y agoThe fact that Xavier Leroy has been working on CompCert gives it an extra level of credibility for me. (Xavier Leroy of INRIA is the main author of OCaml, among other things.)
- peterfirefly 12y agoAnd the original Linux threading support. His report on the Zinc Experiment is well worth reading: http://gallium.inria.fr/~xleroy/bibrefs/Leroy-ZINC.html http://gallium.inria.fr/~xleroy/bibrefs/Leroy-ZINC.html
- Keyframe 12y agoNote that it can't be used commercially without a proper license. Also, no 64 bit.
- jk4930 12y agoTwo thoughts here: 1. If you use it commercially, you can pay for it. 2. In most cases where it's needed, 64 bit doesn't matter. (Though I might be wrong on the second one.)
- e12e 12y agoIt can't be used for anything other than research for free. So you can't write useful systems and give them away without a license either. (You might of course be able to get a license for free, but it rules out using it as a foundation for a Free embedded kit, like writing something like the Arduino platform. Which is a pity, but quite understandable).
- jbapple 12y agoSee also CakeML, "A verified implementation of a significant subset of Standard ML in the HOL4 theorem prover". https://cakeml.org/ https://cakeml.org/ Not that this project, unlike CompCert, is Free Software in the Stallman sense: https://github.com/CakeML/cakeml/blob/master/COPYING https://github.com/CakeML/cakeml/blob/master/COPYING
- khaki54 12y agoSo is this protected from the "Ken Thompson Hack"? http://c2.com/cgi/wiki?TheKenThompsonHack http://c2.com/cgi/wiki?TheKenThompsonHack I guess it would have to be cross compiled for your system otherwise your existing compiler could corrupt it...
- puetzk 12y agoAs long as it's also capable of reproducible builds (and I would think the proofs would be very hard if the output is not even predictable!), you should be able to cross-build it from a certified platform, and bootstrap it from a trusted one (or more than one), and the bootstraps should converge to an identical binary, thus giving you both claims.
- jerf 12y agoUnless you implement the proved compiler from scratch yourself, no. If you're not doing massive amounts of implementation yourself, you have not escaped from Ken Thompson's hack. All this does is rephrase how they promise to not hack you... it doesn't change the fact that what they say they do and what they actually do have nothing in particular connecting them. I wouldn't worry about it until strong AI comes along though. Humans are barely capable of making compilers that work, let alone shipping compromised compilers. (I know Ken demonstrated his hack, but to make something that does that under controlled conditions is one thing, to make one that could be shipped and robustly implement the hack quite another.)
- vilhelm_s 12y agoIt's not self-hosted, so it is not yet at the point where the Thompson hack would apply. That is, CompCert is a C compiler, but it's not written in C, it's written in Coq. So when you use it, you have to trust that the Coq implementation was written correctly, and that nobody has inserted any backdoors in Coq which insert backdoors in Compcert which insert backdoors in your program. The next level would be to also have a verified Coq compiler, which would make the whole system that much more trustworthy. And at _that_ point you could worry about self-perpetuating backdoors in that compiler, and ways to mitigate them.
- 12y ago
- venomsnake 12y agoAnd who verifies the verify-er? (That is generally the problem I have with the concept of unit tests too)
- vilhelm_s 12y agoIdeally, a simpler and therefore more trustworthy verifier. So far, the most fleshed out implementation of this idea is Milawa, which developed a chain of 11 increasingly sophisticated verifiers, each one checked by the previous. http://www.cs.utexas.edu/users/jared/milawa/Web/ http://www.cs.utexas.edu/users/jared/milawa/Web/
- whitten 12y agoDoes anyone know if CompCert can be used to formally verify a commpiler of some other language than C, such as Assembly Language or Python ?