机器人可以不断地访问网站资源，从而消耗资源，产生拒绝服务攻击。为了解决这个问题，Basso等人提出了一个基于马赛克的人机交互证明算法．该算法虽然能在一定程度上阻止拒绝服务攻击，但是它也存在不足：合成的蹈片里总有一张真的图片是完全没有被覆盖的，并且每次重叠都只是重叠1／4的部分。使得真的图片的排列非常有规律，就容易泄漏真的图片的位置．针对这些不足，提出了一种改进的基于马赛克的人机交互证明算法，来阻止拒绝服务攻击。

　　信息安全包括机密性、完整性、可用性、不可否认性等几个方面的基本属性。拒绝服务(denialofSelW‘1oe，简称DOS)攻击是一种破坏可用性的攻击行为，它主要通过发送过量的数据包请求，消耗网络带宽或系统资源，使网络或系统服务负载过重，导致服务质量下降，甚至瘫痪或停止。DoS攻击易于实施、难以防范，目前已经成为信息安全领域的研究热点之一。

　　l相关知识．

　　1．1人机交互证明

　　CAPTCHA fCompletelyAutomatedPublicTuringTesttoTellComputersandHumansApart1是指全自动区分计算机和人类的图灵测试，也被称为自动图灵测试l】1。它不同于传统的图灵测试，而是由计算机来区分使用者是人还是机器。

　　一个典型的CAP1℃HA必须具备下列属性：．

　　1)对于人类用户，应该是快而容易的：

　　2)应该接受所有的人类用户，没有任何歧视；

　　3)几乎没有机器人可以解决这个问题；

　　4)即使知道算法及数据，也可以抵制攻击。

　　CAPTCHA可被分为：文字识别，图像识别和语音识别。

　　基于文本测试的CA CHA利用计算机程序无法识别嵌入在图片里面的极其歪曲和损坏的文本内容。这些图片对于人类通常是易于阅读，但其对于自动程序来说通常是难以辨认，即使是使用最好的光学字符识别软件基于文本的CAPTCHA必须抵抗“部分比承认”攻击I。
　基于图像测试的CAPTCHA要求用户解决视觉模式识别问题或理解图片所表达的概念。由于显示图像需要较高的困难和较大的区域，导致服务器负担加重。此外，建立一个大的数据库也可能存在问题，比如与特定主题的网站不相符。

　　基于音频测试的CAPTCHA侧重于机器很难理解存在扭曲、退化和背景噪声的口语[61，容易受外界干扰，降低语音的识别度。

　　1．2基于马赛克图形的人机识别算法设计及分析

　　随着计算机视觉和模式识别的进步，这种基于文本的CAPTCHA已经没有原来那么有效，更容易受到特定的攻击。目前，计算机还不能完成很多与视觉相关的任务，而这些任务对于人类来说是容易的，可以利用这一点来设计一种方法来区别人类和机器人。

　　AlessandroBasso和StefanoSieeo提出了一种算法，被命名为”MosaHIP”是Mosaic—basedttumanInteractiveProof(基于马赛克的人机互动证明)17]，它利用了现有的计算机在执行中的一些困难：1)在复杂背景下的，在感兴趣的区域中的图像分割：

　　2)在背景混乱情况下的特定概念的识别：

　　3)特定转化被应用到图像后的图形匹配。

　　”MosaHIP”是基于将图像进行拼凑、镶嵌，使用一个由许多小的，部分重叠的图像来组成大的图像的想法。这些小的图像来自两不同的类别：

　　1)描述真的，有意义概念的图像：

　　2)描述人工的或没有意义概念的图像。

　　只有很少的一部分图像是真的，属于第一类，它们需要被用户识别，它们伪随机的放置在拼凑的图像中．并且彼此是重叠的，这，对于计算机来说，识别它们不是容易的事情。剩下的假的图像是由真的图像的颜色直方图中的随机的颜色产生的图形、线等，它被用来产生混乱的背景，目的是为了使机器人识别真的图像困难。

　　图1显示的是基于概念的MosaHIP，要求用户识别被拼凑的图像中包括的真的图像。网2显示的是“最上层”的MosaHIP．要求户识别描述“一些存在”意义的和“放置在最上层”的，不被其他图像覆盖的图像。
 

　　AlessandroBasso和StefanoSicco提出的算法虽然可以在一定程度上区分机器人和人类，但还是存在一些缺陷：

　　首先在算法描述中就存在错误，在第四步中，确定图像I_l所在的区域，将I_】分为4个相同面积的区域，随机的选择一个区域，并放置Ij在这个区域中，与Ij一重叠，这就存在1／4的几率会完全的覆盖图片Ii

　　另外，该算法在安全方面也存在着一定得缺陷：1)无论是基于概念的还是“最上层”的MosaHIP，都有一张完全没有被覆盖的真的图片暴露；2)每放置一张新的真的图片，它就会覆盖上一张图片的1，4区域，无论真的图片的顺序是什么，位置是什么，这些真的图片所在的区域的图片位置是有规律可循的，这就使机器人识别图片变得容易

　　2一个改进的基于马赛克图形的人机识别算法

　　对AlessandroBasso和Stefa130Sicco提出的算法的改进方案：1)在图像数据库P中选择n个图像，将它们添加到真的图像集合R={I…．，1中；如果是基于概念的方法，随机的选择图像I∈R，确定它的种别G，否则I：=I。2)对于每一个Ij∈R，随机的选择缩放比例因数Si，S≤Sj≤S，根据Sj对Ij使用缩放比例函数；确定I．是否需要旋转，随机的选择旋转角度0，0≤o≤0，根据0．旋转Ij；确定Ij的透明度，随机的选择透明度因数，0≤T≤TAX，如果T．：!=O，根据对Ij使用透明度函数：

　　3)制作长m宽n的透明的图像c：在e上随机的选择一个位置，将I∈R放置在这个位置上，确保I没有超过c的边界；如果Ii=I，在集合D中保存I，的左上和右下的坐标：

　　4)对于每一个IiER，2≤j≤n；确定图像Ij一所在的区域，将Ij一。分为4个相同面积的区域，随机的选择一个区域，并按这个区域的方向，在这个区域中随机的选择一个新的区域，这个新的区域的面积≥原来区域的3／5，并放置Ij在这个新的区域中，与li一重叠，并保证它不覆盖Ij．，；如果是基于概念的方法Ii不能重叠预先放置的I，1≤k≤j；如果Ii=I，在集合D中保存I的左上和右下的坐标；
 

　5)计算图像c的颜色直方图，hist(c)；制作长m宽n的背景图像b；在集合RGBh和RGBI中随机的选择颜色形成一个颜色梯度来填充b，RGBh中包括his@)中最常出现的k种颜色．RGB1包括剩下的颜色；

　　6)制作一个与真的图像面积相似的假的图像f，在集合RGBh和RGB1中随机的选择颜色形成一个颜色梯度来填充f；在f中用RGBh中的颜色画各种各样的图形和线；用RGB1中的颜色改变f中一些区域的像素颜色；如果是基于概念的方法，将I分为4个相同面积的区域，随机的选择一个区域，并放置f在这个区域中，与I。重叠，并保证图片f不完全的覆盖图片I，如果是“最上层”的方法，将I分为4个相同面积的区域，随机的选择一个区域，并放置f在这个区域中，与I重叠，并保证图片f不完全的覆盖图片I；

　　7)继续制作图片f，将f添加到背景图像b，从左上角开始；重复步骤7，直到b被假的图像完全覆盖；·

　　8)使用Floyd—Steinberg抖动算法减少图像b颜色的数量；

　　9)重叠合成的图像c到背景图像b，因为c拥有透明的背景，现在b包含了真的和假的图像；

　　lO)对b使用变形函数(使用不是随机选择的输入参数)；

　　l1)返回图像b和坐标集合D；如果是基于概念的方法，还要返回种别G。

　　该算法在步骤4)和6)进行改进，在4)中，本改进算法使得每一张真的图片都覆盖上一张真的图片的随机的面积，但又不会干扰人类的识别，在6)中，对于完全没有没覆盖的真的图片，本改进算法用一张假的图片来与这张真的图片重叠，从而提高算法的安全性

　　3结论

　　本文分析了拒绝服务攻击的危害和防御方法，描述了人机识别技术的现状和与人机识别相关的知识一图灵机和图灵测试等，在此基础上，本文介绍了Basso等人的基于马赛克图形的人机识别算法，并对该算法进行了分析，发现该算法在描述和安全性方面都存在漏洞和不足．针对这些不足，本文在Basso等人提出的基于马赛克图形的人机识别算法的基础上进行了改进，来提高算法的安全性。