## On the Completeness of Attack Mutation Algorithms

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 , an algorithm is
complete with respect to , if it can generate every instance
that the transformations in derive. We show that if the
rules in 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 .
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.

*Download:*[PS,PDF]

Somesh Jha
Last modified: Fri Sep 22 16:54:42 CDT 2006