Before performing pattern matching, a typical misuse-NIDS performs protocol analysis: it parses network traffic according to the attack protocol and normalizes the traffic into the form used by its signatures. For example, consider a NIDS that attempts to identify an HTTP-based attack. The NIDS must extract the URL from the raw traffic, convert HEX encoded characters into their equivalent ASCII form if necessary, and only then perform matching on the normalized URL. Protocol analysis is time consuming, especially in a NIDS that analyzes and normalizes all traffic just to discover that the majority of the traffic does not match any of its signatures.We develop a technique called protomatching that combines protocol analysis, normalization, and pattern matching into a single phase. The goal of the protomatching signatures is to exclude non-attack traffic quickly before the NIDS performs any further time-consuming analysis. Protomatching is based on a novel signature with two properties. First, the signature ensures that the attack pattern appears in the context that enables successful attack. This saves the need for protocol analysis. Second, the signature matches both encoded and normalized forms of an attack and this saves the need for normalization.We empirically show that a Snort implementation that uses protomatching is up to 49% faster than an unmodified Snort.

An attack mutation algorithm takes a known instance of an attack and transforms it into many distinct instances by repeatedly applying attack transformations. Such algorithms are widely used for testing intrusion detection systems. We investigate the notion of completeness of a mutation algorithm: its capability to generate all possible attack instances from a given set of attack transformations. We define the notion of a Phi-complete mutation algorithm. Given a set of transformations Phi, an algorithm is complete with respect to Phi, if it can generate every instance that the transformations in Phi derive. We show that if the rules in Phi are uniform and reversible then a Phi-complete algorithm exists. Intuitively speaking, uniform and reversible transformations mean that we can first exclusively apply transformations that simplify the attack, then exclusively apply transformations that complicate it, and still get all possible instances that are derived by the rules in Phi. Although uniformity and reversibility may appear severe restrictions, we show that common attack transformations are indeed uniform and reversible. Therefore, our Phi-complete algorithm can be incorporated into existing testing tools for intrusion detection systems. Furthermore, we show that a Phi-complete algorithm is useful, not only for testing purposes, but also for determining whether two packet traces are two different mutations of the same attack

Existing reputation systems used by online auction houses do not address the concern of a buyer shopping for commodities - finding a good bargain. These systems do not provide information on the practices adopted by sellers to ensure profitable auctions. These practices may be legitimate, like imposing a minimum starting bid on an auction, or fraudulent, like using colluding bidders to inflate the final price in a practice known as shilling.We develop a reputation system to help buyers identify sellers whose auctions seem price-inflated. Our reputation system is based upon models that characterize sellers according to statistical metrics related to price inflation. We combine the statistical models with anomaly detection techniques to identify the set of suspicious sellers. The output of our reputation system is a set of values for each seller representing the confidence with which the system can say that the auctions of the seller are price-inflated.We evaluate our reputation system on 604 high-volume sellers who posted 37,525 auctions on eBay. Our system automatically pinpoints sellers whose auctions contain potential shill bidders. When we manually analyze these sellers' auctions, we find that many winning bids are at about the items' market values, thus undercutting a buyer's ability to find a bargain and demonstrating the effectiveness of our reputation system.

We present a methodology to automatically construct robust signatures whose accuracy is based on formal reasoning so it can be systematically evaluated. Our methodology is based on two formal languages that describe different properties of a given attack. The first language, called a session signature, describes temporal relations between the attack events. The second, called an attack invariant, describes semantic properties that hold in any instance of the attack. For example, an invariant may state that a given FTP attack must include a successful FTP login and can be launched only after the FTP representation mode has been set to ASCII. We iteratively eliminate false positives and negatives from an initial session signature by comparing the signature language to the language of the invariant. We developed GARD, a tool for session-signature construction, and used it to construct session signatures for multi-step attacks. We show that a session signature is more accurate than existing signatures.

A common way to elude a signature-based NIDS is to transform an attack instance that the NIDS recognizes into another instance that it misses. For example, to avoid matching the attack payload to a NIDS signature, attackers split the payload into several TCP packets or hide it between benign messages. We observe that different attack instances can be derived from each other using simple transformations. We model these transformations as inference rules in a natural-deduction system. Starting from an exemplary attack instance, we use an inference engine to automatically generate all possible instances derived by a set of rules. The result is a simple yet powerful tool capable of both generating attack instances for NIDS testing and determining whether a given sequence of packets is an attack. In several testing phases using different sets of rules, our tool exposed serious vulnerabilities in Snort - a widely deployed NIDS. Attackers acquainted with these vulnerabilities would have been able to construct instances that elude Snort for any TCP-based attack, any Web-CGI attack, and any attack whose signature is a certain type of regular expression.

Data-layout optimizations rearrange fields within objects, objects within objects, and objects within the heap, with the goal of increasing spatial locality. While the importance of data-layout optimizations has been growing, their deployment has been limited, partly because they lack a unifying framework. We propose a parameterizable framework for data-layout optimization of general-purpose applications. Acknowledging that finding an optimal layout is not only NP-hard, but also poorly approximable, our framework finds a good layout by searching the space of possible layouts, with the help of profile feedback. The search process iteratively prototypes candidate data layouts, evaluating them by "simulating" the program on a representative trace of memory accesses. To make the search process practical, we develop space-reduction heuristics and optimize the expensive simulation via memoization. Equipped with this iterative approach, we can synthesize layouts that outperform existing non-iterative heuristics, tune application-specific memory allocators, as well as compose multiple data-layout optimizations.

Although some instructions hurt performance more than others, current processors typically apply scheduling and speculation as if each instruction was equally costly. Instruction cost can be naturally expressed through the critical path: if we could predict it at run-time, egalitarian policies could be replaced with cost-sensitive strategies that will grow increasingly effective as processors become more parallel. This paper introduces a hardware predictor of instruction criticality and uses it to improve performance. The predictor is both effective and simple in its hardware implementation. The effectiveness at improving performance stems from us-ing a dependence-graph model of the microarchitectural critical path that identifies execution bottlenecks by incorporating both data and machine-specific dependences. The simplicity stems from a token-passing algorithm that computes the critical path without actually building the dependence graph. By focusing processor policies on critical instructions, our predictor enables a large class of optimizations. It can (i) give priority to critical instructions for scarce resources (functional units, ports, predictor entries); and (ii) suppress speculation on non-critical instructions, thus reducing "useless" misspecula-tions. We present two case studies that illustrate the potential of the two types of optimization, we show that (i) critical-path-based dynamic instruction scheduling and steering in a clus-tered architecture improves performance by as much as 21% (10 % on average); and (ii) focusing value prediction only on critical instructions improves performance by as much as 5%, due to removing nearly half of the misspeculations.

Test-program generators play a key role in hardware functional verification of large scale processors. However, in the DSP domain, the usage of full-blown test-program generators is much less popular, mainly due to the limited resources (time and money) available when developing such systems. This paper describes a work-model for the fast, low cost construction of a test-program generator for DSPs. The core technology uses Genesys, a known test program generator that, until now, has been used for the verification of large scale processor families, such as PowerPC and x86. We developed the model while using Genesys for verification of the IBM C54XDSP, a fixed-point DSP. The case study shows that it is possible to build a full test-program generator in a very short time and thus achieve better verification coverage in spite of the shorter development time.