Learning DFA representations of HTTP for protecting web applications

Abstract

Intrusion detection is a key technology for self-healing systems designed to prevent or manage damage caused by security threats. Protecting web server-based applications using intrusion detection is challenging, especially when autonomy is required (i.e., without signature updates or extensive administrative overhead). Web applications are difficult to protect because they are large, complex, highly customized, and often created by programmers with little security background. Anomaly-based intrusion detection has been proposed as a strategy to meet these requirements.

This paper describes how DFA (Deterministic Finite Automata) induction can be used to detect malicious web requests. The method is used in combination with rules for reducing variability among requests and heuristics for filtering and grouping anomalies. With this setup a wide variety of attacks is detectable with few false-positives, even when the system is trained on data containing benign attacks (e.g., attacks that fail against properly patched servers).

Introduction

Self-healing systems detect problems and repair them with little or no human intervention, and do so in a timely fashion. Although such detection/response combinations are desirable for many classes of problems, one of the most compelling applications is that of computer security, where Internet-connected computers are routinely attacked by computer viruses, worms, and human adversaries. In living systems, response to damage from analogous threats is coordinated primarily by the immune system. Similarly, “computer immune systems” have been proposed to respond to threats that circumvent conventional computer defenses. Earlier work in computer immunology has addressed many security threats, by program code [1], [2] monitoring network connections [3], [4], [5] and low level program behavior [6], [7], [8], [9]. However, as we explain below, these methods in their current form are not appropriate for protecting web server applications.

Web servers are important to protect because they are so ubiquitous, yet they are currently poorly defended. For example, web-based vulnerabilities have been estimated to account for more than 25% of the total number of reported vulnerabilities from 1999 to 2005 [10]. Web servers must accept complex, highly variable inputs from virtually any host on the Internet, and with the emergence of web application services, they must process those inputs in arbitrarily complex ways. These characteristics make the problem of securing web servers especially challenging.

One approach to protecting computer systems, including web servers, is to craft specific defenses for each observed problem, either in the form of code patches or attack signatures. Both strategies, however, require a human to analyze each problem and develop the solution. This limits the feasible response time to a timescale of hours or days, but attacks by self-replicating programs (viruses or worms) can manifest in a matter of seconds [11]; thus, there is a need for automated mechanisms that can detect and respond to threats in real time. Anomaly-detection methods have been proposed as an alternative because they can potentially detect novel attacks without human intervention [12], [13], [14], [6]. In anomaly detection, a model of normal behavior is developed from empirical observations, and subsequent observations that deviate from the model are labeled anomalies. Anomaly detection is problematic in the case of web servers, however, because web traffic is highly variable and it is difficult to characterize normal behavior in a way that both detects attacks and limits the rate of false alarms.

Other researchers have addressed the anomaly detection problem for web servers by measuring the frequency distribution of one or more simple features of a web request (the conduit of most attacks on web servers) and combining those features into a single anomaly measure. Although the features taken individually, such as character frequency, are often not sufficient for accurate detection, multiple features can be combined with better results [15]. However, these anomaly detectors are trained on data that are free of attacks. This requirement is unfortunate because the normal background of today’s Internet contains large numbers of attacks, most of which are harmless against properly patched servers. Signature-scanning intrusion-detection systems (IDS) such as snort [16] can be used to filter out known harmless attacks; however, the high accuracy required for training requires frequent updates to the attack signature database and careful site-specific tuning to remove rules that generate false alarms. This manual intervention reduces the main advantage of using anomaly detection.

To summarize, there is a need for web servers that can detect and repair damage caused by security violations with minimal human interaction. To accomplish this will require techniques for detecting anomalous web requests that are tolerant of the benign attacks that are inevitably present in observations of normal web traffic. This paper describes a system that addresses these criteria, which learns normal requests using deterministic finite automata (DFA) induction. To account for the high variability in normal web requests, we combine the DFA with a set of simple parser heuristics, which remove the most variable parts of the web request before the induction step, and anomaly heuristics for classifying detected anomalies during the testing phase.

In order to test our system, we collected a data set consisting of 65 attacks against web servers, a much larger corpus than has been used in earlier work, and we studied the normal traffic from four distinct web sites over the course of months. The tests show that our system can detect 79% of the attacks with 40 false alarms per day on a complex website; with simpler websites, our system can detect 90%+ with just a few alarms per day. These numbers are competitive with similar methods but do not require pre-filtering of training data to eliminate attacks in the data.

In the remaining sections, we first give background information on intrusion detection in Section 2. We then describe the DFA method for modeling HTTP requests (Section 3), the datasets we developed for testing (Section 4), and our experimental results in Section 5. Implications of the work are discussed in Section 6. Section 7 reviews related work, and Section 8 gives a summary of our results and plans for future work.