基于相对熵的击键动力学中文自由文本用户认证

黄怡然，胡晓勤

基于相对熵的击键动力学中文自由文本用户认证

黄怡然，胡晓勤

（四川大学计算机学院，成都610065）

击键动力学——对用户的击键的韵律进行分析和处理，已经可以作为一种合法用户识别和入侵检测的一种有效方法。认证的过程是通过观察在击键时的用户行为模式进行判断。在这里，提出运用相对熵作为击键动力学的认证方法，跟之前的方法相比，从认证效果和效率上都有明显提升。实验结果表明，相对熵比传统的欧氏距离方法的错误接受率和错误拒绝率更低，效果更好。

相对熵；击键动力学；错误拒绝率；错误接受率

0　引言

互联网所具有的开放和互联的特性，使得互联网本身具有极大的安全隐患。而传统的用户——口令模式，容易被非法用户获取，可能导致许多重要的隐私的信息泄露。

基于生物特征的认证技术是通过对一个人的在生理或行为特征进行研究，以自动化的方法进行验证或确认那个人的身份。

图1　生物特征的认证技术发展过程

击键动力学就是将击键特性运用于入侵检测能有效地识别用户[1]。研究表明，个人用户的击键特性犹如指纹，难以模仿[2]。击键动力学研究对象时个人的击键的节奏和时间，这是相对稳定的。可以根据击键的节奏和时间来区分不同的人[3]。击键动力学始终是个有趣的课题：（1）因为这项技术的信息获取是通过用户提供的击键信息，而不是通过入侵系统来获取；（2）这项技术不需要昂贵的硬件设备，实现成本不高。

以前的击键动力学研究着重于固定文本进行静态认证，即在用户在输入用户名和密码时进行认证。而在D.Gunetti和C.Picardi[1]在2005年提出了可以在用户自由的击键时，对用户进行持续的认证。

目前研究的一些成果[4]，对自由文本的击键动力学研究的对象绝大部分都是以英文为主的西方语言[5]，中文自由文本的研究较少。

在实验研究中，将采用中文的自由文本模式与相对熵进行结合，在使用相对熵的基础上，对其进行改进，首次提出使用相对熵进行击键动力学的研究。实验结果表明，文中提出的认证方法对中文的自由文本的持续身份认证达到了很好的效果。

1　检测方法

1.1击键时间选取

击键信息的核心是击键的时间信息，而这个时间信息主要有两个时间点决定：一个键的按下时间（press time）和一个键的释放时间（release time）[6]。

击键动力学对于按键持续时间的选取有几个方法[6]，若将连续N键的组合作为一个整体，N键组合的持续时间的选取：

（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