The Original Sin Of Computer Programs

I recently went back and read Ken Thompson’s lecture from the 1984 Turing Awards. The basic idea is well known, but still very interesting: even if you carefully audit a program’s source code and convince yourself it’s clean, that doesn’t mean the resulting binary can be trusted. If the compiler itself is compromised, it can silently inject malicious behavior during compilation, regardless of what the source says. Thompson even shows and example of how a compiler can be taught to recognize specific programs (like a login utility) and insert a backdoor, and then also recognize its own source code and perpetuate that behavior forever, even after the original malicious code has been removed. See picrel for an example. For the whole lecture: https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_ReflectionsonTrustingTrust.pdf The lecture basically forces you to accept the fact that trust in software is transitive and historical. You’re not just trusting the program you’re reading, but the compiler, the compiler that built that compiler, the system it ran on, and so on, stretching back to something you ultimately accept on pure 'faith'. Reading it today, you start to see parallels with modern supply-chain attacks, compromised build environments, and the growing emphasis on reproducible builds (with Nix and GNU Guix, for example), bootstrapping etc. In a sense, a lot of current security work feels like we’re slowly rediscovering and trying to contain the implications Thompson showed decades ago. What I’m not sure about is if this is even a problem that can be actually solved. Techniques like diverse double compilation and reproducible builds clearly help, but they seem more like ways to narrow the gap than to eliminate it entirely. At some point, there’s always a root of trust that can't be proven. Check out the whole lecture, it's just 3 pages and it has a very simple and clear language, it's worth it imho

CPUs themselves are backdoored, like the intel management engine. Decompilation exists but inspecting the actual silicon isn't feasible for civilians.

It's an interesting lecture, truly. But I have genuine doubts born of ignorance: 1. Is a reading of the year 1984 truly valid? I mean, 42 years have passed and compilers and standards have evolved a lot (or well, as much as humanly possible). 2. The problem is known, but the solution has not arrived. And it really won't arrive if the individuals with the resources to carry out more exhaustive research are stupidly obsessed with trying to “improve” generative models without really achieving anything. 3. Is excessive abstraction becoming a problem? How will a solution be reached if the status quo continues to encourage modern programmers not to study, for example, the basics of how to interpret assembly language instructions? I feel that one of the faults stems from wanting to design another new programming language that does the same thing but differently, instead of optimizing the existing tools. Again, everything I say may be wrong and based on my limited experience in compiler design and implementation. Either way, thank you for sharing this resource.

>>43731 >1. Is a reading of the year 1984 truly valid? I mean, 42 years have passed and compilers and standards have evolved a lot (or well, as much as humanly possible). They have not evolved in a way that would negate the original sin idea. >2. The problem is known, but the solution has not arrived. The solution exists, it's just infeasible. You write a compiler in assembly, inspect the machine code generated by the assembler to make certain the executable is exactly what you wrote, then you use that compiler to compile an existing compiler (whose source code you have thoroughly audited).

That isn't really true. Good compilers can bootstrap themselves, so you can be sure the final binary is completely described by the source code, and nothing hidden can be inserted by the compiler.

>>43733 Which ones would be good C compilers? I've been using TCC and is pretty neat, but I think is a bit outdated (although maybe I am completely wrong about this). I also kind of liked SDCC, but working with it is a pain in the arse.

>>43733 That is untrue and you should read the paper before posting about it as the example is a self-compiling C compiler.

>>43727 The Bootstrappable Builds project has solved this issue on the software side by relying on just a 280 byte binary seed, which is small enough to easily audit manually https://bootstrappable.org/projects/mes.html Hardware is still an issue, especially given how complex modern hardare+firmware is. RISC-V might help mitigate this by allowing fairly simple/minimal implementations, though I feel a form of stack machine or TTA might be better suited.

>>43738 I didn't write self-compiling, I wrote boostrappable. See >>43745 to be honest, I don't know what compilers can do that other than GCC on x86. The only binary is a tiny assembler, which can either be audited in its binary form or assembled by hand. This tiny assembler can be used to recursively build more complex assemblers, then a simple C compiler written in assembly. Again, more C compilers are buillt recursively until GCC itself can be built. Of course this doesn't fix everything. You're doing all that on an OS that might have been built with a backdoored compiler that could detect your attempt at building a compiler and insert a backdoor in it. Escaping that would require building both the compiler and OS in a trusted environment. Even worse, you're using a proprietary CPU that is nearly impossible to audit. My gut feeling is that backdooring a CPU to detect and modify programs at compile time would take up too much silicium to be stealthy, but modern CPUs are openly backdoored (much has been written about Intel ME).

fuarrrk Ken Thompson. Unix (and C) was the original sin.

Read the paper. It seemed incomplete, maybe he covers this in the lecture but it is to my understanding that a compiler can be made in a certifiably clean environment, a hash can be created of that compiler program, and it can be then compared to versions compiled on other machines with the same architecture. You can also theoretically keep a log of known diffs for different compiler parameters and have a mathematically secure install for most purposes, certainly most common ones. Thompson also never elaborates on how such a thing can be done undetectably. While I understand that there is some expectation that we do our thinking for ourselves, the paper takes the overall format of: -Abdescription, and slightly clever, implementation of a quine program. -A *very* brief explanation of how compilers work. -Mildly alarmist threat speculation based on that. -Several paragraphs of moralizing about how children should be locked up for having an interest in hacking, and blaming the media about it. At this, the desire to give Thompson the benefit of the doubt wears thin. I think comparing this to supply chain attacks is an interesting point but my understanding of those is that it is libraries, bootloaders, and hardware that tends to get owned rather than the compiler. There are other specs with much wider attack surfaces than your compiler as well. In general I think this potential class of compiler trojans is far from the most pressing concern, even theoretically speaking, which is not to say research should not be conducted on it.

wtf!!!!!!!! can't u just compile the compiler to make sure it's ok? this guy "Ken Thompson" clearly knows nothing about compilers

>>43800 If this is unironically how you understand the criticism being made then you are ngmi

>>43802 Considering the childish manner of speaking and the fact that he literally said that "Ken Thompson [the creator of C] knows nothing about compilers" I think it's beyond safe to assume that it's a joke lol.

It seems more likely the programming language spec is backdoored and standard library i backdoored. Disassembly of a compiler is possible, but an idea can be a resilient parasite that rejects removal. Things like null terminated strings and C's confusing pointer & type syntax have caused so many problems to naturally emerge, just waiting for well funded orgs to take advantage of them.

>>43799 >it is to my understanding that a compiler can be made in a certifiably clean environment, a hash can be created of that compiler program, and it can be then compared to versions compiled on other machines with the same architecture. You can also theoretically keep a log of known diffs for different compiler parameters and have a mathematically secure install for most purposes, certainly most common ones. The point of the paper is that unless you personally are the person who did this, or you've disassembled and analyzed the resulting binary in its entirety, then you cannot be sure the binary isn't malicious >how such a thing can be done undetectably it's not possible for it to be totally undetectable. anyone can disassemble the binary and find it with enough reverse engineering. The idea is just that you either bootstrap everything from the ground up yourself, writing or auditing all the code along the way (which is not at all feasible in almost every real word scenario), or you accept that you're placing some trust in other people.

>>43808 I think that's a non obvious conclusion to draw and I think the paper can be interpreted differently. It is entirely possible to create a system of mitigation against this kind of trojan and worthwhile to if it has not been done already. The question of trust in others is not discussed in the essay at all when Thompson certainly had the imperative to do so, he instead dedicated that portion to a reactionary and patronizing social attitude towards hackers. I can only assume this is because cyber security concepts and trust architecture was in its infancy in 1984 if it existed at all. Trust can be quantified and verified cryptographically. Trojans can be identified by security researchers, the code Ken Thompson writes about can nowadays be fingerprinted and identified automatically and cryptographically secure webs of trust and software distribution channels can and do exist to mitigate these threats. Vulns will always exist its true, but there isn't a specific technical reason why this is the case, the reason is philosophical. >>43804 I knew it was a joke. some reason I thought you were making fun of people who criticized the essay..