提升密码猜测模型的性能

# 提升密码猜测模型的性能 ## 1. 改进的 PCFG 提取算法 在密码猜测模型中，为了更有效地提取密码特征，提出了一种改进的概率上下文无关文法（PCFG）提取算法。该算法的输入包括密码 `pw`、单词字典 `D` 和网站名称后缀列表 `web list`，输出是处理后的分段列表 `seg list`。 ```plaintext Algorithm 2: Extraction algorithm for our refined PCFG. Input: Password pw, word dictionary D, website name suffix list web list Output: handled segment list seg list. 1 seg list=[pw]; /* initial list taking the whole password as a unhandled segment. */ 2 kp min=3;/* the minimum length of the keyboard pattern. */ 3 for seg in seg List do 4 if type(seg) == string and a year occurs in seg then 5 begin, end = index year(seg); 6 divide seg(seg, begin, end);/* divide seg into seg[0 : begin], ('Y' + str(end - begin), seg[begin : end]), seg[end :]. */ 7 for seg in seg List do 8 if type(seg) == string and a website suffix from web list occurs in seg then 9 begin, end = index website(seg); 10 divide seg(seg, begin, end);/* divide seg into seg[0 : begin], ('E' + str(end - begin), seg[begin : end]), seg[end :]. */ 11 for seg in seg list do 12 if type(seg) == string and a word from D occurs in seg then 13 begin, end = index word(seg); 14 divide seg(seg, begin, end);/* divide seg into seg[0 : begin], ('W' + str(end - begin), seg[begin : end]), seg[end :]. */ 15 for seg in seg list do 16 if type(seg) == string then 17 begin, end = index keyboard(seg); 18 if end - begin >= kp min and seg[begin : end] contains more than one character type then 19 divide seg(seg, begin, end);/* divide seg into seg[0 : begin], ('K' + str(end - begin), seg[begin : end]), seg[end :]. */ 20 merge unhandled(seg list);/* merge successive unhandled segments in seg list. */ 21 PCFG extraction(seg list);/* use original PCFG for extraction. */ 22 return seg list; ``` 该算法的主要步骤如下： 1. **初始化**：将整个密码作为一个未处理的分段放入 `seg list` 中。 2. **设置键盘模式最小长度**：设定 `kp min` 为 3。 3. **分段处理**：依次检查 `seg list` 中的每个分段，根据不同的规则进行分段处理，如检测年份、网站后缀、单词和键盘模式等。 4. **合并未处理的分段**：将连续的未处理分段合并。 5. **使用原始 PCFG 进行提取**：对 `seg list` 执行原始 PCFG 提取操作。 改进的 PCFG 与基本 PCFG 的不同之处在于基础结构的标签，新增了一些标签，如 `K`（键盘模式）、`W`（单词）、`E`（网站名称）和 `Y`（年份）。 ## 2. 使用 PCFG 预处理的 PassGAN PassGAN 在猜测 1 亿个密码内的效果不如基于 LSTM 的模型，推测 GAN 学习文本特征的能力弱于 LSTM。由于字符级密码对于 GAN 来说较为复杂，因此使用基于 PCFG 的预处理方法来简化数据，并使用从 PCFG 获得的基础结构来训练模型。 在生成过程中，PassGAN 会无概率地生成重复的基础结构。因此，需要统计不同基础结构的数量，直到唯一基础结构的数量达到目标值。然后，为每个基础结构分配概率 `fi/total`，其中 `fi` 表示相应基础结构的频率，`total` 表示所有基础结构的总数。 以下是使用 PCFG 预处理方法的深度学习模型的流程： ```mermaid graph LR A[原始密码] --> B[PCFG_Extraction] B --> C[基础结构] C --> D[神经网络] D --> E[训练] E --> F[猜测] F --> G[填充] G --> H[分段结果] H --> I[生成] ``` ## 3. Chunk+PCFG 预处理方法 采用了 Xu 等人在 CCS’21 提出的带有块分割的 PCFG 改进方法，并将 Chunk+PCFG 预处理方法分别与 LSTM 和 PassGAN 集成。使用字节对编码（BPE）算法将密码分割成块，然后对每个密码块执行 PCFG，将块级密码转换为基础结构。 ```plaintext Algorithm 3: The process of Chunk+PCFG preprocessing method Input: Password dictionary with the corresponding frequency pwd dict Output: Processed Dictionary pwd dict. 1 while true do 2 (Pairs, avg len)=get pairs(pwd dict);/*Take two consecutive chunks as a pair and record the frequency of pairs in Pairs, avg len is the avg len of chunks.*/ 3 if avg len > threshold then 4 /*threshold stands for the minimum average-length of chunks. */ 5 break; 6 best pair = max(Pairs, key = Pairs.get); /*find the most frequnt pair. */ 7 pwd dict = merge chunk(bestpair, pwddict); 8 PCFG extraction(pwddict);/* perform PCFG on each chunk of passwords.*/ 9 return pwd dict; `` ```