Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Computational Aspects of Attack-Defense Trees
Kordy, Barbara; Pouly, Marc; Schweitzer, Patrick
2011 • In Security and Intelligent Information Systems - International Joint Conferences, SIIS 2011, Warsaw, Poland, June 13-14, 2011, Revised Selected Papers
[en] Attack-defense trees extend attack trees with defense nodes. This richer formalism allows for a more precise modeling of a system’s vulnerabilities, by representing interactions between possible attacks and corresponding defensive measures. In this paper we compare the computational complexity of both formalisms. We identify semantics for which extending attack trees with defense nodes does not increase the computational complexity. This implies that, for these semantics, every query that can be solved efficiently on attack trees can also be solved efficiently on attack-defense trees. Furthermore, every algorithm for attack trees can directly be used to process attack-defense trees.
Disciplines :
Computer science
Author, co-author :
Kordy, Barbara ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Pouly, Marc ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Schweitzer, Patrick ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Language :
English
Title :
Computational Aspects of Attack-Defense Trees
Publication date :
2011
Event name :
Security and Intelligent Information Systems - International Joint Conferences
Event place :
Warsaw, Poland
Event date :
13-14 June 2011
Main work title :
Security and Intelligent Information Systems - International Joint Conferences, SIIS 2011, Warsaw, Poland, June 13-14, 2011, Revised Selected Papers
Schneier, B.: Attack Trees. Dr. Dobb's Journal of Software Tools 24(12), 21-29 (1999)
Weiss, J.D.: A system security engineering process. In: 14th Nat. Comp. Sec. Conf., pp. 572-581 (1991)
Amoroso, E.G.: Fundamentals of Computer Security Technology. Prentice-Hall, Inc., Upper Saddle River (1994)
Vesely, W.E., Goldberg, F.F., Roberts, N., Haasl, D.: Fault Tree Handbook. Technical Report NUREG-0492, U.S. Regulatory Commission (1981)
Mauw, S., Oostdijk, M.: Foundations of Attack Trees. In:Won, D.H., Kim, S. (eds.) ICISC 2005. LNCS, vol. 3935, pp. 186-198. Springer, Heidelberg (2006)
Cervesato, I., Meadows, C.: One Picture Is Worth a Dozen Connectives: A Fault- Tree Representation of NPATRL Security Requirements. IEEE TDSC 4, 216-227 (2007)
Edge, K.S., Dalton II, G.C., Raines, R.A., Mills, R.F.: Using Attack and Protection Trees to Analyze Threats and Defenses to Homeland Security. In: MILCOM, IEEE, pp. 1-7 (2006)
Morais, A.N.P., Martins, E., Cavalli, A.R., Jimenez, W.: Security Protocol Testing Using Attack Trees. In: CSE (2), pp. 690-697. IEEE Computer Society (2009)
Jürgenson, A., Willemson, J.: Serial Model for Attack Tree Computations. In: Lee, D., Hong, S. (eds.) ICISC 2009. LNCS, vol. 5984, pp. 118-128. Springer, Heidelberg (2010)
Bistarelli, S., Peretti, P., Trubitsyna, I.: Analyzing Security Scenarios Using Defence Trees and Answer Set Programming. ENTCS 197(2), 121-129 (2008)
Yager, R.R.: OWA trees and their role in security modeling using attack trees. Inf. Sci. 176(20), 2933-2959 (2006)
Kordy, B., Mauw, S., Radomirović, S., Schweitzer, P.: Foundations of Attack-Defense Trees. In: Degano, P., Etalle, S., Guttman, J. (eds.) FAST 2010. LNCS, vol. 6561, pp. 80-95. Springer, Heidelberg (2011)
Kordy, B., Mauw, S., Melissen, M., Schweitzer, P.: Attack-Defense Trees and Two-Player Binary Zero-Sum Extensive Form Games Are Equivalent. In: Alpcan, T., Buttyán, L., Baras, J.S. (eds.) GameSec 2010. LNCS, vol. 6442, pp. 245-256. Springer, Heidelberg (2010)
Kohlas, J.: Information Algebras: Generic Structures for Inference. Springer, Heidelberg (2003)
Davey, B., Priestley, H.: Introduction to Lattices and Order. Cambridge University Press (1990)
Pouly, M., Kohlas, J.: Generic Inference: A Unifying Theory for Automated Reasoning. John Wiley & Sons, Inc. (2011)
Crama, Y., Hammer, P.: Boolean Functions: Theory, Algorithms and Applications. Cambridge University Press (2011)
Wachter, M., Haenni, R.: Multi-state Directed Acyclic Graphs. In: Kobti, Z., Wu, D. (eds.) Canadian AI 2007. LNCS (LNAI), vol. 4509, pp. 464-475. Springer, Heidelberg (2007)
Darwiche, A., Marquis, P.: A Knowledge Compilation Map. J. Artif. Intell. Res. 17, 229-264 (2002)
