抗特征点匹配识别的滑块式拼图验证码

朱理奥, 曹天杰

(中国矿业大学 计算机科学与技术学院,江苏 徐州 221116)

0 引 言

随着网络商店、论坛等平台的普及,攻击者可以通过运行脚本进行批量注册,之后通过操纵这一批虚假用户来进行诸如恶意差评、恶意转发、恶意发送邮件等行为,既破坏了平台用户的使用体验,也给人们生活带来不便。同时,由于越来越多的商家会在网络平台进行抢购促销,脚本刷票的行为也将为攻击者带来不正当的利益。此外,反复进行的暴力穷举攻击也会对于系统安全产生较大威胁。为了应对这一系列威胁,验证码的概念被人们所提出。验证码,全称为完全自动地区分人类与机器的公共图灵测试(completely automated public turing test to tell computers and humans apart, CAPTCHA)[1],是一种可以有效区分人类用户和机器的测试。

验证码对于用户身份究竟是人类还是计算机程序进行区分,可以迫使意图进行恶意行为的攻击者放弃计算机自动化批量操作而进行人工手动操作,从而加大了攻击者进行大量重复操作时的时间成本,它被视为网络系统安全的一个不可或缺的部分。

目前由于机器学习技术和图像处理技术的不断进步,针对验证码的破解与识别技术也在不断加强。原本被认为有效的验证码,如今正在面临挑战。因此有必要研究和修改验证码,以便提高安全性。本文针对利用特征点匹配来攻破滑块式拼图验证码的攻击方法进行研究,提出一种能够抵抗这一攻击方式的验证码设计方法。

1 相关工作

验证码这一概念最早由文献[2]提出,主要是针对当时Yahoo邮箱的垃圾邮件问题。之后学者们进行了很多验证码相关的研究工作。

最初,验证码主要是基于文本和基于图像的验证码,但是由于机器学习技术和图像处理技术的进步,攻破这一类验证码已不再具有难度,目前已经有相当数量的攻击方法被提出[3-6]。

因此,人们对于新的验证码类型进行了探索,提出了诸如互动式游戏(dynamic cognitive game, DCG)、隐形验证码[7]、眼动验证码[8]、动态物体识别验证码[9]等新的验证码类型。其中,运用最广泛的,便是DCG验证码。这是由于相比于其他类型的验证码,它更为简单,用户在实际使用过程中也更为方便,并且与那些依赖用户生物信息进行的验证相比,不需要专门的硬件支持,同时相比于谷歌推出的noCAPTCHA,一个通过利用用户操作行为进行区分的人机识别机制,不需要收集用户隐私数据。

目前应用最为广泛的一种DCG验证码,是通过让用户完成一个拼图来进行验证的滑块式拼图验证码。这种验证码会将图像中的一部分作为由滑块控制的拼图块,将其位置的原有图像进行暗化处理,得到背景图片,要求人类用户能够察觉出颜色异常的位置,进而明白应当操作滑块将拼图块移动至指定位置。而计算机解决察觉所谓“颜色异常”部分的问题比较困难,因此可以进行人机区分。

对于这一类验证码的攻击,主要是利用验证码认证协议上的漏洞来绕过验证码,而并非识别和攻破验证码本身。基于该问题文献[10-11]提出了通过将目标网站的验证码伪装成正常访问时所需要的验证码,转发给其他普通人类用户来完成的攻击方法;文献[12]提出了利用验证码在客户端验证的特点,伪造已经通过的结果来避免解答验证码,并提出了利用验证码在客户端生成的特性,获取未经处理的原始背景图片,从而计算出目标位置,进而完成验证;文献[13]提出了利用验证码生成时可能会使用同一张图片来生成多个不同验证码的情形,通过使用同一图片的不同验证码来还原出原始图片,进而获取目标位置。对于验证码本身进行攻破,即能模拟人类行为解决这一类验证码的攻击方法,目前只有文献[14]中所提出的基于特征点匹配的方法以及暴力穷举法。

2 基于特征点匹配的攻击方法分析

文献[14]中提出了一种攻破滑块式拼图验证码的方法,具体步骤如下:

(1) 通过特征点(指图像中与周围像素点存在显著差异的像素点)匹配获取目标位置。

(2) 利用机器学习的方法模拟人类移动滑块的鼠标轨迹进行移动,完成验证。

在步骤(1)中,通过利用滑块式拼图验证码在给用户发布任务时,具有将目标位置的图像完整保留,只进行暗化处理的特点,使用Canny算子获得拼图块的特征点模板和背景图片的特征点分布之后,进行目标位置匹配。其中,Canny算子[15]的主要工作流程如下。

(1) 将图片转化为灰度图,具体的转化公式如下：

Values=0.299R+0.587G+0.114B，

其中,Values为转化后相应像素点的像素值;R、G、B分别为转化前该像素点在红、绿、蓝3个通道的值。

(2) 使用如下公式对图片进行高斯滤波,去除噪声,即

其中,(x,y)为像素点的坐标;σ为高斯分布的标准差。

(3) 使用如下2个公式计算X和Y方向的偏导数,以便进行梯度幅值和方向角的计算,即

梯度幅度和方向角的计算公式分别为:

(4) 进行非极大值抑制。

(5) 利用滞后阈值法(即一高一低2个阈值),对像素点进行提取和连接,获得边缘。

由此可以看出,Canny算子是进行边缘检测,即所谓的“特征点”实质上是图片之中的边缘中心。

因为滑块式拼图验证码本身保留了目标位置的图像信息,而拼图块本身便是目标区域的图像,所以在提取出边缘之后,只需要研究每一个位置的图像与拼图块边缘的重合程度,即匹配分值(原文定义为模板图案与目标图案在相同位置上具有的特征点数量占总特征点数的比例),便能找到目标位置。因此,使滑块式拼图验证码能够对抗特征点匹配的关键,便在于干扰Canny算子的边缘检测。

由于Canny算子本身具有的高鲁棒性特点,增加干扰像素的效果可能事倍功半。本文将采用删除特征点的方法,降低目标位置与拼图块在特征点分布上的重合度,从而避免被寻找到目标位置。不过需要注意的是,为了能让人类用户通过验证,应当保留一部分图像信息,以便让人类用户能够定位目标位置。

文献[14]中同样也提到,因为滑块式拼图验证码只有一个水平滑块,即拼图块必定与目标位置拥有相同的纵坐标,针对每一个可能位置计算匹配分值是可能并且开销较小的。因此,本文的方法将会扩展目标位置的可能性,从一维扩展至二维,来提高遍历搜索的成本。这一行为理论上也能提高暴力穷举攻击的成本。

3 部分抹除特征点方案

本方案不将整个目标位置的图像信息删除,而仅仅是进行部分删除。具体而言,是对目标位置内的像素点选择一部分更改为同一像素值,使得目标位置特征点的匹配分值M满足:

M≤Maverage，

其中,Maverage为目标位置所在行除目标位置本身以外的各位置的匹配分值平均值。

因为匹配分值本身被定义为匹配的特征点占总特征点的比例,所以仅仅需要至少修改(1-Maverage)N个特征点即可,其中N为目标位置的特征点总数。

因为Canny算子本身会过滤非特征点,对于非特征点的改动不会影响Canny算子对于特征点的提取,所以出于方便考虑,可以将一个包括至少(1-Maverage)N个特征点的圆形区域内的所有像素点都更改为同一个像素值V,即可实现对目标位置图像信息的部分删除。

根据以上的思路,可以得到如下验证码生成方案。本方案中用到的参数如下:m为目标位置区域的长度;n为目标位置区域的宽度;V为抹除特征点时所更改到的像素值;D为验证时的允许误差;W为最大允许尝试次数。这些参数的具体取值根据实际需要确定。

3.1 生成算法

(1) 在一张图片A中随机选择一个位置作为目标位置L,大小为m×n,将目标位置原有图像复制下来保存,作为拼图块P。

(2) 将L所在行设置为感兴趣带Z,利用Canny算子对P进行特征点提取,并且对Z中除了L以外的位置进行特征点匹配,计算每个位置的匹配分值Mi,取其平均数Maverage,即

(3) 对A的L使用Canny算子进行特征点提取,得到Lm,并且统计其中的特征点总数N。

(4) 随机地选取Lm的特征点中的(1-Maverage)N个,做一个可以包括所有这些特征点的几何圆S,将S内的所有像素点的像素值设置为一个特定值V,得到更改后的图像B,作为验证码的背景图像。

(5) 将背景图片B和拼图块P展示给用户。B的展示方式与现有的滑块式拼图验证码的背景图片展示方式相同。为了便于用户找到P,P的初始位置应在B之外,或对其进行用户界面上的提示与指引。

在步骤(4)中,为获取S,使用k-means聚类算法对于选取的要修改的特征点进行聚类,求得聚类中心C坐标为(xC,yC)。之后以C到距离C最远的特征点之间的距离dmax作为半径r,做如下方程:

(x-xC)2+(y-yC)2=r2，

只要L中的像素点的坐标(xi,yi)满足:

(x-xC)2+(y-yC)2≤r2，

即可判定该像素点在圆之内。此处特征点与C之间的距离di定义为:

3.2 验证阶段

考虑到实际应用过程中用户很难精确地移动拼图块到选定的位置,因此还需要增加一个允许误差D。同时额外多增加一个最大允许尝试次数W。只有用户将拼图块移动到L的D范围内并且尝试次数不多于W,才可算通过验证。

需要注意拼图块的起始位置应当随机,不局限于与目标位置处于同一行。同时出于易用性考量,取消水平滑动条,改为要求用户操纵鼠标拖动拼图块来完成验证。

目前已有的滑块式拼图验证码除检验目标位置之外,还会进行鼠标轨迹的人机区分。由于本方案已经能够在理论上保证针对文献[14]的攻击方法以及穷举攻击的抵抗性(理由详见第4节),这一检验环节可以选择进行保留,以便进一步提高安全性。

由于现有的研究均基于一维情形,并且现有数据集也针对的是一维滑块的验证码,在进行相关研究时存在一些困难。一个思路是将文献[15]中的特征加权的朴素贝叶斯模型[16]推广至二维情形,利用一个合适的数据集进行训练之后获得一个分类器,用于对鼠标轨迹进行分类,划分为人类轨迹和机器轨迹两类。这将在未来的研究中进行,本文暂不展开描述。

3.3 软件实现与应用实例

本文方案可以使用python语言进行编写,使用Pillow库进行图像处理,效果示例如图1所示,示例取m=n=32,V=0。从图1可以看出,本文所提出的部分抹除特征点方案使目标位置内部像素点的像素值不再变化。此时使用Canny算子将无法有效识别出目标区域内部的边缘特征。本文方案由此抹除了目标位置内部图像的边缘特征信息,降低了目标位置的匹配分值,但保留了区域边缘的特征,防止攻击者通过寻找匹配分值最低值的方式来获取目标位置。

图1 图像处理效果

本文方案适用于各种需要验证码的环节,诸如用户注册、用户登录、论坛用户留言等等。

以用户留言为例。服务器应当事先保留有大量已经生成的验证码的背景图片和拼图块图片。当用户编写完留言内容后,点击发送留言。此时服务器接收到用户的留言请求之后,将随机选择一组背景图片和拼图块发送给用户进行验证。用户使用鼠标完成验证之后,将拼图块在背景图片上的相对坐标以及用户的鼠标轨迹数据传回服务器,在服务器端进行验证和分析。通过验证则允许用户留言,未能通过便拒绝用户的留言请求。

4 安全性分析

4.1 针对特征点匹配攻击

本文方法确保了目标位置的匹配分值必定不会大于所在的一整行的平均值,则有:

M≤Maverage。

若攻击时设置的匹配分值阈值T满足:

T≥Maverage。

则导致目标位置并不包含在所寻找出来的位置之中。若匹配分值阈值T过小,则有:

T

这虽然可以搜索到目标位置,但是也将会包括大量非目标位置。这将强制要求攻击者针对每一个背景图片进行调参操作,以便选取效果最好的阈值。在规定允许最大的尝试次数W的情况下,避免了验证码被攻破。

4.2 针对穷举攻击

原本由于滑块式验证码的拼图块仅仅是进行水平方向的滑动,导致目标位置的取值可能性有限。针对一个分辨率为M×N的图片,时间复杂度为θ(M)。在本文方案中,由于拼图块改为了需要进行水平和垂直2个方向的移动,从一维变成了二维,因此大大增加了穷举攻击的时间(时间复杂度变为θ(MN))。

因为目标位置存在随机性以及该方案并未对所用来生成验证码的图片作任何要求,并且同一张图可以生成多张验证码,穷举验证码知识库的攻击,所以只要知识库容量足够大,也将需要耗费大量时间。

4.3 针对深度学习方法攻击

由于最近几年利用深度学习的方法进行的验证码攻击研究主要应用于针对文本验证码的识别[17-19]，而并非是本文所研究的滑块式拼图验证码,本文在此仅进行理论分析。

深度学习的攻击方法是通过提取拼图块的图像信息后与背景图片进行匹配,以便找出目标区域,利用的是背景图片中目标区域的图象纹理信息被完全保留的特点。

本文方案中目标位置的信息并不是完整保留的。要删除的特征点占比大小与目标位置所在行的平均匹配程度有关。如果目标位置所在行里没有多个与目标位置相似的纹理,那么目标位置所有的特征点都会被删除,此时目标位置不会包含拼图块的任何纹理信息,深度学习检测方法会难以检测;如果目标位置所在行里包含有多个与目标位置相似的纹理,那么特征点的删除占比会减少,但是此时会检测出多个位置存在拼图块的图案,无法具体确定是哪一个位置。

5 易用性分析

由于拼图块在显示给用户时具有一定透明度,用户在控制拼图块进行验证时,可以通过拼图块与目标位置未被抹除的部分进行线条对齐,或是观察移动完成后是否存在图像连接偏差,从而定位目标位置,并且由于允许误差D的存在,允许用户在完成验证时存在一定的偏差。

用户虽然需要在一个二维平面上移动拼图块,但是仍然只是沿着斜方向的一条直线进行移动,这不会增加完成测试的用时。同时该方案并未对滑块式验证码的图片显示部分进行修改,本质上依然只是让人类用户完成一个拼图游戏,因此理论上依然保存了易用性。

6 实 验

使用python 3.7进行编程,图形界面使用Qt 4.7.0进行实现,CPU为i7-8750H，操作系统为Windows10,实验图片来自于显著性目标检测数据集。

单次的抵抗攻击实验步骤如下:

(1) 对于一张图片,利用本文方法生成新的验证码。

(2) 使用文献[14]的方法进行攻击(实验中直接选取具有最高匹配分值的位置作为攻击中识别出来的目标位置),判断是否准确获得了目标位置。

(3) 使用穷举攻击,记录为获取目标位置必须经过的穷举次数的平均值。

对每一张图片进行抵抗攻击实验,计算文献[13]的方法和穷举方法对于目标位置的平均识别准确率,并且研究参数D对于识别准确率的影响。之后由人类进行验证码验证测试,记录通过率以及平均时间消耗。

由于拼图块一般比较小,实验中选取V=0,m=n=32。

随着参数D的变化,特征点匹配攻击的平均识别准确率P、穷举攻击的平均尝试次数U的变化情况见表1所列，如图2所示。

表1 D与P、U的关系

可以看出,本文提出的方法在D≤2时,文献[14]的识别算法对目标位置的识别准确率不足1%。但是由于D的增大提高了容错率,导致识别率随着D的增加而增大。无论D的取值如何,尽管D的增大同样也会减少穷举攻击的尝试次数,穷举攻击方法依然都需要大量的尝试才能找到目标位置。

图2 D与P、U的关系

因此,本文方案对于文献[14]中的识别算法具有抵抗性,对于穷举攻击也具有抵抗性。

人类实验中,由2名志愿者进行实验,每人进行20次验证测试，实验结果见表2所列。表2中,Pass为通过率;t为通过测试的平均用时。D与Pass、t的关系如图3所示。

表2 人类实验结果

显然,人类测试通过率随着D的增大而增大,并且在D=3时达到100%，这是由于D增大提高了验证的容错率引起的。人类测试的平均用时则随着D的增大而减小,这是由于D的增大提高了容错率,使得用户在将拼图块拖拽至目标位置后的反复对齐的用时减少了。

一般现有的滑块式拼图验证码的人类完成时间在1～3 s之间,因此可以得出本文方法并未牺牲用户的易用性。

综上所述,本文方案在没有牺牲用户易用性的前提下,具有对特征点匹配攻击的抵抗性。允许误差D在提高用户验证效率的同时,也会带来对于特征匹配攻击的抵抗性的下降。这在实际使用时应当根据实际需要进行权衡取舍。

图3 D与Pass、t的关系

7 结 论

本文针对文献[14]中所提及的利用特征点匹配来绕过验证码的方法进行了分析,并针对性地提出了一个删除目标位置部分特征点的验证码生成方案,使所生成的验证码具有对于此类攻击的抵抗性。本文同时对滑块式验证码进行了用户操纵上的改进,取消了原有的滑动条,将拼图块作为滑块,并且扩大了拼图块的坐标位移维度,以便抵抗穷举攻击。攻击实验和人类测试实验证明,本文的方案在保证用户易用性的情况下,对于基于特征点匹配的攻击方法具有抵抗能力。

本文方法仅仅针对目标位置的选取和处理进行了改进。在实际应用中,可以进一步利用鼠标轨迹的时空特征区分机器与人,以便达到更高的安全性。此外,本文未能针对利用深度学习的攻击方法进行分析，这都将在未来的研究中进行探讨。