Improving Signature Testing Through Dynamic Data Flow AnalysisChristopher KruegelTechnical University [email protected] Balzarotti, William Robertson, Giovanni VignaUniversity of California, Santa Barbarabalzarot,wkr,[email protected] effectiveness and precision of network-based intru-sion detection signatures can be evaluated either by di-rect analysis of the signatures (if they are available) orby using black-box testing (if the system is closed-source).Recently, several techniques have been proposed to gen-erate test cases by automatically deriving variations (ormutations) of attacks. Even though these techniques havebeen useful in identifying “blind spots” in the signatures ofclosed-source, network-based intrusion detection systems,the generation of test cases is performed in a random, un-guided fashion. The reason is that there is no informationavailable about the signatures to be tested. As a result,identifying a test case that is able to evade detection is dif-ficult.In this paper, we propose a novel approach to drive thegeneration of test cases by using the information gatheredby analyzing the dynamic behavior of the intrusion detec-tion system. Our approach applies dynamic data flow anal-ysis techniques to the intrusion detection system to identifywhich parts of a network stream are used to detect an at-tack and how these parts are matched by a signature. Theresult of our analysis is a set of constraints that is used toguide the black-box testing process, so that the mutationsare applied to only those parts of the attack that are rele-vant for detection. By doing this, we are able to performa more focused generation of the test cases and improvethe process of identifying an attack variation that evadesdetection.1. IntroductionIntrusion detection systems (IDSs) can be broadly di-vided into two classes: those that rely on models of nor-mal behavior and detect deviations from these models (i.e.,anomaly-based systems), and those that contain descrip-tions of malicious behavior and detect events (or sequencesof events) that match these descriptions (i.e., signature-based systems). While both classes of intrusion detectionsystems have complementary strengths, they are both vul-nerable to evasion attacks.In the case of anomaly-based systems, evasion tech-niques are used to craft an exploit so that it resembles nor-mal behavior. The application of these techniques is usu-ally called a mimicry attack [30]. In the case of signature-based systems, evasion techniques are used to modify anexploit so that it does not match any of the signatures usedby the intrusion detection system, while retaining the abil-ity to compromise the security of the target system [20].Recently, a number of approaches [4, 13, 16, 18, 22, 23,29] have been proposed to test the effectiveness and preci-sion of network-based intrusion detection systems. In par-ticular, approaches based on the generation of test cases byautomatically deriving variations (or mutations) of knownexploits have been shown to be able to identify problemsin the detection mechanisms used by both open-sourceand commercial, state-of-the-art systems [13, 29]. Theseapproaches leverage a number of transformations, called“mutant operators”, that are applied to an exploit template.The goal of applying these mutation operators is to obtaina modified version that has a different network manifesta-tion with respect to the original attack, but it is still able tocompromise a vulnerable target.Mutant operators can work at different levels of abstrac-tion (e.g., at the network level or at the application level),and they can be composed and/or applied multiple times.For example, consider a first mutant operator that addseffect-free commands to an FTP session (e.g., adds a “CWD.” or a “NOOP” command) and a second one that appliesfragmentation to the IP traffic. The first operator can be ap-plied multiple times to an FTP-based exploit template with-out invalidating the attack (unless, of course, the length ofthe session affects the success of the exploit), while the sec-ond one can be applied in different ways (e.g., by specify-ing different fragment sizes). Thus, the number of possiblevariations of the original exploit that can be used as testcases quickly grows very large.In current approaches, the generation of test cases is ei-ther manually guided or a random process. In the formercase, a human expert selects which operators to apply tothe exploit template and which parameters to use for eachoperator. The results obtained by running the selected testcases might provide hints on how to select the operatorsand their parameters in the next round of tests. In the lat-ter case, the operators (and the values of their parameters)are selected randomly. Both these approaches are less thanoptimal because they either require extensive expert knowl-edge or represent “shots in the dark.” Therefore, there is theneed for a new technique for testing network-based signa-tures that is both automated and more focused than a purelyrandom approach. In theory, some guidance about how togenerate the relevant test cases can be derived from the sig-natures themselves. For example, by looking at which fea-tures of the network traffic are analyzed by a signature, it ispossible to focus the test case generation by using only themutant operators that affect those features. Unfortunately,most intrusion detection system vendors do not make theirsignatures available because they consider them to be theirintellectual property and an advantage with respect to theircompetitors. Thus, in general, one cannot rely on the avail-ability of the signatures to guide the generation of the testcases.To address this problem, we propose a novel approachto drive the generation of test cases based on the analysisof the dynamic behavior of a network-based intrusion de-tection system. As a first step, we apply dynamic data flowanalysis techniques to the NIDS binary to determine whichparts of the attack trace are checked by the NIDS. We thenleverage this information to restrict the test case generationprocess to only use the mutant operators that modify therelevant parts of the attack.Based on the knowledge of which parts of a networktrace are considered by the detection process, we furtherrefine our analysis to also take into account how these partsare used. For simple checks (e.g., the comparison of asource port number with an integer constant),