宋創(chuàng)創(chuàng)，方 勇， 黃 誠*，劉 亮

(1．四川大學電子信息學院，成都610065; 2．四川大學 網(wǎng)絡空間安全學院，成都610207)

(*通信作者電子郵箱opcodesec@gmail．com)

0 引言

在應用系統(tǒng)的認證方面，口令(Password)的安全性直接關(guān)系到整個應用系統(tǒng)的安全以及用戶隱私的保護。隨著互聯(lián)網(wǎng)服務的發(fā)展(如郵件、電子商務、社交網(wǎng)絡等)，越來越多網(wǎng)絡服務需要口令的保護;然而人類的記憶能力有限［1］，這導致用戶不可避免地使用不同程度的弱口令，或者在不同的應用系統(tǒng)中使用同一個口令，從而給應用系統(tǒng)帶來嚴重的安全隱患(如社會工程學攻擊、猜測攻擊［2－3］等)，所以，在用戶注冊時，評估用戶輸入的口令安全性并及時反饋給用戶，提醒其注意口令的強弱，具有重要的意義。

口令安全性研究的難點在于，口令是人產(chǎn)生的，與人的行為直接相關(guān)，而每個人行為因內(nèi)在或者外在的環(huán)境而千差萬別，所以口令之間具有很大的差異。在口令評估方面，基于對猜測攻擊方法和用戶脆弱口令行為的深入理解，常用的方法是使用通用口令列表來評估用戶輸入的口令，如:以用戶輸入口令是否在通用口令列表里來判斷口令是否可接受。這種方法具有很大的局限性，其準確程度取決于黑名單口令列表的大小，并且影響用戶體驗。目前，根據(jù)美國國家標準技術(shù)研究所 (National Institute of Standards and Technology，NIST)的建議［4］而衍生的啟發(fā)式口令強度估計也頗受歡迎，它是基于大小寫字母、數(shù)字和特殊字符 (Lower and Uppercase letters，Digits and Symbol，LUDS)數(shù)量來計算信息熵的，信息熵越大，口令強度就越強;然而，文獻［5－6］中表明基于信息熵的口令強度評估方法，只能提供一個粗略的評估結(jié)果。

鑒于以上口令強度評估技術(shù)的缺陷，近年來，使用統(tǒng)計學來研究口令安全問題逐漸興起，其中有基于馬爾可夫模型［7］，也有基于概率上下文無關(guān)文法(Probabilistic Context-Free Grammar，PCFG)［8］的。這兩種方法在復雜口令強度評估上具有很好的效果，如今也都投入到了應用當中，然而對于非常簡單的弱口令，它們的評估效果就有很大不足;相反地，基于啟發(fā)式的評估方法和黑名單口令集合比基于概率的方法更為有效，基于概率的方法更適合評估比較復雜的口令。

基于上述研究，本文提出了基于機器學習中的集成學習方法，將多個模型作為子模型進行集成學習訓練。在這個過程中，集成學習模型將擴展各個子模型在口令評估上的適用范圍，強化各個子模型評估方法的優(yōu)點，弱化它們的不足，達到合理評估的口令強度的效果。

本文的主要工作包括:

1)提出了基于集成學習的口令評估模型。其中的基學習器包括基于通用口令集的評估模型、啟發(fā)式口令評估模型、基于馬爾可夫鏈的評估模型以及基于概率上下文無關(guān)文法的評估模型等4類評估模型。

2)提出了基學習器自帶判定器策略和基學習器間的偏弱項相對投票的結(jié)合策略，基學習器自帶判定器策略有效避免了由于維度不同而對評估結(jié)果產(chǎn)生影響的問題，偏弱項相對投票結(jié)合策略有效強化各個基學習器的優(yōu)勢，弱化其缺陷。

3)選擇9個網(wǎng)絡上泄露的真實口令集合作為模型的實驗數(shù)據(jù)，設(shè)計有效的評估實驗。實驗結(jié)果表明，本模型在口令強度評估方面要比單獨子模型的表現(xiàn)要好，也證明了本模型的適用性。

1 整體構(gòu)架

針對各個不同的口令強度評估方法存在的優(yōu)勢和不足，本文提出了基于集成學習的口令評估模型，整體架構(gòu)如圖1所示。其中，基學習器包括:基于黑名單口令集的評估學習器、基于啟發(fā)式評估學習器、基于馬爾可夫鏈的評估學習器、基于PCFG學習器等，每個基學習器之間相互獨立。

圖1 模型整體構(gòu)架Fig．1 Architecture of model

輸入口令會同時進入各個基學習器中進行評估，輸出各自的評估分數(shù)S。之后，將S輸入到各自的判定器中，經(jīng)過各自判定器判定，輸出口令判定結(jié)果Lables，其中結(jié)果集Lables包括:弱(weak)、中(middle)、強(strong)三個標簽。根據(jù)各個基學習器的判定結(jié)果，采用Bagging的偏弱項相對投票的組合方法得出最終的評估結(jié)果。

2 模型結(jié)構(gòu)解析

文中提出的模型由4個基學習器組成，分別采用不同的評估方法來評估同一個口令的強度，之后通過集成學習得出最終的評估結(jié)果。

2．1 基于黑名單口令集的口令評估基學習器

該基學習器采用基于黑名單口令集的口令評估方法，針對常見的弱口令的評估，該方法是非常有效的，它也是抵抗常規(guī)猜測攻擊最有效方法之一。

方法中使用通用的弱口令集合為參考集，如:網(wǎng)絡上的通用口令TOP 1000000。待測口令:Password分別與參考集合中的口令比較，如果待測口令存在于參考集合中，則判定該口令強度為弱，否則為強。

本文對該方法進行了改良，采用了待測口令與參考集合中的口令計算文本相似度。對于相似度算法，本文采用Levenshtien相似度算法，計算長度為Lp的待測口令與參考口令集合中每個口令(長度為Lc)的編輯距離(Damerau-Levenshtein distance，DL)為DL，則相似度為Sc計算方法如下:

對于判定器，模型采用不同來源的口令集合(參見第3章實驗部分)進行子模型參數(shù)訓練，在不同標記的數(shù)據(jù)訓練集合下通過訓練得出判定閾值，如在1/2 tianya口令集合作為訓練集，1/2 tianya口令集合作為測試集中，得出閾值相似度 Sc∈［0．8，1］判定為弱口令，Sc∈ (0．5，0．8) 判定為中等強度，Sc∈［0，0．5］則判定待測口令為強密碼。例如:參考集合為 top_1000000［9］，檢測如下口令，其結(jié)果見表1。

表1 Levenshtien相似度評估Tab．1 Levenshtien similarity evaluation

2．2 基于啟發(fā)式口令評估基學習器

該基學習器采用啟發(fā)式口令評估方法，雖然這種方法只能提供一個較粗略的評估結(jié)果，然而它在常規(guī)口令的評估上仍然有很多的應用，如:一些在線的密碼評估計［10－11］以及一些頂尖的技術(shù)公司［12］。這種方法是基于由口令經(jīng)驗衍生的專家規(guī)則來評估的，其中口令經(jīng)驗認為口令構(gòu)成越復雜其脆弱性就越低，抵抗猜測攻擊就越強。如專家規(guī)則有:口令長度越長，口令中包含不同類別的字符種類越多，口令魯棒性就越強。雖然這種專家規(guī)則在某些特別的口令評估上產(chǎn)生不合邏輯的結(jié)果，但是在一定程度上對某些口令評估比較有效，尤其是在抵抗猜測攻擊時。

本文結(jié)合美國國家標準技術(shù)研究所的建議與實際口令評估訓練提出合理的專家規(guī)則，其中除了大小寫字母、數(shù)字、特殊字符數(shù)量和口令長度外，還考慮了連續(xù)的大小寫字母數(shù)字的數(shù)量，中間字符中包含的字符類別，以及重復字符和鍵盤序列等。其評估分數(shù)SN計算方法如下:

其中:A表示口令總長度，Uch表示大寫字母數(shù)量，Lch表示小寫字母數(shù)量，Nch表示數(shù)字數(shù)量，Sch表示特殊字符數(shù)量，Mid表示口令序列中間(非開始和結(jié)尾)包含數(shù)字和特殊字符數(shù)量，R表示符合以上5個條目的數(shù)量，OL表示口令中僅包含小寫字母時口令長度，ON表示口令中進包含數(shù)字時口令長度，RCS表示重復字符(大小寫敏感)數(shù)量，CU表示連續(xù)大寫字母數(shù)量，CL表示連續(xù)小寫字母數(shù)量，CN連續(xù)數(shù)字數(shù)量，KS表示鍵盤序列數(shù)量，DS表示數(shù)字順序的數(shù)量，SS表示鍵盤中特殊字符順序的特殊字符數(shù)量。該方法依賴專家規(guī)則的可靠性。本文認為單純只有小寫字母或者大寫字幕以及數(shù)字的口令皆判定為弱。

對于判定器，模型采用不同來源的口令集合(參見第3章實驗部分)進行子模型參數(shù)訓練，在不同數(shù)據(jù)訓練集合下制定不同判定閾值，如在1/2 tianya口令集合作為訓練集，1/2 tianya口令集合作為測試集中，得出判定閾值:當評估分數(shù)SN∈［0，50］口令判定為弱口令，SN∈(50，70)口令強度為中，SN∈［70，100］則判定為強口令。部分評估結(jié)果如表2所示。

表2 啟發(fā)式口令評估Tab．2 Heuristic-based password evaluation

2．3 基于馬爾可夫鏈口令評估基學習器

該基學習器采用于馬爾可夫鏈口令評估方法。由于口令是人產(chǎn)生的，所以人從口令空間選擇一個口令就產(chǎn)生了這個口令對應的概率，使用這個概率來描述人選擇產(chǎn)生的口令的強度看起來是比較合理的。文獻［13］首次將馬爾可夫鏈模型引入到口令猜測上來，其核心思想是:用戶構(gòu)造口令是從前往后依次進行的，所以，它是根據(jù)口令字符前后之間的關(guān)系來計算口令的概率的。

2．3．1 構(gòu)建n-gram的口令概率矩陣

口令字符前后之間有一定的依賴關(guān)系，n-gram的馬爾可夫模型以(n－1)個前綴字符(稱之為先驗序列)來確定下一個字符的概率。

構(gòu)建n-gram的口令轉(zhuǎn)移矩陣，只需要對于每一個n元字符元組，通過式(3)計算得到其條件概率。條件概率等于該n元組出現(xiàn)的頻數(shù)除以所有以n－1元組為先驗序列的n元組的頻次之和。

其中，U為口令字符空間集合，本文中選擇可顯示字符數(shù)量96，即口令字符空間集合 U={a，b，…，z} ∪ {A，B，…，Z} ∪{0，1，…，9}∪{S}。其中S為可打印的特殊字符集合。較大的字符集會導致轉(zhuǎn)移概率矩陣的稀疏性，然而包含所有可打印的字符能完整地保留口令內(nèi)在的規(guī)律。

2．3．2 口令強度評估

使用口令出現(xiàn)的概率來描述口令強度是基于馬爾可夫評估模型的核心算法。對于n階馬爾可夫模型來說，長度為m的口令 pwd=(c1，c2，…，cm)被選中的概率為:

例如:在4階馬爾可夫模型中，口令song123其出現(xiàn)的概率為:

所以，使用概率描述口令強度定義為:m

本文使用真實口令數(shù)據(jù)集來訓練模型參數(shù)，為了消除數(shù)據(jù)集中過擬合(Overfitting)問題，模型采用了Laplace平滑技術(shù)［14］，即:在訓練完畢之后對于每個字符串的頻數(shù)都加0．01再去計算字符串的概率，公式如下:

其中Σ為口令字符空間的字符數(shù)量，本文使用可顯示字符集，加上一個結(jié)尾符，共96個。

2．3．3 判定器

模型采用不同來源的口令集合(參見第3章實驗部分)進行子模型參數(shù)訓練。對準確率和計算代價進行折中考慮，本文選擇了4階馬爾可夫模型作為評估模型。在不同數(shù)據(jù)訓練集合下制定不同判定閾值，如在1/2 tianya口令集合作為訓練集，1/2 tianya口令集合作為測試集中，得出當評估強度SM∈［0，140］口令判定為弱，SM∈(140，200)判定口令為中等強度，SM≥200則判定為強。案例測試如下:

表3 基于4階馬爾可夫模型評估Tab．3 4-Markov-based password evaluation

2．4 基于概率上下文無關(guān)文法口令評估基學習器

本基學習器采用基于概率上下文無關(guān)文法口令評估方法。觀察大量的實際的口令，會發(fā)現(xiàn)口令存在分段式結(jié)構(gòu)的特點，例如:song123，可以看成兩段，字母段song和數(shù)字段123。考慮到口令的結(jié)構(gòu)特點，文獻［8］提出了基于概率上下文無關(guān)文法的漫步口令猜測算法。該算法先將口令按照字母L、數(shù)字D、特殊字符S三個類別進行分段操作，口令的每個分段是相互獨立的。例如:“song12!@#”被切分為 L4:song，D2:12，S3:!@#，L4D2S3被稱為口令的結(jié)構(gòu)。

2．4．1 概率上下文無關(guān)文法評估算法

該評估算法主要分為訓練和評估兩個階段，在訓練階段統(tǒng)計訓練集中口令的結(jié)構(gòu)特征的頻率表Σ1和字符段的頻率表Σ2。整個過程如圖2所示。

在評估階段，根據(jù)上面獲得的結(jié)構(gòu)頻率表Σ1和字符段頻率表Σ2計算口令出現(xiàn)的概率，計算方法如下:

則口令強度SP的計算方法如下:

圖2 PCFG算法的訓練過程Fig．2 Train process of PCFG algorithm

2．4．2 判定器

本文使用不同來源的口令訓練集對PCFG子模型進行訓練，在不同數(shù)據(jù)訓練集合下制定不同判定閾值，如在1/2 tianya口令集合作為訓練集，1/2 tianya口令集合作為測試集中，得出SP∈［0，150］為弱口令，SP∈(150，200)為中等強度，SP≥200為強口令。測試案例及結(jié)果如表4所示。

表4 基于PCFG模型評估Tab．4 PCFG-based password evaluation

2．5 集成學習的Bagging方法

Bagging是并行式集成學習的著名代表。它是基于自助采樣法(bootstrap sampling)在給定包含m個樣本的數(shù)據(jù)集中，先隨機取出一個樣本放到采樣集中，再把該樣本放回到初始數(shù)據(jù)集，使得下次采用仍有可能被選中，經(jīng)過m次隨機采樣，得到含有m個樣本的采樣集。初始訓練集中約有63．2%的樣本在采樣集合中出現(xiàn)。

本文用4個含m個樣本的采樣集分別訓練4個子模型，再將4個子模型進行結(jié)合。在結(jié)合策略方面，本文對相對多數(shù)投票法進行了改進，使投票結(jié)果偏向于弱項，投票部分規(guī)則如表5所示，當出現(xiàn)票數(shù)相當?shù)膬蓚€選項時，選擇低強度作為輸出，即:偏弱項投票。

表5 偏弱項投票法部分規(guī)則Tab．5 Partial rules of tendency voting

3 實驗及結(jié)果分析

3．1 實驗數(shù)據(jù)集

本文訓練測試所用到的口令數(shù)據(jù)集為國內(nèi)外知名網(wǎng)站泄露的用戶真實口令集(在文獻［15］中使用)，口令集合包括:Tianya表示天涯論壇網(wǎng)站的口令集;CSDN表示CSDN網(wǎng)站的口令集;Dodonew表示網(wǎng)站嘟嘟牛網(wǎng)站的口令集合;Zhen'ai表示珍愛網(wǎng)網(wǎng)站口令集;Sina Weibo表示新浪微博口令集;Rockyou表示國外網(wǎng)站Rockyou的口令集;Battlefield表示國外Battlefield網(wǎng)站口令集;Yahoo表示雅虎郵箱口令集;Phpbb表示國外網(wǎng)站Phpbb口令集。實驗對象為長度(length)大于6的單列口令，不包含其他信息。使用的口令集合描述如表6。

表6 實驗口令集描述Tab．6 Detail of experiments password sets

這些網(wǎng)站泄露的口令集涵蓋了境內(nèi)外多個服務包括社交論壇、游戲、約會交友以及電子商務郵箱等，保證本文中模型得到綜合的訓練和評估。

從表7中可以看出在不同的口令集之間的共有情況。其中第一列表示數(shù)據(jù)集對比并用其首字母大寫表示，如T＆S表示Tianya和Sina Weibo之間的共享比例，其他數(shù)據(jù)集類似?？梢钥闯?，對于口令集合的Top 10000之間的口令共有程度，所屬國家相同的口令集合比所屬國家不同的口令集合的要高。

表7 部分口令集合之間共享比例Tab．7 Password sharing proportion between password sets

表8統(tǒng)計了各個口令集合中4種字符類別LUDS所占比例，可以看出每個網(wǎng)站的口令集，約有99．9%的口令包含兩種或兩種以上的字符類別，約有一半的口令包含三種類別的字符。

表8 口令字符類別(LUDS)所占集合比例 %Tab．8 Proportion of character types in password sets %

表9對口令集合中的口令長度(length＞6)進行了統(tǒng)計。從表中可看出各口令長度子口令集在總口令集中所占比例?？诹铋L度大多集中在7～15位，9位口令最多。

表9 口令集合中各口令長度所占比例 %Tab．9 Proportion of password subset with different length %

3．2 實驗步驟

1)針對訓練樣本數(shù)據(jù)集，依據(jù)Bagging的自助采樣方法進行數(shù)據(jù)采集，每個進行有放回的隨機采樣，選用每個網(wǎng)站口令的1/2作為訓練集合，1/2作為測試集合。每個數(shù)據(jù)集得到4個采樣集。

2)選用采樣得到的訓練集分別對2．1節(jié)～2．4節(jié)介紹的模型以及本文提出的模型進行訓練，得到各自模型參數(shù)。

3)從每個測試樣本集中隨機取出1000個口令進行人工標記。將標記的樣本分別通過2．1節(jié)～2．4節(jié)介紹的模型和文中提出模型進行評估，得到評估結(jié)果。分析實驗評估結(jié)果，得出結(jié)論。

3．3 實驗結(jié)果分析

為了方便描述實驗結(jié)果，本文隨機從測試集合中抽出兩個測試集用來作實驗結(jié)果描述。選擇在1/2 CSDN和1/2 Rockyou口令集合作為訓練集下，隨機從對應測試集合中取出1000個口令進行人工標記，其標記結(jié)果如表10所示。

表10 1/2 CSDN＆1/2 Rockyou口令測試集隨機取1000口令標記結(jié)果Tab．10 Labeling result of random 1000 passwords from 1/2 CSDN＆1/2 Rockyou testing sets

為了評價模型的優(yōu)劣程度，本文將各個基模型與集成學習模型分別在相應的訓練集合下評估對應的標記的測試集的口令，計算其對應的標記口令的評估結(jié)果的混淆矩陣。

在1/2 CSDN訓練集合下各個基模型的評估混淆矩陣如下:基于攻擊的評估模型的混淆矩陣:

基于馬爾可夫(Markov)鏈評估模型的混淆矩陣:

基于概率上下文無關(guān)文法模型的混淆矩陣:

在1/2 Rockyou訓練集合下各個基模型的評估混淆矩陣如下:

基于攻擊的評估模型的混淆矩陣:

基于集成學習模型的混淆矩陣:

從混淆矩陣中可以初步看出在評估標記的測試集合時，各個評估模型的優(yōu)劣性。

為了更直接評價各個模型的性能，本文將計算不同模型在不同的訓練集下的評估的準確率(Accuracy，Ac)、精確率(Precision，Pr)、召回率(Recall，Re)、以及綜合評價指標 F1值(F1-measure，F(xiàn)1)，通過這些指標來衡量本文中模型的優(yōu)劣程度。如表11所示，各個模型的指標對比，可以看出本模型在不同的訓練集合下，口令強度評估的各個性能指標要比傳統(tǒng)的評估模型的表現(xiàn)更好，這也證明了本模型的適用性。

表11 各個模型之間性能對比Tab．11 Performance comparison between models

4 結(jié)語

本文提出了一個高通用性高準確性的口令強度評估模型。它綜合利用以往口令研究領(lǐng)域的評估方法，有效弱化每個評估方法的弱項，強化利用其優(yōu)點，利用集成學習方法，采用偏弱項相對投票法評估口令強度。基于實際網(wǎng)站口令集合的口令評估實驗證明，基于集成學習的口令評估模型具有高度的適用性。下一步的研究是結(jié)合更多的口令評估模型，采用更高級的結(jié)合策略。