ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2018, Vol. 55 ›› Issue (4): 831-845.doi: 10.7544/issn1000-1239.2018.20170087

Previous Articles     Next Articles

Route Prediction Method for Network Intrusion Using Absorbing Markov Chain

Hu Hao1,3, Liu Yuling2, Zhang Hongqi1,3, Yang Yingjie1,3, Ye Runguo4   

  1. 1(PLA Information Engineering University, Zhengzhou 450001); 2(Trusted Computing and Information Assurance Laboratory, Institute of Software, Chinese Academy of Sciences, Beijing 100190); 3(Henan Key Laboratory of Information Security, Zhengzhou 450001); 4(China Electronics Standardization Institute, Beijing 100007)
  • Online:2018-04-01

Abstract: Predictions of network intrusion intention and path are very significant for the security administrator to comprehend the possible threat behaviors of attackers deeply. Existing reports mainly focus on the path prediction under the ideal attack scenario. However, the ideal attack paths are not the real-world paths adopted by the intruders entirely. In order to predict the attack path information of network intrusion accurately and comprehensively, a novel route prediction method based on absorbing Markov chain (AMC) is proposed in this paper. Firstly, a normalization algorithm for state transition probability of AMC is designed with the Markov and absorption properties, then the complete attack graph (AG) proved can be mapped into the AMC. In addition, the probability metric for state transition based on common vulnerability scoring system (CVSS) is designed. Finally, the detailed steps for predicting expected number of visits to attack state and expected number of route lengths are further put forward respectively. Experimental analysis results indicate that our method can quantify the probability distribution of routes with different attack lengths, and calculate the expected number of route lengths. Moreover, it can predict the expected number of atomic attacks needed to compromise the attack goal. The predictions can be used in node threat ranking. Hence, our approach provides more guidance for network security protection in response to network attack threat timely.

Key words: intrusion route prediction, attack graph (AG), absorbing Markov chains (AMC), expected route length, node threat ranking

CLC Number: