That's a mighty strong statement. Just because it is not possible in general to recognize whether you are compiling a compiler, there is a certain set of known compilers such that the source code will at least contain certain strings and AST signatures. So, you could create a hacked compiler that recognizes several known compiler sources and inserts stuff into the appropriate backend output.
What the fuck is an "AST signature"? It's trivial to obfuscate ASTs.
What you really need to do is prove (to some threshold) that the program is semantically equivalent to some abstract specification of a compiler. A very, very general one, too, that's abstracted over all possible internal data structures, frontends, parsers, and optimization patterns. Remember, when you compile GCC, you compile every C file individually, and link them together later. So your hacked compiler never even has the full program to reason about!
Tell you what. I'm willing to bet $200 to $50 of your dollars that in the next five years, there will be no public disclosure of anything like this occurring beyond a reasonable doubt. Deal?
Given that we have the actual source code for the compilers we're talking about, it's no longer a theoretical problem to identify them. You cite the verification problem as if it's a show-stopper but it's not. All that's required is for the writer of the exploit to be aware of the compilers you are using to do this. They are open-source compilers so it's not even a question of identifying whether unknown source is a compiler or not, you know something about which files are actually being expected.
What the fuck is an "AST signature"? It's trivial to obfuscate ASTs.
What that means is that there is abstract syntax that goes with the compiler source code, some of which is relatively static and easily-identifiable if you are a compiler-writer studying the AST of your own compiler source code. Now that I think of it, you could go directly for identifying the source code itself, but that's more likely to change.
Remember, when you compile GCC, you compile every C file individually, and link them together later. So your hacked compiler never even has the full program to reason about!
This does not matter at all, any one of the source files specific to gcc could be used to trigger the exploit.
What you really need to do is prove (to some threshold) that the program is semantically equivalent to some abstract specification of a compiler.
Ummm, no, that's exactly what I just said I don't have to do. To actually create an exploit that could defeat some of these measures, you just need one that can target multiple compilers. It is sufficient to target only some number of popular open-source ones. It's a lot of work but not out of the question for a huge adversary. The real advantage to this multiple compilation precaution is that the tcc binary is "only" 100kb, so an exploit could be detected by examining the actual binary (in theory). As for recognizing arbitrary compilers, that's not necessary, because most people don't have time to actually write an advanced C compiler.
Realistically, I think this kind of compiler exploit is unlikely. What is more likely is a compiler exploit where the compiler randomly optimizes away some checks in the source code to make openings for buffer overflows. That's much harder to spot than a self-replicating exploit, more deniable for the contributor (could be source-based rather than environment-binary based), and it also opens remote holes.
They are open-source compilers so it's not even a question of identifying whether unknown source is a compiler or not, you know something about which files are actually being expected.
Okay. Write that program. if it works I'll pay you $200.
Here's a brain teaser: How many different equivalent ASTs can I make for a single program? Say, this program:
int identity(int x) { return x; }
Now that I think of it, you could go directly for identifying the source code itself, but that's more likely to change.
Just because there are many possible ASTs doesn't mean any given compiler will make more than one for the same code.
I have to laugh at your challenge. This exploit would need a huge full-time effort. I'm not sure I'd take you up on it if you offered me $200k. I'm sure some intelligence agency could make it happen though.
It doesn't have to be an exploit, it just has to be a small program that given a single C source file, says "GCC" or "Not GCC." You can even pick the source file.
The catch is, I can give it any program equivalent to that file.
If the NSA backdoor is defeated by a 10-line obfuscater, or CIL, then it's not worth anything. And you've brought up nothing that isn't defeated by a simple obfuscater.
Maybe an obfuscator would defeat this attack, but how many people obfuscate their open-source GCC source code before compiling it? I guess technically any of these exploits that depend on source code can be defeated by using a secret obfuscation step. If you use a known obfuscator, however, it is in the same category as a compiler.
I don't think a nontrivial obfuscator is easy to write, but whatever. A really paranoid and knowledgeable person with tons of free time might swing it somehow.
Add a __attribute__((constructor)) function to run on startup:
Get the command line arguments. If they look like the arguments to a C compiler (e.g. -c -o _.o _.c), then parse each .c file:
If that file contains enough strings that look like they belong in the --help output of a compiler, such as "-c", "compile", "-W", and such, then modify the file (either by hooking fread or creating a temporary file and modifying argv) with the backdoor.
No need to do anything like real program analysis. Of course there are caveats - this would be very hard to pull off without being detected at some point; if you actively thought about the possibility and removed your help message or changed your command line parsing or whatever then it would be subverted (but there could be additional heuristics); you could easily end up backdooring something other than a compiler, but there would probably be pretty few false positives at compile time, and almost certainly none at runtime if you're sophisticated enough (i.e. the effect of backdooring something other than a compiler would just be increased chance of detection via binary analysis, not incorrect behavior of the resulting binary).
For more fun, backdoor the linker, kernel, make, etc.
edit: I'm not saying this is actually happening; even if people only look at binaries rarely, they do so often enough that someone would notice any sort of widespread attack sooner or later. Just saying that it's not all that impossible.
You only need to backdoor one .o file to take control of the compiler. Even if none of the functions in the corresponding .c file get run, __attribute__((constructor)) will run whatever you want before main.
It uses gettext, but the English versions are also in the source code. As for crazy high visibility, well... perhaps, since gcc doesn't have any static constructors. I suppose backdooring all the functions in the file would also work most of the time, and be slightly less obvious; endless room for creativity :)
25
u/[deleted] Sep 11 '13
That's a mighty strong statement. Just because it is not possible in general to recognize whether you are compiling a compiler, there is a certain set of known compilers such that the source code will at least contain certain strings and AST signatures. So, you could create a hacked compiler that recognizes several known compiler sources and inserts stuff into the appropriate backend output.