Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Strange Loops: Ken Thompson and the Self-referencing C Compiler

scienceblogs.com

Post reply on HN
Print view View original

11–20 of 55 posts

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#11

Post by mhurron »

WalterBright wrote: post #8
pmiller2 wrote: post #7

Earlier quoted context omitted.

Of course, the hard part is to detect whether C1 and C2 "match." Just because 2 different compilers generate different code for the same source doesn't mean one or the other compiler was compromised. By Rice's theorem, it's undecidable in a general case to decide whether two computable functions are equal, so you technically can't do this step in a general way.

Do a binary diff of the executables. That's unambiguous. Remember that C1 and C2 are generated by two different compilers generated from the same source code. The same source code should generate the same binary.

Do not different compilers make different optimizations? Could not the output be then expected to be different?

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#12

Post by jackowayed »

WalterBright wrote: post #8
pmiller2 wrote: post #7

Earlier quoted context omitted.

Of course, the hard part is to detect whether C1 and C2 "match." Just because 2 different compilers generate different code for the same source doesn't mean one or the other compiler was compromised. By Rice's theorem, it's undecidable in a general case to decide whether two computable functions are equal, so you technically can't do this step in a general way.

Do a binary diff of the executables. That's unambiguous. Remember that C1 and C2 are generated by two different compilers generated from the same source code. The same source code should generate the same binary.

No, the same source code will generate different binaries. The spec doesn't say exactly how source code has to map to machine code, just what should happen based on source code. Differences in the optimizers are almost certain to yield differences in the optimized binaries, and even with optimizations off, binaries are likely to be different due to different compilers making decisions that are more-or-less arbitrary differently.

(Plus a backdoor could easily be set to run only when optimizations are on. Almost all production builds that one would want to exploit should be built optimized, and it would make the exploit a bit harder to spot in compiled binaries.)

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#13

Post by WalterBright »

mhurron wrote: post #11
WalterBright wrote: post #8

Earlier quoted context omitted.

Do a binary diff of the executables. That's unambiguous. Remember that C1 and C2 are generated by two different compilers generated from the same source code. The same source code should generate the same binary.

Do not different compilers make different optimizations? Could not the output be then expected to be different?

When A compiles C, and B compiles C, then when we run C to recompile C, it will be doing the SAME optimizations, and should produce exactly the same binaries.

I.e. take the iteration one more time.

(I actually do this as part of the test suite for the Digital Mars C++ compiler - it takes two iterations until the binaries match exactly.)

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#14

Post by WalterBright »

jackowayed wrote: post #12
WalterBright wrote: post #8

Earlier quoted context omitted.

Do a binary diff of the executables. That's unambiguous. Remember that C1 and C2 are generated by two different compilers generated from the same source code. The same source code should generate the same binary.

No, the same source code will generate different binaries. The spec doesn't say exactly how source code has to map to machine code, just what should happen based on source code. Differences in the optimizers are almost certain to yield differences in the optimized binaries, and even with optimizations off, binaries are likely to be different due to different compilers making decisions that are more-or-less arbitrary…

Please read the process again. Let me rephrase it:

A compiles C and produces C1. C1 compiles C and produces D1.

B compiles C and produces C2. C2 compiles C and produces D2.

D1 and D2 should be identical.

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#15

Post by DannoHung »

WalterBright wrote: post #14
jackowayed wrote: post #12

Earlier quoted context omitted.

No, the same source code will generate different binaries. The spec doesn't say exactly how source code has to map to machine code, just what should happen based on source code. Differences in the optimizers are almost certain to yield differences in the optimized binaries, and even with optimizations off, binaries are likely to be different due to different compilers making decisions that are more-or-less arbitrary…

Please read the process again. Let me rephrase it: A compiles C and produces C1. C1 compiles C and produces D1. B compiles C and produces C2. C2 compiles C and produces D2. D1 and D2 should be identical.

Not intrinsically.

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#16

Post by pmiller2 »

WalterBright wrote: post #14
jackowayed wrote: post #12

Earlier quoted context omitted.

No, the same source code will generate different binaries. The spec doesn't say exactly how source code has to map to machine code, just what should happen based on source code. Differences in the optimizers are almost certain to yield differences in the optimized binaries, and even with optimizations off, binaries are likely to be different due to different compilers making decisions that are more-or-less arbitrary…

Please read the process again. Let me rephrase it: A compiles C and produces C1. C1 compiles C and produces D1. B compiles C and produces C2. C2 compiles C and produces D2. D1 and D2 should be identical.

It doesn't matter. "Trusting Trust" is just intended to show that by compromising the C compiler, you can compromise any other binary on the system. So, how are you going to tell D1 and D2 are identical if the diff tools are compromised? Compare them off the machine? Well, what if the file transfer tools/drivers are compromised? Boot to a custom kernel and compare using a different OS? Well, better hope your boot firmware isn't compromised, etc.

I grant that this is not a very practical attack, but it can be made arbitrarily hard to detect, based on the threat model the original attacker (who compromised the C compiler) uses.

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#17

Post by jackowayed »

WalterBright wrote: post #14
jackowayed wrote: post #12

Earlier quoted context omitted.

No, the same source code will generate different binaries. The spec doesn't say exactly how source code has to map to machine code, just what should happen based on source code. Differences in the optimizers are almost certain to yield differences in the optimized binaries, and even with optimizations off, binaries are likely to be different due to different compilers making decisions that are more-or-less arbitrary…

Please read the process again. Let me rephrase it: A compiles C and produces C1. C1 compiles C and produces D1. B compiles C and produces C2. C2 compiles C and produces D2. D1 and D2 should be identical.

Oh, I see, generate two different binaries of the same compiler with different compilers, and you know something is up if the same source compiled by those two separate binaries of the same compiler differ. Assuming the compiler is deterministic, that should work pretty well.

I wonder how well that would work in practice. There are actually quite a few bugs in C compilers[1], and compilers are complicated enough that I could see them hitting some of them when they are compiled. Has anyone done this before?

1: http://www.stanford.edu/class/cs343/resources/finding-bugs-c...

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#18

Post by grecy »

gleenn wrote: post #3

This is awesome because it means backdoors could have been inserted many many versions ago in a compiler and as long as there was a chain of using the compiler to compile itself through each version (as most compilers like GCC are), the hack would be passed ad infinitum. Pretty evil.

Tinfoil hat time.

Let your imagination run if someone had done this at some point to a build of GCC being used by Linus...

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#19

Post by jhuckestein »

WalterBright wrote: post #2

This relies on new compiler binaries being built from the previous compiler binaries. The cycle can be broken by using a different compiler with a different pedigree in the bootstrap process. In fact, this suggests a way to detect the back door: Given Compiler A which is the previous generation, and Compiler B which has a different pedigree, we want to generate Compiler C and detect if it is compromised: A compiles C…

True. But this isn't useful unless you know which code C to do the test on (in the OP's original example C would be the code of the login program).

The only way to tell if a compiler will put a backdoor into certain programs is to read the disassembled source.

Re: Strange Loops: Ken Thompson and the Self-referencing C Compiler

#20

Post by SEMW »

jhuckestein wrote: post #19
WalterBright wrote: post #2

This relies on new compiler binaries being built from the previous compiler binaries. The cycle can be broken by using a different compiler with a different pedigree in the bootstrap process. In fact, this suggests a way to detect the back door: Given Compiler A which is the previous generation, and Compiler B which has a different pedigree, we want to generate Compiler C and detect if it is compromised: A compiles C…

True. But this isn't useful unless you know which code C to do the test on (in the OP's original example C would be the code of the login program). The only way to tell if a compiler will put a backdoor into certain programs is to read the disassembled source.

No. In WalterBright's example, code C is the compiler (the one which you suspect may be backdoored), not the login program. A and B are also compilers, one of which is known-good.

So: the difference you'll find isn't the login-backdoor itself, it's the code that waits for a login program (or another compiler) to be compiled, and inserts that backdoor. This avoids the problem of having to know what the login program or whatever is.

Post reply on HN