# Dynamic Markov Model: Password Guessing Using Probability Adjustment Method
## 2 Related Work
### Other Password Generative Models  
Other password generative models use distinct principles and can achieve a great cracking effect. The PCFG model [20] cuts the password according to the type of character (including letter (\(I\)), number (\(n\)), and special symbol (\(s\))). It counts all generated structures from the training dataset and calculates the probability information during training, eventually uses a queue to generate passwords. [PERSON] adopted keyboard rules in PCFG [43], and could crack extra passwords that obey these rules. [PERSON] conducted deep semantic mining of the letter part, which particularly increased the cracking ability for long passwords [44]. [PERSON] proposed a personal-PCFG model that equally dealt with username, email prefix, and so forth. The reinforced model has better performance especially in target attacks [45]. With the success of deep learning, neural networks that have more capacity and stronger representation ability have attracted attention. [PERSON] generated text using recurrent neural networks, showing that the RNN model has the ability to handle text sequences [46]. [PERSON] took passwords as an extension of human language [21], and first tried to generate passwords in the RNN framework. The RNN generated one character at each time step and used the generated character as the input for the next time step until the terminator appeared or the maximum length was reached. In other studies, RNN [47] was replaced with LSTM [48], promoting the effect of capturing the long-range dependence of characters. [PERSON] devised a PG-RNN that increased the number of neurons, and got competitive results on multiple datasets [34]. The generative adversarial network [15] is currently the best among the generative models, especially in computer vision. PassGAN was introduced in [22] to generate passwords. Then, PassGAN was enhanced [49] to directly learn the probability distribution of the password encoding matrix. After training with the Wasserstein loss function [50; 51], it just needs to provide the generator with random noise sampled in Gaussian distribution, and then the generator outputs the coding matrix of the password. [PERSON] used the relative GAN to improve the loss function, and the performance of GAN in password guessing was greatly improved by multi-source training [52]. In addition, the generator was improved in [53] with recurrent neural networks, which could acquire better generation effect.  
Overall, first, compared with the Markov model, the relatively low speed is an apparent disadvantage for the other models [23]. In the training stage, the PCFG model needs to additionally count structure probability information. For the models based on neural networks, many weight parameters must be trained by the backpropagation algorithm [54]. In the generation stage, the PCFG model has to generate extra structure. The RNN and GAN models contain large scale multiplication operations and activation functions. These complicated operations inevitably slow down inference speed in contrast with random sampling [55]. Second, viewed from the perspective of quality, the PCFG model's straightforward splitting of strings deviates from the actual situation, and models based on neural networks have limit representation ability in passwords [56]. In addition, considering the problem of generating repeated passwords, models based on neural networks usually do not perform satisfactorily if they are not trained well; in particular, the GAN model frequently experiences mode collapse [57]. Statistical machine learning models such as the Markov model and PCFG models, also generate large-scale repeated passwords if the random sampling method is used. In summary, the Markov model has an advantage in terms of comprehensive performance, yet a high repetition rate would be one factor prohibiting the model from cracking efficiently.