Search

Commodity operating systems kernels are typically implemented using low-level unsafe languages, which leads to the inevitability of memory corruption vulnerabilities. Multiple defense techniques are widely adopted to mitigate the impact of memory corruption on executable code and control data. Nevertheless, there has not been much attention to defend against corruption of non-control data despite the fact that previous incidents of kernel exploitation showed that corrupting non-control data is a real threat. We present PrivWatcher, a framework for monitoring and protecting the integrity of process credentials and their usage contexts from memory corruption attacks. PrivWatcher solves multiple challenges to achieve this objective. It introduces techniques to isolate and protect the data that define process credentials and guarantee the locality of this data within the protected memory. Then, by adopting a dual reference monitor model, it guarantees the Time of Check To Time of Use (TOCTTOU) consistency between verification and usage contexts for process credentials. Moreover, it provides a secure mechanism that allows the presumably protected kernel code to verify the protected data without relying on unprotected data fields. PrivWatcher provides non-bypassable integrity assurances for process credentials and can be adapted to enforce a variety of integrity policies. In this paper, we demonstrate an application of PrivWatcher that enforces the original semantics of the OS kernel's access control policy: a change in process privileges is legitimate only if an uncompromised kernel would have allowed it. We implemented a PrivWatcher prototype to protect Ubuntu Linux running on x86-64. Evaluation of our prototype showed that PrivWatcher is effective and efficient.

SEAndroid is a mandatory access control (MAC) framework that can confine faulty applications on Android. Nevertheless, the effectiveness of SEAndroid enforcement depends on the employed policy. The growing complexity of Android makes it difficult for policy engineers to have complete domain knowledge on every system functionality. As a result, policy engineers sometimes craft over-permissive and ineffective policy rules, which unfortunately increased the attack surface of the Android system and have allowed multiple real-world privilege escalation attacks. We propose SPOKE, an SEAndroid Policy Knowledge Engine, that systematically extracts domain knowledge from rich-semantic functional tests and further uses the knowledge for characterizing the attack surface of SEAndroid policy rules. Our attack surface analysis is achieved by two steps: 1) It reveals policy rules that cannot be justified by the collected domain knowledge. 2) It identifies potentially over-permissive access patterns allowed by those unjustified rules as the attack surface. We evaluate SPOKE using 665 functional tests targeting 28 different categories of functionalities developed by Samsung Android Team. SPOKE successfully collected 12,491 access patterns for the 28 categories as domain knowledge, and used the knowledge to reveal 320 unjustified policy rules and 210 over-permissive access patterns defined by those rules, including one related to the notorious libstagefright vulnerability. These findings have been confirmed by policy engineers.

State estimation is a fundamental question in a power grid and it is used to understand the state of power grids based on readings of sensors placed at important power grid components. Current state estimation approaches are highly vulnerable to malicious attacks; an attacker can compromise one or a few sensors to mislead state estimation and thus the power grid control algorithms, leading to catastrophic consequences (e.g., a large-scale blackout). This paper presents a series of attack-resilient state estimation algorithms for power grids. These algorithms use the intrinsic relationship among the state variables and the sensor measurements to effectively tolerate malicious sensor readings. This paper also investigates the properties of these algorithms through theoretical analysis and simulation, which both demonstrate the effectiveness of the proposed approaches.

Virus Scanning-as-a-Service (VSaaS) has emerged as a popular security solution for virtual cloud environments. However, existing approaches fail to scan guest memory, which can contain an emerging class of Memory-only Malware. While several host-based memory scanners are available, they are computationally less practical for cloud environments. This paper proposes SEER as an architecture for enabling Memory VSaaS for virtualized environments. SEER leverages cloud resources and technologies to consolidate and aggregate virus scanning activities to efficiently detect malware residing in memory. Specifically, SEER combines fast memory snapshotting and computation deduplication to provide practical and efficient off-host memory virus scanning. We evaluate SEER and demonstrate up to an 87% reduction in data size that must be scanned and up to 72% savings in overall scan time, compared to naively applying file-based scanning approaches. Furthermore, SEER provides a 50% reduction in scan time when using a warm cache. In doing so, SEER provides a practical solution for cloud vendors to transparently and periodically scan virtual machine memory for malware.

The industry has been looking for a trustworthy mobile platform as smart phones and tablets are increasingly a part of people's daily life. I was fortunate to join the Samsung KNOX team and lead the R&D engineers to build the Samsung KNOX platform for mobile devices. As one of the most trusted mobile platforms today, Samsung KNOX has won a number of recognitions for its security features, such as US DoD STIG, Common Criteria MDFPP certification, and UK Government CESG EUD Guidance. In this talk, we will present some key KNOX features, such as SE Android, application container, and TIMA features such as trusted boot, remote attestation, key store, Client Certificate Manager (CCM), and real-time kernel protection.

TrustZone-based Real-time Kernel Protection (TZ-RKP) is a novel system that provides real-time protection of the OS kernel using the ARM TrustZone secure world. TZ-RKP is more secure than current approaches that use hypervisors to host kernel protection tools. Although hypervisors provide privilege and isolation, they face fundamental security challenges due to their growing complexity and code size. TZ-RKP puts its security monitor, which represents its entire Trusted Computing Base (TCB), in the TrustZone secure world; a safe isolated environment that is dedicated to security services. Hence, the security monitor is safe from attacks that can potentially compromise the kernel, which runs in the normal world. Using the secure world for kernel protection has been crippled by the lack of control over targets that run in the normal world. TZ-RKP solves this prominent challenge using novel techniques that deprive the normal world from the ability to control certain privileged system functions. These functions are forced to route through the secure world for inspection and approval before being executed. TZ-RKP's control of the normal world is non-bypassable. It can effectively stop attacks that aim at modifying or injecting kernel binaries. It can also stop attacks that involve modifying the system memory layout, e.g, through memory double mapping. This paper presents the implementation and evaluation of TZ-RKP, which has gone through rigorous and thorough evaluation of effectiveness and performance. It is currently deployed on the latest models of the Samsung Galaxy series smart phones and tablets, which clearly demonstrates that it is a practical real-world system.

Hadoop is a map-reduce implementation that rapidly processes data in parallel. Cloud provides reliability, flexibility, scalability, elasticity and cost saving to customers. Moving Hadoop into Cloud can be beneficial to Hadoop users. However, Hadoop has two vulnerabilities that can dramatically impact its security in a Cloud. The vulnerabilities are its overloaded authentication key, and the lack of fine-grained access control at the data access level. We propose and develop a security enhancement for Cloud-based Hadoop.

Recent years have witnessed incredible popularity and adoption of smartphones and mobile devices, which is accompanied by large amount and wide variety of feature-rich smartphone applications. These smartphone applications (or apps), typically organized in different application marketplaces, can be conveniently browsed by mobile users and then simply clicked to install on a variety of mobile devices. In practice, besides the official marketplaces from platform vendors (e.g., Google and Apple), a number of third-party alternative marketplaces have also been created to host thousands of apps (e.g., to meet regional or localization needs). To maintain and foster a hygienic smartphone app ecosystem, there is a need for each third-party marketplace to offer quality apps to mobile users.In this paper, we perform a systematic study on six popular Android-based third-party marketplaces. Among them, we find a common "in-the-wild" practice of repackaging legitimate apps (from the official Android Market) and distributing repackaged ones via third-party marketplaces. To better understand the extent of such practice, we implement an app similarity measurement system called DroidMOSS that applies a fuzzy hashing technique to effectively localize and detect the changes from app-repackaging behavior. The experiments with DroidMOSS show a worrisome fact that 5% to 13% of apps hosted on these studied marketplaces are repackaged. Further manual investigation indicates that these repackaged apps are mainly used to replace existing in-app advertisements or embed new ones to "steal" or re-route ad revenues. We also identify a few cases with planted backdoors or malicious payloads among repackaged apps. The results call for the need of a rigorous vetting process for better regulation of third-party smartphone application marketplaces.

SICE is a novel framework to provide hardware-level isolation and protection for sensitive workloads running on x86 platforms in compute clouds. Unlike existing isolation techniques, SICE does not rely on any software component in the host environment (i.e., an OS or a hypervisor). Instead, the security of the isolated environments is guaranteed by a trusted computing base that only includes the hardware, the BIOS, and the System Management Mode (SMM). SICE provides fast context switching to and from an isolated environment, allowing isolated workloads to time-share the physical platform with untrusted workloads. Moreover, SICE supports a large range (up to 4GB) of isolated memory. Finally, the most unique feature of SICE is the use of multicore processors to allow the isolated environments to run concurrently and yet securely beside the untrusted host. We have implemented a SICE prototype using an AMD x86 hardware platform. Our experiments show that SICE performs fast context switching (67 microseconds) to and from the isolated environment and that it imposes a reasonable overhead (3% on all but one benchmark) on the operation of an isolated Linux virtual machine. Our prototype demonstrates that, subject to a careful security review of the BIOS software and the SMM hardware implementation, current hardware architecture already provides abstractions that can support building strong isolation mechanisms using a very small SMM software foundation of about 300 lines of code.

Wireless link signature is a physical layer authentication mechanism, which uses the multi-path effect between a transmitter and a receiver to provide authentication of wireless signals. We identify a new attack, called mimicry attack, against the wireless link signature scheme in [7]. It is assumed in the past that an attacker cannot "spoof" an arbitrary link signature and that the attacker will not have the same link signature at the receiver unless it is at exactly the same location as the legitimate transmitter. However, we show that an attacker can forge an arbitrary link signature as long as it knows the legitimate signal at the receiver's location, and the attacker does not have to be at exactly the same location as the legitimate transmitter in order to forge its link signature.

Patching is a critical security service that keeps computer systems up to date and defends against security threats. Existing patching systems all require running systems. With the increasing adoption of virtualization and cloud computing services, there is a growing number of dormant virtual machine (VM) images. Such VM images cannot benefit from existing patching systems, and thus are often left vulnerable to emerging security threats. It is possible to bring VM images online, apply patches, and capture the VMs back to dormant images. However, such approaches suffer from unpredictability, performance challenges, and high operational costs, particularly in large-scale compute clouds where there could be thousands of dormant VM images.This paper presents a novel tool named Nuwa that enables efficient and scalable offline patching of dormant VM images. Nuwa analyzes patches and, when possible, converts them into patches that can be applied offline by rewriting the patching scripts. Nuwa also leverages the VM image manipulation technologies offered by the Mirage image library to provide an efficient and scalable way to patch VM images in batch. Nuwa has been evaluated on freshly built images and on real-world images from the IBM Research Compute Cloud (RC2), a compute cloud used by IBM researchers worldwide. When applying security patches to a fresh installation of Ubuntu-8.04, Nuwa successfully applies 402 of 406 patches. It speeds up the patching process by more than 4 times compared to the online approach and by another 2--10 times when integrated with Mirage. Nuwa also successfully applies the 10 latest security updates to all VM images in RC2.

This paper presents HyperSentry, a novel framework to enable integrity measurement of a running hypervisor (or any other highest privileged software layer on a system). Unlike existing solutions for protecting privileged software, HyperSentry does not introduce a higher privileged software layer below the integrity measurement target, which could start another race with malicious attackers in obtaining the highest privilege in the system. Instead, HyperSentry introduces a software component that is properly isolated from the hypervisor to enable stealthy and in-context measurement of the runtime integrity of the hypervisor. While stealthiness is necessary to ensure that a compromised hypervisor does not have a chance to hide the attack traces upon detecting an up-coming measurement, in-context measurement is necessary to retrieve all the needed inputs for a successful integrity measurement.HyperSentry uses an out-of-band channel (e.g., Intelligent Platform Management Interface (IPMI), which is commonly available on server platforms) to trigger the stealthy measurement, and adopts the System Management Mode (SMM) to protect its base code and critical data. A key contribution of HyperSentry is the set of novel techniques that overcome SMM's limitation, providing an integrity measurement agent with (1) the same contextual information available to the hypervisor, (2) completely protected execution, and (3) attestation to its output. To evaluate HyperSentry, we implement a prototype of the framework along with an integrity measurement agent for the Xen hypervisor. Our experimental evaluation shows that HyperSentry is a low-overhead practical solution for real world systems.

Cloud computing is revolutionizing how information technology resources and services are used and managed but the revolution comes with new security problems. Among these is the problem of securely managing the virtual-machine images that encapsulate each application of the cloud. These images must have high integrity because the initial state of every virtual machine in the cloud is determined by some image. However, as some of the enefits of the cloud depend on users employing images built by third parties, users must also be able to share images safely.This paper explains the new risks that face administrators and users (both image publishers and image retrievers) of a cloud's image repository. To address those risks, we propose an image management system that controls access to images, tracks the provenance of images, and provides users and administrators with efficient image filters and scanners that detect and repair security violations. Filters and scanners achieve efficiency by exploiting redundancy among images; an early implementation of the system shows that this approach scales better than a naive approach that treats each image independently.

Kernel rootkits have posed serious security threats due to their stealthy manner. To hide their presence and activities, many rootkits hijack control flows by modifying control data or hooks in the kernel space. A critical step towards eliminating rootkits is to protect such hooks from being hijacked. However, it remains a challenge because there exist a large number of widely-scattered kernel hooks and many of them could be dynamically allocated from kernel heap and co-located together with other kernel data. In addition, there is a lack of flexible commodity hardware support, leading to the socalled protection granularity gap -- kernel hook protection requires byte-level granularity but commodity hardware only provides page level protection.To address the above challenges, in this paper, we present HookSafe, a hypervisor-based lightweight system that can protect thousands of kernel hooks in a guest OS from being hijacked. One key observation behind our approach is that a kernel hook, once initialized, may be frequently "read"-accessed, but rarely write"-accessed. As such, we can relocate those kernel hooks to a dedicated page-aligned memory space and then regulate accesses to them with hardware-based page-level protection. We have developed a prototype of HookSafe and used it to protect more than 5,900 kernel hooks in a Linux guest. Our experiments with nine real-world rootkits show that HookSafe can effectively defeat their attempts to hijack kernel hooks. We also show that HookSafe achieves such a large-scale protection with a small overhead (e.g., around 6% slowdown in performance benchmarks).

Recent studies have demonstrated that it is possible to perform public key cryptographic operations on the resource-constrained sensor platforms. However, the significant resource consumption imposed by public key cryptographic operations makes such mechanisms easy targets of Denial- of Service (DoS) attacks. For example, if digital signatures such as ECDSA are used directly for broadcast authentication without further protection, an attacker can simply broadcast forged packets and force the receiving nodes to perform a large number of unnecessary signature verifications, eventually exhausting their battery power. This paper studies how to deal with such DoS attacks when signatures are used for broadcast authentication in sensor networks. In particular, this paper presents two filtering techniques, a group-based filter and a key chain-based filter, to handle DoS attacks against signature verification. Both methods can significantly reduce the number of unnecessary signature verifications that a sensor node has to perform. The analytical results also show that these two techniques are efficient and effective for resource-constrained sensor networks.

Software vulnerabilities have been the main contributing factor to the Internet security problems such as fast spreading worms. Among these software vulnerabilities, memory corruption vulnerabilities such as buffer overflow and format string bugs have been the most common ones exploited by network-based attacks. Many security countermeasures (e.g., patching, automatic signature generation for intrusion detection systems) require vulnerability information to function correctly. However, despite many years of research, automatically identifying unknown software vulnerabilities still remains an open problem.In this paper, we present the development of a security debugging tool named MemSherlock, which can automatically identify unknown memory corruption vulnerabilities upon the detection of malicious payloads that exploit such vulnerabilities. MemSherlock provides critical information for unknown memory corruption vulnerabilities, including (1) the corruption point in the source code (i.e., the statement that allows the exploitation of memory corruption vulnerability), (2) the slice of source code that helps the malicious input to reach the corruption point, and (3) the description of how the malicious input exploits the unknown vulnerability. We evaluate MemSherlock with a set of 11 real-world applications that have buffer overflow, heap overflow, and format string vulnerabilities. The evaluation results indicate that MemSherlock is a useful tool to facilitate the automatic vulnerability analysis process.

Broadcast authentication is an important application in sensor networks. Public Key Cryptography (PKC) is desirable for this application, but due to the resource constraints on sensor nodes, these operations are expensive, which means sensor networks using PKC are susceptible to Denial of Service (DoS) attacks: attackers keep broadcasting bogus messages, which will incur extra costs, thus exhaust the energy of the honest nodes. In addition, the long time to verify each message using PKC increases the response time of the nodes; it is impractical for the nodes to validate each incoming message before forwarding i.In this paper we discuss this type of DoS attacks, in which the goal of the adversary is to exhaust the energy of the sensor nodes and to increase their response time to broadcast messages. We then present a dynamic window scheme, where sensor nodes determine whether first to verify a message or first to forward the message by themselves. This is made possible with the information such as how far this node is away from the malicious attacker, and how many hops the incoming message has passed. We compare the performance of the proposed scheme with other schemes, and show that it can contain the damage of DoS attacks to only a small portion of the sensor nodes.

Remotely-launched software exploits are a common way for attackers to intrude into vulnerable computer systems. As detection techniques improve, remote exploitation techniques are also evolving. Recent techniques for evasion of exploit detection include polymorphism (code encryption) and meta-morphism (code obfuscation). This paper addresses the problem of detecting in network traffic polymorphic remote exploits that are encrypted, and that self-decrypt before launching the intrusion. Such exploits pose a great challenge to existing malware detection techniques, partly due to the non-obvious starting location of the exploit code in the network payload.We describe a new method for detecting self-decrypting exploit codes. This method scans network traffic for the presence of a decryption routine, which is characteristic of such exploits. The proposed method uses static analysis and emulated instruction execution techniques. This improves the accuracy of determining the starting location and instructions of the decryption routine, even if self-modifying code is used. The method outperforms approaches that have been previously proposed, both in terms of detection capabilities, and in detection accuracy.The proposed method has been implemented and tested on current polymorphic exploits, including ones generated by state-of-the-art polymorphic engines. All exploits have been detected (i.e., a 100% detection rate), including those for which the decryption routine is dynamically coded, or self-modifying. The false positive rate is close to 0%. Running time is approximately linear in the size of the network payload being analyzed.

Anonymity is increasingly important for network applications concerning about censorship and privacy. The existing anonymous communication protocols generally stem from mixnet and DC-net. They either cannot provide provable anonymity or suffer from transmission collision. In this paper, we introduce a novel approach which takes advantage of hierarchical ring structure and mix technique. This proposed protocol is collision free and provides provable k-anonymity for both the sender and the recipient, even if a polynomial time adversary can eavesdrop all network traffic and control a fraction of participants. Furthermore, it can hide the sender and the recipient from each other and thus can be used for anonymous file sharing. The analysis shows the proposed protocol is secure against various attacks. Measurements further demonstrate it is practical.

Accurate and synchronized time is crucial in many sensor network applications due to the need for consistent distributed sensing and coordination. In hostile environments where an adversary may attack the networks and/or the applications through external or compromised nodes, time synchronization becomes an attractive target due to its importance. This paper describes the design, implementation, and evaluation of TinySeRSync, a secure and resilient time synchronization subsystem for wireless sensor networks running TinyOS. This paper makes three contributions: First, it develops a secure single-hop pairwise time synchronization technique using hardware-assisted, authenticated medium access control (MAC) layer timestamping. Unlike the previous attempts, this technique can handle high data rate such as those produced by MICAz motes (in contrast to those by MICA2 motes). Second, this paper develops a secure and resilient global time synchronization protocol based on a novel use of the μTESLA broadcast authentication protocol for local authenticated broadcast, resolving the conflict between the goal of achieving time synchronization with μTESLA-based broadcast authentication and the fact that μTESLA requires loose time synchronization. The resulting protocol is secure against external attacks and resilient against compromised nodes. The third contribution consists of an implementation of the proposed techniques on MICAz motes running TinyOS and a thorough evaluation through field experiments in a network of 60 MICAz motes.

Cyber attacks against networked computers have become relentless in recent years. The most common attack method is to exploit memory corruption vulnerabilities such as buffer overflow and format string bugs. This paper presents a technique to automatically identify both known and unknown memory corruption vulnerabilities. Based on the observation that a randomized program usually crashes upon a memory corruption attack, this technique uses the crash as a trigger to initiate an automatic diagnosis algorithm. The output of the diagnosis includes the instruction that is tricked to corrupt data, the call stack at the time of corruption, and the propagation history of corrupted data. These results provide useful information in fixing the vulnerabilities. Moreover, the diagnosis process also generates a signature of the attack using data/address values embedded in the malicious input message, and is used to block future attacks. Such a signature is further associated with the program execution state to reduce false positives without decreasing the detection rate. The proposed techniques enable the development of a decentralized self-diagnosing and self-protecting defense mechanism for networked computers. We report the implementation experience and experimental evaluation of a prototype system on Linux.

Many key pre-distribution techniques have been developed recently to establish pairwise keys for wireless sensor networks. To further improve these schemes, researchers have proposed to take advantage of sensors' expected locations to help pre-distributing keying materials. However, it is usually very difficult, and sometimes impossible, to guarantee the knowledge of sensors' expected locations. In order to remove the dependency on expected locations, this paper proposes a practical deployment model, where sensor nodes are deployed in groups, and the nodes in the same group are close to each other after the deployment. Based on this model, the paper develops a novel group-based key pre-distribution framework, which can be combined with any of existing key pre-distribution techniques. A distinguishing property of this framework is that it does not require the knowledge of sensors' expected locations and greatly simplifies the deployment of sensor networks. The analysis also shows that the framework can substantially improve the security as well as the performance of existing key pre-distribution techniques.

With the advance of technology, Public Key Cryptography (PKC) will sooner or later be widely used in wireless sensor networks. Recently, it has been shown that the performance of some public-key algorithms, such as Elliptic Curve Cryptography (ECC), is already close to being practical on sensor nodes. However, the energy consumption of PKC is still expensive, especially compared to symmetric-key algorithms. To maximize the lifetime of batteries, we should minimize the use of PKC whenever possible in sensor networks.This paper investigates how to replace one of the important PKC operations--the public key authentication--with symmetric key operations that are much more efficient. Public key authentication is to verify the authenticity of another party's public key to make sure that the public key is really owned by the person it is claimed to belong to. In PKC, this operation involves an expensive signature verification on a certificate. We propose an efficient alternative that uses one-way hash function only. Our scheme uses all sensor's public keys to construct a forest of Merkle trees of different heights. By optimally selecting the height of each tree, we can minimize the computation and communication costs. The performance of our scheme is evaluated in the paper.

Sensor networks are ideal candidates for applications such as target tracking and environment monitoring. Security in sensor networks is critical when there are potential adversaries. Establishment of pairwise keys is a fundamental security service, which forms the basis of other security services such as authentication and encryption. However, establishing pairwise keys in sensor networks is not a trivial task, particularly due to the resource constraints on sensors. This paper presents several techniques for establishing pairwise keys in static sensor networks. These techniques take advantage of the observation that in static sensor networks, although it is difficult to precisely pinpoint sensors' positions, it is often possible to approximately determine their locations. This paper presents a simple location-aware deployment model, and develops two pairwise key predistribution schemes, a closest pairwise keys predistribution scheme and a location-based pairwise keys scheme using bivariate polynomials, by taking advantage of sensors' expected locations. The analysis in this paper indicates that these schemes can achieve better performance if such location information is available and that the smaller the deployment error (i.e., the difference between a sensor's actual location and its expected location) is, the better performance they can achieve.

This paper presents group key distribution techniques for large and dynamic groups over unreliable channels. The techniques proposed here are based on the self-healing key distribution methods (with revocation capability) recently developed by Staddon et al. [27]. By introducing a novel personal key distribution technique, this paper reduces (1) the communication overhead of personal key share distribution from O(t2log q) to O(tlogq), (2) the communication overhead of self-healing key distribution with t-revocation capability from O((mt2+tm)log q) to O(mtlog q), and (3) the storage overhead of the self-healing key distribution with $t$-revocation capability at each group member from O(m2log q) to O(mlogq), where $t$ is the maximum number of colluding group members, $m$ is the number of sessions, and $q$ is a prime number that is large enough to accommodate a cryptographic key. All these results are achieved without sacrificing the unconditional security of key distribution. In addition, this paper presents two techniques that allow trade-off between the broadcast size and the recoverability of lost session keys. These two methods further reduce the broadcast message size in situations where there are frequent but short-term disruptions of communication and where there are long-term but infrequent disruptions of communication, respectively.

Understanding strategies of attacks is crucial for security applications such as computer and network forensics, intrusion response, and prevention of future attacks. This paper presents techniques to automatically learn attack strategies from correlated intrusion alerts. Central to these techniques is a model that represents an attack strategy as a graph of attacks with constraints on the attack attributes and the temporal order among these attacks. To learn the intrusion strategy is then to extract such a graph from a sequences of intrusion alerts. To further facilitate the analysis of attack strategies, which is essential to many security applications such as computer and network forensics, this paper presents techniques to measure the similarity between attack strategies. The basic idea is to reduces the similarity measurement of attack strategies into error-tolerant graph/subgraph isomorphism problem, and measures the similarity between attack strategies in terms of the cost to transform one strategy into another. Finally, this paper presents some experimental results, which demonstrate the potential of the proposed techniques.

Traditional intrusion detection systems (IDSs) focus on low-level attacks or anomalies, and raise alerts independently, though there may be logical connections between them. In situations where there are intensive intrusions, not only will actual alerts be mixed with false alerts, but the amount of alerts will also become unmanageable. As a result, it is difficult for human users or intrusion response systems to understand the alerts and take appropriate actions. This paper presents a practical technique to address this issue. The proposed approach constructs attack scenarios by correlating alerts on the basis of prerequisites and consequences of intrusions. Intuitively, the prerequisite of an intrusion is the necessary condition for the intrusion to be successful, while the consequence of an intrusion is the possible outcome of the intrusion. Based on the prerequisites and consequences of different types of attacks, the proposed approach correlates alerts by (partially) matching the consequence of some previous alerts and the prerequisite of some later ones. The contribution of this paper includes a formal framework for alert correlation, the implementation of an off-line alert correlator based on the framework, and the evaluation of our method with the 2000 DARPA intrusion detection scenario specific datasets. Our experience and experimental results have demonstrated the potential of the proposed method and its advantage over alternative methods.