基于集成學習的口令強度評估模型

宋創創，方 勇， 黃 誠*，劉 亮

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

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

0 引言

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

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

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

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

本文的主要工作包括:

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

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

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

1 整體構架

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

圖1 模型整體構架Fig．1 Architecture of model

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

2 模型結構解析

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

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

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

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

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

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

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

2．2 基于啟發式口令評估基學習器

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

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

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

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

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

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

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

2．3．1 構建n-gram的口令概率矩陣

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

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

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

2．3．2 口令強度評估

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

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

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

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

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

2．3．3 判定器

模型采用不同來源的口令集合(參見第3章實驗部分)進行子模型參數訓練。對準確率和計算代價進行折中考慮，本文選擇了4階馬爾可夫模型作為評估模型。在不同數據訓練集合下制定不同判定閾值，如在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 基于概率上下文無關文法口令評估基學習器

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

2．4．1 概率上下文無關文法評估算法

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

在評估階段，根據上面獲得的結構頻率表Σ1和字符段頻率表Σ2計算口令出現的概率，計算方法如下:

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

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

2．4．2 判定器

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

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

2．5 集成學習的Bagging方法

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

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

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

3 實驗及結果分析

3．1 實驗數據集

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

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

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

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

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

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

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

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

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

3．2 實驗步驟

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

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

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

3．3 實驗結果分析

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

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

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

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

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

基于概率上下文無關文法模型的混淆矩陣:

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

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

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

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

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

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

4 結語

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