A Novel Attack Graph Posterior Inference Model Based on Bayesian Network

Shaojun Zhang, Shanshan Song
DOI: 10.4236/jis.2011.21002                

Abstract

Network attack graphs are originally used to evaluate what the worst security state is when a concerned net-work is under attack. Combined with intrusion evidence such like IDS alerts, attack graphs can be further used to perform security state posterior inference (i.e. inference based on observation experience). In this area, Bayesian network is an ideal mathematic tool, however it can not be directly applied for the following three reasons: 1) in a network attack graph, there may exist directed cycles which are never permitted in a Bayesian network, 2) there may exist temporal partial ordering relations among intrusion evidence that can-not be easily modeled in a Bayesian network, and 3) just one Bayesian network cannot be used to infer both the current and the future security state of a network. In this work, we improve an approximate Bayesian posterior inference algorithm–the likelihood-weighting algorithm to resolve the above obstacles. We give out all the pseudocodes of the algorithm and use several examples to demonstrate its benefit. Based on this, we further propose a network security assessment and enhancement method along with a small network scenario to exemplify its usage.

Keywords

Network Security, Attack Graph, Posterior Inference, Bayesian Network, Likelihood-Weighting

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	O. Sheyner, J. Haines, S. Jha, et al., “Automated Generation and Analysis of Attack Graphs,” Proceedings of the 2002 IEEE Symposium on Security and Privacy, Oakland, 12-15 May 2002, pp. 273-284. doi:10.1109/SECPRI.2002. 1004377
[2]	S. Jajodia, S. Noel and B. O’Berry, “Topological Analysis of Network Attack Vulnerability,” Managing Cyber Threats: Issues, Approaches and Challenges, Kluwer Academic Publisher, 2004.
[3]	P. Ammann, D. Wijesekera and S. Kaushik, “Scalable, Graph-Based Network Vulnerability Analysis,” Procee- dings of the 9th ACM Conference on Computer & Communications Security, Washington DC, 2002, pp. 217-224.
[4]	X. Ou, S. Govindavajhala and A. Appel, “MulVAL: A Logic-Based Network Security Analyzer,” Proceedings of the 14th conference on USENIX Security Symposium, Baltimore, 31 July-5 August 2005, pp. 8-23.
[5]	R. Lippmann, K. Ingols, C. Scott, et al., “Validating and Restoring Defense in Depth Using Attack Graphs,” Proceedings of the 2007 IEEE Military Communications Conference, Washington DC, 2006.
[6]	P. Ning and D. Xu, “Learning Attack Strategies from Intrusion Alerts,” Proceedings of the 10th ACM Conference on Computer and Communications Security, Wash- ington DC, October 2003.
[7]	S. Noel, E. Robertson and S. Jajodia, “Correlating Intrusion Events and Building Attack Scenarios through Attack Graph Distances,” Proceedings of the 20th Annual Computer Security Applications Conference, Tucson, December 2004, pp. 350-359. doi:10.1109/SECPRI.2002. 1004377
[8]	L. Wang, A. Liu and S. Jajodia, “Using Attack Graphs for Correlating, Hypothesizing, and Predicting Intrusion Alerts,” Computer Communications, Vol. 29, No. 15, 2006, pp. 2917-2933. doi:10.1016/j.comcom.2006.04.001
[9]	Y. Zhai, P. Ning, P. Iyer, et al., “Reasoning about Complementary Intrusion Evidence,” Proceedings of the 20th Annual Computer Security Applications Conference, Tucson, 6-10 December 2004, pp. 39-48. doi:10.1109/ CSAC.2004.29
[10]	D. Yu and D. Frincke, “Improving the Quality of Alerts and Predicting Intruder’s Next Goal with Hidden Colored Petri-Net,” Computer Networks, Vol. 51, No. 3, 2007, p. 632. doi:10.1016/j.comnet.2006.05.008
[11]	S. Zhang, L. Li, J. Li, et al., “Using Attack Graphs and Intrusion Evidences to Extrapolate Network Security State,” Proceedings of the 4th International Conference on Communications and Networking in China, Guang Zhou, 2009. doi:10.1109/CHINACOM.2009.5339841
[12]	Z. Bhahramani, “An Introduction to Hidden Markov Models and Bayesian Networks,” International Journal of Pattern Recognition and Artificial Intelligence, Vol. 15, No. 1, 2001, pp. 9-42. doi:10.1142/S0218001401000836
[13]	F. Salfner, “Modeling Event-driven Time Series with Generalized Hidden Semi-Markov Models,” Technical Report 208, Department of Computer Science, Humboldt University, Berlin, Germany, 2006.
[14]	F. Jensen, “Bayesian Networks and Decision Graphs,” Statistics for Engineering and Information Science, Springer, 2001.
[15]	K. Korb and A. Nicholson, “Bayesian Artificial Intelligence,” CRC Press, 2003. doi:10.1201/9780203491294
[16]	S. Zhang, J. Li and X. Chen, “Building Network Attack Graph for Aalert Causal Correlation,” Computers & Security, Vol. 27, No. 5-6, 2008, pp. 188-196. doi:10.1016/ j.cose.2008.05.005
[17]	“National Institute of Standards and Technology,” 2010. Common Vulnerability Scoring System. http://nvd.nist.gov/cvss.cfm
[18]	“Open Security Foundation,” 2010. OSVDB: The Open Source Vulnerability Database. http://osvdb.org/