3 Effectiveness
--- Growth of Stack --->
<--- Increasing Address ---
Figure 4: Format of an attack which uses a large buffer overflow to increase the odds of success.
Address obfuscation is not a bulletproof defense against all memory error
exploits, but is instead a probabilistic technique which increases
the amount of work required before an attack (or sequence of attacks)
succeeds. Hence, it is critical to have an estimate of the increase in
attacker work load.
In this section, we first analyze the effectiveness of address
obfuscation against previously reported attacks and attack variations
(``classic'' attacks). Then we discuss attacks that can be specifically
crafted to exploit weaknesses of address obfuscation.
3.1 Classic Attacks
Address obfuscation provides good protection against the majority of the
``classic'' attacks. Most of these attacks involve overwriting of a
single pointer or datum without any ability to read the memory contents
before attacking. Against address obfuscation, an attacker is forced to
make guesses about the address of one or more program values in order to
succeed.
3.1.1 Stack Smashing Attacks
A classic stack-smashing attack is absolute address-dependent, since the
absolute address of the injected code must be placed in the return address
stored in the stack frame. Let N be the size of the virtual address
space available for the initial random stack offset, and assume that the
stack offset is chosen randomly from { 0 ... N-1 } (with a uniform
distribution). Furthermore, we don't wish to allow an offset of zero, and
Linux requires that the stack pointer be a 32-bit word-aligned address,
which reduces the set of possible offsets to { 4, 8, ... N }.
(In this analysis, we assume that the one-time
offset N is much larger than the effect of stack-frame padding, and
hence ignore the latter. The purpose of stack-frame padding is to introduce
significant additional randomization into the addresses so that
attacks become difficult even if an attacker has somehow learned
the value of N.)
Assuming the attacker knows the value of N, the attacker can guess an
address randomly and have a
4/N chance of success. Moreover,
if the guess happens to be wrong, then the program will likely crash, and
will have to be restarted. At this time, a new random value for stack
offset will be generated, which means that each failure does not provide
any information to the attacker. Thus, the probability of a successful
attack after k attempts is given by 1-(1-4/N)k. From this, it
can be shown that the probability of success approaches 0.5 after about
N/8 attempts.
The attacker can improve the odds of success by increasing the size of the
attack data. This can be done by writing to the buffer a block containing
copies of a guessed address G (enough copies to be relatively sure that
the return address is overwritten --- in our implementation, of the order
of 256 copies), followed by a block of K NOPs, and
then the attack code. As long as G falls somewhere in the block of NOPs
(or directly equals the first instruction of the inject code), the attack
will succeed. This is illustrated in Figure 4, which
shows the overlap between the stack values (along the top), and the attack
data (along the bottom). When the current function returns, execution will
jump to the guessed address G, which the attacker hopes will be within
the range of the NOPs or the first instruction of the injected code.
The insertion of K NOPs increases the odds of success by a factor of K
to 4 · K/N, reducing the average number of attempts for a
reasonable chance of success to roughly N/8 · K.
Fortunately, K is limited in size because the attacker must avoid
writing to the read-only stack padding. If the overflow runs
into the read-only region, a segmentation fault will occur, preventing the
attack from succeeding. This restricts the value of K to be much smaller
than N.
C programs tend not to use too much stack space;
in the example programs of Figure 5,
the amount of average stack storage allocated ranged
from 1 to 4 kilobytes.
For such programs, the maximum ratio of N to K will be 2.5 · 104, and the odds of a
single attack succeeding will be 4/2.5 · 104, resulting in
about 3000 attempts, or 12 megabytes of data transmitted,
for a reasonable (approx 0.5) probability of
success. While this may seem like a small number, note that:
-
every failure will cause a branch to a random
address, which is highly likely to cause the target program to crash, so an
attacker is not simply free to keep trying different addresses until an
attack attempt succeeds. Instead, the repeated crashing of the program
is likely to raise suspicion of the intruder's
presence.
- the total amount of data that needs to be sent by the attacker
is obtained by multiplying the size of attack data by the number of
attack attempts. This number will be of the order of N/8, and is largely
independent of the size of data used in each attack attempt.
3.1.2 Existing code attacks
Existing code attacks, also called return-into-libc attacks,
typically involve overwriting the return address on the
stack with the address of existing code, typically a function
in the standard C-library, such as execve. The arguments to
this function will be taken from the stack, which has been overwritten
by the same buffer overflow to contain the data chosen by attacker.
In order for such an attack to succeed, the attacker needs to
guess the location of the vulnerable function. With a randomization of the
order of 100MB, and given the constraint that the base addresses of
libraries and the executable must start at a multiple of page size
(4KB), the probability of success is of the order of 4 · 10-5.
Attacks that corrupt other stack-resident function pointers are all similar to
an existing code attack, and the probability of a successful attack remains
the same as with existing code attacks.
3.1.3 Format-String Attacks
A format-string vulnerability [33]
occurs whenever a program contains a call to
the printf family of functions with a first parameter (format
string) that is provided by an attacker. Since the format string provides
a great deal of control over the behavior of printf function, the
ability of an attacker to provide a format string can be likened to the
ability to execute attacker-chosen code. For this reason, most
techniques developed to deal with buffer overflows are not effective
against format string attacks.
The common form of this attack uses the somewhat obscure %n format
parameter, which takes a pointer to an integer as an argument, and writes
the number of bytes printed so far to the location given by the argument.
The number of bytes printed can be easily controlled by printing an
integer with a large amount of padding, e.g., %432d. The printf function assumes that the address to write into is provided as an
argument, i.e., it is to be taken from the stack. If the attacker-provided
format string is stored on the stack, and if printf can be tricked into
extracting arguments from this portion of the stack, then it is possible
for an attacker to overwrite an arbitrary, attacker-specified location in
memory with attacker-specified data. Such an attack can be used to change
return values without trampling over canary values used by StackGuard and
other approaches.
The format-string attack described above is an absolute-address dependent
attack. It requires the attacker to know the absolute location where the
return address is stored on the stack, and the absolute location where the
attack code is present. This means that the probability of a successful
attack using this approach cannot be any larger than that for
stack-smashing attacks.
Certain kinds of format-string vulnerabilities can be exploited
to read stack contents. In particular, if the vulnerable printf
(or variant) call is one that sends its output to the attacker, then
the attacker can potentially learn the randomizations used in the program,
and use this knowledge to craft a successful attack. (See
Section 3.2.1 for details.)
3.1.4 Data Modification Attacks
Attacks which target non-pointer data values are one of the most difficult
to defend against. For instance, a string which contains a shell command
may be stored adjacently to the end of a buffer with an overflow vulnerability.
In this case, an attacker can overflow the buffer with ASCII text
containing a different command to be executed. The success of the attack
depends only upon the relative distance between the buffer and the command
string. Furthermore, even if the relative distance is randomized, the
attacker can use blank characters as padding to increase the odds of
success. If the attacker pads the injected string with more blanks than
the maximum increase in distance between the buffer and the shell string,
then the odds of success are high, especially when the data is located in
the static area. If it is located on the stack, then the introduction of
blanks (or other padding characters) may corrupt critical data on the
stack, which may cause the program to crash. For this reason, such padding
may not be very successful for stack-resident data.
Our current implementation provides limited protection against this
attack, in the case where the data resides on the stack or heap. In the
case of heap, if the overflow attack overwrites critical data within the
same malloc-ed block as the target of the copy operation, then
randomization does not help. Otherwise malloc randomization is effective,
with the effectiveness increasing proportionately with the number
of malloc blocks that are overwritten by the attack.
Similarly, if the buffer and vulnerable data appear on the same stack
frame, our current implementation does not provide any help. However, if
they reside in different stack frames, then some level of protection is
available, depending on the distance between the buffer and the vulnerable
data.
The scope of protection can be expanded using the technique presented
in [16], where all of the sensitive data (such as function and data
pointers) can be located at addresses below the starting address of any
buffer. Since the overflows can only move upward in memory, they can never
reach from the buffer to a sensitive data location without crossing over
into previous stack frames, in which case the return address will be
corrupted.
Our current implementation provides no protection against relative
address-dependent overflows that corrupt data in the static area. A fuller
implementation of address obfuscation, which includes reordering of
static variables as well as padding between them, will indeed provide a good
degree of protection against data modification attacks in the
static area.
3.1.5 Heap Overflow and Double-Free Attacks
Due to the lack of adequate checking done by malloc on the validity
of blocks being freed, code which frees the same block twice corrupts the
list of free blocks maintained by malloc. This corruption can be
exploited to overwrite an arbitrary word of memory with an arbitrary
value [2]. A heap overflow attack achieves the same effect
through a buffer overflow that also corrupts the data structures
maintained by malloc [23].
Both of these are absolute address-dependent
attacks, and the protection provided by address obfuscation is quite
good, as the address of a single word is
randomized over 108/4 possible values.
3.1.6 Integer Overflow Attacks
Integer overflow attacks exploit an integer overflow to bypass runtime
checks in a program. Since an integer has a fixed size, an overflow during
a computation causes it to change its value in an undefined manner
(typically, the value ``wraps around'' from a large positive value to a
small negative one, or vice-versa). Due to the wrap-around, boolean
conditions which test the values of integers resulting from arithmetic
overflow are often incorrectly evaluated. For example, if i is
sufficiently large, the expression i+5 can overflow, resulting in a
negative value, and causing the condition i+5 > limit to evaluate to
false, when it should be true.
This effectively disables the bounds
checking, allowing an overflow attack to be
performed in spite of the bounds checking.
The level of protection
provided by address obfuscation from these kinds of attack is the same as
for normal buffer overflow attacks. In particular, if the target corrupted
by an attack is a pointer, then the probability of a successful attack is
low. This was the case with the recent Snort integer overflow
vulnerability. If the attack targets security critical data, then the
protection is similar to that for relative address attacks. In particular,
a good degree of protection is available for heap-resident data, while the
level of protection for stack resident data is some what lesser. As an
example, the sshd integer overflow attack involved overwriting a critical
piece of string data with a null character, which was interpreted by the
sshd server to mean that no password was required for a user to log in.
Address obfuscation provides a good degree of protection against such an
attack, while some of the related approaches such as
PointGuard can be defeated by this attack.
3.2 Specifically Crafted Attacks
We have identified three specific attacks
which can be used to attempt to defeat address
obfuscation when the victim
program contains the ``right'' vulnerability.
These occur when (1) a program has a bug which allows an
attacker to read the memory contents,
or (2) an overflow exists that can be used
to modify two pointer values (a buffer pointer and a function pointer),
or (3) an overflow can be used to overwrite just the
lower part of a pointer. In the case of (1), the attacker can craft
an attack that succeeds deterministically. In the case of (2) and (3),
the probability of success is significantly higher than the classic
attacks, but far from deterministic.
We note all of the attacks discussed in this section require
vulnerabilities that are very uncommon. Moreover, although our current
implementation is vulnerable to these attacks, a full implementation of
address obfuscation, employing all of the transformations described in
Section 2.1, and using dynamically changing random values, will
be much less vulnerable.
3.2.1 Read/Write Attacks
If a program contains a bug which allows an attacker to print the values
stored in arbitrary memory locations, then most of the existing security
schemes can be compromised if there is a vulnerability somewhere in
the program. In the case of address obfuscation, the attacker can compare
pointer values stored in the program against a local, non-obfuscated copy,
and possibly decipher the obfuscation mapping. A specific instance of this
occurs when an attacker can control the format-string passed to a printf, provided the vulnerable print statement sends its output to the
attacker [29]. Given such a vulnerability, an attacker can send a
format string that would cause the stack contents to be printed. From the
output, the attacker can guess with a high probability (or with certainty,
if no stack frame padding is used) the locations holding saved frame
pointer and return address. By comparing these values with those that can
be observed on their local version of the vulnerable program that has not
been obfuscated, the attacker can identify the obfuscation mapping. Armed
with this mapping, the attacker can develop an attack that will succeed
with a high probability. This time, the attacker will use the standard
format-string attack that uses the n% directive.
We point out that changing just the base addresses of different memory
regions, as done with PaX ASLR, does not help with this attack. Most other
techniques, such as PointGuard and StackGuard are also vulnerable to this
attack. In the case of PointGuard, the obfuscated stack can be compared to
a non obfuscated process, and the xor mask value can be inferred. In the
case of StackGuard, the stack can be examined to determine the canary
value, and then stack smashing can be used.
Address obfuscation, as implemented now, seems to provide some additional
protection over ASLR: it is no longer possible to deterministically
identify the location of frame pointer or return address. But this added
difficulty does not translate into additional protection: the
format-string based read attack does not cause the program to crash, so
the attacker can perform multiple attacks to read the stack multiple times
until he/she can determine the frame pointer with certainty. However, if
the stack-frame padding is varied continuously at runtime, then address
obfuscation will provide significant degree of protection. In this case,
the location of the buffer, the saved frame pointer, as well as the return
address, will change between the time the attacker read the contents of
the stack and the time he/she tries to modify the return address. This
will significantly decrease the chances of a successful attack.
Probability of a successful existing-code attack can also be decreased
significantly by using the more general form of address obfuscation
of code, which involves reordering routines, etc.
3.2.2 Double Pointer Attacks
A program which contains a both a (preferably stack-allocated) pointer to
a buffer and a buffer overflow vulnerability can be exploited to work
around obfuscation. For example, consider the following code fragment,
which is similar to one suggested for defeating StackGuard [7]:
void
f(char *user_input1, char *user_input2) {
char *buf1 = malloc(100);
char buf2[100];
strcpy(buf2, user_input1);
strncpy(buf1, user_input2, 100);
...
The steps required to exploit this code are as follows. First, the
attacker can guess an address G likely to be valid (somewhere in the
heap is a good choice). Second, the first strcpy to buf2 can
be overflowed to overwrite the the top stack locations with G, setting
both buf1 and the saved return address to equal G. Once this is
done, the strcpy to buf1 will copy user_input2 to G.
user_input2 should contain the injected code. When the function
returns, it will jump to address G, which is the start of the code
injected via user_input2.
The probability of success with this attack is proportional to the
probability of guessing a valid address G in memory. This probability is
small for programs that use small amounts of memory as compared to the
amount of randomization. For instance, if the program uses a megabyte of
memory, then the probability success (with a 100MB padding) is one in a
hundred. The same line of reasoning holds with PointGuard: the attacker
can overwrite buf1 and the return address with G, but these values
will be interpreted as G xor M where M is the xor mask used by
PointGuard to encrypt pointers. This means that the probability of success
is proportional to that of guessing a G such that G xor M
corresponds to a writable portion of the memory. This probability is given
by (size of data memory used by program)/(size of address space), a
quantity that is smaller than the corresponding number for address
obfuscation.
3.2.3 Partial Overwrite Attacks
A partial overwrite attack is an attack which overwrites only part
of a targeted value. For example, under the x86 architecture, an overflow
could overwrite just the least significant byte of the return address.
(This is hard to achieve if the buffer overflow was the result of an
unchecked strcpy or similar function, since the terminating null
character would clobber the rest of the return address. Thus, we need a
buffer overflow that does not involve strings.) Since the only
transformation made to code addresses is that of changing the base
address, and since the quantity of change is constrained to be a multiple
of the page size (4096 bytes on Linux), the location pointed by the return
address is predictable when we we change its last 8 bits.
If exploitable code (i.e., code that can be used as a target in the case
of existing code attacks) can be found within 256 bytes of the return
address of a function with buffer-overflow vulnerability, then this attack
will work against address obfuscation. However, it is very unlikely that
such exploitable code can be found, so the attack suggested in
[3] is more elaborate. Specifically, the attack involves the
use of a call to the printf function in the caller code that
precedes the call to the function with buffer overflow vulnerability. The
attack then modifies the return address so that a return goes to the
instruction that calls printf. The argument of the vulnerable
function, which was attacker-provided, now becomes the argument to printf. At this point, the attacker can print the contents of the stack
and then proceed as with the case where a format string bug allowed the
attacker to read the stack contents.
Note that the stack-frame padding significantly increases the difficulty
of carrying out this attack. In particular, there is a significant
level of uncertainty (of the order of 128 bytes)
in the distance between the vulnerable buffer
and the return address, which the attacker can overcome only through
guessing.
If additional code address obfuscation transformations
are used, (for instance, reordering of routines or introducing gaps within
routines) then the attack becomes even harder.