Alert-driven Attack Graph Generation using S-PDFA

A. Nadeem, S.E. Verwer, Stephen Moskal, Shanchieh Jay Yang

Research output: Contribution to journalArticlepeer-review

40 Downloads (Pure)


Ideal cyber threat intelligence (CTI) includes insights into attacker strategies that are specific to a network under observation. Such CTI currently requires extensive expert input for obtaining, assessing, and correlating system vulnerabilities into a graphical representation, often referred to as an attack graph (AG). Instead of deriving AGs based on system vulnerabilities, this work advocates the direct use of intrusion alerts. We propose SAGE, an explainable sequence learning pipeline that automatically constructs AGs from intrusion alerts without a priori expert knowledge. SAGE exploits the temporal and probabilistic dependence between alerts in a suffix-based probabilistic deterministic finite automaton (S-PDFA) — a model that brings infrequent severe alerts into the spotlight and summarizes paths leading to them. Attack graphs are extracted from the model on a per-victim, per-objective basis. SAGE is thoroughly evaluated on three open-source intrusion alert datasets collected through security testing competitions in order to analyze distributed multi-stage attacks. SAGE compresses over 330k alerts into 93 AGs that show how specific attacks transpired. The AGs are succinct, interpretable, and provide directly relevant insights into strategic differences and fingerprintable paths. They even show that attackers tend to follow shorter paths after they have discovered a longer one in 84.5% of the cases.
Original languageEnglish
Pages (from-to)731-746
Number of pages16
JournalIEEE Transactions on Dependable and Secure Computing
Issue number2
Publication statusPublished - 2022

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project

Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.


  • Alert-driven attack graphs
  • Explainable machine learning
  • Suffix automaton model
  • Attacker strategy
  • Intrusion alerts


Dive into the research topics of 'Alert-driven Attack Graph Generation using S-PDFA'. Together they form a unique fingerprint.

Cite this