# Network Attack Path Selection and Evaluation Based on Q-Learning
## 1 Introduction  
Smart grid is a typical cyber-physical system (CPS), which uses intelligent terminals such as massive sensors and advanced metering equipment to realize remote monitoring, control, and protection of the grid [1, 2]. Advanced Persistent Threat (APT) attacks use the openness and easy accessibility of smart terminals to invade, carry out multi-step attacks through network security vulnerabilities, and, finally, enter the main station and destroy power production on a large scale [3]. For example, Ukraine suffered a \"Black Energy\" attack in 2015 [4] and there was also Israel's power outage in 2009 [5]. Therefore, predicting the path of a multi-step attack and analyzing the cross-layer risk of the power CPS under the attack will help ensure the safe and stable operation of the power CPS [6]. When attacking, the attacker tends to choose the path with low attack cost and high attack profit to carry out the invasion, as this is the best attack path. The purpose of the best attack path discovery is to analyze the attacking behavior by alert correlation technology, reveal the hidden logic, construct attack scenarios, and then infer the subsequent attack steps of attackers, providing important evidence for active defense of network security [7]. It has been an important method of dealing with the multi-step attacks [8]. Current research is usually static analysis based on experience. Literature used a forward search strategy to find hidden attack paths. Reference [9] adopted heuristic search algorithms to generate attack graphs. Reference [10] proposed pruning attack graph branches to exploit Greedy search strategy finds the attack path. Reference [11] made use of an attack tree and a genetic algorithm to solve the optimal attack path problem, and found the solution through a genetic algorithm. However, the above-mentioned research has high computational complexity and is difficult to apply to large-scale networks. At the same time, it cannot reflect the influence of the different attackers on the path selection. In order to solve the above problems, the Q-Learning algorithm is introduced to discover the best attack path. Q-Learning belongs to a category of semi-supervised learningalgorithms [12]. Because of its simplicity and convergence advantages [13; 14], it has been widely used in various fields of robot path finding and planning [15]. In recent years, it has also begun to be applied in finding attack paths. Reference [16] put forward a Q-Learning method to identify key attack sequences in consideration of physical system behavior, with good results. However, the research mainly focused on network topology attacks, without considering the security vulnerabilities of the network itself. Reference [17] proposed a method of using Q-Learning to analyze the attack path based on the attack graph. However, when quantifying the threat of a network attack, only the benefit of the attack is considered and the attack cost is not considered. There is also a problem of computational efficiency. Based on the above problems, this paper establishes an FPN-Q learning algorithm to find the best attack path. Fuzzy Petri Net (FPN) [18] combines the ability of Petri Net to describe asynchronous concurrency and graphical representation with the fuzzy reasoning ability of fuzzy systems. Therefore, this algorithm uses FPN to model the network attack process with uncertain characteristics, and use the fuzzy inference parameters of FPN to improve the Q-Learning algorithm, which improves the learning efficiency of the algorithm. In addition, considering the attack cost and the attack reward, the attack gain is proposed to quantify the threat of the attack path to the system. In order to evaluate the impact of the discovered best attack path on the real-time operation of the power grid, an information-physical system coupling model is established based on the function of load control, and the risk indicator is proposed.