# Improved Deep Recurrent Q-Network of POMDPs for Automated Penetration Testing
## 2 Preliminary
### Pomdp  
The Markov Decision Process (MDP) is a general framework for modeling sequential decision-making problems and is the theoretical basis of reinforcement learning. In the MDP, the transition of an environment's state is determined by the current state. However, in the real world, environments rarely match the characteristics of MDPs. The Partially Observed Markov Decision Process (POMDP) is a more suitable framework for describing transitions in a real environment. Previously, POMDPs were suggested as a model for PT [11]. POMDPs are usually defined by a tuple \(<\mathcal{S},\mathcal{A},\mathcal{O},\mathcal{T},\mathcal{R},\Omega,b_{0}>\). We combine PT scenarios to explain their specific meaning. The meaning of \(\mathcal{S}\), \(\mathcal{A}\), \(\mathcal{T}\), and \(\mathcal{R}\) are the same as in MDPs. State space \(\mathcal{S}\) describes the information about the environment such as the detected host, exploitable vulnerabilities, and so on. Action space \(\mathcal{A}\) means that the agent possessed the ability to solve the target tasks such as scanning networks, exploiting vulnerabilities, and so on. Transition \(\mathcal{T}(s_{t+1}|a_{t},s_{t})\), the probability of the environment's state transformation, describes how the state of environment changes once the agent has finished its action \(a_{t}\). Reward \(\mathcal{R}(a_{t},s_{t})\) means the value of the results in which the agent interacts with the environment. The agent obtains reward \(r\) after finishing action \(a_{t}\) at state \(s_{t}\). In the process of PT, different nodes have different values. For example, the server containing the database is sensitive and the value of this server is certainly high. If the action fails to succeed, the agent would receive a negative reward. In addition, \(\mathcal{O}\), \(\Omega\), and \(b_{0}\) are unique to POMDPs. Observation \(\mathcal{O}\) is the discrete set of environment observations from the perspective of the agent, and the observation only describes a partial environment, which may be enough to deduce the full information about the environment [12]. The transition of observation \(\Omega(o_{t}|s_{t+1},a_{t})\in[0,1]\) describes the probability corresponding to the current state \(s_{t+1}\) and observation \(o_{t}\) after the agent executes \(a_{t}\). Belief \(b_{0}\) means the initial probability distribution of the state [13]. The belief function \(b_{t+1}(s_{t+1})=Pr(s_{t+1}|o_{t},a_{t},b_{t})\) is a statistic for the history of actions and observations, which shows the probability distribution of the states [14]. The calculation of belief is as follows: \begin{table}
\begin{tabular}{l l l l} \hline \hline
**Type** & **Prerequisites** & **Advantages** & **Disadvantages** \\ \hline \multirow{4}{*}{White-box} & Testers thoroughly & This method saves time & \\  & comprehend the target & and complete testing can & \\  & networks’ logical structures. & be achieved. & \\  & The structures and & & \\  & configurations of target & This method can simulate & \\  & networks are fully unknown & a real attack to find & \\  & to testers, except for the entry & unexpected results and is & \\  & points. & easily understood. & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The Classification of Penetration Testing. \[b_{t+1}(s_{t+1}) =Pr(s_{t+1}|o_{t},a_{t},b_{t}) \tag{1}\] \[=\frac{Pr(o_{t}|s_{t+1},a_{t},b_{t})Pr(s_{t+1}|a_{t},b_{t})}{Pr(o_{t }|a_{t},b_{t})}\] \[=\frac{\Omega(s_{t+1},a_{t},o_{t})\sum_{s\in S}Pr(s_{t+1}|a_{t},b_ {t},s_{t})Pr(s_{t}|a_{t},b_{t})}{Pr(o_{t}|a_{t},b_{t})}\] \[=\frac{\Omega(s_{t+1},a_{t},o_{t})\sum_{s\in S}T(s_{t+1}|a_{t},s_ {t})b(s_{t})}{Pr(o_{t}|a_{t},b_{t})},\]  
in which state \(s\), observation \(o\), and action \(a\) are all the history of the agent in the same training episode. In the POMDP, the agent can only observe part of the environment (the full state of environment is hidden) and chooses an action based on those observations. The goal of the POMDP tasks is to find a policy that has maximum discount rewards.