Lehekülje Thesis:Approximation of the Fully-Adaptive Strategies lähteteksti vaatamine

Back [[Aleksandr_Lenin_MSc_Thesis_topics|to the list of topics]]

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.

In [6] adversarial budget was assumed to be unlimited. It is natural to assume that the adversarial budget is limited. Such an assumption would allow to model adversarial decision making process more closely to the one which we might observe in real life. The results of this research were published in [7]. Authors could analyze only the tree elementary cases, as even these elementary cases quickly became quite complex. The complexity of the computational method has not been assessed, but it supposedly belongs to the P class. 

The Failure-Free model [6] is less complex and provides reliable upper bounds, however it may result in over-secured systems. Due to the fact that when the move fails the attacker finds himself in the very same instance of the security game results in the existence of non-adaptive strategies in the set of optimal strategies of the game, and the ordering of the attack steps in non-adaptive optimal strategies is irrelevant. In the model with budget limitations the subset of non-adaptive strategies exists in the set of all strategies in the game. Non-adaptive strategies are relatively easy to derive and compute. One of the open questions is to figure out how well the most optimal strategy from the subset of non-adaptive strategies might approximate the most optimal strategy from the set of all possible strategies. If the most optimal strategy from the subset of non-adaptive strategies provides pretty good approximation to the most optimal strategy from the set of all possible strategies, then it might enable calculation of acceptably precise result without facing the complexity and the computational overhead introduced by the precise utility calculation routines.

The tasks for this thesis are the following:
* Define the subset of non-adaptive strategies to consider.
* Implement computational method computing the result for the most optimal strategy from the set of all possible strategies in the game
* Implement computational method computing the result for the considered subset of non-adaptive strategies.
* Compare the results.




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 efficient 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

[7] Lenin, A., Buldas, A.: Limiting adversarial budget in quantitative security assessment.
In Decision and Game Theory for Security - 5th International Conference, GameSec 2014, Los
Angeles, CA, USA, November 6-7, 2014. Proceedings, pages 153–172, 2014.