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

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

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

0 引言

在應(yīng)用系統(tǒng)的認證方面，口令(Password)的安全性直接關(guān)系到整個應(yīng)用系統(tǒng)的安全以及用戶隱私的保護。隨著互聯(lián)網(wǎng)服務(wù)的發(fā)展(如郵件、電子商務(wù)、社交網(wǎng)絡(luò)等)，越來越多網(wǎng)絡(luò)服務(wù)需要口令的保護;然而人類的記憶能力有限［1］，這導(dǎo)致用戶不可避免地使用不同程度的弱口令，或者在不同的應(yīng)用系統(tǒng)中使用同一個口令，從而給應(yīng)用系統(tǒng)帶來嚴重的安全隱患(如社會工程學(xué)攻擊、猜測攻擊［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)計學(xué)來研究口令安全問題逐漸興起，其中有基于馬爾可夫模型［7］，也有基于概率上下文無關(guān)文法(Probabilistic Context-Free Grammar，PCFG)［8］的。這兩種方法在復(fù)雜口令強度評估上具有很好的效果，如今也都投入到了應(yīng)用當中，然而對于非常簡單的弱口令，它們的評估效果就有很大不足;相反地，基于啟發(fā)式的評估方法和黑名單口令集合比基于概率的方法更為有效，基于概率的方法更適合評估比較復(fù)雜的口令。

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

本文的主要工作包括:

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

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

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

1 整體構(gòu)架

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

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

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

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

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

2．1 基于黑名單口令集的口令評估基學(xué)習(xí)器

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

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

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

對于判定器，模型采用不同來源的口令集合(參見第3章實驗部分)進行子模型參數(shù)訓(xùn)練，在不同標記的數(shù)據(jù)訓(xùn)練集合下通過訓(xùn)練得出判定閾值，如在1/2 tianya口令集合作為訓(xùn)練集，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ā)式口令評估基學(xué)習(xí)器

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

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

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

對于判定器，模型采用不同來源的口令集合(參見第3章實驗部分)進行子模型參數(shù)訓(xùn)練，在不同數(shù)據(jù)訓(xùn)練集合下制定不同判定閾值，如在1/2 tianya口令集合作為訓(xùn)練集，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 基于馬爾可夫鏈口令評估基學(xué)習(xí)器

該基學(xué)習(xí)器采用于馬爾可夫鏈口令評估方法。由于口令是人產(chǎn)生的，所以人從口令空間選擇一個口令就產(chǎn)生了這個口令對應(yīng)的概率，使用這個概率來描述人選擇產(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為可打印的特殊字符集合。較大的字符集會導(dǎo)致轉(zhuǎn)移概率矩陣的稀疏性，然而包含所有可打印的字符能完整地保留口令內(nèi)在的規(guī)律。

2．3．2 口令強度評估

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

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

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

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

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

2．3．3 判定器

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

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

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

本基學(xué)習(xí)器采用基于概率上下文無關(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)文法評估算法

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

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

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

圖2 PCFG算法的訓(xùn)練過程Fig．2 Train process of PCFG algorithm

2．4．2 判定器

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

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

2．5 集成學(xué)習(xí)的Bagging方法

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

本文用4個含m個樣本的采樣集分別訓(xùn)練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ù)集

本文訓(xùn)練測試所用到的口令數(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)外多個服務(wù)包括社交論壇、游戲、約會交友以及電子商務(wù)郵箱等，保證本文中模型得到綜合的訓(xùn)練和評估。

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

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

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

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

為了方便描述實驗結(jié)果，本文隨機從測試集合中抽出兩個測試集用來作實驗結(jié)果描述。選擇在1/2 CSDN和1/2 Rockyou口令集合作為訓(xùn)練集下，隨機從對應(yīng)測試集合中取出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)劣程度，本文將各個基模型與集成學(xué)習(xí)模型分別在相應(yīng)的訓(xùn)練集合下評估對應(yīng)的標記的測試集的口令，計算其對應(yīng)的標記口令的評估結(jié)果的混淆矩陣。

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

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

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

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

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

基于集成學(xué)習(xí)模型的混淆矩陣:

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

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

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

4 結(jié)語

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