Efficient Attack Graph Analysis through Approximate Inference. / Muñoz-González, Luis; Sgandurra, Daniele; Paudice, Andrea; Lupu, Emil.

In: ACM Transactions on Information and System Security, Vol. 20, No. 3, 10, 11.08.2017, p. 1-30.

Research output: Contribution to journalArticle

Published

Standard

Efficient Attack Graph Analysis through Approximate Inference. / Muñoz-González, Luis; Sgandurra, Daniele; Paudice, Andrea; Lupu, Emil.

In: ACM Transactions on Information and System Security, Vol. 20, No. 3, 10, 11.08.2017, p. 1-30.

Research output: Contribution to journalArticle

Harvard

Muñoz-González, L, Sgandurra, D, Paudice, A & Lupu, E 2017, 'Efficient Attack Graph Analysis through Approximate Inference', ACM Transactions on Information and System Security, vol. 20, no. 3, 10, pp. 1-30. https://doi.org/10.1145/3105760

APA

Muñoz-González, L., Sgandurra, D., Paudice, A., & Lupu, E. (2017). Efficient Attack Graph Analysis through Approximate Inference. ACM Transactions on Information and System Security, 20(3), 1-30. [10]. https://doi.org/10.1145/3105760

Vancouver

Muñoz-González L, Sgandurra D, Paudice A, Lupu E. Efficient Attack Graph Analysis through Approximate Inference. ACM Transactions on Information and System Security. 2017 Aug 11;20(3):1-30. 10. https://doi.org/10.1145/3105760

Author

Muñoz-González, Luis ; Sgandurra, Daniele ; Paudice, Andrea ; Lupu, Emil. / Efficient Attack Graph Analysis through Approximate Inference. In: ACM Transactions on Information and System Security. 2017 ; Vol. 20, No. 3. pp. 1-30.

BibTeX

@article{9d3c2cb7bc2a4d8a985b403c78b3664b,
title = "Efficient Attack Graph Analysis through Approximate Inference",
abstract = "Attack graphs provide compact representations of the attack paths an attacker can follow to compromise network resources from the analysis of network vulnerabilities and topology. These representations are a powerful tool for security risk assessment. Bayesian inference on attack graphs enables the estimation of the risk of compromise to the system{\textquoteright}s components given their vulnerabilities and interconnections and accounts for multi-step attacks spreading through the system. While static analysis considers the risk posture at rest, dynamic analysis also accounts for evidence of compromise, for example, from Security Information and Event Management software or forensic investigation. However, in this context, exact Bayesian inference techniques do not scale well. In this article, we show how Loopy Belief Propagation—an approximate inference technique—can be applied to attack graphs and that it scales linearly in the number of nodes for both static and dynamic analysis, making such analyses viable for larger networks. We experiment with different topologies and network clustering on synthetic Bayesian attack graphs with thousands of nodes to show that the algorithm{\textquoteright}s accuracy is acceptable and that it converges to a stable solution. We compare sequential and parallel versions of Loopy Belief Propagation with exact inference techniques for both static and dynamic analysis, showing the advantages and gains of approximate inference techniques when scaling to larger attack graphs.",
author = "Luis Mu{\~n}oz-Gonz{\'a}lez and Daniele Sgandurra and Andrea Paudice and Emil Lupu",
year = "2017",
month = aug
day = "11",
doi = "10.1145/3105760",
language = "English",
volume = "20",
pages = "1--30",
journal = "ACM Transactions on Information and System Security",
issn = "1094-9224",
publisher = "Association for Computing Machinery (ACM)",
number = "3",

}

RIS

TY - JOUR

T1 - Efficient Attack Graph Analysis through Approximate Inference

AU - Muñoz-González, Luis

AU - Sgandurra, Daniele

AU - Paudice, Andrea

AU - Lupu, Emil

PY - 2017/8/11

Y1 - 2017/8/11

N2 - Attack graphs provide compact representations of the attack paths an attacker can follow to compromise network resources from the analysis of network vulnerabilities and topology. These representations are a powerful tool for security risk assessment. Bayesian inference on attack graphs enables the estimation of the risk of compromise to the system’s components given their vulnerabilities and interconnections and accounts for multi-step attacks spreading through the system. While static analysis considers the risk posture at rest, dynamic analysis also accounts for evidence of compromise, for example, from Security Information and Event Management software or forensic investigation. However, in this context, exact Bayesian inference techniques do not scale well. In this article, we show how Loopy Belief Propagation—an approximate inference technique—can be applied to attack graphs and that it scales linearly in the number of nodes for both static and dynamic analysis, making such analyses viable for larger networks. We experiment with different topologies and network clustering on synthetic Bayesian attack graphs with thousands of nodes to show that the algorithm’s accuracy is acceptable and that it converges to a stable solution. We compare sequential and parallel versions of Loopy Belief Propagation with exact inference techniques for both static and dynamic analysis, showing the advantages and gains of approximate inference techniques when scaling to larger attack graphs.

AB - Attack graphs provide compact representations of the attack paths an attacker can follow to compromise network resources from the analysis of network vulnerabilities and topology. These representations are a powerful tool for security risk assessment. Bayesian inference on attack graphs enables the estimation of the risk of compromise to the system’s components given their vulnerabilities and interconnections and accounts for multi-step attacks spreading through the system. While static analysis considers the risk posture at rest, dynamic analysis also accounts for evidence of compromise, for example, from Security Information and Event Management software or forensic investigation. However, in this context, exact Bayesian inference techniques do not scale well. In this article, we show how Loopy Belief Propagation—an approximate inference technique—can be applied to attack graphs and that it scales linearly in the number of nodes for both static and dynamic analysis, making such analyses viable for larger networks. We experiment with different topologies and network clustering on synthetic Bayesian attack graphs with thousands of nodes to show that the algorithm’s accuracy is acceptable and that it converges to a stable solution. We compare sequential and parallel versions of Loopy Belief Propagation with exact inference techniques for both static and dynamic analysis, showing the advantages and gains of approximate inference techniques when scaling to larger attack graphs.

U2 - 10.1145/3105760

DO - 10.1145/3105760

M3 - Article

VL - 20

SP - 1

EP - 30

JO - ACM Transactions on Information and System Security

JF - ACM Transactions on Information and System Security

SN - 1094-9224

IS - 3

M1 - 10

ER -