This is a followup to our previous post, which introduces our research exploring new strategies for protecting legacy applications on the DARPA CFAR program. Briefly, our approach is to generate variants of a target application that behave the same when given benign input but different when given malicious input. Then we run a set of these variants in a multi-variant execution environment (MVEE) that can detect a divergence in behavior, revealing attacks like buffer overflows, after which we can react and recover. Please check out our previous post for an overview of our approach before diving into the details below.
In this post, we describe some of our strategies for generating secure variant sets and highlight some findings that illustrate why choosing the appropriate transformations can be surprisingly challenging, as in some cases layering additional defenses may negate previously-applied protections.
Variant Generation Transformations
Previously, we described our workflow of generating variants of a program by building the target application with a diversifying compiler. We call this a “multicompiler” and call the specific techniques that diversify a program “transformations.” Some of the transformations we support include:
- code layout randomization: reorder functions in a binary so code of interest exists at different locations in each variant
- globals layout randomization: pad and reorder globals so their absolute and relative positions are different in each variant
- stack variable randomization: like globals layout randomization, but for the variables in each stack frame
- heap layout randomization: runtime over-provisioning and random allocation to place heap objects at different locations in each variant
- C++ vtable randomization: reorder virtual function table entries to detect attacks that use these code pointers
- data randomization: XOR data before storing it in memory, XORing back on load. Partition variables via alias analysis and give each set a different XOR key in each variant, so an out-of-bounds write from
XtoYfillsYwith the attacker’s data XORed withX’s key - data cross-checks: check that data values used in conditionals correspond across all variants in a set
- function-entry cross-checks: make sure variants in a set are always executing corresponding functions at runtime
- fine-grained heap object ID checks: track allocations and cross-check variants in a set to detect e.g., use-after-free attacks
- struct layout randomization: in general, the programmer is permitted to make assumptions about the underlying order of struct field, but in circumstances where it is safe to permute this can help detect within-struct attacks
Running Variant Sets
Memory corruption exploits are brittle in that they depend on specific internal and low-level properties of a program. By varying these properties in each variant, we can produce variant sets where an exploit that works against one variant cannot work against another. But how exactly are variants run together in a MVEE?
The feature/performance trade-offs of different MVEEs vary, but we rely on the core property that all variants run simultaneously, and the MVEE unifies input to and output from each variant (and effects, e.g. syscalls) to make the set appear to be a single instance to other parts of the system.
This means the MVEE broadcasts the attacker’s input to all variants – an attacker cannot send different input to each variant. Similarly, the MVEE intercepts each variant’s attempt to produce output (or other system effect, like file I/O) and unifies this output – or detects/blocks/reacts to a divergence in behavior. So, an attacker cannot directly query each variant for variant-specific data.
Hazards of Blindly Applying Software Diversity Techniques
Conceptually, if randomization reduces the chance of an attack succeeding to some probability P, and you combine N variants in a set, one might guess that the probability that the set remains vulnerable is P^N. In fact, this is not always the case, and composing software diversification techniques requires care as some combinations can negate the security you thought you were adding. This section contains some examples of this hazard and guidelines for constructing secure variant sets. We discuss this problem in more detail in our Layered Assurance Workshop paper, titled “Composition Challenges for Automated Software Diversity”.
Example: “Skewed Return” Attack
Imagine the application to defend has some stack variable X and a vulnerability exists that allows an attacker to overflow past the end of X and overwrite the saved return address on the stack, controlling the execution of the application when the function returns.
application : | VariableX_1 | ... | RET | // attacker's RET goal = 12345
payload : | Xfiller>>>>>>>>>>>> 12345 |
When the MVEE unifies the variant set’s input and output it will duplicate the payload from the attacker and pass it to each variant simultaneously. Against a set of two duplicate variants, the attacker’s chosen value will overwrite the saved return address in each variant identically. If we apply code randomization to each variant, then a desirable function the attacker wishes to execute will be located at different addresses in each variant. The attacker can make the variants jump to whatever address they wish but cannot choose different addresses for each variant. The MVEE can detect when a variant starts to be have differently than the others (or crash), revealing the attack.
variant 1 : | VariableX_1 | ... | RET_1 | // RET_1 goal = 12345
variant 2 : | VariableX_2 | ... | RET_2 | // RET_2 goal = ABCDE
payload : | Xfiller>>>>>>>>>>>> 12345 | // cannot achieve both goals
In the sample above, the “twinned” layout prevents the attacker from constructing any payload that will overwrite RET with the (different) desired values in both variants.
Consider now that instead of overwriting the return, the attacker wishes to overwrite from X to some adjacent stack variable Y. We can randomize the order of stack variables, so an overwrite past the end of X may access Y in one variant, but not another. For example, if we align the vulnerable buffer X:
variant 1 : | VarX_1 | VarY_1 |
variant 2 : | VarY_2 | VarX_2 | // attacker cannot reach Y_2
payload : | Xfiller>> AtkY1 |
In variant 2, Y is before X and thus not vulnerable to this overwrite of X. If the variants each attempt to print their values of Y, for example, the MVEE will see variant 1 printing the attacker-corrupted value, and variant 2 printing the uncorrupted value.
Unfortunately, adding stack variable shuffling has negated the protection we originally gained from our code shuffling example above. Shuffling the stack variables changes the offset from the X buffer to the saved return address in each variant, so the attacker now can craft a single payload that overwrites RET with a different code address in each variant simultaneously.
variant 1 : | VarX_1 | Var_Y1 | ... | RET_1 | // attacker wins
variant 2 : | VarY_2 | VarX_2 | ... | RET_2 | // attacker wins
payload : | Xfiller>>>>>>>>>> ABCDE > 12345 |
Padding vs. Shuffling
In additional to shuffling the order of variables, we can insert random padding between variables to increase the amount of entropy. This may seem particularly appealing in regions with few variables (e.g., small stack frames). While there are instances where padding can make it more difficult for an attacker to guess a random layout, there are situations where adding padding makes it harder to detect attacks in a multi-variant environment.
Imagine a vulnerability that allows an attacker to perform an offset write over the contents of an important permission variable. With variable shuffling, there is some chance that an offset write from the vulnerable buffer to permission in one variant manifests as an overwrite of, for example, some function pointer in another variant in the set. If the attacker’s desired permission value is not a valid function pointer then the MVEE may also detect the attack if the variant uses that function pointer. However, introducing padding increases the chance that an out-of-bounds write that is advantageous in one variant ends up only overwriting padding in another variant. This decreases the chance of “incidental” detection (via corruption of other state) and makes it easier for an attacker to overtake variants via “skewed” attacks as described above, or by overtaking single variants one at a time.
Cross-Stack-Frame Attacks and SafeStack
Code randomization leads to the detection of many buffer-overflows that write past the end of a stack variable buffer and onto contents of a parent stack frame, as these overflows clobber the return address between the two stack frames. An attacker’s payload must contain valid a return address value, which the variant uses used to return to the function caller’s context where the (corrupted) data in the parent stack frame is in scope. Well-selected data layouts (avoiding pitfalls such as those described above) constrain the attacker, leaving them unable to create a payload that overwrites the return address with valid code addresses in all variants without the MVEE detecting the attack. Similarly, it may be impossible for the attacker to overwrite the saved base pointer with valid addresses in all variants.
original stack: | vuln[] | saved RBP | RET | parent_frame_data[] |
payload: | ATTACK>>>>>>>>(RBP)>(RET)>>>OVERWRITE_PARENT>> |
SafeStack is a stack protection technique in clang that moves all potentially vulnerable stack variables to a separate “unsafe stack”. Specifically, address-taken variables are moved to the unsafe stack as these are typically prone to out-of-bounds accesses. This leaves return addresses and variables known to be only accessed safely on the “real” stack, which the attacker cannot reach from the overflows on the unsafe stack. Unfortunately, adding SafeStack to variants can make it easier for an attacker to overflow and corrupt data in parent stack frames, as there are no saved return addresses (or saved base pointers, etc.) between stack frames on SafeStack’s “unsafe stack” containing vulnerable buffers.
"safe" stack: | saved RBP | RET |
"unsafe" stack: | vuln[] | parent_frame_data[] |
payload: | ATTACK>>>>OVERWRITE_PARENT>> |
In this scenario, adding SafeStack to variants actually introduces the possibility of previously-infeasible data-only parent-stack-frame overwrites.
Hazard: Data Randomization + “Skewed Data”
The examples above show some hazards of combining multiple transformations, but we must also reason carefully about individual transforms to understand the limitations of each.
Our “data randomization” transformation uses alias analysis to determine the set of memory locations that can be addressed by a given memory access. The results of the alias analysis are used to partition data references and give each set a unique XOR “key.” Variants XOR data with its corresponding key before storing it in memory, then XOR it back on load. This means that an out-of-bounds write from variable X to variable Y will write data to Y using X’s key, which the variant will XOR with Y’s key instead when it later retrieves it from memory. The keys are different in each variant, so this gives data values protected by these keys a similar protection as what we get for code pointers from code randomization: even if the attacker knows what values they need in each variant, they cannot write different values to each variant. At least one variant ends up with “garbage” the attacker cannot control.
At first glance, this seems quite strong: with 64-bit keys, there is a 1 in 264 chance the keys “line up” to give the attacker a specific desired value. However, there is an issue: the “skewed data range” problem. Specifically, the attacker’s desired value(s) may not be evenly distributed across the possible values for the target variable. Consider the code:
if (is_admin) { ... }
The attacker does not need to completely control the content of is_admin in each variant, but only to make is_admin nonzero across the set, which is extremely likely even with data randomization.
Our solution is to insert data cross-checks to make sure the exact content of values used in conditionals are equivalent across the variant set. During variant generation, we instrument variants to pass these values to the MVEE monitor at runtime, so the MVEE can do the comparison across all variants in the set. This maximizes the value of our data randomization transformation, as now the MVEE detects divergent behavior if is_admin has a different value in each variant, even if the conditional expression would have evaluated to true in each. The insertion of these cross-checks requires some additional analysis to avoid cross-checking pointer values, as we expect addresses to vary across the set as a result of our other transformations.
Secure Variant Set Design
So, what makes a good variant set? A full analysis and assurance case is beyond the scope of this post, but some general guidelines:
- Randomize code layout differently in each variant.
- Enforce disjoint memory layouts such that there is no absolute address that is valid in all variants.
- Apply data randomization and cross-checks, with different data rando keys in each variant.
Additionally, it is useful to have two “twin” variants with the same relative data layouts but different code layouts and data randomization keys. Twinned data layouts make it impossible for attackers to use many vulnerabilities to write different variables in each variant, exposing attacks on:
- code pointers values via code layout randomization (and/or disjoint memory)
- data values, via data randomization & data cross-checks
Adding a third variant with a reversed-order data layout of the twins can rule out attacks based on vulnerabilities that can only write one direction, e.g. common overflows past one end of a buffer. In this case, if X can overflow onto Y in the twinned variants, Y will be before X in the “reversed” variant.
Conclusion
Software diversity transformations interact in subtle ways that can impact the security of a multi-variant set, and naively maximizing randomness does not always maximize the chance to detect an attack. We have strengthened our defenses by taking a more structured approach. Please see our paper “Composition Challenges for Automated Software Diversity” for additional detail and recommendations for variant set composition.
Acknowledgments
This material is based upon work supported by the United States Air Force and DARPA under Contract No. FA8750–15-C–0124.
The views, opinions and/or findings expressed are those of the author and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government.
Distribution Statement “A” (Approved for Public Release, Distribution Unlimited).