Secure the IoT Networks as Epidemic Containment Game
The spread of a computer virus among the Internet of Things (IoT) devices can be modeled as an Epidemic Containment (EC) game, where each owner decides the strategy, e.g., installing anti-virus software, to maximize his utility against the susceptible-infected-susceptible (SIS) model of the epidemic...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-01-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/13/2/156 |
| _version_ | 1797409488011001856 |
|---|---|
| author | Juntao Zhu Hong Ding Yuchen Tao Zhen Wang Lanping Yu |
| author_facet | Juntao Zhu Hong Ding Yuchen Tao Zhen Wang Lanping Yu |
| author_sort | Juntao Zhu |
| collection | DOAJ |
| description | The spread of a computer virus among the Internet of Things (IoT) devices can be modeled as an Epidemic Containment (EC) game, where each owner decides the strategy, e.g., installing anti-virus software, to maximize his utility against the susceptible-infected-susceptible (SIS) model of the epidemics on graphs. The EC game’s canonical solution concepts are the Minimum/Maximum Nash Equilibria (MinNE/MaxNE). However, computing the exact MinNE/MaxNE is NP-hard, and only several heuristic algorithms are proposed to approximate the MinNE/MaxNE. To calculate the exact MinNE/MaxNE, we provide a thorough analysis of some special graphs and propose scalable and exact algorithms for general graphs. Especially, our contributions are four-fold. First, we analytically give the MinNE/MaxNE for EC on special graphs based on spectral radius. Second, we provide an integer linear programming formulation (ILP) to determine MinNE/MaxNE for the general graphs with the small epidemic threshold. Third, we propose a branch-and-bound (BnB) framework to compute the exact MinNE/MaxNE in the general graphs with several heuristic methods to branch the variables. Fourth, we adopt NetShiled (NetS) method to approximate the MinNE to improve the scalability. Extensive experiments demonstrate that our BnB algorithm can outperform the naive enumeration method in scalability, and the NetS can improve the scalability significantly and outperform the previous heuristic method in solution quality. |
| first_indexed | 2024-03-09T04:15:16Z |
| format | Article |
| id | doaj.art-a48532e1fccf46f19ad8d1c899c1f556 |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-03-09T04:15:16Z |
| publishDate | 2021-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-a48532e1fccf46f19ad8d1c899c1f5562023-12-03T13:55:44ZengMDPI AGSymmetry2073-89942021-01-0113215610.3390/sym13020156Secure the IoT Networks as Epidemic Containment GameJuntao Zhu0Hong Ding1Yuchen Tao2Zhen Wang3Lanping Yu4School of Cyberspace, Hangzhou Dianzi University, Hangzhou 310018, ChinaSchool of Cyberspace, Hangzhou Dianzi University, Hangzhou 310018, ChinaSchool of Cyberspace, Hangzhou Dianzi University, Hangzhou 310018, ChinaSchool of Cyberspace, Hangzhou Dianzi University, Hangzhou 310018, ChinaSchool of Information Engineering, Hangzhou Dianzi University, Hangzhou 310018, ChinaThe spread of a computer virus among the Internet of Things (IoT) devices can be modeled as an Epidemic Containment (EC) game, where each owner decides the strategy, e.g., installing anti-virus software, to maximize his utility against the susceptible-infected-susceptible (SIS) model of the epidemics on graphs. The EC game’s canonical solution concepts are the Minimum/Maximum Nash Equilibria (MinNE/MaxNE). However, computing the exact MinNE/MaxNE is NP-hard, and only several heuristic algorithms are proposed to approximate the MinNE/MaxNE. To calculate the exact MinNE/MaxNE, we provide a thorough analysis of some special graphs and propose scalable and exact algorithms for general graphs. Especially, our contributions are four-fold. First, we analytically give the MinNE/MaxNE for EC on special graphs based on spectral radius. Second, we provide an integer linear programming formulation (ILP) to determine MinNE/MaxNE for the general graphs with the small epidemic threshold. Third, we propose a branch-and-bound (BnB) framework to compute the exact MinNE/MaxNE in the general graphs with several heuristic methods to branch the variables. Fourth, we adopt NetShiled (NetS) method to approximate the MinNE to improve the scalability. Extensive experiments demonstrate that our BnB algorithm can outperform the naive enumeration method in scalability, and the NetS can improve the scalability significantly and outperform the previous heuristic method in solution quality.https://www.mdpi.com/2073-8994/13/2/156cyber-securityepidemic controlgame theorycomplex network |
| spellingShingle | Juntao Zhu Hong Ding Yuchen Tao Zhen Wang Lanping Yu Secure the IoT Networks as Epidemic Containment Game Symmetry cyber-security epidemic control game theory complex network |
| title | Secure the IoT Networks as Epidemic Containment Game |
| title_full | Secure the IoT Networks as Epidemic Containment Game |
| title_fullStr | Secure the IoT Networks as Epidemic Containment Game |
| title_full_unstemmed | Secure the IoT Networks as Epidemic Containment Game |
| title_short | Secure the IoT Networks as Epidemic Containment Game |
| title_sort | secure the iot networks as epidemic containment game |
| topic | cyber-security epidemic control game theory complex network |
| url | https://www.mdpi.com/2073-8994/13/2/156 |
| work_keys_str_mv | AT juntaozhu securetheiotnetworksasepidemiccontainmentgame AT hongding securetheiotnetworksasepidemiccontainmentgame AT yuchentao securetheiotnetworksasepidemiccontainmentgame AT zhenwang securetheiotnetworksasepidemiccontainmentgame AT lanpingyu securetheiotnetworksasepidemiccontainmentgame |