University of Twente Student Theses


Effectiveness of Modular analysis on Attack Trees using Binary Decision Diagrams

Pirinski, Vasil (2023) Effectiveness of Modular analysis on Attack Trees using Binary Decision Diagrams.

[img] PDF
Abstract:Attack trees are a simple model used for system security that provides a systematic way to assess possible attacks on a system and quantify them using different metrics, such as total cost or damage caused. This is an NP-Complete problem. However, brute-forcing all possible attacks is too costly for large attack trees, so there are algorithms for making the analysis more efficient. One such algorithm transforms the attack tree into a Binary Decision Diagram (BDD). Solving this is exponential in time at worst, so we apply an existing method, called Modular analysis, where the work is split by first solving smaller components (modules). The goal of this research is to check the effect Modular analysis has on the performance of the BDD algorithm. We construct a corpus of attack trees of up to 260 nodes and analyze the computation times of our implementations for both methods. The results indicate that the time complexities of both methods are exponential, but Modular analysis tends to be significantly faster. Moreover, this increase in performance is dependent on the number of modules. However, this combined approach introduces some computational overhead, which causes negligibly longer computation times for attack trees that take fractions of a second to solve. The results we show are for calculating the minimal total cost.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:54 computer science
Programme:Computer Science BSc (56964)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page