基于相對熵的擊鍵動力學中文自由文本用戶認證

黃怡然，胡曉勤

基于相對熵的擊鍵動力學中文自由文本用戶認證

黃怡然，胡曉勤

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

擊鍵動力學——對用戶的擊鍵的韻律進行分析和處理，已經可以作為一種合法用戶識別和入侵檢測的一種有效方法。認證的過程是通過觀察在擊鍵時的用戶行為模式進行判斷。在這里，提出運用相對熵作為擊鍵動力學的認證方法，跟之前的方法相比，從認證效果和效率上都有明顯提升。實驗結果表明，相對熵比傳統的歐氏距離方法的錯誤接受率和錯誤拒絕率更低，效果更好。

相對熵；擊鍵動力學；錯誤拒絕率；錯誤接受率

0　引言

互聯網所具有的開放和互聯的特性，使得互聯網本身具有極大的安全隱患。而傳統的用戶——口令模式，容易被非法用戶獲取，可能導致許多重要的隱私的信息泄露。

基于生物特征的認證技術是通過對一個人的在生理或行為特征進行研究，以自動化的方法進行驗證或確認那個人的身份。

圖1　生物特征的認證技術發展過程

擊鍵動力學就是將擊鍵特性運用于入侵檢測能有效地識別用戶[1]。研究表明，個人用戶的擊鍵特性猶如指紋，難以模仿[2]。擊鍵動力學研究對象時個人的擊鍵的節奏和時間，這是相對穩定的?？梢愿鶕翩I的節奏和時間來區分不同的人[3]。擊鍵動力學始終是個有趣的課題：（1）因為這項技術的信息獲取是通過用戶提供的擊鍵信息，而不是通過入侵系統來獲?。唬?）這項技術不需要昂貴的硬件設備，實現成本不高。

以前的擊鍵動力學研究著重于固定文本進行靜態認證，即在用戶在輸入用戶名和密碼時進行認證。而在D.Gunetti和C.Picardi[1]在2005年提出了可以在用戶自由的擊鍵時，對用戶進行持續的認證。

目前研究的一些成果[4]，對自由文本的擊鍵動力學研究的對象絕大部分都是以英文為主的西方語言[5]，中文自由文本的研究較少。

在實驗研究中，將采用中文的自由文本模式與相對熵進行結合，在使用相對熵的基礎上，對其進行改進，首次提出使用相對熵進行擊鍵動力學的研究。實驗結果表明，文中提出的認證方法對中文的自由文本的持續身份認證達到了很好的效果。

1　檢測方法

1.1擊鍵時間選取

擊鍵信息的核心是擊鍵的時間信息，而這個時間信息主要有兩個時間點決定：一個鍵的按下時間（press time）和一個鍵的釋放時間（release time）[6]。

擊鍵動力學對于按鍵持續時間的選取有幾個方法[6]，若將連續N鍵的組合作為一個整體，N鍵組合的持續時間的選?。?/p>

（1）第一個鍵按下到第N個鍵按下之間的時間，稱為PP持續時間；

（2）第一個鍵釋放到第N個鍵按下之間的時間，稱之為RP持續時間；

（3）第一個鍵釋放時間到第N個鍵釋放時間，稱之為RR持續時間；

（4）第一個鍵按下時間到第N個鍵釋放時間，稱之為PR持續時間。

以雙鍵為例，第一個鍵的按下時間、第一個鍵的釋放時間、第二個鍵的按下時間以及第二鍵釋放時間，這四個時間的組合可以作為雙鍵持續時間。

圖2　擊鍵時間選取方法

如圖2所示，雙鍵組合的持續時間可以擴展為N鍵組合。在本文中，我們將采用雙鍵的時間，而每一種時間選取都對實驗有一定影響。

1.2中文自由文本與認證標準

根據擊鍵動力學的文獻顯示，靜態認證和持續認證之間有著很大差別[7]。靜態認證是指對用戶在登錄系統時輸入密碼的過程中，對用戶進行認證。靜態認證的文本是固定不變的，所有登錄用戶都是輸入同樣的文本。

與靜態認證不同，持續認證意味著在用戶按鍵時進行連續性和周期性的檢測。由于靜態認證和持續認證的特點不同，持續認證的認證對象都是自由文本。自由文本的意義是，用戶自由地鍵入他們想寫的內容，不受預定文本的影響。當然，所選取的進行實驗的自由文本，是能夠進行有意義的動態擊鍵識別分析最少的文本量。從這點上來看，到目前為止所有的系統引用都應被視為有一定文本量的文本，即是在本系統中自由文本也是內容自由的文本量滿足一定量的文本。

擊鍵韻律作為用戶的生物特征已被證明可行[8]。但是運用擊鍵動力學進行生物特征認證時，構建用戶模型是提供與用戶擊鍵方式相近的一個接受域。

對于所有生物認證方法[8]，最重要的性能指標是錯誤接受率（False Accept Rate，FAR），錯誤拒絕率（False Reject Rate，FRR），和相等錯誤率（Equal Error Rate，EER）。FAR反映的是一個生物認證系統的認證的功能指標，其值越高，說明合法用戶被系統接受的可能性更高，非法用戶被系統接受的可能性也同樣更高。FRR反映的是一個生物認證系統的認證的性能指標，其值越高，說明非法用戶被系統接受的可能性更低，合法用戶被系統接受的可能性也同樣更低，相對的系統性能降低，易用性降低。相等錯誤率EER可以作為一個單項性能指標，因為它表明當FAR和FRR相等時的誤差量度，EER值越低，代表著這個認證或識別方法的性能越好。FAR值越小，代表FRR值越小。

1.3相對熵

熵是一體系中的狀態函數，其值與達到狀態的過程無關。在文中熵指的是香農熵，表示一條信息的信息量大小和它的不確定性有直接的關系。一個隨機變量X，其值為{x1，x2，…，xn}的相對熵H（X）為：

E表示期望，I表示隨機變量的信息量。

如果用一個變量p表示X的質量函數，那么公式可寫作：

對數基數b的值為2。

對于一個未認證的用戶B，他進入系統時聲稱與合法用戶A為同一個人。那么，需要將用戶B擊鍵形成的待測文本與用戶A的樣本文本進行比較，得出認證結果。假設已有的樣本文本A的一個有限序列值為{a1，a2，…，an}，而待測文本B的相同的有限序列值為{b1，b2，…，bn}。由此，可以確定樣本文本有限序列的的全部信息的不確定度，為：

同理，若待測文本聲稱與樣本文本屬于同一人的文本，那么可得待測文本有限序列的全部信息的不確定度為：

因此，這兩個量的差異

上面公式是a和b兩個概率分布的量化差異。這是經典的相對熵：

結果會得到一個值，這個值表明了A與B之間的全部信息的差距的一個度量。對于用戶A的文本的樣本序列集{a1，a2，…，an}，其中任意一個元素ai（i∈1，2，…，n）包含的信息量包括了用戶擊鍵韻律的時間信息和文本信息，以量化標準就是文中ai所表示的雙鍵在全文中的詞頻w（ai）和雙鍵的持續時間t（ai）。同理可得，B與A量化后的差異為：

式（7）就是B與A的相對熵量化差。

1.4判定標準

由于個人的擊鍵持續時間是服從高斯分布的，這里將用系數k作為調節閾值，作為認證的接受域控制。

對于已有的樣本文本，已經確認了樣本A1{a11，a12，…，a1n}與樣本A2{a21，a22，…，a2n}是同一用戶提供樣本。可以得到A1與A2一個相對熵。

根據式（8）可得對于合法用戶A所有樣本，得到其平均的相對熵。

由式（9）可知，對于一個聲稱屬于用戶A的新樣本B，可以提取得到他相同的一個文本B{b1，b2，…，bn}，對于任意Ai（i=1，2，…，n）是用戶A的一個樣本。如果滿足式（10）情況，那么認定樣本B是用戶A的一個新樣本；否則，認定B是一個入侵者的樣本。

2　實驗及結果

2.1實驗設置

在進行實驗的過程中，邀請到了12位志愿者為我們提供訓練樣本，每一位提供的訓練樣本的樣本空間較大，最少會有300kb的文本。本文通過編寫一個程序，在志愿者知曉的情況下，獲取志愿者使用騰訊QQ這款SNS進行聊天時的擊鍵數據。這個程序提前安裝志愿者自己的筆記本計算機上，是隱蔽執行的。每一位志愿者在進行聊天時，聊天的內容是不受限制，根據實際聊天情況輸入信息。在志愿者輸入達到一定數據量的數據時，就會生成一個文本，并自動發送到指定的計算機上。這個文本之中記載了志愿者在這次聊天過程中，敲擊的所有按鍵以及每個按鍵的按下時間和釋放時間。

這些樣本在實驗時可以確定每位志愿者的模型。這幾位志愿者被要求在固定的計算機上聊天，不能變換機器，他們聊天生成的數據被固定保存在對應計算機內，并且作為每一臺計算機的檢測標準。另外，再邀請30位志愿者，這些志愿者本文只選取他們的一個定長文本，這些人是作為入侵者，在實驗中檢測他們是否被判斷為合法用戶。這些志愿者可以在任何一臺計算機鍵入，但是這些志愿者提供數據則統一保存在了一起，不需作為檢測樣本。

每一位志愿者的母語都是漢語，平常在進行聊天時，都是使用漢語交流，敲擊習慣符合一般中文輸入的習慣。由于志愿者均有自己的筆記本電腦，是熟練掌握鍵盤輸入的熟手，所以連續的兩個雙鍵鍵入的時間間隔是有限的，由此，本文中設定雙鍵持續時間大于500ms的全部視為非連續雙鍵，不予采納。

在獲取了志愿者擊鍵的文本后，從中提取相關信息。每一位志愿者聊天的語言組織差別較大，同時由于可能用戶使用了不同的輸入法，對同一個詞敲擊也有不同習慣。本文取所有志愿者在聊天時使用最為頻繁的十組雙鍵，這些雙鍵組合為{wo，in，an，en，ng，sh，ch，zh，on，ni}，。每一個提供模型志愿者得到雙鍵持續時間集合的訓練文本，每一位志愿者的其中一個雙鍵至少有1000個持續時間，有一個至少10×1000個雙鍵的訓練文本（樣本中雙鍵總量大很多，考慮到還有還有其他雙鍵存在，選取的雙鍵只占一部分）；每一個作為入侵者的志愿者用同樣方式訓練之后，每一位志愿者的其中一個雙鍵至少有100個持續時間，有一個至少10× 100的入侵文本。作為入侵者的志愿者提供的樣本以固定大小攻擊所有訓練文本，同時訓練文本也可以隨機劃分出與入侵者文本量同樣大小的若干文本。

2.2識別效果

在這里，將相對熵的認證效果，與歐氏距離進行對比。歐氏距離（Euclidean Distance）是在擊鍵動力學中效果比較好的一種認證方法，在這領域有廣泛的應用。（引用）對于兩種不同的認證方法，按照相同的實驗設定進行實驗。一個志愿者的樣本作為檢測樣本，其他的志愿者作為入侵者進行認證，可以得出FAR效果。得到的結果如下。

圖3　兩種距離對比FAR效果圖

圖3為兩種方法在使用k作為收斂域的閾值時，不同的k值得到的效果。隨著k值的增大，用戶接受域擴大，表示對合法用戶被系統接受的可能性更高，非法用戶被系統接受的可能性也同樣更高。在每一個相對的接受域范圍內，相對熵的錯誤接受率FAR都更低，效果有明顯提升。

然后，用志愿者本人的樣本作入侵者進行認證，可以得出FRR的效果對比。結果如圖4所示。

由圖4可以看出，相較歐氏距離，相對熵的FRR提升也有比較明顯。隨著k值增大，合法用戶與非法用戶接受率都會降低，但是相對熵的錯誤接受率FRR都更低，效果更好。

圖4　兩種距離對比FRR效果圖

總的來講，在逐步擴大訓練文本的情況下，其相對熵作為擊鍵韻律判斷會進一步準確和細化，在此條件下，檢測出一個新文本是否屬于合法用戶所需要的文本大小也會越來越小。當訓練文本足夠大時，對于只有一段文本量較小的新樣本，也能夠做出正確檢測。

3　結語

在基于中文文本的生物特征的擊鍵動力學研究中，對擊鍵的時間序列分別采用歐氏距離與相對熵進行認證。經過志愿者們提供的大量數據的檢驗，驗證了相對熵對擊鍵韻律的認證能夠很好地檢測出合法用戶和入侵者，效果比歐氏距離更佳。相對熵的效果比歐氏距離有明顯提升，系統實現也相對簡單。通過采用這種方法實現擊鍵動力學的生物特征識別，并可以聯系其他生物特征建立一個擊鍵動力學的多模態生物特征識別系統[9]。對生物特征識別系統，最大的威脅時偽造生物特征。在未來的工作中，探討如何提出的方案可以防止偽造使用合成生物技術[9]。這樣可以進一步提高擊鍵動力學的性能。

[1]D.GUNETTI and C.PICARDI.Keystroke Analysis of Free Text[C].ACM Transactions on Information and System Security（ACM TISSEC），Vol.8，No.3，August 2005，Pages 312~347

[2]R.Giot and Mohamad.El-Abed and C.Rosenberger.Web-Based Benchmark for Keystroke Dynamics Biometric Systems:A Statistical Analysis[C].Intelligent Information Hiding and Multimedia Signal Processing（IIH-MSP），2012 Eighth International Conference on 18-20 July 2012，pages 11~15

[3]K.Killourhy and R.Maxion.Comparing Anomaly-Detection Algorithms for Keystroke Dynamics[C].Dependable Systems&Networks, 2009.DSN'09.IEEE/IFIP International Conference on June 29 2009-July 2 2009，pages 125~134

[4]S.Cho,C.Han,D.H.Han,H.Kim.Web-based Keystroke Dynamics Identity Verification Using Neural Network[M].Journal of Organizational Computing and Electronic Commerce,10（4）:295~307,2000

[5]S.Haider,A.Abbas,and A.K.Zaidi.A Multi-Technique Approach for User Identification Through Keystroke Dynamics[C].IEEE International Conference on Systems,Man and Cybernetics,pages 1336~1341,2000

[6]E.Yu and S.Cho.GA-SVM Wrapper Approach for Feature Subset Selection in Keystroke Dynamics Identity Verification[C].In Proceedings of the International Joint Conference on Neural Networks（IJCNN）,pages 2253~2257.IEEE Press,2003

[7]P.Kang,S.Hwang,and S.Cho.Continual Retraining of Keystroke Dynamics Based Authenticator[C].In Proceedings of the 2nd International Conference on Biometrics（ICB'07）,pages 1203~1211.Springer-Verlag Berlin Heidelberg,2007

[8]R.Joyce and G.Gupta.Identity Authentication Based on Keystroke Latencies.[M].Communications of the ACM,33（2）:168~176,1990

[9]giotetR.Giot,M.El-Abed,B.Hemery,C.Rosenberger.Unconstrained Keystroke Dynamics Authentication with Shared Secret[J]. Computer.Security,vol.30,no.6~7,pp.427~445,June 2011

Relative Entropy;Keystroke Dynamic;False Acceptance Rate;False Rejection Rate

User Authentication of Keystroke Dynamics Chinese Free-Text Based on Relative Entropy

HUANG Yi-ran，HU Xiao-qin

（College of Computer Science,Sichuan University，Chengdu 610065）

Keystroke dynamics,the user's keystroke rhythms analysis and processing,can be used as an effective method to take a legitimate user identification and intrusion detection.It is useful for continuously verifying a user once the authentication process has successfully ended. Proposes to use the relative entropy as the authentication method.Obviously,improves the effectiveness and efficiency of the certification significantly.The results are encouraging and suggest that attains a lower false acceptance ate and false rejection rate than Euclidean Distance.

1007-1423（2015）12-0009-05

10.3969/j.issn.1007-1423.2015.12.002

黃怡然（1988-），男，重慶涪陵人，碩士研究生，研究方向為網絡與信息安全安全

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

2015-03-24

2015-04-16