Computer Science ›› 2021, Vol. 48 ›› Issue (5): 294-300.doi: 10.11896/jsjkx.200700108

• Information Security • Previous Articles     Next Articles

Attack Path Analysis Method Based on Absorbing Markov Chain

ZHANG Kai1,2,3, LIU Jing-ju1,3   

  1. 1 College of Electronic Engineering,National University of Defense Technology,Hefei 230037,China
    2 Jiuquan Satellite Launch Center,Jiuquan,Gansu 732750,China
    3 Anhui Province Key Laboratory of Cyberspace Security Situation Awareness and Evaluation,Hefei 230037,China
  • Received:2020-07-17 Revised:2020-08-13 Online:2021-05-15 Published:2021-05-09
  • About author:ZHANG Kai,born in 1992,postgraduate.His main research interests include network security situation awareness and so on.(
    LIU Jing-ju,born in 1974,professor.Her main research interests include network security situation awareness and network security detection.

Abstract: The analysis of network attack path from the perspective of attackers is of great significance to guide network security defense.The existing analysis methods based on absorbing Markov chain have some problems,such as incomplete consideration of state transition and unreasonable calculation of state transition probability.In order to solve these problems,this paper proposes an attack path analysis method based on absorbing Markov chain.Based on the generation of attack graph and the exploitability score of vulnerability,the situation that the failure state transition of non-absorbing nodes will be fully considered.In order to map the attack graph to the absorbing Markov chain model,this paper proposes a new method to calculate the state transition probability.Then,by using the properties of the state transition probability matrix of the absorbing Markov chain,it calculates the threat ranking of the nodes in the attack path and the expected length of the attack path.Then,the application feasibility of absorbing Markov chain with multi absorbing states is discussed.The results of the experiment show that the proposed method can effectively calculate the node threat ranking and path length expectation.Through comparative analysis,this method is more in line with the actual situation of network attack and defense than the existing methods.

Key words: Absorbing Markov chain, Attack graph, Attack path analysis, Network security, Node threat ranking, Path length expectation

CLC Number: 

  • TP393.8
[1]HUANG Y H,WU Y F,YANG H P,et al.Graph-based vulnerability assessment for APT attack[J].Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition),2017,29(4):535-541.
[2]YU D,FRINCKE D.Improving the quality of alerts and predicting intruder's next goal with Hidden Colored Petri-Net[J].Computer Networks,2007,51(3):632-654.
[3]WANG S,TANG G M,KOU G,et al.Attack path predictionmethod based on causal knowledge net[J].Journal on Communications,2016(10):198.
[4]LIU Y L,FENG D G,LIAN Y F,et al.Network Situation Prediction Method Based on Spatial-Time Dimension Analysis[J].Journal of Computer Research and Development,2014,51(8):1681-1694.
[5]ZENG S W,WEN Z H,DAI L W,et al.Analysis of Network Security Based on Uncertain Attack Graph Path[J].Computer Science,2017,44(S1):361-365.
[6]KAYNAR K.A taxonomy for attack graph generation and usage in network security[J].Journal of Information Security and Applications,2016,29:27-56.
[7]ZENG J,WU S,CHEN Y,et al.Survey of Attack Graph Analysis Methods from the Perspective of Data and Knowledge Processing[J].Security & Communication Networks,2019,2019(11):1-16.
[8]SHEYNER O,HAINES J,JHA S,et al.Automated Generationand Analysis of Attack Graphs[C]//Proceedings 2002 IEEE Symposium on Security and Privacy.2004.
[9]WANG S,ZHANG Z,KADOBAYASHI Y.Exploring attackgraph for cost-benefit security hardening:A probabilistic approach[J].Computers & Security,2013,32:158-169.
[10]MIEHLING E,RASOULI M,TENEKETZIS D.Optimal De-fense Policies for Partially Observable Spreading Processes on Bayesian Attack Graphs[C]//ACM Workshop on Moving Target Defense.2015.
[11]ABRAHAM S,NAIR S.Cyber security analytics:a stochastic model for security quantification using absorbing markov chains[J].Journal of Communications,2014,9(12):899-907.
[12]ABRAHAM S,NAIR S.A Predictive Framework for Cyber Security Analytics using Attack Graphs[J].International Journal of Computer Networks & Communications,2015,7(1).
[13]FREI S.Security econometrics:The dynamics of (in) security[M].BookSurge Publishing,2009.
[14]HU H,LIU Y L,ZHANG H Q,et al.Route Prediction Method for Network Intrusion Using Absorbing Markov Chain[J].Journal of Computer Research and Development,2018,55(4):831-845.
[15]YE Z W,GUO Y B,WANG C D,et al.Survey on application ofattack graph technology[J].Journal on Communications,2017,38(11):121-132.
[16]GRINSTEAD C M,SNELL J L.Introduction to probability[M].American Mathematical Soc.,2012.
[17]OU X,GOVINDAVAJHALA S,APPEL A W.MulVAL:ALogic-based Network Security Analyzer[C]//USENIX security symposium.2005,8:113-128.
[18]YOUSEFI M,MTETWA N,ZHANG Y,et al.A novel approach for analysis of attack graph[C]//IEEE International Conference on Intelligence and Security Informatics (ISI).IEEE,2017:7-12.
[1] LIU Jie-ling, LING Xiao-bo, ZHANG Lei, WANG Bo, WANG Zhi-liang, LI Zi-mu, ZHANG Hui, YANG Jia-hai, WU Cheng-nan. Network Security Risk Assessment Framework Based on Tactical Correlation [J]. Computer Science, 2022, 49(9): 306-311.
[2] ZHAO Dong-mei, WU Ya-xing, ZHANG Hong-bin. Network Security Situation Prediction Based on IPSO-BiLSTM [J]. Computer Science, 2022, 49(7): 357-362.
[3] DU Hong-yi, YANG Hua, LIU Yan-hong, YANG Hong-peng. Nonlinear Dynamics Information Dissemination Model Based on Network Media [J]. Computer Science, 2022, 49(6A): 280-284.
[4] DENG Kai, YANG Pin, LI Yi-zhou, YANG Xing, ZENG Fan-rui, ZHANG Zhen-yu. Fast and Transmissible Domain Knowledge Graph Construction Method [J]. Computer Science, 2022, 49(6A): 100-108.
[5] LYU Peng-peng, WANG Shao-ying, ZHOU Wen-fang, LIAN Yang-yang, GAO Li-fang. Quantitative Method of Power Information Network Security Situation Based on Evolutionary Neural Network [J]. Computer Science, 2022, 49(6A): 588-593.
[6] LI Jia-rui, LING Xiao-bo, LI Chen-xi, LI Zi-mu, YANG Jia-hai, ZHANG Lei, WU Cheng-nan. Dynamic Network Security Analysis Based on Bayesian Attack Graphs [J]. Computer Science, 2022, 49(3): 62-69.
[7] ZHANG Shi-peng, LI Yong-zhong. Intrusion Detection Method Based on Denoising Autoencoder and Three-way Decisions [J]. Computer Science, 2021, 48(9): 345-351.
[8] CHEN Hai-biao, HUANG Sheng-yong, CAI Jie-rui. Trust Evaluation Protocol for Cross-layer Routing Based on Smart Grid [J]. Computer Science, 2021, 48(6A): 491-497.
[9] YANG Ping, SHU Hui, KANG Fei, BU Wen-juan, HUANG Yu-yao. Generating Malicious Code Attack Graph Using Semantic Analysis [J]. Computer Science, 2021, 48(6A): 448-458.
[10] WANG Jin-heng, SHAN Zhi-long, TAN Han-song, WANG Yu-lin. Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network [J]. Computer Science, 2021, 48(6): 338-342.
[11] LIU Quan-ming, LI Yin-nan, GUO Ting, LI Yan-wei. Intrusion Detection Method Based on Borderline-SMOTE and Double Attention [J]. Computer Science, 2021, 48(3): 327-332.
[12] JIANG Jian-feng, SUN Jin-xia, YOU Lan-tao. Security Clustering Strategy Based on Particle Swarm Optimization Algorithm in Wireless Sensor Network [J]. Computer Science, 2021, 48(11A): 452-455.
[13] WANG Yu-chen, QI Wen-hui, XU Li-zhen. Security Cooperation of UAV Swarm Based on Blockchain [J]. Computer Science, 2021, 48(11A): 528-532.
[14] MA Lin, WANG Yun-xiao, ZHAO Li-na, HAN Xing-wang, NI Jin-chao, ZHANG Jie. Network Intrusion Detection System Based on Multi-model Ensemble [J]. Computer Science, 2021, 48(11A): 592-596.
[15] WU Pei-pei, WU Zhao-xian, TANG Wen-bing. Real-time Performance Analysis of Intelligent Unmanned Vehicle System Based on Absorbing Markov Chain [J]. Computer Science, 2021, 48(11A): 147-153.
Full text



No Suggested Reading articles found!