David A. Wheeler's Blog

Mon, 02 Nov 2009

New PhD Dissertation: Fully Countering Trusting Trust through Diverse Double-Compiling

An Air Force evaluation of Multics, and Ken Thompson’s Turing award lecture (“Reflections on Trusting Trust”), showed that compilers can be subverted to insert malicious Trojan horses into critical software, including themselves. If this “trusting trust” attack goes undetected, even complete analysis of a system’s source code will not find the malicious code that is running. Previously-known countermeasures have been grossly inadequate. If this attack cannot be countered, attackers can quietly subvert entire classes of computer systems, gaining complete control over financial, infrastructure, military, and/or business system infrastructures worldwide.

Thankfully, there is a countermeasure to the “trusting trust” attack. In 2005 I wrote a paper on Diverse Double-Compiling (DDC), published by ACSAC, where I explained DDC and why it is an effective countermeasure. But some people still raised concerns. Would DDC really counter the attack? Would DDC scale up to real-world compilers? Also, the ACSAC paper required “self-parenting” compilers — can DDC handle compilers that are not self-parenting?

I’m now releasing Fully Countering Trusting Trust through Diverse Double-Compiling, my 2009 PhD dissertation that expands on how to counter the “trusting trust” attack by using the “Diverse Double-Compiling” (DDC) technique. This dissertation was accepted by my PhD committee on October 26, 2009.

On November 23, 2009, 1-3pm, I will be giving a public defense of this dissertation. If you’re interested, please come! It will be at George Mason University, Fairfax, Virginia, Innovation Hall, room 105. [campus location] [Google map]

This dissertation’s thesis is that the trusting trust attack can be detected and effectively countered using the “Diverse Double-Compiling” (DDC) technique, as demonstrated by (1) a formal proof that DDC can determine if source code and generated executable code correspond, (2) a demonstration of DDC with four compilers (a small C compiler, a small Lisp compiler, a small maliciously corrupted Lisp compiler, and a large industrial-strength C compiler, GCC), and (3) a description of approaches for applying DDC in various real-world scenarios. In the DDC technique, source code is compiled twice: once with a second (trusted) compiler (using the source code of the compiler’s parent), and then the compiler source code is compiled using the result of the first compilation. If the result is bit-for-bit identical with the untrusted executable, then the source code accurately represents the executable.

Many people commented on my previous 2005 ACSAC paper on the topic. Bruce Schneier wrote an article on ‘Countering “Trusting Trust”’, which I think is one of the best independent articles describing my work on DDC.

This 2009 dissertation significantly extends my previous 2005 ACSAC paper. For example, I now have a formal proof that DDC is effective (the ACSAC paper only had an informal justification). I also have additional demonstrations, including one with GCC (to show that it scales up) and one with a maliciously corrupted compiler (to show that it really does detect them in the real world). The dissertation is also more general; the ACSAC paper only considered the special case of a “self-parenting” compiler, while the dissertation eliminates that assumption.

So if you’re interested in countering the “trusting trust” attack, please take a look at my work on countering trusting trust through diverse double-compiling (DDC).

path: /security | Current Weblog | permanent link to this entry