Computer Science ›› 2019, Vol. 46 ›› Issue (12): 165-173.doi: 10.11896/jsjkx.190400092

• Information Security • Previous Articles     Next Articles

Extended Attack Graph Generation Method Based on Knowledge Graph

YE Zi-wei, GUO Yuan-bo, LI Tao, JU An-kang   

  1. (The Third Institute,Information Engineering University,Zhengzhou 450001,China)
  • Received:2019-04-17 Online:2019-12-15 Published:2019-12-17

Abstract: Existing attack graph generation and analysis techniques mainly depend on vulnerability scores.External factors such as hardware and software cann’t be considered to judge their impact and correct vulnerability scores.As a result,generated attack graph is difficult to accurately reflect the real risk of nodes and attack paths.Information extraction and knowledge reasoning in knowledge graph technique are effective means to integrate vulnerability information acquired by multiple sources,and can be used to calculate the risk of nodes and attack paths more accurately in the network.Firstly,knowledge graph based on atomic attack ontology is designed to extend the input and display information of attack graph.Then,an extended attack graph generation framework based on knowledge graph is proposed.On this basis,the attack graph generation algorithm and calculation of attack success rate and attack profit are given,so as to achieve a more comprehensive and accurate evaluation of vulnerabilities.Finally,experimental results verify the effectiveness of proposed method.

Key words: Attack graph, Knowledge graph, Attack success rate, Attack profit, Risk assessment

CLC Number: 

  • TP393
[1] JHA S,SHEYNER O,WING J.Two formal analyses of attack graphs[C]//Proceedings 15th IEEE Computer Security Foundations Workshop(CSFW-15).IEEE,2002:49-63.
[2] SHEYNER O,HAINES J,JHA S,et al.Automated generation and analysis of attack graphs[C]//IEEE Symposium on Security and Privacy.IEEE,2002:273-284.
[3] WANG L,NOEL S,JAJODIA S.Minimum-cost network harde- ning using attack graphs [J].Computer Communications,2006,29(18):3812-3824.
[4] CHEN F,MAO H D,ZHANG W M,et al.Survey of attack graph technique [J].Computer Science,2011,38(11):12-18.(in Chinese)陈铎,毛捍东,张维明,等.攻击图技术研究进展[J].计算机科学,2011,38(11):12-18.
[5] WANG S,ZHANG Z,KADOBAYASHI Y.Exploring attack graph for cost-benefit security hardening:a probabilistic approach[J].Computers & Security,2013,32(1):158-169.
[6] HONG J,KIM D S.Harms:hierarchical attack representation models for network security analysis[C]//The 10th Australian Information Security Management Conference.Western Australia,2012:1-8.
[7] KOTENKO I,STEPASHKIN M.Attack graph based evaluation of network security[C]//IFIP International Conference on Communications and Multimedia Security.Springer Berlin Heidelberg,2006:216-227.
[8] WANG L,ISLAM T,LONG T,et al.An attack graph-based probabilistic security metric[C]//IFIP Annual Conference on Data and Applications Security and Privacy.Springer Berlin Heidelberg,2008:283-296.
[9] LIU Q,ZHANG Y.VRSS:A new system for rating and scoring vulnerabilities[J].Computer Communications,2011,34(3):264-273.
[10] LEI K,ZHANG Y,WU C.A system for scoring the exploitability of vulnerability based types [J].Journal of Computer Research and Development,2017,54(10):2296-2309.
[11] LIAO D,ZHOU M,LIU D,et al.Assessment method of automatic optimizing CVSS v2.0 vulnerability indicators [J].Computer Engineering and Applications,2015,51(2):103-107.
[12] OU X,BOYER W F,MCQUEEN M A.A scalable approach to attack graph generation[C]//The 13th ACM Conference on Computer and Communications Security.ACM,2006:336-345.
[13] RICK V H.A framework for the motivation of attackers in attack tree analysis [D].Holland,Delft:Delft University of Technology,2015.
[14] WANG L,JAJODIA S,SINGHAL A,et al.k-Zero day safety:measuring the security risk of networks against unknown attacks[J].Lecture Notes in Computer Science,2010,11(1):573-587.
[15] WANG L,JAJODIA S,SINGHAL A,et al.k-Zero day safety:a network security metric for measuring the risk of unknown vulnerabilities[J].IEEE Transactions on Dependable & Secure Computing,2014,11(1):30-44.
[16] WANG L,ZHANG M,JAJODIA S,et al.Modeling network diversity for evaluating the robustness of networks against zero-day attacks[C]//European Symposium on Research in ComputerSecurity.Springer International Publishing,2014:494-511.
[17] ZHANG M,WANG L,JAJODIA S,et al.Network diversity:a security metric for evaluating the resilience of networks against zero-day attacks[J].IEEE Transactions on Information Forensics & Security,2016,11(5):1071-1086.
[18] FADLALLAH A,SBEITY H,MALLI M,et al.Application of attack graphs in intrusion detection systems:an implementation[J].International Journal of Computer Networks,2016,8(1):1-12.
[19] AHMADINEJAD S H,JALILI S,ABADI M.A hybrid model for correlating alerts of known and unknown attack scenarios and updating attack graphs[J].Computer Networks,2011,55(9):2221-2240.
[20] LIU W X,ZHENG K F,WU B,et al.Alert processing based on attack graph and multi-source analyzing[J].Journal on Communications,2015,36(9):135-144.
[21] WU Y B,YANG F,LAI G H,et al.Research progress of know- ledge graph learning and reasoning[J].Journal of Chinese Mini-Micro Computer Systems,2016,37(9):2007-2013.(in Chinese)吴运兵,杨帆,赖国华,等.知识图谱学习和推理研究进展[J].小型微型计算机系统,2016,37(9):2007-2013.
[22] LI H,WANG Y,CAO Y.Searching forward complete attack graph generation algorithm based on hypergraph partitioning[J].Procedia Computer Science,2017,107(5):27-38.
[23] PIETERS W,DAVARYNEJAD M.Calculating adversarial risk from attack trees:Control strength and probabilistic attackers[M]//Data Privacy Management,Autonomous Spontaneous Security,and Security Assurance.Springer International Publishing,2015:201-215.
[24] ZHANG S J,LI J H,SONG S S,et al.Using Bayesian inference for computing attack graph node beliefs[J].Journal of Software,2010,21(9):2376-2386.
[25] FRIGAULT M,WANG L.Measuring network security using Bayesian network-based attack graphs[C]//The 3rd IEEE International Workshop on Security,Trust,and Privacy for Software Applications.IEEE,2008:698-703.
[26] POOLSAPPASIT N,DEWRI R,RAY I.Dynamic security risk management using bayesian attack graphs[J].IEEE Transactions on Dependable & Secure Computing,2011,9(1):61-74.
[27] FANG Y,YIN X C,LI J Z.Research of quantitative network security assessment based on Bayesian-attack graphs[J].Application Research of Computers,2013,30(9):2763-2766.
[28] MIEHLING E,RASOULI M,TENEKETZIS D.Optimal de- fense policies for partially observable spreading processes on Bayesian attack graphs[C]//The Second ACM Workshop on Moving Target Defense.ACM,2015:67-76.
[29] DURKOTA K,LISY V,BOSANSKY B,et al.Optimal network security hardening using attack graph games[C]//Twenty-Fourth International Joint Conference on Artificial Intelligence.2015:7-14.
[30] ABRAHAM S,NAIR S.Predictive cyber security analytics framework:a non-homogenous markov model for security quantification[J].Journal of Communications,2014,12(9):899-907.
[31] JIA Y,QI Y,SHANG H,et al.A practical approach to constructing a knowledge graph for cybersecurity[J].Engineering,2018,4(1):53-60.
[32] LIANG Z,ZHOU J K,ZHU H,et al.Research on Aggregation Technology for Information Security Knowledge Based on Security Ontology[J].Netinfo Security,2017,196(4):78-85.(in Chinese)梁中,周嘉坤,朱汉,等.基于安全本体的信息安全知识聚合技术研究[J].信息网络安全,2017,196(4):78-85.
[33] IANNACONE M,BOHN S,NAKAMURA G,et al.Developing an ontology for cyber security knowledge graphs[C]//Cyber and Information Security Research Conference.ACM,2015:12.
[34] ASAMOAH C,TAO L,GAI K,et al.Powering filtration process of cyber security ecosystem using knowledge graph[C]//IEEE International Conference on Cyber Security and Cloud Computing.IEEE,2016:240-246.
[35] NADEAU D,SEKINE S.A survey of named entity recognition and classification[J].Lingvisticae Investigations,2007,30(1):3-26.
[36] LAO N,MITCHELL T,COHEN W W.Random walk inference and learning in a large scale knowledge base[C]//Conference on Empirical Methods in Natural Language Processing.2012:529-539.
[37] BENGIO Y,DUCHARME R,VINCENT P,et al.A neural probabilistic language model[J].Journal of Machine Learning Research,2003,3(2):1137-1155.
[38] MNIH A,HINTON G.Three new graphical models for statistical language modelling[C]//Proceedings of the24th International Conference on Machine Learning.ACM,2007:641-648.
[39] YE Z W,GUO Y B,WANG C D,et al.Survey on application of attack graph technology[J].Journal on Communications,2017,38(11):125-136.(in Chinese)叶子维,郭渊博,王宸东,等.攻击图技术应用研究综述[J].通信学报,2017,38(11):125-136.
[40] CHEN X,FANG B,TAN Q.Inferring attack intent of malicious insider based on probabilistic attack graph model[J].Chinese Journal of Computers,2014,37(1):62-72.
[41] TANJA B,MARCOS K,HEIKO S,et al.Using natural lan- guage processing to enable in-depth analysis of clinical messages posted to an internet mailing sist:a feasibility study[J].Journal of Medical Internet Research,2011,13(4):e98.
[42] FINKEL J R,GRENAGER T,MANNING C.Incorporating non-local information into information extraction systems by Gibbs sampling[C]//Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics.Association for Computational Linguistics,2005:363-370.
[1] BAI Xue, Nurbol and WANG Ya-dong. Map Analysis for Research Status and Development Trend on Network Security Situational Awareness [J]. Computer Science, 2020, 47(6A): 340-343.
[2] LI Xin-chao, LI Pei-feng, ZHU Qiao-ming. Knowledge Graph Representation Based on Improved Vector Projection Distance [J]. Computer Science, 2020, 47(4): 189-193.
[3] XIANG Ying, FENG Jun, XIA Pei-pei, LU Jia-min. Extraction of Water Conservancy Spatial Relationship Words Based on Bootstrapping [J]. Computer Science, 2020, 47(12): 131-138.
[4] XIAO Yong, QIAN Bin, ZHOU Mi. Cross-media Knowledge Graph Construction for Electric Power Metering Based on Semantic Correlation [J]. Computer Science, 2020, 47(11A): 126-131.
[5] ZHANG Chun-xia, PENG Cheng, LUO Mei-qiu, NIU Zhen-dong. Construction of Mathematics Course Knowledge Graph and Its Reasoning [J]. Computer Science, 2020, 47(11A): 573-578.
[6] LI Zhong-wen, DING Ye, HUA Zhong-yun, LI Jun-yi, LIAO Qing. Knowledge Graph Completion Model Based on Triplet Importance Integration [J]. Computer Science, 2020, 47(11): 231-236.
[7] CHEN Xiao-jun, XIANG Yang. Construction and Application of Enterprise Risk Knowledge Graph [J]. Computer Science, 2020, 47(11): 237-243.
[8] CHEN Xiao-jun, XIANG Yang. STransH:A Revised Translation-based Model for Knowledge Representation [J]. Computer Science, 2019, 46(9): 184-189.
[9] YAN Gong-da, DONG Peng, WEN Hao-lin. Simulation Modeling of Complex Engineering Project Schedule Risk AssessmentBased on Multi Agent [J]. Computer Science, 2019, 46(6A): 523-526.
[10] GUANJian, WANG Jing-bin, BIAN Qian-hong. Multi-keyword Streaming Parallel Retrieval Algorithm Based on Urban Security Knowledge Graph [J]. Computer Science, 2019, 46(2): 35-41.
[11] SUN Wen-ping, CHANG Liang, BIN Chen-zhong, GU Tian-long, SUN Yan-peng. Travel Route Recommendation Based on Knowledge Graph and Frequent Sequence Mining [J]. Computer Science, 2019, 46(2): 56-61.
[12] ZHAN Xiong, GUO Hao, HE Xiao-yun, LIU Zhou-bin, SUN Xue-jie, CHEN Hong-song. Research on Security Risk Assessment Method of State Grid Edge Computing Information System [J]. Computer Science, 2019, 46(11A): 428-432.
[13] YANG De-jie, ZHANG Ning, YUAN Ji, BAI Lu. Individual Credit Risk Assessment Based on Stacked Denoising Autoencoder Networks [J]. Computer Science, 2019, 46(10): 7-13.
[14] YIN Liang,HE Ming-li,XIE Wen-bo,CHEN Duan-bing. Process Modeling on Knowledge Graph of Equipment and Standard [J]. Computer Science, 2018, 45(6A): 502-505.
[15] XU Bing-feng, HE Gao-feng. Penetration Testing Method for Cyber-Physical System Based on Attack Graph [J]. Computer Science, 2018, 45(11): 143-148.
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[8] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[9] YANG Yu-qi, ZHANG Guo-an and JIN Xi-long. Dual-cluster-head Routing Protocol Based on Vehicle Density in VANETs[J]. Computer Science, 2018, 45(4): 126 -130 .
[10] SHI Chao, XIE Zai-peng, LIU Han and LV Xin. Optimization of Container Deployment Strategy Based on Stable Matching[J]. Computer Science, 2018, 45(4): 131 -136 .