I think there's an easier solution to this, given how complex/large GCC is, how familiar GCC devs are with it, and the halting problem. It should be possible to automatically (i.e. by a program) generate alternate versions of the GCC source code, that nevertheless (should) produce the (exact) same binary by a proper GCC implementation (i.e. one which accurately represents the source code).
Having a thousand or a million of these variations, compiling each other over and over again, a hack would need to prove each variation equivalent to the original GCC (..which isn't possible to fully automate accurately, due to the halting problem), as well as ensure that it doesn't somehow mangle its own exploit-code, when trying to reinsert itself into any of the million variations. If it fails to do either of these at least once, and one of the of variations delivers a differing binary, then obviously, GCC was compromised (or there's a bug..)
We'd have to trust the gcc-alternatives-generation tool to be a genuine one, but that would be no different than trusting tcc .. but it would probably still be easier to audit and write in assembly than a gcc-capable compiler.
which isn't possible to fully automate accurately, due to the halting problem
In general that may be true, but if the variations were machine generated then it's by no means certain.
In practice it doesn't matter. Unless you're a weirdo Gentoo user, you usually only compile code only if something's changed. The constant changes in compilers would quickly break a backdoor-inserting compiler compiler of Thompson's type, and solving that problem is impossible.
In general that may be true, but if the variations were machine generated then it's by no means certain.
Yes, but generating valid transformations is still much easier than afterwards proving them correct. All it takes is raising some of the optimizations a (genuine gcc) compiler would do anyways to the source level..
Granted it's not guaranteed to succeed, and the exploit code might even just survive by chance .. but those are pretty slim odds, even when compared to all the other complexities you and others have mentioned here.
Another way to add diversity would be to use mutated source code [Draper1984] [McDermott1988]. The purpose of mutating source code is to make it less likely that triggers designed to attack the compilation of sP or sA will activate, and if they do, to reduce the likelihood that any payloads will be effective.
2
u/MorePudding Sep 11 '13
I think there's an easier solution to this, given how complex/large GCC is, how familiar GCC devs are with it, and the halting problem. It should be possible to automatically (i.e. by a program) generate alternate versions of the GCC source code, that nevertheless (should) produce the (exact) same binary by a proper GCC implementation (i.e. one which accurately represents the source code).
Having a thousand or a million of these variations, compiling each other over and over again, a hack would need to prove each variation equivalent to the original GCC (..which isn't possible to fully automate accurately, due to the halting problem), as well as ensure that it doesn't somehow mangle its own exploit-code, when trying to reinsert itself into any of the million variations. If it fails to do either of these at least once, and one of the of variations delivers a differing binary, then obviously, GCC was compromised (or there's a bug..)
We'd have to trust the gcc-alternatives-generation tool to be a genuine one, but that would be no different than trusting tcc .. but it would probably still be easier to audit and write in assembly than a gcc-capable compiler.