Formalizing Attack Mutation for NIDS Testing

Abstract

Attack mutation is a common way to test a misuse Network Intrusion Detection System (NIDS). In this technique, a known instance of an attack is transformed by repeatedly applying attack transformations into many distinct instances. For example, we cangenerate many instances of an HTTP attack by splitting it into TCP segments in many different ways. The underlying intuition behind attack mutation is that many attack instances are derivable from a few simple exemplary instances. We formally justify the intuition behind attack mutation. We prove that for many transformations, all mutations of an attack are derivable from each other. Furthermore, we show that all mutations can be derived from a few atoms which are the simplest versions of the attack. Based on our findings, we developed two algorithms: testing and forensics. Given a set of transformations, our testing algorithm derives all attack mutations (up to a certain length) from an exemplary attack instance. Our forensics algorithm complements the testing one; it determines whether two mutations are derivable from each other. Our algorithms accommodate most of the known transformations, so the algorithms can be immediately integrated into existing NIDS testing tools.