Christopher Kruegel
Technical University Vienna
Austria

Davide Balzarotti
UC Santa Barbara
USA

William Robertson
UC Santa Barbara
USA

Giovanni Vigna
UC Santa Barbara
USA

The effectiveness and precision of network-based intrusion detection signatures can be evaluated either by direct analysis of the signatures (if they are available) or by using black-box testing (if the system is closed-source). Recently, several techniques have been proposed to generate test cases by automatically deriving variations (or mutations) of attacks. Even though these techniques have been useful in identifying ``blind spots'' in the signatures of closed-source, network-based intrusion detection systems, the generation of test cases is performed in a random, unguided fashion. The reason is that there is no information available about the signatures to be tested. As a result, identifying a test case that is able to evade detection is difficult.

In this paper, we propose a novel approach to drive the generation of test cases by using the information gathered by analyzing the dynamic behavior of the intrusion detection system. Our approach applies dynamic data flow analysis techniques to the intrusion detection system to identify which parts of a network stream are used to detect an attack. In addition, we can determine how these parts are matched by a signature. The result of our analysis is a set of constraints that is used to guide the black-box testing process so that the mutations are applied to only those parts of the attack that are relevant for detection. By doing this, we are able to perform a more focused generation of the test cases and improve the process of identifying an attack variation that evades detection.

Keywords: Evasion, dynamic analysis, binary analysis, attack mutations

Read Paper (in PDF)