2008年4月17日 星期四

ASIRRA

有使用過網頁郵件或是一些網路討論區的人都會知道,有一種叫 CAPTCHA 的東西。CAPTCHA 是利用把隨機產生的文字經過一些扭曲、加上雜訊等動作之後的圖片,讓使用者去進行判讀,主要目的是要避免那種自動化的程式大量申請網頁郵件帳號或網路討論區帳號,再利用這些帳號來散播廣告信件。

很明顯的 CAPTCHA 的有效性,是基於「人類可以判讀」而「電腦不容易判讀」的假設之上。但是,現在電腦判讀 CAPTCHA 的能力愈來愈強,而且有些 CAPTCHA 已經混亂到人都不太容易看得清楚了。因此,這已經是一個相當嚴重的問題。最近的一些報導中顯示,包括 Gmail 和 Hotmail 的 CAPTCHA 系統都已經被有效率的破解,甚至達到平均一分鐘即可自動建立一個帳號的效率。

為了解決這個問題,也有很多人想過不同的方法。一個很明顯的「人類很擅長」而「電腦很不容易做」的工作,是圖片的辨識。其中一個例子是 KittyAuth 系統。KittyAuth 會隨機選出不同的動物的圖片,並要求使用者選出貓咪的圖片。理論上電腦很難判斷一張動物的照片是不是貓咪,所以可以達到分辨人類和電腦的效果。

不過 KittyAuth 和其它類似的系統都有同樣的缺點:他們的圖片資料庫的大小不夠。這使得破解變得容易:電腦不需要真的去判斷哪些照片是貓咪,它只需要「記住」哪些照片是貓咪就好了。如果照片都沒有經過任何更改,可以很容易利用 MD5 等 signature 比對的方式,就可以快速判斷一張照片是否在資料庫中。當然,一個解決方法是把照片進行細微的改動,例如加上一些雜訊。不過即使如此,如果資料庫不大(例如數百張照片),要比對兩張照片是否相似,也不是困難的事情。

為了解決這個問題,Microsoft Research 提出了一個叫 ASIRRA 的系統。基本上 ASIRRA 和 KittyAuth 一樣,也是使用動物的照片,要求使用者選出哪些是貓咪。不過,和 KittyAuth 不同的是,ASIRRA 和 Petfinder.com 合作。Petfinder.com 是一個幫無家可歸的寵物找到新家的服務,他們有數百萬張不同動物的照片。因此,ASIRRA 系統可以解決 KittyAuth 等系統的最大問題,即資料庫大小有限的問題。另外,為了避免電腦程式利用亂猜的方式,ASIRRA 要求使用者選出所有貓咪的圖片,而不是只選出其中一張。例如,12 張照片中,如果有未知數目的貓咪照片,則一個亂猜的程式,正確選出所有貓咪照片的機率,只有 1/4096。

那麼 Petfinder.com 能得到什麼好處呢?ASIRRA 在每張動物的照片下,增加一個 "Adopt Me" 的連結,讓有興趣的使用者,可以選擇領養照片中的動物。這同時也讓 Petfinder.com 可以大量增加其動物照片的曝光率。

目前 Microsoft Research 提供 ASIRRA 供大眾進行 beta 測試。不過這樣的系統倒底是不是真的有效呢?恐怕也很難說,畢竟理論上數百萬張照片,仍有機會透過人工方式進行分辨(畢竟這些照片一開始也是以人工方式進行分辨的)。想要破解 ASIRRA 的人,可以儘可能收集到足夠多的照片資料,以人工進行分辨後,即使沒辦法達到 100% 成功率,但若有 80% 成功率,也可以大幅提高猜對的機率(12 張照片若有 80% 猜對機率,則完全正確選中的機率會提高到 1/15)。

另一種可能的方式,是透過圖片合成。最簡單的方法,是把大量動物的照片,經過去背處理,再隨機以不同的大小,甚至不同的角度,貼在隨機的背景上(例如類似草皮的圖案)。然後,再要求使用者點選在貓咪上。為了降低亂猜的成功率,可以要求使用者需連續答對一定的次數。這樣一來,即使想要破解的人,已經取得完整經過去背處理的照片資料庫,要比對出貓咪的位置,仍會需要費一番功夫。另一種方法則是利用 3D 繪圖技術,從隨機的角度繪製不同的 3D 物品,同樣是貼在隨機的背景上,再要求使用者選出指定的物品。不過,這樣做的話,伺服器的負擔可能會變得很重。

1 則留言:

猪头没有头 提到...

我是Google Stencil Buffer关键词找到你好久未更新hotball的小屋,我是个入门级的3D图形编程爱好者,不知道能不能+我MSN呢,因为我常常看书看到囧..无处讨论..

我的MSN:yara_1120 at hotmail.com