Moving target defense decision-making algorithm based on multi-stage evolutionary signal game model

doi:10.11772/j.issn.1001-9081.2021071154

Abstract

Abstract:

Currently， the network security accidents occur frequently， and traditional passive defense technologies have no possible response to unknown network security threats. In response to this problem， a multi-stage evolutionary signal game model was constructed. And with the background that the defender actively launches inductive signals for security defense， a Moving Target Defense （MTD） decision-making algorithm based on the multi-stage evolutionary signal game model was proposed. Firstly， the basic elements of the model were defined and the overall model was analyzed theoretically based on the assumptions of incomplete information constraints and complete rationality of both sides of the game. Then， a method for quantifying the benefits of offensive and defensive strategies was designed， and a detailed optimal strategy solving process for equilibrium was given. Finally， the MTD method was introduced to analyze the evolution trends of both sides’ strategies in multi-stage attack and defense. Experimental results show that the proposed algorithm can predict the optimal defense strategies at different stages accurately， and has guiding significance for the research of new network active defense technology. At the same time， the results of comparing the proposed algorithm with the traditional random uniform strategy selection algorithm through Monte Carlo simulation experiment verify the effectiveness and safety of the proposed algorithm.

Key words: network attack and defense, signal game, Moving Target Defense (MTD), evolutionary game, multi-stage evolution

摘要：

当前网络安全事故频发，传统被动防御技术已经无法应对未知的网络安全威胁。针对这一问题，构建了多阶段演化信号博弈模型，并以防御方主动发射诱导信号进行安全防御为背景，提出了一种基于多阶段演化信号博弈模型的移动目标防御（MTD）决策算法。首先，以博弈双方不完全信息约束及完全理性前提为假设对模型的基本元素进行定义并进行模型整体理论分析；然后，设计了攻防策略的收益量化方法，并给出了详细的最优策略均衡求解过程；最后，引入MTD方法分析多阶段攻防情况下双方策略的演化趋势。实验结果表明，所提算法能准确预测出不同阶段最优防御策略，而且对新型网络主动防御技术研究具有指导意义。同时，通过蒙特卡洛仿真实验，将所提算法与传统随机均匀策略选择算法进行对比，所得结果验证了所提算法的有效性和安全性。

关键词: 网络攻防, 信号博弈, 移动目标防御, 演化博弈, 多阶段演化

CLC Number:

TP393.08

Wenting BI, Haitao LIN, Liqun ZHANG. Moving target defense decision-making algorithm based on multi-stage evolutionary signal game model[J]. Journal of Computer Applications, 2022, 42(9): 2780-2787.

毕文婷, 林海涛, 张立群. 基于多阶段演化信号博弈模型的移动目标防御决策算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2780-2787.

Figures/Tables 17

Fig. 1 Flowchart of game

Tab. 1 Attack lethality

攻击

分类

攻击描述

攻击

分类

Tab. 2 Symbols and their meanings

符号	含义	符号	含义
AC	攻击成本	SYC	系统损失
AE	攻击收益	AL	致命度
SC	诱导信号成本	Criticality	危险度
DC	防御成本	SDC	安全属性损害
DE	防御收益

Tab. 3 Game properties comparison of different algorithms

算法	博弈类型	动态性	行为理性	博弈类型	均衡求解
文献［18］算法	完全信息	单阶段	完全理性	静态博弈	简单
文献［19］算法	不完全信息	单阶段	不完全理性	演化博弈	详细
文献［20］算法	不完全信息	单阶段	完全理性	信号博弈	简单
文献［21］算法	不完全信息	多阶段	完全理性	Markov 时间博弈	详细
文献［12］算法	不完全信息	多阶段	完全理性	Markov 矩阵博弈	详细
本文算法	不完全信息	多阶段	有限理性	Markov 信号博弈	详细

Fig. 2 Simulation experiment topology

Tab. 4 Attack strategy set

攻击策略	策略描述	攻击描述	致命度AL	攻击成本
$A S 1$	Remote buffer overflow	Root	10	200
$A S 2$	Install SQL Listener program	Probe	1	125
$A S 3$	Homepage attack	Root	10	150
$A S 4$	Web-rhost attack	Root	10	160
$A S 5$	Oracle TNS Listener	Root	10	120
$A S 6$	Steal account and crack it	User	5	180
$A S 7$	LPC to LSASS process	Probe	1	30
$A S 8$	Install delete Trojan	Probe	1	100

Tab. 4 Attack strategy set

攻击策略	策略描述	攻击描述	致命度AL	攻击成本
$A S 1$	Remote buffer overflow	Root	10	200
$A S 2$	Install SQL Listener program	Probe	1	125
$A S 3$	Homepage attack	Root	10	150
$A S 4$	Web-rhost attack	Root	10	160
$A S 5$	Oracle TNS Listener	Root	10	120
$A S 6$	Steal account and crack it	User	5	180
$A S 7$	LPC to LSASS process	Probe	1	30
$A S 8$	Install delete Trojan	Probe	1	100

Tab. 5 Defense strategy set

防御类型	防御策略	策略描述	频率	防御成本
高等级	$D S 1$	Platform migration	Fixed	300
	$D S 2$	Fingerprint switch	Fixed	260
	$D S 3$	IP hopping	Random	280
	$D S 4$	Protocol changing	Random	190
	$D S 5$	Route Enlarging	Random	180
低等级	$D S 6$	Delete suspicious account		160
	$D S 7$	Address blacklist		130
	$D S 8$	Repair server		100
	$D S 9$	Unistall delete Trojan		120
	$D S 10$	Renew root data		110

Tab. 5 Defense strategy set

防御类型	防御策略	策略描述	频率	防御成本
高等级	$D S 1$	Platform migration	Fixed	300
	$D S 2$	Fingerprint switch	Fixed	260
	$D S 3$	IP hopping	Random	280
	$D S 4$	Protocol changing	Random	190
	$D S 5$	Route Enlarging	Random	180
低等级	$D S 6$	Delete suspicious account		160
	$D S 7$	Address blacklist		130
	$D S 8$	Repair server		100
	$D S 9$	Unistall delete Trojan		120
	$D S 10$	Renew root data		110

Tab. 6 State transition probability of each stage

状态转移	转移概率	状态转移	转移概率
$S 1 → S 2$	0.60	$S 3 → S 4$	0.78
$S 2 → S 3$	0.85	$S 3 → S 5$	0.18
$S 2 → S 4$	0.90	$S 4 → S 5$	0.36

Tab. 6 State transition probability of each stage

状态转移	转移概率	状态转移	转移概率
$S 1 → S 2$	0.60	$S 3 → S 4$	0.78
$S 2 → S 3$	0.85	$S 3 → S 5$	0.18
$S 2 → S 4$	0.90	$S 4 → S 5$	0.36

Tab. 7 Attack and defense strategies of each stage

网络状态	攻击策略	防御策略
$S 1$	$A S 1 = {A S a 1, A S a 2, A S a 6}$	$D S 1 = {D S d 3, D S d 6}$
$S 2$	$A S 2 = {A S a 4, A S a 5, A S a 8}$	$D S 2 = {D S d 3, D S d 8}$
$S 3$	$A S 3 = {A S a 2, A S a 6, A S a 7}$	$D S 3 = {D S d 4, D S d 8}$
$S 4$	$A S 4 = {A S a 2, A S a 3, A S a 8}$	$D S 4 = {D S d 1, D S d 9}$
$S 5$	$A S 5 = {A S a 2, A S a 4, A S a 6}$	$D S 5 = {D S d 2, D S d 10}$

Tab. 7 Attack and defense strategies of each stage

网络状态	攻击策略	防御策略
$S 1$	$A S 1 = {A S a 1, A S a 2, A S a 6}$	$D S 1 = {D S d 3, D S d 6}$
$S 2$	$A S 2 = {A S a 4, A S a 5, A S a 8}$	$D S 2 = {D S d 3, D S d 8}$
$S 3$	$A S 3 = {A S a 2, A S a 6, A S a 7}$	$D S 3 = {D S d 4, D S d 8}$
$S 4$	$A S 4 = {A S a 2, A S a 3, A S a 8}$	$D S 4 = {D S d 1, D S d 9}$
$S 5$	$A S 5 = {A S a 2, A S a 4, A S a 6}$	$D S 5 = {D S d 2, D S d 10}$

Tab. 8 Attack and defense benefit matrices of each stage

网络状态	$S I 1$	$S I 2$
$S 1$	$(923,743) (606,690) (350,95) (177,42) (583,383) (410,330)$	$(736,606) (592,582) (271,66) (127,42) (456,306) (312,282)$
$S 2$	$(1 719,1 599) (1 574,1 564) (1 699,1 526) (1 644,1 384) (321,141) (206,106)$	$(1 475,1 405) (1 310,1 320) (1 515,1 460) (1 350,1 100) (321,191) (251,201)$
$S 3$	$(310,140) (1 674,1 564) (893,793) (1 644,1 348) (405,145) (276,106)$	$(238,123) (155,156) (713,553) (723,733) (333,95) (225,86)$
$S 4$	$(3 112,2 912) (2 852,2 832) (3 162,2 900) (2 902,2 810) (620,320) (360,240)$	$(2 560,1928) (2 344,2 374) (3 990,2410) (2 394,2 314) (500,250) (284,114)$
$S 5$	$(4 674,4 514) (4 458,4 448) (4 714,4 614) (4 498,4 432) (2 444,2 264) (2 228,2 198)$	$(3 862,3 752) (3 682,3 722) (3 902,3 700) (3 722,3 652) (2 007,1 877) (1 872,1 874)$

Tab. 8 Attack and defense benefit matrices of each stage

网络状态	$S I 1$	$S I 2$
$S 1$	$(923,743) (606,690) (350,95) (177,42) (583,383) (410,330)$	$(736,606) (592,582) (271,66) (127,42) (456,306) (312,282)$
$S 2$	$(1 719,1 599) (1 574,1 564) (1 699,1 526) (1 644,1 384) (321,141) (206,106)$	$(1 475,1 405) (1 310,1 320) (1 515,1 460) (1 350,1 100) (321,191) (251,201)$
$S 3$	$(310,140) (1 674,1 564) (893,793) (1 644,1 348) (405,145) (276,106)$	$(238,123) (155,156) (713,553) (723,733) (333,95) (225,86)$
$S 4$	$(3 112,2 912) (2 852,2 832) (3 162,2 900) (2 902,2 810) (620,320) (360,240)$	$(2 560,1928) (2 344,2 374) (3 990,2410) (2 394,2 314) (500,250) (284,114)$
$S 5$	$(4 674,4 514) (4 458,4 448) (4 714,4 614) (4 498,4 432) (2 444,2 264) (2 228,2 198)$	$(3 862,3 752) (3 682,3 722) (3 902,3 700) (3 722,3 652) (2 007,1 877) (1 872,1 874)$

Tab. 9 Attack and defense equilibrium values of each stage

网络状态	攻击策略概率均衡值
网络状态	$f 1 (A S 1)$	$f 1 (A S 2)$	$f 1 (A S 3)$	$f 2 (A S 1)$	$f 2 (A S 2)$	$f 2 (A S 3)$	$q 1 (S I 1)$	$q 2 (S I 1)$
$S 1$	1	0	0	0	1	0	1	0
$S 2$	1	0	0	0	1	0	1	0
$S 3$	0	1	0	0	1	0	1	1
$S 4$	0	1	0	0	1	0	1	1
$S 5$	1	0	0	1	0	0	1	1

Tab. 9 Attack and defense equilibrium values of each stage

网络状态	攻击策略概率均衡值
网络状态	$f 1 (A S 1)$	$f 1 (A S 2)$	$f 1 (A S 3)$	$f 2 (A S 1)$	$f 2 (A S 2)$	$f 2 (A S 3)$	$q 1 (S I 1)$	$q 2 (S I 1)$
$S 1$	1	0	0	0	1	0	1	0
$S 2$	1	0	0	0	1	0	1	0
$S 3$	0	1	0	0	1	0	1	1
$S 4$	0	1	0	0	1	0	1	1
$S 5$	1	0	0	1	0	0	1	1

Fig. 3 First stage attack and defense evolutionary trajectories

Fig. 4 Second stage attack and defense evolutionary trajectories

Fig. 5 Third stage attack and defense evolutionary trajectories

Fig. 6 Fourth stage attack and defense evolutionary trajectories

Fig. 7 Fifth stage attack and defense evolutionary trajectories

Fig. 8 Comparison of benefit between different strategies

References 22

1	LIN H Q， YAN Z， CHEN Y， et al. A survey on network security-related data collection technologies［J］. IEEE Access， 2018， 6： 18345-18365. 10.1109/access.2018.2817921
2	NASH J F， Jr. Equilibrium points in n-person games［J］. Proceedings of the National Academy of Sciences of the United States of America， 1950， 36（1）： 48-49. 10.1073/pnas.36.1.48
3	汪贤裕，肖玉明. 博弈论及其应用［M］. 2版. 北京：科学出版社， 2016： 4-55.
	WANG X Y， XIAO Y M. Game Theory and Its Application［M］. 2nd ed. Beijing： Science Press， 2016：4-55.
4	张晓玉，李振邦. 移动目标防御技术综述［J］. 通信技术， 2013， 46（6）：111-113. 10.3969/j.issn.1002-0802.2013.06.033
	ZHANG X Y， LI Z B. Overview of moving target defense technology［J］. Communication Technology， 2013， 46（6）：111-113. 10.3969/j.issn.1002-0802.2013.06.033
5	LYE K W， WING J M. Game strategies in network security［J］. International Journal of Information Security， 2005， 4（1/2）： 71-86. 10.1007/s10207-004-0060-x
6	林旺群，王慧，刘家红，等. 基于非合作动态博弈的网络安全主动防御技术研究［J］. 计算机研究与发展， 2011， 48（2）： 306-316.
	LIN W Q， WANG H， LIU J H， et al. Research on active defense technology of network security based on non-cooperative dynamic game theory［J］. Journal of Computer Research and Development， 2011， 48（2）： 306-316.
7	姜伟，方滨兴，田志宏，等. 基于攻防随机博弈模型的防御策略选取研究［J］. 计算机研究与发展， 2010， 47（10）：1714-1723.
	JIANG W， FANG B X， TIAN Z H， et al. Research on defense strategies selection based on attack-defense stochastic game model［J］. Journal of Computer Research and Development， 2010， 47（10）： 1714-1723.
8	王元卓，林闯，程学旗，等. 基于随机博弈模型的网络攻防量化分析方法［J］. 计算机学报， 2010， 33（9）：1748-1762. 10.3724/sp.j.1016.2010.01748
	WANG Y Z， LIN C， CHENG X Q， et al. Analysis for network attack-defense based on stochastic game model［J］. Chinese Journal of Computers， 2010， 33（9）： 1748-1762. 10.3724/sp.j.1016.2010.01748
9	THEODORAKOPOULOS G， BARAS J S. Game theoretic modeling of malicious users in collaborative networks［J］. IEEE Journal on Selected Areas in Communications， 2008， 26（7）： 1317-1327. 10.1109/jsac.2008.080928
10	王增光，卢昱，李玺. 基于不完全信息博弈的军事信息网络主动防御策略选取［J］. 兵工学报， 2020， 41（3）： 608-617. 10.3969/j.issn.1000-1093.2020.03.022
	WANG Z G， LU Y， LI X. Active defense strategy selection of military information network based on incomplete information game［J］. Acta Armamentarii， 2020， 41（3）： 608-617. 10.3969/j.issn.1000-1093.2020.03.022
11	弭乾坤，吴斌，杜宁，等. 基于不完全信息博弈模型的信息系统安全风险评估方法［J］. 计算机与现代化， 2019（4）： 118-126. 10.3969/j.issn.1006-2475.2019.04.022
	MI Q K， WU B， DU N， et al. Information system security risk assessment based on incomplete information game model［J］. Computer and Modernization， 2019（4）： 118-126. 10.3969/j.issn.1006-2475.2019.04.022
12	LEI C， ZHANG H Q， WAN L M， et al. Incomplete information Markov game theoretic approach to strategy generation for moving target defense［J］. Computer Communications， 2018， 116： 184-199. 10.1016/j.comcom.2017.12.001
13	MALEKI H， VALIZADEH S， KOCH W， et al. Markov modeling of moving target defense games［C］// Proceedings of the 2016 ACM Workshop on Moving Target Defense. New York： ACM， 2016： 81-92. 10.1145/2995272.2995273
14	LI Z M， CHEN X， ZHANG Y， et al. Fuzzy mathematics and game theory based D2D multicast network construction［J］. Journal of Systems Engineering and Electronics， 2019， 30（1）： 13-21. 10.21629/jsee.2019.01.02
15	GHOSH D， SHARMA A， SHUKLA K K， et al. Globalized robust Markov perfect equilibrium for discounted stochastic games and its application on intrusion detection in wireless sensor networks： part I — theory［J］. Japan Journal of Industrial and Applied Mathematics， 2020， 37（1）： 283-308. 10.1007/s13160-019-00397-9
16	黄健明，张恒巍. 基于随机演化博弈模型的网络防御策略选取方法［J］. 电子学报， 2018， 46（9）：2222-2228. 10.3969/j.issn.0372-2112.2018.09.025
	HUANG J M， ZHANG H W. A method for selecting defense strategies based on stochastic evolutionary game model［J］. Acta Electonica Sinica， 2018， 46（9）： 2222-2228. 10.3969/j.issn.0372-2112.2018.09.025
17	MOORE D， SHANNON C， VOELKER G M， et al. Internet quarantine： requirements for containing self-propagating code［C］// Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway： IEEE， 2003： 1901-1910. 10.1109/infcom.2003.1209180
18	ZHANG N B. Defensive strategy selection based on attack-defense game model in network security［J］. International Journal of Performability Engineering， 2018， 14（11）： 2633-2642.
19	黄健明，张恒巍. 基于改进复制动态演化博弈模型的最优防御策略选取［J］. 通信学报， 2018， 39（1）：170-182. 10.11959/j.issn.1000-436x.2018010
	HUANG J M， ZHANG H W. Improving replicator dynamic evolutionary game model for selecting optimal defense strategies［J］. Journal on Communications， 2018， 39（1）：170-182. 10.11959/j.issn.1000-436x.2018010
20	蒋侣，张恒巍，王晋东. 基于多阶段Markov信号博弈的移动目标防御最优决策方法［J］. 电子学报， 2021， 49（3）：527-535. 10.12263/DZXB.20191070
	JIANG L， ZHANG H W， WANG J D. A Markov signaling game-theoretic approach to moving target defense strategy selection［J］. Acta Electonica Sinica， 2021， 49（3）：527-535. 10.12263/DZXB.20191070
21	谭晶磊，张恒巍，张红旗，等. 基于Markov时间博弈的移动目标防御最优策略选取方法［J］. 通信学报， 2020， 41（1）：42-52. 10.11959/j.issn.1000-436x.2020003
	TAN J L， ZHANG H W， ZHANG H Q， et al. Optimal strategy selection approach of moving target defense based on Markov time game［J］. Journal on Communications， 2020， 41（1）：42-52. 10.11959/j.issn.1000-436x.2020003
22	GORDON L A， LOEB M P， LUCYSHYN W S， et al. The 2005 CSI/FBI computer crime and security survey［J］. Computer Security Journal， 2005， 21（3）： 1-22.

[1]	Fangxing GENG, Zhuo LI, Xin CHEN. Incentive mechanism design for hierarchical federated learning based on multi-leader Stackelberg game [J]. Journal of Computer Applications, 2023, 43(11): 3551-3558.
[2]	ZHENG Wanbo, CHEN Huimin, WU Yanqing, XIA Yunni. Simulation of information sharing strategy based on emergency rescue [J]. Journal of Computer Applications, 2023, 43(1): 306-311.
[3]	GONG Ying, HE Yanting, CAO Cejun. Co-evolutionary simulation regarding emergency logistics in major public health risk governance [J]. Journal of Computer Applications, 2021, 41(9): 2754-2760.
[4]	LI Congdong, HUANG Hao, ZHANG Fanshun. Knowledge sharing behavior incentive mechanism for lead users based on evolutionary game [J]. Journal of Computer Applications, 2021, 41(6): 1785-1791.
[5]	Ying LEI, Wanbo ZHENG, Wei WEI, Yunni XIA, Xiaobo LI, Chengwu LIU, Hong XIE. Task offloading method based on probabilistic performance awareness and evolutionary game strategy in “cloud + edge” hybrid environment [J]. Journal of Computer Applications, 2021, 41(11): 3302-3308.
[6]	WANG Yueping, XU Tao. User association mechanism based on evolutionary game [J]. Journal of Computer Applications, 2020, 40(5): 1392-1396.
[7]	WANG Xilong, WANG Jicheng, LUO Cheng, TIAN Xiuxia. Evolutionary game model under synergistic effect of time scale and selection preference [J]. Journal of Computer Applications, 2019, 39(6): 1824-1828.
[8]	ZHANG Chuanhao, GU Xuehui, MENG Caixia. Anti-sniffering attack method based on software defined network [J]. Journal of Computer Applications, 2018, 38(11): 3258-3262.
[9]	LIU Baojian, ZHANG Xiaoyi, LI Qing. Evolutionary game theory based clustering algorithm for multi-target localization in wireless sensor network [J]. Journal of Computer Applications, 2016, 36(8): 2157-2162.
[10]	WANG Yingjie, CAI Zhipeng, TONG Xiangrong, PAN Qingxian, GAO Yang, YIN Guisheng. Online incentive mechanism based on reputation for mobile crowdsourcing system [J]. Journal of Computer Applications, 2016, 36(8): 2121-2127.
[11]	XU Xiaoqiong, ZHOU Zhaorong, MA Xiaoxia, YANG Liu. Cooperative behavior based on evolutionary game in delay tolerant networks [J]. Journal of Computer Applications, 2016, 36(2): 483-487.
[12]	LIU Dafu, SU Yang, XIE Hong'an, YANG Kai. Analysis of evolutionary game on client's evaluation strategy selection in e-commerce [J]. Journal of Computer Applications, 2016, 36(12): 3269-3273.
[13]	XU Ming LIU Guang-zhong. Burst detection algorithm for data streams in three dimensional under water acoustic sensor networks [J]. Journal of Computer Applications, 2012, 32(12): 3544-3547.