Research Abstracts - 2007

Introduction

The goal of the proposed research is to develop new techniques that enable a system to learn where it is vulnerable to an attack or programming error, then automatically generate and evaluate ways that it can thwart the attack or recover from the error to continue to execute successfully. It is designed to work for systems, such as existing standard information technology installations, that have large monocultures of identical applications, for instance internet explorer 6 running on windows XP. By sharing information about attacks, errors, and response and recovery strategies, the system can learn which strategies work best. The end result is a system whose robustness and resilience automatically grow over time as it learns how to best adapt and respond to the attacks and errors that its components inevitably encounter.

We developed a targeted bounds enforcement technology to identify the location of bounds violation errors in the program, by using signals such as the presence of injected code or program failures. We than generate a variety of patches, all of which use bounds checking to eliminate the out of bounds writes that cause the program to fail. These patches are provided to an evaluation and filtering service, which distributes them to other instantiations of the same application, which also contain the same error or vulnerability. These applications randomly apply the different patches (including the possibility of applying no patch at all). They then monitor their execution to determine if the patch caused the program to fail or otherwise perform unacceptably. The evaluation and filtering component then uses this monitoring information to learn which patches provide suboptimal performance and filter these patches out.

Data Structure Consistency Learning and Enforcement Attacks or errors may manifest themselves as violations of data structure consistency properties. Our data structure consistency enforcement technology first monitors selected instantiations of a given application to learn properties that all data structures appear to satisfy in successful executions. By sharing constraints extracted from multiple instantiations, the chances of learning an incorrect constraint are minimized (but not completely eliminated). Once learned, the constraints are then provided to other instantiations.

The instantiations then monitor their execution for violations of the constraints and randomly apply different repair strategies (including applying no repair at all) when they detect a violation. By analyzing the results of the different repair strategies, the evaluation and filtering component learns which repairs produce the best results, then filters out repairs which produce suboptimal results. Note that it also recognizes and eliminates incorrect learned constraints—the best alternative for such constraints is simply no repair at all.

We will use Daikon [3] to learn these constraints. The Daikon tool for dynamically detecting likely program invariants, which works on C, Java, and Perl programs, Excel files, and other input sources, has been used in published research from at least a dozen universities and research labs, and has also been applied to real-world programs.

We intend to produce a production-quality implementation of our techniques. Moreover, we intend this implementation to operate successfully on standard COTS stripped Windows binaries, including all Microsoft core services, Microsoft Office, and Microsoft servers. Supporting these large, complex commercial applications is an enormously challenging technical task because the system must correctly deal with the full complexity of the Windows execution environment.

We use the Determina Managed Program Execution Engine (MPEE) to support these applications. This software provides an efficient emulation engine for Windows binaries. It typically imposes less than 5% overhead, yet still provides an API that enables tools to inspect every instruction before it executes, to suspend the execution at chosen points, and to arbitrarily modify and patch the application.

Problem Description

Most information technology installations today deploy many identical instantiations of the same software product on multiple machines. Because of this monoculture, a single error or security vulnerability can cause the entire system to fail catastrophically as all instantiations fail when presented with the same attack or error. Two especially important manifestations of attacks or errors are the presence of injected code or damage to the information representation of the program. Ideally, it would be possible to use learning to change the weakness of this monoculture (many instantiations of the same application) into a strength. Specifically, one could learn from the failure of one instantiation to identify the error or vulnerability responsible for the failure, develop a mechanism to protect all instantiations from the worst effects of the error or attack and to enable the applications to recover and to continue to execute after the error or attack. If there are multiple possible mechanisms or mechanism variants, it would be desirable to try the different variants to see how they work out. It would be then possible to identify the most effective variants and discard less effective variants.

One problem that greatly complicates the realization of this vision is the difficulty of developing techniques that can effectively monitor and modify executables in the complex world of COTS Windows software. Challenges include the difficulty of building the efficient emulation system required to provide the API for the monitoring and modification system and, especially, the difficulty of correctly handling the complexity of the various system interfaces upon which all COTS Windows applications rely.

Research Goals

Our first goal is to develop a targeted bounds checking technique that applies bounds checking in combination with continued execution to parts of the application that have been found to contain an error or vulnerability. This technique uses the presence of injected code to locate parts of the program that have a bounds error, then generates a variety of patches that use bounds checking to execute through the error. The goal is to use the availability of multiple instantiations of the same application to have the applications collaborate so that one instantiation can locate the vulnerability and pass the information along to other instantiations, which then try various alternatives to evaluate which patches work best. If successful, the result would be a system that automatically recognizes attacks and errors and learns which responses work best. Our goal is to detect 95% of injected code attacks and recover from 60% of these attacks.

Our second goal is to develop a data structure consistency enforcement technique that leverages the presence of multiple instantiations of the same application to learn important data structure consistency constraints and the best ways to repair such constraints. This technique will combine observations from multiple instantiations to build a set of constraints that the program is expected to observe. These constraints will be distributed to the other instantiations, which will apply various data structure repair strategies (including no repair at all) and combine their results to determine which strategies work best. If successful, the result would be a system that automatically recognizes errors and attacks that corrupt the information representation of the application and learns how to best recover from these violations. Our goal is to detect 50% of attacks and errors that damage the information representation and to recover from more than 30% of these errors and attacks.

Systems today remain vulnerable to attacks and errors that can catastrophically take down an entire computing system. If successful, the deployment of our technology will significantly improve the ability of these systems to thwart and recover from errors and attacks. The ideal end result would be a significant reduction in the vulnerability of our information technology infrastructure to attacks from adversaries and internal errors that disable the system. It will also demonstrate how to obtain and apply learning technology to improve the behavior of complex computer systems.

Technical Approach

This proposal is a collaboration between researchers at the Massachusetts Institute of Technology and Determina, a company currently marketing a product that has been demonstrated to completely protect both commercial and open-source off-the-shelf software products against code injection attacks, including day-zero worms. Determina’s current technology recognizes when a program has been attacked, then terminates the program’s execution or the offending thread before the attack can take effect. The goal of this proposal is to exploit the availability of a community of machines running the same software to augment Determina’s technology so that it can learn how to make attacked programs rebuff an attempted attack and continue to execute successfully. We propose to augment Determina’s technology with two new techniques: 1) targeted bounds enforcement and 2) data consistency enforcement.

Both of these techniques involve learning key properties that the program must respect to execute successfully, then selectively monitoring the execution to enforce these properties as the program runs. Our proposed targeted bounds enforcement technique first uses the Determina execution engine to identify an attack that exploits an out of bounds memory vulnerability in the program. It then uses failure-oblivious computing [2] to generate a patch that enables the program to continue to execute through the error. After patch distribution and validation, both other currently executing versions of the program and subsequently executing versions are immune to all attacks that attempt to exploit the vulnerability. Our proposed data consistency enforcement technology uses Determina’s code instrumentation API extend our consistency constraint learning and enforcement technology to stripped Windows binaries [1]. We also propose to develop new techniques that exploit the availability of a large community of machines executing identical copies of the software. Specifically, these techniques will synthesize observations from multiple machines to recognize false learned constraints and to progressively learn which repairs produce the best results.

The goal of our targeted bounds enforcement technology is to preserve the integrity of core elements of the execution (such as the procedure call stack linkage) to enable the program to execute after an attack. The key idea is to apply failure-oblivious computing [2] to discard the illegitimate memory writes that would otherwise corrupt the execution. With these key elements preserved, the program can then continue to execute even in the face of attacks.

Current implementations of failure-oblivious computing use a compiler to introduce the checks required to recognize and discard illegal writes. This approach requires access to the source code of the program; the checks may make the program execute as much as ten times slower than the original.

We propose to eliminate these drawbacks as follows. First, we will leverage the Determina execution engine to develop a technique that will learn the location of errors in the program that are the root cause of the vulnerability. Specifically, we will tag the procedures that are executing at the time that the Determina execution engine detects the attempt to execute illegitimate code as potential sources of the out of bounds memory error. We will then use Determina’s binary code rewriting technology to generate a patch that uses failure-oblivious computing to eliminate the out of bounds writes that comprise the vulnerability. We will then use Determina’s LiveShieldTM technology to distribute the patch to all members of the application community. Note that because the checking overhead will be restricted to the code containing the error, the vast majority of the code will execute without checks at its original speed.

The basic approach of learning constraints in the community is as follows:

• Windows binaries (the target program) are instrumented to extract sample information (the value of variables at various program points).
• The resulting sample data is sent to Daikon (which is running in a separate process)
• When the target program exits (or at configurable intervals), Daikon writes out a constraint file.
• The Determina Node Manager transfers each constraint file as it is created to a central server.
• At the central server, contraint files from different clients and different times are merged to create constraints that are valid across all of the instrumented executions.

References:

[1] Derek Bruening, Timothy Garnett, and Saman Amarasinghe. An infrastructure for adaptive dynamic optimization. In Proceedings of International Symposium on Code Generation and Optimization (CGO ’03), pages 265–275, March 2003.

[2] Martin Rinard. Acceptability-oriented computing. In OOPSLA ’03: Companion of the 18th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, pages 221–239, New York, NY, USA, 2003. ACM Press.

[3] Michael D. Ernst, Jeff H. Perkins, Philip J. Guo, Stephen McCamant, Carlos Pacheco, Matthew S. Tschantz, and Chen Xiao. The Daikon system for dynamic detection of likely invariants. In Science of Computer Programming, 2007.