基于加权相对距离的自由文本击键特征认证识别方法

宋梦玲，胡晓勤

（四川大学计算机学院，成都　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。可见加权相对距离算法优于传统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方法对击键序列的认证效果更理想。总体而言，随着击键个数的增加，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-），男，四川内江人，博士，讲师，研究方向为信息安全