globik 10 июн 2011 в 15:33

Взлом матановой капчи на C# — это просто!

4 мин

42K

В этом топике я хочу вам рассказать о взломе т.н. «матан-капчи», пример которой был представлен в недавнем топике Матановая капча на PHP — это просто!.
Прочитав статью автора об этой замечательной капче, мне захотелось написать программу для её распознавания, как говорится just for fun ;)

Начнем со стандартной подготовительной процедуры, а именно: поиска уязвимостей. Уязвимости, помеченные курсивом не используются при распознавании.

Слабые стороны:

Черные символы на белом фоне.
Отсутствие шумов и других артефактов (например линий).
Символы никогда не пересекаются.
Всегда одинаковый шрифт.
Под интегралом всегда 4 слагаемых.
Степени и множители состоят из одной цифры.
Степени и множители находятся в диапазоне от 2 до 5.

К сильным сторонам можно отнести:

Наличие нелинейных искажений.
Возможное отсутствие степени или множителя x.
Иногда, dx слипаются в один символ.
Меняется ширина капчи.

Составим алгоритм распознавания:

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

Исходная капча

Битовое изображение

За единицу будем считать пиксель, чья яркость по цветовой модели HSB < 0.8, за ноль, соответственно >= 0.8. После этого, капча примет следующий вид:

Нумерация символов

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

public int FloodFill(ref int[,] source, int num, int x, int y)
{
    if (source[x, y] == -1)
    {
        source[x, y] = num;
        FloodFill(ref source, num, x - 1, y - 1);
        FloodFill(ref source, num, x - 1, y);
        FloodFill(ref source, num, x - 1, y + 1);

        FloodFill(ref source, num, x, y - 1);
        FloodFill(ref source, num, x, y + 1);

        FloodFill(ref source, num, x + 1, y - 1);
        FloodFill(ref source, num, x + 1, y);
        FloodFill(ref source, num, x + 1, y + 1);
        return ++num;
    }
    return num;
}

...

int num = 1;
for (int x = 0; x < CaptchaWidth; x++)
    for (int y = 0; y < CaptchaHeight; y++)
        num = FloodFill(ref bit, num, x, y);

Распознавание символов

Учитывая нелинейные искажения и отличающийся размер символов лучшим вариантом для их распознавания, будет искусственная нейронная сеть. Что бы немного облегчить задачу, я воспользовался бесплатной библиотекой Fast Artificial Neural Network Library. Она написана на C++, и хороша тем, что имеет интерфейсы практически под все популярные языки программирования, включая и C#.

Все символы, перед распознаванием приводятся к одному размеру: в данном случае 16px x 21px.
Таким образом, на вход нейронной сети будет подаваться массив из 336 элементов (16*21). Каждый элемент задает цвет соответствующего пикселя целым числом: 0 или 1.
Средний слой состоит из 130 нейронов. А на выходе массив из 14 элементов с вещественными значениями от 0 до 1, соответствующими числам от 0 до 9, знаку +, d, x, и слипшемуся dx.

Обучение проходило на 3090 образцах, среди которых больше всего символов «x» и меньше всего «d». Несмотря на это, процесс обучения на моём C2D e6750 занял всего 40 секунд.
Код для обучения НС:

static void Main(string[] args)
{
    NeuralNet net = new NeuralNet();
    //Указываем слои нейронной сети
    uint[] layers = { 336, 130, 14 };
    net.CreateStandardArray(layers);
    //Устанавливаем случайные веса
    net.RandomizeWeights(-0.1, 0.1);
    net.SetLearningRate(0.7f);
    //Загружаем данные для обучения НС
    TrainingData data = new TrainingData();
    data.ReadTrainFromFile("train.tr");
    //Обучаем сеть
    net.TrainOnData(data, 1000, 0, 0.001f);
    //Сохраняем готовую НС в файл
    net.Save("skynet.ann");
}

Структура текстового файла train.tr:

num_train_data num_input num_output
inputdata seperated by space
outputdata seperated by space
...
inputdata seperated by space
outputdata seperated by space

Примеры символов, передающихся на распознавание:

Распознавание интеграла

Сперва найдем и распознаем пределы. Верхний может состоять из 1-2 цифр, причем максимальное значение равно 10. Нижний находится в диапазоне от 0 до -10.
Облегчим задачу нейронной сети:

Если верхний предел состоит из двух цифр, то это 10 (нижний из трех).
Минус распознаем алгоритмически по пороговому значению высоты символа.
При распознавании, не будем учитывать выходы НС, не соответствующие цифрам.

Найдем знак интеграла, просто двигаясь вправо от левой границы с отступом от верхней границы в половину высоты капчи. Все, что правее – подынтегральное выражение.
Зная номер интеграла, количество объектов на капче, и то, что эти объекты пронумерованы слева направо, дальнейшим последовательным распознаванием символов мы получим примерно следующую строку «5x5+x5-4x2+4x5dx». Предварительно упростим работу парсеру выражения — приведем её к виду "+5x5+x5-4x2+4x5".
Некоторые закономерности позволяют легко получить итоговые данные для решения интеграла:

Знаки "+" и "-" разделяют слагаемые.
Цифры после «x» – степень.
И т.д.

На выходе получим 2 массива с множителями и степенями x. Дальнейшее решение интеграла трудностей уже не представляет.

Вместо заключения

Качество распознавания всей капчи впечатляет: 93,8% на выборке в 500 штук!

Скачать готовую программу, демонстрирующую решение интеграла можно здесь. Или вместе с исходниками (+ программа для обучения нейросети и обучающая выборка) здесь.
Надеюсь, ни мой сервер, ни сервер хабраюзера grishkaa не ляжет под хабраэффектом ;)

Теги:

Хабы:

.NET