Abstract: penetration testing offers strong advantages in the discovery of hidden vulnerabilities in a network and assessing network security. However, it can be carried out by only security analysts, which costs considerable time and money. The natural way to deal with the above problem is automated penetration testing, the essential part of which is automated attack planning. Although previous studies have explored various ways to discover attack paths, all of them require perfect network information beforehand, which is contradictory to realistic penetration testing scenarios. To vividly mimic intruders to find all possible attack paths hidden in a network from the perspective of hackers, we propose a network information gain based automated attack planning (NIG-AP) algorithm to achieve autonomous attack path discovery. The algorithm formalizes penetration testing as a Markov decision process and uses network information to obtain the reward, which guides an agent to choose the best response actions to discover hidden attack paths from the intruder’s perspective. Experimental results reveal that the proposed algorithm demonstrates substantial improvement in training time and effectiveness when mining attack paths.

NIG-AP：一种自动化渗透测试新方法

[1]Alexander Pretschner AS, 2017. Automated Attack Planning Using a Partially Observable Model for Penetration Testing of Industrial Control Systems. MS Thesis, Technische Universität München, München, Germany.

[2]Backes M, Hoffmann J, Künnemann R, et al., 2017. Simulated penetration testing and mitigation analysis. https://arxiv.org/abs/1705.05088v1

[3]Baulcombe DC, 1999. Fast forward genetics based on virus-induced gene silencing. Curr Opin Plant Biol, 2(2):109-113.

[4]Beale J, Meer H, van der Walt C, et al., 2004. Nessus Network Auditing: Jay Beale Open Source Security Series. Elsevier, Amsterdam, the Netherlands.

[5]Chad‘es I, Chapron G, Cros MJ, et al., 2014. MDPtoolbox: a multi-platform toolbox to solve stochastic dynamic programming problems. Ecography, 37(9):916-920.

[6]Core Security, 2019. Core Impact Penetration System. https://www.secureauth.com/products/penetration-testing/core-impact [Accessed on Feb. 23, 2019].

[7]Fox M, Long D, 2003. PDDL2.1: an extension to PDDL for expressing temporal planning domains. J Artif Intell Res, 20:61-124.

[8]Futoransky A, Notarfrancesco L, Richarte G, et al., 2010. Building computer network attacks. https://arxiv.org/abs/1006.1916

[9]Holik F, Horalek J, Marik O, et al., 2014. Effective penetration testing with metasploit framework and methodologies. IEEE 15^th Int Symp on Computational Intelligence and Informatics, p.237-242.

[10]Khan S, Parkinson S, 2017. Towards automated vulnerability assessment. 27^th Int Conf on Automated Planning and Scheduling, p.33-40.

[11]Kingma DP, Ba J, 2014. Adam: a method for stochastic optimization. https://arxiv.org/abs/1412.6980

[12]Kurniawati H, Hsu D, Lee WS, 2008. SARSOP: efficient point-based POMDP planning by approximating optimally reachable belief spaces. In: Brock O, Trinkle J, Ramos F (Eds.), Robotics: Science and Systems IV. MIT Press, Massachusetts, USA, Chapter 10.

[13]Lee C, Lee GG, 2006. Information gain and divergence-based feature selection for machine learning-based text categorization. Inform Process Manag, 42(1):155-165.

[14]Liang JY, Shi ZZ, 2004. The information entropy, rough entropy and knowledge granulation in rough set theory. Int J Uncert Fuzzy Knowl Syst, 12(1):37-46.

[15]Mnih V, Kavukcuoglu K, Silver D, et al., 2013. Playing Atari with deep reinforcement learning. https://arxiv.org/abs/1312.5602

[16]Mnih V, Kavukcuoglu K, Silver D, et al., 2015. Human-level control through deep reinforcement learning. Nature, 518(7540):529-533.

[17]Obes JL, Sarraute C, Richarte G, 2013. Attack planning in the real world. https://arxiv.org/abs/1306.4044

[18]Roberts M, Howe A, Ray I, et al., 2011. Personalized vulnerability analysis through automated planning. Proc Int Joint Conf on Artificial Intelligence, p.50-57.

[19]Samant N, 2011. Automated Penetration Testing. MS Thesis, San Jose State University, California, USA.

[20]Sarraute C, Richarte G, Lucángeli Obes J, 2011. An algorithm to find optimal attack paths in nondeterministic scenarios. 4^th ACM Workshop on Security and Artificial Intelligence, p.71-80.

[21]Sarraute C, Buffet O, Hoffmann J, 2012. POMDPs make better hackers: accounting for uncertainty in penetration testing. 26^th AAAI Conf on Artificial Intelligence, p.1816-1824 .

[22]Sarraute C, Buffet O, Hoffmann J, 2013. Penetration testing == POMDP solving? https://arxiv.org/abs/1306.4714

[23]Schneier B, 1999. Attack trees. Dr Dobb's J, 24(12):21-29.

[24]Sheyner O, Haines J, Jha S, et al., 2002. Automated generation and analysis of attack graphs. IEEE Symp on Security and Privacy, p.273-284.

[25]Shmaryahu D, Shani G, Hoffmann J, et al., 2017. Partially observable contingent planning for penetration testing. 1^st Int Workshop on Artificial Intelligence in Security, p.33-40.

[26]Stefinko Y, Piskuzub A, 2017. Theory of modern penetration testing expert system. Inform Process Syst, 148(2):129-133.

[27]Steinmetz M, 2016. Critical constrained planning and an application to network penetration testing. 26^th Int Conf on Automated Planning and Scheduling, p.141-144.

[28]Sutton RS, Barto AG, 1998. Reinforcement Learning: an Introduction. MIT Press, Cambridge, London.

[29]Szepesvári C, 2010. Algorithms for Reinforcement Learning. Morgan & Claypool Publishers, San Rafael, Argentina.

[30]Zhuang YT, Wu F, Chen C, et al., 2017. Challenges and opportunities: from big data to knowledge in AI 2.0. Front Inform Technol Electron Eng, 18(1):3-14.