On cyber attacks and the maximum-weight rooted-subtree problem

This paper makes three contributions to cyber-security research. First, we define a model for cyber-security systems and the concept of a cyber-security attack within the model's framework. The model highlights the importance of game-over components - critical system components which if acquire...

Full description

Saved in:
Bibliographic Details
Main Authors: Geir Agnarsson, Raymond Greenlaw, Sanpawat Kantabutra
Format: Journal
Published: 2018
Subjects:
Online Access:https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84983353699&origin=inward
http://cmuir.cmu.ac.th/jspui/handle/6653943832/55610
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Chiang Mai University
id th-cmuir.6653943832-55610
record_format dspace
spelling th-cmuir.6653943832-556102018-09-05T03:07:15Z On cyber attacks and the maximum-weight rooted-subtree problem Geir Agnarsson Raymond Greenlaw Sanpawat Kantabutra Computer Science Decision Sciences Engineering Mathematics This paper makes three contributions to cyber-security research. First, we define a model for cyber-security systems and the concept of a cyber-security attack within the model's framework. The model highlights the importance of game-over 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 defense-in-depth/layered-security 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 cyber-security 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 target-acquisition vertex function p on T, the attacker's budget and the game-over threshold B,G ∈ ℚ+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 game-over 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, integer-valued, and rational-valued among a given fixed number of distinct values. Using recursion and dynamic-programming techniques, we show that for constant penetration costs an optimal cyber-attack strategy can be found in polynomial time, and for integer-valued and rational-valued penetration costs optimal cyber-attack strategies can be found in pseudo-polynomial time. Third, we provide a list of open problems relating to the architectural design of cyber-security systems and to the model. 2018-09-05T02:58:25Z 2018-09-05T02:58:25Z 2016-01-01 Journal 0324721X 2-s2.0-84983353699 10.14232/actacyb.22.3.2016.3 https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84983353699&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/55610
institution Chiang Mai University
building Chiang Mai University Library
country Thailand
collection CMU Intellectual Repository
topic Computer Science
Decision Sciences
Engineering
Mathematics
spellingShingle Computer Science
Decision Sciences
Engineering
Mathematics
Geir Agnarsson
Raymond Greenlaw
Sanpawat Kantabutra
On cyber attacks and the maximum-weight rooted-subtree problem
description This paper makes three contributions to cyber-security research. First, we define a model for cyber-security systems and the concept of a cyber-security attack within the model's framework. The model highlights the importance of game-over 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 defense-in-depth/layered-security 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 cyber-security 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 target-acquisition vertex function p on T, the attacker's budget and the game-over threshold B,G ∈ ℚ+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 game-over 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, integer-valued, and rational-valued among a given fixed number of distinct values. Using recursion and dynamic-programming techniques, we show that for constant penetration costs an optimal cyber-attack strategy can be found in polynomial time, and for integer-valued and rational-valued penetration costs optimal cyber-attack strategies can be found in pseudo-polynomial time. Third, we provide a list of open problems relating to the architectural design of cyber-security systems and to the model.
format Journal
author Geir Agnarsson
Raymond Greenlaw
Sanpawat Kantabutra
author_facet Geir Agnarsson
Raymond Greenlaw
Sanpawat Kantabutra
author_sort Geir Agnarsson
title On cyber attacks and the maximum-weight rooted-subtree problem
title_short On cyber attacks and the maximum-weight rooted-subtree problem
title_full On cyber attacks and the maximum-weight rooted-subtree problem
title_fullStr On cyber attacks and the maximum-weight rooted-subtree problem
title_full_unstemmed On cyber attacks and the maximum-weight rooted-subtree problem
title_sort on cyber attacks and the maximum-weight rooted-subtree problem
publishDate 2018
url https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84983353699&origin=inward
http://cmuir.cmu.ac.th/jspui/handle/6653943832/55610
_version_ 1681424537963462656