USENIX '05 Paper
[USENIX '05 Technical Program]
Automatic Synthesis of Filters to Discard Buffer Overflow Attacks:
1 illustrates the architecture of ARBOR, which forms a protective layer between a process and the external environment by adaptively filtering out attack inputs. The adaptation is based on a feedback loop: inputs which don't trigger an intrusion report from the detector are allowed to pass through the filter unmodified, while inputs that trigger an intrusion report activate the feedback loop, causing the filter to be modified to block future attacks. The principal components of ARBOR are described below.
The input filter inspects all input entering the system and filters out (i.e., drops) those inputs that match existing filter rules. The filtering rules are generated (automatically) by the analyzer component, and are intended to capture characteristics that distinguish attack-bearing inputs from benign ones.
The behavior model is a central component that is consulted by all components of ARBOR. It is constructed from events, such as system calls and other relevant library calls, intercepted by the logger. The model takes the form of a finite-state automaton that is similar to a control-flow graph of a program, except that (a) it records only those events reported by the logger, and not the internal program actions, such as assignments and jumps, and (b) it captures only those program paths that were actually traversed. The behavior model is based on our earlier work . The behavior model provides contextual clues that form the basis of the filter generation logic in the analyzer component, as well as provides the tests made by the input filter.
The logger, like the rest of the components, is implemented using library call interposition. (Instead of system call interposition, we use library interposition because of its low performance overhead. Library interposition also provides adequate security for our purposes, since we are interested in program behaviors before it is compromised.) It records a log of input events that is used subsequently by the analyzer. In order to reduce space as well as time overheads due to logging, only a subset of data is sampled and logged.
The detector is external to ARBOR. Our current implementation uses address obfuscation  to build the detector. With the defense of address obfuscation, each buffer overflow attempt will be turned into a server crash. We intercept this crash event to trigger the feedback loop in ARBOR.
The analyzer is responsible for synthesizing filters that distinguish attack-bearing inputs from benign ones. The analyzer resides in a separate process from the protected process, collecting recent program behavior events from the logger. If the protected process is attacked, the analyzer will be notified by the detector. Upon receiving a notification, the analyzer examines recent inputs to the protected process to identify attack-bearing inputs. The process of analysis is described in greater detail in the following section.
One of the key insights in this paper is that we can infer relevant context information by observing the actions of the protected process, e.g., the execution path taken by the program, the contents of runtime stack at the point of input operation, parameters to input operation. We treat a process as a state machine, which makes transitions from one state to another. The transitions are made on library calls. In our approach, we use the location in the program from which library calls are made to represent states of the state machine. The state machine provides a context of the process's current operation. In addition, we may rely on context information observed near the input operation in question. This leads to two major types of contexts: current context and historical context.
Current context is the program state at the point of input, which helps to distinguish a specific input operation from others made by the protected program. In our implementation, current context is defined by the location in the program from which the input operation was invoked, and a sequence of return addresses on the program's stack. The return addresses provides information about how the current operation is invoked. It is particularly helpful when the program uses a centralized input handler function that is called from multiple places in the code, and this function in turn invokes the actual input operation. In this case, the calling location for the input function may always remain the same, but the sequences of return address on the stack are different.
With the current context, the analyzer synthesizes a filter rule matching the attack as follows. For each suspicious input, the analyzer first identifies its current context , and then retrieves the input statistics under context , which is maintained by the logger during the program's normal execution. If in this context, the size of the suspicious input is significantly larger than the maximum size that has ever been seen during normal execution, we report this input as an attack-bearing input. The synthesized filtering rule is simply one that flags an attack if the input size is larger than the geometric mean of and .
If the context of all input operations made by a program are identical, then the above approach may fail to distinguish between attack-bearing and benign inputs. In this case, we extend our approach to use historical context, which takes into account the program paths that were taken prior to the input operation.
We used ARBOR to defend several programs against remote buffer overflow attacks. Our focus was on ``real'' buffer overflow attacks, so we examined buffer overflow attacks reported on securityfocus.com during 2001-2003. We found eight attacks with working exploit code.
Figure 2 shows the results obtained with these programs, which are ratios of attack-bearing input size and maximum benign input size. A ratio less than one indicates that ARBOR cannot distinguish attack-bearing input from benign input under the program context used. The results are divided into three groups according to the context involved in the synthesized filters. In the first group (gtkftpd, ircd, lshd, ntpd), current context (specifically, the program location from where the input operation was called) was enough to generate an effective filter. The programs in the second group (oops, epic4, samba) received several types of inputs from a single location, so current context was not sufficient to synthesize filters. However, by using historical context, ARBOR was able to create an accurate filter that discarded subsequent attacks. The third group (passlogd) consists of a single program, for which ARBOR cannot successfully generate a filter. The buffer overflow in the third group is caused by part of the input, which cannot be identified by the overall length of the input.
As a final point, we note that we restricted ourselves to length-based
filters as a way to stress our approach for inferring and using program
context in filtering rules. By using other criteria, such as input
character distributions, in conjunction with length-based and
context-based filtering rules, the approach can be made even more
Automatic patch generation  attempts to deal with rapidly propagating worms by automatically generating a patch to fix the vulnerability being exploited by the worm. The primary differences with our approach are that  uses a more complex generate-and-test approach to diagnose the vulnerability exploited in an attack, requires source code of the protected server, plus an isolated, sandboxed duplicate of the protected server to test the correctness of the patch.
The HACQIT project  takes an alternative approach that combines software diversity with content-filters deployed at the network level. Attacks are suspected when two implementations of the same software yield different results on the same input. A rule-based algorithm is used to learn characteristics of inputs suspected of containing attacks, and generate a filter to discard such requests in the future at the firewall. This algorithm has been shown to work against Code Red worm. However, it is not clear how the algorithm can be generalized to deal with all types of buffer overflow attacks.
Failure-oblivious computing  is a source code transformation approach that can also recover quickly from attacks. It detects out-of-bounds write accesses, and directs them to a different (free) memory area. Subsequent out-of-bounds reads to the same area return the data that was previously written. Other out-of-bounds reads return carefully chosen values, e.g., all zeroes. The main strength of this approach is that it reliably detects the root cause of the problem. Its weaknesses are the high overheads required for memory error detection, often exceeding 100%; and the possibility that processing the attack input may cause the program to fail and/or crash, although their experiments indicate that is atypical.
While the approach is very effective on existing attacks, it does have some weaknesses that may be exploited in attacks specifically designed to fool it. For instance, attacks may be delivered through a sequence of small packets, causing each input operation to return a small amount of data. We are developing techniques to deal with this problem by assembling together the data returned by successive input operations, and developing filters based on this assembled data rather than the data returned by individual input operations.
A second problem concerns attacks where the buffer overflow is triggered by a field in the request, and not the entire request. Therefore, the length of input is not a characteristic of the attack. In this case, we need to identify the vulnerable field in the input, and use the identification information to increase the accuracy of program contexts. We are currently investigating techniques to handle such attacks.
This paper was originally published in the
Proceedings of the 2005 USENIX Annual Technical Conference,
April 1015, 2005, Anaheim, CA, USA
Last changed: 2 Mar. 2005 aw