Robust Attack Graphs

Abstract

Every day, Intrusion Detection Systems around the world generate huge amounts of data. This data can be used to learn attacker behaviour, such as Techniques, Tactics, and Procedures (TTPs). Attack Graphs (AGs) provide a visual way of describing these attack patterns. They can be generated without expert knowledge and vulnerability reports. The goal of AGs is to reduce alert fatigue, and to give another perspective on attacker behaviour.
SAGE, the state-of-the-art method for generating AGs uses FlexFringe's state merging algorithms to learn the underlying state machine to model these attacks. A big challenge of these state merging algorithms is learning infrequent behaviour. Next to that, the underlying state machines cannot deal with noisy input data.
In this work, a sequence-automaton alignment algorithm is used to align sequences of states to a state machine. Our method iteratively aligns infrequent sequences to the model, effectively learning both frequent and infrequent behaviour.
The method is evaluated on a security competition dataset, where experiments show that the algorithm is able to recover from noise such as added or removed events. The learned models are also reduced to half its original size, while better fitting to the training data.
Last, we show how our method can be used to learn the model of an anomaly detection dataset. The test data is predicted using three anomaly conditions, and results in all anomalous data being labelled correctly. The F1-score is competitive compared to other state of the art methods.