AGENT: Attack Generation for NIDS Testing

 

The problem: The goal of a Network Intrusion Detection System (NIDS) is to alert a system administrator each time an intruder tries to penetrate the network.   A misuse NIDS defines attacks via a table of malicious signatures:  if an ongoing activity matches a signature in the table, an alarm is raised.  Thousands of organizations depend upon such systems because they are simple to understand, enable administrators to customize the signature database, and provide concrete information about the events that have occurred.

 

Unfortunately, research and experience have shown that attackers can effectively elude almost any NIDS. Attackers can hide an attack in two fundamentals ways. First, they can change the way the attack is delivered, for example, by splitting the attack into many network packets. Second, they can alter the attack payload so that it no longer matches the NIDS signature, for example, by using a different encoding for URLs. Unlike analysts of security protocols, who use formal threat models to evaluate the resistance of a protocol against attacks, NIDS analysts carry out their evaluation using ad hoc methods and tools. We believe that improving NIDS robustness requires a formal threat model that exhaustively descries attackers’ capability to elude a NIDS.

 

Our approach: We observe that variants of the same attack can be methodically computed, or derived, from each other. We formalize this observation using natural deduction to define an attack derivation model. Our model comprises a set of transformation rules, each rule represents an atomic transformation the attacker can use to hide the attack signature, and an exemplary instance of the attack from which we derive all other instances using any combination of the rules.

 

Based on this formal model we built AGENT, which addresses two problems:

 

  1. The black hat problem: given a NIDS and an instance of an attack A, find an instance of A that evades the NIDS.
  2. The white hat problem (which is the problem that NIDS designers try to solve): given an instance of an attack A and a sequence of packets s, determine whether s is an instance of A.

 

AGENT is capable of handling the two problems. To deal with the black hat problem, AGENT uses the attack derivation model to generate attack instances and feeds these instances into the given NIDS until it finds one that is undetected. To deal with the white hat problem, AGENT uses the model to check whether the given instance matches one of the instances generated.

 

Availability: AGENT is available upon request.


People:

  1. Shai Rubin
  2. Somesh Jha
  3. Barton P. Miller

 

Publication:

 1. S. Rubin, S. Jha, and B. P. Miller. Automatic generation and analysis of NIDS attacks. In  the Annual Computer Security Applications Conference (Tucson, AZ, December 2004). (pdf). This paper won the Student Paper  Award and the Best Paper Award in ACSAC 2004.



Funding: