A multi-step attack pattern discovery method based on graph mining

One fundamental challenge for Alert Correlation(AC) is to learn attack strategies. Attack graph is one of the most commonly used models to describe attack patterns(strategies), however, attack graph generating technology is far from practical. There are two general approaches to generate attack graphs. The first uses graph based search technology to find the paths of possible attacks, such as model checking, assumes that the premises and consequences of the attacks are known. And the other makes use of statistical method, such as frequent sequence mining, try to find the relationship of attacks in the dimension of time. In this paper, we proposed a graph mining based approach to discover attack patterns for attack graph generating. Firstly, we propose a new structure ECG, and transform sequential events into ECG, in which their time sequential and space relations is reserved. Moreover, we propose a DAG mining algorithm to discovery the frequent graph patterns from the ECG, and finally transform the graph patterns into attack graph. Different to existing methods, our method finds relationship of attacks in the dimension of both time and space, so that it can detect attacks more concisely. The effectiveness and efficiency of the approach is validated by DARPA 1999, 2000 intrusion detection evaluation datasets. As far as we know, this is the first time to discover knowledge of attack based on graph mining.