[SGVLUG] Reverse Engineering / Analyzing the SELinux Kernel Source Code?

[Dustin Laurence]

On Wed, May 24, 2006 at 11:24:32AM -0700, Jeremy Leader wrote:

> Dustin Laurence wrote:

> >I also like his point that it's likely that you could just get away with
> >doing a preprocessing transform of an untrusted compiler's source;
> >randomly renaming symbols would foil most obvious backdoors while
> >preserving the semantics.
> 
> I thought Thompson addressed this (based on my vague memory of reading
> the paper when it was first published).  The backdoor just has to do
> a pattern-match on the intermediate representation, much like the
> unification algorithm Prolog uses.

If he was pattern matching on an IR, I didn't catch that, but it makes
sense.  I should re-read.  Then the other suggestion, to do things like
insert extra code that doesn't actually affect the semantics becomes
more useful, however.  Going to an IR is a curse as well as a blessing,
because higher level semantic information is being lost.  I wouldn't be
surprised if the real-world tactic would be to have multiple checks at
multiple levels of abstraction; "offense in depth," as it were.  That
way you have to properly obfusticate at *all* levels rather than just
one.

Most of this stuff is "in principle" we only know for sure that this was
done once, by KT (though I strongly suspect others have played with it
at least to assess it's difficulty and effectiveness, sometimes under
classified circumstances).  So there isn't a lot of practical knowledge
about how to actually do it robustly.

> A really well-written backdoor would be immune even against semi-semantic
> changes like replacing for loops with while loops.  However, I suspect
> that as you increase the sophistication of your protective transformation,
> the level of effort (programmer time and cpu time) for you to perform
> the transformation grows more slowly than the level of effort for the
> backdoor to detect its target in the transformed source.

Yes, I think that would be correct.  Compilers don't really understand
the program they are compiling, and I think a programmer, working at a
higher level, is going to be able to produce equivalent code that the
compiler simply can't recognize as equivalent.

Isn't testing for semantic equality in the general case equivalent to
the halting problem?

Dustin

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://www.sgvlug.net/pipermail/sgvlug/attachments/20060524/a9d2419e/attachment.bin