基于馬賽克圖形的人機識別系統的設計與分析

摘要:機器人可以不斷地訪問網站資源，從而消耗資源，產生拒絕服務攻擊。為了解決這個問題，Basso等人提出了一個基于馬賽克的人機交互證明算法，該算法雖然能在一定程度上阻止拒絕服務攻擊，但是它也存在不足:合成的圖片里總有一張真的圖片是完全沒有被覆蓋的，并且每次重疊都只是重疊1/4的部分，使得真的圖片的排列非常有規律，就容易泄漏真的圖片的位置。針對這些不足，提出了一種改進的基于馬賽克的人機交互證明算法，來阻止拒絕服務攻擊。

關鍵詞:拒絕服務攻擊;馬賽克;人機交互證明;機器人;信息安全

中圖分類號:TP309文獻標識碼:A文章編號:1009-3044(2010)05-1171-03

Design and Analysis of Mosaic-based Human Interactive Recognition System

ZHAI Shuo， GAO Cai-yun

(College of Computer Science， China University of Mine and Technology， Xuzhou 221116， China)

Abstract: Robots can continue to access the web site resources to consume resources， resulting in denial of service attacks. In order to solve the problem， Basso et al presents a mosaic-based human-computer interaction proven algorithm， it can prevent the denial of service attacks at some degree， but it also have weakness: one of the real pictures is not covered in the Synthetic picture， and each overlap is just only 1/4 part， which makes really pictures with a very regular， and leak the location of really pictures. This article utilizes these deficiencies to propose an improved mosaic-based human-computer interaction proven algorithm， thus prevents denial of service attacks.

Key words: denial of service attacks; mosaic; human-computer interaction proven; robots; information security

信息安全包括機密性、完整性、可用性、不可否認性等幾個方面的基本屬性。拒絕服務(denial of service，簡稱DOS)攻擊是一種破壞可用性的攻擊行為，它主要通過發送過量的數據包請求，消耗網絡帶寬或系統資源，使網絡或系統服務負載過重，導致服務質量下降，甚至癱瘓或停止。DoS攻擊易于實施、難以防范，目前已經成為信息安全領域的研究熱點之一。

1 相關知識

1.1 人機交互證明

CAPTCHA(Completely Automated Public Turing Test to Tell Computers and Humans Apart) 是指全自動區分計算機和人類的圖靈測試，也被稱為自動圖靈測試[1]。它不同于傳統的圖靈測試[2]，而是由計算機來區分使用者是人還是機器。

一個典型的CAPTCHA必須具備下列屬性:

1)對于人類用戶，應該是快而容易的;

2)應該接受所有的人類用戶，沒有任何歧視;

3)幾乎沒有機器人可以解決這個問題;

4)即使知道算法及數據，也可以抵制攻擊。

CAPTCHA可被分為:文字識別，圖像識別和語音識別[3]。

基于文本測試的CAPTCHA利用計算機程序無法識別嵌入在圖片里面的極其歪曲和損壞的文本內容。這些圖片對于人類通常是易于閱讀，但其對于自動程序來說通常是難以辨認，即使是使用最好的光學字符識別軟件[4]。基于文本的CAPTCHA必須抵抗“部分比承認”攻擊[5]。

基于圖像測試的CAPTCHA要求用戶解決視覺模式識別問題或理解圖片所表達的概念。由于顯示圖像需要較高的困難和較大的區域，導致服務器負擔加重。此外，建立一個大的數據庫也可能存在問題，比如與特定主題的網站不相符。

基于音頻測試的CAPTCHA側重于機器很難理解存在扭曲、退化和背景噪聲的口語[6]，容易受外界干擾，降低語音的識別度。

1.2 基于馬賽克圖形的人機識別算法設計及分析

隨著計算機視覺和模式識別的進步，這種基于文本的CAPTCHA已經沒有原來那么有效，更容易受到特定的攻擊。目前，計算機還不能完成很多與視覺相關的任務，而這些任務對于人類來說是容易的，可以利用這一點來設計一種方法來區別人類和機器人。

Alessandro Basso和Stefano Sicco提出了一種算法，被命名為\"MosaHIP\" 是Mosaic-based Human Interactive Proof(基于馬賽克的人機互動證明)[7]，它利用了現有的計算機在執行中的一些困難:

1)在復雜背景下的，在感興趣的區域中的圖像分割;

2)在背景混亂情況下的特定概念的識別;

3)特定轉化被應用到圖像后的圖形匹配。

\"MosaHIP\"是基于將圖像進行拼湊、鑲嵌，使用一個由許多小的，部分重疊的圖像來組成大的圖像的想法。這些小的圖像來自兩個不同的類別:

1)描述真的，有意義概念的圖像;

2)描述人工的或沒有意義概念的圖像。

只有很少的一部分圖像是真的，屬于第一類，它們需要被用戶識別，它們偽隨機的放置在拼湊的圖像中，并且彼此是重疊的，這樣，對于計算機來說，識別它們不是容易的事情。剩下的假的圖像是由真的圖像的顏色直方圖中的隨機的顏色產生的圖形、線等，它們被用來產生混亂的背景，目的是為了使機器人識別真的圖像困難。

圖1顯示的是基于概念的MosaHIP，要求用戶識別被拼湊的圖像中包括的真的圖像。圖2顯示的是“最上層”的MosaHIP，要求用戶識別描述“一些存在” 意義的和“放置在最上層”的，不被其他圖像覆蓋的圖像。

圖1 基于概念:要點擊“菠蘿”圖2 “最上層的”:要點擊“剪刀”

Alessandro Basso和Stefano Sicco提出的算法雖然可以在一定程度上區分機器人和人類，但還是存在一些缺陷:

首先在算法描述中就存在錯誤，在第四步中，確定圖像Ij-1所在的區域，將Ij-1分為4個相同面積的區域，隨機的選擇一個區域，并放置Ij在這個區域中，與Ij-1重疊，這就存在1/4的幾率會完全的覆蓋圖片Ij-1。

另外，該算法在安全方面也存在著一定得缺陷:1)無論是基于概念的還是“最上層”的MosaHIP，都有一張完全沒有被覆蓋的真的圖片暴露;2)每放置一張新的真的圖片，它就會覆蓋上一張圖片的1/4區域，無論真的圖片的順序是什么，位置是什么，這些真的圖片所在的區域的圖片位置是有規律可循的，這就使機器人識別圖片變得容易。

2 一個改進的基于馬賽克圖形的人機識別算法

對Alessandro Basso和Stefano Sicco提出的算法的改進方案:

1)在圖像數據庫P中選擇n個圖像，將它們添加到真的圖像集合R={I1， ... ， In}中;如果是基于概念的方法，隨機的選擇圖像Ir∈R，確定它的種別Gr，否則Ir:= In。

2)對于每一個Ij ∈R，

隨機的選擇縮放比例因數Sj，SMIN ≤ Sj ≤ SMAX，根據Sj對Ij使用縮放比例函數;確定Ij是否需要旋轉，隨機的選擇旋轉角度⊙j， ⊙MIN ≤ ⊙j ≤ ⊙MAX，根據⊙j旋轉Ij;確定Ij的透明度，隨機的選擇透明度因數Tj，0 ≤Tj ≤ TMAX，如果Tj:!=0，根據Tj對Ij使用透明度函數;

3)制作長m寬n的透明的圖像c;

在c上隨機的選擇一個位置，將I1 ∈R放置在這個位置上，確保I1沒有超過c的邊界;如果I1=Ir，在集合D中保存I1的左上和右下的坐標;

4)對于每一個Ij ∈R，2 ≤ j ≤ n;

確定圖像Ij-1所在的區域，將Ij-1分為4個相同面積的區域，隨機的選擇一個區域，并按這個區域的方向，在這個區域中隨機的選擇一個新的區域，這個新的區域的面積≥原來區域的3/5，并放置Ij在這個新的區域中，與Ij-1重疊，并保證它不覆蓋Ij-2;如果是基于概念的方法Ij不能重疊預先放置的Ik， 1≤ k ≤ j;如果Ij=Ir，在集合D中保存Ij的左上和右下的坐標;

5)計算圖像c的顏色直方圖，hist(c);

制作長m寬n的背景圖像b;在集合RGBh和RGBl中隨機的選擇顏色形成一個顏色梯度來填充b，RGBh中包括hist(c)中最常出現的k種顏色，RGBl包括剩下的顏色;

6)制作一個與真的圖像面積相似的假的圖像f，在集合RGBh和RGBl中隨機的選擇顏色形成一個顏色梯度來填充f;在f中用RGBh中的顏色畫各種各樣的圖形和線;用RGBl中的顏色改變f中一些區域的像素顏色;如果是基于概念的方法，將I1分為4個相同面積的區域，隨機的選擇一個區域，并放置f在這個區域中，與I1重疊，并保證圖片f不完全的覆蓋圖片I1，如果是“最上層”的方法，將In分為4個相同面積的區域，隨機的選擇一個區域，并放置f在這個區域中，與In重疊，并保證圖片f不完全的覆蓋圖片In;

7)繼續制作圖片f，將f添加到背景圖像b，從左上角開始;重復步驟7，直到b被假的圖像完全覆蓋;

8)使用Floyd-Steinberg抖動算法減少圖像b顏色的數量;

9)重疊合成的圖像c到背景圖像b，因為c擁有透明的背景，現在b包含了真的和假的圖像;

10)對b使用變形函數(使用不是隨機選擇的輸入參數);

11)返回圖像b和坐標集合D;如果是基于概念的方法，還要返回種別Gr。

該算法在步驟4)和6)進行改進，在4)中，本改進算法使得每一張真的圖片都覆蓋上一張真的圖片的隨機的面積，但又不會干擾人類的識別，在6)中，對于完全沒有沒覆蓋的真的圖片，本改進算法用一張假的圖片來與這張真的圖片重疊，從而提高算法的安全性。

3 結論

本文分析了拒絕服務攻擊的危害和防御方法，描述了人機識別技術的現狀和與人機識別相關的知識—圖靈機和圖靈測試等，在此基礎上，本文介紹了Basso等人的基于馬賽克圖形的人機識別算法，并對該算法進行了分析，發現該算法在描述和安全性方面都存在漏洞和不足，針對這些不足，本文在Basso等人提出的基于馬賽克圖形的人機識別算法的基礎上進行了改進，來提高算法的安全性。

參考文獻:

[1] Ahn L V，Blum M，Langford J.Telling humans and computers apart automatically[M].New York:ACM，2004:56-60.

[2] Turing A M.Computing machinery and intelligence[M].Mind LIX 59，1950:433-460.

[3] Chew M，Tygar J D.Image recognition CAPTCHAs[C].in Proceeding. of the 7th International Information Security Conference (ISC 2004).Springer，2004.

[4] Coates A，Baird H，Fateman R.Pessimal print:A reverse turing test[C].In Proc of the Sixth Intl Conf on Document Analysis and Recognition.Seattle，WA，2001.

[5] Datta A，Li J，Wang J Z.Imagination:a robust image-based captcha generation system[C].In Proceedings of the 13th annual ACM international conference on Multimedia (MULTIMEDIA'05).New York:ACM，2005.

[6] Kochanski G，Lopresti D，Shih C.A reverse turing test using speech[C].In Proceedings of the International Conferences on Spoken Language Processing Denver.Colorado，2002.

[7] Alessandro Basso，Stefano Sicco.Preventing massive automated access to Web resources[J].Computers Security，2008.