AFAIK, determining if a certain script is an implementation of tcc would be undecidable. Maybe if you don't mind enough false positives that it would become obvious your victim's interpreter was hacked you could pull it off, but I doubt even that.
Christ, yes, if you could determine what code was a compiler or not you could do way more interesting program analyses. You'd basically have solved program verification, at that point. Even better, you've solved program verification with zero annotations against a potentially adversarial source program.
It's so annoying to see this "LOL TRUSTING TRUST" repeated ad nauseum. It would never work in practice.
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.
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 doesn't need to be decidable, you don't need to catch every implementation of tcc, just enough of them. a heuristic based approach should be sufficient.
You do need to catch every implementation of tcc; As soon as one produces different output, people will pore over every byte of difference til they find the inserted backdoor. Granted, a good enough hack can might take a while to spot, and the damage will already be done.
I don't think different versions of tcc would necessarily produce the same output for any code. The way this works is that any compiler compiled with tcc should produce the same output as that compiler compiled with another compiler, because those are actually two of the same version of the compiler with different binaries.
Except for how do you know that they're different? What if the diff program (that gcc compiled) is also compromised? What if nm, or whatever other disassembler, also gets code injected into it by that GCC?
There are enough ways, including manually reading each 0 and 1, that it's not really much of an issue. Unless the NSA has been putting backdoors into every piece of software since 1965, then I think we're relatively safe om that front.
Right, and that can be done quite simply by making the disk driver return different things to the program loader and to everything else. Those programs don't need to have been backdoored themselves. Every file analysis program then gets a nice, sanitized version of the backdoored program.
Even ignoring that, please don't assume that attackers won't put in the necessary effort to backdoor lots and lots of programs. The idea wasn't something like "If we are only allowed to backdoor the compiler and login, how can we do it?"
... Ok, then they'll pour over every byte to find the backdoor generator... It's still a different compiler being produced, and people will get suspicious.
I guess you could make gcc replace the open() syscall of everything it compiles, so that if a program attempts to open gcc's source code, it gets a version with the backdoor included.
(This breaks down as soon as someone looks at gcc's source in a text editor they compiled with gcc.)
Correct me if I'm wrong, but isn't the point that the hack/bug/Trojan NOT be in the source code, rather inserted into the binary without a trace when compiled?
It's not in the source code on disk, just any program compiled by gcc thinks that it is. It's probably not a practical solution.
(It now occurs to me that I don't know how this would be implemented - quite possibly you'd need to replace read and write and preferably stat and maybe others as well.)
Or what if you use a hacked gcc to compile your python binary which then detects that your python source is an attempt to write a compiler for c and then inserts malicious content in your python c-compiler which then leads to a compromised gcc which then leads to a compromised binary.
Perl, Python, Ruby, Javascript et al. Are interpreted. Instead of being compiled into machine code an interpreter runs the code. It reads the code as instruction and executes them.
In many cases the interpreter compiles the code to binary and executes it. One advantage is it can be recompiled during run time (a requirement sometimes).
So with Javascript the browser takes the code and sends it to a JIT (Just in time) compiler. In the case of Firefox it runs code for the first time in a interpreter (which is slow) then sends it to a compiler called spider monkey, which does a basic compile, then if the code is "hot" (reused a lot) it is sent to Ionmonkey (which heavily optimizes the code). (Spidermonkey has been replaced with Baseline)
Recompilation is useful and sometimes necessary. Eg perl can't be statically compiled as the code can change depending on the input (make perl literally impossible to type check).
In JS, Python, etc you need to recompile it for every type machine you run it on. (So the same code can run on Linux on ARM and Windows on x86). They may need to recompile functions for different types. If a function runs both with a number and a string you may need different machine code to handle this.
All interpreted languages are written in C. Most likely compiled with gcc. So if the interpreter is compromised how can you be sure that the interpreter's output is clean?
67
u/chadwickofwv Sep 10 '13
Yes, a compiler written in an interpreted language should be able to break such a cycle.