A Stochastic Game Model for Host Scanning and Anti-Scanning

doi:10.3969/j.issn.1671-1122.2026.06.010

Abstract

Abstract:

In the field of cyber space mapping and anti-mapping, attackers mostly use the batch scanning strategy based on breadth-first search to detect online active hosts and identify potential malicious targets. Defenders mainly adopt the method of setting network traffic thresholds to identify malicious scanning behaviors. However, due to the dynamic and ever-changing nature of the network environment and the flexibility of opponents’ strategic adjustments, traditional static strategies have serious deficiencies in dynamic adaptability. To address this issue, this study designed a stochastic game model for host scanning and anti-scanning. It transformed the continuous grouped scanning process into a Markov decision process, precisely depicting the evolutionary mechanism of the dynamic strategies of both sides. By using the improved asymmetric Nash Q-learning algorithm, the approximate equilibrium solution was successfully obtained. Experimental results show that the dynamic strategy adopted under equilibrium conditions has significant advantages in terms of comprehensive benefits compared with traditional fixed strategies.

Key words: host liveness detection, packet scanning, traffic detection, threshold setting, stochastic game

CLC Number:

TP309

XIE Xiaomin, LI Pengdeng, LIU Yuan, TIAN Zhihong. A Stochastic Game Model for Host Scanning and Anti-Scanning[J]. Netinfo Security, 2026, 26(6): 967-976.

Figures/Tables 9

References 24

[1]	ZOU Zhenwan, HOU Yingsa, GUO Qingrui. Research on Cyberspace Surveying and Mapping Technology Based on Asset Detection[C]// IEEE. 2024 IEEE 6th Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC). New York: IEEE, 2024: 946-949.
[2]	XUE Xiangyang, ZOU Hong, ZHAO Jin, et al. Advances in Anti-Surveying-and-Mapping Theory and Technologies for Data Infrastructure[J]. Strategic Study of CAE, 2025, 27(1): 72-87.
	薛向阳, 邹宏, 赵进, 等. 数据基础设施抗测绘理论与技术发展研究[J]. 中国工程科学, 2025, 27(1): 72-87.
[3]	DURUMERIC Z, BAILEY M, HALDERMAN J A. An {Internet-Wide} View of {Internet-Wide} Scanning[C]// USENIX. The 23rd USENIX Conference on Security Symposium. Berkeley: USENIX, 2014: 65-78.
[4]	SHENG Chuan, YAO Yu, ZHAO Lianxiang, et al. Scanner-Hunter: An Effective ICS Scanning Group Identification System[J]. IEEE Transactions on Information Forensics and Security, 2024, 19: 3077-3092.
[5]	CASWELL B, FOSTER J C, RUSSELL R, et al. Snort 2.0 Intrusion Detection[M]. Rockland: Syngress Publishing, 2003.
[6]	SHAPLEY L S. Stochastic Games[J]. Proceedings of the National Academy of Sciences of the United States of America (PNAS), 1953, 39(10): 1095-1100.
[7]	BITIRGEN K, FILIK U B. Markov Game Based on Reinforcement Learning Solution against Cyber-Physical Attacks in Smart Grid[EB/OL]. (2024-12-01)[2025-05-13]. https://www.sciencedirect.com/science/article/abs/pii/S095741742401474X
[8]	HU Junling, WELLMAN M P. Nash Q-Learning for General-Sum Stochastic Games[J]. Journal of Machine Learning Research, 2003(4): 1039-1069.
[9]	LEONARD D, LOGUINOV D. Demystifying Service Discovery: Implementing an Internet-Wide Scanner[C]// ACM. The 10th ACM SIGCOMM Conference on Internet Measurement. New York: ACM, 2010: 109-122.
[10]	LEONARD D, YAO Zhongmei, WANG Xiaoming, et al. Stochastic Analysis of Horizontal IP Scanning[C]// IEEE. 2012 Proceedings IEEE INFOCOM. New York: IEEE, 2012: 2077-2085.
[11]	ALI M Q, AL-SHAER E, SAMAK T. Firewall Policy Reconnaissance: Techniques and Analysis[J]. IEEE Transactions on Information Forensics and Security, 2014, 9(2): 296-308.
[12]	LEE C B, ROEDEL C, SILENOK E. Detection and Characterization of Port Scan Attacks[EB/OL]. (2003-06-18)[2025-05-13]. https://www.semanticscholar.org/paper/Detection-and-Characterization-of-Port-Scan-Attacks-Lee-Roedel/8830f1780bd7da10fd6090346b83d17fc9b09c97
[13]	RICHTER P, SMARAGDAKIS G, PLONKA D, et al. Beyond Counting: New Perspectives on the Active IPv4 Address Space[C]// ACM. The 2016 Internet Measurement Conference. New York: ACM, 2016: 135-149.
[14]	STANIFORD S, PAXSON V, WEAVER N. How to Own the Internet in Your Spare Time[EB/OL]. (2002-08-05)[2025-05-13]. https://www.researchgate.net/publication/238280597_Nicholas_Weaver_How_to_0wn_the_Internet_in_Your_Spare_Time
[15]	WANG Pinghui, ZHENG Qinghua, NIU Guolin, et al. Port Scan Detection Algorithms Based on Statistical Traffic Features[J]. Journal on Communications, 2007(12): 14-18.
	王平辉, 郑庆华, 牛国林, 等. 基于流量统计特征的端口扫描检测算法[J]. 通信学报, 2007(12): 14-18.
[16]	SAGATOV E S, MAYHOUB S, SUKHOV A M, et al. Proactive Detection for Countermeasures on Port Scanning Based Attacks[C]// IEEE. 2021 17th International Conference on Network and Service Management (CNSM). New York: IEEE, 2021: 402-406.
[17]	AFFINITO A, BOTTA A, GALLO L, et al. Spark-Based Port and Net Scan Detection[C]// ACM. The 35th Annual ACM Symposium on Applied Computing. New York: ACM, 2020: 1172-1179.
[18]	PATEL S K, SONKER A. Rule-Based Network Intrusion Detection System for Port Scanning with Efficient Port Scan Detection Rules Using Snort[J]. International Journal of Future Generation Communication and Networking, 2016, 9(6): 339-350.
[19]	VUGRIN E D, CRUZ J, REEDY C, et al. Cyber Threat Modeling and Validation: Port Scanning and Detection[C]//ACM. The 7th Symposium on Hot Topics in the Science of Security. New York: ACM, 2020: 1-10.
[20]	KIKUCHI H, FUKUNO N, KOBORI T, et al. Automated Port-Scan Classification with Decision Tree and Distributed Sensors[J]. Journal of Information Processing, 2008, 16: 165-175.
[21]	BOUKEBOUS A A E, FETTACHE M I, BENDIAB G, et al. A Comparative Analysis of Snort3 and Suricata[C]// IEEE. 2023 IEEE IAS Global Conference on Emerging Technologies (GlobConET). New York: IEEE, 2023: 1-6.
[22]	NING Zepeng, XIE Lihua. A Survey on Multi-Agent Reinforcement Learning and Its Application[J]. Journal of Automation and Intelligence, 2024, 3(2): 73-91.
[23]	MOGHADDAM A R, KEBRIAEI H. Multiagent Reinforcement Learning for Nash Equilibrium Seeking in General-Sum Markov Games[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2025, 55(1): 221-227.
[24]	HU Jueming, PALIWAL Y, KIM H, et al. Reinforcement Learning with Predefined and Inferred Reward Machines in Stochastic Games[EB/OL]. (2024-09-28)[2025-05-13]. https://www.sciencedirect.com/science/article/abs/pii/S092523122400941X

符号	定义
N	目标主机范围内主机总数
n	攻击者当前已扫描主机数量
m	防御者将合法源地址误报为恶意扫描地址的数量
τ	扫描一组主机所需的时间
t	第t个时间步（表示博弈时间进程）
G	分组总数
T	扫描全部主机所需的总时间步
$s\in S $	各阶段博弈对抗的状态
${{a}_{i}}\in {{A}_{i}},i\in \{\text{att,def}\} $	参与者i的行动
$a_{i}^{*},i\in \{\text{att,def}\} $	参与者i遵循均衡策略 $\pi _{i}^{*} $采取的最优行动
${{d}^{j}},j\in \{0,1,2\} $	博弈状态中，扫描行为被检测成功的标识
${{R}_{i}},i\in \{\text{att,def}\} $	参与者i的收益函数
${{\delta }_{i}},i\in \{\text{att,def}\} $	参与者i的折扣因子（表示耐心程度）
${{U}_{i}},i\in \{\text{att,def}\} $	参与者i的收益函数
${{\pi }_{i}},i\in \{\text{att,def}\} $	参与者i的策略
${{\Pi }_{i}},i\in \{\text{att,def}\} $	参与者i的策略空间
${{g}_{i}},i\in \{\text{0,1,}\cdots \text{,}G\} $	第i个主机分组的编号
${{H}_{i}},i\in \{\text{0,1,}\cdots \text{,}G\} $	第i个主机分组中包含的主机数量
$\pi _{i}^{*},i\in \{\text{att,def}\} $	参与者i的最优均衡策略