Agnarsson, Geir and Greenlaw, Raymond and Kantabutra, Sanpawat: On Cyber Attacks and the MaximumWeight RootedSubtree Problem. In: Acta cybernetica, (22) 3. pp. 591612. (2016)

Cikk, tanulmány, mű
actacyb_22_3_2016_3.pdf Download (426kB)  Preview 
Abstract
This paper makes three contributions to cybersecurity research. First, we define a model for cybersecurity systems and the concept of a cybersecurity attack within the model's framework. The model highlights the importance of gameover components  critical system components which if acquired will give an adversary the ability to defeat a system completely. The model is based on systems that use defenseindepth/layeredsecurity approaches, as many systems do. In the model we define the concept of penetration cost, which is the cost that must be paid in order to break into the next layer of security. Second, we define natural decision and optimization problems based on cybersecurity attacks in terms of doubly weighted trees, and analyze their complexity. More precisely, given a tree T rooted at a vertex r, a penetrating cost edge function c on T, a targetacquisition vertex function p on T, the attacker's budget and the gameover threshold B,G ϵ Q+ respectively, we consider the problem of determining the existence of a rooted subtree T' of T within the attacker's budget (that is, the sum of the costs of the edges in T' is less than or equal to B) with total acquisition value more than the gameover threshold (that is, the sum of the target values of the nodes in T' is greater than or equal to G). We prove that the general version of this problem is intractable, but does admit a polynomial time approximation scheme. We also analyze the complexity of three restricted versions of the problems, where the penetration cost is the constant function, integervalued, and rationalvalued among a given fixed number of distinct values. Using recursion and dynamicprogramming techniques, we show that for constant penetration costs an optimal cyberattack strategy can be found in polynomial time, and for integervalued and rationalvalued penetration costs optimal cyberattack strategies can be found in pseudopolynomial time. Third, we provide a list of open problems relating to the architectural design of cybersecurity systems and to the model.
Item Type:  Article 

Journal or Publication Title:  Acta cybernetica 
Date:  2016 
Volume:  22 
Number:  3 
ISSN:  0324721X 
Page Range:  pp. 591612 
DOI:  https://doi.org/10.14232/actacyb.22.3.2016.3 
Uncontrolled Keywords:  Számítógépes támadások  biztonság, Vírusvédelem 
Date Deposited:  2017. Mar. 16. 13:10 
Last Modified:  2018. Jun. 06. 18:59 
URI:  http://acta.bibl.uszeged.hu/id/eprint/40264 
Actions (login required)
View Item 