Ken Thompson's classic "Reflections on Trusting Trust" examined the impacts of planted build chain bugs, from an example of a compiler Trojan to a hypothetical "well-placed microcode bug". Once theoretical & remote, such scenarios have lately been revealed as a stark reality.
But what if we could have every individual piece of software or firmware in the binary toolchain bug-free, performing just as their programmers intended? Would we be safe from run-away computation if only well-formed inputs to each of the individual tools were allowed? Not so. Potential for malicious computation lurks in a variety of input formats along all steps of the binary runtime process construction and execution. Until the "glue" data of an ABI and the binary toolchains in general is reduced to predictable, statically analyzable power, plenty of room for bug-less Trojans remains.
We will discuss our latest work in constructing Turing-complete computation out of different levels of metadata, present tools to normalize and disambiguate these metadata, and conclude with proposals for criteria to trust binary toolchains beyond "Trusting trust" compilers and planted bugs.