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

31–40 of 55 posts

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

#31

Post by [deleted] »

jackowayed wrote: post #17
WalterBright wrote: post #14

Earlier quoted context omitted.

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…

[deleted]

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

#32

Post by zerohp »

grecy wrote: post #18
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...

Linus doesn't distribute kernel binaries.

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

#33

Post by [deleted] »

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.

[deleted]

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

#34

Post by adrusi »

barbs wrote: post #27

Interesting! Out of curiosity, if this were the Gnu C Compiler, would this be illegal, since the GPL requires the source to be distributed with the binary, and the source and binary don't match?

The is no definition of "match" beyond just what the compiler produces. No spec dictates what the output of a compiler should be.

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

#35

Post by acchow »

kwantam wrote: post #6

The original article, which this (kind of) summarizes: "Reflections on Trusting Trust" by Ken Thompson. http://cm.bell-labs.com/who/ken/trust.html Sort of disappointing that the blog entry doesn't bother linking to the original, which is at least as well written.

Was first introduced to this article in CS 458/658 at Waterloo.

My favourite part was "This is a deep concept. It is as close to a 'learning' program as I have seen" since getting a compiler to recognize when, where, and how to inject (self-propagating) backdoor code seemed practically impossible.

It also expressed the idea of "self-referencing" more succinctly than the backdoor trick.

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

#36

Post by InclinedPlane »

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.

> The same source code should generate the same binary.

This is utterly false and reveals a deep misunderstanding of compiler technology. Aside from optimizations and exactly how they are implemented in each compiler there are still many more or less arbitrary choices that a compiler needs to make in order to translate source code into machine code. Address layout being one of the most prevalent. Indeed, these choices are so arbitrary and lead to such a high degree of difference in the binary forms that the same compiler running on the same code will often generate different binary output. And the same compilers running on very slightly different code bases will quickly generate substantially divergent output. This is why programs like bsdiff and courgette exist, because comparing binaries is actually an enormously non-trivial problem.

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

#37

Post by csense »

Let's pretend a compiler with this backdoor will always correctly detect when it's compiling a compiler. I.e. looksLikeCompilerCode() and generateCompilerWithBackDoorDetection() are oracles.

With this assumption, to write a compiler that's safe, you can't run it through an existing possibly-compromised compiler. You would have to bootstrap your safe compiler, as if for a totally new language.

So you'd have to initially write it in a different language. You probably can't write it in most existing languages, e.g. Python and Java are both implemented in C. Because, if you tried to write a safe compiler in Python, a sufficiently smart [1] C compiler would have been able to tell that you were compiling a Python interpreter when it compiled /usr/bin/python, and inserted a backdoor into that Python interpreter which will trigger when the interpreter is interpreting a C compiler written in Python.

You'd basically have to consider any code that has ever passed through an automated tool to be potentially backdoored, so you'd have to start writing in machine code (no assembler allowed, of course, because it's probably written in C). Of course, you could program an assembler in pure machine code (or using a potentially-tainted assembler, verifying its output by hand).

[1] It'd either be a general artificial intelligence of human level programming ability, or some kind of magical oracle.

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

#38

Post by WalterBright »

InclinedPlane wrote: post #36
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.

> The same source code should generate the same binary. This is utterly false and reveals a deep misunderstanding of compiler technology. Aside from optimizations and exactly how they are implemented in each compiler there are still many more or less arbitrary choices that a compiler needs to make in order to translate source code into machine code. Address layout being one of the most prevalent. Indeed, these choice…

> This is utterly false and reveals a deep misunderstanding of compiler technology.

I've written many professional compilers, front to back, and I use the binary difference technique to verify that the compiler is capable of exactly reproducing itself.

If you've got a compiler that generates different binaries depending on the time of day, the address the compiler was loaded at, or something else that is not the compiler switches + source code provided to it, you've got a compiler with serious QA issues.

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

#39

Post by Dylan16807 »

alanctgardner2 wrote: post #28
sjay wrote: post #26

Earlier quoted context omitted.

From the original, Ken on the press lionizing hackers: "I have watched kids testifying before Congress. It is clear that they are completely unaware of the seriousness of their acts. There is obviously a cultural gap. The act of breaking into a computer system has to have the same social stigma as breaking into a neighbor's house. It should not matter that the neighbor's door is unlocked. The press must learn that mi…

I'm pretty sure the context of that quote is completely applicable to weev. "It should not matter that the neighbor's door is unlocked", is clearly Ken saying that something being technically simple does not make it morally or legally justifiable.

But at the same time, simply entering is not going to get the feds after you. And while standing on someone's lawn and staring into their living room certainly has a stigma, it will never get you put in prison for decades. (For the weev analogy pretend they have some financial documents on the table in the living room.)

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

#40

Post by InclinedPlane »

WalterBright wrote: post #38
InclinedPlane wrote: post #36

Earlier quoted context omitted.

> The same source code should generate the same binary. This is utterly false and reveals a deep misunderstanding of compiler technology. Aside from optimizations and exactly how they are implemented in each compiler there are still many more or less arbitrary choices that a compiler needs to make in order to translate source code into machine code. Address layout being one of the most prevalent. Indeed, these choice…

> This is utterly false and reveals a deep misunderstanding of compiler technology. I've written many professional compilers, front to back, and I use the binary difference technique to verify that the compiler is capable of exactly reproducing itself. If you've got a compiler that generates different binaries depending on the time of day, the address the compiler was loaded at, or something else that is not the comp…

That's nice that your compiler works that way but that's not the way most do.

More importantly the salient point was about comparing the binary output of different compilers.

While it's certainly possible to create tools which make it make it possible to determine if the binary output of different compilers are effectively the same such tools are very non-trivial to create. The idea that different compilers are likely to produce exactly identical output is sheer fantasy.

Post reply on HN