[E-Lang] Announcing stl-E 0.8.9k: An interim non-distributed release

Bill Frantz frantz@communities.com
Wed, 03 Jan 2001 12:12:56 -0800

At 10:15 AM 1/3/01 -0500, Jonathan S. Shapiro wrote:
>> KeyKOS used what is to me a rather powerful argument that it was immune to
>> the Ken Thompson attack.  We used an assembler which was released before
>> the design of KeyKOS.  I believe that it is currently unfeasible to install
>> a Ken Thompson attack against a system without knowing at least something
>> of it's design....
>There is a more persuasive argument. First, observe that assemblers are
>very simple programs.

Note that there was a C version of KeyKOS.  We used the same argument there.

>Until very recently, their output is entirely
>deterministic modulo a very small number of transformations on the
>	1. selection of branch span sizes
>	2. Introduction of delay slots (MIPS)
>Further, it is possible to write a *disassembler* that generates
>something very close to the original input. It is then possible to
>automate the comparison of the decompiled assembler with the original
>assembly input.
>That is, the assembler result can be checked.

Compiler output can be checked as well.  For a high assurance project, with
a small security kernel, it might be worth while to hand examine the
compiler output to see if it is a "reasonable" implementation of the source

I fully agree that assembler is easier to examine by hand, and the
examination can possibly be automated.  (The KeyKOS assembler -- IBM
Assembler H -- was a very powerful macro assembler, and the KeyKOS source
made use of some of the advanced macro features.  Decompiling it would
certainly require the symbol table.

>> (With powerful enough AI in the compiler, perhaps you
>> could do it.  But that is currently unfeasible.)
>I don't know, Bill. You strike me as a pretty powerful AI... :-)

Wait a minute!  I'm all natural.  (Except for my fillings.  And the DDT in
my fat.  And...) :-)

I think the point here is that a Ken Thompson compiler written before the
system it was attacking would have to recognize common patterns (e.g. trap
handlers), and install a universal back door.

>Quite frankly, I'm not worried about security holes in the compiler
>nearly as much as I worry about *bugs* in the compiler.

After my recent experience with the JVM, I can't argue a bit.

I think that coding style can help a lot in avoiding the bugs.  You need to
know what the compiler test suites check, and try to limit yourself to the
checked subset of the language.  I suspect the less optimization you use,
the safer you are.  Only optimizing your performance kernel, and hand
checking it might be attractive, and a lot less work than hand checking the
whole thing.