Synthesizing fast intrusion prevention/detection systems from high-level specifications*

To build survivable information systems (i.e., systems that continue to provide their services in spite of coor¬dinated attacks), it is necessary to detect and isolate in¬trusions before they impact system performance or func¬tionality. Previous research in this area has focussed primarily on detecting intrusions after the fact, rather than preventing them in the first place. We have devel¬oped a new approach based on specifying intended pro¬gram behaviors using patterns over sequences of system calls. The patterns can also capture conditions on the values of system-call arguments. At runtime, we inter¬cept the system calls made by processes, compare them against specifications, and disallow (or otherwise mod¬ify) those calls that deviate from specifications. Since our approach is capable of modifying a system call be¬fore it is delivered to the operating system kernel, it is capable of reacting before any damage-causing system call is executed by a process under attack. We present our specification language and illustrate its use by de¬veloping a specification for the ftp server. Observe that in our approach, every system call is intercepted and subject to potentially expensive operations for matching against many patterns that specify normal/abnormal behavior. Thus, minimizing the overheads incurred for pattern-matching is critical for the viability of our ap¬proach. We solve this problem by developing a new, low-overhead algorithm for matching runtime behaviors against specifications. A salient feature of our algorithm is that its runtime is almost independent of the number of patterns. In most cases, it uses a constant amount of time per system call intercepted, and uses a constant amount of storage, both independent of either the size or number of patterns. These benefits make our algorithm useful for many other intrusion detection methods that employ pattern-matching. We describe our algorithm, and evaluate its performance through experiments.