4 ms·
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 on
by pmiller2 13y ago
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.
- WalterBright 13y agoDo 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.
- mhurron 13y agoDo not different compilers make different optimizations? Could not the output be then expected to be different?
- WalterBright 13y agoWhen 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.)
- jackowayed 13y agoNo, 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.)
- WalterBright 13y agoPlease 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.
- DannoHung 13y agoNot intrinsically.
- pmiller2 13y agoIt 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.
- jlgreco 13y agoUse a card deck as your persistent storage. Give the card deck to undergrads to verify by hand. ;)
- IgorPartola 13y agoRight. Use 1000 different hash functions to hash the binaries and compare. Surely it is impractical to compromise all future hashing algorithms by detecting their pattern.
- jlgreco 13y agoOh, I'm just thinking that you only write and read from storage that can be manually verified. You therefore wouldn't verify the output of your compiler with anything that was compiled by that compiler.. instead you would verify it with the owners manual and some underlings to do the grunt work. So you run your compiler, and it punches cards for you. You then turn off the machine, remove the cards, and verify them. If that checks out, then you boot the machine with the cards again. Anything that persists the reboot has to be on those cards, and is therefore subject to uncompromised inspection.
- deleted 13y ago[deleted]
- InclinedPlane 13y ago> 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.
- WalterBright 13y ago> 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.
- InclinedPlane 13y agoThat'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.
- e12e 13y agoNo, the point was comparing the binary output of the same compiler, compiled by itself, compiled by different compilers... (Yeah, I missed that the first time round, too).
- mcpherrinm 13y agoRice's theorem is nice and all, but in the real world we can model executables as things other than turing machines and answer questions about them. If I was trying to detect a "trusting trust" type backdoor, one thing I might do is model the control flow of the executable as a graph, and use something like approximate graph isomorphism to detect additional large blocks of code.
- asabjorn 13y agoA solution to this problem happens to be my thesis topic, and yes it is a very difficult problem. We achieve this by a mechanism to randomly test functions in binaries without knowing the function call signature.