Thesis:Genetic Failure Free Computations

The first model capable of performing multiparameter quantitative analysis was suggested by Buldas [1]. Later on A.Jürgenson/Kalu and J.Willemson improved the model of Buldas et al. and suggested the two new models -- the so-called parallel model [2] and the serial model [3].

Even though being theoretically sound, the results of Jürgenson and Willemson are rather discouraging from an engineering point of view. Even applying all the optimizations outlined in [2] the authors were able to analyze attack scenarios with no more than 20 basic actions in reasonable time, as this does not suffice for many practical applications. In their subsequent work authors suggest a set of further optimizations, as well as suggest a genetic algorithm for fast approximations [4]. These improvements allowed to slightly increase the performance of the computational method compared to [2]. Authors state that the genetic algorithm allowed them to analyze attack scenarios containing 70-80 basic actions in 1-2 minutes. Even if this approach allows to analyze attack scenarios containing slightly more than 100 basic actions in reasonable time, this is still far from being sufficient, as real-life attack sceanrios contain thousands, or even dozens of thousands of basic actions.

Further development of the quantitative security analysis models starts couple of years later with the appearanance of the Buldas-Stepanenko model [5] which introduces the upper bound ideology. This model was later on improved by Budldas and Lenin in [6]. The new model was named the Failure-Free model. Authors have shown that finding an optimal strategy in the Failure-Free model is an NP-complete problem and have suggested effective methods to get the approximation of the adversarial utility upper bound. The suggested computational routines deriving approximated upper bound had linear complexity which allowed to analyze attack scenarios of practical size.

Bibliography:

[1] Buldas, A., Laud, P., Priisalu, J., Saarepera, M., Willemson, J.: Rational Choice of Security Measures via Multi-Parameter Attack Trees. In: Critical Information Infrastructures Security. First International Workshop, CRITIS 2006. Volume 4347 of LNCS., Springer (2006) 235–248

[2] Jürgenson, A., Willemson, J., Computing Exact Outcomes of Multi-parameter Attack Trees, In On the Move to Meaningful Internet Systems: OTM 2008, IS 2008, Monterrey, Mexico, November 9-14, 2008, volume 5332 of Lecture Notes in Computer Science, pages 1036-1051. Available at http://research.cyber.ee/~jan/publ/JW08.pdf

[3] Jürgenson, A., Willemson, J., Serial Model for Attack Tree Computations. In D. Lee and S. Hong (Eds.): ICISC 2009, Lecture Notes in Computer Science, volume 5984, pp. 118-128, Springer 2010. Available at http://research.cyber.ee/~jan/publ/serialattack.pdf

[4] Jürgenson, A., Willemson, J., On Fast and Approximate Attack Tree Computations, in Information Security and Practice, 6th International Conference (ISPEC 2010), volume 6047 of LNCS, pages 56-66, Springer-Verlag, 2010. Available at http://research.cyber.ee/~jan/publ/approxtree_paper.pdf

[5] Buldas, A., Stepanenko, R.: Upper bounds for adversaries' utility in attack trees. In Grossklags, J., Walrand, J.C., eds.: GameSec. Volume 7638 of Lecture Notes in Computer Science., Springer (2012) 98-117

[6] Buldas, A., Lenin, A.: New e�cient utility upper bounds for the fully adaptive model of attack trees. In Das, S.K., Nita-Rotaru, C., Kantarcioglu, M., eds.: GameSec. Volume 8252 of Lecture Notes in Computer Science., Springer (2013) 192-205