Lambda the Ultimate

Ken Thompson's point was that the binary version of compiler A could generate malicious code, even (or only!) when compiling *itself*. So if you compile A's source (sA) with A's binary

bA( sA ) -> bA2

it inserts its malicious code, and bA2 == bA bit for bit, and includes the malicious code even though it does not show up in A's source at all.

The DDC trick is to use a different compiler for the same language, and "double" compile A's source: First, compile A's source with the other compiler:

bOther( sA ) -> bAo

Next, compile A's source with this newly created compiler:

bAo( sA ) -> bAq

bAo is produced by a compiler built from sA. Therefore when sA is compiled by bAo, the output bAq should be the same as bA2. (Modulo, e.g., time stamps in .exe files.)

If it isn't, Wheeler argues, about the only explanation is that our other compiler (bOther) implements an identical malicious hack.

ummm, if they're different compilers, in general how can it be expected of them to produce "bit for bit" identical binaries.

I haven't read the article yet, but in my first pass at skimming that abstract, I misunderstood it in a way that made it come out right: you use both a trusted and an untrusted compiler to boostrap two binaries for the untrusted compiler, and then use those to compile the system; they should produce bit-identical code.

My second pass at the abstract, however, shows that it doesn't actually say so, but again, I haven't read it yet.

Also, it'd seem that having access to a trusted compiler renders the whole exercise needlessly circuitous.

The trusted compiler can be much simpler than the untrusted one, and produce very unoptimal code. Essentially, if you're given an optimizing compiler for language X by an untrusted source, that includes a binary-only bootstrap compiler and source for the full compiler, and you need to verify if you can trust the bootstrap compiler you're given and the executables it produces, one way to do it is to write your own bootstrap compiler for X.

I think the point is that bOther could be a compleatly diffrent compiler, built from a diffrent source.

Then, while bAo's binary representation may differ from bA's, its functional behaviour should be the same because it's also built from sA---therefore the output which it produces (bAq) should equal bA's output (bA2).

I was confused by scruzia's statement "bAo is produced by..." which should probably have read "bAo is a compiler built from sA".

Yah, I guess I wasn't explicit about my naming convention. The "A" was meant to describe compilers built from A's sources, and "Other" meant an Other compiler, built from Other sources.

Anyway, why not just use bOther? Maybe bOther is subject to an unacceptable license. Maybe it is glacially slow, has bad error messages, or doesn't play well with their IDE. Maybe they need to add extensions, fix bugs, etc., and don't have access to bOther's source (though that tends to lower one's trust level). Maybe they want to insert their *own* malicious code. :-)

Why not use the trusted compiler? Well, for lots of reasons; scruzia has noted some of them. The compiler may be glacially slow or produce glacially slow results. It may not have the functions you need (the trusted compiler only needs to be able to compile the other compiler... it may lack LOTS of functionality). It may not work on the same CPU architecture. It may have a license you don't like.

And be careful. As noted in the paper, the trusted compiler may ALSO be malicious. It just has to be malicious in a different way. See the paper for more discussion about this.

The rise of multi-processor and multi-core architectures isn't really relevant in this case. What's required is that the output of a compiler be deterministic -- that is, given the same input, it produces the same output.

Let's say you're given a compiler that accepted "print(1+1)", and it non-deterministically produced "2" or "4". Would you accept that? I doubt it. If it's semantically null, it generally wouldn't impact this process either.

What does affect the process is when a compiler of a given version takes the same inputs, and generates different code at different times. Date/timestamps are an obvious example, but they're also easily handled. Optimizations that "flip a coin" are actually easily handled, too, as long as the compiler provides control over the random number seed. gcc, for example, provides such control over its random number seed, so this isn't just theoretical. Control over random number seeds already exists for other reasons, because nondeterministic compilers are a major headache in testing.

The real challenge is uncontrolled nondeterminism, e.g., some Java compilers' output depends on the address allocated by free(), and is essentially uncontrollable. But it turns out that this is bad for other reasons: Such compilers are essentially untestable. This wouldn't be a problem if compiler bugs never occurred, but they occur all too frequently. A compiler that doesn't produce the same output twice is incredibly hard to debug; the cost of making a compiler deterministic is almost instantly paid off by the first time a bug is worked off. So it's not really a problem in practice.

Using an interpreter as the trusted compiler in a DDC process is just a special case of DDC. An interpreter can be a helpful way to implement the trusted compiler, but you still have to consider the issues described in the paper. Interpreters can be subverted, too, after all. For example, let's imagine a C interpreter written in C. Somebody compiled the interpreter, and if the compiler has a trigger/payload for the interpreter, you're still dead meat. Also, the infrastructure can detect things you might think initially are "too hard to detect". That doesn't mean interpreters are useless; it just means that you have to pay attention to the preconditions. The paper outlines those.

Now, if you just mean "compile the first compiler with an interpreter and that's it", then you've just moved the attack location. As an attacker, I'll just wait until you use the interpreter. Then I'll subvert THAT. Whereas DDC tells you what the "correct answer" should be, which you can compute over and over again with different environments. Since an attacker would have to subvert all those different environments to avoid detection, they're in much worse shape.

If your argument is "use interpreters everywhere" that doesn't really help; that just moves the attack somewhere else. I presume that's not what you meant.

I would expect any peer reviewer would respond that this shouldn't be published because there are so many systems that this is useless on.

I don't think this objection invalidates the paper. The author also encountered the time-stamp problem in his experiment with the tcc compiler (section 8) and could work around by considering object files instead of archives. Alternatively, with a bit more work, you could make the diff or hashes of the executables without considering the time stamp.

On the other hand I feel that all components of a tool chain should at least optionally be deterministic. It gives me a warm fuzzy feeling when a bootstrap converges after two builds.

I had to deal with timestamps in my test case. They're annoying, but you can work around them to get useful results.

As I noted above, non-determinism in compilers makes debugging incredibly hairy. Since debugging is costly to start with, most people consider uncontrolled nondeterminism in a compiler to be a bug, and eliminating that nondeterminism will save so much money/time on debugging that it's not a hard argument to make. Few compilers are THAT nondeterministic, and here is yet another reason to make them deterministic. Note that gcc includes, as a test case, a nondeterminism test, so this isn't at all unreasonable.

You may be conflating a DIFFERENT problem with Solaris from years ago. The Solaris C compiler of years ago was so bad that it couldn't compile the gcc compiler at all. In fact, the Solaris C compiler couldn't compile MOST code unless it was written for the Solaris C compiler (it didn't support ANSI C, and had so many bugs that you needed to carefully write around them if I remember correctly). As a result, to get gcc on Solaris you had to start with a gcc binary for Solaris... you couldn't port gcc to Solaris using the Solaris C compiler. But this was a limitation of Sun's compiler, not a general problem endemic everywhere. Besides, the key is that you only need to go through this process to test a particular compiler... the people who do the test can account for it, so the rest of us don't have to.