Attack and defense in the layered cyber-security model and their (1 ± ϵ)-approximation schemes

Abstract

© 2020 Elsevier Inc. Let M=(T,C,P) be a security model, where T is a rooted tree, C is a multiset of costs and P is a multiset of prizes and let (T,c,p) be a security system, where c and p are bijections of costs and prizes. The problems of computing an optimal attack on a security system and of determining an edge e∈E(T) such that the maximum sum of prizes obtained from an optimal attack in (T,c,p) is minimized when c(e)=∞ are considered. An O(G2n)-time algorithm to compute an optimal attack as well as an O(G2n2)-time algorithm to determine such an edge are given, in addition to a (1-ϵ) FPTAS with the time bound [Formula presented] and a (1+ϵ) FPTAS with the time bound [Formula presented] for the first and second problems, respectively.