转载

验证码的认识和简单验证码的攻防

验证码（CAPTCHA）一词，几乎是上网的人都接触过。通俗地将，验证码就是一种把坐在电脑前的人类与机器区分开来的测试，也算是一种最常见反图灵测试。一般来说，验证码由计算机生成，服务器端的计算机知道答案，但在网线这端，应该只有用户（即真正的人）知道答案，而计算机不知道。

从上面的定义里，易得：

验证码应该是不易被计算机识别或破解出来的，如果用简单的算法，也能得到极高的破解率（大于或接近于75％），则这个验证码不算一个合格的验证码。
要攻破验证码，最好的方法应该是机器学习，因为这个方法能让计算机模拟人类的行为。通过一定的样本训练后，机器的识别度会接近人类。
当然，要攻破验证码，找到一些没事干的人进行分布式验证码人肉识别（俗称“打码”），也是一个不错的方法，只不过这种方法需要投入金钱。
要防御破解验证码的攻击，应该从其源头想起——验证码不就是区别人和机器么？那么，鼠标的细微移动，键盘的键入速度，用户（可有可能是电脑）看见验证码后的反应等等，都可以作为识别机器和人的证据。当然，对于验证码，添加一些机器能识别得到，而人类反而看不见的东西，也能很好地揪出那些干坏事的人。
时刻记住，验证码是给人看的，所以要从人的角度破解、防御验证码（攻击）。

破解篇：

当下，最流行的还是图形验证码。让我们来看几个简单的图形验证码，然后分析一下它们的共同点和弱点。

验证码	弱点
	①有背景，但是色调很淡，干扰点的色调也很单一。
	②最弱的验证码，没有任何杂点、背景等。但很久以前，很多论坛都盛行这种验证码。
	③同样是没有背景，但是有了颜色随意的干扰点，略微提高了识别难度。
	④有杂点，有背景，而且杂点还不少。只是验证码主题颜色单调。

很显然，②是最简单的。识别这个验证码，只有一个步骤：匹配字模——直接循环匹配已有的所有的同字体的数据，找出最高的相似度（算法见附录0x01）。但是不是所有的验证码程序编写者都这么不负责。像①③④，虽然还是很简单，但至少可以难到新手们。

但仔细观察可以发现，搅局者只是那些各色的背景和一些干扰点而已。要识别，还是很容易，只是要在②的基础上加上以下几步：

1 、图像预处理：遍历所有像素点，去除背景。由于验证码不像国宝熊猫那么黑白分明，其彩色的信息量极大，不便于处理，所以要二值化，是整张图片变成只含有0与1的矩阵。得到一个W*H的二维数组（矩阵）。

2 、去除干扰：删除干扰的点、线。干扰像素的特点是不连续，占用的像素点与主题有固定的差值（或许不固定，但大小关系一般固定），可以很容易地设计算法容易过滤。而如果干扰像素采用了和验证码正文明显不同的颜色，则可以在第一步二值化中直接去掉。对于干扰线，则有其它的算法（见附录 0x00）。

3 、字符分割：把数组里连续的字符切割成一个个独立的字符。算法很简单，按照列遍历，找到一列没有数据 1 的，就记录。如果字符有旋转的，还得根据边缘把它再给摆直。

以④为例，这是HUSTOJ（一个著名的在线评测系统）的验证码，给出识别的源码：点击下载。

以上种种，都是极为简单的图形验证码。但谷歌这种大公司，就搞出了整我们的验证码，上图如下:

验证码的认识和简单验证码的攻防

这种人都难以辨认的验证码，机器自然很难攻破（前者识别率约为30%，后者为5%）。其实其问题出在“字符分割”这一步。由于扭曲的验证码都粘连在一起，所以不能很好地分割。对于这种字符的分割，最好的方法是“滴水算法”，其原理是模仿水滴从高处向低处自然滴落的过程来对字符串进行切分。具体算法可以参考： http://www.docin.com/p-891657169.html

防御篇：

攻击验证码，其实也比较容易。那么，如果没有相应的防御措施，各大网站上就会充斥着“xxx001”、“xxx002”、“xxx003”等ID，在评论里发着各种广告。这不能被容忍！还记得上面那个让人抓狂，让电脑“爆炸” 的变态验证码么？要从验证码识别的角度防御验证码破解，可以通过字符扭曲与字符粘连做到。还有一个有效的建议：不要使用普通字符，让验证码的各个部分使用不同比例的缩放或者旋转。

跳出这个思维惯性的圈，我们是不是可以用其他的方法干掉侵略者？Google已经想出了一个很创新的想法。它们想抛弃验证码，使用一个“I AM NOT A ROBOT”的复选框来代替。据说，区分人类和机器之间的微妙差异，在于他/她/它在单击之前移动鼠标的那一瞬间。

但我们没有大公司，更不会研究出这种算法。所以，我们可以在CSS文件中加一些花招，例如翻转图形。真正的用户会看见翻转后的图形，而计算机则只能看见原本的图形。类似这样的方法其实还有很多。

附录：

0x00——干扰线去除算法：

这个算法有一个要求，就是验证码的干扰线与主体的颜色不同。

给出思路，代码很容易实现。统计每种颜色出现的最左上的地方、最右下的地方。如果这两个坐标的差值大于某个阀值，就把这种颜色去除。

0x01——字模比对算法（编辑距离）：

  def editpath(s1,s2): m, n = len(s1), len(s2) colsize, v1, v2 = m + 1, [], [] for i in range((n + 1)):  v1.append(i)  v2.append(i) for i in range(m + 1)[1:m + 1]:  for j in range(n + 1)[1:n + 1]:   cost = 0   if s1[i - 1] == s2[j - 1]:    cost = 0   else:    cost = 1   minValue = v1[j] + 1   if minValue > v2[j - 1] + 1:    minValue = v2[j - 1] + 1   if minValue > v1[j - 1] + cost:    minValue = v1[j - 1] + cost   v2[j] = minValue  for j in range(n + 1):   v1[j] = v2[j] return v2[n]

这就是一个经典的编辑距离算法，时间复杂度为O(len(str1)*len(str2))，在大常数的python下跑算法，实在很慢。考虑到我们并不是严格地计算编辑距离是几，只是在一些字模中取出最值罢了、所以可以加一个优化：

     while (data[k1]==(vchash[i])[k1])and(k1<len(data)-1):             k1+=1;         while (data[k2]==(vchash[i])[k2])and(k2>0):             k2-=1;         if k1-k2>=0:             return i          tmps=editpath((vchash[i])[k1:k2],data[k1:k2])

代码中的tmps可以与min进行比对。经测试，这种优化可以减少时间至原来的1/6甚至更少！

正文到此结束