本发明涉及网络信息技术领域，具体涉及基于随机森林的口令猜测方法和系统。
背景技术：
口令现在作为一种不可或缺、不可替代的认证方式存在于我们的日常生活中，原因在于口令具有以下特点：
(1)简洁性。口令认证无需机器学习模型的大计算量、大数据量来保证认证过程的执行，并且可以简便地支持在线或离线认证；
(2)任意性。口令对于用户而言可以任意选择，而相比之下指纹或人脸信息则是客观存在的，对于用户而言，它的形式又是不可知的；
(3)可更改性。生物信息对用户而言在常规条件下不可更改，这一点直接导致，若某认证系统使用的生物信息数据被泄露，那么该系统的所有使用者在日后的生物信息认证中都存在着不安全性，而口令在泄露后可更改，再次设置口令后攻击者所获得的原始口令对于下一次攻击不会有直接的帮助。
因此，至少一段时间内，口令仍将作为一种主流认证方式，那么用户对于口令的选取则会直接影响用户所关心的网络与信息安全问题。
口令的缺点在于易失性。正是由于口令的任意性，用户需要记忆自己的口令，否则忘记口令只能通过繁琐的重设流程重新设置。为了保证口令的可用性，用户倾向于选取便于记忆的口令，但这一行为会导致口令强度减弱。因为口令猜测攻击便是利用用户这一脆弱行为，通过一些统计上的规律进行口令猜测，易于记忆的口令通常也是易于猜测的口令。如何评判口令的强度，以及在保证可用性的情况下如何选取口令可以使得强度更高，是用户使用口令猜测最为关心的问题。
因此，存在如下需求：在充分考虑用户口令重用行为的基础上，反馈给用户准确的口令强度。
口令强度的度量可以帮助用户评估自己的口令强度和选取适当的强口令，其中最为主要的方法是使用口令强度评价器(passwordstrengthmeter,psm)进行评估。主流的psm分为两个大类：(1)启发式psm，基于人为规定的一些规则和模式进行匹配判断，是目前较为主流的psm；(2)基于口令猜测攻击算法的psm，这类psm模拟一个攻击者进行口令猜测，在一定猜测数内无法猜测到的口令判定为强口令。第一类psm虽然在目前应用广泛，但由于其启发式设计，缺乏足够的针对性和准确性，并且许多“投机取巧”的口令选取方式会创造出大量易于猜测的“伪强口令”。而第二类psm的优劣则取决于模拟的攻击算法。使用的攻击算法越强、越先进，其评价越准确。
在2005年，narayanan和shmatikov基于自然语言处理的方法，提出了一个基于markov模型的口令猜测算法(arvindnarayananandvitalyshmatikov."fastdictionaryattacksonpasswordsusingtime-spacetradeoff".in:proc.ccs,2005:364-372)：假设口令中每个字符只与前面n个字符相关，而与其它字符无关；通过统计字符串的频次，使用贝叶斯公式计算每个前缀后面的字符概率。由于该算法基于统计频次拟合模型，导致算法在阶数n过大时容易过拟合，并且算法效果依赖于训练集大小以及口令多样性，由于概率计算需要使用训练集中字符串的频次，因此，利用该算法无法准确评估口令的强度。
在2009年，weir等提出了另一种基于概率模型的口令猜测算法：概率上下文无关文法(pcfg)(mattweir,sudhiraggarwal,brenodemedeirosetal."passwordcrackingusingprobabilisticcontext-freegrammars".in:proc.s&p,2009:391-405.)。该算法的核心思想是把字符串分为三类：dls字段，即d(数字)、l(大小写字母)和s(特殊字符)，然后根据这三类字符分割口令，使用训练得到的上下文无关文法计算每个口令的概率。由于该算法的模型拟合采用的是对自定义的dls字段进行分割，从而导致利用该算法无法准确估计一些长结构的口令强度。
在2016年，melicher等提出了一个基于深度学习的口令猜测算法(williammelicher,blaseur,seanmsegretietal."fast,lean,andaccurate:modelingpasswordguessabilityusingneuralnetworks".in:25th{usenix}securitysymposium({usenix}security16),2016:175-191.)。该算法首次应用神经网络，基于markov模型的思想，采用lstm(longshort-termmemory,长短期记忆网络)构建神经网络。但是，该算法的效果依赖于超参数的设置，评估口令强度的稳定性低。
因此，现有技术中的口令猜测算法在评估口令强度的准确性或稳定性上存在一定缺陷，需要提出更为合理的技术方案，解决现有技术中存在的技术问题。
技术实现要素：
为了克服上述内容中提到的现有技术存在的缺陷，本发明提供了基于随机森林的口令猜测方法和系统，旨在通过使用随机森林模型拟合口令猜测模型生成猜测口令并给出该口令的概率大小，克服原始markov模型由于模型拟合原理导致的容易过拟合的问题。
为了实现上述目的，本发明具体采用的猜测方法的技术方案是：
基于随机森林的口令猜测方法，选取markov模型并进行模型改进，包括：
对非平衡数据集进行预处理，将口令训练集中的每个字符作为一个目标类别；
提取出字符的前缀特征作为特征向量；
用口令训练集训练随机森林模型以得到多分类问题的概率模型；
根据概率模型生成候选口令，由此进行口令猜测。
上述猜测方法，通过口令猜测模型生成口令。本发明使用随机森林拟合口令猜测模型，通过把口令猜测生成的问题看作是多分类问题，把口令中每个字符看作是类别，字符前若干长度的前缀特征作为特征向量，通过随机森林拟合这个多分类问题。随机森林拟合的样本是前缀特征和相应字符类别，每次划分时考虑前缀特征中使分裂后基尼不纯度最小的特征作为划分规则，满足相同规则的样本划分到同一个子节点中。最后满足同一组划分规则的样本落到同一个叶子节点中，叶子节点中的样本由于满足一组划分规则因此可以认为是相似的样本，字符类别的分布也可以认为是相似的。训练后，随机森林拟合出多棵决策树，每棵决策树由多组划分规则和包含相似样本的叶子节点构成。
本发明方法改进了原始markov模型通过统计频次拟合模型的原理，充分利用每个字符前的前缀特征，解决了原始markov模型容易过拟合的问题以及口令强度评估不准确的问题；改进了以往基于随机森林的口令猜测算法训练集非平衡问题，提高了算法的泛化能力；改进了以往基于随机森林的口令猜测算法特征定义，更加匹配用户行为和符合二叉决策树结构的调整。
上述公开的技术方案中，非平衡数据集是指，在分类问题中存在某些类的样本数量远少于其他的类，这些少数类称为“负类”，与之相反的多数类称为“正类”，而非平衡数据集的分类普遍存在负类分类准确率偏低的问题。对非平衡数据集的预处理包括如下步骤：
取markov模型的阶数为6，统计数据集的样本分布并依此判定负类；
针对每一负类构造负类重心，且针对每一个负类构造多个样本并组成负类样本集，直到负类样本集达到设定大小。
进一步的，所述的前缀特征包括字符特征和长度特征，对于字符串长度为n的前缀，共使用5*n 2个维度表示前缀的特征。提取前缀特征包括如下步骤：
遍历前缀中的每个字符，对于每个字符提取字符特征；
获取前缀的长度特征，包括前缀所在口令已经遍历的字符的长度，和前缀所在口令中该前缀的后一个字符所在的相同字符类型的段已经遍历的长度。
再进一步，对上述技术方案中公开的字符特征进行优化，所述的字符特征包括shift类型、字符类型、字符所在类型序号、字符键盘所在行号和字符键盘所在列号五个维度的特征。
再进一步，将上述技术方案进行优化，对字符特征进行表示时，所述的shift类型，以1表示使用shift键进行键入，以0表示未用shift键进行键入；所述的字符类型，以0表示字母，以1表示非字母；所述的字符所在类型序号，以1～26顺序对应26个字母，大写字母和小写字母对应相同的序号，且以1～10顺序对应键盘上的“1”～“0”这10个阿拉伯数字的序号，数字键上的符号与该键上的阿拉伯数字对应相同的序号；以11～21一一对应键盘上没有顺序标记的其余特殊字符；字符键盘所在行号和字符键盘所在列号根据实际行列顺序进行编号标记。
进一步的，对上述技术方案进行优化，当用口令训练集训练随机森林模型以得到多分类问题的概率模型时，包括如下步骤：
遍历口令训练集中的所有口令，在原始口令前添加多个起始符，添加的起始符的个数等于随机森林模型的阶数；并在原始口令后添加一个字符作为结束符进行口令补齐，形成新的口令字符串，并从中确定每个字符的目标类别，以及从每个字符对应的前缀中提取前缀特征作为特征向量；
以特征向量和目标类别分别构建特征向量数组和目标类别数组，将特征向量数组和目标类别数组输入到随机森林模型中进行训练，得到训练好的随机森林模型。
进一步的，在进行随机森林模型训练时，对技术方案进行优化设置，将随机森林模型中决策树棵数为30，叶子结点最少样本数为10。
进一步的，对上述技术方案进行优化，所述的根据概率模型生成候选口令，包括如下步骤：
从空串开始生成口令，并将空串的概率赋为1，首先对空串补齐起始符，并将空串和相应概率二元组压入到候选口令队列；所述二元组可表示为("stststststst",1)，其中st为起始符，该二元组的第一列表示候选口令的字符串，第二列表示该候选口令的概率；
从候选口令队列的队首提取字符串的前缀特征，一般的，前缀特征的长度等于该前缀的字符长度；并利用概率分布模型获取字符串的最后一个字符的概率分布；在一个字符串s中，若终结符的字符概率pend与候选口令的概率ps乘积大于指定阈值，则在候选口令数组中增加该字符串s的二元组(s，pend*ps)；该字符串后接的字符c的字符概率pc与候选口令的概率ps乘积大于指定阈值，则在候选口令数组中增加该字符的二元组(s|c,pc*ps)；重复从候选口令队列中进行该操作直至候选口令队列为空。
进一步的，上述技术方案中公开的候选口令数组为二维数组，第一维表示生成的候选口令，第二维表示该候选口令的相应概率，候选口令数组根据相应概率值从大到小将候选口令进行排序。
上述公开了口令猜测的方法，以通过口令猜测的方式匹配认证口令的相似度，从得到的候选口令数组中，相应概率越大的候选口令与认证口令匹配成功的几率越大，根据匹配的几率同理匹配出该认证口令的强度。
本发明还公开了基于随机森林的口令猜测系统，用于实现上述口令猜测方法，具体的，本口令猜测系统包括：
训练集预处理模块，用于提高模型的泛化能力；
前缀特征提取模块，用于提取字符串的前缀特征，包括字符特征和长度特征；
训练集读入和处理模块，用于读入口令训练集并进行包括补齐与提取前缀特征的处理；
模型训练模块，用于训练随机森林模型，当前字符作为目标类别，将前缀特征和目标类别分别保存到特征向量数组和相应的目标类别数组中，将特征向量数组和目标类别数组输入到随机森林中进行训练，得到训练好的随机森林模型；
口令生成模块，用于将前缀特征输入到训练好的随机森林模型中，得到前缀字符串的后缀字符的概率分布，进一步进行口令生成。
与现有技术相比，本发明具有的有益效果是：
本发明方法改进了原始markov模型通过统计频次拟合模型的原理，充分利用每个字符前的前缀特征，解决了原始markov模型容易过拟合的问题以及口令强度评估不准确的问题。利用本发明所提供的基于随机森林模型的口令猜测方法和系统，提高了采用现有传统口令猜测算法评估口令强度方法的拟合能力和泛化能力，提升了口令获取的准确率，同时本发明方法降低了对口令训练集大小的依赖，提高了方法的鲁棒性，能够提高对用户口令的安全性评估的稳定性和准确性。
附图说明
为了更清楚地说明本发明实施例的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，应当理解，以下附图仅表示出了本发明的部分实施例，因此不应看作是对范围的限定，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其它相关的附图。
图1为口令猜测方法的模型训练流程示意图。
图2为生成口令的流程示意图。
具体实施方式
下面结合附图及具体实施例对本发明做进一步阐释。
在此需要说明的是，对于这些实施例方式的说明用于帮助理解本发明，但并不构成对本发明的限定。本文公开的特定结构和功能细节仅用于描述本发明的示例实施例。然而，可用很多备选的形式来体现本发明，并且不应当理解为本发明限制在本文阐述的实施例中。
实施例1
针对现有技术中口令猜测方法的准确性较低和稳定性较差的现象，本实施例提供了一种更为准确稳定的口令猜测方法，具体公开了如下的技术方案。
基于随机森林的口令猜测方法，选取markov模型并进行模型改进，包括：
s01：使用c_smote算法对非平衡数据集进行预处理，将口令训练集中的每个字符作为一个目标类别；
s02：提取出字符的前缀特征作为特征向量；
s03：用口令训练集训练随机森林模型以得到多分类问题的概率模型；
s04：根据概率模型生成候选口令，由此进行口令猜测。
上述猜测方法，通过口令猜测模型生成口令。本发明使用随机森林拟合口令猜测模型，通过把口令猜测生成的问题看作是多分类问题，把口令中每个字符看作是类别，字符前若干长度的前缀特征作为特征向量，通过随机森林拟合这个多分类问题。随机森林拟合的样本是前缀特征和相应字符类别，每次划分时考虑前缀特征中使分裂后基尼不纯度最小的特征作为划分规则，满足相同规则的样本划分到同一个子节点中。最后满足同一组划分规则的样本落到同一个叶子节点中，叶子节点中的样本由于满足一组划分规则因此可以认为是相似的样本，字符类别的分布也可以认为是相似的。训练后，随机森林拟合出多棵决策树，每棵决策树由多组划分规则和包含相似样本的叶子节点构成。
本发明方法改进了原始markov模型通过统计频次拟合模型的原理，充分利用每个字符前的前缀特征，解决了原始markov模型容易过拟合的问题以及口令强度评估不准确的问题；改进了以往基于随机森林的口令猜测算法训练集非平衡问题，提高了算法的泛化能力；改进了以往基于随机森林的口令猜测算法特征定义，更加匹配用户行为和符合二叉决策树结构的调整。
上述公开的技术方案中，非平衡数据集是指，在分类问题中存在某些类的样本数量远少于其他的类，这些少数类称为“负类”，与之相反的多数类称为“正类”，而非平衡数据集的分类普遍存在负类分类准确率偏低的问题。对非平衡数据集的预处理包括如下步骤：
s011：取markov模型的阶数为6，统计未改造前的数据集的样本分布并依此判定负类；
s012：依据c_smote算法，针对每一负类构造负类重心；
s013：针对每一个负类构造多个样本并组成负类样本集，直到负类样本集达到设定大小。
优选的，在本实施例中可根据实际需要设定负类样本集的大小。
本实施例中，所述的前缀特征包括字符特征和长度特征，对于字符串长度为n的前缀，共使用5*n 2个维度表示前缀的特征。提取前缀特征包括如下步骤：
s021：遍历前缀中的每个字符，对于每个字符提取字符特征；
s022：获取前缀的长度特征，包括前缀所在口令已经遍历的字符的长度，和前缀所在口令中该前缀的后一个字符所在的相同字符类型的段已经遍历的长度。
优选的，对上述技术方案中公开的字符特征进行优化，所述的字符特征包括shift类型、字符类型、字符所在类型序号、字符键盘所在行号和字符键盘所在列号五个维度的特征。
优选的，本实施例将上述技术方案进行优化，对字符特征进行表示时，所述的shift类型，以1表示使用shift键进行键入，以0表示未用shift键进行键入；所述的字符类型，以0表示字母，以1表示非字母；所述的字符所在类型序号，以1～26顺序对应26个字母，大写字母和小写字母对应相同的序号，且以1～10顺序对应键盘上的“1”～“0”这10个阿拉伯数字的序号，数字键上的符号(双引号内的符号，不包括两端的双引号)“！@#$％^&*()”分别与该键上的阿拉伯数字“1”～“0”对应相同的序号；以11～21一一对应键盘上没有顺序标记的其余特殊字符；字符键盘所在行号和字符键盘所在列号根据实际行列顺序进行编号标记。
优选的，没有顺序标记的其余特殊字符包括“`-＝[]\；’,./”和“～_ {}|:”<>？”等(双引号内的符号，不包括两端的双引号)，对此以此采用11～21这11个阿拉伯数字进行一一对应，具体对应关系可自行设定。
优选的，当相同的键位上存在两个字符时，通过shift类型和/或字符类型以进行字符类型所在序号的区别。
对上述技术方案进行优化，当用口令训练集训练随机森林模型以得到多分类问题的概率模型时，包括如下步骤：
s031：遍历口令训练集中的所有口令，在原始口令前添加多个起始符，添加的起始符的个数等于随机森林模型的阶数；并在原始口令后添加一个字符作为结束符进行口令补齐，形成新的口令字符串；
s032：确定每个字符的目标类别，以及从每个字符对应的前缀中提取前缀特征作为特征向量；
优选的，本实施例中采用s021～s022的方法进行前缀特征提取，在进行前缀特征提取时，设置前缀长度大于等于6。
s033：遍历所有训练集中的口令，对每个口令执行s031和s032步骤，以特征向量和目标类别分别构建特征向量数组和目标类别数组，将特征向量数组和目标类别数组输入到随机森林模型中进行训练，得到训练好的随机森林模型。
优选的，本实施例在进行随机森林模型训练时，对技术方案进行优化设置，将随机森林模型中决策树棵数为30，叶子结点最少样本数为10。
对上述技术方案进行优化，所述的根据概率模型生成候选口令，包括如下步骤：
s041：从空串开始生成口令，并将空串的概率赋为1，首先对空串补齐起始符，并将空串和相应概率二元组压入到候选口令队列；所述二元组可表示为("stststststst",1)，其中st为起始符，该二元组的第一列表示候选口令的字符串，第二列表示该候选口令的概率；
s042：从候选口令队列的队首提取字符串的前缀特征，一般的，前缀特征的长度等于该前缀的字符长度；并利用概率分布模型获取字符串的最后一个字符的概率分布；在一个字符串s中，若终结符的字符概率pend与候选口令的概率ps乘积大于指定阈值，则在候选口令数组中增加该字符串s的二元组(s，pend*ps)；该字符串后接的字符c的字符概率pc与候选口令的概率ps乘积大于指定阈值，则在候选口令数组中增加该字符的二元组(s|c,pc*ps)，其中s|c表示该字符串s后面接的字符c；
s043：重复从候选口令队列中进行该操作直至候选口令队列为空。
优选的，上述技术方案中公开的候选口令数组为二维数组，第一维表示生成的候选口令，第二维表示该候选口令的相应概率，候选口令数组根据相应概率值从大到小将候选口令进行排序。
实施例2
上述实施例公开了口令猜测的方法，以通过口令猜测的方式匹配认证口令的相似度，从得到的候选口令数组中，相应概率越大的候选口令与认证口令匹配成功的几率越大，根据匹配的几率同理匹配出该认证口令的强度。
本实施例公开了基于随机森林的口令猜测系统，用于实现上述口令猜测方法，具体的，本口令猜测系统包括：
训练集预处理模块，用于提高模型的泛化能力；
前缀特征提取模块，用于提取字符串的前缀特征，包括字符特征和长度特征；
训练集读入和处理模块，用于读入口令训练集并进行包括补齐与提取前缀特征的处理；
模型训练模块，用于训练随机森林模型，当前字符作为目标类别，将前缀特征和目标类别分别保存到特征向量数组和相应的目标类别数组中，将特征向量数组和目标类别数组输入到随机森林中进行训练，得到训练好的随机森林模型；
口令生成模块，用于将前缀特征输入到训练好的随机森林模型中，得到前缀字符串的后缀字符的概率分布，进一步进行口令生成。
以上即为本发明列举的实施方式，但本发明不局限于上述可选的实施方式，本领域技术人员可根据上述方式相互任意组合得到其他多种实施方式，任何人在本发明的启示下都可得出其他各种形式的实施方式。上述具体实施方式不应理解成对本发明的保护范围的限制，本发明的保护范围应当以权利要求书中界定的为准，并且说明书可以用于解释权利要求书。
1.基于随机森林的口令猜测方法，其特征在于，选取markov模型并进行模型改进，包括：
对非平衡数据集进行预处理，将口令训练集中的每个字符作为一个目标类别；
提取出字符的前缀特征作为特征向量；
用口令训练集训练随机森林模型以得到多分类问题的概率模型；
根据概率模型生成候选口令，由此进行口令猜测。
2.根据权利要求1所述的基于随机森林的口令猜测方法，其特征在于，对非平衡数据集的预处理包括如下步骤：
取markov模型的阶数为6，统计数据集的样本分布并依此判定负类；
针对每一负类构造负类重心，且针对每一个负类构造多个样本并组成负类样本集，直到负类样本集达到设定大小。
3.根据权利要求1所述的基于随机森林的口令猜测方法，其特征在于，前缀特征包括字符特征和长度特征，提取前缀特征包括如下步骤：
遍历前缀中的每个字符，对于每个字符提取字符特征；
获取前缀的长度特征，包括前缀所在口令已经遍历的字符的长度，和前缀所在口令中该前缀的后一个字符所在的相同字符类型的段已经遍历的长度。
4.根据权利要求3所述的基于随机森林的口令猜测方法，其特征在于，所述的字符特征包括shift类型、字符类型、字符所在类型序号、字符键盘所在行号和字符键盘所在列号五个维度的特征。
5.根据权利要求4所述的基于随机森林的口令猜测方法，其特征在于，所述的shift类型，以1表示使用shift键进行键入，以0表示未用shift键进行键入；所述的字符类型，以0表示字母，以1表示非字母；所述的字符所在类型序号，以1～26顺序对应26个字母，大写字母和小写字母对应相同的序号，且以1～10顺序对应键盘上的“1”～“0”这10个阿拉伯数字的序号，数字键上的符号与该键上的阿拉伯数字对应相同的序号；以11～21一一对应键盘上没有顺序标记的其余特殊字符；字符键盘所在行号和字符键盘所在列号根据实际行列顺序进行编号标记。
6.根据权利要求3所述的基于随机森林的口令猜测方法，其特征在于，用口令训练集训练随机森林模型以得到多分类问题的概率模型时，包括如下步骤：
遍历口令训练集中的所有口令，在原始口令前添加起始符并在原始口令后添加结束符进行口令补齐，形成新的口令字符串，并从中确定每个字符的目标类别，以及从每个字符对应的前缀中提取前缀特征作为特征向量；
以特征向量和目标类别分别构建特征向量数组和目标类别数组，将特征向量数组和目标类别数组输入到随机森林模型中进行训练，得到训练好的随机森林模型。
7.根据权利要求6所述的基于随机森林的口令猜测方法，其特征在于，随机森林模型中决策树棵数为30，叶子结点最少样本数为10。
8.根据权利要求1所述的基于随机森林的口令猜测方法，其特征在于，所述的根据概率模型生成候选口令，包括如下步骤：
从空串开始生成口令，并将空串的概率赋为1，首先对空串补齐起始符，并将空串和相应概率二元组压入到候选口令队列；
从候选口令队列的队首提取字符串的前缀特征，并利用概率分布模型获取概率分布；在一个字符串s中，若终结符的字符概率pend与候选口令的概率ps乘积大于指定阈值，则在候选口令数组中增加该字符串s的二元组(s，pend*ps)；该字符串后接的字符c的字符概率pc与候选口令的概率ps乘积大于指定阈值，则在候选口令数组中增加该字符的二元组(s|c,pc*ps)；重复从候选口令队列中进行该操作直至候选口令队列为空。
9.根据权利要求8所述的基于随机森林的口令猜测方法，其特征在于，候选口令数组为二维数组，第一维表示生成的候选口令，第二维表示该候选口令的相应概率，候选口令数组根据相应概率值从大到小将候选口令进行排序。
10.基于随机森林的口令猜测系统，用于实现权利要求1～9中任一项所述的口令猜测方法，其特征在于，包括：
训练集预处理模块，用于提高模型的泛化能力；
前缀特征提取模块，用于提取字符串的前缀特征，包括字符特征和长度特征；
训练集读入和处理模块，用于读入口令训练集并进行包括补齐与提取前缀特征的处理；
模型训练模块，用于训练随机森林模型，当前字符作为目标类别，将前缀特征和目标类别分别保存到特征向量数组和相应的目标类别数组中，将特征向量数组和目标类别数组输入到随机森林中进行训练，得到训练好的随机森林模型；
口令生成模块，用于将前缀特征输入到训练好的随机森林模型中，得到前缀字符串的后缀字符的概率分布，进一步进行口令生成。
技术总结