《2009 Password Cracking Using Probabilistic Context-Free Grammars ---首次提出CFG---仅考虑lower 口令集----------Weir 2009 S&P》

《2014 A Study of Probabilistic Password Models- --IEEE S&P 2014 Ma jery 》

《口令安全研究进展_计算机研究与发展 2016》

根据论文可知，该算法的实现流程大致如下：

所有步骤均使用C++实现

将数据集分为训练集和测试集，并且去除其中含有空格和一些特殊符号（不可显示的）的密码 又因为字典字符全为小写，故依据论文不考虑大小写，将训练集和测试集中的字符部分全部化为小写

首先将训练集中的密码处理为Base结构（例如：@password1 -> S1L8D1）并计算每种Base结构出现的概率（通过stl中的map实现） 然后统计出特殊符号和数字的概率（如D1可以是0，1，2，3，4，5，6，7，8，9，通过训练集计算分别出他们的概率），这同样可以通过map实现。 从而可以得到口令猜测中的变量替换规则：PCFG

采用了优先队列，结构体包含如下三个项目：1.index value（即这个预终端结构处理到哪个部分如L3D2S1，L3索引为0，D2，索引为1，S1索引为2）2.pivot value（用于指示预终端结构生成中的替换范围，比如若pivot值为2，则只能替换这个预终端结构中索引值大于2的部分）3.该预终端结构/基础结构的概率 每次取优先队列队首，然后将可替换部分依据PCFG进行替换，再将替换后的预终端结构存入优先队列

优先队列排序依据：概率 > pivot value

由预终端结构到终端结构为填充单词部分，有两种方法：

先选择概率最高的预终端结构，然后根据预终端结构的字符部分的长度替换单词（例如：！L3123，字典中长度为3的单词有hat cat、则终端结构为！hat123、！cat123），然后再选择概率第二高的预终端结构（直接排序处理即可）3.该预终端结构出现的概率。4.预终端结构 这个要通过dfs实现！

根据字典中各长度的单词数量分配概率，从而计算终端结构的概率

实验中用于训练和测试的数据下载自网站,选用myspace。

在网站上下载的文件为带有各个密码出现次数的密码文件，所以我通过c++程序将其变成单一密码形式。 如： 2 password -> password password 然后再将得到的密码随机分为Train set 和 Test set

目前问题： 1.如何将生成的文法 在猜测时用代码实现变量替换（解决，类似链表的思路） 2.如何最后导入词典并利用词典生成终端结构即破解密码（2014的论文中似乎不导入外部词典，要使用 n-gram markov 来进行L部分的变量替换）（解决） 3.2014的方法对2009方法中的具体改进之处（似乎是L部分采用markov） 4.最后猜测生成后如何与测试集比对（采用set） 5.如何将结果展示（先生成大约3e7个guess然后由于先生成的口令概率最大，故可以从头至尾与test集比对统计成功率即可，然后将结果导入Excel生成图像）

实验中的问题： 1.论文中说删去非ASCLL以及含空格的口令后剩余口令数目为60k+，但是我本地操作后剩余为41260（但是训练样本和实验样本数目比例仍然设置为3:2）,也因此base struct 数目与论文中不一致 2.论文中的实验集与测试集均比我使用的大，所以导致其破解能力下降