Time complexity of the edge replacement problem in a cyber security system

Abstract

© 2018 IEEE. In this article, we propose a new defensive problem in a security system. Let S(T, c, p) be a security system, where T = (V, E) is a rooted tree rooted at r, c and p are assignment functions c: E(T) → + and p: V(T) {r} → +, respectively. Additionally, let T[v] be a rooted subtree rooted at v of T that is obtained by removing an edge {u, v} E(T), where u is the parent of v, from T. Given a security system S(T, c, p) and a budget B+, we consider the problem of determining an edge {u, v} E(T) and an edge {w′, v}, where a vertex w′ V(T)\ V(T[v]), such that the maximum total of prizes obtained from an optimal attack in S(T′, c′, p) is minimized when {u, v} has been replaced by {w′, v}, where c′({w′, v}) = c({u, v}) and for all edge e E(T′) \{w′, v}, c′(e) = c(e). We define the decision and optimization versions of the problem to use when determining time computational complexities. We prove that the decision version is coNP-hard. Additionally, we show that the optimization version can be solved in pseudo-polynomial time. Conclusion and open problems are given in the last section.