Wstęp
Graficzne znaki zabezpieczające powszechnie nazywane CAPTCHA stanowią najpopularniejszą metodę w przeciwdziałaniu zautomatyzowanym akcjom wykonywanym przez złośliwe programy (roboty) internetowe. Zaatakowana witryna drastycznie obniża swoją jakość ponieważ staje się ogromnym zbiorem bezsensownych treści lub odnośników, a nierzadko traci zasoby systemowe i staje się niedostępna dla użytkowników.
W swojej pracy badam różne rodzaje zaburzeń znaków, utrudniające rozpoznanie przez maszynę. Przedstawiam ich skuteczność w obronie przed zautomatyzowanym działaniem oraz trudność generacji. Swoje wnioski opieram na podstawie testów przeprowadzonych za pomocą komercyjnych programów służących do rozpoznawania tekstu. Opracowuję także własny program tego typu, wykorzystujący topologiczne cechy obrazu. W odróżnieniu od rozwiązań komercyjnych zaimplementowany program nakierowany jest przede wszystkim na rozpoznawanie graficznych znaków zabezpieczających – CAPTCHA.
W końcu efekty badań służą do stwierdzenia, które metody zaburzeń znaków są najskuteczniejsze. Nie tylko sprawiają, że użycie techniki CAPTCHA jest bardzo efektywną metodą zabezpieczającą przed zautomatyzowanym działaniem, ale także nie powodują problemów z odczytaniem dla użytkowników oraz gwarantują łatwą implementację i szybką generację.
10.12.2008. 16:32
Cel pracy
Celem pracy jest zbadanie różnych rodzajów zaburzeń obrazu wykorzystywanych w graficznych kodach bezpieczeństwa typu CAPTCHA pod kątem skuteczności w zapobieganiu zautomatyzowanym działaniom. Zaburzenia w obrazach uniemożliwiające rozpoznanie znaków przez programy OCR charakteryzują się maksymalną skutecznością. Badania rozpoczynam od stworzenia programu do automatycznego rozpoznawania graficznych kodów bezpieczeństwa i przetestowania go na prostym zestawie znaków. Dodatkowo dla skuteczniejszych CAPTCHA opieram się na komercyjnych programach OCR. Efektem badań jest znalezienie najskuteczniejszych zaburzeń używanych w technice CAPTCHA.
Założenia:- Dane wejściowe są plikiem graficznym
- Dane wyjściowe są rozpoznanym ciągiem znaków
- CAPTCHA są małych rozmiarów (np. 100 x 30 pikseli), dlatego badane obrazy będą wymiarami zbliżone do popularnych wymiarów CAPTCHA
- Zestaw testowy składa się z CAPTCHA wykorzystywanych na popularnych stronach internetowych, przedstawiających różne metody zaburzeń znaków
10.12.2008. 12:38
Definicja
CAPTCHA - (Completely Automated Public Turing Test to Tell Computers and Humans Apart) – jest to rodzaj testu mający na celu ustalenie czy użytkownik jest człowiekiem czy maszyną. Głównie stosuje się go jako zabezpieczenie w formularzach na stronach internetowych. Aby użytkownik mógł wysłać dane, koniecznie musi przepisać treść z obrazka (na przykład kilkuelementowy ciąg losowych znaków lub krótki wyraz). Z założenia ten obrazek z łatwością potrafi odczytać człowiek, a dla maszyny staje się to niemożliwe.10.12.2008. 11:42
Historia
Na początku lat pięćdziesiątych XX wieku Alan Turing zastanawiał się nad problemem odróżnienia ludzi od maszyn udających ludzi. To skłoniło go do opisania metody pozwalającej na rozróżnienie człowieka od maszyny, znanej jako test Turinga.
W 1997 roku Andrei Broder, razem ze swoimi kolegami, zastosował pierwsze prymitywne CAPTCHA na witrynie AltaVista. Miało to zapobiec automatycznemu dodawaniu adresów URL do ich wyszukiwarki internetowej. Aby stworzyć obrazki, które są odporne na oprogramowanie służące do rozpoznawania znaków czyli OCR (Optical Character Recognition), zespół szukał elementów, które powodują błędne rozpoznanie znaków. W 2000 roku Luis von Ahn i Manuel Blum opracowali i opublikowali informacje o CAPTCHA, które zawierały dane o programach potrafiących odróżnić ludzi od maszyn. Stworzyli wiele przykładów CAPTCHA, włączając w to pierwsze, które były szeroko stosowane (na przykład przez portal Yahoo!).
10.12.2008. 10:49
Gdzie jest używana?
Najkrótszą odpowiedzią na to pytanie z pewnością byłoby następujące zdanie: „Wszędzie tam, gdzie zależy nam na obronie przed automatycznymi robotami internetowymi”.
Poniżej przedstawię kilka najpopularniejszych zastosowań CAPTCHA:- portale internetowe – zabezpieczenie przed automatycznym tworzeniem kont e-mail, które to często wykorzystywane są do rozsyłania spamu.
- wyszukiwarki internetowe - zabezpieczenie przed automatycznym dodawaniem adresów URL do wyszukiwarki
- fora internetowe - zabezpieczenie przed automatycznym rejestrowaniem, a co za tym idzie, automatycznym dodawaniem treści
- systemy komentarzy na stronach WWW - zabezpieczenie przed automatycznym dodawaniem komentarzy
- księgi gości - zabezpieczenie przed automatycznym dodawaniem wpisów
- bramki sms - zabezpieczenie przed automatycznym wysyłaniem sms’ów
- strony WWW pozwalające na umieszczanie dowolnych plików – zabezpieczenie przed automatycznym pobieraniem plików
09.12.2008. 16:53
Dlaczego jest używana?
CAPTCHA jest używana za względu na:- uniwersalność – większość ludzi na świecie zna alfabet łaciński i cyfry arabskie, poza tym ogromna część klawiatur komputerowych wyposażona jest w tego typu znaki
- łatwość implementacji – na całość mechanizmu CAPTCHA składa się co najwyżej kilka niewielkich plików PHP
- dość dobrą skuteczność – nawet mało wymyślna CAPTCHA jest wystarczająco skuteczna przed wieloma robotami internetowymi
- szybkość – utworzenie i wyświetlenie obrazka z CAPTCHA odbywa się błyskawicznie szybko i niezauważalnie dla użytkownika
08.12.2008. 16:56
Przed czym chroni?
Umiejętne stosowanie CAPTCHA potrafi ochronić serwis WWW głównie przed zalewem niechcianych treści lub wyczerpaniem zasobów systemowych (na przykład ciągłe i automatyczne ściąganie plików może blokować przepustowość łączy serwerów) a tym samym obniżeniem jego jakości.07.12.2008. 16:58
Dlaczego CAPTCHA jest łamana?
CAPTCHA jest łamana z kilku powodów:- pozycjonowanie strony internetowej w wyszukiwarkach internetowych (zespół czynności mający na celu umieszczenie danej strony wysoko w wynikach wyszukiwania na jakąś frazę) poprzez umieszczanie w komentarzach, wiadomościach na forach internetowych, wpisach w księgach gości odnośników do pozycjonowanej strony
- indeksacja strony internetowej w wyszukiwarkach internetowych (umieszczenie strony internetowej w bazie wyszukiwarki) poprzez umieszczanie w komentarzach, wiadomościach na forach internetowych, wpisach w księgach gości odnośników do indeksowanej strony
- promowanie strony internetowej wśród użytkowników (zwiększenie liczby odwiedzin) poprzez umieszczanie w komentarzach, wiadomościach na forach internetowych, wpisach w księgach gości odnośników do promowanej strony
- dodawanie adresów URL do wyszukiwarki, aby przyspieszyć indeksację (umieszczenie strony internetowej w bazie wyszukiwarki)
- zakładanie kont pocztowych w celu rozsyłania spamu
- wysyłanie krótkich wiadomości tekstowych (sms) zawierających informacje o promowanym produkcie lub adres strony internetowej przez bramki sms
- automatyczne pobieranie plików
06.12.2008. 17:00
Kontrowersje
Stosowanie CAPTCHA budzi spore kontrowersje. Rozwój i skuteczność automatów odczytujących treści z graficznych znaków zabezpieczających, powoduje, że programiści tworzą coraz bardziej wymyślne CAPTCHA. Niestety często zdarza się, że takie zabezpieczenie blokuje nie tylko maszyny, ale także ludzi. Po prostu część liter i cyfr na obrazku jest bardzo nieczytelna, co powoduje pomyłki i frustracje użytkowników, które skutkują opuszczeniem strony WWW. Błędnie wykonana CAPTCHA potrafi zblokować zdrowego człowieka z dobrym wzrokiem. Jednak użytkownicy Internetu to także osoby z wadami wzroku, a nawet niewidome. Jeżeli twórca witryny nie zaimplementował zastępczej metody odróżnienia człowieka od maszyny, wtedy pewne istotne części strony WWW stają się niedostępne dla takich osób.05.12.2008. 18:17
CAPTCHA a rozpoznawanie znaków
Poniżej przedstawiam rodzaje zaburzeń stosowane w technice CAPTCHA. Najważniejszym parametrem jest skuteczność czyli trudność w rozpoznawaniu znaków zniekształconych poszczególnymi zaburzeniami. Do badań nad skutecznością posłużyłem się swoim programem Optico, a także trzema innymi komercyjnymi rozwiązaniami (Readiris Pro, ABBYY FineReader, OmniPage Professional). Ocenę skuteczności uśredniłem spośród otrzymanych wyników i podzieliłem na następujące przedziały:- Bardzo duża – mniej niż 0.1% poprawnie rozpoznanych ciągów znaków
- Duża – od 0.1% do 1% poprawnie rozpoznanych ciągów znaków
- Średnia – od 1% do 5% poprawnie rozpoznanych ciągów znaków
- Mała – od 5% do 10% poprawnie rozpoznanych ciągów znaków
- Bardzo mała – od 10% do 50% poprawnie rozpoznanych ciągów znaków
- Bliska zeru – więcej niż 50% poprawnie rozpoznanych ciągów znaków
Należy zauważyć, że nawet 5% skuteczność w rozpoznaniu całego ciągu znaków jest niezadowalająca. Oznacza to, że co dwudziesta CAPTCHA ulega prawidłowemu rozpoznaniu. Dla człowieka taka wartość byłaby niedopuszczająca jednak maszyna wykonująca jeden proces rozpoznawania znaków w ciągu sekundy mogłaby pomyślnie zaatakować stronę 180 razy w ciągu godziny. Dlatego jedynie rozwiązania pozwalające na blisko stuprocentową skuteczność w ochronie przed automatycznym rozpoznaniem ciągu znaków są naprawdę skuteczne.
Drugim parametrem jest trudność generacji. Jej wartość oparłem o rodzaje użytych algorytmów do transformacji lub generacji znaków.
Te same rodzaje zaburzeń mogą mieć różne implementacje, dlatego ich skuteczność oraz trudność generacji mogą być inne i zawierać się w określonym przedziale.
04.12.2008. 18:20
Rodzaje zaburzeń w CAPTCHA
- Brak zaburzeńNajprostszy model CAPTCHA, który jest najłatwiejszy w implementacji, ale także nie posiada praktycznie żadnych zabezpieczeń. Jedyne zabezpieczenie, to takie, że w ogóle należy użyć programu OCR.
Skuteczność: Bliska zeru.
Trudność generacji: Bardzo mała
- Niestandardowa czcionka
Opiera się jedynie technikom korelacyjnym (porównanie ze wzorcem). Używając metody omnifont można rozpoznać znaki. W zależności o użytej czcionki skuteczność rozpoznawania może się wahać.
Skuteczność: Mała – Średnia
Trudność generacji: Mała - Średnia
- Mała czcionka
Czcionka o niewielkich rozmiarach sprawia, że obraz możemy rozpoznać szybciej, co jest dużym ułatwieniem. Poza tym mała czcionka wyklucza wiele innych zaburzeń takich jak ziarnistość, rozmycie czy mały kontrast.
Skuteczność: Mała
Trudność generacji: Mała
- Znaki na różnych wysokościach
Zwykła segmentacja jest odporna na różnice wysokości poszczególnych znaków.
Skuteczność: Bliska zeru
Trudność generacji: Mała
- Obrót znaków
Czasami obrót znaków może zmniejszać skuteczność wydobycia cech znaków. Jednak przy zastosowaniu współrzędnych lokalnych znaków (wzajemne położenie miejsc szczególnych znaków) zamiast współrzędnych globalnych (położenie miejsc szczególnych znaków względem całego obrazu) obrót znaków nie powoduje trudności w rozpoznawaniu.
Skuteczność: Mała
Trudność generacji: Średnia
- Pochylenie znaków
Wyklucza techniki korelacyjne, ale metoda „omnifont” pozwala na rozpoznanie pochylonych znaków.
Skuteczność: Mała – Średnia
Trudność generacji: Średnia
- Duże odstępy między znakami
Duże odstępy z reguły ułatwiają segmentację. Jednak czasami duży odstęp w połączeniu z różnymi wielkościami czcionek i innymi zaburzeniami może sprawić, że dany znak nie należy do prawidłowo rozpoznanego ciągu.
Skuteczność: Mała
Trudność generacji: Mała
- Małe odstępy między znakami
Prosta i skuteczna metoda. Powoduje duże trudności w segmentacji, wykrywaniu krawędzi i ekstrakcji cech znaków. Dla przeciętnego człowieka nie sprawia trudności w odczytaniu znaków.
Skuteczność: Duża
Trudność generacji: Mała - Średnia
- Niesłownikowe wyrazy
Słownikowe wyrazy ułatwiają rozpoznanie tekstu książki czy gazety, jednak w przypadku CAPTCHA nie używa się słowników, tym bardziej, że użytkownikom nie znającym danego języka wcale to nie pomaga.
Skuteczność: Bliska zeru
Trudność generacji: Bardzo mała
- Podział znaków na kilka wyrazów
Po zaimplementowaniu prostych algorytmów odróżniających odległości znaków i całych słów, rozpoznanie nie stanowi problemu.
Skuteczność: Mała
Trudność generacji: Mała
- Kolor
Utrudniona lub niemożliwa staje się segmentacja na podstawie koloru. Jednak wykrywanie krawędzi doskonale sprawdza się w takich przypadkach.
Skuteczność: Średnia
Trudność generacji: Mała
- Niski kontrast
Program OCR może odpowiednio wyostrzyć obraz, jednak dla człowieka niski kontrast może być bardzo dokuczliwy w odczytaniu znaków.
Skuteczność: Mała
Trudność generacji: Mała - Średnia
- Rozmycie znaków
Metoda podatna na wyostrzenie znaków.
Skuteczność: Mała – Średnia
Trudność generacji: Średnia
- Tło jednolite
Tło jednolite nie stanowi żadnego problemu przy rozpoznawaniu znaków.
Skuteczność: Zerowa
Trudność generacji: Bardzo mała
- Tło o powtarzalnym wzorze
Jeżeli tło powoduje błędy przy rozpoznaniu znaków można pobrać jego próbkę a następnie odjąć ją od całego obrazu.
Skuteczność: Mała
Trudność generacji: Mała
- Tło niejednolite
Tego typu tła są trudne do wykluczenia, jednak często nie jest to potrzebne w poprawnym rozpoznaniu ciągu znaków. Duży kontrast między tłem a znakami pozwala na poprawną segmentację i ekstrakcję cech.
Skuteczność: Mała – Średnia
Trudność generacji: Średnia
- Małe elementy nie będące znakami
Małe elementy scalone z literami i cyframi mogą skutecznie zaburzyć rozpoznawane znaki. Niestety człowiek także może mieć problemy z odczytaniem kodu.
Skuteczność: Średnia – Duża
Trudność generacji: Mała - Średnia
- Przekreślenie wyrazu
Podobnie jak w przypadku mniejszych elementów nie będących znakami, duże przekreślenia sprawiają trudności maszynom, ale także ludziom.
Skuteczność: Średnia
Trudność generacji: Mała - Średnia
- Nielinearne transformacje
W połączeniu z nietypową czcionką oraz niewielkimi odległościami między znakami może stanowić dobrą barierę przed programami typu OCR.
Skuteczność: Średnia – Duża
Trudność generacji: Średnia - Duża
- Ziarniste znaki
Podatna na próbkowanie, a w bardziej zaawansowanych przypadkach do rozpoznania używa się algorytmów analizy skupień ziaren.
Skuteczność: Średnia
Trudność generacji: Średnia - Duża
- Trójwymiarowe znaki
Jedna z najskuteczniejszych metod utrudniających rozpoznanie znaków. Wykorzystuje zdolność człowieka do spostrzegania trójwymiarowych elementów na dwuwymiarowych obrazach. Bardzo łatwa w odczytaniu dla człowieka i niesamowicie trudna dla maszyny.
Skuteczność: Bardzo duża
Trudność generacji: Duża
- Poruszające się elementy
Trudność rozpoznania bardzo zależy od sposobu użycia animacji w celu utrudnienia rozpoznania znaków. Jeżeli użyty jest obraz GIF, wtedy można wyodrębnić poszczególne klatki animacji i rozpocząć normalne rozpoznawanie obrazów. Problem jest bardziej złożony gdy użyjemy techniki Adobe Flash, wtedy niezbędne okaże się przechwytywanie obrazu z przeglądarki. Bardzo skuteczne są animacje, które pozwalają zidentyfikować znaki dopiero po przeanalizowaniu każdej klatki. Żadna pojedyncza klatka nie może pozwalać na rozpoznanie wszystkich znaków, a najlepszą skuteczność otrzyma się, gdy brak nawet jednej klatki uniemożliwia odczytanie całości. Jako przykład można podać ciąg kilku znaków, które poruszają się w losowy sposób, dodatkowo zmieniają swój kształt (najlepiej za pomocą nielinearnych transformacji) i wielkość. Poza tym cała animacja jest tylko widoczna w bardzo szybko poruszającym się niewielkim oknie. Wyklucza to możliwość analizy poszczególnych klatek, a jednocześnie sprawia, że człowiek nie ma problemu z odczytaniem całości.
Skuteczność: Średnia – Duża
Trudność generacji: Duża
03.12.2008. 18:38
Metody rozpoznawania znaków
Technika CAPTCHA jest stosunkowo młodą metodą liczącą niewiele ponad 10 lat. Rozpoznawanie CAPTCHA jest zbliżone do rozpoznawania zwykłych znaków (głównie liter), które początki swoje miało w końcu lat dwudziestych XX wieku. W 1929, Gustav Tauschek opatentował pierwszą metodę OCR (ang. Optical Character Recognition) czyli technikę rozpoznawania znaków. Cały system składał się z fotodetektora i szablonów liter. Gdy litery dokładnie pasowały do szablonu, wtedy do detektora nie dobiegało światło, a litera została pozytywnie rozpoznana.W latach 50. XX wieku rozwój techniki OCR spowodowany został przez Agencję Bezpieczeństwa Narodowego (NSA) Stanów Zjednoczonych. Wydrukowane rozkazy miały być automatycznie wprowadzane do komputerów.
Kilka lat później został wprowadzony przez Readers Digest pierwszy system OCR dla zastosowań komercyjnych, aby po latach rozwoju w 1965 posłużyć się jako narzędzie do rozpoznawania numerów seryjnych kuponów promocyjnych. Ten prymitywny system był bardzo wrażliwy na zaburzenia i rozpoznawał tylko jeden typ, specjalnie stworzonej do takich celów, czcionki OCR-A. Litery były zapisane jako matryca punktów. Jeżeli rozpoznany obraz pasował do wzorca litery, wtedy literę uznaje się za rozpoznaną. W praktyce oznaczało to, że litera musiała być identyczna ze wzorcem, co przy jakości liter drukowanych za pomocą obecnych w tamtych latach drukarkach było sporym problemem.
Później pojawiły się urządzenia bardziej uniwersalne, które oprócz czcionek OCR-A i OCR-B potrafiły rozpoznać kilka innych. Niestety nadal techniką wykorzystywaną przy rozpoznawaniu było porównywanie ze wzorcem.
02.12.2008. 18:40
Metody rozpoznawania znaków 2
Dopiero w połowie lat 70. XX wieku technikę porównywania ze wzorcem zaczęto zastępować analizą cech charakterystycznych. Zamiast na podobieństwie całej litery skupiano się na jej poszczególnych elementach takich jak linie pionowe, linie poziome, proporcje tych linii, kulistość, zaokrąglenia, kształt krzywizn, zakończenia, współczynniki kątowe. Pozwalało to na rozpoznawanie niezależne od czcionki, gdyż każda litera składa się z określonych części. Na przykład litera „E” będzie rozpoznana gdy wykryjemy jedną pionową linię i 3 poziome, które są krótsze, przylegają do niej pod kątem prostym (lub zbliżonym do kąta prostego) od prawej strony w trzech miejscach. Na górze i dole oraz mniej więcej pośrodku. Opisanie w ten sposób liter jest dużo bardziej pracochłonne, ale także pozwala na większą skuteczność przy odczytywaniu znaków. Taka technika rozpoznawania znaków nazywa się „Omnifont” (łac. omni - wszyscy). Pierwszym urządzeniem, które korzystało z opisanej wyżej metody, był wprowadzony w 1975 roku czytnik KRM (Kurzweil Reading Machine) nazwany tak na cześć swojego twórcy - Raymonda Kurzweila.Na początku lat osiemdziesiątych rozpoczął się nagły rozwój nowej dziedziny nauki jaką była teoria sztucznych sieci neuronowych (Artificial Neural Network Theory lub Neurocomputing). Od samego początku sieci neuronowe znalazły zastosowanie w algorytmach rozpoznawania tekstu. Jednak w pierwszych latach były używane wyłącznie jako klasyfikatory. Na podstawie danych wejściowych, które obejmowały matematyczno-geometryczne cechy charakterystyczne znaku, podejmowały decyzję o tym, jaki to znak. W porównaniu z tradycyjnymi metodami, rozpoznawanie znaków za pomocą sieci neuronowych miało ogromną zaletę - możliwość uczenia się "na przykładach". Specjalnie stworzony zestaw uczący podany na wejście sieci pozwalał na przeszkolenie jej. Następnie, aby sprawdzić skuteczność sieci neuronowej testujemy ją zestawem weryfikującym. Poprawnie przeszkolona sieć powinna być odporna na jak największe zaburzenia i rozpoznawać znaki, które odbiegają wyglądem od swoich wzorcowych odpowiedników z zestawu uczącego.
Obecnie sieci neuronowe wykorzystywane są wówczas, gdy zawodzą inne techniki rozpoznawania znaków. Sieć pełni nie tylko rolę klasyfikatora, ale także sama wykrywa cechy charakterystyczne danego znaku. Odpowiednio połączone warstwy neuronów są w stanie, w trakcie uczenia, wyodrębnić z pikselowego obrazu zadanego znaku cechy geometryczne odróżniające go od innych liter. Poza tym niektóre modele ANN potrafią skutecznie rozpoznawać całe sekwencje mocno zdeformowanych i zakłóconych znaków bez konieczności podziału sekwencji na pojedyncze litery (rozpoznawanie bezsegmentacyjne).
Do rozpoznawania tradycyjnych tekstów dobrej jakości nie opłaca się stosować technik z użyciem sieci neuronowych, które charakteryzują się dużym czasem przetwarzania informacji. W takich przypadkach dużo bardziej efektywna jest metoda „omnifont”. W przypadku niewielkiej ilości mocno zaburzonych znaków takich jak te używane w technice CAPTCHA, sieci neuronowe mogą być bardzo dobrym rozwiązaniem. Jednak ogromna ilość i rodzaj zaburzeń stanowią duży problem nad wyborem odpowiedniego zestawu testowego.
01.12.2008. 18:43
Z tą współdziałamy od długiego czasu, więc warto ją obejrzeć: odzyskiwanie danych. Z tą współdziałamy od któtkiego czasu, więc powinieneś ją odwiedzić: pożyczki. Słyszałem, że ta strona internetowa jest niepowtarzalna: naprawy powypadkowe gorzów. Z tą współdziałamy od paru miesięcy, więc musisz ją obejrzeć: sklepy internetowe. Ta witryna na pewno spodoba Ci się, więc powinieneś ją zobaczyć: Sklep RTV AGD.Spis treści
- Wstęp
- Cel pracy
- Definicja
- Historia
- Gdzie jest używana?
- Dlaczego jest używana?
- Przed czym chroni?
- Dlaczego CAPTCHA jest łamana?
- Kontrowersje
- CAPTCHA a rozpoznawanie znaków