Alert-driven Attack Graph Generation using S-PDFA

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

Research output: Contribution to journalArticleScientificpeer-review

6 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
Number of pages16
JournalIEEE Transactions on Dependable and Secure Computing
Publication statusE-pub ahead of print - 2021


  • 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