韓偉力 張俊杰 徐 銘 王傳旺 張浩東 何震瀛 陳 虎

1(復(fù)旦大學(xué)數(shù)據(jù)分析與安全實驗室 上海 200438)2(華南理工大學(xué)軟件學(xué)院 廣州 510006)(wlhan@fudan.edu.cn)

迄今為止，基于文本口令的身份認證仍是保護用戶個人信息和在線財產(chǎn)的最流行方式之一[1].盡管近年來研究人員提出了各種身份認證方法，例如基于指紋或手勢的身份認證[2]，但因口令易用和低成本的顯著優(yōu)勢[3-4]，互聯(lián)網(wǎng)用戶仍傾向于使用文本口令.

為更好地研究口令的安全性，研究人員提出了多種數(shù)據(jù)驅(qū)動的口令猜測方法，如概率上下文無關(guān)文法(probabilistic context-free grammars, PCFG)[5]、馬爾可夫(Markov)方法[6]和長短期記憶(long short-term memory, LSTM)[7]神經(jīng)網(wǎng)絡(luò)方法，并致力于優(yōu)化這些猜測方法[8-17].由于這些方法具備不同的猜測優(yōu)勢，即能夠以更小的猜測數(shù)猜中特定類型的口令，Ur等人[18]提出使用每條口令被不同方法猜中所需要的最小猜測數(shù)作為評估該口令安全性的保守指標，稱為“Min_auto”.這樣的保守指標完美地結(jié)合了不同方法的猜測優(yōu)勢，可以看作是多方法混合猜測的理想上界.但在實際的猜測場景中，實現(xiàn)Min_auto的猜測效果需要的猜測數(shù)是單一方法的多倍，且不同方法會生成大量重復(fù)的猜測口令，嚴重浪費了計算資源.

為了在實際猜測的場景中減少計算資源的浪費，并在有限的猜測數(shù)內(nèi)最大化地利用不同方法的猜測優(yōu)勢，本文提出了一個通用的參數(shù)化混合猜測的框架.該框架可以混合不同數(shù)據(jù)驅(qū)動方法的猜測優(yōu)勢以生成更高效的猜測集.該框架由2部分構(gòu)成：模型剪枝和最優(yōu)猜測數(shù)分配.模型剪枝可以確?？蚣苤械拿總€方法僅生成自身擅長猜測的口令，從而避免與其他方法生成重復(fù)口令；而理論證明最優(yōu)的猜測數(shù)分配方案可以確保不同方法生成指定猜測數(shù)的口令時，框架的整體猜測效率將達到最優(yōu).

為了驗證框架的通用性和最優(yōu)性，本文也基于該框架進行了猜測實踐.本文分析了現(xiàn)有數(shù)據(jù)驅(qū)動的口令猜測方法的猜測優(yōu)勢，并根據(jù)分析結(jié)果將具備不同猜測優(yōu)勢的方法作為框架的組成模塊，設(shè)計了多個混合不同猜測模型的參數(shù)化混合口令猜測方法(parameterized hybrid password guessing Method, hyPassGu).實驗評估結(jié)果顯示，不同方法組合構(gòu)建的hyPassGu均超越了單一方法的猜測效率，驗證了框架的通用性.而和其他猜測數(shù)分配方案的比較結(jié)果也證實了框架中猜測數(shù)分配方案的最優(yōu)性.

本文的主要貢獻有2個方面：

1) 提出了一個能夠結(jié)合不同數(shù)據(jù)驅(qū)動方法猜測優(yōu)勢的通用參數(shù)化混合猜測框架.在該框架中，本文通過分析數(shù)據(jù)驅(qū)動方法的猜測模型，提出了模型剪枝的通用方案.此外，為了保證框架整體猜測效率的最優(yōu)，本文提出并在框架中應(yīng)用了理論證明最優(yōu)且適用多個方法的猜測數(shù)分配策略.

2) 基于框架和對現(xiàn)有數(shù)據(jù)驅(qū)動方法的優(yōu)勢分析，提出了組合不同方法的多個參數(shù)化混合猜測方法(統(tǒng)稱為hyPassGu)，并通過對這些方法猜測效率的評估實驗驗證了框架的通用性和最優(yōu)性.實驗結(jié)果表明，不同方法組合構(gòu)建的hyPassGu均表現(xiàn)出超越單一方法的猜測效率，在1010猜測數(shù)下超越了單一方法最優(yōu)效率的1.52%～35.49%.并且，相較于單一方法的最優(yōu)效率，hyPassGu與Min_auto的差距相對縮短了16.78%～63.99%.此外，實驗結(jié)果還表明，最優(yōu)分配策略的猜測表現(xiàn)穩(wěn)定優(yōu)于平均分配策略和隨機分配策略，并在108猜測數(shù)下在離散程度最大的數(shù)據(jù)集上有16.87%的相對提升，同時更多元的混合方法整體表現(xiàn)出更好的猜測效率.這些結(jié)果進一步驗證了框架的通用性和最優(yōu)性.

1 相關(guān)工作

1.1 數(shù)據(jù)驅(qū)動猜測方法的優(yōu)化

在過去的數(shù)十年里，研究人員致力于改進現(xiàn)有數(shù)據(jù)驅(qū)動猜測方法在猜測某些口令時的不足，以此來提高方法的猜測效率.

對于PCFG方法，Veras等人[13]利用自然語言處理算法提取分析口令中的語義模式，增強了模型對于字母字符串的泛化能力，使得模型可以生成更多可能的字母字符串.Houshmand等人[8]通過引入更多的口令結(jié)構(gòu)模式來更細粒度地定義口令中的結(jié)構(gòu)，增強了模型對于結(jié)構(gòu)的泛化能力.Li等人[11]引入了拼音字典來彌補模型在中文口令破解方面的不足.韓偉力等人[15]通過裁剪PCFG模型的搜索空間并引入變形的方式，來生成與樣本口令高度相似的模擬口令.鄒靜等人[16]則是根據(jù)用戶習(xí)慣來2次劃分高概率結(jié)構(gòu)，以解決高概率結(jié)構(gòu)只能生成少量口令的問題.

對于Markov方法，Ma等人[12]提出了Markov模型的變種，即n階Markov模型，來增強Markov模型對上下文信息的利用能力.這里的n指的是用來推測下一個字符出現(xiàn)概率的連續(xù)字符數(shù)量.此外，他們還提出了用變階Markov模型，即Backoff來解決高階Markov模型存在的數(shù)據(jù)稀疏問題.與n階Markov模型不同，Backoff會選擇出現(xiàn)頻率達到預(yù)設(shè)閾值的盡可能長的字符串來推測下一個出現(xiàn)的字符，以此在盡可能利用上文信息的同時避免數(shù)據(jù)稀疏的問題.

不同于已有研究對單一方法的改進思路，本文提出的參數(shù)化混合猜測旨在最大化利用多個數(shù)據(jù)驅(qū)動猜測方法各自不同的猜測優(yōu)勢，即利用不同方法的優(yōu)勢來彌補各自的不足.

1.2 現(xiàn)有猜測方法中的混合猜測實踐

現(xiàn)有的猜測方法中，一些方法已經(jīng)實現(xiàn)了混合猜測的簡單實踐，如Hashcat[19]和PCFGv4.1[20].

Hashcat中的混合攻擊模式實際上是一種組合攻擊.它將字典攻擊和其他諸如暴力攻擊、掩碼攻擊的攻擊方式相結(jié)合，既發(fā)揮了字典中單詞常被用戶使用的優(yōu)勢，又利用其他攻擊方式來擴展字典攻擊的搜索空間，提高了猜測效率.以字典攻擊和暴力攻擊相結(jié)合的方式為例，暴力攻擊所能生成的字符串可以作為字典中每一個單詞的前綴或者后綴.換句話說，如果使用暴力攻擊來為單詞添加1個數(shù)字作為后綴，那么根據(jù)單詞“hello”可以得到“hello0”到“hello9”的猜測口令.

PCFGv4.1則是設(shè)計了一個可選的參數(shù)“coverage”來控制基于Markov模型的暴力生成方法的使用.這個想法嘗試使用暴力生成方法來擴展模型的搜索空間，從而提高猜測效率.但是，該工作缺乏對PCFGv4.1和Markov模型的深入分析，因而不能最大程度地利用每個方法的獨特優(yōu)勢.

此外，也有一些研究工作對猜測集的混合進行了相關(guān)探索.Parish等人[21]通過計算不同猜測方法生成的口令之間的相似性及互補性、利用不同方法的互補性進行混合猜測實驗，進而提升混合猜測集的破解效率.汪定等人[22]則通過利用循環(huán)神經(jīng)網(wǎng)絡(luò)(recurrent neural network，RNN)、LSTM分別和PCFG，Markov，PR模型組合生成猜測集的方法，首次證實了在相同猜測數(shù)下，組合不同類型模型所產(chǎn)生口令猜測集的破解率通常高于單一猜測集.這些研究工作對猜測集的混合做了一定探索，但缺乏針對猜測集的高效混合策略的系統(tǒng)分析和考慮，如利用不同方法的優(yōu)勢互補而非簡單的互補來提高猜測集的有效性.

相較于已有工作在猜測集混合方面的探索，本文從優(yōu)勢互補的角度出發(fā)，通過理論分析和證明提出了針對數(shù)據(jù)驅(qū)動猜測方法的通用的參數(shù)化混合猜測框架，并基于該框架和現(xiàn)有的數(shù)據(jù)驅(qū)動猜測方法進行了猜測實踐，實現(xiàn)了高效的參數(shù)化混合猜測.

2 參數(shù)化混合猜測框架

為了在有限的猜測數(shù)內(nèi)最大化地利用不同方法的猜測優(yōu)勢，本文提出了如圖1所示的參數(shù)化混合猜測的框架.該框架具體分為2個部分：模型剪枝和最優(yōu)猜測數(shù)分配.其中模型剪枝是為了讓不同猜測方法在發(fā)揮自身猜測優(yōu)勢的同時避免生成彼此重復(fù)的猜測口令，從而提高猜測數(shù)的利用率；而最優(yōu)猜測數(shù)分配是為了在總猜測集的數(shù)目確定的情況下，通過調(diào)整不同猜測方法的可用猜測數(shù)(即圖1中的k1～kn)，使得總猜測集的猜測效率最優(yōu).下面將介紹這2個部分的做法.

Fig. 1 Framework of parameterized hybrid password guessing圖1 參數(shù)化混合口令猜測的框架

2.1 模型剪枝

數(shù)據(jù)驅(qū)動的猜測方法是基于訓(xùn)練集訓(xùn)練出的生成模型，一般可以看作1棵樹，其中每個葉子節(jié)點對應(yīng)的是1條猜測口令，而從根節(jié)點到葉子節(jié)點的路徑則可以看作該猜測口令的生成路徑.模型生成1條口令的過程就是從根節(jié)點查找到該口令對應(yīng)的葉子節(jié)點的路徑，而這條路徑上的中間節(jié)點表示的是組成該口令的字符串片段以及對應(yīng)的概率.如果某條口令對應(yīng)的生成路徑缺失了部分節(jié)點，那么模型從根節(jié)點將無法找到該口令對應(yīng)的葉子節(jié)點，也因此不會生成出這條口令.

Fig. 2 Example of model pruning of data-driven password guessing methods圖2 數(shù)據(jù)驅(qū)動的口令猜測方法的模型剪枝示例

如圖2所示，將數(shù)據(jù)驅(qū)動的生成方法抽象成1棵生成樹，其中Si表示生成過程中的1種狀態(tài)，不同的下標數(shù)字表示不同的狀態(tài).在數(shù)據(jù)驅(qū)動的生成方法中，Si可以指代口令的上下文信息(如Markov模型使用的上下文字符)、口令的結(jié)構(gòu)或者口令結(jié)構(gòu)的內(nèi)容實例(如PCFG模型使用的口令結(jié)構(gòu)和結(jié)構(gòu)對應(yīng)的具體實例).

從起始符開始，生成模型將根據(jù)生成過程的上一狀態(tài)選擇下一狀態(tài)，直到遇到終止符為止.圖2中刪除了從狀態(tài)S1到狀態(tài)S4的轉(zhuǎn)移路徑，有2條生成路徑將受此影響而無法正常生成猜測口令，因此圖2中的生成方法最終只能生成由狀態(tài)S1S2S3和S5S4S6構(gòu)成的2條猜測口令.

通過刪除一些不必要的生成路徑，模型將只保留其擅長猜測的口令所對應(yīng)的生成路徑，而不同模型擅長猜測的口令互不相同，這就可以保證不同模型將不會生成重復(fù)的猜測.刪除生成路徑的做法就是模型剪枝，具體的實現(xiàn)方式是把生成路徑中的某個不影響其他路徑的節(jié)點刪除，即將該節(jié)點對應(yīng)的字符串片段和相應(yīng)的轉(zhuǎn)移概率從模型中移除.

2.2 最優(yōu)猜測數(shù)分配

通過建立概率猜測方法猜測口令，破解數(shù)與猜測數(shù)之間關(guān)系的數(shù)學(xué)模型，本節(jié)提出了2個引理和1個定理來探尋最優(yōu)的猜測數(shù)分配方案.該方案是基于理想攻擊場景提出的，即訓(xùn)練集與測試集具有相同的分布.這類攻擊場景也被稱為站內(nèi)猜測(intra-site guessing)，被研究者們廣泛采用[8,11,22-25].此外，考慮到大猜測數(shù)的情況下訓(xùn)練集的限制會導(dǎo)致概率猜測方法出現(xiàn)瓶頸，即破解口令數(shù)不再增長，本文在本節(jié)中僅分析概率猜測方法尚未達到破解瓶頸時的情況，并將在4.5節(jié)的實驗評估中討論大猜測數(shù)對分配方案的影響.

隨著猜測數(shù)的增長，一個概率猜測方法破解出的口令數(shù)也會增長，也就是說它的“破解數(shù)-猜測數(shù)”曲線是一條單調(diào)遞增的曲線(曲線上的點的橫坐標表示使用的猜測數(shù)，縱坐標表示破解口令數(shù)).由于概率猜測方法會優(yōu)先猜測概率更高的口令，而更高的概率往往意味著猜測方法認為該口令在測試集中出現(xiàn)的頻率也更高.這帶來的結(jié)果就是小猜測數(shù)下單次命中能破解的口令數(shù)要多于大猜測數(shù)下單次命中能破解的口令數(shù).換句話說，單位猜測數(shù)里被猜中的口令數(shù)會隨著猜測數(shù)的增長而減小，即“破解數(shù)-猜測數(shù)”曲線的一階導(dǎo)數(shù)逐漸變小，最后趨近于0.因此，一個概率猜測方法的“破解數(shù)-猜測數(shù)”曲線可以看作一個單調(diào)遞增的凹函數(shù)(凹函數(shù)的二階導(dǎo)數(shù)小于0，即一階導(dǎo)數(shù)單調(diào)遞減).

基于上述數(shù)學(xué)模型，最優(yōu)的猜測數(shù)分配策略的目標是在不同概率方法的“破解數(shù)-猜測數(shù)”曲線上分別尋找1個點，使得所有點的橫坐標的和為定值時，縱坐標的和是所有組合情況中的最大值，此時每個概率方法曲線上的點對應(yīng)的橫坐標就是被分配的可用猜測數(shù).引理1證明了上述目標在概率方法僅有2個時的等價條件，定理1則是將等價條件拓展到n個方法的情況.

(1)

(2)

(3)

(4)

(5)

證畢.

n≥2且n為整數(shù).

證明.可以利用數(shù)學(xué)歸納法來證明該定理.首先，根據(jù)引理1，定理1在n=2的時候成立.接著，假設(shè)定理1在n=k(k≥2且k是個整數(shù))的時候成立.那么當n=k+1的時候，對于k+1個點中的任意k個點，定理1成立.換句話說，當固定k+1個點中的任意1個點，然后尋找其他k個點的縱坐標和為最大值的情況時，這k個點的一階導(dǎo)數(shù)一定相同.更進一步，固定k+1個點中的其他任意點，再重復(fù)上述操作，可以發(fā)現(xiàn)k+1個點的一階導(dǎo)數(shù)的值會趨于相同，最終可以得到k+1個點的縱坐標和為最大值的條件是這k+1個點的一階導(dǎo)數(shù)都相同.與引理1中式(2)到式(1)的推導(dǎo)類似，k+1個凹函數(shù)組成的函數(shù)的二階導(dǎo)數(shù)也小于0，這意味組成的函數(shù)也是凹函數(shù)，所以找到的局部最大值也是全局最大值.

證畢.

由引理1和定理1可知，最優(yōu)猜測數(shù)分配策略應(yīng)當找到不同概率方法的“破解數(shù)-猜測數(shù)”曲線上一階導(dǎo)數(shù)相等的點，即單位猜測數(shù)內(nèi)破解口令數(shù)相等的點.文獻[26]表明口令數(shù)據(jù)集的分布符合Zipf定律，即將口令按照在數(shù)據(jù)集中出現(xiàn)的頻率降序排序之后，口令出現(xiàn)頻率的lg值和口令排名的lg值滿足式(6).基于該定律，對于理想的猜測方法(每次猜測能破解出剩余口令中概率最高的口令)而言，其每次猜測破解的口令數(shù)目的lg值(即式(6)中的lgy)和已經(jīng)使用的猜測數(shù)的lg值(即式(6)中的lgx)滿足：

lgy=lgC-α×lgx.

(6)

盡管實際的概率猜測方法不能保證每次猜測都能夠破解出1條口令，但在總體趨勢上滿足了優(yōu)先猜測概率更高(出現(xiàn)頻率也更高)的口令，因此可以假設(shè)概率猜測方法在單位猜測數(shù)內(nèi)所能破解的口令數(shù)目的lg值和已經(jīng)使用的猜測數(shù)的lg值也滿足式(6).此外，同一數(shù)據(jù)集內(nèi)不同猜測方法的α值會在該數(shù)據(jù)集Zipf分布的α值周圍擾動，因此可以看作近似相同.本文也將在第3節(jié)的應(yīng)用實踐中通過實證實驗來驗證該假設(shè)的相關(guān)性質(zhì).

基于上述假設(shè)，引理2證明了不同猜測方法曲線上一階導(dǎo)數(shù)相等的點的橫坐標與數(shù)據(jù)集中口令分布的等價關(guān)系.

證明.這2條單位猜測數(shù)內(nèi)破解口令數(shù)曲線可表示為lgy1=lgC1-α×lgx1和lgy2=lgC2-α×lgx2.

這里引入了口令類別的概念來泛化各個方法的猜測優(yōu)勢，這樣做一方面可以避免過擬合，使得方法的猜測優(yōu)勢不局限于特定數(shù)據(jù)集的特定口令，另一方面也可以利用訓(xùn)練集和測試集的同分布特性，基于訓(xùn)練集中的口令分布提前為框架中的各個方法分配猜測數(shù).

3 參數(shù)化混合猜測方法

基于第2節(jié)提出的框架，本節(jié)將現(xiàn)有的數(shù)據(jù)驅(qū)動猜測方法應(yīng)用到框架中來設(shè)計實際可用的參數(shù)化混合猜測方法，具體步驟分為：優(yōu)勢分析、模型剪枝和猜測數(shù)分配.為方便表示，這些參數(shù)化混合猜測方法統(tǒng)稱為hyPassGu.

3.1 數(shù)據(jù)驅(qū)動方法的優(yōu)勢分析

本節(jié)將口令根據(jù)其構(gòu)成字符種類分為7類：僅由字母構(gòu)成、僅由數(shù)字構(gòu)成、僅由特殊符號構(gòu)成、由字母和數(shù)字構(gòu)成、由字母和特殊符號構(gòu)成、由數(shù)字和特殊符號構(gòu)成、由3種字符一起構(gòu)成.接著，本節(jié)量化比較了現(xiàn)有的概率猜測模型在不同類別的口令上的猜測效率，并分析了其優(yōu)勢背后的方法原理.為了衡量模型生成新的有效口令的能力，實驗將數(shù)據(jù)集按3∶1的比例拆分成訓(xùn)練集和測試集，并從測試集中去除了在訓(xùn)練集中出現(xiàn)的口令來計算猜測效率.本節(jié)選取了中文數(shù)據(jù)集CSDN和英文數(shù)據(jù)集Rockyou來進行分析實驗，以此探究各模型在這兩種數(shù)據(jù)集上的猜測優(yōu)勢規(guī)律.

根據(jù)圖3展示的結(jié)果，這些概率方法在不同類別的口令上表現(xiàn)差別很大.

3階Markov(Markov-3)在猜測僅由字母構(gòu)成的口令上整體表現(xiàn)最優(yōu)，在CSDN數(shù)據(jù)集上優(yōu)于其他方法，在Rockyou數(shù)據(jù)集上略遜于Semantic PCFG；4階Markov(Markov-4)在猜測僅由數(shù)字構(gòu)成的口令上整體表現(xiàn)最優(yōu)，在CSDN數(shù)據(jù)集上優(yōu)于其他方法，在Rockyou數(shù)據(jù)集上略遜于Backoff；而在猜測僅由特殊符號構(gòu)成的口令上則是Backoff和2階Markov(Markov-2)分別在CSDN和Rockyou數(shù)據(jù)集上表現(xiàn)最優(yōu).Markov模型在1類字符構(gòu)成的口令上的優(yōu)異猜測效果表明， 口令中使用的連續(xù)同類字符之間的關(guān)聯(lián)會更加緊密，因此使用多個連續(xù)同類字符來預(yù)測下一個同類字符會很有效.并且，相較于使用連續(xù)出現(xiàn)的字符預(yù)測下一個出現(xiàn)的不同類的字符，預(yù)測同類的字符需要的搜索空間更小，這也會幫助模型達到更準確的預(yù)測效果.一般而言，更高的階數(shù)會使得Markov模型的猜測效率更好，但過高的階數(shù)也會造成過擬合的問題.例如，圖3中的6階Markov模型就表現(xiàn)出了嚴重的過擬合問題，導(dǎo)致其在各類口令上的猜測效果都不佳.

Fig. 3 Guessing efficiency of single method on different types of passwords under 1010 guesses圖3 1010猜測數(shù)下單一方法在不同類別口令上的猜測效率

PCFGv4.1在猜測2類及以上字符構(gòu)成的口令方面表現(xiàn)幾乎均優(yōu)于其他方法，除了在Rockyou數(shù)據(jù)集的數(shù)字和特殊符號構(gòu)成的口令上表現(xiàn)略遜于3階Markov，這是因為PCFGv4.1引入了多詞模式、鍵盤模式、上下文模式和年份模式來更細粒度地區(qū)分口令的結(jié)構(gòu)，從而使得模型在猜測2類及以上字符構(gòu)成的口令時，一方面能生成更多可能的組合，另一方面也能減少一些不必要的搜索空間來提高猜測效率.其中，多詞模式根據(jù)單詞出現(xiàn)的頻率將連續(xù)的長字母串分成多個單獨單詞來表示結(jié)構(gòu)，可以豐富長字母串的組合情況；鍵盤模式將識別出的鍵盤上的連續(xù)輸入看作特定的鍵盤結(jié)構(gòu)，可以減少模型針對數(shù)字、字母、特殊符號混雜的鍵盤串的不必要搜索；上下文模式識別常見的特殊符號和字母數(shù)字的組合來作為特定結(jié)，如“<3”，“:p”這些類似表情的輸入，也是對不同類字符混雜字符串搜索空間的減少；而年份模式則是把單獨出現(xiàn)的連續(xù)4個數(shù)字中符合要求的數(shù)字識別為年份，這種更細粒度的類別標簽可以減少年份串和其他字符串組合時的搜索空間.

總的來說，現(xiàn)有的概率猜測模型中，Markov模型(1～5階、Backoff)在猜測僅由1類字符構(gòu)成的口令方面表現(xiàn)明顯優(yōu)勢，而PCFGv4.1在猜測2類及以上字符構(gòu)成的口令方面表現(xiàn)優(yōu)于其他方法，兩者互補的優(yōu)勢為后續(xù)參數(shù)化混合猜測方法的設(shè)計提供了便利.而Markov-6、Semantic PCFG和LSTM則沒有表現(xiàn)出明顯的猜測優(yōu)勢，因此不在混合猜測方法設(shè)計的考慮范圍之內(nèi).

3.2 hyPassGu的模型剪枝

了解到不同方法的猜測優(yōu)勢后，需要通過模型剪枝來限制各方法生成的口令.剪枝方法參照了2.1節(jié)的介紹，本文將以Markov模型和PCFGv4.1模型為例，結(jié)合2.1節(jié)的樣例介紹具體的做法.

根據(jù)3.1節(jié)的優(yōu)勢分析結(jié)果，Markov模型應(yīng)當僅生成1類字符構(gòu)成的口令，比如“password”這種僅由小寫字母構(gòu)成的口令，因此需要對其模型剪除2類及以上字符構(gòu)成的口令的生成路徑；PCFGv4.1模型則與之相反，需要剪除1類字符構(gòu)成的口令的生成路徑.

Markov模型的生成方法依賴上文的字符內(nèi)容來預(yù)測下一個要生成的字符，對照圖2中的示例可知，狀態(tài)Si在Markov模型中表示上下文的字符.以1階Markov模型為例，口令“abc”的生成路徑為“起始”-“起始a”-“ab”-“bc”-“c終止”.通過觀察可以發(fā)現(xiàn)，在1類字符構(gòu)成的口令所對應(yīng)的生成路徑中，所有的狀態(tài)都僅包含1類字符，而2類及以上字符構(gòu)成的口令中至少存在1段路徑的狀態(tài)包含多類字符，因此只需要從Markov模型中刪除包含多類字符的狀態(tài)轉(zhuǎn)移路徑，就可以剪除2類及以上字符構(gòu)成的口令的生成路徑.在實際的實踐中，通過限制訓(xùn)練集為僅包含1類字符構(gòu)成的口令，來使得Markov模型統(tǒng)計的狀態(tài)轉(zhuǎn)移只包含同類字符之間的情況，從而保證Markov模型僅能生成1類字符構(gòu)成的口令.

PCFG模型的生成方法與Markov模型略有不同，它的狀態(tài)分為2類：一類是口令結(jié)構(gòu)、一類是結(jié)構(gòu)的具體內(nèi)容實例.舉例來說，口令“abc123”的生成路徑為“起始”-“L3D3”-“abcD3”-“abc123”-“終止”.通過觀察可以發(fā)現(xiàn)，在起始符到口令結(jié)構(gòu)的選擇這一步，PCFG模型通過口令結(jié)構(gòu)就可以知道最終生成的口令將包含幾類字符，因此通過刪除1類字符構(gòu)成的口令所對應(yīng)的口令結(jié)構(gòu)，模型將只能生成2類及以上字符構(gòu)成的口令.在實際的實踐中，對于PCFGv4.1訓(xùn)練得到的口令結(jié)構(gòu)文件進行分析，去除了其中僅由1類字符構(gòu)成的口令結(jié)構(gòu)，并對剩余的口令結(jié)構(gòu)概率做了歸一化處理.具體來說，本文去除了僅由“A”(英文字母)、“D”(數(shù)字)、“O”(特殊符號)、“Y”(年份，純數(shù)字)中的某一類標簽組成的口令結(jié)構(gòu).

3.3 hyPassGu的猜測數(shù)分配

在對hyPassGu中的模型剪枝后，參照2.2節(jié)中的最優(yōu)猜測數(shù)分配策略，本節(jié)將驗證式(6)，并探究在實際數(shù)據(jù)集上α取值的情況.以108作為單位猜測數(shù)，本節(jié)使用式(6)來擬合實際的猜測方法.

表1展示了CSDN數(shù)據(jù)集上的擬合結(jié)果.PCFGv4.1方法破解情況線性擬合的決定系數(shù)R2=0.99，Markov方法破解情況線性擬合的決定系數(shù)平均為0.75左右，這意味著大部分數(shù)據(jù)點符合回歸曲線.

Table 1 Fitting Results of Zipf’s Law Based on CSDN

此外，p值檢驗的結(jié)果顯示所有的p<10-3，這意味著回歸曲線的系數(shù)可以很好地表示數(shù)據(jù)點.不同方法在CSDN數(shù)據(jù)集上擬合結(jié)果的系數(shù)α值都很接近，集中在1.2和1.3左右.此外，本文基于Rockyou數(shù)據(jù)集的擬合結(jié)果與基于CSDN數(shù)據(jù)集的擬合結(jié)果相似，系數(shù)α值也集中在1.2和1.3左右.基于這些結(jié)果，本文推薦使用1.2和1.3作為最優(yōu)猜測數(shù)分配策略中α的值.

4 實驗與評估

基于第3節(jié)的方法設(shè)計，本節(jié)通過實驗評估不同配置下的hyPassGu的猜測效率，以此驗證框架的通用性以及猜測數(shù)分配策略的最優(yōu)性.此外，還探究了猜測數(shù)大小和口令數(shù)據(jù)集離散程度對分配策略的影響，并討論了混合方法種類數(shù)對猜測效率的影響.

4.1 數(shù)據(jù)集

如表2所示，本文在實驗中使用了4個從真實網(wǎng)站泄露的大規(guī)?？诹顢?shù)據(jù)集：CSDN[27]，Youku[28]，Rockyou[29]，Neopets[30].其中，CSDN和Youku的數(shù)據(jù)集泄露自中文網(wǎng)站，而Rockyou和Neopets的數(shù)據(jù)集泄露自英文網(wǎng)站.此外，CSDN和Rockyou數(shù)據(jù)集是2011年之前泄露的，Youku和Neopets數(shù)據(jù)集則是近6年泄露的.這些數(shù)據(jù)集在區(qū)域跨度和時間跨度上都頗具代表性，并且在先前的研究[11-12,14,23-25]中被研究人員廣泛使用.

為了盡可能保證本文實驗中使用的數(shù)據(jù)是真實用戶創(chuàng)建的口令，本文參照先前的研究[12]，從數(shù)據(jù)集中清理了包含非可打印ASCII碼的口令和長度超過32的口令，最終本文從4個數(shù)據(jù)集中獲取了共計超過1.5億條的口令數(shù)據(jù).

Table 2 Basic Information of Password Datasets

本節(jié)實驗中的數(shù)據(jù)集均按3∶1隨機拆分為訓(xùn)練集和測試集，并且為了衡量模型生成新的有效口令的能力，測試集中去除了訓(xùn)練集中出現(xiàn)過的口令后來計算猜測效率.

4.2 模型剪枝后的優(yōu)勢評估實驗

根據(jù)3.1節(jié)分析得到的結(jié)論，本節(jié)按照3.2節(jié)介紹的方法對Markov模型(1～5階、Backoff)和PCFGv4.1這7個模型進行剪枝，并評估了各模型在剪枝后對其擅長猜測口令的破解率相較于剪枝前的提升幅度.評估結(jié)果如表3所示，各模型在剪枝后，在其擅長猜測口令上的破解率相較于之前均有不同程度的相對提升(0.24%～54.45%)，驗證了剪枝方案的有效性.

Table 3 Relative Improvement of Guessing Advantages After Model Pruning Under 1010 Guesses

4.3 二元hyPassGu的評估實驗

1) 實驗配置

本節(jié)選取了6對存在不同優(yōu)勢的概率模型，即PCFGv4.1和6種不同的Markov模型(Backoff和1～5階Markov模型).模型剪枝后，PCFGv4.1將只能生成2類及以上字符構(gòu)成的口令，而Markov模型將只能生成1類字符構(gòu)成的口令.圖4展示了組合不同猜測方法的二元hyPassGu在CSDN數(shù)據(jù)集上的猜測效果，其中每張子圖里的Min_auto曲線使用的模型為該子圖中對應(yīng)的2個單一方法.

2) 實驗結(jié)果

如圖4所示，二元hyPassGu的猜測效率相較于單一方法提升了1.52%～35.49%.其中，優(yōu)勢差異越明顯的2個方法，在參數(shù)化混合之后的猜測效率提升就越大，但想要獲得更高的總破解效率，則需要結(jié)合優(yōu)勢更強的方法.

Fig. 4 Guessing efficiency of binary hyPassGu compared with that of other methods based on CSDN圖4 基于CSDN數(shù)據(jù)集二元hyPassGu與其他方法的猜測效率

具體來說，1階Markov在猜測僅由數(shù)字構(gòu)成的口令上表現(xiàn)遠優(yōu)于PCFGv4.1，而PCFGv4.1在猜測2類及以上的字符構(gòu)成的口令上表現(xiàn)遠優(yōu)于1階Markov，因此兩者的優(yōu)勢結(jié)合后猜測效率的相對提升達到了35.49%；而對于3階Markov和4階Markov而言，它們在猜測2類及以上字符構(gòu)成的口令上不如PCFGv4.1表現(xiàn)優(yōu)異，但與PCFGv4.1的差距相較于1階Markov來說要小很多，因此優(yōu)勢結(jié)合后猜測效率的相對提升也要少一些.但是，鑒于3階Markov和4階Markov在猜測1類字符構(gòu)成的口令上更強的優(yōu)勢，將它們與PCFGv4.1結(jié)合可以在總的破解率上達到更高，即達到49.88%和49.92%的破解率.

此外，與多模型結(jié)合的理想上界Min_auto相比，二元hyPassGu與它在猜測效率上的差距控制在5.22%～6.68%.相較于單一方法的最優(yōu)效率與Min_auto的差距，二元hyPassGu將差距縮短了16.78%～63.99%.

4.4 三元hyPassGu的評估實驗

1) 實驗配置

本節(jié)選取3階Markov、4階Markov和PCFGv4.1來設(shè)計三元hyPassGu.考慮到僅由特殊符號構(gòu)成的口令在現(xiàn)有的真實口令集中的占比不到0.1%，難以針對這類口令單獨分配猜測數(shù)，因此由3階Markov來猜測僅由特殊符號構(gòu)成的口令.各模型的猜測任務(wù)具體為：3階Markov猜測僅由字母構(gòu)成和僅由特殊符號構(gòu)成的口令；4階Markov猜測僅由數(shù)字構(gòu)成的口令；PCFGv4.1猜測2類及以上字符構(gòu)成的口令.在4個數(shù)據(jù)集上的評估實驗結(jié)果如圖5所示，其中Min_auto曲線中使用的模型為3階Markov、4階Markov和PCFGv4.1.

2) 相較于單一方法的猜測效率提升

Fig. 5 Guessing efficiency of ternary hyPassGu compared with that of other methods圖5 三元hyPassGu與其他方法的猜測效率的比較

如圖5所示，在4個數(shù)據(jù)集上的評估實驗表明，三元hyPassGu在1010猜測數(shù)下的猜測效率超越單一猜測方法的最優(yōu)猜測效率4.55%～11.58%.不同數(shù)據(jù)集上單一方法的表現(xiàn)各有優(yōu)劣，其中在CSDN數(shù)據(jù)集上3階Markov表現(xiàn)最優(yōu)，在Youku數(shù)據(jù)集上4階Markov表現(xiàn)最優(yōu)，在Rockyou數(shù)據(jù)集上，3階Markov和4階Markov表現(xiàn)最優(yōu)，而在Neopets數(shù)據(jù)集上，PCFGv4.1和4階Markov表現(xiàn)最優(yōu)，而相比之下，結(jié)合了不同方法猜測優(yōu)勢的三元hyPassGu在4個數(shù)據(jù)集上均表現(xiàn)出相較于單一猜測方法猜測效率的穩(wěn)定提升.

此外，相較于單一方法的最優(yōu)效率，三元hyPassGu與Min_auto猜測效率的差距縮短了22.54%～43.19%.

3) 不同猜測數(shù)分配策略的比較

本節(jié)利用4個數(shù)據(jù)集上不同策略的比較實驗來驗證2.2節(jié)提出的最優(yōu)猜測數(shù)分配策略的最優(yōu)性.

如表4所示，第1列表示數(shù)據(jù)集，第2列和第3列表示不同α取值的最優(yōu)猜測數(shù)分配策略下的三元hyPassGu的猜測效率，第4列表示平均分配策略(即混合方法中每個方法使用的猜測數(shù)一樣)下的三元hyPassGu的猜測效率，第5列表示1 000組隨機分配策略下的三元hyPassGu的平均猜測效率，第6列表示在實際的破解實驗中三元hyPassGu能達到的最優(yōu)性能.為了找到三元hyPassGu的實際最優(yōu)性能，需要比較模型在所有可能配置下的性能.以1010猜測數(shù)為例，需要使用PCFGv4.1、3階Markov和4階Markov各自生成1010條猜測口令，然后遍歷總數(shù)為1010的所有可能的組合，最終找到能猜測出最多數(shù)量口令的組合并把它的表現(xiàn)作為hyPassGu的最優(yōu)性能.

從表4中可以看出，不同α值對猜測效率的影響很小，整體來說α=1.2時猜測效率更好.最優(yōu)分配策略下的三元hyPassGu表現(xiàn)遠優(yōu)于隨機分配策略下的三元hyPassGu，超出了7.60%～17.05%.此外，最優(yōu)分配策略下的三元hyPassGu的猜測效率與實際最優(yōu)性能的差值在0.07%～0.42%之間，而平均分配策略下的三元hyPassGu的猜測效率與實際最優(yōu)性能的差值是上述差值的3.6～8.7倍.上述差值表明最優(yōu)分配策略的可提升空間很有限，因此可以認為本文提出的猜測數(shù)分配策略是最優(yōu)的.

Table 4 Guessing Efficiency of Ternary hyPassGu with Different Allocation Strategies Under 1010 Guesses

4.5 最優(yōu)猜測數(shù)分配策略的探究實驗

鑒于表4中最優(yōu)分配策略在1010猜測數(shù)下相較于平均分配策略并沒有明顯的猜測效率優(yōu)勢(尤其在CSDN和Rockyou數(shù)據(jù)集上)，本節(jié)利用蒙特卡洛方法[31]進一步探究了猜測數(shù)大小和口令數(shù)據(jù)集離散程度這2個因素對最優(yōu)猜測數(shù)分配策略的影響.其中，根據(jù)已有研究[8,11,13,18,21-25]常用生成離線口令猜測集的大小，本節(jié)選取了108～1014作為猜測數(shù)的范圍；另一方面，本節(jié)使用各特征的口令占比計算得到的標準差(standard deviation, SD)作為口令數(shù)據(jù)集離散程度的度量指標.

實驗結(jié)果如表5所示，第1列表示數(shù)據(jù)集，第2列表示各數(shù)據(jù)集中不同特征口令占比計算得出的標準差(該值的大小反應(yīng)了數(shù)據(jù)集中不同特征口令分布的離散程度，值越大，數(shù)據(jù)集口令分布越不均勻)，第3，6，9，12列表示各猜測數(shù)下平均分配策略的猜測效率，第4，7，10，13列表示各猜測數(shù)下最優(yōu)分配策略的猜測效率(根據(jù)4.4節(jié)的結(jié)果，α=1.2)，第5，8，11，14列則表示最優(yōu)分配策略相較于平均分配策略的相對提升.

Table 5 Performance Improvement of Optimal Allocation Strategy Under Different Guesses when α=1.2

Fig. 6 Improvement of the best performance of ternary hyPassGu compared with that of binary hyPassGu圖6 三元hyPassGu相較于二元hyPassGu最優(yōu)效率的提升

1) 猜測數(shù)大小對最優(yōu)分配策略的影響

如表5所示，在108猜測數(shù)下，最優(yōu)分配策略相較于平均分配策略的提升效果最好，平均相對提升6.59%.而當猜測數(shù)在108～1014之間時，最優(yōu)分配策略相較于平均分配策略的提升效果逐漸降低，原因是隨著猜測數(shù)的增長，概率方法由于訓(xùn)練集的限制逐漸達到瓶頸，破解數(shù)將不再增長，不同分配策略的效率差距也因此減小.

2) 數(shù)據(jù)集的口令離散程度對最優(yōu)分配策略的影響

如表5所示，通過對比可以發(fā)現(xiàn)，最優(yōu)分配策略相較于平均分配策略的提升效果與標準差值呈正相關(guān)，即標準差值越大，數(shù)據(jù)集口令分布越不均勻、最優(yōu)分配策略的猜測優(yōu)勢越明顯.其中，Neopets數(shù)據(jù)集的離散程度最高，最優(yōu)分配策略帶來的提升也最明顯，在108猜測數(shù)下提升可以達到16.87%.這是因為當標準差值較小、數(shù)據(jù)集中對應(yīng)特征的口令分布趨于平均時，最優(yōu)分配策略將采取和平均分配策略基本一致的分配方案，兩者猜測效率也將相似.

4.6 混合方法種類(元數(shù))對破解效果的影響

本節(jié)通過對比分析三元hyPassGu和二元hyPassGu的猜測效率，討論混合方法種類數(shù)(元數(shù))對破解效果的影響.圖6中的橫坐標表示使用的猜測數(shù)(考慮到最優(yōu)分配策略發(fā)揮作用的猜測數(shù)區(qū)間，這里也選取了108～1014作為猜測數(shù)的范圍)，縱坐標表示的是三元hyPassGu相較于二元hyPassGu中最好的猜測效率的相對提升.其中，三元hyPassGu混合的是PCFGv4.1、3階Markov和4階Markov，而二元hyPassGu分別混合的是PCFGv4.1和3階Markov，以及PCFGv4.1和4階Markov.

從圖6可以看出，三元hyPassGu相較于二元hyPassGu整體表現(xiàn)更好，有一定的猜測效率提升，而在較大猜測數(shù)下(1012～1014)，三元hyPassGu和二元hyPassGu的猜測效率趨于相同.這一點與最優(yōu)分配策略的提升表現(xiàn)一致，意味著概率方法在大猜測數(shù)下的破解瓶頸也導(dǎo)致了更多元的混合方法在大猜測數(shù)下并未有明顯的猜測效率提升.

5 討 論

1) 更多元的混合猜測方法

隨著口令猜測方面研究的發(fā)展，優(yōu)化的猜測方法甚至全新的方法，例如基于表征學(xué)習(xí)的方法[22]正不斷被提出.將一個新的口令猜測方法結(jié)合到本文提出的框架中有以下2種情況：①如果它根據(jù)概率降序生成候選口令，參考本文第3節(jié)的步驟就可以嘗試將它結(jié)合到框架中.②如果它隨機地生成候選口令需要先引入口令的概率計算和排序，例如，表征學(xué)習(xí)的采樣方法[22]，而這是我們未來的工作方向.

此外，本文在分析基于深度學(xué)習(xí)技術(shù)的口令猜測方法LSTM時發(fā)現(xiàn)其沒有相較于其他方法獨有的猜測優(yōu)勢，因此在實現(xiàn)混合方法時并未結(jié)合基于深度學(xué)習(xí)的口令猜測方法.在未來的研究中，可以考慮利用遷移學(xué)習(xí)等技術(shù)來提高深度學(xué)習(xí)方法在特定類型口令上的猜測效率，并且在改進PCFG等傳統(tǒng)方法時也可從強化已有猜測優(yōu)勢的角度入手，進一步提高這些概率方法的優(yōu)勢猜測能力，從而使得多元混合方法在大猜測數(shù)下(1012以上)也能有更好的猜測表現(xiàn).

2) 最優(yōu)猜測數(shù)分配策略的可能偏差

猜測數(shù)的最優(yōu)分配策略可能會由于以下一些步驟導(dǎo)致一些偏差：首先，當使用Zipf定律去擬合不同猜測方法單位猜測數(shù)內(nèi)破解的口令數(shù)時，Markov方法的決定系數(shù)R2<0.9，這意味著擬合結(jié)果不能很好地解釋所有的原始數(shù)據(jù).其次，單位猜測數(shù)內(nèi)破解的口令數(shù)的積分值被近似為目標集的大小是很理想的近似，而實際的曲線積分值會小于目標集的大小.盡管這些可能的偏差會導(dǎo)致最優(yōu)分配策略和實際最優(yōu)性能的差距，但是第4節(jié)的實驗評估結(jié)果顯示兩者的表現(xiàn)非常接近，并且可供繼續(xù)優(yōu)化的空間也很有限.此外，分配策略中α值的選擇依賴于實證分析的結(jié)果，但是4個數(shù)據(jù)集上的良好表現(xiàn)也表明α值的選擇可以看作是通用的.

6 總 結(jié)

本文提出了一個能夠在有限猜測數(shù)內(nèi)充分利用不同方法的猜測優(yōu)勢來高效地生成口令的參數(shù)化混合猜測的框架.基于現(xiàn)有的數(shù)據(jù)驅(qū)動猜測方法，本文通過分析它們的猜測優(yōu)勢并組合不同方法來構(gòu)建實際可用的參數(shù)化混合猜測方法.評估結(jié)果表明，不同方法組合構(gòu)建的參數(shù)化混合猜測方法均表現(xiàn)出超越單一方法的猜測效率，驗證了框架的通用性.在1010猜測數(shù)下，參數(shù)化混合猜測方法超越了單一方法的最優(yōu)效率1.52%～35.49%，且最優(yōu)猜測數(shù)策略配置下的參數(shù)化混合猜測方法表現(xiàn)均優(yōu)于其他策略配置下的參數(shù)化混合猜測方法.此外，相較于單一方法的最優(yōu)效率，參數(shù)化混合猜測方法與Min_auto理想值的差距相對縮短了16.78%～63.99%.不同猜測數(shù)下的實驗結(jié)果還表明，最優(yōu)分配策略的猜測表現(xiàn)優(yōu)于平均分配策略和隨機分配策略，并在108猜測數(shù)下，在離散程度最大的數(shù)據(jù)集上有16.87%的相對提升.這些結(jié)果進一步驗證了框架的最優(yōu)性.

本文的實驗結(jié)果與分析充分說明了結(jié)合不同概率模型的猜測是比單一猜測方法更高效的生成口令猜測集的方式.在接下來的工作中，我們將嘗試將更多的猜測方法結(jié)合到本文提出的混合猜測框架中.我們還將引入不同的口令分類方案，例如根據(jù)口令長度分類，更加深入挖掘數(shù)據(jù)驅(qū)動方法的猜測優(yōu)勢.此外，我們還將研究動態(tài)調(diào)整框架中不同方法可用猜測數(shù)的方案.

作者貢獻聲明：韓偉力負責提出混合不同猜測方法優(yōu)勢的研究方向和算法思路，以及文章整體架構(gòu)的設(shè)計和修改；張俊杰負責參數(shù)化混合猜測方法hyPassGu的設(shè)計和改進，以及全文內(nèi)容的撰寫；徐銘負責全文內(nèi)容表達的修改，以及hyPassGu改進思路的討論和補充；王傳旺和張浩東負責完成hyPassGu和其他方法的對比實驗，以及文章定理的驗證；何震瀛和陳虎負責文章整體思路的指導(dǎo)，以及文章內(nèi)容的修改.