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

• Main Author: Supachai Mukdasanit
• Format: Conference Proceeding
• Published: 2019
• Subjects: Computer Science; Engineering; Mathematics
• Online Access: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85066496357&origin=inward; http://cmuir.cmu.ac.th/jspui/handle/6653943832/65507
• Institution: Chiang Mai University

© 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.