В последнее время ни один более или менее популярный сайт не обходится без использовании капчи. Эпоха «Веб 2.0» дала пользователям возможность изменять содержание сайтов, но вместе с этим такую возможность получили и спамеры. Ручное заполнение форм спамерам экономически невыгодно, поэтому они используют роботов, на пути которых и становится капча. CAPTCHA — Completely Automated Public Turing test to tell Computers and Humans Apart. Принцип капчи основан на сложности автоматического распознавания искаженного и зашумленного текста.

Адекватность защиты
При выборе капчи стоит исходить из основного правила построения систем безопасности — стоимость взлома должна превышать стоимость того, что может получить злоумышленник. Однако, в случае с капчей есть две проблемы, не позволяющие нам в полной мере реализовать это правило. Во-первых, чрезмерное усложнение капчи может отпугнуть некоторую часть посетителей сайта, например, если заставлять их вводить код с изображения при добавлении каждого комментария (как это делают некоторые владельцы блогов в LiveJournal). Вторая проблема — «китайцы».

В интернете существует несколько сервисов, предлагающих услуги по ручному распознаванию капчей жителями Китая и некоторых других стран, готовых работать за мизерную плату. Часть этих сервисов заявляют, что обладают уникальными технологиями автоматического распознавания образов, однако, при ближайшем рассмотрении такие факты, как задержка в 30 секунд перед отправкой ответа и вероятность распознавания выше 90%, выдают их реальные схемы. Стоимость распознавания 1000 экземпляров начинается от $1, что не так уж и много. Кроме того, существует давно известный способ бесплатного краудсорсинга — подстановка капчи, требующей распознавания, на другой ресурс (как правило порно-сайт), пользователи которого, ничего не подозревая, будут вводить код с изображения. Эти факты ограничивают наши возможности по усложнению защиты.

Говоря об адекватности защиты, стоит разделить спам-роботов на автоматических и полуавтоматических. Автоматические роботы подобно роботам поисковых систем переходят с сайта на сайт и пытаются заполнить и отправить любую форму, которую встретят по пути. Если после отправки формы на странице появляется отправленная информация, форма заносится в список и периодически «спамится». Продвинутые версии таких роботов способны распознавать некоторые виды популярных капч, но большая часть капчей, особенно разработанные для сайта индивидуально, таких роботов успешно останавливают. Собственно, автоматические роботы и являются основной угрозой для подавляющего большинства сайтов. Сайты с большой посещаемостью или хотя бы хорошим рейтингом PageRank могут удостоиться персонального внимания спамеров, что может означать более «тонкую» настройку робота, использование «китайцев» или применение системы распознавания образов, пример которой будет рассмотрен чуть ниже в этой статье.

Немного математики
При распознавании капчи задача состоит не столько в увеличении точности распознавания, как это может показаться на первый взгляд, сколько в минимизации процессорного времени, необходимого для успешного распознавания одного экземпляра. Немногие сайты отслеживают количество неудачных попыток ввода капчи, но в любом случае такие ограничения легко обходятся при использовании нескольких прокси-серверов. Таким образом точность распознавания, равная даже в 1%, может считаться успешной, при условии приемлемого расхода процессорного времени на все 100 попыток.

Одна из основных характеристик капчи — количество возможных вариантов ответа. Допустим, наша капча состоит из 6 цифр и символов латинского алфавита в нижнем регистре, тогда количество всех возможных комбинаций (10 + 26) ^ 6 равно приблизительно 2 млрд., что практически недостижимо для случайного перебора. К сожалению, не все проводят такие расчеты, поэтому периодически появляются капчи, предлагающие ответить, какое животное изображено на картинке, имея при этом всего лишь 10 вариантов ответа. При ручном анализе такого сайта, спамеру будет достаточно указать роботу только один вариант ответа — теория вероятностей сделает все остальное. Сюда же можно отнести и всевозможные арифметические задачи («Сколько будет пять умножить на семь?»), которые легко решаются при помощи регулярных выражений. Однако, для полностью автоматических роботов даже такого вида защиты будет достаточно.

Ещё одно популярное заблуждение создателей капчей: чем сложнее прочитать код человеку, тем сложнее прочитать его роботу. Это заблуждение приводит к появлению капч, которые пользователи с трудом вводят с десятой попытки, но при этом автоматическое распознавание работает на ура. Например, человеку трудно читать светлый шрифт на светлом фоне, а для системы распознавания разница между цветами в один бит так же легко определяется как и визуально заметная разница. Вообще, использование в капче более чем двух цветов практически бесполезно, обратите внимание на капчи крупных сайтов — большая часть из них состоят из темной одноцветной надписи на белом фоне. Это связано с тем, что наиболее сложной задачей является распознавание текста в самой надписи, а не поиск её местоположения на изображении. Помимо прямой уязвимости, капча может оказаться ненадежной из-за уязвимости в скриптах. Например, самая глупая ошибка — передавать текст капчи в виде параметра к скрипту, который генерирует изображение. Или возможность использовать код с изображения несколько раз в течение какого-то времени.

Пример взлома
Итак, лучший способ понять, как оценить надежность капчи — разобрать пример взлома. Выбор пал на капчу сайта xakep.ru, которая используется при регистрации новых пользователей и добавлении комментариев. Код состоит из четырех цифр, что дает нам 10000 вариантов — не так уж и много, но от прямого перебора защитит. Для вывода цифр используется один шрифт, надпись слегка поворачивается в пространстве, но поворот настолько незначительный, что мы не будем принимать его во внимание.

«Пиксельный» шум по всему изображению снимается простейшим фильтром по яркости: все пиксели, яркость которых выше некоторого значения, закрашиваются белым цветом, остальные — черным. Такая операция очищает практически весь шум, за исключением отдельных точек, не мешающих дальнейшей обработке. Остается лишь одна проблема — случайно разбросанные линии, которые значительно затрудняют, во-первых, определение позиции надписи, во-вторых, распознавание отдельных цифр. Поставим задачу довести точность распознавания хотя бы до 5% при приемлемых затратах процессорного времени. Такая постановка задачи позволит нам выбрать уязвимость, которая должна встречаться хотя бы в каждой 20-й капче и с большой вероятностью гарантировать нам распознавание. И такая уязвимость есть — на некоторых изображениях линии практически не пересекают цифры и такие изображения встречаются достаточно часто. От этой особенности и будем отталкиваться.

Для работы нам в первую очередь потребуется набор распознанных образцов. Скажем, 100 штук для начала будет достаточно. Для этого придется немного поработать «китайцем», но для упрощения задачи можно написать небольшой скрипт, загружающий изображения с капчами с сервера и формирующий форму, которую нам придется заполнить вручную. Так как мы решили опираться на наименее зашумленные изображения, то в качестве образцов стоит использовать именно их. Итак, через несколько минут скучной работы у нас есть директория, в которой аккуратно сложены файлы с капчами, имена которых соответствуют кодам на изображении (например, 2716.jpg). Для подобных экспериментов лучше всего подходят скриптовые языки, такие как PHP или Python, также может быть полезен Matlab, в котором есть удобные библиотеки для анализа и обработки изображений. Мы будем использовать PHP, в котором все функции для работы с изображениями имеют префикс image, для низкоуровневой работы с пикселями достаточно imagecolorat. Вот, например, фрагмент кода, который формирует маску изображения с темными участками:

Маска, во-первых, выполняет роль упомянутого выше фильтра по яркости, а, во-вторых, увеличивает скорость работы с изображением — нет необходимости каждый раз выполнять преобразования при сравнении цветов пикселей.

Поиск надписи
Основной принцип, на котором основаны надежные капчи, — затруднение выделения отдельных символов в надписи. Это достигается путем смещения символов относительно их первоначальных позиций и искажений надписи в целом. В капче сайта xakep.ru расстояния между центрами цифр (~19 пикселов) и размеры самих цифр (16x24 пискселов) практически не меняются. Из всех искажений, применяемых к надписи, значительный эффект оказывает только наклон шрифта — им нам пренебречь не удастся. Если бы не шумовые линии, мы бы смогли сразу точно определить расположение цифр на изображении путем отсечения светлых участков со всех четырех сторон — наши цифры были бы единственным темным пятном. Но придется решить небольшую оптимизационную задачу.

Задача оптимизации в общем виде состоит в поиске оптимального значения параметров некоторой целевой функции, значение которой необходимо максимизировать или минимизировать. В нашем случае целевой функцией будет суммарная яркость (точнее её обратное значение) области предполагаемого расположения надписи. Другими словами мы будем стараться найти на изображении темное пятно, по форме напоминающее нашу надпись (нам известны размеры цифр и расстояния между ними). Итак, у нас есть 4 прямоугольника, которые при наличии наклона шрифта превращаются в параллелограммы, необходимо найти такое расположение этой группы параллелограммов и такой наклон, чтобы минимизировать суммарную яркость внутри этих параллелограммов. В итоге у нас есть три параметра: x, y (левый верхний угол первого параллелограмма) и d — сдвиг нижнего основания относительно верхнего. Такой метод поиска надписи будет эффективен для не слишком зашумленных линиями изображений, о которых мы и говорили выше.

Для решения подобных задач оптимизации, таких, для которых нет возможности найти аналитическое решение, хорошо подходят генетические алгоритмы. Генетический алгоритм моделирует процессы биологической эволюции: на основе естественного отбора направляет случайный перебор решений в нужном направлении (максимизации или минимизации целевой функции). На первом шаге алгоритма создается начальная популяция особей, каждая особь — один из вариантов решения (набор параметров). Затем для каждой особи рассчитывается значение целевой функции, называемое в контексте эволюции приспособленностью. Если значение целевой функции устраивает постановщика задачи, алгоритм останавливается, если нет — начинается создание нового поколения.

Новое поколение формируется на основе предыдущего с помощью операторов мутации и кроссовера, которые моделируют соответствующие биологические процессы. Оператор мутации изменяет случайным образом один из параметров решения, а оператор кроссовера скрещивает два решения (например, случайным образом выбирается часть параметров первого решения и соединяется с соответствующими параметрами второго). Отбор особей для создания нового поколения осуществляется по принципу естественного отбора — чем выше значение целевой функции (приспособленность) особи, тем выше вероятность её перехода в новую популяцию. После создания нового поколения вновь проводится оценка каждой особи, выявляется лучшая и проверяется условие остановки. Если цель всё ещё не достигнута, создается очередная популяция и т.д. В нашем случае решением является вектор из трех переменных x, y и d, а целевая функция — суммарная яркость пикселов внутри параллелограммов. Расчет целевой функции производится следующим образом:

Так как во время работы алгоритма расчет целевой функции для заданного решения будет происходить многократно, разумно будет использовать маску, создание которой было описано ранее. Маска позволит избежать многократных преобразований и сравнений цветов пикселей при оценке решения. Реализовав алгоритм и проведя тестирование получаем очень хорошие результаты — 90% точного определения расположения надписи при затратах в одну-две секунды процессорного времени. На основе найденного решения «вырезаем» все 4 цифры из изображения и приводим их к прямоугольному виду (16x24 пикселов):

Распознавание
Теперь задача сводится к распознаванию каждой отдельной цифры. Даже на «удачных» образцах с низкой зашумленностью цифры все равно в большинстве случаев перекрываются линиями, что не позволит нам просто сравнивать их с шаблонами. Классический инструмент для распознавания текста — искусственные нейронные сети, которые мы и будем использовать. Искусственная нейронная сеть представляет собой математическую модель нейронной сети головного мозга человека (или животного). Нейросеть состоит из простейших элементов — нейронов. Нейроны связаны между собой, по этим связям проходят сигналы — числа от 0 до 1. Каждый нейрон выполняет несложную математическую операцию: на основе поступающих от других нейронов сигналов и их весов вычисляется выходной сигнал текущего нейрона. Веса связей между нейронами являются параметрами, которые определяют работу нейронной сети.

Нейроны группируются в последовательность слоев (feedforward сети), входной сигнал (условия задачи) поступает на первый слой и последовательно проходит все слои до последнего (решение). Обучение нейронной сети может происходить с учителем (набором уже решенных задач) или без него (например, на основе реакции среды). Обучение с учителем происходит путем последовательного выполнения нейронной сети на уже решенных задачах и сравнения получившегося результата с ответом: если ответ не совпадает, производится коррекция весов связей. С математической точки зрения нейронная сеть в целом — это «черный ящик».

Процессы, происходящие внутри нейросети, очень трудно поддаются математическому анализу, поэтому для прикладных целей нейросеть достаточно рассматривать как некоторую систему, способную находить закономерности в некоторых наборах данных. Самостоятельно реализовывать нейронные сети для такой задачи дело неблагодарное, поэтому мы воспользуемся бесплатной библиотекой Fast Artificial Neural Network (wwwleenissen.dk/fann). Эта библиотека хороша тем, что имеет интерфейсы практически для всех популярных языков программирования и требует минимального опыта работы с нейросетями. Для использования достаточно нескольких функций:

// Создание нейросети
// Параметры:
// 1. Количество слоев и нейронов в каждом из них
// 2. Связность нейросети (1 – полносвязная)
// 3. Скорость изменения весов при обучении
$ann = fann_create(array(384, 150, 10), 1, 0.7);

// Обучение нейросети
// Параметры:
// 1. Нейросеть
// 2. Обучающий набор (массив, содержащий массивы, соответствующие входному и выходному слоям)
// 3. Максимальное количество итераций
// 4. Допустимая погрешность
// 5. Промежутки, через которые выводится отчет об обучении
fann_train($ann, $set, 10000, 0.001, 100);

// Выполнение нейросети на входном наборе $input
$output = fann_run($ann, $input);

// Запись нейросети в файл
fann_save($ann, 'ann.data');

// Загрузка нейросети из файла
$ann = fann_create('ann.data');

Опытным путем была подобрана оптимальная структура нейронной сети для нашей задачи — три слоя по 384, 150 и 10 нейронов. Первый (входной) слой принимает значения соответствующих пикселов (16х24 = 384) изображения цифры, нормализованные к отрезку от 0 до 1 (значение яркости), внутренний слой играет основную роль в распознавании, а последний выходной слой представляет собой вектор из 10 переменных от 0 до 1, каждая из которой соответствует одной из цифр: чем выше значение, тем больше подобие изображения, соответствующей цифре. В данном случае используется только один внутренний слой, потому что логика, реализуемая нашей нейросетью, практически является «примеркой» усредненных шаблонов каждой цифры к изображению, поэтому нескольких последовательных операций не требуется. Для обучения нейросети воспользуемся заготовленными образцами, кроме того нам потребуется ещё один набор образцов для независимого тестирования, который должен формироваться случайным образом без учета зашумленности:

Первая попытка обучения на 100 образцах дала 43% успешных распознаваний на независимом тестовом наборе, что соответствует примерно 3% (0.43 ^ 4), что уже близко к нашей цели. Дополнив базу образцов ещё 100 экземплярами, получаем 55% успешных распознаваний отдельных цифр и примерно 10% всей капчи. С учетом того, что на попытку распознавания одной капчи расходуется около 1-2 секунд процессорного времени, общие затраты на успешный взлом одной капчи составят 10-20 секунд. Это, в целом, приемлемое время, однако увеличение количества образцов для обучения нейросети позволит значительно снизить эти расходы. Для тестирования используем следующий код:

Выводы и заключение
Как показывает практика, любая капча может быть взломана, вопрос лишь в том, оправдает ли результат затраченные усилия. Что на данный момент точно нереализуемо, так это универсальная система распознавания, способная без какой либо ручной настройки распознавать любые капчи. Какие рекомендации можно дать сайту xakep.ru по усилению безопасности капчи? Во-первых, добавить искажения, изменяющие расположение цифр относительно друг друга, что затруднит их разделение. Во-вторых, исключение вариантов, при которых шумовые линии практически не перекрывают надпись, — это также затруднит определение положения всей надписи и уменьшит точность распознавания цифр нейросетью. В-третьих, можно увеличить количество цифр хотя бы до 6, что значительно уменьшит общую вероятность успешного распознавания. Эти рекомендации справедливы и для большинства других сайтов. Для тех сайтов, взлом капчи которых является экономически выгодным для спамеров, следует предусматривать дополнительные меры защиты, например, подтверждение регистрации через отправку кода по SMS (как это делает Google в некоторых случаях).

Технологии распознавания образов, текстов, звуков развиваются параллельно с увеличением вычислительной мощности компьютеров. Рано или поздно капчи перестанут быть преградой для роботов, однако, проблема может быть решена с помощью упомянутого выше подтверждения через смс или надежных OpenID-провайдеров, осуществляющих проверку своих пользователей.

Интересные капчи
reCAPTCHA. Тем, кто хочет воспользоваться готовым решением, можно посоветовать использовать reCAPTCHA (recaptcha.net). reCAPTCHA помимо защиты сайта от роботов выполняют другую полезную функцию — помогает оцифровывать бумажные книги. Капча состоит из двух слов, одно из которых уже было распознано ранее, а второе не смогла распознать система оцифровки книг. Пользователь, разумеется, не знает, какое слово неизвестно системе, поэтому вынужден вводить оба. reCAPTCHA хороша тем, что использует слова, которые ранее не прошли через систему распознавания, т.е. для ее взлома как минимум придется переплюнуть серьезную коммерческую OCR-систему. Ко всему прочему, reCAPTCHA использует дополнительные шумы и искажения, которые периодически меняются. Недостаток у reCAPTCHA только один — она очень популярна, соответственно и интерес к её взлому очень большой.

Трехмерная капча. Создатели этой капчи (http://ocr-research.org.ua) уверены в ее стойкости. Разумеется, стандартные системы распознавания текста с ней не справятся, но при индивидуальном подходе можно найти ряд уязвимостей. Во-первых, символы расположены на одинаковом расстоянии друг от друга и находятся на одной линии (в трехмерном пространстве). Во-вторых, легко заметить, что торцы выпуклых символов состоят из многоугольников, по площади больших, чем многоугольники остальной поверхности. Эти многоугольники легко найти программно, а вместе они формируют отчетливые контуры символов. На основе контуров символов можно определить углы, на которые была повернута плоскость, и развернуть её обратно. После этого можно проводить распознавание каждого отдельного символа с помощью нейронной сети. Так как эта капча не очень популярна, можно считать её достаточной для ресурсов, не представляющих особый интерес для спамеров.

Капча с виртуальной клавиатурой. Очень хорошая капча до недавнего времени была у сервиса mail.ru. Капча состоит из нескольких символов некоторого периодически изменяемого алфавита. Пользователь вводит ответ с помощью виртуальной клавиатуры. Основное преимущество такой капчи — очень хорошая стойкость к ручному распознаванию «китайцами». Дело в том, что сервисы, предлагающие ручное распознавание, работают по принципу: отправил картинку, получил ответ в текстовом виде. Для ручного распознавания потребовалось бы создание специального интерфейса для передачи помимо изображения ещё и виртуальной клавиатуры. Кроме того ввод этой капчи занимает больше времени, чем ввод большинства других, потому что определять непривычные для глаза символы сложнее, чем символы латинского алфавита или цифры. Таким образом увеличивается стоимость ручного распознавания. Автоматическое распознавание также затруднено: постоянная смена символов не позволит хорошо обучить нейросеть, а также сами символы трудно отделить друг от драга. Основной недостаток — сложность ввода для обычного пользователя, возможно, по этой причине в mail.ru от нее и отказались.

Анимированная капча. Интересный вариант капчи предложил Нилой Митра из Института технологий Дели (видео – http://brightcove.newscientist.com/serv … 7814603001). На основе трехмерной анимированной модели некоторого объекта (например, бегущей лошади) создается анимация, на которой объект покрыт случайно изменяющимися пятнами. Кроме того схожими пятнами покрыт и весь фон. На основе одного кадра распознать объект может быть трудно, но в динамике на это уходит пара секунд. Автоматическое распознавание на данный момент крайне затруднено — при таком количестве шума очень трудно определить, какие из этих пятен должны формировать образ. Казалось бы, очень перспективное направление, однако у капчи есть серьезный недостаток. Для её использования потребуется создание базы анимированных моделей, на каждую из которых придется затратить значительное количество времени, иначе можно будет просто угадывать ответ многочисленными попытками. Кроме того, если каждый раз не генерировать новую анимацию (что дает большую нагрузку на процессор), можно будет сохранять хеши распознанных вручную изображений. Также эта капча никак не защищена от сервисов, предлагающих ручное распознавание.