Efficient Algorithms for Quantitative Attack Tree Analysis

Carlos E. Budde; Mariëlle Stoelinga

doi:10.1109/CSF51468.2021.00041

Efficient Algorithms for Quantitative Attack Tree Analysis

Carlos E. Budde
, Mariëlle Stoelinga

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

11 Citations (Scopus)

168 Downloads (Pure)

Abstract

Numerous analysis methods for quantitative attack tree analysis have been proposed. These algorithms compute relevant security metrics, i.e. performance indicators that quantify how good the security of a system is, such as the most likely attack, the cheapest, or the most damaging one. This paper classifies attack trees in two dimensions: proper trees vs. directed acyclic graphs (i.e. with shared subtrees); and static vs. dynamic gates. For each class, we propose novel algorithms that work over a generic attribute domain, encompassing a large number of concrete security metrics defined on the attack tree semantics. We also analyse the computational complexity of our methods.

Original language	English
Title of host publication	2021 IEEE 34th Computer Security Foundations Symposium (CSF)
ISBN (Electronic)	978-1-7281-7607-9
DOIs	https://doi.org/10.1109/CSF51468.2021.00041
Publication status	Published - 10 Aug 2021
Event	IEEE 34th Computer Security Foundations Symposium, CSF 2021 - Dubrovnik, Croatia Duration: 21 Jun 2021 → 25 Jun 2021 Conference number: 34

Conference

Conference	IEEE 34th Computer Security Foundations Symposium, CSF 2021
Abbreviated title	CSF 2021
Country/Territory	Croatia
City	Dubrovnik
Period	21/06/21 → 25/06/21

Keywords

2024 OA procedure
cs.DS
F.1.0; F.2.2; G.2.3

Access to Document

10.1109/CSF51468.2021.00041

Efficient_Algorithms_for_Quantitative_Attack_Tree_AnalysisFinal published version, 987 KBLicence: Taverne

11 Citations
1 Preprint

Efficient Algorithms for Quantitative Attack Tree Analysis
Budde, C. E. & Stoelinga, M., 16 May 2021.
Research output: Working paper › Preprint › Academic

Open Access
File
73 Downloads (Pure)

Cite this

@inproceedings{7e5812873324429ebc4da1a250b361b4,

title = "Efficient Algorithms for Quantitative Attack Tree Analysis",

abstract = " Numerous analysis methods for quantitative attack tree analysis have been proposed. These algorithms compute relevant security metrics, i.e. performance indicators that quantify how good the security of a system is, such as the most likely attack, the cheapest, or the most damaging one. This paper classifies attack trees in two dimensions: proper trees vs. directed acyclic graphs (i.e. with shared subtrees); and static vs. dynamic gates. For each class, we propose novel algorithms that work over a generic attribute domain, encompassing a large number of concrete security metrics defined on the attack tree semantics. We also analyse the computational complexity of our methods. ",

keywords = "2024 OA procedure, cs.DS, F.1.0; F.2.2; G.2.3",

author = "Budde, \{Carlos E.\} and Mari{\"e}lle Stoelinga",

note = "Public version of CSF'21 paper, including an appendix with all proofs of lemmas and theorems; IEEE 34th Computer Security Foundations Symposium, CSF 2021, CSF 2021 ; Conference date: 21-06-2021 Through 25-06-2021",

year = "2021",

month = aug,

day = "10",

doi = "10.1109/CSF51468.2021.00041",

language = "English",

booktitle = "2021 IEEE 34th Computer Security Foundations Symposium (CSF)",

}

TY - GEN

T1 - Efficient Algorithms for Quantitative Attack Tree Analysis

AU - Budde, Carlos E.

AU - Stoelinga, Mariëlle

N1 - Conference code: 34

PY - 2021/8/10

Y1 - 2021/8/10

N2 - Numerous analysis methods for quantitative attack tree analysis have been proposed. These algorithms compute relevant security metrics, i.e. performance indicators that quantify how good the security of a system is, such as the most likely attack, the cheapest, or the most damaging one. This paper classifies attack trees in two dimensions: proper trees vs. directed acyclic graphs (i.e. with shared subtrees); and static vs. dynamic gates. For each class, we propose novel algorithms that work over a generic attribute domain, encompassing a large number of concrete security metrics defined on the attack tree semantics. We also analyse the computational complexity of our methods.

AB - Numerous analysis methods for quantitative attack tree analysis have been proposed. These algorithms compute relevant security metrics, i.e. performance indicators that quantify how good the security of a system is, such as the most likely attack, the cheapest, or the most damaging one. This paper classifies attack trees in two dimensions: proper trees vs. directed acyclic graphs (i.e. with shared subtrees); and static vs. dynamic gates. For each class, we propose novel algorithms that work over a generic attribute domain, encompassing a large number of concrete security metrics defined on the attack tree semantics. We also analyse the computational complexity of our methods.

KW - 2024 OA procedure

KW - cs.DS

KW - F.1.0; F.2.2; G.2.3

U2 - 10.1109/CSF51468.2021.00041

DO - 10.1109/CSF51468.2021.00041

M3 - Conference contribution

BT - 2021 IEEE 34th Computer Security Foundations Symposium (CSF)

T2 - IEEE 34th Computer Security Foundations Symposium, CSF 2021

Y2 - 21 June 2021 through 25 June 2021

ER -

Efficient Algorithms for Quantitative Attack Tree Analysis

Abstract

Conference

Keywords

Access to Document

Fingerprint

Research output

Efficient Algorithms for Quantitative Attack Tree Analysis

Cite this