Reliability analysis of graphical CAPTCHA-systems by the example of KCAPTCHA.pdf Тест Тьюринга - тест, предложенный Аланом Тьюрингом в 1950 г. Тьюринг пред-ложил исследовать возможность машин делать то, что могут делать люди как мыс-лящие создания. Тест проходит следующим образом. Человек задает вопросы в пись-менном виде человеку и компьютеру. Его задача - определить, с кем он общается.В 1952 г. ученый предложил другую версию теста, получившую название «Стандарт-ная интерпретация». В этой версии жюри задает вопросы компьютеру, а роль компью-тера состоит в том, чтобы заставить значительную часть членов жюри поверить, чтоон на самом деле человек.Существуют модификации теста Тьюринга, в которой роли машины и человека по-меняли местами. Такие тесты называются обратными тестами Тьюринга. CAPTCHA -это разновидность обратного теста. CAPTCHA от англ. «Completely Automated PublicTuring test to tell Computers and Humans Apart»-полностью автоматизированныйпубличный тест Тьюринга для различения компьютеров и людей. Основная идея те-ста - предложить пользователю такую задачу, которую может решить человек, нокоторую несоизмеримо сложно предоставить для решения компьютеру.CAPTCHA чаще всего используется при необходимости предотвратить использо-вание интернет-сервисов ботами, в частности для предотвращения автоматическихрегистраций почтовых ящиков, отправок сообщений, скачивания файлов, массовыхрассылок.Актуальность применения CAPTCHA можно увидеть, например, из статистикиобъемов рассылаемого спама. Более 97 % электронных сообщений, отправляемых че-рез Интернет, являются спамом. Применение CAPTCHA-защиты позволяет усложнитьзадачу регистрации почтовых ящиков ботами.В наиболее распространённом варианте CAPTCHA от пользователя требуется вве-сти символы, как правило, изображённые на предлагаемом ему рисунке в искажённомвиде. Альтернативами являются аудио-CAPTCHA, математические примеры, тексто-вые задачи, задачи на распознавание предметов.Для анализа надежности графических CAPTCHA была разработана компьютер-ная программа на языке Java и проанализирована одна из распространенных систем -проект KCAPTCHA.KCAPTCHA [1]-это готовое решение с открытым исходным кодом для генера-ции графических капч (картинок с проверочным текстом), изначально написанноена языке PHP. На данный момент имеется порт на платформу Java. Пригенерациииспользуется около 20 шрифтов и применяются волновые алгоритмы искажения, ко-торые являются наиболее сложными для автоматического распознавания, но в то жевремя искаженные символы остаются довольно легко читаемыми человеком. Подоб-ные алгоритмы искажения применяются при генерации многих других защищенныхкапч. KCAPTCHA была выбрана для анализа устойчивости графических капч к ав-томатическому распознаванию.Распознавание состоит из нескольких этапов. На начальном этапе происходиточистка изображения. Цвет фона определяется после просмотра крайней области изоб-ражения, в которой не содержится символов. Всем пикселям, цвета которых отлича-ются от фонового не более чем на заданную константу, присваивается цвет фона.Распознавание отдельных символов происходит двумя основными способами. Пер-вый способ - распознавание на основе количества «ног» символа и распознавание наоснове количества «ног» повернутого символа. Например, символ «m» стоит на трех«ногах». Символ «с», повернутый на 0, 180 и 270°, стоит на одной «ноге»; символ «с»,повернутый на 90°, - на двух «ногах».Второй способ - распознавание на основе анализа контрольных точек скелета изоб-ражения и связей между ними. Для выделения скелета используется алгоритм утонче-ния изображения Зонга -Суня [2]. Контрольными точками или вершинами называ-ются точки, лежащие на пересечении двух или более отрезков, и точки на концах этихотрезков. Для каждой контрольной точки определяются и анализируются их соседи ипути до них.Такие тесты были написаны для цифр и букв английского алфавита. Строчные ипрописные буквы не различаются. При стандартных настройках системы KCAPTCHAточность распознавания отдельных символов лежит в диапазоне от 87 до 99 %. Времяраспознавания одного символа при работе одного ядра процессора мощностью 2,4 ГГцсоставляет примерно 30 мс.Общий алгоритм распознавания выглядит следующим образом.1. Находится скелет изображения.2. Находятся контрольные точки скелета изображения и сортируются по X-коор-динате.3. Для первой вершины находятся все контрольные точки, до которых существуетмаршрут от данной вершины. Если разница X-координат текущей вершины и любогоее соседа меньше заданной константы, то список этих вершин передается на распо-знавание. Если символ распознан, выбирается новая текущая вершина и алгоритмпродолжается. Иначе распознаваемый символ имеет общие точки со своим соседом.Необходимо их разделить. Для этого просматриваются вершины, имеющие трех илиболее соседей. Если вершина удовлетворяет определенным критериям, то из списка еесоседей удаляются некоторые вершины. Новый список соединенных вершин передает-ся на распознавание. Если символ распознан, его вершины помечаются как просмот-ренные и происходит переход к началу алгоритма.Эффективность алгоритма зависит от количества символов, имеющих общие точ-ки со своими соседями, и от количества мест соединений различных символов. Наи-большую сложность при автоматическом распознавании вызывает сегментированиесимволов, имеющих общие точки.

Скачать электронную версию публикации