# Grey-Box Fuzzing Based on Reinforcement Learning for XSS Vulnerabilities
## 4 Methodology
### Reinforcement Learning Model
#### 4.3.1 Model  
There are two important objects in reinforcement learning: agent and environment. The agent continuously interacts with the environment by \"perceiving the current state\(\rightarrow\) executing the corresponding action\(\rightarrow\)obtaining the corresponding reward\(\rightarrow\)adjusting the current policy\". The goal of reinforcement learning is to find the best policy \(\pi\), so that the agent can obtain the maximum reward by acting according to the policy \(\pi\). Reinforcement learning algorithms are divided into value-based models and probability-based models, represented by Q-learning [34] and Policy Gradient [35]. The critical idea of Q-learning is to build a Q-table to record the expected reward value \(Q(s,a)\) that the agent will obtain when choosing action \(a\) in state \(s\). The agent chooses the action with the largest reward according to the Q-table in each interaction step. In Q-learning, the update formula of the \(Q\) value is  
\[Q(s,a)=Q(s,a)+\alpha\big{(}r+\gamma Q\big{(}s^{\prime},a^{\prime}\big{)}-Q(s, a)\big{)} \tag{6}\]  
where \(s\) is the current state of the agent, \(a^{\prime}\) is the action the agent chooses in the next state \(s^{\prime}\), \(r\) is the reward the agent obtains from state \(s\) to state \(s^{\prime}\), \(\alpha\) is the learning rate, and \(\gamma\) is the discount factor of the reward value. \(Q(s,a)\) is the \(Q\) value of the current state, and the estimated value of \(Q\) is represented by \(r+\gamma*\max Q(s^{\prime},a^{\prime})\), which is updated by learning the error between these two \(Q\). When the Q-table is too large, it takes time and space to search for and store the \(Q\) value. To solve this problem, [PERSON] et al. [36] used a neural network to simulate a Q-table and proposed the deep Q-network (DQN) to avoid dimension explosion caused by a complex environment. There are two neural networks with the same structure but different parameters in the DQN: the prediction network and the target network. The \(Q(s,a;\theta^{pre})\) of the prediction network is used to predict the \(Q\) of action of the current state. The \(Q(s,a;\theta^{tar})\) of the target network is used to calculate the \(Q\) estimated \(Q_{target}\), the calculation formula is  
\[Q_{target}=r+\gamma*maxQ\big{(}s^{\prime},a^{\prime};\theta^{tar}\big{)} \tag{7}\]  
where \(\theta\) is the parameters of the neural network. In the beginning, the prediction network and target network parameters are the same. During training, the parameters of the prediction network are updated in real time through gradient descent, and the parameters are assigned to the target network every step \(c\). The training samples of the prediction network are obtained from the experience pool, which records the trace \(\{s,a,r,s^{\prime}\}\) generated by the interaction between the agent and the environment. During training, a small batch of data is randomly sampled from the experience pool to update the network parameters. This process is called experience replay. Experience replay eliminates the correlation of adjacent samples, improves the utilization of samples, and makes the neural network easy to converge. In the DQN, the maximization operation of calculating \(Q_{tar}\) tends to overestimate the value of an action, and double Q-learning (DDQN) [37] eliminates overestimation by improving the \(Q_{tar}\) calculation. DDQN also has two Q-networks. It first uses the prediction network to select the action a\({}^{max}\) with the largest \(Q\) in the next state \(s^{\prime}\), and then obtains the \(Q\big{(}s^{\prime},a^{max};\theta^{tar}\big{)}\) corresponding to the action \(a^{max}\) through the target network. The value is not necessarily equal to \(max\ Q\big{(}s^{\prime},a^{max};\theta^{tar}\big{)}\), so DDQN can avoid selecting overestimated actions, which makes the calculated \(Q_{tar}\) as close as possible to the real value.