RE: Preventing exploitation with rebasing

["Ilya Dubinsky" <IlyaD () 3vium com>]

IMHO, this is not possible at all.

Take a program that uses machine code for a jump instruction as both
data value and code instruction. Clearly it can't be relocated under any
circumstances without modifying its code.

Also, an algorithm to decide whether the code can be relocated can be
reduced to the halting problem:

Suppose we have such an algorithm. 

The algorithm must distinguish between data embedded in the program and
actual code (if you have a data value which is also machine code to jump
instruction, it shouldn't be touched). So the algorithm will also have
to determine whether a jump instruction is ever reached.
 
It is easy to see that every program can be written in a relocatable
way.
Now take such a program P and an input, make a program Q that calls P
with the input. 

Place jump instruction to somewhere in the end of Q. Use the very same
jump instruction as a data value at the beginning of Q. Call this new
program Q'.

Now run the algorithm on Q'.
If the jump instruction is reached, Q' can't be relocated, but it means
that P stops on the given input.

If it is not reached, and because P is relocatable, Q' is relocatable
too, but it means that P doesn't stop on the given input.

This completes the reduction and the proof that such a utility is
impossible to build in proper way.

-----Original Message-----
From: Bugtraq User [mailto:bq () soft-analysts com] 
Sent: Thursday, February 06, 2003 12:43 AM
To: David Litchfield
Subject: Re: Preventing exploitation with rebasing

> Going back to exe image files and rebasing. Surely they can be rebased
even
> without a .reloc section? All I need to do is edit the image base in
the PE
> header then parse the assembly looking for absolute addresses such as
> function addresses, static variables etc and modify these addresses,
too.
>

I'm sorry but I don't think this is feasible in real life.  In a test 
program it may seem possible, but try and apply it to a real PE
executable 
that actually does something and you will see that it is not.  To even 
begin to do what you suggest, you would need to:

1) Write a functional disassembler that understands instruction 
boundaries and knows which instructions reference absolute addresses 
(easy).

2) Understand parts of the code section that are not assembly 
instructions, such as JMP tables used by switch statements, and similar 
constructs (getting harder).

3) Understand and be able to predict unknown data types, or infer their 
data type by where they may or may not be referenced within code (quite 
difficult).

How do you know if \x44\x42\x41\x00 within a .data section is an
absolute 
address 0x414244 or if it is actually the string DBA\0?

For all that effort, you might as well develop a more worthwhile
security 
measure.