Тем не менее, конечный набор шрифтов может быть подобран, и соответственно использован для создания программ автоматического распознавания. Это проблема, которая была решена относительно искажений символов, с которыми достаточно менять разные параметры от изображения к изображению (например, угол поворота или степень размытия).

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

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

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

2.2 Морфинг шрифтов как новый вид искажения

2.2.1 Определение морфинга шрифтов и применение в CAPTCHA

С целью создания из конечного множества шрифтов несчетное множество, введём определение морфинга шрифтов. Обычно понятие "морфинг" используется в компьютерной анимации для создания эффектов плавного перехода между кадрами, сценами или анимации движения отдельных объектов. В задаче преобразования шрифтов, применим его для пары фигур с целью получения нескольких уникальных промежуточных состояний таким образом, чтобы результатом этой операции стал новый символ, сочетающий в себе очертания таких же символов из других шрифтов.

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

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

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

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

Во-вторых, создание шрифтов должно зависеть от скорости использования генерируемых изображений. В качестве параметра снижающего нагрузку на сервис, можно определить переменную m, как максимальное количество изображений, для которых используется созданный шрифт. Тогда, например, для 1000 изображений CAPTCHA, нужно будет создать 1000/m шрифтов. В этом случае, при скорости обращений к сервису пользователями в 1 изобр. в секунду, получим необходимую скорость создания новых шрифтов в 1/m шрифтов в секунду.

Параметр m может зависеть от количества запросов CAPTCHA в секунду, если реализация сервиса предусматривает защиту от одновременно большого числа запросов одним пользователем.

Параметр m может быть пропорционален отношению количества символов в используемом алфавите к максимальному или среднему количеству символов на одном изображении, если первое больше второго. Например, мощность алфавита, состоящего из латинских заглавных и цифр, 36, а средняя длина набора символов на одно изображение 4, тогда начертание всех символов алфавита может быть показано с помощью как минимум 9-ти изображений. Т.е. существует высокая вероятность того, что можно составить словарь для автоматического распознавания CAPTCHA за 9 изображений. Следовательно, с таким набором параметров, целесообразно менять шрифт через каждые 9 изображений.

Параметр m может определяться уравнением, если запоминать в отдельный массив, какие символы были показаны, а на каждое новое изображение добавлять 1 символ из тех, что показаны еще не были. Тогда для алфавита из 36 символов и фиксированной длинной слова на изображении в 4 символа, m будет равна 33. Разумеется, такая зависимость между символами на изображениях и шрифтами облегчит разработку систем автоматического распознавания. Поэтому в процессе реализации системы должна быть учтена рекомендация демонстрировать изображения из таких серий с выборкой случайным образом, желательно вперемежку и разным пользователям.

Таким образом, нагрузку на сервис можно оптимизировать, но в большинстве случаев, результаты сильно зависят от количества символов в используемом алфавите.

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

Так как морфинг - это создание промежуточных состояний, то условие будет выполняться и на ограниченном наборе шрифтов. Даже при бесконечной выборке состояний между всего лишь двумя шрифтами, например, "Times New Roman" и "Georgia". Однако, кроме преобразований векторов, система генерации CAPTCHA должна еще и создавать изображения в растровом виде, где крохотные изменения положения точек уже не будут заметны, оставшись за рамками погрешности систем автоматического распознавания CAPTCHA.

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

Пусть n - количество шрифтов в базисе, а k - количество шрифтов получаемых в процессе морфинга между 2-мя базисными шрифтами, тогда количество новых шрифтов N будет рассчитываться по формуле (2.4).

(2.4)

Проверим её. Допустим, мы составили базис F₀ из 3 шрифтов (n₀=3) и морфингом собираемся получать по 2 новых шрифта (k=2), тогда N₀ будет равно 6. Мы получили количество новых шрифтов, создаваемых морфингом из взятого базиса.

Представим результат в виде геометрической фигуры, на которой шрифты будут обозначены вершинами, а проведенный морфинг ребрами (см. рис.2.4).

Рисунок 2.4 Схематическое представление увеличения множества шрифтов.

Черным обозначено начальное множество F₀, красным F₁, синим F_2,линиями показаны пары для морфинга.

Составлено автором

Теперь возьмем за основу получившиеся шрифты (F₁), чтобы создать новые (n₁=6).

На этот раз у нас получилось 30 различных шрифтов. Однако каждый из них несет в себе особенности первоначального множества F₀. Если продолжить итерации, то количество шрифтов будет увеличиваться, но с каждым новым циклом все шрифты будут все более и более походить на один - среднее между тремя начальными шрифтами. Таким образом, можно утверждать, что с каждой итерацией, множество новых шрифтов стремится к одному среднему_. То есть для создания программы автоматического распознавания, достаточно знать среднее значение морфинга среди базисных шрифтов, чтобы алгоритм смог распознавать большинство символов на изображениях.

Вновь представим результат 2-х итераций морфинга на множестве шрифтов F₀, только теперь, в каждом новом цикле будут использоваться не только новые шрифты, но и шрифты прошлой итерации (см. рис.2.5). В этом случае, количество элементов второй итерации (N₁) можно будет рассчитать по формуле 2.5 У нас получится 36 элементов.

(2.5)

Новые точки, обозначающие шрифты, появляются равномерно по всей площади треугольника. Следовательно, на i-ой итерации, каждый случайно выбранный шрифт может содержать или не содержать признаков одного или нескольких базовых шрифтов (из множества F₀).

Рисунок 2.5 Схематическое представление увеличения множества шрифтов на каждом отрезке. Черным обозначено начальное множество F₀, красным F₁, синим F₂, линиями показаны пары для морфинга.

Составлено автором

Формула 2.5 позволяет рассчитать количество новых шрифтов в зависимости от выбранных параметров их распределения по имеющемуся базису.

2.2.2 Алгоритм морфинга

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

Рисунок 2.7 Три промежуточных состояния морфинга символа "0" близкие к шрифте "Georgia" (слева) и "Times New Roman" (справа). Зеленым отмечены точки начал сплайнов.

Составлено автором

На рисунке 2.7 изображены три состояния морфинга символа "0" из шрифта "Georgia" в "Times New Roman". Как видно из примера, символ по центру представляет собой нечто среднее между двумя другими.

Рисунок 2.8 Исходные изображения символа "0" шрифтов "Georgia" (слева) и "Time New Roman" (справа). Зеленым отмечены точки начал сплайнов.

Составлено автором

На рисунке 2.8 показаны исходные фигуры символа "0". Сравнивая рисунки, можно заметить, что точки начала сплайнов расположены по-разному: на рис.2.7 они прикреплены к нижнему левому углу, а на рис.2.8 в одном случае к верхнему краю, а в другом к правому. Причина кроется в необходимости унификации фигур перед морфингом, Так как морфинг относительно векторов - это поиск точки лежащей на линии на заданном удалении от двух других, то для каждой вершины её можно определить по формуле 2.6.

(2.6)

В формуле 2.6, v_s и v_e - начальный и конечный вектор, а t - коэффициент, определяющий позицию между ними. Это значит, что между точками двух сплайнов необходимо установить четкое соотношение для реализации дальнейшего поиска промежуточных вершин.

Упрощенный процесс унификации состоит из следующих пунктов:

Чтение файлов шрифтов и конвертация форматов к единому внутреннему представлению. Данный шаг необходим для ускорения и упрощения работы алгоритмов, т.к. каждый формат (TTF, SVG, PS и т.д.) по-своему уникален.

Для каждого сплайна, поиск ближайшей к нижнему левому углу точки и назначение её началом. Пункт является одним из шагов, направленных на установление связи между вершинами двух фигур по их индексам.

Проверка (и изменение) направления расстановки векторов в сплайне так, чтобы они прорисовывались в одном направлении. Значимость шага аналогична предыдущему.

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

Добавление к фигуре новых сплайнов, если их количество в двух фигурах различно. Например, может быть случай, когда в одном начертании цифры "6" овал внутри есть, а в другом его нет, тогда нужно добавить сплайн, который превратится в овал внутри внешнего сплайна. Для реализации данного пункта, среди сплайнов 2-х фигур устанавливается попарное соответствие исходя из положения сплайна и его размеров (актуально, например, для овалов внутри цифры "8"). Затем, для сплайнов без пары из одной фигуры создаются сплайны с таким же количеством точек в другой, только с одинаковыми координатами в центре обрабатываемого сплайна. Получившийся вырожденный сплайн в процессе морфинга развернется в полноценную кривую.

Увеличение числа точек в каждом сплайне. Шаг актуален для вогнутых фигур (например, цифры "7"), т.к. положение одних точек относительно других в сплайнах обоих фигур может отличаться. Увеличение числа точек следует делать, исходя из их расположения относительно точек из другого сплайна соответствующего обрабатываемому. Рис.2.9 хорошо иллюстрирует отсутствие такой корректировки.

Рисунок 2.9 Пример отсутствия корректировки количества и/или положения точек в процессе подготовки фигур к морфингу.

Составлено автором

Рисунок 2.10. Пример морфинга нескольких символов.

Составлено автором

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

2.2.3 Морфинг на множестве шрифтов

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

В пункте 2.2.1 был рассмотрен алгоритм проведения морфинга с использованием двух шрифтов. Однако возможно создание новых шрифтов с использованием трёх и более изначальных шрифтов.

Минимальное количество шрифтов для осуществления морфинга задано числом 2 с целью упрощения формул и алгоритмов его проведения. И не является препятствием для создания новых шрифтов на множестве мощностью более двух.

Рисунок 2.11. Представление множества шрифтов на плоскости.

Составлено автором

Рассмотрим случай, когда множество шрифтов определено как и примем за начало координат точку A, искомый шрифт обозначим как точку X (рисунок 2.11). Тогда для получения шрифта X необходимо провести морфинг между шрифтами A, B и C таким образом, чтобы X сочетало в себе особенности всех трёх шрифтов в соответствии с его положением внутри треугольника ABC относительно вершин.

Для этого построим луч из точки C, проходящий через точку X и пересекающий отрезок AB в точке X_AB (рисунок 2.12).

Рисунок 2.12. Отображение точки X на отрезок AB.

Составлено автором

Тогда отношение длины отрезка AX_AB к длине отрезка X_ABB будет коэффициентом t_AB, необходимым для получения промежуточного шрифта X_AB с помощью морфинга между шрифтами A и B. Таким образом можно получить шрифт X_AB. Для получения шрифта X, определим его коэффициент t_X как отношение длины отрезка X_ABX к длине отрезка CX.

Для случая четырёх шрифтов в исходном множестве, к указанному примеру добавится построение другого луча - из точки D. С его помощью найдём точку X_ABC на плоскости ABC. Пример представлен на рисунке 2.13. После этого, используем алгоритм, описанный в предыдущем абзаце, приняв точку X_ABC за точку X.

Рисунок 2.13. Построение луча из точки D для нахождения проекции точки X на плоскость X_ABC.

Составлено автором

Таким образом, мы определили алгоритм приведения морфинга n шрифтов к морфингу двух шрифтов, который уже известен из пункта 2.2.2 В общем случае для n-мерного множества, потребуется n-1 шагов с морфингом между одним из базовых шрифтов и первым шрифтом из множества или полученным в результате морфинга на предыдущем шаге шрифтом.

3. Практическое применение результатов исследования

3.1 Разработка системы для проведения CAPTCHA

3.1.1 Проектирование и реализация системы

Для организации централизованной системы генерации и проверки символьно-графического CAPTCHA разработаем сервис, предоставляющий такие услуги. В качестве алгоритма генерации изображений использовать пример, описанный в пункте 2.1.2.

Основные требования, предъявляемые к сервису:

Генерация изображений по описанному в пункте 2.1.2 алгоритму;

Удаленный вызов процедур (RPC), описание сервиса с помощью WSDL, обмен сообщениями в формате XML с помощью SOAP;

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

Схема взаимодействия сервиса CAPTCHA и сайта при открытии пользователем формы обратной связи представлена на рисунках 3.1 и 3.2.

Рисунок 3.1 Схема начала взаимодействия сервиса, сайта и пользователя в нотации BPMN.

Составлено автором

На рисунке 3.1 Представлено начало взаимодействия, когда пользователь открывает страницу формы обратной связи, на которой должен увидеть изображение CAPTCHA. Соответственно, сервис должен иметь в кэше заранее сгенерированные изображения и правильные ответы к ним. А после инициализации новой сессии, пометить использованное изображение так, чтобы другой пользователь его уже не получил в соответствии с рекомендациями изложенными в пункте 1.3.

Чтобы отправить введенное сообщение, пользователь должен заполнить форму, среди полей которой будет и поле для ответа на тест CAPTCHA. Однако проверку правильности должен провести сервис CAPTCHA. Схема взаимодействия пользователя, сайта и сервиса при проверке корректности заполненной формы приведена на рисунке 3.2.

Рисунок 3.2 Схема проверки корректности заполненной пользователем формы в нотации BPMN.

Составлено автором

Схема иллюстрирует процесс проверки корректности введенного кода CAPTCHA параллельно с верификацией других полей формы. Хотя это зависит от конкретной реализации сайта, всё же рекомендуется для ускорения его работы.

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

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

В соответствии с представленными на рисунках 3.1 и 3.2 схемами поведения сервиса CAPTCHA при инициализации и проверке, составим схему базы данных, которая предусматривала бы возможность хранения следующих сущностей:

индивидуальных настроек для каждого обслуживаемого сервисом сайта;

журнала успешности проведенных проверок;

информации о заранее сгенерированных изображениях CAPTCHA

Рисунок 3.3 Схема базы данных в нотации UML.

Составлено автором

Схема базы данных представлена на рисунке 3.3 К описании таблицы "captcha_site" стоит добавить следующее:

поле "auth_token" играет роль секретного ключа однозначно идентифицирующего подключенный сайт;

поля, начинающиеся на "captcha_", хранят используемые сайтом опции генерации изображений CAPTCHA, в том числе, размер буфера заранее генерируемых изображений ("captcha_count_lim"), минимальную и максимальную длину слова ("captcha_vcode_len_min", "captcha_vcode_len_max") и настройки, описывающие положение символов относительно друг друга и их искажения.

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

· ссылку на информацию о сайте

· ссылку на запись об изображении CAPTCHA

· время прохождения теста

· код результата, значения которого могут быть следующими:

o "S" - тест пройден ("Succeeded");

o "F" - тест завален ("Finished");

o "OC" - CAPTCHA устарела ("Old CAPTCHA");

o "NC" - нет сгенерированных CAPTCHA ("No CAPTCHA");

o "NF" - указанный код CAPTCHA не найден в БД ("NOT FOUND");

o "OS" - сессия устарела ("Old Session");

o "NS" - не найдена сессия, связанная с указанным кодом CAPTCHA ("No Session").

· вариант, введенный пользователем при попытке пройти тест для последующего анализа.

Описанный сервис реализован с использованием языка Python, фреймворка Django, СУБД MySQL, технологий SOAP и WSDL, а так же модулей suds и spyne для Python с целью организации работы и тестирования сервиса.

Код реализации SOAP-интерфейса системы приведен в приложении 3. Код программы тестирования сервиса приведен в приложении 4. В таблице 3.1 описан паспорт сервиса.

Таблица 3.1. Паспорт сервиса CAPTCHA

№	Код операции	Наименование операции	Назначение операции	Тип параметра	Наименование параметра
1	init	Инициализация новой сессии	Передача ссылки на изображение CAPTCHA	Входящий	XML-документ с токеном сайта
				Исходящий	XML-документ с кодом, по которому можно получить изображение CAPTCHA, и ссылкой на сервер с этим изображением
2	check	Проверка корректности введенного кода CAPTCHA	Передача результатов проверки	Входящий	XML-документ с токеном сайта, кодом изображения CAPTCHA и вариантом ответа
				Исходящий	XML-документ с результатами проверки

Составлено автором

Таким образом, разработана система аутентификации CAPTCHA, удовлетворяющая выдвигаемым требованиям (ее исходный код приведен в Приложении 5). Во-первых, в её основе лежит алгоритм генерации изображений для теста Тьюринга созданный с использованием предложенной в пункте 2.1.2 методики разработки подобных алгоритмов. Во-вторых, система реализована в виде сервиса на основе стандартов WSDL и SOAP, что предоставляет возможность легкой интеграции сервиса со сторонними приложениями. В-третьих, для различных подключенных к сервису сайтов или систем могут быть использованы уникальные настройки подпрограммы генерации изображений, что позволяет применять отличающиеся друг от друга алгоритмы генерации CAPTCHA на разных сайтах или системах.

3.1.2 Тестирование

В процессе разработки сервиса CAPTCHA собирались статистические данные для последующей корректировки алгоритмов генерации изображений. В процессе разработки к сервису были подключены 4 сайта различной тематики, однако наиболее активным его использованием мог похвастаться лишь один. Накопленные статистические данные представлены в таблице 3.1.1 Информация разбита по месяцам, для удобства визуализации, и построен график (рис.3.1.1), на котором представлены результаты двух выборок: генеральной (таблица 3.1.1) и референтной (таблица 3.1.2). Генеральная выборка отражает все имеющиеся у автора данные об успешности прохождения CAPTCHA, в то время, как референтная ограничивает источники данных лишь двумя сайтами, которые предоставили доступ к наиболее интересной для исследования группе людей. Это обусловлено тем, что в генеральную выборку попали, во-первых, данные о прохождении CAPTCHA, которые были созданы в процессе проверки работоспособности сервиса, а во-вторых, приглашенной для тестирования сервиса в декабре 2012 года фокус-группой, состоящей из трех человек, которым была поставлена задача попытаться отгадать по 20 различных CAPTCHA. Что примечательно, после исключения данных о результатах работы фокус-группы, процентное соотношение удачных и неудачных попыток прохождения CAPTCHA практически не изменилось. Хотя пользователи сайтов, статистика из которых попала в референтную выборку, были наименее активны именно в декабре, поэтому погрешность таких данных весьма высока.

Все результаты приведены на рисунке 3.1.1, где изображен процент удачного прохождения CAPTCHA в сравнении с количеством неудачных попыток.

Таблица 3.1.1. Генеральная совокупность данных о прохождении CAPTCHA на основе стандартного алгоритма.

Месяц	Количество попыток, шт.	Итого, %
	Удачных	Неудачных	Всего	Удачных	Неудачных
октябрь	23	12	35	66%	34%
ноябрь	27	7	34	79%	21%
декабрь	104	14	118	88%	12%
январь	72	21	93	77%	23%
февраль	47	11	58	81%	19%
март	51	6	57	89%	11%
апрель	50	14	64	78%	22%
май	35	2	37	95%	5%

Таблица 3.1.2. Выборка референтных данных о прохождении CAPTCHA на основе стандартного алгоритма.

Месяц	Количество попыток, шт.	Итого, %
	Удачных	Неудачных	Всего	Удачных	Неудачных
октябрь	20	12	32	63%	37%
ноябрь	23	6	29	79%	21%
декабрь	15	2	17	88%	12%
январь	72	20	92	78%	22%
февраль	31	6	37	84%	16%
март	28	2	30	93%	7%
апрель	37	3	40	93%	7%
май	34	2	36	94%	6%

Рисунок 3.1.1 График различных выборок данных о прохождения CAPTCHA на основе стандартного алгоритма.

Составлено автором

Как видно из графика на рисунке 3.1.1 и таблицы 3.1.2, общая тенденция оказалась положительной, хотя наблюдались падения количества удачных прохождений CAPTCHA в январе и апреле. Программа сбора статистика была интегрирована в сервис лишь 19 октября 2012 года, когда алгоритм еще не соответствовал требованиям изложенной в п.2.1.2 методики и совершенствовался по мере сбора статистики, поэтому стоит разбить отрезок времени с 19.10.2012 по 25.05.2013 на этапы внесения изменений в применяемый алгоритм. Это позволяет ощутить ценность влияния указанных в методике изменений на практике.

Этап 1, 19.10.2012 - 09.12.2012

Алгоритм имеет следующие характеристики:

используются только цифры

размеры изображения составляют 200 пикселей в ширину и 50 в высоту

длина набора от 4 до 5 символов

наложение символа на предыдущий по оси Х на отрезке от 0 до 1/3 от его ширины Имеется в виду ширина предыдущего символа, т. к. иначе тонкие цифры заслонялись бы широкими

поворот символа на угол на отрезке от - 20 до 20 градусов

используется 29 различных контурных шрифтов

случайный шрифт для каждого символа

Этап 2, 12.12.2012-25.05.2013

Алгоритм претерпевает следующие изменения:

наложение символа на предыдущий по оси Х на отрезке от 0.1 до 0.3 от его ширины

положение символа по оси Y меняется на отрезке от 0 до 5 пикселей (относительно высоты изображения, до 10%)

поворот символа на угол на отрезке от 7 до 15 градусов по часовой или против часовой стрелки

размер символа от 100% до 150% относительно изначального

количество шрифтов сокращено до 22

каждый набор символов изображается одним случайным шрифтов

Хотя основным изменением стало применение одного случайного шрифта ко всем символам набора сразу, на 2-ом этапе развития алгоритма проводились мелкие корректировки алгоритма.

График с данными сгруппированными относительно различных этапов приведен на рисунке 3.1.2, данные для которого представлены в таблице 3.1.3.

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

Таблица 3.1.3. Выборка данных, сгруппированная по этапам изменения алгоритма генерации CAPTCHA

	Генеральная выборка
Этап	Количество попыток, шт.	Итого, %
	Удачных	Неудачных	Всего	Удачных	Неудачных
Этап 1	41	16	57	72%	28%
Этап 2	214	36	250	86%	14%
	Референтная выборка
Этап	Количество попыток, шт.	Итого, %
	Удачных	Неудачных	Всего	Удачных	Неудачных
Этап 1	52	18	70	74%	26%
Этап 2	284	62	346	82%	18%

Рисунок 3.1.2 График различных выборок, сгруппированных по этапам изменения алгоритма генерации CAPTCHA.

Составлено автором

3.2 Разработка системы для генерации новых шрифтов с помощью морфинга и интеграция в систему для проведения CAPTCHA

3.2.1 Проектирование и реализация

С целью реализации масштабируемого проекта, создадим систему генерации новых шрифтов в виде отдельного сервиса. Сформулируем основные требования.

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

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

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

Рисунок 3.4 Схема разделения системы морфинга шрифтов на логические блоки. Составлено автором

Обобщив вышесказанное, автор пришёл к схеме разделения логических частей изображенным на рисунке 3.4 образом. Описание представленных сущностей и их основных функций:

· Интерфейс пользователя - веб-сайт для доступа к настройкам сервиса.

· Внешнее API - внешний интерфейс сервиса для интеграции со сторонними системами. Включает в себя: выдачу новых шрифтов, аутентификацию и контроль частоты обращений к системе.

· Cache API - внутренний интерфейс кэширующей БД для управления шрифтами внутри неё. Выделен в отдельную сущность для уменьшения связности отдельных компонентов системы.

· Генератор шрифтов - запускаемая по расписанию программа создания новых шрифтов на основе имеющихся. Учитывает настройки пользователей. Реализует алгоритм морфинга описанный ранее.

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

· Тип СУБД: Кэширующей БД и БД настроек.

· Количество серверов и узлов Кэширующей БД и БД настроек в том числе для повышения отказоустойчивости и скорости доступа к данным.

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

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

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

Разберём подробнее структуру Генератора шрифтов. С одной стороны, в него поступают имеющиеся в Кэширующей БД шрифты в зависимости от пользовательских настроек. С другой, из него выходят новые шрифты созданные с использованием морфинга. Количество поступающих шрифтов в Генератор может быть от двух штук, верхняя планка теоретически не ограничена.

С целью однозначного именования шрифтов в Cache БД, обозначим общую методику. Морфинг на заданном множестве шрифтов проводится попарно за несколько итераций в зависимости от заданных коэффициентов. Это значит, что можно утверждать следующее: новый шрифт, полученный морфингом на множестве из n шрифтов будет однозначно характеризоваться n-1 коэффициентом и строгой последовательностью морфинга между членами этого множества.

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

3.2.2 Тестирование

Для проверки морфинга шрифтов была создана свёрточная нейронная сеть (CNN), как наиболее подходящая для распознавания изображений Куликова В.В., Тимощук А.С. Сравнение рекуррентных и сверточных нейронных сетей на задаче классификации текста // СТУДЕНЧЕСКАЯ НАУКА ДЛЯ РАЗВИТИЯ ИНФОРМАЦИОННОГО ОБЩЕСТВА сборник материалов VI Всероссийской научно-технической конференции. 2017 Издательство: Северо-Кавказский федеральный университет (Ставрополь).С. 266-269. Программа реализована на базе библиотеки Keras (см Приложение 7). На рисунке 3.6 показан вывод программы обучающей НС. В качестве базы для обучения НС была выбрана база рукописных шрифтов MNIST, так как она позволяет обучить НС так, чтобы образ символа был максимально оторван от мелких деталей конкретных шрифтов.

Рисунок 3.6 Результат обучения НС на базе MNIST.

Составлено автором

1. Проверка распознавания шрифта Times New Roman

В первую очередь, требовалось отладить работу НС и генератора изображений. Поэтому был взят шрифт Times New Roman, полученные результаты распознавания приведены на рисунке 3.7 Все цифры распознаются корректно.

Рисунок 3.7 Результаты распознавания обученной НС цифр из шрифта Times New Roman. Составлено автором

2. Среднее между Times New Roman и фигурой квадрат

Взят созданный с помощью морфинга шрифт, который имеет 70% черт шрифта Times New Roman и 30% черт квадрата (см. рисунок 3.8).

Рисунок 3.8 Шрифт, созданный с помощью морфинга, имеет 70% черт шрифта Times New Roman и 30% черт квадрата

Составлено автором

На рисунке 3.9 представлены результаты работы программы распознавания.

Рисунок 3.9 Вывод результатов распознавания шрифта созданного с помощью морфинга, который имеет 70% черт шрифта Times New Roman и 30% черт квадрата

Составлено автором

Общий вывод: только половина символов была распознана. Проанализируем ошибочные ответы детально:

· цифра "2" распознана некорректно как цифра "4" с вероятностью 98%, скорее всего, из-за сильных перепадов в тонкости своих отдельных частей, так как в рукописных шрифтах подобного нет

· цифра "6" распознана некорректно как цифра "8" с вероятностью 61.3%, в основном, за счёт появившихся искажений

· цифра "7" распознана некорректно как цифра "1" с вероятностью 25.96%, такая ошибка часто допускается и людьми

· цифра "9" распознана некорректно как цифра "4" с вероятностью 55.63%, возможно, в связи с тем, что вырезанная окружность внутри цифры очень мала

Таким образом, ошибки распознавания связаны с наличием появившихся в следствие морфинга артефактов и отличий от рукописных шрифтов.

3. Контурный шрифт Brutality

База MNIST наполнена рукописными образцами. Поэтому был проведён тест распознавания контурного шрифта (Рис.3.10), чтобы оценить влияние этого фактора.

Рисунок 3.10. Контурный шрифт Brutality.

Составлено автором

На рисунке 3.11 приведены результаты тестирования. Они говорят о том, что использование контурных шрифтов оказывает существенное влияние на распознаваемость, когда НС построена на базе MNIST.

Рисунок 3.11. Результаты распознавания шрифта Brutality НС, обученной на базе MNIST.

Составлено автором

Таким образом, вероятность распознавания цифр, изображенных с помощью полученного морфингом шрифта (на 30% квадрат), в свёрточной НС, обученной на базе рукописных шрифтов, снижается примерно на 80% в сравнении с вероятностью распознавания того же шрифта без применения морфинга. Использование контурных шрифтов в той же НС, снижает вероятность распознавания примерно на 50%, что объясняется тем фактом, что НС обучалась не для распознавания контурных шрифтов. Однако следует обратить внимание на то, что влияние морфинга оказалось более существенным. Что может свидетельствовать при прочих равных условиях в пользу эффективности разработанного алгоритма.

Заключение

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

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

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

Однако следует признать, что, стремясь сделать CAPTCHA нечитаемой для ботов, накладывая все больше искажений и шумов, мы генерируем CAPTCHA, нечитаемую и для человека. Анализ ряда сайтов со сложной CAPTCHA с искажениями показывает, что чтобы пройти тест требуется не одна, и даже не две попытки. А если ещё и есть ограничение по времени, то пользователь, зачастую, просто уходит на другие ресурсы. При этом дальнейшие разработки в этой области постепенно приводят к тому, что новейшие программы распознавания умело очищают символьно-графический CAPTCHA от шумов и искажений. Дальнейшее распознавание символов с использованием сверточных нейронных сетей не представляет большого труда.

Для решения указанной проблемы, автором предлагается новый вид нелинейного искажения символов - морфинг, позволяющий решить проблему ограниченности количества шрифтов. Была разработана система для генерации новых шрифтов с помощью морфинга и осуществлена ее интеграция в систему для проведения CAPTCHA. Отсутствие сгенерированного при помощи морфинга нового шрифта в базе нейронной сети позволяет предположить значительные трудности в распознавании.

Для проверки гипотезы была с Проверка ее функционирования проведена на стандартном шрифте Times New Roman, который сеть распознает с вероятностью, близкой к 100%. Автор логично предположил, что морфинг любых стандартных шрифтов (даже в количестве большем, чем 2, а такая возможность у метода имеется) также будет распознан сетью с очень высокой вероятностью.

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

Библиографический список

1. Ахмад А. С.Э. Цвет и надежное конструирование CAPTCHA / Ахмад А.С.Э., Ян Д., Нг В.И. // Открытые системы. СУБД - 2012 - N 4 - С.38

2. Биркун Н.И. Разработка методики оценки уязвимости системы аутентификации на основе технологии CAPTCHA / Биркун Н.И., Тураров Ж.Ж., Зозуля А.О. // Перспективные информационные технологии (ПИТ 2014) труды Международной научно-технической конференции - 2014 - С. 191-195

3. Взгляд на современные системы защиты от спама веб-форм глазами бывшего спамера // Хабрахабр [Электронный ресурс] URL: http://habrahabr.ru/post/107286/ (дата обращения: 25.12.2012)

4. Взлом старой каптчи сайта Хабрахабр // Хабрахабр [Электронный ресурс] URL: http://habrahabr.ru/post/161159/ (дата обращения: 25.12.2012)

5. Голубева А.С. Экспериментальная оценка устойчивости к автоматическому распознаванию CAPTCHA при различных видах искажений // Приоритетные направления развития науки, техники и технологий международная научно-практическая конференция. 2016. С.214-217.

6. Гуськова А.М., Басараб М.А. Исследование эффективности применения CAPTCHA как средства защиты сайтов // Современные тенденции развития науки и технологий - 2015 - N 5-2 - С.12-17

7. Д. Гудкова. Спам в первом квартале 2012. // SECURE LIST. Аналитика. - 3 мая 2012. [Электронный ресурс] URL: http://www.securelist.com/ru/analysis/208050754/Spam_v_pervom_kvartale_2012 (дата обращения 25.04.2013)

8. Ломаем каптчу Яндекса // Хабрахабр [Электронный ресурс] URL: http://habrahabr.ru/post/64535/ (дата обращения 25.12.2012)

9. Мещеряков Р.В., Ягницын В.А. Определение пользователя системы с помощью синтеза речевого сообщения // В сборнике: Научная сессия ТУСУР - 2009 материалы докладов Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых, 12-15 мая 2009 года: в 5 ч. М-во образования и науки Российской Федерации, Федеральное агентство по образованию, Томский гос. ун-т систем упр. и радиоэлектроники (ТУСУР) - Томск - 2009 - С.55-57

10. Морфинг - Википедия // Википедия - Свободная энциклопедия [Электронный ресурс] URL: http://ru. wikipedia.org/wiki/Морфинг (дата обращения: 25.04.2013)

11. Попов А.А., Козлов А.Е. Исследование надежности полностью автоматического теста тьюринга для различения компьютеров и людей (CAPTCHA) для предотвращения несанкционированного ввода информации в интернете // Известия Российского экономического университета им. Г.В. Плеханова - 2012 - N 3 (8) - С.80-98

12. Построение защищенной надписи // CAPTCHA.ru [Электронный ресурс] URL: http://www.captcha.ru/articles/visual/ (дата обращения: 25.12.2012)

13. Распознавание некоторых современных CAPTCHA // Хабрахабр [Электронный ресурс] URL: http://habrahabr.ru/post/116222/ (дата обращения: 25.12.2012)

14. Тьюринг А.М. Вычислительные машины и разум. // В сб.: Хофштадер Д., Деннет Д. Глаз разума. - Самара: Бахрах-М, 2003. - С.47-59.

15. Яковлев А.В. Анализ надежности графических CAPTCHA-систем на примере проекта KCAPTCHA / Шуваева А.М., Пеливан М.А. // Приборы и системы. Управление, контроль, диагностика - 2015 - N 7 - С.15-19.

16. Ян Д. Перспективы повышения устойчивости CAPTCHA / Ян Д., Ахмад А. С.Э. // Открытые системы. СУБД - 2011 - № 2 - С.42

17. CAPTCHA // Wikipedia - The Free Encyclopedia [Электронный ресурс] URL: http://en. wikipedia.org/wiki/CAPTCHA (дата обращения: 25.12.2012)

18. Django documentation // Django Software Foundation, 2005-2012 [Электронный ресурс] URL: https: // docs. djangoproject.com/en/1.4/ (дата обращения 25.12.2012)

19. Documentation suds // Documentation suds [Электронный ресурс] URL: https: // fedorahosted.org/suds/wiki/Documentation (дата обращения 25.12.2012)

20. El Ahmad A. S. The robustness of a new CAPTCHA / El Ahmad A. S., Yan J., Marshall L. // Cборник Proceedings of the 3rd European Workshop on System Security, EUROSEC'10 3rd European Workshop on System Security, EUROSEC'10 - 2010 - С.36-41

21. Gladkikh E. Localized CAPTCHA testing on users and farms / Gladkikh E., Nikolaev K., Nikitin M. // WWW 2014 Companion - Proceedings of the 23rd International Conference on World Wide Web 23 - 2014 - С.277-278

22. Jose A., Vinoth Lakshmi S. Web security using visual cryptography against phishing // Middle East Journal of Scientific Research - 2014 - Т.20 - N 12 - С.2626-2632

23. Lakhvich D. Using CAPTCHA in a massive free association experiment on the internet // CEUR Workshop Proceedings 3 - 2014 - С.167-171.

24. Li S. Breaking e-banking CAPTCHAs / Li S., Shah S. A. H., Khan M. A. U., Khayam S. A., Sadeghi A. - R., Schmitz R. // Сборник Proceedings - Annual Computer Security Applications Conference, ACSAC 26th Annual Computer Security Applications Conference, ACSAC 2010. Сер. "Proceedings - 26th Annual Computer Security Applications Conference, ACSAC 2010" sponsors: Applied Computer Security Associates (ACSA) - Austin, TX - 2010 - С.171-180

25. Metz C. CAPTCHA-ing the spammer; a technology that tries to distinguish between humans and machines may be a capable weapon against spam // PC Magazine - 2003 - С.70

26. Namprempre Ch., Dailey M. N. Mitigating dictionary attacks with text-graphics character CAPTCHAs // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences - 2007 - Т. E90-A - N 1 - С.179

27. Nosach Yu. CAPTCHA development experience using element of HTML5 canvas / Nosach Yu., Kodola G., Volynec N. // Современные инновационные технологии подготовки инженерных кадров для горной промышленности и транспорта - 2016 - N 3 - С.325-334

28. Priyanka K. Providing secure access to biologically inspired databases using CAPTCHA / Priyanka K., Kushwaha D. K., Kaur H. // Proceedings - 2013 International Conference on Machine Intelligence Research and Advancement - 2014 - С.614-618

29. Rui Y., Liu Z. Artifacial: automated reverse turing test using facial features // Multimedia Systems. 2004. Т.9. № 6. С.493-502.rui Y., Liu Z. Artifacial: automated reverse turing test using facial features // Multimedia Systems - 2004 - Т.9 - N 6 - С.493-502

30. Shouket A. K. Secured architecture strategy for fighting against bots / Shouket A. K., Abdullah A., Yasir A. // Computer Sciences and Telecommunications - 2013 - № 4 (40) - С.16-23

31. Shumilov A. Philippovich A. Gesture-based animated CAPTCHA // Information and Computer Security - 2016 - Т.24 - N 3 - С.242-254

32. Shumilov A., Philippovich A. Using 3d animated hand gestures to create a new type of CAPTCHA // CEUR Workshop Proceedings 3 - 2014 - С.151-155.

33. SOAP Version 1.2 Part 1: Messaging Framework (Second Edition) // World Wide Web Consortium (W3C), 2007 [Электронный ресурс] URL: http://www.w3.org/TR/2007/REC-soap12-part1-20070427/ (дата обращения 25.12.2012)

34. SOAP Version 1.2 Part 2: Messaging Framework (Second Edition) // World Wide Web Consortium (W3C), 2007 [Электронный ресурс] URL: http://www.w3.org/TR/2007/REC-soap12-part2-20070427/ (дата обращения 25.12.2012)

35. Spyne Documentation - spyne 2.9.3 documentation // Spyne Contributors [Электронный ресурс] URL: http://spyne. io/docs/index.html (дата обращения 25.12.2012)

36. von Ahn L. CAPTCHA: Using hard AI problems for security / von Ahn L., Blum M., Hopper N. J., Langford J. // Lecture Notes in Computer Science - 2003 - Т.2656 - С.294-311

37. Wang L. Againts spyware using CAPTCHA in graphical password scheme / Wang L., Chang X., Ren Z., Gao H., Liu X., Aickelin U. // Сборник Proceedings - International Conference on Advanced Information Networking and Applications, AINA 24th IEEE International Conference on Advanced Information Networking and Applications, AINA2010 - 2010 - С.760-767

38. Web Services Description Language (WSDL) 1.1 // World Wide Web Consortium (W3C), 2001 [Электронный ресурс] URL: http://www.w3.org/TR/wsdl (дата обращения 25.12.2012)

39. Welcome to PyBrain's documentation! // PyBrain v0.3 documentation - CogBotLab & Idsia [Электронный ресурс] URL: http://pybrain.org/docs/ (дата обращения 25.05.2013)

40. Zadiraka V. K. Using CAPTCHA in computer steganography / Zadiraka V. K., Shvidchenko I. V., Bredelev B. A., Kudin A. M. // Cybernetics and Systems Analysis - 2015 - Т.51 - N 5 - С.801-807

41. Zhu Q., Keogh E. Using CAPTCHAs to index cultural artifacts // Lecture Notes in Computer Science - 2010 - Т.6065 - С.245-257

Размещено на Allbest.ru