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

摘要

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 O(1ϵ2n3log⁡G) and a (1+ϵ) FPTAS with the time bound O(1ϵ2n4log⁡G) for the first and second problems, respectively.