Proactive Obfuscation

View this page in Romanian courtesy of azoft

Overview

Independence of replica failures is crucial when using replication in reliable distributed services. But replicas that use the same code share the same vulnerabilities. So, replicas do not fail independently when under attack. Proactive obfuscation is a new method of restoring some measure of that independence whereby each replica is periodically restarted using a freshly generated diverse executable.

Various techniques have been proposed for obfuscation---automatically creating diverse executables during compilation, loading, or at run-time. These include address reordering and stack padding, system call reordering, instruction set randomization, and heap randomization. All produce obfuscated executables, which are believed more likely to crash in response to certain classes of attacks rather than fall under the control of an adversary. For example, a buffer overflow attack typically will depend on stack layout details, so replicas using differently obfuscated executables based on address reordering or stack padding are likely to crash instead of succumbing to attacker control.

Model of Obfuscation

Rather than depending on properties of particular obfuscation techniques, we abstract two properties that we require them to satisfy.

Obfuscation Independence.
For t > 1, the amount of work for an adversary to compromise t obfuscated replicas is Ω(t) times the work needed to compromise one replica.
Bounded Adversary.
The time needed for an adversary to compromise t + 1 replicas is greater than the time needed to reobfuscate, reboot, and recover n replicas.

Obfuscation Independence implies that different obfuscated executables exhibit some measure of independence. The premise of current obfuscation methods is that they approximate Obfuscation Independence. Given enough time, however, an adversary might still be able to compromise t+1 replicas. Obfuscation Independence and Bounded Adversary together imply that periodically reobfuscating and rebooting replicas nevertheless makes it harder for adversaries to maintain control over more than t compromised replicas. In particular, by the time an adversary could have compromised t+1 obfuscated replicas, all n have been reobfuscated and rebooted (with the attacker evicted), so no more than t replicas are ever compromised.

Mechanisms

Proactive obfuscation depends on three mechanisms, which are depicted in the following representation of a replicated service with n replicas.

Reply Synthesis.
Clients send input to replicas---each replica implements the same interface as a centralized service and sends output to clients. To transform the output from many replicas into an output from the replicated service, replicas employ an output synthesis function f_d, where d specifies the minimum number of distinct replicas from which a reply is needed. Reply Synthesis is the mechanism that implements the output synthesis function for clients.
State Recovery.
Replicas keep state that may change when they process input from clients---after rebooting, a State Recovery mechanism provides a way for replicas to recover state so they can continue participating in the replicated service. To convert state received from multiple replicas into a single state, rebooted replicas employ a state synthesis function g_r, where r specifies the minimum number of distinct replicas from which a reply is needed.
Refresh.
A Refresh mechanism provides freshly obfuscated executables to replicas, periodically reboots hosts, and informs replicas of epoch changes

Implementation

We used these mechanisms to implement prototypes of two services: a distributed firewall (based on pf in OpenBSD) using state machine replication and a distributed query-update service using quorum systems. Both prototypes implement the mechanisms in userspace using a pseudo-device to handle packets received by the kernel. Both are implemented in C using OpenSSL. Our paper gives details of the evaluation of these prototypes.