Attack Grammar: A New Approach to Modeling and Analyzing Network Attack Sequences

Attack graphs have been used to show multiple attack paths in large scale networks. They have been proved to be useful utilities for network hardening and penetration testing. However, the basic concept of using graphs to represent attack paths has limitations. In this paper, we propose a new approach, the attack grammar, to model and analyze network attack sequences. Attack grammars are superior in the following areas: First, attack grammars express the interdependency of vulnerabilities better than attack graphs. They are especially suitable for the IDS alerts correlation. Second, the attack grammar can serve as a compact representation of attack graphs and can be converted to the latter easily. Third, the attack grammar is a context-free grammar. Its logical formality makes it better comprehended and more easily analyzed. Finally, the algorithmic complexity of our attack grammar approach is quartic with respect to the number of host clusters, and analyses based on the attack grammar have a run time linear to the length of the grammar, which is quadratic to the number of host clusters.