(1)马尔可夫链
马尔可夫链又叫做离散时间马尔可夫链，是在状态空间内从一个状态转换到另一状态的随机过程。该过程具有"无记忆"的性质:下一个状态的概率分布由当前状态所决定，在时间顺序中和它前面的事件无关。这种性质也被叫做马尔可夫性质，在实际应用中作为统计模型具有很多的应用。
在马尔可夫链的每一步中，系统根据概率分布，可从一个状态转变到另一个状态，也可以保持当前状态。状态的改变叫做过渡，与不同的状态改变相关的概率叫做过渡概率。比如，对于满足马尔可夫性质的随机变量序列刀，刀，刀，… ， Xn ， 则下一时刻的状态Xn+1 的条件分布只取决于当前的状态X刃，与过去的状态无关，我们做出如下定义(每个状态的概率P (刀， X2, .x3，…，却1) >0) ，则
P(Xn+l =XIX1=X1,X2 =X2,X3=X3,…,Xn=Xn)
=P(Xn+1 = XIXn = Xn)
以上公式中Xi 所有可能的取值构成了该链的状态空间S，这表示从一个时刻到下一个时刻的概率P (Xn+1 =xl Xn=x的，强调了马尔可夫链与P (Xn-l=xn-l) 这一结构无关。马尔可夫链还有相应的变种形式，比如多阶马尔可夫链，例如m 阶马织可夫链(其中m 是有限的)，其公式如下所示:
P(Xn+l =x I X1=X1, X 2 =X2, X 3=X3,…,Xn=Xn)
= P( Xn + 1 = X I Xn = Xn,…, Xn-m +1 X.川+ 1, Xn-m Xn-m)n > m
也就是说从一个时刻到下一个时刻的概率，未来的下一个状态取决于之前的m 个状态。
马尔可夫链具有以下性质:
.可还原性:
•周期性:
•重现性:
•各态遍历性:
.律动性。
有基于全串的马尔可夫链，以"password "为例，其公式如下所示:
P(password)=P(p )P( alp )P( slpa )P( sipas). . . P( dlpasswor)
对于变种的马尔可夫链，我们假设最高阶是4 阶，同样是以" password "的概率为例，其公式如下所示:
P(password)=P(p )P( alp )P( slpa )P( slpas). . . P( dlswor)
通常情况下，可以使用一个已泄露的密码口令集作为训练集，统计得到一个存有n阶字符子串出现概率的数据库。利用马尔科夫模型的可还原性，能够计算出任何一个口令在训练集中的概率。在猜测过程中，将高概率的字符子串组成的口令依次输出。但是该模型依旧存在着不足之处，得到的n 阶字符子串长度是规定好的，并不能体现口令中的语义、变形等规律，同时训练集中不存在的字符子串概率很难计算。
(2) 基于PCFG 方法
基于PCFG 的方法允许用户创建自己的口令并且自动从训练集中导出编码规则。将数据集分成两个部分，分成训练、集和测试集两部分。随机的从其中一个口令数据集中选择部分口令集作为PCFG 训练、集，同时从剩下的每个自令数据集中随机的选择部分口令集作为PCFG 的测试集。选择训练集的理论依据是，选择数据集中会有更多不同的组成类型。
首先，它将所有训练集中的口令划分成柜应字符的序列片段，并且获得相应的基本结构及其相关的发生概率。在训练程序中，对于给定的训练、集中的每一个口令，将口令变换成基础结构类型，并将这样的基础结构加入专门保存基础结构的列表中，相同的基础结构类望的不再重复的增加进入列表。同时计算相同基础结构类型的出现的次数，并且计算出所有基础结构类型出现的总次数。计算每个口令中存在的数字和特殊字符的概率。这些数字和特殊字符以个数来分开存储。

然后，就可以得到以降序排列的概率口令猜测，这里的概率口令指的是基础结构类型。在生成新的训练集的程序中，将存储基础结构类型列表中的每个基础结构片段与外部输入的字典、在训练程序中生成的数字和特殊宇符存储的文件进行比对，生成新的口令训练集。还是以基础结构L7S1D3 为例， L7 片段表示此结构中有7 个连续的字母，那么就在外部输入的字典中寻找字母长度为7 的口令，并保存到用来存储字母的列表中S1同样的表示此结构中有一个特殊字符，那么就将保存相应个数的特殊字符文件中的内容保存到用来存储数字的列表中，同样的可以将数字保存到相应的用来存储数字的列表中。在这些列表生成完了之后，以L7 S 1 D3 的顺序对每个列表进行遍历，将遍历中匹配到的内容相结合，这就生成了新的训练口令集。比如， L7S 1趴在字典中匹配到字符串"wanglei, zhangji" ，在数字和特殊字符文件中匹配到"123" ， "@"，那么生成的口令就应该是"wanglei@123 "和"zhangji@123 "。而任何一个猜测的概率都是其内部各个片段概率的乘积。比如， "wanglei@123" 的概率就是:
P("wanglei@123") = P(L7S1D3) * P(L7 • wanglei) * P(Sl • @)*P(Ð3• 123)
生成的新的训练集中，口令也是按照概率由高到低排列。数字片段和特殊字符片段的概率从训练集中得出，而字母字符片段的概率可以从训练集中得到也可以从外部输入字典中得到。