Attack time analysis in dynamic attack trees via integer linear programming

Research output: Working paper

15 Downloads (Pure)

Abstract

Attack trees are an important tool in security analysis, and an important part of attack tree analysis is computing metrics. This paper focuses on dynamic attack trees and their min time metric. For general attack trees, calculating min time efficiently is an open problem, with the fastest current method being enumerating all minimal attacks, which is NP-hard. This paper introduces 3 new tools for calculating min time. First, we show that static attack trees can be handled by a fast bottom-up algorithm. Second, we introduce a novel method for general dynamic attack trees based on mixed integer linear programming. Third, we show how the computation can be sped up by identifying the modules of an attack tree, i.e. subtrees connected to the rest of the attack tree via only one node. Experiments on a generated testing set of large attack trees verify that these methods have a large impact on performance.
Original languageEnglish
PublisherarXiv.org
Number of pages18
Publication statusPublished - 9 Nov 2021

Fingerprint

Dive into the research topics of 'Attack time analysis in dynamic attack trees via integer linear programming'. Together they form a unique fingerprint.

Cite this