《一种基于样本的模拟口令集生成算法-韩伟力.pdf》由会员分享，可在线阅读，更多相关《一种基于样本的模拟口令集生成算法-韩伟力.pdf（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第40卷第5期 计 算 机 学 报 v0140 No52017年5月 CHINESE JOURNAL OF COMPUTERS May 2017一种基于样本的模拟口令集生成算法韩伟力 袁 琅 李思斯 王晓阳(复旦大学软件学院上海201203)(上海市数据科学重点实验室 上海201203)摘要大规模的用户口令集因可用于评估口令猜测算法的效率、检测现有用户口令保护机制的缺陷等，而广受系统安全研究领域的重视然而，尽管可以通过一些渠道，譬如网站口令泄露、用户自愿征集或者个别网站出于研究目的的共享等，获取真实的大规模用户明文口令对当前研究人员来说仍然非常困难为应对上述问题，该文提出了一种基于样本的模拟口
2、令集生成算法(Sample Perturbation Based Password Generation，SPPG)该算法利用较容易获得的小规模真实口令样本，通过学习生成概率模型，并产生大规模用户口令集合为评估这一算法的效能，该文提出了一组模拟口令集质量的检测指标，包括真实口令覆盖率、Zipf分布拟合度等最后，论文对比了SPPG算法与当前常见的用户口令猜测概率模型，包括概率上下文无关文法和多种马尔科夫模型，在生成用户口令集上的效能差异结果显示，SPPG算法产生的模拟口令集在各指标下都有更好的表现平均地，在真实口令覆盖率上，相对上下文无关文法和四阶马尔科夫模型分别提高了958和7279，相对三阶
3、和一阶马尔科夫模型分别提高了1034倍和1341倍，并且Zipf分布的拟合度保持在09及以上的水平同时，其口令结构分布和特殊模式的使用也更符合真实用户生成口令的情况关键词 口令安全；口令集生成；样本；概率上下文无关文法；马尔科夫模型中图法分类号TP391 DOI号10。11897SPJ1016201701151An Efficient Algorithm to Generate Password Sets Based on SamplesAbstractHAN WeiLi YUAN Lang LI SiSi WANG XiaoYang(Software School，Fudan Univers
4、ity，Shanghai 201203)(Shanghai Key Laboratory of Data Science，Shanghai 201203)Largescale real user password sets are well regarded important in the field of systemsecurity research，due to their usages in evaluating the efficacy of the algorithms that guesspasswords，and detecting defects of existing p
5、assword protection mechanisms，etcAt present，some ways of capturing real passwords are available for researchers，such as accidental ormalicious passwords disclosure，voluntary user contributions，or sharing by voluntary websitesfor research purposesHowever，there are some serious 1imitations involved in
6、 collecting userpassword sets in the above waysFor example，password sets that are captured from passwordsdisclosure may have been tampered，and therefore their quality cannot be guaranteedWhatSmore。types of these password sets are limitedAs a result，it is still difficult for researches tohave access
7、to the largescale clear-text user passwords in a systematic mannerMotivated toresolve the above issue，this paper presents a sample perturbation based password generationalgorithm(SPPG for short)The algorithm is to use a given smallscale real user password sampleas a training set to generate a probab
8、ility model that can then be used to provide largescale password收稿日期：20161031；在线出版日期：201703一01本课题得到上海市科委“创新行动计划项目”(16DZll00200)、国家自然科学基金(61572136，61370080)资助韩伟力，男，1975年生，博士，教授，中国计算机学会(ccF)高级会员，主要研究方向为访问控制、网络身份安全、大数据E-mail：wlhanfudaneducn袁琅，女，1993年生，硕士研究生，主要研究方向为信息安全李思斯，女，1995年生，硕士研究生，主要研究方向为信息安全王晓阳，
9、男，1955年生，博士，教授，中国计算机学会(ccF)高级会员，主要研究领域为数据分析与安全万方数据1152 计 算 机 学 报 2017年setsThe smallscale sample is relatively easier to obtainWith the purpose of improving theauthenticity of the simulation password sets，the SPPG algorithm is designed based on the idea ofsample perturbationOn the one hand，the algori
10、thm takes advantage of the ProbabilisticContextFree Grammar to parse the sample，and then generates passwords that have the samestructures with passwords in the sampleOn the other hand，it also utilizes rules that arefrequently used for users to deform their passwords，and then generates passwords that
11、 are similar topasswords in the sampleTo evaluate the efficacy of the SPPG algorithm，this paper presents aset of criteria to evaluate the quality of the simulation password setsThese criteria include thecoverage rate of the real passwords，the goodness of fit to the Zipf distribution，the similarity o
12、fpassword structure distributions and the proportion of special patternsIn the end，this papercompares the efficacy of the SPPG algorithm with the popular probability models of passwordguessing，including the Probabilistic ContextFree Grammar and several variants of the Markovmodels,In the experiment，
13、smallscale samples are randomly selected from real user passwordsets，and then are used by different models to generate the simulation password setsThe experimentresults show that the SPPG algorithm has better performancesOn average，the coverage of thereal passwords is improved by 958and 7279respecti
14、vely compared with the ProbabilisticContextFree Grammar and the 4-order Markov modelAnd the coverage of the real passwords is1034 times more than the 3-order Markov model and 1341 times more than the 1 order MarkovmodelBesides，the goodness of fit to the Zipf distribution remains at a high level that
15、 is no lessthan 09As for the password structure distribution and the proportion of special patterns，simulation password sets generated by the SPPG algorithm are also shown to be more similar tOthe real password sets compared with simulation password sets generated by the other modelsKeywords passwor
16、d security；password set generation；sample；password contextfree grammar；Markov model引 仁习文本口令是目前最常用的网站用户认证方式之一它在为用户和网站管理者提供使用便利的同时也伴随着严重的安全威胁在系统安全研究领域，大规模的用户口令集因可用于评估口令猜测算法的效率、检测现有用户口令保护机制的缺陷等，而成为十分关键的研究材料当前，真实的用户口令集可通过一些渠道收集，如：部分口令安全研究直接利用公开可获得的大规模泄露口令作为用户口令集进行研究13；也有研究者通过用户自愿征集的方式来收集El令；另外，个别网站还会出于研
17、究目的而共享用户口令H然而，后两种渠道获取的口令规模有限，而网上泄露的用户口令又有着其他严重的局限，例如：(1)当前泄露的用户真实口令，其数据质量不能保证，导致研究结果会随着数据质量的差异而不一致例如文献Es指出Tianya和7k7k口令集，由于数据污染而包含大量的相同条目，这样的口令集会给口令研究的结果带来偏差甚至，迄今为止尚不能判断这些数据集是否还存在其他的污染(2)当前泄露的用户真实口令种类有限当前泄露的大规模用户口令集通常都是基于Web的论坛型网站口令集，缺少包括网上银行、企业信息系统等更为敏感的信息系统口令集这使得研究人员得到的研究结果不能直接影响到这些高度敏感系统的安全防护(3)当
18、前泄露的口令集存在时效性问题随着时间的推移，很多系统采取单向加密机制保护存储的用户口令，使得研究人员通过口令泄露获取用户明文口令变得越来越困难这导致当前的口令安全研究很多采用的是2012年左右泄露的用户口令综上，有针对性地获取大规模的用户口令集对Tianyahttp：helptianyacnabouthistory201 I0602166666shtm 7k7khttp：www7k7keomhtmlabouthtm万方数据5期 韩伟力等：一种基于样本的模拟口令集生成算法 1153于研究人员来说仍然十分困难然而无论是真实用户口令集还是高质量的模拟用户口令集，对于评估用户口令猜测算法的效率、评估用
19、户口令强度度量方法的有效性、构建口令字典等都同样十分重要为了解决这一问题，本文利用机器学习领域虚拟样本生成的思想，提出了一种利用现有的口令作为小样本来生成能反映目标网站真实用户口令选择的模拟口令集的方法通过这一方法生成的口令集，由于用户口令的小样本相对可控，因此无论是大规模模拟数据集的质量、用户口令的种类，还是用户口令的时效性都可以得到有效保障在机器学习领域，虚拟样本是指在未知样本概率分布函数的情况下，利用研究领域先验知识并结合已有的训练样本，产生待研究问题的样本空间中的部分合理样本6在模拟口令集生成的问题中，先验知识表现为现有的口令研究中发现的一些用户口令设置规律，已有的样本即研究者能够获取
20、的小规模口令数据模拟口令集的目标是尽可能生成属于真实用户口令分布空间中的合理样本，即生成大规模真实的网站用户口令用户口令的生成方法总体可以归纳为3类：(1)基于特定场景的规则(如长度限制或字符种类限制等)产生具有一定特征的口令；(2)基于字典，再结合一些变形产生口令当前流行的口令攻击工具John the Ripperq)产生候选口令的字典模式就属于这种情况；(3)建立口令概率模型，训练口令数据，并生成概率模型空间中的其他口令常用的用户口令模型包括Narayanan和ShmatikovL7J在2005年提出的基于马尔科夫模型(以下简写为“Markov”模型)的口令生成方法和Weir等人L81在2
21、009年提出的基于概率上下文无关文法(ProbabilisticContextFree Grammar，以下简写为“PCFG”)的口令生成方法在用户口令研究中，口令生成主要用于网站口令猜测攻击基于概率模型的方法由于相对其他方法具有更好的适应性和扩展性，因此是目前最有效的口令攻击方法之一然而，这些以攻击为目的而生成的口令在恢复网站原始口令的同时，也包含许多不属于真实用户设置的口令本文提出的基于样本的模拟口令集生成算法(Sample PerturbationBased Password Generation，以下简写为“SPPG”)充分考虑到现有口令生成模型的不足，并在它们的基础上实现了更优的模拟
22、口令生成效能本文也提出了一组指标来评估口令集生成算法的有效性评估的标准主要是所生成的模拟口令集的真实性本文认为，口令概率模型生成的口令集真实性可以通过模拟口令是否符合真实用户设置口令的习惯来判断这涉及两个层次的条件：首先，模拟口令集需要符合人类口令集普遍的分布规律Wang等人对网站用户口令集的整体频率分布进行了研究，他们指出用户口令集的1=1令出现频次与频次的排序之间存在Zipf分布的特点因此，利用Zipf分布的拟合程度来评估模拟口令集应是个良好的指标；其次，模拟口令集需要描述样本对应的网站中用户口令设置习惯，例如该网站中所有口令的长度分布、字符类型分布等本文综合考虑了这两个条件，并提出从真实
23、口令覆盖率、Zipf分布拟合度、口令结构分布以及特殊模式的使用这4个方面对口令集真实性进行全面的统计分析结果显示，由SPPG算法生成的模拟口令集相比PCFG模型和一阶或多阶Markov模型具有更高的真实性本文的主要贡献包括：(1)提出了一种高效的基于样本的模拟口令集生成算法SPPG该算法利用小规模用户真实口令样本，采用基于扰动的方式生成大规模模拟口令数据SPPG算法借助了上下文无关文法学习生成概率模型，但进一步对该模型空间进行了裁剪并添加了与样本具有更高相关性的口令，增加了模拟口令集的真实性另外，SPPG算法不必对整个口令空间进行概率排序，这明显提高了模拟口令集生成速度平均地，PCFG模拟口令
24、集的生成时间约为SPPG的243倍；而单机的一阶Markov模拟口令集生成时间约为SPPG的3364倍(2)提出利用多个指标从不同角度对模拟口令集的质量进行综合评估的方法以中英文网站泄露的大量真实口令数据为实验材料，对比了SPPG算法与现有两种主要口令模型分别生成的模拟口令集的真实性评估结果显示SPPG的模拟口令集的真实口令覆盖率相对PCFG提高了958，相对一阶Markov提高了1341倍；在不同样本和模拟规模下Zipf拟合度始终保持在09以上，能较好地符合Zipf分布；口令结构分布和包含特殊模式的口令比例都比PCFG和Markov模型更接近真实用户生成口令的情况John the Rippe
25、r password crackerhttp：wwwopenwalltomjohnZipfS Law in Passwordshttps：eprintiacrorg2014631pdf 2014万方数据计 算 机 学 报 2017拄本文第1节描述背景和主要的研究内容；第2节介绍相关工作，包括两种口令概率模型、虚拟样本生成方法和现有的口令特征研究；第3节提出基于小样本的模拟口令集生成算法；第4节利用多个评估指标对比几种模型产生的模拟口令集质量；第5节是实验要点和其他问题的讨论；最后，第6节对本文进行总结和展望2 相关工作21口令概率模型利用口令概率模型生成口令的过程大致包括训练口令样本，建立概率
26、模型，再输出概率空间中包含的所有可能口令Ma等人93对口令概率模型设计空问做了详细的总结，他们将口令模型分为基于整个字符串的模型和基于模板的模型基于模板的模型将一个用户口令分解为几个片段，然后分别为每个片段计算概率典型的代表为PCFG模型8而基于整个字符串的模型则没有分段的概念典型代表为Castelluccia等人1 0提出的基于整个字符串的Markov模型，另外还有Melicher等人1u提出的基于人工神经网络的模型等211基于上下文无关文法的口令生成PCFG是一种基于模板的口令模型该方法将口令用数字(D)、字母(L)和特殊字符(S)这3种形式表示，且连续相同类型的字符划归到同一片段例如口令
27、“passwordl23”表示为L。D。，称为半终端结构口令概率的计算分为半终端结构的计算和半终端结构实例化为具体字符串的计算例如，口令“passwordl23”的概率计算为P(“passwordl23”)一P(L8D3)P(“password”I L8)P(“123”JD3)概率模型建立好之后，口令生成过程通过优先队列实现概率从高到低的输出212基于马尔科夫模型的口令生成马尔科夫模型本身是自然语言处理中的方法，由Narayanan等人73首次用来描述口令的字符序列分布，从而帮助约减口令猜测空间，并实现快速的字典攻击文献103基于这一模型计算口令概率，实现了具有适应性的13令强度评估标准后来其
28、他研究者123也使用Markov模型进行猜测攻击实验并验证了该模型的有效性文献E9还对马尔科夫链的多种变形做了详细讨论，包括马尔科夫链不同阶数的选择以及一些标准化处理和平滑处理方法一个靠阶马尔科夫链的计算公式可表示为P(zi z：一1，zi一2，z1)一P(32iI zi一1，Xf一。)对口令“C。C：Ci”，按一阶马尔科夫模型计算其概率为P(“C1 C2C3cf”)一P(c1 Co)P(c2 C1)P(c3 C2)P(ci k一，)，其中C。表示开始字符，而P(c；h一。)的值从训练集中统计而来概率模型建立之后，口令生成过程根据由马尔科夫链形成的树形结构而从根部开始搜索可能的所有口令一些研究
29、试图对PCFG和Markov模型进行改进例如，Zou等人1 3指出PCFG模型中基本的高概率口令结构能产生的口令数目较少，因此将这些高概率口令结构按用户划分习惯进行再次划分Veras等人143提出基于自然语言处理的方法其核心思想是在PCFG算法的基础上，通过分词和词性标注进一步挖掘字母片段中包含的语义信息自然语言处理方法目前的口令猜测攻击效果介于PCFG和Markov之间1 5|一些研究916也用实验对比了PCFG和Markov模型口令猜测的表现通常，PCFG模型在猜测初期即尝试次数较少的时候猜测效率比Markov模型更高；但PCFG模型最终的覆盖率比较有限，而Markov模型在猜测后期表现更
30、好Ur等人17指出，由于不同的概率模型在口令猜测的有效性上存在系统性的差别，依赖任何一种单一的模型都难以取得理想的结果各模型在使用时，需要仔细地配置并与其他方法进行结合本文首次提出了专门用于生成模拟用户口令集的算法后文中讨论的PCFG和Markov模型生成口令集是一种通用的模拟口令集生成途径本文用它们的对比实验来展示本文提出算法的效率22使用样本生成模拟数据集在机器学习领域，虚拟样本生成技术已经得到了许多研究这些研究按照生成思想大致可以分为3类1 8|：(1)基于研究领域具体的先验知识构造虚拟样本；(2)基于扰动的思想构造虚拟样本；(3)基于研究领域的分布函数构造虚拟样本在口令生成的方法中，基
31、于规则限制和基于字典的方法类似于基于先验知识的构造方法；用概率模型生成候选口令的方法类似于基于分布构造函数的构造方法在生成模拟口令集的场景中，简单的基于规则的生成方法要求目标集合具有明显的规则特征；基于字典的口令生成方法适应性和口令空间的覆盖率有限；基于概率模型的方法由于并不能完整地描述小样本中包含的口令分布信息，所以合理性有限以PCFG和Markov模型为例，PCFG模型重点描述了半终万方数据5期 韩伟力等：一种基于样本的模拟口令集生成算法端结构的计算和半终端结构实例化，而Markov模型则更关注相邻字符之间的链式概率关系它们都在一定程度上对训练口令进行了解析和概率统计，但都不够完整事实上，
32、在先验知识有限且分布构造函数难以确认的情况下，生成基于样本的模拟口令集最适宜采用基于扰动的思想文献19以建立优良的口令强度标准为目的，对PCFG和Markov模型的局限性作了初步的分析他们指出用户设置口令时倾向于直接对现有的口令进行一些混合规则的变化，而不是产生一个全新的无关的口令因此这两种模型刻画的概率空间和实际情况有一定差距这些讨论也印证了本文采用基于扰动的思想生成模拟口令集的合理性23用户口令特征分析研究者利用大规模泄露的口令或通过调研收集的真实用户口令，进行了详细的口令特征分析9,20-22这些研究使得我们对用户口令设置习惯有了比较全面的了解231 口令频次分布哈佛大学语言学专家Zip
33、f在语料库中发现一条统计型经验规律，称为Zipf分布Zipf分布的表述为：将单词在语料库中出现的次数由大到小排列，单词频数与单词排序数的常数次幂存在反比关系2012年，文献23调研了能否使用Zipf分布来描述用户口令集中的口令频率实验表明用户口令集中频次与其排序基本符合Zipf分布2014年，Wang等人再次分析了口令集中的这一特性，研究表明Zipf分布完美地存在于用户生成的口令集中同时，论文给出了Zipf公式：f：一Ci 5，其中C和5为具体数据集决定的常量，为LI令在集合中出现的频次，i为口令频次由高到低排序的序号232 口令结构特点许多研究对用户口令集的结构特征进行了经验分析，分析内容主
34、要包括口令长度分布、口令中95个可打印字符的分布、口令中“数字字母特殊字符”的字符类型分布等例如，文献E20以部分英文用户和西班牙用户的口令为研究对象，分析了两类用户1：1令在I：I令长度、字符类型、首尾字母的频率分布等方面存在的差别文献9对中英文网站用户的口令长度分布、字符类型分布等特征进行挖掘统计结果显示不同网站的用户El令集在结构特征上有一定的差异Shen等人口4也从El令长度、组成和大小写选择等方面对大规模口令集进行了分析他们将统计结果与往年的I：1令特征研究进行了对比，并指出用户口令特征会以某些方式随着时间不断改变233 口令中的语义信息研究发现语言、地区文化等因素也会影响口令的设置
35、文献21调研了4个公司的口令构造异同并展示了中国文化对口令设置的影响例如中文用户的口令中会包含一些与普通话有谐音的数字(“5201314”、“7758520”等)文献22利用可视化方法调研了口令中的语义信息，并且发现口令中包含明显的日期格式文献5-1对中英文用户口令中的特殊模式作了更详细的调研，最后发现口令中各种语义信息，包括汉语拼音、英文单词、诗词、行政区等Li等人25针对大规模中英文口令集进行了系统性分析，发现中文用户口令特有的性质Han等人分析了口令重用情况，并指出了口令重用带来的严重安全威胁Liu等人263分析了2011年中国部分网站泄露的大量真实口令中的结构和语义规律，并进一步发现这
36、些口令与口令之间、口令与用户其他信息之间一些明显的站内和跨站关联规则3 口令集生成算法设计31算法概述为了在生成大规模口令的同时保持口令集的真实性，本算法采用基于扰动的样本生成思想并结合PCFG模型来构造模拟口令集这意味着口令集主要围绕已有的样本进行扩展，即基于已有的元素对口令空间进行填充填充的方法主要是按照用户设置密码通常采用对已有密码进行变形而不是重新创建完全无关的密码的思想，基于训练集里的口令进行一些变形，从而生成更可能符合用户实际使用的口令最终，模拟口令集中的口令就由与样本完全相同的口令以及基于样本的相似口令组成基于扰动的口令生成不仅可以提高模拟口令的真实性，还可以实现比单纯的PCFG
37、和Markov等概率模型更快速的模拟口令生成算法中PCFG模型的使用，一方面是利用它来控制模拟口令集口令结构分布的合理性，另一方面也扩大了模拟口令集的生成空间尽管Markov模型在口令猜测方面也有很好的表现，并且相对PCFG模型可以产生更大Han WeiLi，Li ZhiGong，Ni MinYue，et a1Shadowattacks based on password reuses：A quantitative empiricalviewIEEE Transactions on Dependable and Secure Computing，2016，DOI：101 109TDSC2016
38、2568187Zipfs Law in Passwordshttps：eprintiacrorg2014631pdf 2014万方数据计 算 机 学 报的猜测空间，但通常PCFG模型能更好地描述原始1：3令集的特征因此，本算法主要借助PCFG模型对口令结构进行划分32算法详细描述如算法1所示，本文提出的基于样本的模拟口令集生成算法主要包括两步：(1)样本的训练步骤1表示根据PCFG的方法对样本建立概率模型首先将口令转化为以数字(D)、小写字母(L)、大写字母(U)和特殊字符(S)的形式表示的字符类型，再统计每一种子模板中不同长度的结构片段对应的具体口令子字符串概率(2)模拟口令的生成步骤218
39、表示算法会循环地为SampleSet中每个口令生成X个相关的模拟口令其中，XNM，N为模拟口令集的目标口令数，M为样本集的口令总数，X是向下取整的结果步骤317具体地根据样本口令来生成模拟口令在文献3的用户口令设置习惯调研中，用户在设置新口令时按照与已有口令的相似程度可以分为三种情况：使用已有口令、设置相似的口令和设置全新的VI令本算法也利用这一规律生成三类与样奉口令具有不同相似程度的模拟口令，它们分别是与样本口令完全相同的口令、与样本口令相似的口令以及与样本口令具有相同结构的任意口令首先，在步骤36中生成与P完全相同的模拟口令P 7，并加入模拟口令集SimulationSet相同口令的比例为
40、模拟口令总数的110；剩余部分的模拟口令由步骤717来生成步骤9随机生成和口令P在PCFG模型空间中具有相同结构的新口令P7为了提高生成真实口令的可能性，在步骤10判断口令P 7在PCFG模型中的概率值是否小于1N若小于1N说明按照PCFG模型的估算，P 7在模拟口令集中出现频率小于1，算法在步骤11对P7进行重新生成如果二次生成的口令P 7概率仍然小于1N，则在步骤13中用Transformation方法将P 7取为与P相似的口令，Transformation方法在后文有详细的介绍在以上的步骤中，随机产生与口令P结构相同的口令，是利用PCFG这种比较符合常规的口令结构划分方式对口令结构分布进
41、行控制若直接利用PCFG空间随机生成新口令，只能提高模拟口令生成速度，而无法提高PCFG模型的模拟口令真实性因此步骤1015通过重新生成的方式使得新口令P7集中于PCFG概率空间中的高概率部分，另一部分则通过口令变形的方式生成考虑到步骤218生成的是样本集合整数倍的模拟口令，不一定等于模拟口令集目标总数N因此剩余小部分的模拟口令SimulationSet2需要再通过gPSim“znio咒Sg(即步骤218)来生成其中，作为基准的样本1：3令SampleSet2从SampleSet中随机采样，SampleSet2的总数Mz=NzX步骤2224将最后一部分模拟口令加入模拟口令集Simulation
42、Set中最终，算法返回SimulationSet(步骤25)算法1 基于样本的模拟口令生成算法输入：已知的样本集合SampleSet一种口令结构划分方法PCFG模拟口令集目标口令数N中间结果：不同类型和长度的口令片段及其比例SegProbs输出：模拟口令集SimulationSet1SegProbsPCFG(SampleSet)2FOR each户in SampleSet DO3 X1一X1017 X10：14FOR i一0；iX1；i+D05 SimulationSetadd(p7)6 END FOR7X2一XX18 FOR i一0；iX2；i+DO9P 7十SameStruct(SegPr
43、obs，户)10 IF PCFG(p7)IN THEN11P 7SameStruct(SegProbs，p)12 IF PCFG(p7)IN THEN13P7Transformation(p)14 END IF15 END IF16 SimulationSetadd(p7)17 END FOR18END FOR19N2一NM*x20SampleSet2一,-PasswordSampling(SampleSet，Nj)21SimulationSet2-getSimulationSet(SampleSet2，N2)22FOR each P in SimulationSet2 DO23 Simula
44、tionSetadd(p)24END FOR25RETURN SimulationSet算法2展示了基于变形的相似口令生成方法Transformation的具体内容与样本口令相似的口令是通过对样本口令进行常见的规则变换而得到一些研究31叼调查了广受用户欢迎的一些针对已有万方数据5期 韩伟力等：一种基于样本的模拟口令集生成算法 1157口令的变换规则不同的研究因为调研的规模大小、目标人群的差异等原因可能会对这些规则的具体使用情况给出不一致的结论但总体而言这些变换规则被使用的频率基本类似在实际的用户口令设置中，可能用到的相似口令变换规则不胜枚举本算法选取了在文献3，19的调研中，用户使用比例最高的
45、十条变换规则的交集部分注意，“反转”(例如，将口令“abcl23”变为“321cba”)和“插入网站特定的信息”(例如，向口令中插入网站的名字)虽然也属于上述交集部分，但在本文的算法中暂不考虑这是由于，为了便于记忆，用户选择反转的口令通常带有一定的特征，这些特征的多样性使得算法难以迅速且准确地过滤出这类口令；而插入网站特定的信息时，可用于插入的信息也是形式多样因此，为了保证算法生成的扩展口令的真实性以及算法生成模拟口令的时间效率，我们最终针对交集部分里的六条规则进行相应的变换算法2首先在步骤3中随机选定一条当前口令变换要使用的规则，然后相应地在步骤5、7、9、11、13或15中实现变换以下是这
46、几种变换的实现细节步骤45对应删除变换如果口令由两种及以上的字符类型组成，算法会对口令中出现个数最少的那类字符C进行删除为了增加相似口令的多样性，被删除的字符可以是口令中包含的所有的C类字符，也可以是由别的字符类型分隔开的一段C类字符另外，一些用户习惯设置新口令时在现有口令基础上添加一个字符因此，删除变换也可以是删除口令中的一个字符例如，样本口令“123passwordl23”通过删除变换可以得到相似口令“passwordl23”、“password”或“123passwordl2”考虑到许多用户设置新口令时会选择对现有口令进行添加部分字符的变换同时，进入算法2的口令为在PCFG模型中概率较小
47、的口令这类口令往往具有长度较长或结构较为复杂的特征因此进行删除部分字符的处理很可能得到与样本口令相似且符合用户口令设置习惯的新口令注意，如果当前场景中明确规定了最短口令长度，那么当删除变换执行后的口令长度小于最小口令长度，则删除不成功步骤67对应字母大小写变换这也是最常见的用户口令变换之一大小写变换一般为口令的首字母变换，同时也可能有整个字母片段的大小写变换(若字母片段为全小写则将它转为全大写形式；若字母片段为全大写，则将其转为全小写形式；若有的大写有的小写，则转为全大写或全小写形式)步骤89对应Leet0变换主要对常见的几种形似的字符做替换，包括a与的互换、s与$的互换、o与0的互换、i与1
48、的互换、e与3的互换和t与7的互换例如将从样本口令“password”变换到“p$Sword”；步骤101l对应子字符串位置的变换算法以特殊符号作为分隔符，将子字符串按照字符类型分类若除去特殊符号后口令不是单一的字符类型，则将首尾的子字符串进行位置交换例如从“gzwz0204”到“02049zwz”；步骤1213对应连续字符的变换口令中字符的连续可能有两种形式一种是字符串的ASCII值连续，一种是字符串在标准键盘中同一行位置里的连续连续字符的变换是将字符串按照相同的规律添加一个字符或删除一个字符或整个口令字符串替换为另一个同类型的字符串例如从样本口令“12345678”变换到“123456789”、“1234567”或“abcdefgh”；步骤1415表示若口令本身具有回文或重复的特征，则取口令的一半作为相似口令，例如从样本口令“passwordpassword”到相似口令