There is a rich history of programming exploitation which makes use of the insecurity of the C memory model. To counteract the threats of memory corruption attacks, several techniques have been implemented. The problem still remains though, and since the programmer is responsible for making all the checks, even the most restrictive protection schemes have their limitations.

Radu is a Junior C/C++ software engineer on the Hubgets Core team. Since memory corruption attacks are something every programmer should be aware of, he came up with the idea of writing the current article, where he explains how some of these memory corruption attacks may happen, indicating a set of solutions that are presently applied to prevent them. You’ll also find a series of tips on how, under specific circumstances, one can use printf to inject instructions even under stiff security constraints.

Something to begin with

You’re probably already familiar with the old example of the stack buffer overflow attacks.

#include <string.h>
void foo (char *bar) {
    char c[12];
    strcpy(c, bar); // no bounds checking
}
int main (int argc, char **argv) {
    foo(argv[1]);
}

Here’s the normal layout of the stack.

If the first program argument is a string longer than 12 bytes (including the null terminator), when copying this string to the variable c, its bytes will be stored on the stack. Due to the stack layout during the execution of function foo, data will be overwritten. An attacker could provide a string long enough to overwrite foo‘s return address. When foo returns, it pops the return address from the stack, which results in the program continuing execution from that address. Thus, the execution is redirected to a path chosen by the attacker.

In the image above, an input of “AAAAAAAAAAAAAAAAAAAA\x08\x35\xC0\x80” was given to the program. The effect is overwriting the return address with the value 0x80C03508 (note the little endianness), which may be the address of a function chosen by the attacker.

This is a simple case of a control flow hijack attack. The code pointer is modified and the control flow leaves the valid graph. However, operating systems and compilers have implemented several protection schemes against various types of exploitation.

The Defense

For instance, stack canaries may detect buffer overflows before the execution of unintended code is initialized.

As soon as the program starts, small random integers are chosen and placed in the memory just before the stack return pointer. When the overflow overwrites the return address of the function, the canary value will also be changed. Before the method uses the return pointer on the stack, the value is checked. This way, a simple overflow attack just like the one shown in the example above will be detected.

However, there are other indirect means by which an attacker may gain control over the instruction pointer. Apart from redirecting the execution, malicious programs may be stored in the buffer itself on the stack.

To counterpart this scenario, code execution from the stack may be disallowed by enforcing a memory policy on the stack memory region. Thanks to this data execution prevention policy, the only way for an attacker to succeed with a stack buffer overflow would be to place their code payload in a non-protected region of memory, or to disable the execution protection. If there are ways to store the malicious code in the heap, the policy will be easily tricked.

Suppose the attacker cannot find ways to place shellcode in the heap. He can still resort to techniques such as return to libc. In such a case, instead of directly injecting code on the stack, first the stack will be infected with the proper configuration so that the execution should jump to routines that are already present in the executable memory of the process. This way a sequence of standard library calls may be achieved, with the effect of disabling memory execute protections.

In the latter exploit method, the attacker needs to know the addresses of executable routines that can be used. A randomization of the memory layout could theoretically prevent this. Address space layout randomization places randomly in memory key areas of a process like the positions of the stack, heap and libraries. Compiling programs as PIE (position-independent executables) helps randomizing the base of the executable too. However, the entropy of the randomization should be high enough so as to avoid brute forcing the memory space.

Make it stiffer

Apart from these protection techniques, one may use the control flow graph of a program to check if the program execution follows a valid path through the static CFG. Control-Flow Integrity adds a check before each indirect jump/call or function return, ensuring that the target location is among the valid locations for that jump.

void a() {
    foo();
}
 
void b() {
    foo();
}
 
void foo();

However, in this example, where foo is called from a, CFI is not enough to stop an attacker from returning to b when exiting from foo. This happens because a path from foo back to b is considered valid in the control flow graph.

Adding a stack integrity policy (or a shadow stack) helps solving this. The shadow stack ensures that each function call can only return to the function that called it.

When these two protection schemes are active, the attacker will have very limited influence over return instructions as he will not be able to jump to other arbitrary locations like other call-sites.

In some implementations, however, the shadow stack is omitted because of the performance overhead it triggers.

Can’t fight all the breaches

It will be extremely difficult for an attack to occur inside a system that implements all of the above protection schemes. The execution flow of a program should stay within a predefined control flow graph.

In a paper entitled Control-Flow Bending: On the Effectiveness of Control-Flow Integrity, the authors demonstrate that, even within those execution limits, some “gadgets” may be written in order to “inject” various forms of small programs.

Specifically, if an attacker has access to the arguments given to a printf call, he can theoretically perform Turing-complete computations.

A conceptual example

int main() {
    int target;
    int cond = 1;
    int x = 123;
    char *fmt = malloc(13);
 
    strcpy(fmt, "%s%hhnQ%*d%n");
 
    /* equivalent to executing:
    * target = cond ? x : target */
    printf(fmt, &cond, fmt + 6, x - 2, 0, &target);
 
    printf("\nTarget is %d\n", target);
    free(fmt);
    return 0;
}

In the code sample shown above, you can see how printf can be used to conditionally write a value to a location.

The operation that we want to execute is target = cond ? x : target. This is achieved with printf due to the format string “%s%hhnQ%*d%n“. But how?

Let’s analyze the rest of parameters given to printf.

• &cond: The “%s” format specifier expects a string. We pass a pointer to an integer that is either 0 or 1. Because of the endianess, the integer 1 is stored as two bytes: 0x01 (low) and 0x00 (high). The bytes in the integer 0 will be 0x00 and 0x00. This is important because if the condition is 1, then 1 byte will be printed. Otherwise, no bytes will be printed.
• fmt + 6: This is the address of the character Q inside the format string. The “%hhn” format specifier writes a single byte consisting of the number of characters written so far. This byte is written to the corresponding address given as argument. In this case, the address is fmt + 6. This means that, if the condition is 0, the Q in the format string will be replaced by a 0 (there were 0 bytes written for the previous “%s”). If the condition is 1, then Q is replaced by 1. It’s an essential trick to this example because, if the condition is 0, the format string becomes “%s%hhn0%*d%n”. When printf parses the next part of the format string, it will meet 0, the null byte and it will stop. The execution has no effect on the target variable, which is exactly what we wanted when the condition is false.
• x – 2: The “%*d” format specifier expects a number that specifies how many bytes of padding to print and the integer to be printed with that padding. We give a padding of x – 2 because so far two bytes have been printed and we want x bytes to be written in the end.
• 0: The integer to print with the above padding. Its value does not matter.
• &target: This address will be used with “%n” format specifier. What happens is that a value consisting of the number of bytes printed so far will be written at the address given by &target. This number is x – 2 (the above padding) + 2 (the condition) = x. This way, the integer value x is written at the address &target.

Printf is Turing-complete

The way to achieve Turing completeness for this printf-oriented programming is to implement a functionally complete set of logical operators and to find a method to loop the execution.

The code sample below implements logical OR and NOT operations using the concepts previously illustrated. A true value is represented as the byte sequence 0x01 0x00, while a false value is represented as the byte sequence 0x00 0x00.

void or(int *in1, int *in2, int *out) {
    printf("%s%s%n", in1, in2, out);
    printf("%s%n", out, out);
}
void not(int *in, int *out) {
    printf("%*d%s%n", 255, 0, in, out);
    printf("%s%n", out, out);
}

OR operation

In the first printf, if either of the in operands is true, then at least 1 byte will be printed (for false operands, no byte is printed with the “%s” specifier). Then the “%n” will cause printf to store the number of bytes printed so far to the address given by out. This way, if at least one operand is true, the value stored is non-zero. The second printf simply normalizes the value at out address, making it 1, if it was non-zero and leaving it 0 otherwise.

NOT operation

First, the integer 0 (its value is not important) is printed inside 255 bytes of padding. Then the bytes at in are printed. This may result in printing one (in in true) or zero (in is false) bytes to the output. What follows is the “%n” specifier which saves the number of bytes printed to the out address.

For 255 bytes printed (in is false), the bytes at out are 0xFF 0x00 (little endian ordering). Then the second printf, which saves to out the number of bytes it printed from the out address itself, will save 1 byte (out is true).

For 256 bytes printed (in is true), the bytes at out are 0x00 0x01. Thus, the “%s” in the second printf will not print any bytes, and the value 0 will be saved at out (out is false).

Looping

In order to loop the printf-program execution, one needs a way to loop the format string. The printf() function uses a pointer that keeps track of the processed characters in the format string. If an attacker wants to achieve a loop effect, he must overwrite the value of this pointer, setting it to point to other desired regions inside the format string. As difficult as this step might be, it is not impossible.

Conclusions

Even though modern protection schemes constitute a strong defense against control-flow hijacking, they cannot ensure complete security. Certainly, there are trade-offs between protection techniques and performance, but even a well guarded system can suffer breaches as long as the programming language allows it.