Анализ алгоритмов генерации CAPTCHA - Справочные материалы - Системное администрирование - Каталог статей - Архив документации и мануалов для админов

Воскресенье, 11.12.2016, 13:50
Приветствую Вас Гость | RSS
Мой сайт
Главная
Регистрация
Вход
Форма входа

Меню сайта

Категории раздела
Об ОС Windows [137]
В категории размещаются статьи, касающщиеся операционных систем от Microsoft.
Об ОС *Nix [198]
В данной категории собраны статьи об ОС семейства Unix/Linux/FreeBSD/...
Справочные материалы [351]
Справка по всему разделу.
Виртуализация и Облака [46]
Networks & Routing [86]
DataBases [22]

Наш опрос
Оцените мой сайт
Всего ответов: 193

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

Главная » Статьи » Системное администрирование » Справочные материалы

Анализ алгоритмов генерации CAPTCHA

Анализ алгоритмов генерации CAPTCHA

Дата: 18.01.2012 02:06 (Изменено: 25.02.2012 15:52)
Автор: Intellect Категория: Капча Теги: captcha, алгоритмы, защита
Введение

Эта статья выходит как продолжение статьи Какой должна быть капча?

Здесь мы рассмотрим существующие решения различных защит CAPTCHA их минусы и плюсы, стойкость к распознаванию и читаймость со стороны человека.

Естественно вы должны давать себе отчет в том для чего вы разрабатываете защиту от спам ботов на своем сайте. То есть конкретно от чего вы хотите защитится? Вариантов два:
1) От случайных спам-ботов. Существует много спам-ботов, гуляющих по интернету, и пытающихся заспамить любые формы. Если форма защищенна капчей, он пытается ее распознать автоматически. Если капча очень простая, ему это получется, если капча хотябы чуть-чуть усложнена то у него не получается распознать и бот идет искать другую форму.
2) От целенаправленного взлома капчи. Это когда кто то садится писать программу-анализатор целенаправленно под вашу защиту, учитывая все особенности генерации вашей капчи.

Защищаясь от случайных спам ботов достаточно будет реализовать какую нибудь простенькую защиту на JS без картинки. Или если вы таки решились на CAPTCHA то достаточно будет очень простой капчи.

А вот от целенаправленного взлома вас не спасет ни один алгоритм. Тут скорее вопрос в том сколько ресурсов готов потратить взломщик на вашу защиту. Если ему понадобится для этого нанять десяток программистов, а также арендовать пару десятков серверов, то я думаю он откажется от этой затеи.

Алгоритмы

Возьмем самую простейшую капчу и попытаемся ее усложнить . Вот такой рисунок у нас будет подопытным

1. Случайный шум

Очень часто разработчики накладывают шум на картинку. Вот например вот так:
Но они видимо не знают, или не догадываются что такой шум очень легко убрать. Смотрите сами. Весь шум состоит из множества случайных пикселей. Попробуем взломать капчу с шумом. Чтобы убрать шум, анализируем каждый пиксель на картинке.

А точнее анализируем пиксели вокруг него. Если количество закрашенных пикслей вокруг него меньше определенной константы, то этот пиксель является шумом, если больше то этот пиксель принадлежит картинкe. Убираем пиксели определенные как шум и получаем чистую картинку. В зависимости от силы шума проходим алгоритм несколько раз. Посмотрим что получится у нас:
Ой) В первом случае мы получили практически оригинальную картинку. А во-втором случае мы получили картинку с парой клякс и чуть-чуть кривыми цифрами, но ни то ни другое не скажется на качестве распознавания.

Итого имеем усложнение читамости, практической пользы - нет.

2. Случайные линии

Хм, а давайте проведем эксперимент? Давайте применим к обоим картинкам предыдущий фильтр "антишум".

Ну вот и линий не осталось. Конечно вторая картинка пострадала немножко, но не настолько чтобы ее нельзя было распознать.
Итог: Смысла в линиях нет

3. Сетка

Еще один из примеров это наложение сетки:

Не знаю на что рассчитывают авторы, но это вообще глупость какаято. Опять применяем банальный антишум и получаем:

Конечно не обязательно использовать "антишум". Можно програмно высчитывать шаг сетки и убирать ее. Но обычно все сетки делают толщиной в один пиксель, и "антишума" будет достаточно чтобы ее убрать.

То есть толку от наложения сетки нет..

4. Игра цветами

Тут конечно очень много вариаций как можно сгенерировать картинку.
Допустим сделать разноцветный шрифт. Смысла нет. Определяем цвет фона, и все отличное от цвета фона закрашиваем в черный цвет. Так получаем оригинал.

Сделать разноцветный фон и оставить шрифт черным. Опять не правильно. Заменяем все "не черное" (т.е. цветной фон) на белый и получаем оригинал.

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

Итог: при правильном подходе, можно реализовать стойкую капчу. Но необходимо обязательно учитывать тот момент чтобы пользователь смог эту капчу потом прочитать.

5. Уменьшение контраста с фоном


Для машины отличие даже в один бит - это уже абсолютно разные цвета. И машина сможет распознать даже такое изображение:

Бьюсь об заклады вы подумали мол "что за серый прямоугольник", но вглядитесь, там видны контуры цифр, (или у вас хреновый монитор).
Итог: бесполезно

6. Градиентные цвета

Такой алгоритм генерации считается стойким к програмному распознанию, так как почему то считается что "не существует алгоритма позволяющего выделить участок с текстом из картинки". Давайте развеем этот миф и взломаем градиентную капчу. Возьмем вот такой градиент:

Пусть все цвета для градиента выбираются случайно и так чтобы всегда был контраст с фоном (во всех подобных капчах так и происходит).
В данном случае всякие увеличения/уменьшения контрастности/яркости не помогут выделить текст. И тут многие программисты становятся в тупик. Но делается это элементарно. Выделим часть строки пикселей из этой картинки:

Обратите внимание. В градиенте соседние пиксели лишь незначительно меняют свой цвет. Резкий контраст происходит на границах с цветом текста. На основе этого факта пишем программу, которая будет построчно обходить картинку (алгоритм для каждой строки в виде блок схемы).

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

Что имем в итоге? Затраты на генерацию такой картинки в разы выше чем у обычной картинки, т.к. закрашивание градиентом - ресурсоемкая задача. Но при этом эта защита обходится относительно просто. Вообщем опять толку нету.

7. Смещения символов


Весь алгоритм сводится к поиску "самых темных" участков с размерами приблизительно соответствующим размерам символов. Выделяем такие участки и распознаем. Как выделять области с символами из изображения смотрите ниже.

Фактически опять ничего не изменилось. Нет никакого увеличения стойкости.

8. Вращение символов

Еще один используемый метод это вращения/наклоны символов. Вот пример этого:

Идея распознавания очень проста. Мы вырезаем отдельный символ и вращаем его до тех пор пока ширина квадрата в который вписывается символ не станет минимальной. Возьмем тройку из этой капчи в качестве примера и попробуем повращать влево и вправо:

(Под каждым символом указанна ширина в пикселях)
Как видите - теория верна. Мы нашли оригинальный символ. Тоже самое повторяем для остальных символов и получаем в итоге оригинальную картинку.
И снова капча взломана.

9. "Склеивание" символов

Ну и конечно многие считают что "склеивание" символов поможет от разбиения картинки на участки с символами с последующим их распознаванием.

Но и здесь картинку можно элементарно разбить на символы. Кстати именно этот метод позволяет находить положения символов в пункте "6. Смещение символов". Я упущу тот момент что все символы могут быть одинаковыми по ширине и тогда можно будет картинку поделить на равные части. Так вот вырежем участок с символами и увеличим его:

А теперь построим график количества черных пикслей для каждого "столбца пикселей" в изображении:

Согласитесть сразу бросается в глаза три точки минимума соответствующие границам символов. Благодаря этому графику разбиваем рисунок на части и распознаем как обычно. Причем даже если символы частично наложить друг на друга (в разумных пределах), на графике все также будут видны точки минимумов, хоть и не так явно. Что дает возможность распознавать изображения даже с наложениями символов.
Итог: бесполезно

10. Скручивание символов

Рассмотрим скручивание и прочие изменения геометрии символов.

На мой взгляд одна из немногих методик, действительно снижающих процент распознания капчи. Конечно при условии что каждый раз изменение геометрии уникально, иначе можно подобрать параметры обратного преобразования.
Минусы:
- Сложно в реализации
- Ресурсоемко
- Снижает читабельность
Плюсы:
- Сложно для программного распознования

Но опять же, сложно это не значит не возможно. Для решения данной проблемы существует класс алгоритмов называемых "нейронные сети" - им скармливается огромное колличество уже распознанных изображений, алгоритм самообучается на основе этих результатов, до тех пока сам не сможет распознавать новые изображения.

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

Итог: хоть порой сильно снижает читабельность, но этот метод оправдан

11. Абстракции

Появилась у меня идея использовать такой вот метод:

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

Вообщем не буду подводить конкретных итогов. Так как метод придумал сам (не претендую на авторство, возможно такие реализации уже существуют), и объективно судить себя не могу.
На мой взгляд, стойко к програмному распознанию но сильно снижает читабельность.

Заключение

При разработке своей CAPTCHA-защиты сайта учитывайте приведенный выше материал, и не пользуйтесь теми методами которые не увеличивают стойкость капчи, так как эти методы в большинстве снижают читабельность кода на картинке (см. золотое правило)

Всему своё место, всему своё имя – читай RSS не проходи мимо!


Источник: http://intsystem.org/295/analiz-captcha-algorithms/
Категория: Справочные материалы | Добавил: admin (22.12.2012)
Просмотров: 604 | Комментарии: 1 | Теги: analize, CAPTCHA | Рейтинг: 0.0/0
Всего комментариев: 0
Имя *:
Email *:
Код *:
Поиск

Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz


  • Copyright MyCorp © 2016