基于加權相對距離的自由文本擊鍵特征認證識別方法

宋夢玲，胡曉勤

（四川大學計算機學院，成都　610065）

基于加權相對距離的自由文本擊鍵特征認證識別方法

宋夢玲，胡曉勤

（四川大學計算機學院，成都610065）

加權相對距離；自由文本；擊鍵；特征識別；認證

0　引言

本文描述的擊鍵特性的分析是根據擊鍵序列的檢測屬于異常入侵檢測范疇。收集不同用戶在QQ聊天中生成的擊鍵樣本，通過分析建立正常用戶的擊鍵序列模板，將訓練樣本與測試樣本進行匹配以檢測入侵是否發生。

本文在分析、比較擊鍵特性識別算法的基礎上，收集了大量的數據并進行實驗與分析。本文的實驗是以雙鍵為基本鍵對進行實驗的[1-2]。在基于相對距離的算法上，為每對雙鍵的相對距離賦予不同權值，計算訓練樣本與測試樣本的加權相對距離和。通常，同一個用戶的測試樣本與訓練樣本的相似度越大，其加權相對距離和越小。反之，不同用戶的測試樣本與訓練樣本的相似度越小，加權相對距離和越大，由此可以判斷該訓練樣本是否屬于該用戶。

1　擊鍵動力學

擊鍵動力學識別分為靜態和動態擊鍵識別兩種。靜態擊鍵識別：Bergadano[3-4]所做的實驗中，要求自愿者根據他們所提供的固定文本來擊鍵產生樣本來構建用戶的模型，其樣本與被識別的輸入樣本是相同的文本[5]。

動態擊鍵識別：用戶按著自己的習慣、方式擊鍵產生的非固定樣本構建模型就是動態擊鍵識別[6-7]。本文所提出的擊鍵特識別方法就是基于自由文本的動態擊鍵識別。

2　擊鍵時間

擊鍵可以分為單鍵、雙鍵、三鍵、四鍵，以及N鍵。研究證明，使用雙鍵作為擊鍵特征的區分度最好，特征最明顯。如圖1 所示：

圖1　雙鍵時間示意圖P:press R:release（visio繪制）

PR為按下一個鍵到釋放該鍵的時間間隔；PP為按下一個鍵到按下下一個鍵的時間間隔；RP為釋放一個鍵到按下下一個鍵的時間間隔；RR為釋放一個鍵到釋放下一個鍵的時間間隔。雙鍵組合的持續時間可以擴展為N鍵組合。在本文中，我們將采用雙鍵的時間。

3　傳統的R方法[8]

文獻[3]和文獻[4]提出并完善了基于相對距離的擊鍵識別（即R方法）。與之相對的是采用絕對距離（擊鍵時間）衡量擊鍵樣本間的相似度與差異性。R方法的支持者認為，擊鍵是一個持續的過程，擊鍵時間是一個絕對值。在這個過程中，用戶可能會受到外界或自身影響，將擊鍵時間的絕對值作為擊鍵特征存在不穩定、偶然性等特征，難以衡量擊鍵樣本之間的真實差異性。實驗證明，不同雙鍵按照時間長短排序的位置存在著某種穩定關系[8]，受外部因素影響較小，適于作為擊鍵特征，由此提出了R方法。

對于給定的兩數組V={a1，a2，…，ak}，V'={a1'，a2'，…，ak'}，維度均為K。定義亂序度為V和V相同元素位置的距離絕對值之和。例如，數組V={2，5，1，4，3}，V’= {1，2，3，4，5}，則V和V'的無序度為:|0-1|+|1-4|+|2-0|+| 3-3|+|4-2|=1+3+2+0+2=8?？芍?，當數組V與V'排序完全相同時，無序度最小為0；反之，排序完全相反時，無序度最大，無序度的值如下：

因此，對于給定K個元素的數組來說，我們可以對其進行歸一化，即歸一化的無序度=當前無序度/最大無序度，顯然，歸一化無序度的取值范圍為[0，1]。

設有擊鍵樣本S1=classification和S2=authentication。它們共有的雙鍵有ic，ca，at，ti，，io，on這6對。其中 ：S1={265，150，280，230，260，240}，S2={320，220，200，150，190，210}，將它們的值從小到大升序排列，如表1所示：

表1　樣本S1和S2雙鍵時間排列（排序后）

最大距離為二者間的最大無序度，即maxDistance（S1，S2）=62/2=18，則R距離（相對距離）=當前距離/最大距離，即R（S1，S2）=d（S1，S2）/maxDistance（S1，S2）= 12/18=0.6666。

4　基于加權相對距離的特征識別方法

本方在R方法的基礎上對不同鍵對的相對距離進行加權，盡可能地縮同一用戶間的差異性，同時擴大不同用戶間的差異。維護了樣本的穩定性，并且具有更高的準確識別度。

設有N個擊鍵時間值的有序擊鍵序列：測試數組S1={a1，a2，…，ai，…，an}，訓練數組S2={b1，b2，…，bi，…，bn}。S1和S2都被分為M組，每組雙鍵個數為N/M，每組賦予不同權值，為k1，k2，…，km。由于每對雙鍵的相對距離都賦予了權值，為與傳統的R方法進行比較，將權值作歸一化處理。即:

本方法是比較位置索引值，因此它是關于符號序列之間的變化程度。改進方法和示例如下：以擊鍵序列arithmetic為雙鍵樣本S1和S2，有9個雙鍵：ar，ri，it，th，hm，me，et，ti，ic。 S1={185，160，230，310，280，245，260，220，250}，S2={210，195，230，190，290，235，270，220，255}，單位均為ms。按擊鍵時間從小到大升序排列后，如表2所示。

R方法計算S1和S2之間的距離有：d（S1，S2）=|0-1|+|1-2|+|2-3|+|3-4|+|4-5|+|5-6|+|6-7|+|7-8|+|8-0|=1+ 1+1+1+1+1+1+1+8=16。

最大距離maxDistance（S1，S2）=（92-1）/2=40，則相對距離=距離/最大距離R（S1，S2）=d（S1，S2）/ maxDistance（S1，S2）=16/40=0.40。上例中，只有雙鍵th位置改變，導致其他雙鍵的相對位置改變，最終得到的相對距離和累加了所有雙鍵的位置差異，擴大擊鍵樣本間的差異性，使得認證效果變差。實際上，這兩個樣本間的差異性很小。

表2　樣本S1和S2雙鍵時間排列（排序后）

而加權相對距離的特征識別算法是將S1和S2適當的分組，并賦予每組不同的權值。在本文實驗中，提取的源數據是根據雙鍵頻率由大到小排列的，因此出現頻率高的雙鍵的權值大于出現頻率低的雙鍵的權值。經過反復實驗，將S1和S2分為3組，每組3個雙鍵，每組的權值分別為3，2.5，1.25時，所得到的認證效果最佳，對權值作歸一化處理：k=（k1*3+k2*3+k3*3）/ 9=2.25。d（S1，S2）w=3*|0-1|+3*|1-2|+3*|2-3|+2.5*|3-4|+ 2.5*|4-5|+2.5*|5-6|+1.25*|6-7|+1.25*|7-8|+1.25*|8-0|= 3+3+3+2.5+2.5+2.5+1.25+1.25+10=29；d（S1，S2）w'=d（S1，S2）w/k=29/2.25=12.9。

最大距離maxDistance（S1，S2）=（92-1）/2=40，則加權相對距離=距離/最大距離，即Rw（S1，S2）=d（S1，S2）w'/ maxDistance（S1，S2）=12.9/40=0.32＜R（S1，S2）=0.40?？梢娂訖嘞鄬嚯x算法優于傳統R方法。

再看雙鍵僅發生微弱變化時的情況，設有雙鍵樣本S3和S4，有9個雙鍵值：ar，ri，it，th，hm，me，et，ti，ic。其中，S3={185，160，230，310，280，245，260，220，250}，S4={195，190，220，290，270，235，255，210，230}，單位均為ms。如表3所示。

可以看出，樣本S3和S4的順序大致相同，僅雙鍵ic和et的位置發生了交換。

按傳統的R方法計算S1和S2之間的距離，有：d（S1，S2）=|0-0|+|1-1|+|2-2|+|3-3|+|4-4|+|5-6|+|6-5|+|7-7|+|8-8|=0+0+0+0+0+1+1+0+0=2。

表3　樣本S3和S4雙鍵時間排列（排列后）

最大距離maxDistance（S1，S2）=（92-1）/2=40，則相對距離=距離/最大距離，即R（S1，S2）=d（S1，S2）/max Distance（S1，S2）=2/40=0.05。這里只有me和ic的位置發生交換，其余雙鍵的位置沒有改變，最終相對距離只累計了me和ic的位置差異。

同樣，將升序排列后的擊鍵樣本S3作為測試數組分為3組，由此可得：d（S1，S2）w=3*0+3*0+3*0+2.5*0+2.5*0+ 2.5*1+1.25*1+1.25*0+1.25*0=0+0+0+0+0+2.5+1.25+0+0= 3.75；d（S1，S2）w'=d（S1，S2）w/k=3.75/2.25=1.67＜2。

可見，無論雙鍵的擊鍵時間位置發生較大改變還是微弱改變，本方法得到的歸一化距離比傳統的R方法小。即絕對擊鍵時間的變化不會較大的影響本方法對擊鍵樣本間相似度的計算，該方法能夠得到較小的歸一化距離。

假設存在一個新的自稱屬于用戶Uk的擊鍵樣本X，認證的目的是判定樣本X是屬于用戶Uk還是樣本集里其他用戶的，也或者都不屬于樣本集里任一用戶的。分別計算樣本X與Uk之間的相對距離d（S1，S2）w'。

5　實驗及結論

5.1實驗數據

本文實驗所采用的數據全是源于QQ聊天過程中產生的。歷時半年，我們選取10位志愿者參加作為合法用戶，另外15個志愿者作為攻擊者。經過預處理，選取了頻率較高的30對雙鍵，并截取了每位合法用戶的20組雙鍵數據，最終得到10×20=200個認證次數。而對于攻擊數據，10個合法用戶的每組數據都將會作為攻擊數據去攻擊除自己以外的所有數據，攻擊次數為200×9×20=36000次。15個攻擊者都有一組攻擊數據，攻擊10個合法用戶，攻擊次數為15×10×20=3000次。最終的攻擊次數為36000+3000=39000次。如表4所示：

表4　實驗數據

5.2實驗數據預處理

本實驗所做的預處理是針對于擊鍵時間的篩選、鍵對的選取、數據的最終截取這三部分組成。

實驗所取擊鍵時間值得范圍是0＜PP＜500ms。統計分析所有志愿者的雙鍵次數和，降序排列。實驗最終選取了次數總和最多的前30對雙鍵。為了確保選取的擊鍵時間值的個異性（即不單純的重復時間值來構造擊鍵序列），我們將所有用戶中出現次數最少那組雙鍵作為基準，超過該基準的所有擊鍵時間值被舍棄，實驗中以雙鍵次數最小值20作為最終數據組數。而本文提出的權值k1>k2>k3，是根據實驗截取的雙鍵序列是根據雙鍵出現的頻率由高到低排列的，經過大量的實驗分析，我們選取了權值組合{3，2.5，1.25}，所得到的實驗結果最優。

5.3實驗結果

實驗得到了不同的認證結果，并且在給定相同數量的雙鍵的情況下，基于加權相對距離的特征識別優于R方法。FRR和FAR的實驗結果如表5所示：

表5　本方法與R方法實驗結果對比

由圖可得：本方法的FRR和FAR分別提高了14.29%和7.42%。此外，我們還基于本方法和R方法研究了實驗中用戶的數量、擊鍵序列組數以及每組擊鍵序列中雙鍵的數量對分類錯誤率的影響，對比關系如圖2 、3、4所示

圖2　用戶數量與認證結果的關系對比圖

圖3　擊鍵序列組數與認證結果的關系對比圖

圖4　雙鍵個數與認證結果的關系對比圖

5.4實驗結果分析

從表5中可知，對于本方法，通過對排序后的擊鍵序列賦予不同的權值，得到的認證結果FRR和FAR皆優于R方法。由圖2 、圖3 、圖4 可知，本方法較R方法對擊鍵序列的認證效果更理想?？傮w而言，隨著擊鍵個數的增加，FRR越來越低。FAR都隨著用戶數量、擊鍵序列組數、擊鍵個數的增加而減小。從圖2 、圖3 可以看出，當用戶數量、擊鍵序列組數到達一定數量后，FAR趨于0。由圖4 可知，當擊鍵個數足夠大時，FRR和FAR都趨于0。

因此，我們可以得出結論：本方法的認證結果比R方法更高、識別準確度更好。

6　結語

本文提出了一種基于加權相對距離的擊鍵特征識別方法。與R方法相比，擊鍵時間值的驟變或微變，本方法的歸一化距離都小于R方法的，因此本方法縮小了R方法由于某一擊鍵時間值驟變引起的相對距離的累加問題，更好地反映了用戶擊鍵特性的差異。實驗證明，本方法的正確率和識別度均高于R方法，并研究了用戶數量、擊鍵序列組數和雙鍵數量對本方法FRR和 FAR的影響。

由于實驗條件和時間所限，本文忽略了外部條件的影響。未來的實驗中，可以針對三鍵、四鍵…N鍵等多種組合，甚至是環境、鍵盤燈外在因素對擊鍵特征識別的影響作更深入的研究。

[1]Daniele Gunetti,Claudia Picardi,Giancarlo Ruffo.Keystroke Analysis of Different Languages:A Case Study[C].The 6th International Symposium on Intelligent Data Analysis,Madrid,Spain,September 8-10,2005：133-144.

[2]Daniele Gunetti,Claudia Picardi,Giancarlo Ruffo.Dealing with Different Languages and Old Profiles in Keystroke Analysis of Free Text[C].The 9th Congress of the Italian Association for Artificial Intelligence,Milan,Italy,September 21-23,2005.3673:347-358

[3]Francesco Bergadano,Daniele Gunetti,Claudia Picardi.User Authentication through Keystroke Dynamics1.ACM Transactions on Information and System Security,Vol.5,No.4,November 2002：367-397.

[4]Francesco Bergadano,Daniele Gunetti,Claudia Picardi.Identity Verification through Dynamic Keystroke Analysis.Intelligent Data Analysis.Vol.7,No.5,January 2003：469-496.

[5]Mariusz Rybnik，Piotr Panasiuk，Khalid Saeed，User Authentication with Keystroke Dynamics using Fixed Text.International Conference on Biometrics and Kansei Engineering,DOI 10.1109.2009：70-79

[6]Giot,Romain;Dorizzi,Bernadette;Rosenberger,Christophe.Analysis of Template Update Strategies for Keystroke Dynamics.IEEE Symposium Series on Computational Intelligence(SSCI 2011),2011：21-28

[7]M.Rybnik,M.Tabedzki,K.Saeed.A Keystroke Dynamics Based System for User Identification.Computer Information Systems and Industrial Management Applications-CISIM 2008,2008：225-230.

[8]Daniele Gunetti,Claudia Picardi.Keystroke Analysis of Free Text[J].ACM Transactions on Information and System Security,Vol.8, No.3,August 2005：312-347

According to the keystroke characteristics authentication and recognition method of free text based on a relative distance,which named method R,proposes a keystroke characteristics authentication and recognition method of free text based on the weighted relative Distance. Through collecting keystrokes of free text when users used QQ chat,analyses the keystroke characteristics of each user,extracts the information of double key,calculate weighted distance,normalized processing and authentication judgment.And then calculates the data to get FRR and FAR.Experiments prove that FRR and FAR of this method is less than that of method R,and get a higher recognition accuracy. Keywords：

Weighted Relative Distance;Free Text;Keystroke;Characteristics Recognition;Authentication

Keystroke Characteristics Authentication and Recognition Method of Free Text Based on the Weighted Relative Distance

SONG Meng-ling，HU-Xiao-qin
（College of Computer Science,Sichuan University，Chengdu 610065）

2015-12-11

2016-01-18

基于相對距離的自由文本擊鍵特征認證識別方法（即R方法），提出一種基于加權相對距離的自由文本擊鍵特征認證識別方法。通過收集用戶在QQ聊天過程中產生的擊鍵自由文本數據，對用戶的擊鍵特性進行分析，提取其中的雙鍵數據信息，計算加權距離、歸一化處理及認證判斷。分別計算FRR和FAR。實驗證明文中所用方法的FRR和FAR都低于R方法，識別準確度更好。

宋夢玲（1990-），四川眉山人，碩士研究生，研究方向為計算機網絡與安全

胡曉勤（1977-），男，四川內江人，博士，講師，研究方向為信息安全