Visible to the public Preventing Exploits Against Software Of Uncertain Provenance

Presented as part of the 2012 HCSS conference.

David Melski,, GrammaTech, Inc.

We describe the results of the first phase in the development of PEASOUP, a technology that enables the safe execution of software executables of uncertain provenance. PEASOUP (Preventing Exploits Against Software of Uncertain Provenance) prevents exploits of number-handling weaknesses and memory-safety weaknesses in Software of Uncertain Provenance (SOUP). In addition, PEASOUP prevents any exploit based on arc-injection or code-injection, regardless of the type of vulnerability targeted for attack. PEASOUP advanced the state-of-the-art in automatic program analysis, diversification, confinement, and remediation. PEASOUP is joint work of GrammaTech, the University of Virginia, the Georgia Institute of Technology, and Raytheon.

Analysis. The PEASOUP analyzer uses a novel combination of precise run-time analyses [40] with recent techniques for generating high-coverage test suites [19, 39]. The analyzer has the following components: test-case generation, input classification, intermediate representation recovery, variant generation, and variant validation.

Diversification. During Phase I, we developed a novel diversification technique called Instruction-Layout Randomization (ILR) that works by relocating 99.7% of the instructions in a program. Many approaches to diversification suffer from low-entropy or complicated estimates of the measure of introduced entropy based on assumptions that may not hold for some executables. ILR advances the state of the art in program diversification because it does not suffer from these shortcomings: it is simple to show that 99.7% of instructions can be relocated to any one of 231 addresses (on a 32-bit machine). This represents 3.5 orders of magnitude improvement over some of the most common, successful diversification techniques. ILR makes any type of arc-injection attack infeasible, including attacks based on Return-Oriented Programming (ROP). Furthermore, ILR still has the desirable properties of existing diversification techniques: it has low overhead and is easy to deploy.

In addition to ILR, we demonstrated that PEASOUP can safely perform Stack-Layout Randomization (SLR) on software binaries. Previous approaches to randomizing the layout of the stack required access to a program's source code

Confinement. Both ILR and SLR demonstrate the power of PEASOUP's analysis phase to recover high-quality IR. In fact ILR and SLR demonstrate that it is possible to implement confinement techniques such as control-flow integrity and stack-canaries directly on binaries. Previous binary analysis techniques were not adequate for these purposes.

Phase I also demonstrated that it is possible to combine Software Dynamic Transaltion with Secure In-VM Monitoring (SIM). SDT provides PEASOUP with the ability to implement fine-grained security policies. However, the translator itself could be subject to attack. SIM solves this short-coming by using hard-ware memory protection to ensure that the translator is not compromised. We believe that this represents an advance in the provable security guarantees that can be made for a fine-grained policy enforcement technique.

Remediation. Finally, PEASOUP demonstrated advances in the state-of-the-art for automatic program remediation during the independent evaluation of the Phase I prototype. Specifically, the padding introduced by PEASOUP's diversification techniques allowed real-world applications (bzip2, ngircd) to continue correct execution when they were provided malicious inputs.

This work is sponsored by Air Force Research Laboratories (contract #FA8650-10-C-7025).


Dr. David Melski is the principal investigator of GrammaTech's PEASOUP effort. Dr. Melski is the vice-president of research at GrammaTech. In that role, he oversees GrammaTech's research on automated program analysis and transformation to develop tools and techniques that aide with information assurance, software producibility, reverse engineering of software, and software protection. Melski graduated summa cum laude from the University of Wisconsin in 1994 with a B.S. in Computer Sciences and Russian Studies. He received his Ph.D. in Computer Sciences from the University of Wisconsin in 2002, where his research interests included static analysis, profiling, and profile-directed optimization. His publications include an invited submission to the Journal of Theoretical Computer Science on the interconvertibility of a class of set constraints and context-free reachability. Melski's Ph.D. thesis presented a framework for developing interprocedural path-profiling techniques, and examined the use of path profiles for automatic program optimization. While at Wisconsin, Melski worked as a research assistant and was twice awarded the CISCO fellowship.

Creative Commons 2.5

Other available formats:

Preventing Exploits Against Software Of Uncertain Provenance