Фрактальная капча на Python

27 июля 2011

После написания заметки о генераторах фракталов, меня посетила одна идея. В свое время я интересовался автоматическим распознаванием капч (которые captcha). Так вот, распознавание происходит в несколько этапов. Текст капчи отделяются от фона, вычищается от мусора, нарезается на буквы. Затем буквы приводятся к одному размеру и используются для обучения нейронной сети. Притом первый шаг — отделение текста от фона, как правило, является довольно простым.

Давайте посмотрим на некоторые капчи:

Примеры Captcha

Обратите внимание на номера с 4-го по 7-й. Эти капчи достаточно контрастны для того, чтобы преобразовать их в черно-белое изображение (матрицу ноликов и единичек) практически без потери информации. С капчей номер 3 та же проблема, хотя это и менее очевидно. На самом деле она даже слабее остальных капч, потому что позволяет легко разбить изображенное число на цифры. Эту капчу когда-то давно я написал для своего первого форума.

Вы могли узнать капчу номер 1, она использовалась (до сих пор используется?) Яндексом. И она была успешно взломана без особой магии. Капча номер 2 может показаться надежной, но на самом деле она таковой не является. Капча номер 6 также была взломана.

Номера 4 и 5 — это KCaptcha и Blogger.com соответственно. Обе пока что держатся, видимо за счет сложности нарезания букв. KCaptcha, если вдруг кто не в курсе, пользуется большой популярностью. Например, она используется в движке DLE и на rutracker.org. Так что сломав ее можно поиметь неплохой профит.

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

При чем тут фракталы? Рад, что вы спросили (на самом деле вы не спрашивали, но возразить-то все равно не можете :). Как выяснилось, есть такой алгоритм генерации красивых картинок под названием плазма. Алгоритм очень простой. И да, картинка, которую он выдает на выходе — это тоже фрактал.

Иллюстрация к предыдущим двум абзацам:

Алгоритм создания Captcha

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

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# FractalCaptcha.py v 0.1
# (c) Alexandr A Alexeev 2011 | http://eax.me/

from PIL import Image, ImageDraw, ImageFont, ImageFilter
from random import random

# создаем капчу, содержащую символы из строки secret
def captcha(secret, width=200, height=80,
    fontName='arial.ttf', fontSize=54,
    blur = 2):
  mask = Image.new('RGBA', (width, height))
  font = ImageFont.truetype(fontName, fontSize)

  x_offset = -10
  draw = ImageDraw.Draw(mask)
  for i in range(len(secret)):
    x_offset += 20 + int(random()*20)
    y_offset = -10 + int(random()*30)
    draw.text((x_offset, y_offset), secret[i], font=font)

  # последний символ также должен быть повернут
  angle = -10 + int(random()*15)
  mask = mask.rotate(angle)

  bg = plazma(width, height)
  fg = plazma(width, height)
  result = Image.composite(bg, fg, mask)

  # blur усложнит выделение границ символов
  # альтернативный вариант - гаусово размытие:
  # http://rcjp.wordpress.com/2008/04/02/gaussian-pil-image-filter/
  if blur > 0:
    for i in range(blur):
      result = result.filter(ImageFilter.BLUR)
 
  # почему-то blur иногда не действует на границах капчи
  # использовать crop?
  return result

# генерируем "плазму" размером width x height
def plazma(width, height):
  img = Image.new('RGB', (width, height))
  pix = img.load();

  for xy in [(0,0), (width-1, 0), (0, height-1), (width-1, height-1)]:
    rgb = []
    for i in range(3):
      rgb.append(int(random()*256))
    pix[xy[0],xy[1]] = (rgb[0], rgb[1], rgb[2])

  plazmaRec(pix, 0, 0, width-1, height-1)
  return img

# рекурсивная составля функции plazma
def plazmaRec(pix, x1, y1, x2, y2):
  if (abs(x1 - x2) <= 1) and (abs(y1 - y2) <= 1):
    return
   
  rgb = []
  for i in range(3):
    rgb.append((pix[x1, y1][i] + pix[x1, y2][i])/2)
    rgb.append((pix[x2, y1][i] + pix[x2, y2][i])/2)
    rgb.append((pix[x1, y1][i] + pix[x2, y1][i])/2)
    rgb.append((pix[x1, y2][i] + pix[x2, y2][i])/2)
   
    tmp = (pix[x1, y1][i] + pix[x1, y2][i] +
           pix[x2, y1][i] + pix[x2, y2][i])/4
    diagonal =  ((x1-x2)**2 + (y1-y2)**2)**0.5
    while True:
      delta = int ( ((random() - 0.5)/100 * min(100, diagonal))*255 )
      if (tmp + delta >= 0) and (tmp + delta <= 255):
        tmp += delta
        break
    rgb.append(tmp)

  pix[x1, (y1 + y2)/2] = (rgb[0], rgb[5], rgb[10])
  pix[x2, (y1 + y2)/2]= (rgb[1], rgb[6], rgb[11])
  pix[(x1 + x2)/2, y1] = (rgb[2], rgb[7], rgb[12])
  pix[(x1 + x2)/2, y2] = (rgb[3], rgb[8], rgb[13])  
  pix[(x1 + x2)/2, (y1 + y2)/2] = (rgb[4], rgb[9], rgb[14])
   
  plazmaRec(pix, x1, y1, (x1+x2)/2, (y1+y2)/2)
  plazmaRec(pix, (x1+x2)/2, y1, x2, (y1+y2)/2)
  plazmaRec(pix, x1, (y1+y2)/2, (x1+x2)/2, y2)
  plazmaRec(pix, (x1+x2)/2, (y1+y2)/2, x2, y2)

if __name__ == '__main__':
  result = captcha("12345")
  result.save("result.png", "PNG")

Если под Windows интерпретатор будет ругаться по поводу поддержки шрифтов, поставьте PIL отсюда. Капча будет смотреться красивее, если использовать шрифт Comic Sans MS.

Важный момент. Перед тем, как вернуть картинку, мы пару раз применяем к ней фильтр blur. Если этого не делать, будет относительно несложно выделить контуры символов. Я рисовал капчи в Gimp в соответствии с последней иллюстрацией, делал различные варианты размытия, а затем пытался выделить границы символов с помощью фильтров типа «Лаплас», «Неон» и их комбинаций. Выяснилось, что лучше всего границы скрываются либо после многократного размытия изображения по Гауссу, либо после многократного blur.

Поскольку в PIL нет размытия по Гауссу, выбор пришлось сделать в пользу blur. С другой стороны, а что нам мешает использовать стороннюю реализацию размытия по Гауссу? Вот соответствующая заплатка к скрипту:

8a9,22
> from numpy import mgrid, exp
>
> def gaussian_grid(size = 5):
>     m = size/2
>     n = m+1  # remember python is 'upto' n in the range below
>     x, y = mgrid[-m:n,-m:n]
>     fac = exp(m**2)
>     g = fac*exp(-0.5*(x**2 + y**2))
>     return g.round().astype(int)
>
> class GAUSSIAN(ImageFilter.BuiltinFilter):
>     name = "Gaussian"
>     gg = gaussian_grid().flatten().tolist()
>     filterargs = (5,5), sum(gg), 0, tuple(gg)
32,34d45
<   # blur усложнит выделение границ символов
<   # альтернативный вариант - гаусово размытие:
<   # http://rcjp.wordpress.com/2008/04/02/gaussian-pil-image-filter/
37,38c48
<       result = result.filter(ImageFilter.BLUR)
<  
---
>       result = result.filter(GAUSSIAN)

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

Фрактальные капчи

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

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

Метки: , .

Подпишитесь на блог с помощью RSS, E-Mail, Google+ или Twitter.

Понравился пост? Поделитесь с другими: