Attack Countermeasure Trees: A Non-state-space Approach Towards Analyzing Security and Finding Optimal Countermeasure Sets

Attack tree (AT) is one of the widely used combinatorial models in security analysis. The basic formalism of AT does not take into account defense mechanisms. Defense trees (DTs) have been developed to investigate the effect of defense mechanisms using measures such as attack cost, security investment cost, return on attack (ROA) and return on investment (ROI). DT, however, places defense mechanisms only at the leaf nodes and the corresponding ROI/ROA analysis does not incorporate the probabilities of attack. In attack response tree (ART), attack and response are both captured but ART suffers from the problem of state-space explosion, since solution of ART is obtained by means of a partially observable Markov Decision Process model. In this thesis, we present a novel attack tree paradigm called attack countermeasure tree (ACT) which takes a purely noon-state-space approach to security analysis taking into account attacks as well as countermeasures (in the form of detection and mitigation techniques). In ACT, detection and mitigation are allowed not just at the leaf node but also at the intermediate nodes while at the same time the state-space explosion problem is avoided in its analysis. We propose algorithms to perform single and multiobjective optimization to find optimal countermeasure sets under different sets of budgetary constraints. We illustrate the features of ACT using several case studies.