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.

At this time all the models were computing the so-called Attack Trees - a hierarchical description of an attack scenario in the form of a tree (a data structure). Later research has shown that real-life attacks only in very rare cases can be represented in the form of a tree, actually they are graph structures (PDAG) and we call them Attack Graphs. The Failure-Free model cannot provide reliable results, working on a graph structure and needs a "pure tree" structure.

Thus, in order to be able to analyze the scenario using the Failure-Free model, an attack scenario from graph representation must first be converted to a tree representation, only then one can analyze the scenario using the Failure-Free model.

Lenin et al. came up with a solution to this problem, enabling transformations from a PDAG into a tree, however, the complexity of this transformation is not estimated yet. Certainly, this kind of transformation has a certain penalty on the performance of the entire method limiting the size of attack scenarios that we might be able to analyze in reasonable time.

In the following thesis we suggest to implement a genetic algorithm for the Failure-Free model. The hypothesis for this work is that the genetic approximation for the Failure-Free model might be more efficient (in terms of performance) than the combination of PDAG -> Tree -> Failure-Free Model.

Of course, when the transformation component will get ready, we will need to compare the performance of both of the methods, but this is a topic for another thesis.

The tasks for this thesis are the following:

• Design and implement the genetic algorithm for the Failure-Free model, capable of working directly on PDAG stuctures
• Document the algorithm
• Estimate computational complexity of the phases of the algoorithm
• Run benchmarking tests

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