Captcha Karakterlerinin Yapay Sinir Ağları Kullanılarak
Tanınması
Süleyman Eken, Ahmet Sayar
Bilgisayar Mühendisliği
Kocaeli Üniversitesi
Umuttepe Kampüsü,41380, Kocaeli-Türkiye
{suleyman.eken, [email protected]
Öz–CAPTCHA (İnsan ve Bilgisayar Ayrımı Amaçlı Tam
Otomatik Genel Turing Testi), insan ile bilgisayar davranışlarını
sınama-yanıt doğrulaması şeklinde ayırt etmek amacıyla
geliştirilen bir güvenlik önlemidir. Üyelik formlarından, e-posta
servislerine; çevrimiçi anketlerden, multimedya barından
sitelerden çok büyük miktarda içerik indirilmesini engellemeye
kadar birçok kullanım alanı vardır. Matematiksel bir sorunun
cevaplamasını veya resimler arasından mantıksal bazı kriterlerle
seçim yapılmasını isteyen CAPTCHA türleri olmasına rağmen en
yaygın olarak kullanılanı deforme edilmiş resim şeklinde
karakterlerden oluşanıdır. Bu makalede, görüntü işleme
tekniklerini ve yapay sinir ağlarını (YSA) beraber kullanarak
CAPCHA karakterlerini tanıyan bir sistem önermekteyiz.
Önerilen sistemin etkinliği farklı CAPCHA türleri için test
edilmiştir.
Anahtar Kelimeler – Captcha tanıma, görsel Captcha, görüntü
momentleri, güvenlik, Levenberg-Marquardt geri yayılım
I. GİRİŞ
Modern hesaplamanın babası olarak kabul edilen Alan
Turing (1912-1954) tarafından 1950 senesinde makinelerin
insanlar gibi düşünebilip düşünemediğini veya düşünebilir
gibi göründüğünü anlayabilmek için bir test önerdi [1]. Turing
testi olarak bilinen bu sınama sisteminde, sorgulayıcı
katılımcıları (insan ve bilgisayar) görmediği ve duymadığı
halde onlara yönelttiği sorulara aldığı cevaplardan hangisinin
makine/bilgisayar olduğunu anlayamıyorsa ilgili makine bu
testi geçmiştir [2]. Ters Turing testi olarak bilinen sistemlerde
de aynı aktörler (insan ve bilgisayar) olmasına rağmen
insanların makinelerden ayrılması hedeflenmiştir. Turing
testinde sorgulayıcı da bir insan olmasına rağmen, Ters Turing
testinde ise sorgulayıcı bir makinedir. Ters Turing testini
uygulayan sistemler HIPs (İnsan Etkileşimli Kanıtlar) veya
CAPTCHAs (İnsan ve Bilgisayar Ayrımı Amaçlı Tam
Otomatik Genel Turing Testi) [3] olarak isimlendirilirler.
Çoğu firma servislerini otomatik skript saldırılarına karşı
korumak için bu sistemleri kullanır. Bu servislere örnek olarak
mail, çevrimiçi kayıt, bilet/etkinlik rezervasyonları, çevrimiçi
oylamalar, chat odaları ve web günlükleri verilebilir. Efektif
olması açısından CAPTCA’ler, bunları kırmak isteyen botlara
(otomatik yazılım programları) göre yeterince caydırıcı; fakat
servis kullanıcıları tarafından da kolayca anlaşılabilir ve
çözülebilir olmalıdır.
CAPTCHA’ler genellikle desenli arka plana sahip resmin
içinde harf ve sayıların döndürülmesi, eğilmesi şeklinde
görülürler. Bu harf ve sayılar bazen bir kitap yazısı gibi
okunabilmekte bazen de kullanıcıların sinirini bozacak
derecede okunamaz olabilmektedir. Birçok CAPTCHA türü
olmasına rağmen en çok görüleni resim içerisine yerleştirilen
karakterler şeklindedir. Var olan diğer türlere örnek olarak;
“iki üç daha kaç eder?” gibi matematiksel bir problemin
sonucunu soran, “ateş sıcak mı, soğuk mu?” gibi basit
sorulardan oluşan, birkaç resim içerisinden istenen resmin
bulunmasını isteyen veya resimdeki bir noktaya tıklanmasını
isteyen türler verilebilir. Ekran okuyan programları kullanarak
webde gezinen görme engelli kullanıcılar için de işitsel
CAPCHA’ler mevcuttur [4].
Yüksek çözünürlüklü karakterlerin tanınması problemi
(Optik karakter tanıma - OCR) yaklaşık 20 sene önce çözüldü.
Diğer taraftan el yazısının tanınması konusunda hala
literatürde boşluklar vardır. Karışık arka plana sahip
CAPTCHA’lerdeki karakterlerin tanınması işlemi de el
yazısının tanınmasına benzemektedir. Biz de bu makalede,
farklı kaynaklardan elde ettiğimiz 4 farklı CAPTCHA türüne
görüntü işleme tekniklerini ve YSA’yı beraber kullanarak
karakterlerinin tanınmasını sağladık.
Makalenin geri kalanı şu şekilde organize edilmiştir: 2.
bölümde karakterlerin tanınması ve bölümleme sırasında
karşılaşılan problemler üzerinde durulmuştur. Sonraki
bölümde, CAPCHA karakterlerinin tanınması ve kırılmasına
yönelik literatürde var olan çalışmalar irdelenmiştir. 4.
bölümde CAPCHA karakterlerinin tanınmasına yönelik
önerdiğimiz sistemin mimarisi ve farklı türler üzerinde
sistemin kullanılabilirliği açıklanmıştır. Son bölümde ise
sonuçlar değerlendirilmiş ve ileride ne gibi çalışmalar
yapılacağından bahsedilmiştir.
II. KARAKTERLERİN BÖLÜMLENMESİ VE TANINMASI
SORUNLARI
Görüntüyü çeşitli öğelere ayırma işlemine bölümleme
(segmentasyon) adı verilir. Tüm otomatik görüntü tanıma
sistemlerinin çok önemli bir parçasıdır. Bölümleme
probleminin çözülmesi karakterlerinin yerlerinin doğru bir
şekilde saptanmasını gerektirmektedir. Karakterlerin yerlerinin
resim içinde rastgele dağıtılmış olması, resmin arka plan
dokusu, ön plan/arka plan ızgara çizgileri ve yay şeklindeki
dağınık çizgiler bölümleme problemini zorlaştırmaktadır.
Şekil 1’de text bazlı değişik CAPTCHA türleri verilmiştir.
(a) MSN/Hotmail CAPTCHA örnekleri
(b) Google CAPTCHA örnekleri
(c) Ticketmaster CAPTCHA örnekleri
Şekil 1 Farklı CAPTCHA türleri
CAPCHA’deki karakterlerin eğri büğrü olması (Şekil 1
b’deki gibi), karmaşık arka plan dokusunun olması ve ön plan
çizgilerinin varlığı (Şekil 1 c) gibi sebepler görüntü
bölümleme ön işlem adımlarının verimliliğini azaltarak
kötüleştirmektedir. Karakterlerin yerleri doğru bir şekilde
tespit edildikten sonra karakterler doğru bir şekilde ancak
tanınabilmektedir. Tanıma işlemi ise; karakterlerin büyüklük
ve rotasyonundaki değişiklikler, yerel ve global eğrilikler,
birbirleriyle rastgele kesişen çizgiler (Şekil 1 a) gibi
nedenlerle zorlaşmaktadır. Bir CAPCHA’nin karakterlerini
tanımanın kolaylığı, bölümleme ve tanıma problemlerinin
güçlüğüne bağlı olarak değişmektedir.
III. İLGİLİ ÇALIŞMALAR
CAPTCHA karakterlerinin herhangi bir yöntemle
kırılmasını/tanınmasını engellemek amacıyla bugünlerde
CAPTCHA tasarımcıları epey uğraşmasına rağmen literatürde
CAPTCHA’lerin kırılmasına yönelik birçok çalışma
mevcuttur. Bunlardan bazıları şunlardır: Yan ve Salah [5],
Microsof’un sadece büyük harfler ve rakamlardan oluşan sekiz
karakterli MSN CAPTCHA’lerini (Şekil 1 a) %60 oranında
kırmayı başarmışlardır. Bu işlemi ikileştirme, kesikli
karakterleri onarma, renk tabanlı bölümleme ve gürültü
kaldırma gibi çeşitli görüntü işleme algoritmaları kullanarak
gerçeklemişlerdir. Aynı yazarlar [6], Captchaservice.org
tarafından üretilen CAPTCHA’leri kırmak için bölümlemeden
sonra her bir karakter için daha önce hesaplanan piksel sayısı
sorgu tablosu (lookup table) kullanmışlardır. İlgili site
tarafından üretilen dört farklı türdeki CAPTCHA’yi sözlük
saldırısı yöntemiyle %92, yılan bölümlemesi (snake
segmentation) ve basit geometrik analiz algoritmaları ile %99
oranında kırmışlardır. Chellapilla ve Simard [7] Google
tarafından kullanılan CAPTCHA’leri (Şekil 1 b) makine
öğrenmesi yaklaşımıyla kırmışlardır. Mori ve Malik [8] Yahoo
tarafından kullanılan EZ-Gimpy CAPTCHA’sini şekil
içeriklerini eşleştirme yöntemiyle %92 oranında yenmişlerdir.
Moy ve arkadaşları [9] ise aynı türdeki CAPTCHA’leri
distorsiyon tahmin teknikleri kullanarak %99 oranında
yenmişlerdir. Chandavale ve arkadaşları text [10] tabanlı
CAPTCHA’leri ilk önce karakterlerine ayrıştıran daha sonra
da karakterlerden elde ettiği özellik vektörlerine göre tanıyan
bir sistem önermişlerdir. Kullandıkları özellik vektörlerini;
karakterdeki boşluk sayısı, karakterin boyu ve beyaz-siyah
piksel geçişlerinin maksimum sayısı içermektedir. Ramya ve
Jayasree [11] karmaşık arka plana sahip, Bot Detect ve Google
CAPTCHA türlerini ön-kısım tabanlı kestirici ve karakteradaptif maskeleme yöntemleri ile kırmaya yönelik bir sistem
önermişlerdir. Jan ve arkadaşları [12] bölümlemeye dayanıklı
tüm CAPTCHA türlerini kırmaya yönelik bir sistem
geliştirmişler ve güçlü bir CAPTCHA’nin nasıl tasarlanacağı
hakkında bilgiler vermişlerdir.
Bursztein ve arkadaşları [13] popüler web sitelerinden
elde ettikleri anti-bölümleme teknikleri ile güçlendirilmiş ve
bozuk karakterlere sahip 15 CAPTCHA türüne sistematik
değerlendirme tekniği uygulamışlar ve bunlardan 13’nün
otomatik saldırılara karşı korunmasız olduğunu saptamışlardır.
Makalenin sonunda da CAPTCHA tasarımcıları için
önerilerde bulunmuşlardır. Chow ve arkadaşları [14] mobil
kullanıcılara yönelik rastgele oluşturulmuş karakter grubu ve
İngilizce kelimeler arasından İngilizce kelimeleri seçtirmek
suretiyle tıklanabilir bir CAPTCHA türü önermişlerdir.
Oluşturdukları türe karşı yapılabilecek sınıflandırma
saldırılarını (İngilizce bir kelime mi değil mi?) ise İngilizce
kelimelerin karakterlerinin ikili (bigram) ve üçlü (trigram) yan
yana olma olasılığını kullanarak oluşturdukları İngilizce
olmayan kelimelerle engellemişlerdir. En ilginç CAPTCHA
türlerinden olan reCAPTCHA [15], kütüphanelerdeki yazılı
metinleri dijital ortama aktarırken ortaya çıkan sayfalardaki
bozulmalar ve basım problemlerini dikkate alarak hem bu
metinlerin dijital ortama aktarılmasını hem de botlar
tarafından taranması oldukça zor bir güvenlik sağlamaktadır.
Bu sistemde, dijital ortama aktarılırken okunamamış bir
kelime ve düzgün okunmuş iki kelime çifti kullanıcıya
sunulmaktadır. Kontrol için okunmuş kelime kullanılırken
diğeri için verilen cevap da metinlerin bilgisayara aktarılması
işini gerçeklemiş oluyor. Jan ve arkadaşları [12]; Facebook ve
Twitter gibi milyonlarca kullanıcıya sahip sosyal ağlarda
kullanılan
reCAPTCHA’yi
%33
oranında
kırmayı
başarmışlardır.
IV. CAPCHA KARAKTERLERİNİ TANIYAN SİSTEMİN
MİMARİSİ
Dört farklı türdeki CAPTCHA’nin karakterlerini tanıyan
sistemin (Şekil 2’ye bakınız) temel bileşenleri şu şekildedir:
(i) diğer aşamaların işini kolaylaştırmaya yönelik ön işlemler,
(ii) karakterlerin dikey bölümleme yöntemiyle elde edilmesi,
(iii) elde edilen her bir karakter için özellik vektörünün
oluşturulması ve (iv) YSA kullanılarak bu özellik vektörlerine
göre tanıma işleminin gerçeklenmesi. Her bir aşama takip
eden alt bölümlerde detaylandırılmıştır.
Özellik Vektörü Çıkarma
HAM CAPTCHA
GÖRÜNTÜSÜ
ÖN İŞLEMLER
DİKEY
BÖLÜMLEME
ÖZELLİK
VEKTÖRÜ
ÇIKARMA
[1, 12, 7, 6, 9, 10]
İncelenen CAPTCHA görüntüleri; a-z (küçük harfleri), AZ (büyük harfleri) ve 0-9 arası rakamları içerebilmektedir. Bu
karakterlerin tanınması için özellik vektörleri oluşturulmuştur.
Özellik vektöründe; değişmez momentler, çevre uzunluğu,
görüntü oranı ve Euler sayısı gibi her karakteri ayırt etmeye
yarayacak değerler vardır.
1960’ların başında Hu, matematiksel moment teorisinden
yedi değişmez moment geliştirmiştir [17]. Bu yedi moment,
ölçeklendirme, döndürme ve dönüşüm gibi işlemlere karşı
bağımsız çalışmakta ve karakter tanıma gibi örüntü tanıma
problemlerinde fark edilebilir bir başarı artışı sağlamaktadır.
İki boyutlu (p+q) dereceli ve f(x,y) dağılımlı bir görüntü için
moment şöyle tanımlanmaktadır:
mpq
YSA İLE
KARAKTER
TANIMA
∬ xp yq f(x,y)
burada p,q
0, 1, 2,……değerlerini alabilir. Merkez
momentleri aşağıdaki gibi ifade edilir;
∬
Şekil 2 CAPTCHA karakterlerini tanıyan sistemin mimarisi
(1)
-̅
-̅
-̅
-̅
(2)
burada;
Ön işlemler
İlk olarak ham CAPTCHA görüntüsü gri seviyeye
çevrilmiştir. Daha sonra karakterleri (ön plan) arka plandan
ayırmak için gri seviye görüntü, ikili görüntüye çevrilir.
Eşikleme işleminde, görüntünün özelliklerinin bölgeden
bölgeye değişebileceğini dolayısıyla görüntünün her bir
bölgesinde farklı bir eşik değerini kullanılması gereksinimi,
piksellerin yerleşimi ve aralarındaki ilişkilerin hesaba
katılması gerekmektedir. Uygulamamızda eşikleme için
piksellerin gri seviye değerlerinin tüm imgedeki dağılımlarının
yanı sıra yerel özelliklerini de göz önüne alan Otsu eşikleme
yöntemi kullanılmıştır [16].
CAPTCHA görüntülerinde bazen yatay ve dikey çizgiler
olabilmektedir. Bu çizgilerin kaldırılması karakterlerin
tanınması açısından önemlidir. Bunun için görüntünün her
satır ve sütunundaki siyah piksellerin sayısına bakılır. Bu
piksellerin toplam değeri, satır ve sütun uzunluğunun %75’i
kadar ise bu pikseller kaldırılır (rengi arka plan rengine
döndürülür). Son olarak gürültüleri gidermek için medyan
filtre kullanılmıştır.
Dikey Bölümleme
Tanıma işlemini zorlaştıracak gürültü ve çizgilerden
arındırılan
görüntü
bu
adımda
karakterlerine
ayrıştırılmaktadır. Görüntünün sütunlar boyunca dikey
izdüşümü histogramı çıkarılır. Bu histogramın minimum
olduğu yerlerden görüntü bölümlenir (Şeklil 2’nin dikey
bölümleme kısmına bakınz). Bu işlemden sonra artık her bir
karakter birbirinden bağımsız olarak elde edilmiş olur. Daha
sonra her bir karakter 40x60’lık boyutta normalize edilir.
ve ̅
̅
(3)
olarak tanımlanır. m00 ikili görüntünün alanını
vermektedir. Merkez momentleri, dönüşüm altında
değişmezlerdir. Bazen momentlerin boyutlara bağlı olarak
normalizasyonu istenebilir. Bu işlem μ00 moment değeri ile
gerçekleştirilebilir. Böylece normalize merkez momenti
Eşitlik 4 ile hesaplanır:
μ
pq
pq
(p+q)
1+
μ00 2
(4)
Hu, normalize merkez momentlerini kullanarak yedi adet
değişmez moment geliştirmiştir. Özellik vektöründe Hu’nun
geliştirdiği yedi moment kullanılmıştır.
Kullanılan diğer özellikleri şu şekilde özetlenebilir: Çevre
uzunluğu, bir karakteri çevreleyen piksellerin adedini
vermektedir. Eşitlik 5’te verildiği gibi görüntü oranı,
karakterin yer aldığı maksimum ve minimum satır ve sütunun
bulunması ile hesaplanmaktadır.
cmax - cmin +1
rmax - rmin +1
(5)
Euler sayısı ise karakter sayısının karakterdeki boşluk
sayısından çıkarılması ile elde edilir. Q karakteri için bu sayı 0
iken, 8 karakteri için -1’dir. Ön işlemlerden geçirilen
görüntüler kendilerini karakterize edecek özellik vektörlerinin
hesaplanmasından sonra YSA sınıflandırıcısının girişlerine
verilmiştir.
YSA ile Karakter Tanıma
KAYNAKLAR
Karakter tanıma işlemi veya genel olarak karakterlerin
sınıflandırılması işlemi klasik veya akıllı olarak
yapılabilmektedir. Klasik metotlar daha çok Bayes karar
teorisi temellidir. Bu yöntemleri (en yakın komşu, maksimum
olabilirlik, ikili ağaç sınıflandırıcıları, hiyerarşik kümeleme
analizi, Gauss modelleri, vb.) kullanmamızın nedeni
sınıflandırılacak her sınıf için hata kriterini dikkate
almamalarıdır [18]. Akıllı sınıflandırma yapıları ise genellikle
YSA tabanlıdır. Çalışmamızda kullanılan sinir ağı yapısı ve
parametreleri Tablo 1’de verilmiştir. Ağ, her bir karakter için
farklı büyüklükte ve açılarda hazırlanmış 20’şer adet eğitim
verisi seti ile Levenberg-Marquardt hata geri yayılım
algoritması kullanılarak eğitilmiştir.
TABLO 1 KULLANILAN YSA MODELİ
Yapay Sinir Ağı Yapısı
Çok Katmanlı İleri
Beslemeli
Katman sayısı
3
10-6-62
Katmanlardaki hücre sayısı
Başlangıç ağırlıkları ve eşik Rasgele
değerler
Etkinleştirme fonksiyonu
Sigmoid
YSA Eğitim Parametreleri
Öğrenme Kuralı
Levenberg-Marquardt hata
geri yayılım
Hedeflenen toplam karesel
10-7
hata
YSA modeli
Test edilen CAPTCHA’ler Paypal, SGK ve
http://www.thisisbusiness.info/ sitelerinden temin edilmiştir.
Önerilen yöntemin ara aşamalı çıktıları ve başarı oranları
Tablo 2’de verilmiştir.
TABLO 2 CAPTCHA TÜRLERİNE GÖRE BAŞARI ORANLARI
Captcha Türleri
http://www.thisisbusiness.info/
Paypal
Tanıma
Oranı
%86
%89.48
SGK (karışık)
%96.6
SGK (Sayısal)
%100
V. SONUÇLAR VE GELECEK ÇALIŞMALAR
CAPTCHA karakterleri; karmaşık arka plana sahip olma
ve karakterlerin düzensiz dağılımı gibi çeşitli nedenlerden
dolayı OCR programları tarafından çözülememektedir.
Önerdiğimiz yöntem farklı türdeki CAPTCHA’leri başarılı bir
şekilde kırmıştır. Ayrıca gerçekleştirilen sistem kullanılarak
bazı sitelerin güvenliği artırılabilir. İleriki çalışmalarımızda,
daha karmaşık türdeki CAPTCHA’leri kırmayı ve daha
güvenilir bir CAPTCHA tasarlamanın yöntemlerini anlatmayı
planlamaktayız.
[1] Turing, A.M. “Computing machinery and intelligence. Mind”, Mind,
59:433-460, 1950.
[2] Nabiyev V.V., Yapay Zeka: Problemler, Yöntemler, Algoritmalar, Seçkin
Yayıncılık, 83-86, 2005.
[3] Von Ahn L., Blum M., Langford J., “Telling Humans and Computers
Apart Automatically”, Communications of the ACM, 47(2):57-60, 2004.
[4] Schlaikjer A., “A Dual-Use Speech CAPTCHA: Aiding Visually
Impaired Web Users while Providing Transcriptions of Audio Streams,”
Technical Report CMU-LTI-07-014, Carnegie Mellon University, 2007.
[5] Yan J., Salah A.S.E., “Usability of captchas or usability issues in captcha
design”, Symposium On Usable Privacy and Security (SOUPS’08), 4452, USA, Temmuz 2008.
[6] Yan J., Salah A.S.E., “Breaking visual captchas with nave pattern
recognition algorithms”, 23. Annual Computer Security Applications
Conference, (ACSAC’07), 279-291, USA, Aralık 2007.
[7] Chellapilla K., Simard P., “Using machine learning to break visual human
interaction proofs (hips)”, Advancesin Neural Information Processing
Systems 17, Neural Information Processing Systems (NIPS), 265- 272,
2004.
[8] Mori G., Malik J., “Recognizing objects in adversarial clutter: Breaking a
visual captcha”, Conference on Computer Vision and Pattern Recognition
(CVPR’03), 1:134-141, Haziran 2003.
[9] Moy G., Jones N., Harkless C, Potter R., “Distortion Estimation
Techniques in Solving Visual CAPTCHAs”, Proceedings of the 2004
IEEE Computer Society Conference on Computer Vision and Pattern
Recognition (CVPR’04), 2:23-28, 2004.
[10]Chandavale A.A., Sapkal A.M., Jalnekar R.M., “Algorithm To Break
Visual CAPTCHA”, Second International Conference on Emerging
Trends in Engineering and Technology (ICETET’09), 258-262, 2009.
[11] Ramya T., Jayasree M., “Captcha Recognition and Robustness
Measurement using Image Processing Techniques”, IOSR Journal of
Computer Engineering (IOSR-JCE), 13(1):67-72, 2013.
[12]Technical Report, Yan J., Salah A.S.E., Tayara M., “The Robustness of
Google CAPTCHAs”, Newcastle University, UK, 2011.
[13]Bursztein E., Martin M., Mitchell J.C., “Text-based CAPTCHA Strengths
and Weaknesses”, ACM Computer and Communication security 2011
(CSS’11), 2011.
[14]Chow R., Golle P., Jakobsson M., Wang L., Wang X., “Making captchas
clickable”, Proceedings of the 9th workshop on Mobile computing
systems and applications (HotMobile’08), 91-94, New York, NY, USA,
2008.
[15]von Ahn L., Maurer B., McMillen C., Abraham D., Blum M. “recaptcha:
Human-based character recognition via web security measures”, Science
Express, 321(5895): 1465-1468, 2008.
[16]Otsu N., “A threshold selection method from gray level histograms”,
IEEE Transactions on Systems, Man, and Cybernetics, 9(1):62-66, 1979.
[17]Hu M.K., “Visual Pattern Recognition by Moment Invariants”, IRE
Trans.,Inf., Theor., IT-8:179-187, February 1962.
[18]Lévy Mangin J-P., Moriano J.A., Bourgault N., “Modeling Comparisons
for some Classification Methods, Bayesian, Neural and Traditional
Cluster Techniques”, CIENCIA ergo sum, 17(2):127-135, 2010.
Download

IEEE Conference Paper Template