Attack and defense in the layered cyber-security model and their (1 ± ϵ)-approximation schemes
| Autor: | Supachai Mukdasanit, Sanpawat Kantabutra |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Multiset
General Computer Science Computer Networks and Communications Applied Mathematics 0102 computer and information sciences 02 engineering and technology Computer security model 01 natural sciences Theoretical Computer Science Combinatorics Computational Theory and Mathematics 010201 computation theory & mathematics 020204 information systems 0202 electrical engineering electronic engineering information engineering Tree (set theory) Enhanced Data Rates for GSM Evolution Bijection injection and surjection Security system Mathematics |
| Zdroj: | Journal of Computer and System Sciences. 115:54-63 |
| ISSN: | 0022-0000 |
| DOI: | 10.1016/j.jcss.2020.07.001 |
| Popis: | 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 ( G 2 n ) -time algorithm to compute an optimal attack as well as an O ( G 2 n 2 ) -time algorithm to determine such an edge are given, in addition to a (1-ϵ) FPTAS with the time bound O ( 1 ϵ 2 n 3 log G ) and a (1+ϵ) FPTAS with the time bound O ( 1 ϵ 2 n 4 log G ) for the first and second problems, respectively. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect