An interesting experiment would be to see if a modern, easy(relatively) to audit compiler like tcc can still be used to bootstrap a more full-featured compiler like gcc or llvm. That would provide at least some protection against this, in that it is unlikely a backdoor in your binary version of gcc will have a trusting trust backdoor for tcc, which can then compile a clean gcc.
I know this was possible in the past, but I'm not sure if tcc can still compile a relatively new gcc.
Better off making it close to but not C language so it's easy to compile. A language easy to compile + easy to write a compiler in. Scheme and ML are probably ideal for the compiler + verification part given I've seen it done already down to machine code in relatively few pages of text. Not C-like, though.
Best method I can think of is assembly writes a macro assembler that writes compiler for simple, high-level language which is used for the first, C compiler. That compiles the complicated, optimizing one. HLA, a P-code variant, and Hansen's Edison are all potential contenders for low-level language. An Oberon-like language with something closer to C syntax & Wirth-style compiler might do for initial, high-level language. tcc or QBE backend have potential for simple, initial, C compiler. I'd do both LLVM and GCC for last step as good projects rely on each.
If one wanted to spend money, then license CompCert, extract it to ML, compile with CakeML, verify each function against assembly, and equivalence check everything with testing. CompCert verifies C to ASM with its outputed ML verified by CakeML assuming their specs are correct. Easiest cheat. Use CompCert to compile first C compiler, the main C compilers, or anything else you can.
This particular attack is done entirely in the rustc frontend, so adding another way to build the backend shouldn't matter? One requires a new implementation of the frontend to apply diversity mitigations.
You need to generate the MIR though (to feed to miri); this only fixes attacks that happen in the pipeline after MIR. Doing path and type resolution is the tough part and so far we only have one implementation of that.
How about writing a minimal pseudo-Rust compiler that treats all invalid Rust code as undefined behavior? This would be a lot easier than reimplementing the real Rust compiler, because a lot of the complexity is in the compile time error checking (eg. the borrow checker) and the detailed error messages. The original Rust compiler could be used to check the code is valid first. Would this be any use for diverse double compiling style countermeasures? You might be able to write a backdoor that both circumvents the error checking in the real Rust compiler and exploits undefined behavior in the pseudo-Rust compiler, but this must be more difficult than a traditional trusting trust attack.
> Thankfully, (from what I have seen), the borrow checker is not needed to compile rust code (just to ensure that it's valid)
It's not finished, though, and honestly I'm pretty sure that borrow checking isn't even that hard compared to all the other stuff a Rust compiler has to do, like generic/trait resolurion. But we'll see.
> It's not finished, though, and honestly I'm pretty sure that borrow checking isn't even that hard compared to all the other stuff a Rust compiler has to do, like generic/trait resolurion.
You can implement basic trait resolution via name mangling and a global map. I did this as an experiment a number of years ago to implement type class-like overloading in C. I'm not sure how far you could take that technique though. I don't think it would work for higher-kinded types, but Rust doesn't have those.
I think that borrow checking is only a minor part of the complexity. You still need to do most of type checking for type and method resolution. So it would be easier, but not much easier.
If you really find that attack interesting, you might also find it interesting to read the paper Thompson ripped it off of. Paul Karger co-invented INFOSEC and more attacks/defenses than about anyone in the field if you're counting foundational stuff. He wrote during his landmark pentest of MULTICS that the PL/I compiler could be subverted with a trap door. Added you could even do a compiler/compiler trap. The trap doors were their favorite technique. Thompson was working on MULTICS and received that evaluation. His initial citation for his idea was "an unknown, Air Force document." They made him change it later by giving him another copy. Everyone still credits Thompson despite Karger inventing it and the original mitigations. Those became part of Orange Book class A1 requirements for security certification with all those products coming with defenses against subversion by malicious developers.
The misattribution and forcing a correction by Thompson is in 3.2.4 of their lessons learned paper:
Also note they were inventing both hacking techniques and INFOSEC while doing this evaluation. It was part of forerunner work happening among small number of people with little to draw on. It's why you see me say "the legendary Paul Karger" when describing the results they got. Due credit might be "Paul Karger's compiler attack popularized & further explored by Ken Thompson's paper, Trusting Trust." I keep mentioning it until more give it.
Back on topic. These days we have verified and certifying compilers, too. Even typed assembly language with correctness proofs. Lots of stuff to base it off of that's close to what most developers can understand. Basic refinement from Rust compiler code with no optimizations to macro assembly or local scripting languages is what I've been recommending outside verified compilers since any developer can do it without special tooling. I even proposed bash one time although as a compile target more than what I'd try code it in lol. I see using local scripting is in your suggestions, too. That different people are thinking on same lines here more often might mean it's worth exploring further.
As I said there, Wheeler was exemplary for handling most of this right ahead of time. He gave credit to Karger for inventing the compiler subversion attack. He wrote the reference page on high-assurance FLOSS (for compiler verification) and high-assurance SCM (for repo security, esp distribution). He also wrote a cheat I gripe about in reproducible builds to give us something to work with if high-assurance methods get ignored. Any of his stuff on this subject is worth reading.
It shouldn't be hard, and I've played with the Go AST before. I ... could :)
This was sort of a bucket list thing though, doing it a second time is less fun :p And I don't have that much time.
Why don't you try? The technique explained in the blog post is pretty universal. Go has an AST too, and while the Folder abstraction doesn't exist in its codebase (as far as I know), you can still tweak the AST. In the case of Go it would be easier to do the injection during parsing. https://github.com/golang/go/blob/5c9035acc1e1540a564ea66000... would be a good entry point. https://golang.org/pkg/go/ast/ should help.
(I am not a Go compiler dev so there may be better entry points)
> Simply recompile the purported source code twice: once with a second (trusted) compiler, and again using the result of the first compilation. If the result is bit-for-bit identical with the untrusted binary, then the source code accurately represents the binary
This sounds very familar to me. If I remember correctly, this is exactly what happens when you build GCC. GCC's 3-stage bootstrap process is well-known for a long time, as well as the decussion about whether this makes sense or is just paranoid.
It's nice to have this written down and analyzed throughly in a scientific paper, though.
I'll dig into the article, but out front there is something I don't understand. What is this second, trusted compiler? How did we get that? Why not just use that and its results, rather than vetting foreign compilers...? EDIT: Reading, but I think I'm having more questions, not less. The compiler source could introduces optimizations into the compiler binary's output that could be used to recompile the source again and get a _better_ binary right? The article speaks of compiling the source once with the the foreign compiler and then again with its results; but, on the trusted side it seems to be saying you just do one compilation and you don't compile the source again with the result of that compilation. Seems like you'd have to use the same measures on both sides before comparing binaries?
We can't. It's why we need verifiable builds. C0, CompCert, KCC, and Simpl all have strong evidence of their ability to produce correct code from good C or specs of it. Checking that on local tooling plus an assembly build of it would be a start. It can build other things.
Or you can use the incremental approach I describe elsewhere in this thread.
For the minority of you that haven't read the original Reflections on Trusting Trust, you should do so now. It goes more in depth on this attack category, and its implications. Personally, I would say it's one of the few papers that should be required reading for programmers (along with In The Beginning Was The Command Line, and The Lambda Papers).
Technically it would have been in the original C complier written for the original unix by Ken Thompson and Dennis Ritchie, and been compiled in every complier and login utility since the 70s. At this point try finding a complier that doesn't trace is compiling lineage at some point reach back to a complier compiled by a complier that doens't eventually reach back to it may be pretty hard.
True, but that compiler wasn't open source. The real head-scratcher here seems to be that you can have a self-replicating security vulnerability in a completely open source stack including the compiler
> "The local variable is called krate because crate is a keyword"
This is an interesting solution to a problem I often face (whenever I write a tool to in environment X to process something for environment X) . Is this a common way to handle this problem? I don't think I've seen this before.
Say a trusting trust attack is discovered. Whats the resolution? Do you manually edit the binary? Do you rewrite a compiler in a language with a verified compiler?
Would something like randomizing memory layouts, or reversing stack direction be an easy mitigation or solve an attack like this?
Randomizing memory layouts and modifying the stack will have no impact since this attack isn't exploiting anything in the language, you've created a compiler that intentionally miscompiles source code. And not only does it miscompile source code, it miscompiles itself so that it preserves the exploit.
One potential way to try to remove attacks like this is to run the source code of the compiler through something that randomizes the structure and text without changing how it actually functions. That way, you may be able to defeat the code that is trying to match on code that looks like the part of the compiler it's trying to hijack.
you use an old compiler binary that didn't have the attack yet to compile the latest source code that it is able to compile, then use that compile the latest it can compile, and so forth.
what I mean is that I wouldn't expect a the 2012 rust prerelease to be able to compile the 2016 rust source code, but it can probably do 2013, use that to compile 2014, use that to compile 2015 use that to compile 2016.
As long as you have a single binary from any point before the attack was introduced it shouldn't be an issue. The whole point is that at no point does the source code contain the trust backdoor, so you can just work forward from any binary that doesn't have it yet.
if the very first version of rust binary already had it as an issue, as well as was written in rust, you could conceivably have a problem though. then you would need an alternative compiler, however sub-optimal it might be...
or you could simply patch and remove the backdoor from the binary and then have it compile itself without inserting the backdoor.
> but it can probably do 2013, use that to compile 2014, use that to compile 2015 use that to compile 2016.
Clearly you aren't aware of Rust's history :)
proto-Rust has been under so many rapid changes that each compiler usually only compiles with a specific hash. Now stuff works with a numbered Rust release, but that's a relatively new phenomenon. This process will likely need to go through hundreds of compilation steps. Doable, but not as simple as a year-by-year process.
I believe the year numbers were used by logicallee only as an example. Of course, if somebody is trying this, they need to figure out a different (smaller) time scale that actually works.
In the worst case, you have to follow each commit in the version control system of the compiler, but I'm pretty sure you don't need to do it that fine grained.
yes. I'm pretty shocked Manishearth didn't get that I was just giving examples of the process with placeholder dates, since I started my comment explicitly stating (I add emphasis here):
>you use an old compiler binary that didn't have the attack yet to compile the latest source code that it is able to compile, then use that to compile the latest it can compile, and so forth.
in trying to find the "latest source code that it is able to compile" you can do a binary search backward from the current version of the source code. it doesn't take long to find the latest version for each one (i.e. the latest each one compiles without error, into a working binary that passes some test suite). And anyway whenever you're binary-searching forward (i.e. after any point where the binary search yields ""greater-than" because the one you just tried compiled) then you can just use the version you just successfully compiled. Let me illustrate what i mean with this binary search:
so if we're at version 1 million today, which the version 7 doesn't compile, then you try version 7 on version 500,000 (it'll fail), then on version 250,000 (it'll fail), version 125,000 (it'll fail), version 125,000 (it'll fail), version 62,500 (it'll fail), version 31,250 (it'll fail), version 62500 (fail), version 31250 (fail), versions, 15625, 7812, 3906, 1953 and 976.
Now suppose that version 7 compiles version 976 successfully. So the failure with version 7 is between 976 and 1953. But since version 976 is stronger, you can start working forward with version 976. So it's like a binary search that's restarted whenever you get a "greater-than".
Even if for some reason this were a manual process, each time you get a working version you at least halve the remaining space.
Finally, as you said above, someone could make a batch file / shell script that literally goes through every commit in the version control system (not skipping any) and always use the previously working version on the next working version. A script doing so may well run in matter of days, though, depending on how long it takes to compile a the compiler compiler. Ordinarily there are a lot of commits!
The binary search above cuts this down significantly. (However the binary search isn't theoretically guaranteed to be faster; after all theoretically we can imagine that version 7 compiles version 8 but fails on version 9; version 8 compiles version 9 but fails on version 10; etc. So theoretically every single commit could be breaking. (Theoretically.)
But that's extremely unlikely to be the case. I don't imagine you'd have to do more than a few hundred compilations with the above binary-search methodology before you got one that started with version 7 but stepping through the commits in the way specified, produced a binary that compiles the latest version.
The process may have to be partly manual due to breaking changes in semantics of invoking the compiler or its dependencies, but that should be rare.
This process would also in the end allow you to do a bit-for-bit comparison of the output of the current version of the compiler when compiled using the above trusteable version, versus compiled from source code with the "trusting-trust" backdoor (where every version is backdoored and inserts a backdoor when compiling itself, without this backdoor being in the source code anywhere.
so the above process would let you tell whether there's a trusting-trust backdoor, as long as there is a single early version that for sure didn't have it yet, and you have the commit history (from which the trusting-trust has been edited out).
as I said above, if you don't have a single known-good version without the trusting-trust backdoor, then you'll have to write something that can compile version 2 or 3 (or 7) yourself, in another language.
I just wanted to note that the scale was way off. You said "I wouldn't expect a the 2012 rust prerelease to .." followed by "but it can probably do 2013", so it was clear you had an expectation of what the dates would be approximately like.
And for many compilers, this is true -- you can use really old compilers to compile the new one. But not everyone is aware of how tumultuous Rust's history is, so I thought it interesting to note.
yeah I was just trying to illustrate what I meant, like, the process. And you're right, I didn't know it was so tumultuous so with your clarification it's an interesting observation :)
(By comparison the specifications for C don't break earlier compilers often at all.)
I suppose the true counter is to write a verified scheme (or forth) interpreter in assembly language, and then write a simple rust compiler in that scheme, which you use to compile the real compiler, and then you can use that to make an optimized build of the compiler.
>So you have a string containing the contents of the module, except for itself
I assume interesting versions of TT would have to avoid this trick, since someone running "strings" on the binary would notice something very suspicious, unless something strange is done to string literals.
Unless your assembler, loader, OS, or microprocessor is also backdoored :)
The original article was really about this -- at the end of the day, you have to trust _someone_. Of course, we more easily trust microprocessors and assemblers over binary blobs, so
> I assume interesting versions of TT would have to avoid this trick
Pretty easy to encode the string literal into some binary format.
Alternatively, serialize and later deserialize the AST with a stable binary serialization mechanism.
A really good version of TT operating on the AST would have to backdoor not only the part where it creates the AST, but also the parts where intermediate state is displayed by the compiler (e.g. where it can dump AST/MIR output).
There are things you can do. As a proof of concept, I didn't bother to do them. My current POC is toothless and I like it that way!
It's cleaner to instead operate at the end of the pipeline; on llvm ir or the generated binary (but it's also harder to write). And if you can insert a trusting trust attack in llvm itself, well, that would be something :)
> Unless your assembler, loader, OS, or microprocessor is also backdoored :)
True... but it has to be backdoored for that particular system. There are many ways you can make it very unlikely that the other compiler/system is backdoored for the same target.
The simplest being my proposal that was a variation on my scheme for bouncing packets/messages across many non-cooperating, national jurisdictions a decade ago. That is: diversity with mutually-suspicious or competing parties. The hardware and software comes from different people, fabs, and nationalities. Preferably that compete. You run the same verifiable core on all of them with lots of tests for equivalence. Build non-optimizing compiler in that from readable source. Build optimizing one with that.
With about 5... esp U.S., French, Russian, Chinese, and Japanese... you should be fine. Add South Korea these days with Samsung hardware. The software doesn't have to come from same countries as hardware. Better if it doesn't. All safety checks on in it with POLA enforced at the least. Shady exploits based on language primitives (esp C's) is why the compilers need to be in safe languages.
"Unless your assembler, loader, OS, or microprocessor is also backdoored :)"
On the lowest level, you can hand-check it with pencil and paper. Per Brinch Hansen used to write the earliest compilers in ALGOL that he type-checked and tested by hand. He'd then write optimized assembly that visibly matched each function or procedure. He claimed the ALGOL still aided correctness plus served as better documentation of algorithms than commented ASM.
Far as Rust, one could do it by hand if they skipped safety checks and optimizations. Otherwise, do it in older or randomly acquired stuff highly unlikely to be subverted. Many such devices.
One of the interesting points raised in the original Trusting Trust paper was exactly this - that next level of trust can again be subverted via microcode modification, and so on and so forth. I really don't view Trusting Trust (in the original paper) as an attack so much as a philosophical question being asked about trust in general and the way it propagates through supply chains. It's almost a paper more on economics than anything else..
> I really don't view Trusting Trust (in the original paper) as an attack so much as a philosophical question being asked about trust in general
Yep. This was the original intention of the talk/paper; it was about _trust_, not attacking compilers. Attacking compilers is just a super cool example that was used.
Once intelligence agencies start backdooring microcode (especially in a way that chip manufacturers can't detect), I'm throwing out my computer and living in the woods.
Agreed. If it matters this much to you, better move now.
I'm not even sure that the open source RISC-V initiative might prevent this, as theoretically the NSA could gain access to the manufacturing plant and insert their own core.
The only way to catch that at that point would be to X-ray the chip and look for their mod, or something. Anyway, assume the NSA has access to your shit, focus on preventing the random from grabbing your bank account access and stealing your money.
It doesn't need to be in assembly, you could write a compiler/interpreter in any non-Rust language and use that to verify the compiler binary from source (unless you think that someone has already inserted a backdoor into your X-lang compiler with the specific intent of inserting backdoors into the Rust compiler, which is a bit of a stretch (especially if you use a compiler that completely predates Rust, e.g. a version of GCC from 2005)). And even writing your compiler in assembler doesn't provide assurance that your CPU itself hasn't been compromised. :P
IIRC, last time he was asked about this, he said something like "I consider it a great compliment that someone thinks I'm smart enough to have done this, I assure you I am not."
Eventually it will be revealed that he even bothered to politely document the backdoor in the Rust reference manual, confident that nobody would ever, ever believe anything found in the reference manual.
rustc was originally written in OCaml by Graydon Hoare.
Hypothetically, Graydon could have inserted a trusting trust attack in the ocaml compiler that would also insert a version of itself inside rustc. Highly unlikely; very hard to do, but ... possible.
The more impressive part is: that manages to self-preserve across hundreds of Rust language/compiler versions with wildly varying designs and semantics all the way up to today's version.
(This file is no longer in master because the compiler bootstraps from the previous stable release; too lazy to accurately isolate the last time it was updated)
I know this was possible in the past, but I'm not sure if tcc can still compile a relatively new gcc.