Transcript slides - The Fengs

Evolutionary Security
CS 610: Advanced Security
Gabriel Daleson
Economic Perspective
• Time space, and secrets are scarce
• Complexity of assembly code is (roughly)
of quadratic order, so…
• Attackers have an economy of scale
defenders do not
“The Ultimate Attack”
• Important first step: kidnap sysadmin (and
anyone else who might try to stop you,
particularly those with root access) and
keep locked up in cellar.
• At this point, target computer is just a finite
state machine.
• Finite state machines can be analyzed and
modified at will. (Physical access)
“The Ultimate Defense”
•
•
•
•
“You only have to outrun the halfling” idea
Make the attack too hard.
Note economic perspective!
Security through obscurity
Automating it
• The bad guys write viruses – automatic
attackers…
• so defenders write automatic obfuscators.
• This is evolutionary defense.
Geometric Concerns
• The set of all I/O-preserving
transformations on a single program is a
group.
• composing two I/O-preserving
transformations gives you an I/Opreserving transformation (do one, then
the other)
• doing nothing preserves I/O
Geometric Concerns (cont.)
• Removing an I/O-preserving
transformation preserves I/O
• Composition of I/O-preserving
transformations is associative
• So, generators?
Generating Transformations –
1. Instruction Reordering
• Given a sequence of instructions, shuffle
them.
• Works well on linear programs.
• Requires analysis of everything that jumps
to reordered program (COME FROM)
• For real-world programs, *lots* of analysis
required to maintain functionality.
Generating Transformations –
2. Variable Substitution
• Instead of using a nice clean symbol table,
move variables around in memory.
• Attackers (and you) can’t call it index any
more, it’s now 0xDEADBEEF.
• Now instead of jump analysis, it’s memory
analysis – can only be performed at
runtime, unless you’re a big fan of heap
corruption.
Generating Transformations –
3. Jump Insertion/Deletion
• Easy – throw in lots of spurious GOTO/jmp
instructions.
• Finally, an attack we can do without
analysis!
• …but your computer will end up slower
than an abacus. (Jumps take a long time!)
• We already do delete jumps – it’s called
optimization
Generating Transformations –
4. Call Insertion/Deletion
• Just like jump insertion/deletion, but with
function calls
• Sure, it does help obfuscate
• …and, in addition to making your
computer slow, it now also chews through
stack space.
Generating Transformations –
5. Garbage Insertion
• Throw in trash instructions.
• You can do it, and it only slows your
computer down a little.
• Very possible! Many instruction sets have
equivalent instructions or equivalent
codings for instructions that can be
substituted with no effect on I/O.
Generating Transformations –
6. Simulation
• Write an interpreter for a different coding
scheme, and translate your instructions
back and forth.
• Labor intensive – someone has to put the
interpreter together.
• Slow, too. (Java?)
Generating Transformations –
7. Build & Execute
• Instead of making your code interpret,
make it write some code itself and compile
that.
• We do this already, in some sense – JIT
compiling?
• Not that slow
• So where are you going to get the
compiler?
Generating Transformations –
8. Redundant Instructions
• Test things multiple times.
• Good idea! You’ve heard it before.
• Read/write/use checking – never do
anything with data unless you’ve looked at
it!
• Some slowdown, but makes up for it in
fixing bugs.
Other Generating Transformations
• Anti-debugger mutations - these will
depend on which debugger you’re anti.
• Program interleaving; just like reordering,
but doing it with multiple programs.
Algebraic Considerations
• This is not a minimal set of generators;
you put calls together from jumps.
• Even if it is minimal, is it free?
• What sort of structure does this group
have if it’s not free?
“Evolutionary”
•
•
•
•
Sort of a misnomer, in a biological sense.
Randomness?
Selection?
Reproduction?
But does it work?
• At least in the small case given, yes.
• Hard to get a real world test – gobs of
compile and run-time program analysis
required
Human Aspects
• “Ultimate Attack” requires sysadmins to do
nothing.
• This is evolutionary, if the defender is
doing the evolution…
• …then again, all security is evolutionary in
that paradigm.
Problems
• Is this an economy of scale for the
defender?
• this trades speed (almost all of it) for
security
• The Gödel, Escher, Bach aspect – attack
the evolver
• Humans don’t write code this way