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 acyber-security attack within the model's framework. The modelhighlights the importance of game-over components - criticalsystem components which if acquired will give an adversary the abilityto defeat a system completely. The model is based on systems thatuse defense-in-depth/layered-security approaches, as many systemsdo. In the model we define the concept of penetration cost,which is the cost that must be paid in order to break into the nextlayer of security. Second, we define natural decision and optimizationproblems based on cyber-security attacks in terms of doubly weightedtrees, and analyze their complexity. More precisely, given a treeT rooted at a vertex r, a penetrating cost edge functionc on T, a target-acquisition vertex function p on T,the attacker's budget and the game-over thresholdB,G ∈ ℚ+respectively, we consider the problem of determiningthe existence of a rooted subtree T' of T within the attacker'sbudget that is, the sum of the costs of the edges in T' is lessthan or equal to B with total acquisition value more than thegame-over threshold that is, the sum of the target values of thenodes in T' is greater than or equal to G. We prove that thegeneral version of this problem is intractable, but does admit apolynomial time approximation scheme. We also analyze the complexityof three restricted versions of the problems, where the penetrationcost is the constant function, integer-valued, and rational-valuedamong a given fixed number of distinct values. Using recursion anddynamic-programming techniques, we show that for constant penetrationcosts an optimal cyber-attack strategy can be found in polynomialtime, and for integer-valued and rational-valued penetration costsoptimal cyber-attack strategies can be found in pseudo-polynomialtime. Third, we provide a list of open problems relating to the architecturaldesign of cyber-security systems and to the model.