基于加速度传感器的WLALCS身份认证及实现

高焕芝+郭云镝+刘晴+陈再良+邹北骥

收稿日期：20140326

基金项目：国家自然科学基金资助项目（61173122，61262032）；湖南省自然科学基金资助项目（12JJ6059， 12JJ2038）

作者简介：高焕芝（1976-），女，河北唐山人，中南大学博士研究生

通讯联系人，Email：csgrandeur@csu.edu.cn

摘要：针对当前移动设备身份认证方法或易破解、或难实现、或成本高的问题，提出一种新的基于手机加速度传感器的人体感知身份认证方法.该方法利用当前手机普遍内置的加速度传感器采集人体运动数据（通常为动态手势），结合经典匹配算法LCS，提出限制匹配窗口的近似判等最长公共子序列算法，对采样点序列限制区间匹配，针对浮点数据对采样点距离近似判等，进行数据匹配实现身份认证，并基于云计算模型实现了手机身份认证平台.较之已有的基于手势身份认证方法，有效降低了针对模仿动作攻击的接受错误率，非攻击认证相等错误率为2%，而模仿动作攻击的相等错误率降低至5%.该系统具有易于在各类移动设备系统部署，不需要额外的设备等优势，且基于生物特征原理，特别加强了抵抗模仿动作攻击的健壮性，不易被破解.

关键词：加速度传感器；身份认证；近似判等最长公共子序列；云计算

中图分类号：TP391 文献标识码：A

Accelerometer Based Authentication Method in WLALCS

GAO Huanzhi1， GUO Yundi1，2， LIU Qing1，2， CHEN Zailiang1，2， ZOU Beiji1，2

（1.School of Information Science and Engineering， Central South Univ，Changsha，Hunan410083， China；

2. Mobile Health Ministry of EducationChina Mobile Joint Laboratory， Changsha，Hunan410083， China ）

Abstract：Aiming at problems in authentication methods of mobile devices， such as being easy to crack or difficult to implement or high costs， this paper presented a new mobile phone acceleration sensor authentication method on human perception. To use the current widespread acceleration sensor in mobile phones to capture human motion data （typically dynamic gesture）， we proposed an authentication algorithm named Window Limited Approximate Longest Common Sequence （WLALCS） based on the classical matching algorithm LCS. And we implemented an authentication system on cloud computing model. Compared with the existing gesture and accelerometer based authentication methods， this method effectively reduced the equal error rate on imitate action attack. Nonimitate attack authentication EER （Equal Error Rate） is 2%， and imitate attack authentication EER is 5%. This system is easy to deploy on any smart phone systems and does not need any additional sensors. Based on the biological characteristics， we reinforced the robustness towards mimicry attack.

Key words：accelerometer； authentication； Window Limited Approximate Lonest Common Sequence（WLALCS） ； cloud computing

传统的身份认证方法有用户名密码、PIN、文本形式和九宫格等，此类方法输入口令的时候很容易被窃取，从而仿冒真实用户身份，简单的口令容易被破解，复杂的口令造成用户记忆上的不便.因此，需要一种新的更为有效的身份认证方式，要求简单易用、安全可靠.生物特征认证技术的兴起对传统身份认证方法起到了很好的补充和完善作用.

基于生物特征[1]的身份认证，由于其安全、可靠和便利等特点，越来越受到人们的重视，生物特征识别技术在过去的十几年中取得了长足的进展，生物特征认证方法主要有人脸认证[2]、指纹认证[3]、虹膜认证[4]和手写签名认证[5]等.然而在手持设备身份认证方面，以上认证技术存在技术成本高、需要特定的硬件设施和易被仿冒等缺点.

随着2010年以来智能手机市场的爆发式增长，当前的手机普遍带有加速度传感器（三轴加速度传感器、陀螺仪等），同时结合手机本身能够运行软件的特性，为低成本、高效率实现基于重力加速度传感器的人体行为感知方法与身份认证带来了契机.

近年来智能终端普遍装备了越来越丰富的传感器，出现了新的身份认证方法.如利用三轴加速计进行的步态身份认证[6-8]，利用三轴加速计把简单运动轨迹与密码对应的身份认证[9-10]等.

每个人对持有的物体进行空间移动（通常为手持物体在空间中划动笔画，但不限于用手）时，其动作角度、力度和速度等都具有自己的个体特征，通过智能手机内置加速度传感器则可获取用户移动手机时的这些空间动作信息.针对用户对手机完成的空间移动数据的个体特征进行分析，可实现身份认证.这种认证方法的好处是在数据采集过程中不依赖场景、光照、用户体征完整性（视力、听力和语言等）以及额外的设备，实现成本低，方便易用，可用于需要身份认证的场合，在即将进入移动互联网的时代浪潮下，具有广阔的应用前景.

基于手势的身份认证方法，文献[11]受到步态识别的启发，从生物特征的角度进行了可行性分析，通过加速度传感器采集手势数据，并通过监督和非监督降维进行分类，通过数据分析，提出手势运动可作为人体行为的生物特征，并可应用于小群体的身份认证的结论.文献[12]结合文献[13]中基于手势识别的认证方法在非模仿动作攻击场景下得到了良好的效果，对基于加速度传感器采集手势特征的身份认证方法前景给出了积极的观点.文献[13-15]描述了几种基于手机三轴加速计进行手势身份认证的方法，文献[14]基于特定的手势进行认证，不允许用户自定义个性化的手势.文献[15]中的方法需要较多的训练样本才能达到较为理想的相等错误率（Equal Error Rate，EER），文献[13]中的工作更侧重于人机交互的手势识别精度，而认证方面，在非攻击认证情况下取得了较好效果，但对于针对性模仿动作攻击，EER依然为10%，无法应用于关键性信息的加密认证.

移动设备的身份认证，要求具备易用性与实时性的特征，即要求仅需要较小的样本，不受周边环境影响，同时验证花费时间短.需要大样本训练的基于学习的方法（如HMM[16]等）、基于视觉（使用摄像头）和语音等方法都会受到一定的限制.

本文基于动态规划原理、最长公共子序列（Longest Common Sequence， LCS）[17]算法，设计了一个限制匹配窗口的近似判等最长公共子序列（Window Limited Approximate Longest Common Sequence， WLALCS）算法，并以动态时间规整（Dynamic Time Warping， DTW）[18]作为辅助判断条件，在Lumia1520和PC服务器上实现了基于云计算的手机身份认证原型系统.该系统整个认证过程在50 ms左右，系统不受光照和噪声等环境影响，通过20名20～30岁的实验者一周时间进行手势动作攻击实验结果，该系统有效将模仿动作攻击的认证过程相等错误率（EER）降低至5%，有效地改善了基于三轴加速计的手势身份认证方法在模仿动作攻击时的不健壮性.

1WLALCS认证算法

本文针对利用加速度传感器提取动作特征进行身份认证问题，基于LCS设计了WLALCS算法，同时以DTW算法作为针对模板与验证数据序列累积距离辅助判断条件.

1.1数据获取及处理

利用Lumia搭载的WP8系统内置三轴加速度传感器获取运动数据，结合软件设置，用户将按钮按下为动作起点，系统开始记录用户动作的加速度数据；按钮松开为手势终点，系统停止记录.

采样频率为60 Hz，获取数据为时间序列的x，y和z三轴加速度g（g为重力加速度，取9.8 m/s2）的浮点数，并对数据平滑处理以消除冲击噪声.

1.2WLALCS算法思想

对于时间序列X，设X.length为X的采样点个数，X[i]为时间顺序第i个采样点.设待匹配序列T为模板序列，S为样本序列.

1.2.1数据筛选

由于人完成特定动作的时间有一定的不稳定性，而人类的反应时间一般在0.3 s，针对采样频率， 0.3×60 = 18，实验时取允许采样点个数误差为20，即对于长度与模板相差超过20的数据将直接拒绝.

1.2.2最长公共子序列（LCS）

最长公共子序列算法是基于动态规划的经典线性序列匹配算法，子序列为线性序列顺序连续或非连续子集，最长公共子序列指两个或多个线性序列的最长非连续公共部分，可有效表示两个线性序列的编辑距离和相似度[17].

算法描述如下[19]：

两个序列T和S的最长公共子序列为LCS（T，S），LCSdp（i，j）表示由序列T的T[1]～T[i]组成的子序列与序列S的S[1]～S[j]组成的子序列的最长公共部分，即该动态规划算法的子问题，如式（1）所示，LCSdp（T.length，S.length）即为LCS（T，S）的结果.

LCST，S=LCSdpT.length，S.length.（1）

由规则EQUAL（T[i]，S[i]）判定T[i]与S[i]相等关系.当EQUAL（T[i]，S[i]）分别为TRUE和FALSE时，LCSdp采取不同的递推规则.EQUAL（T[i]，S[i]）为TRUE时，规则如式（2）所示，为FALSE时，规则为式（3）所示.

LCSdpi，j=maxLCSdpi-1，j-1+1

LCSdpi-1，j

LCSdpi，j-1， （2）

LCSdpi，j=maxLCSdpi-1，j

LCSdpi，j-1.（3）

1.2.3限制匹配窗口

由于人有一定的反应时间，故模板和测试数据序列的动作起点往往是没有完全对齐的，在做LCS时枚举匹配起点，并限制匹配窗口大小，取最长匹配结果为最终匹配结果，即Window limited.取T和S采样点较少的一个的采样点个数为匹配窗口大小，这里假设S.length < T.length，枚举匹配起点start由1至T.length-S.length，设每个start对应的T[start]～T[start+S.length-1]的采样点组成的序列为P，则WLALCS（T，S）为：

WLALCST，S=max[LCS（P，S）]. （4）

1.2.4近似判等

对于式（2），由于获取的数据序列为浮点数，对于相近的采样点很难完全相等，故可规定两点距离小于一定阈值时判定两点相等，即近似判等.

设定ratio_errdis判等阈值，定义S[i]与T[i]的距离为三轴坐标差的绝对值与T所有采样点对应坐标最大值和最小值的差的比值的和，即

DistanceTi，Si=

∑x，y，zpTi.p-Si.pmaxT.p-minT.p.（5）

则当Distance（T[i]，S[i]）

1.2.5序列相似度

定义序列相似度为WLALCS（T，S）的匹配长度与模版T的长度的比值.即序列相似度matched_proportion为：

matched_proportioin=WLALCST，ST.length. （6）

1.2.6算法复杂度

由于采样点个数与模板相差20以上的样本将被直接排除，故枚举起点的复杂度可视为常数，WLALCS的时间和空间复杂度都为O（T.length·S.length）.

1.3动态时间规整

动态时间规整（DTW）是基于动态规划的对线性序列进行模式匹配的经典算法，文献[13]在手势识别方法上对该算法有了详细的描述，本研究使用此方法作为辅助判断方法，阈值参数会相对放宽.算法简单描述如下：

DTW（T，S）为序列T与S的DTW距离，DTWdp（i，j）表示由序列T的T[1]～T[i]组成的子序列与序列S的S[1]～S[j]组成的子序列的最优DTW距离，DTWdp（T.length，S.length）即为DTW（T，S）的结果，如式（7）所示.最优子问题递推规则如式（8）所示.

DTWT，S=DTWdpT.length，S.length. （7）

DTWdpi，j=minDTWdpi-1，j-1

DTWdpi-1，j

DTWdpi，j-1+

DistanceTi，Sj. （8）

DTW的时间和空间复杂度都为O（T.length·S.length）.

2云计算认证平台

目前流行的移动设备操作系统复杂多样，主流的有Android， IOS， Windows Phone等，但即使相同的Android系统，也因为版本不同，给APP开发者的软件适配带来很多麻烦.同时，现有设备的CPU浮点运算能力与3～5年前的PC机相仿，虽然运行论文所提算法没有问题，但对于未来提高认证精度而可能会采用的更为复杂的算法，移动设备的硬件压力将越来越大.目前移动互联网已进入3G时代，而4G技术也正在兴起.本文所采集的每组手势数据仅为1～5 kB，足够在普通应用场所进行快速数据交换.

云计算是一种新兴的计算模型，对用户透明，用户无需了解云计算的具体机制即可获得需要的服务[20].基于云计算认证平台的实现，使得客户端的开发只需要考虑数据的采集和发送，整个认证过程在云端进行，极大地提高了开发效率和身份认证算法的运行效率，降低APP开发的适配压力，解放了移动设备CPU和存储设备，对未来利用云端的手势数据进行大数据分析也带来了便利.

2.1总体设计

客户端为移动设备，服务端为计算机服务器.客户端将采集的手势数据发送至服务器，在服务器进行匹配认证，并将认证数据存储在数据服务器，以供未来研究分析.并返回结果给客户端.数据传输遵循TCP/IP协议，客户端通过无线网发送数据，系统总体设计如图2所示.系统自顶向下分为数据处理云端、数据交换接口、客户端、用户，系统结构如图3所示.

2.2实现

2.2.1数据处理云端

数据处理云端，实验采用普通酷睿双核，4 GB内存PC机，基于WPF开发的集数据接收发送、存储、管理、匹配认证、图形化分析于一体的服务器软件，能够实时侦听用户数据，存储历史认证数据，对用户认证信息进行快速反馈.

2.2.2数据交换接口

客户端与服务器的数据交换使用TCP/IP协议，通过客户端与服务器建立TCP链接.客户端采集的手势数据以文件流形式通过TCP链接发送至服务器，数据格式为：

1）指令行，标定数据文件处理方式，以@开头.

2）用户信息，标定发送数据的用户.

3）手势数据.

2.2.3客户端

客户端通过调用传感器的API获取用户手势数据，在手势结束后对数据打包进行发送.

3实验结果与分析

本文针对认证系统对模仿动作攻击的健壮性，设计不同组别的手势，并令参与实验人员了解手势的执行方式和执行时间，并且所有实验者完全在视觉暴露的环境下执行手势，互相作为模仿动作攻击对象.

3.1实验结果

通过对序列相似度认证阈值threshold的研究，对于模仿动作攻击数据，受试者工作特征（receiver operating characteristic，ROC）曲线如图4所示.

图4中，FAR为认假率（False Accept Rate），FRR为拒真率（False Reject Rate），对于模仿动作攻击认证，EER达到5%，优于文献[7]和[8]中的10%.对于非模仿动作攻击认证，所提方法的EER也达到了2%，优于文献[7]和[8]中的3%.认证效果对比如表1所示.

3.2实验分析

由图4可知，随着threshold值的增加，用户的认证难度加大，同时对模仿动作攻击的防御能力也随之增强.而在模仿动作攻击成功率降低至较低水平时，用户认证的成功率依然比较可观.

不同的人做手势的时候，由于个人习惯、肌肉强度和骨骼结构不同等方面的影响，动作不同阶段特别是变换速度与方向的时候会有较大的差别，大多数情况下完成一个动作的时间乃至一个动作的不同阶段的时间会有不同，仅从采样点累积距离角度出发，不能很好地反映这方面的差异.论文所提算法采用了限制窗口的近似最长公共子序列方法，有效地反映了模板与测试数据之间局部运动速度特点的差异和整体动作的采样点匹配比例，在模仿动作欺骗攻击的防御上起到了更好的效果.

4总结

针对基于手机加速度传感器进行身份认证方法中，对于模拟动作攻击的健壮性不强的问题，进行了算法研究，提出WLALCS算法在保持正常认证环境下的认证精度的前提下，有效提高了模拟动作攻击的抵抗力.

通过模拟动作攻击实验，建立了近2 000个手势的模仿动作攻击手势数据库，通过实验，所提算法WLALCS的EER达到了2%，模仿动作攻击EER达到了5%，对于模仿攻击具有了更好的防御性，提高了认证系统的安全性.

研究基于NOKIA Lumia1520，个人计算机实现了云计算模型认证系统.WLALCS算法结合基于云计算模型的认证系统，有效减轻了不同系统移动终端开发的适配压力，解放了移动终端的CPU和存储压力，认证算法的运行效率不再受限于移动终端CPU配置的高低，为未来实现更为复杂精细的认证系统提供了条件.认证历史数据存储在云端，也使针对动作特征的大数据分析成为可能.

参考文献

[1]PANKANTI S， BOLLE R，JAIN A.Biometrics： the future of identification[J]. Computer， 2000， 33（2）： 46-49.

[2]WALLACE R，MCLAREN M，MCCOOL C，et al. Crosspollination of normalization techniques from speaker to face authentication using gaussian mixture models[J]. Information Forensics and Security， IEEE Transactions on， 2012， 7（2）： 553-562.

[3]NANNI L， BRAHNAM S， LUMINI A. Biohashing applied to orientationbased minutia descriptor for secure fingerprint authentication system[J]. Electronics letters， 2011， 47（15）： 851-853.

[4]BANERJEE S， MUKHOPADHYAY S， RONDONI L. Multiimage encryption based on synchronization of chaotic lasers and iris authentication[J]. Optics and Lasers in Engineering， 2012， 50（7）： 950-957.

[5]SCHEIDAT T， KMMEL K， VIELHAUER C. Short term template aging effects on biometric dynamic handwriting authentication performance[C]//Communications and Multimedia Security. Berlin：Springer Berlin Heidelberg， 2012： 107-116.

[6]GAFUROV D， HELKALA K， SNDROL T. Biometric gait authen tication using accelerometer sensor[J]. Journal of computers， 2006， 1（7）： 51-59.

[7]TAMVIRUZZAMAN M， AHAMED S I， HASAN C S，et al. ePet： when cellular phone learns to recognize its owner[C]//Proceedings of the 2nd ACM Workshop on Assurable and Usable Security Configuration. ACM， 2009： 13-18.

[8]DERAWI M，NICKEL C，BOURS P，et al.Unobtrusive userauthentication on mobile phones using biometric gait recognition[C]//Intelligent Information Hiding and Multimedia Signal Processing （IIHMSP）， 2010 Sixth International Conference on. Piscataway， N J： IEEE， 2010： 306-311.

[9]PATEL S N，PIERCE J，ABOWD G.A gesturebased authentication scheme for untrusted public terminals[C]//Proceedings of the 17th Annual ACMS Ymposium on User Interface Software and Technology. New York： ACM Press ，2004：157-160.

[10]CHONG M，MARSDEN G.Exploring the use of discrete gestures for authentication[M]. Berlin： Springer Berlin Heidelberg， 2009： 205-213.

[11]FARELLA E，OMODHRAIN S，BENINI L， et al. Gesture signature for ambient intelligence applications： a feasibility study[M]. Berlin： Springer Berlin Heidelberg， 2006： 288-304.

[12]LIU J， ZHONG L， WICKRAMASURIYA J， et al. User evaluation of lightweight user authentication with a single triaxis accelerometer[C]//Proceedings of the 11th International Conference on HumanComputer Interaction with Mobile Devices and Services. NewYork： ACM， 2009： 15.

[13]LIU J， ZHONG L， WICKRAMASURIYA J， et al. uWave： accelerometerbased personalized gesture recognition and its applications[J]. Pervasive and Mobile Computing， 2009， 5（6）： 657-675.

[14]OKUMURA F， KUBOTA A， HATORI Y， et al. A study on biometric authentication based on arm sweep action with acceleration sensor[C]//Intelligent Signal Processing and Communications.ISPACS'06，International Symposium on. Piscataway， N J： IEEE， 2006： 219-222.

[15]MATSUO K， OKUMURA F， HASHIMOTO M， et al. Arm swing identification method with template update for long term stability[M]. Berlin： Springer Berlin Heidelberg， 2007： 211-221.

[16]RABINER L， JUANG B. An introduction to hidden Markov models[J]. ASSP Magazine， IEEE， 1986， 3（1）： 4-16.

[17]HUNT J，SZYMANSKI T.A fast algorithm for computing longest common subsequences[J]. Communications of the ACM， 1977， 20（5）： 350-353.

[18]MYERS C，HABINER L.A Comparative study of several dynamic timewarping algorithms for connected word[J]. Bell System Technical Journal， 1981，60（7）：1389-1409.

[19]CORMEN T，LEISERSON C，RIVEST R，et al.Introduction to algorithms[M]. 3rd ed. Cambridge： MIT Press， 2001：390-397.

[20]ARMBRUST M， FOX A， GRIFFITH R， et al. A view of cloud computing[J]. Communications of the ACM， 2010， 53（4）： 50-58.

[10]CHONG M，MARSDEN G.Exploring the use of discrete gestures for authentication[M]. Berlin： Springer Berlin Heidelberg， 2009： 205-213.

[11]FARELLA E，OMODHRAIN S，BENINI L， et al. Gesture signature for ambient intelligence applications： a feasibility study[M]. Berlin： Springer Berlin Heidelberg， 2006： 288-304.

[12]LIU J， ZHONG L， WICKRAMASURIYA J， et al. User evaluation of lightweight user authentication with a single triaxis accelerometer[C]//Proceedings of the 11th International Conference on HumanComputer Interaction with Mobile Devices and Services. NewYork： ACM， 2009： 15.

[13]LIU J， ZHONG L， WICKRAMASURIYA J， et al. uWave： accelerometerbased personalized gesture recognition and its applications[J]. Pervasive and Mobile Computing， 2009， 5（6）： 657-675.

[14]OKUMURA F， KUBOTA A， HATORI Y， et al. A study on biometric authentication based on arm sweep action with acceleration sensor[C]//Intelligent Signal Processing and Communications.ISPACS'06，International Symposium on. Piscataway， N J： IEEE， 2006： 219-222.

[15]MATSUO K， OKUMURA F， HASHIMOTO M， et al. Arm swing identification method with template update for long term stability[M]. Berlin： Springer Berlin Heidelberg， 2007： 211-221.

[16]RABINER L， JUANG B. An introduction to hidden Markov models[J]. ASSP Magazine， IEEE， 1986， 3（1）： 4-16.

[17]HUNT J，SZYMANSKI T.A fast algorithm for computing longest common subsequences[J]. Communications of the ACM， 1977， 20（5）： 350-353.

[18]MYERS C，HABINER L.A Comparative study of several dynamic timewarping algorithms for connected word[J]. Bell System Technical Journal， 1981，60（7）：1389-1409.

[19]CORMEN T，LEISERSON C，RIVEST R，et al.Introduction to algorithms[M]. 3rd ed. Cambridge： MIT Press， 2001：390-397.

[20]ARMBRUST M， FOX A， GRIFFITH R， et al. A view of cloud computing[J]. Communications of the ACM， 2010， 53（4）： 50-58.

[10]CHONG M，MARSDEN G.Exploring the use of discrete gestures for authentication[M]. Berlin： Springer Berlin Heidelberg， 2009： 205-213.

[11]FARELLA E，OMODHRAIN S，BENINI L， et al. Gesture signature for ambient intelligence applications： a feasibility study[M]. Berlin： Springer Berlin Heidelberg， 2006： 288-304.

[12]LIU J， ZHONG L， WICKRAMASURIYA J， et al. User evaluation of lightweight user authentication with a single triaxis accelerometer[C]//Proceedings of the 11th International Conference on HumanComputer Interaction with Mobile Devices and Services. NewYork： ACM， 2009： 15.

[13]LIU J， ZHONG L， WICKRAMASURIYA J， et al. uWave： accelerometerbased personalized gesture recognition and its applications[J]. Pervasive and Mobile Computing， 2009， 5（6）： 657-675.

[14]OKUMURA F， KUBOTA A， HATORI Y， et al. A study on biometric authentication based on arm sweep action with acceleration sensor[C]//Intelligent Signal Processing and Communications.ISPACS'06，International Symposium on. Piscataway， N J： IEEE， 2006： 219-222.

[15]MATSUO K， OKUMURA F， HASHIMOTO M， et al. Arm swing identification method with template update for long term stability[M]. Berlin： Springer Berlin Heidelberg， 2007： 211-221.

[16]RABINER L， JUANG B. An introduction to hidden Markov models[J]. ASSP Magazine， IEEE， 1986， 3（1）： 4-16.

[17]HUNT J，SZYMANSKI T.A fast algorithm for computing longest common subsequences[J]. Communications of the ACM， 1977， 20（5）： 350-353.

[18]MYERS C，HABINER L.A Comparative study of several dynamic timewarping algorithms for connected word[J]. Bell System Technical Journal， 1981，60（7）：1389-1409.

[19]CORMEN T，LEISERSON C，RIVEST R，et al.Introduction to algorithms[M]. 3rd ed. Cambridge： MIT Press， 2001：390-397.

[20]ARMBRUST M， FOX A， GRIFFITH R， et al. A view of cloud computing[J]. Communications of the ACM， 2010， 53（4）： 50-58.