войти зарегистрироваться

Искусственный интеллект whois

индекс
225,69

Ломаем каптчу Яндекса

На прошлой неделе был топик «Ломаем капчу» — каптча там была довольно простая, но в комментариях предложили сломать каптчу Яндекса. Мне эта идея показалась интересной, и я решил попробовать.




Постановка задачи


Итак, у нас есть вот такая каптча:



Основные особенности:
  • 6 цифр;
  • Изображение монохромное;
  • Фон белый;
  • Искажения, которые, однако, незначительно смещают цифры со своих позиций;
  • Две шумовые линии очень похожие на синусоиды.

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

Задача: написать программу, распознающую каптчу Яндекса с вероятностью не менее одного процента.
 

Первичная обработка


Приступим. Для начала сделаем самую простую часть — приведем изображение к удобному для распознаванию виду. Код написан на PHP (скриптовые языки для таких экспериментов удобнее), внизу будет ссылка на архив с исходниками.

Для начала закрасим логотип Яндекса белым прямоугольником (его координаты не меняются):



Иногда этот прямоугольник «откусывает» часть последней цифры, но это не страшно.

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



Убираем линии


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

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

В итоге решено было использовать генетические алгоритмы, тем более, опыт работы с ними у меня большой. Останавливаться на описании ГА я не буду — об этом можно прочитать в Википедии.

Суть работы ГА в нашем случае — подобрать такую линию (а точнее набор точек), которая лучше всего удовлетворяет нашей целевой функции. Целевая функция (fitness) для каждого предложенного ГА варианта решения считает его приспособленность в виде одного положительного числа. В нашем случае это количество точек решения, которые попадают на пиксели, отличные от цвета фона, плюс дополнительные очки за «связность линии» (иначе решение будет состоять из отдельные точек).

Начальная популяция генерируется из линий, типичных для этой каптчи. Оператор мутации — «вытягивание» линии в случайном месте. Оператор кроссовера стандартный. Выбор особей в новую популяции по принципу рулетки.

Однако, генетический алгоритм — прожорливая штука. Адекватные решения он находил за 2-3 минуты, что в нашем случае неприемлемо, а также почти в каждом случае возникала одна проблема — линия «перескакивала» с полосы на часть цифры. С точки зрения нашей целевой функции такое поведение выявить было невозможно (см. 1-ю и 4-ю цифры):



В начале статьи я упомянул, что линии похожи на синусоиды — этот предположение оказалось полезным. В качестве решения я взял не набор точек, а параметры синусоиды (растяжение по осям, угол наклона, начальная фаза, сдвиг по вертикали). Перебирать 5 параметров намного проще, чем почти 200. К тому же теперь нам не надо следить за формой кривой — она изначально такая, которая нам необходима. Оператор мутации теперь меняет случайный параметр синусоиды, а оператор кроссовера не используется. В итоге за 8-10 секунд алгоритм неплохо справляется с поставленной задачей:



Теперь остается только закрасить белыми линиями толщиной в 3 пикселя (небольшой мусор остался):



И обрезать края с порогом в несколько пикселей:



Divide and conquer


Разделяем изображение на 6 равных частей, обрезаем лишние края, масштабируем каждое до размеров 20х30 пикселей:



Качество немного пострадало, но мы все ещё можем легко сказать, какие там изображены цифры, значит и робот сможет :) Задача сводится к распознаванию каждой отдельной цифры.

Если удастся добиться распознавания отдельной цифры с вероятностью не менее 50%, общая вероятность правильного распознавания каптчи будет 0,5^6 ~ 0.015, т.е. 1,5%, что нам и требуется.

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

Самому кодить нейросеть дело неблагодарное, да ещё и на PHP — пошел искать библиотеку. Первое, что выдал Гугл, — Fast Artificial Neural Network Library. Библиотека написана на C++, но имеет интерфейсы для большинства распространенных сред. Есть extension и для PHP (правда на последнюю версию он ставится не без напильника).

На вход нейросети подается массив из 600 элементов (изображение 20х30 пикселей), каждый элемент задает яркость соответствующего пикселя вещественным числом 0 до 1. На выходе — массив из 10 элементов от 0 до 1, каждый из которых задает близость входных данных к соответствующей цифре. Между входным и выходным слоями всего лишь один слой из 150 нейронов. Почему один? Так получилось в результате практических экспериментов, что такая конфигурация работает лучше всего на этой задаче.

Библиотека действительно очень быстрая — на 300 образцах (50 каптчей) за 5 минут она обучила нейросеть до 30% вероятности распознавания. Неплохо, но нам нужны как минимум 50%.

Постепенно добавляя новые образцы для обучения (пришлось поработать китайцем), заветные 50% были получены на 1800 образцах после 3 часов обучения. На тестовом наборе из 100 каптчей (не участвовавших в обучении) удалось успешно распознать 2, что соответствует нашим предположениям. Время распознавания одной каптчи — 8-10 секунд.
 

Заключение


Поставленная задача выполнена. На все ушло два вечера (+ ночью компьютер сеть обучал). Можно было «добивать» каптчу и дальше, добавляя новые и новые образцы для обучения, но у меня на это нет времени да и желания. Хотя, если кто-то захочет, за пару дней сможет довести дело до конца, а пока у ребят из Яндекса есть время на усложнение каптчи :)

Архив с исходниками выложу минут через 30.

UPD: исходники: yandex_captcha.tar.gz (1 Мб).

По просьбам в комментариях выкладываю без скриптов для обучения и вариант с 40% вероятностью распознавания (для каждой цифры). Думаю, Яндексу это не навредит.

UPD2: небольшое FAQ:

Q: 1,5% — это же мало!?
A: Дальнейшее увеличение точности зависит лишь от количества образцов для обучения и проблемы не представляет.

Q: Почему бы не попытаться «выправить» линии вместе с цифрами?
A: Искажения цифр и линий не зависят друг от друга.
+386
15 июля 2009, 15:13
P_r_i_m_a_t

комментарии (300)

  • теперь гугл на очереди
    • А они меня потом лазерным лучем со своего нового спутника не сожгут? :)
      • За вами уже выехали :)
        • *сжигает ноутбук*
          Яндекс или сразу Гугл? :)
          • И флешку попробуйте разобрать, а то вдруг они научились расшифровывать.
          • на подхоже новый гаджет для гиков — автосжигалка ноутбука, питающаяся по USB этого же ноутбука.
            • Не напоминает Uplink? ;)
      • раскрыть комментарий
    • неоднократно убеждался что даже вводя правильную капчу в гугле, гугл «сьедает» её только с 3-4 раза
      это баг или фича?
      • Это главный секрет: спутник сканирует место, откуда вводится каптча, и ищет беснующегося человечка, если таковой находится, значит каптчу вводит не робот.
        • Нифига. Они преобразуют введенную пользователем строку в изображение, накладывают шумы, и сравнивают его с капчей. Не всегда сравнение удается по техническим причинам.
          • Чорт. Почему глупые юморные комментарии набирают баллы, когда внизу идут серьезные дискуссии по теме топика, и всем похеру что там обсуждается. А вот лазерный луч, бендер и тупые шутки типа моей — это да, это понятно, это нужно плюсануть. А многие ведь читают только комментарии с большой зелененькой или краснинькой цифиркой справа.
            • Ну и что? Это ж хабрасила. Она мало что даёт.
              А вот попробуйте высказаться поперёк мнения любого гуру — выясните как шустро изменяется карма из-за серьёзных ответов.
      • минусующие, сейчас специально проверил — то же самое, gmail требует 3-4 ввода правильной капчи для регистрации, ошибиться в самой капче сложно — она хорошо читается

        ощущение, что для некоторых ip есть определенное количество «штрафных» капч, необходимых для успешной регистрации
    • Или же знаменитая ReCAPTCHA
      • Ога, ога, ломануть её и ABBYY банкрот.
        • ды там человек-то хрен разберет, что накалякано…
          • Ну у нейронок прокаченных распознавалка как правило лучше работает, чем у людей.
            • иногда может создасться впечатление, что отсеивают не роботов, а людей )))
              • Ага, обычно раз по 5 обновляю её, прежде чем ввести...))…
      • Особенно интересно посмотреть на процесс взлома её аудио версии…
    • так их сломали уже давно кажется. что-то подобное не так давно слышал. ведь это тоже люди придумали. а другие сломали. все как обычно=)))))
      • да, вон человек ниже уже написал, что статью скоро напишет как и что.
      • эх блин. фанаты, е мае, вы хоть погуглите для приличия. www.webplanet.ru/news/security/2008/02/15/gmail_capcha.html вот первое, что нашел.
        • Весело получается ) Гугл нашёл и показал как ломать самого себя же )))
        • Там, однако, нет ничего про то, как её сервер распознавал. Возможно, китайцами просто…
  • очень круто! %))
  • Супер. Вот это уже намного серьезнее, нежели пример который был до этого. Реально, rocket science :)
  • Автор укусил Yandex за капчу :)
    • И даже не подавился :) Впечатляет | Интересная статья
  • молодец!
  • Блин скоро капчи до такого состояния усложнят, что человек будет их с тетьей четвертой попытки распознавать, не то что робот =)
    • *третьей
      • многие это уже сделали
        • да я и у яндекса со второй попытки угадываю…

          самые крутые капчи у reCAPTCHA — и полезные и несложные человеку.
          • Самая жесткая капча — котята с рапидшары. Было бы интересно с таким справиться
            img13.nnm.ru/0/d/3/8/f/0d38fbce1d05cc1702089d54af96a8a8_full.jpg
            • Хех, это просто. Нужен скриптик, который говорит «Кыш!», ну а дальше — понятно.
              • Дык там нужно еще угадывать только сидящих котят. Или еще каких
            • вот конкретно с этой капчей вполне реально справится, мы просто ротейтим котят и передвигаем матрицу по рисунку, записываем координаты совпадений, как распознать данный шрифт — я думаю писать не надо. Дальше пересекаем, намного проще чем яша.
              • У них одно время котята со шрифтом еще «погнутые» были, так что не всё так тривиально.
            • Я ее ни разу не прошел :-/
            • img379.imageshack.us/img379/6630/1208799443965hz7.png
            • Если мне не изменяет память, эту капчу легко взломали. Прога есть Universal Share Downloader, легко распознавала.
              • вот у меня он ниразу нормально не работал.

                только я поставлю попробовать в очередной раз — на оффсайте сообщение, что рапида сменила алгоритм, и пока капчи — руками))))
                • Вы наверно попали как раз на период, когда рапида каждый день капчи меняла)) Но и тогда выход был — народные умельцы взламывали в течении нескольких часов и заливали на свой сервак новый алгоритм — можно было настроить автообновление проги с их сервака =)
            • Вспомнил про котят: KittenAuth (http://arstechnica.com/old/content/2006/04/6554.ars).
      • Их усложнят до такого состояния, что боты их будут понимать чаще, чем люди…
    • скоро уже никакие капчи не помогут. регистрироваться будем только ПО БЛАТУ ))
      • как на хабре :) строго по приглашениям :)
        • Да-а-а, «строго», все уже поставили IE8 и набивает инвайты. dammit, грядет наплыв крабов
    • А помните котят и щеночков на файло-помойке? Я вообще с пятого-шестого раза только отгадывал их!
  • Отлично, но было бы интересно посмотреть на реализацию нейросети на чистом РНР.
    • а вот это не оно?

      www.tremani.nl/open-source/neural-network/?p=source
      • О! Классно! Спасибо, после работы вечерком засяду за эксперименты.
        • блинский, извините. трекбол, случайно минуснул.
          • исправил вашу ошибку :)
          • Да, как бы, ничего страшного :)
          • Давно с трекболом? Я к своему неделю привыкал, теперь он кажется мне в сто раз удобнее мышки и в двести раз лучше тачпада :)
            • к трекболу (домашнему) привыкаю по мин 10 мин каждый день после рабочей мышки )))

              для работы трекбол хорош когда нервы никто не треплет и все идет своим чередом, а если запара, то старая мыша выручает
            • Гениальнейшее изобретение, но вот позиционирование на маленьких расстояниях бывает проблемным (шарики засорились и не вертятся). Иногда.
              Мыши (и тачпады) в утиль!
            • если привыкнуть к планшету еще удобнее будет :)
              • у самого планшет wacom'овский, рисовать на нем просто сказка

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

                Мышка и трекбол удобнее, небольшое мановение руки и все :)
                • не, к планшету я более чем привычен, но продолжительное время держать руку на весу мне неудобно, то есть все таки требует непривычного напряжения мышц и больше двух-трех часов работать с ним сложно.
          • Если бы на хабре сделали возможность переголосовать пока не перезагрузил страницу, но не дождешься скорее всего. Просто помню что эту проблему обсуждали больше года назад.
      • Не смог удержаться :) Конец рабочего дня благополучно сорван.
        • и ведь не пятница :)
          • Среда — почти пятница;) По крайней мере, когда такая пища для ума.
      • спасибо, посмотрим
  • Меня всегда интересовали разработки ABBY, наверняка если бы они взялись то могли бы многие капчи распознать.
    • В какой-то из качалок с файлообменников (USD Downloader, кажется) использовались именно библиотеки Finereader'a для обхода капчи.
  • Поздравляю)
  • Пойду готовить статью по взлому гугловской капчи… Там я делал без нейросети
    • ждем с нетерпением!
  • Бедный яндекс…
    Может не надо исходники выкладывать?
    • это нехорошо, невыкладывать — некорректно.
      лучше выложить — пусть подумают, поменяют.

      и всем хорошо — нам интересно, им безопасно.
    • Поддерживаю. Автор, вы молодец! Алгоритм — этого достаточно. Не нужно исходников.
      • Я не буду выкладывать скрипт обучения, образцы и т.п. Только текущий вариант решения — использовать его дороже, чем китайцев :)
      • все равно хочется хотя бы одним глазком посмотреть
    • 1,5% распознавания это не так много, до большего придется допиливать день-два. У Яндекса есть время…
      • Как вы предполагаете, каков может быть предел точности? Если, например, использовать 10 тыс. образцов. Или 100 тыс.
        • По грубым подсчетам 10-20 тыс. образцов для 65-70%. Дальше трудно сказать.
          • Это я про вероятность для отдельной цифры.
    • «Может не надо исходники выкладыватьЭ

      Кому надо у того уже есть.
  • Вроде USD качает(раньше точно качал) без распознавания. Скорее всего сообщает яндексу что Яндекс.Бар стоит
    • При выходе Фаерфокса с яндекс-баром быстро выяснилось, что достаточно передать определённый юзер-агент, и капча не требуется.
  • Программисты яндекса вас проклянут — вы прибавили им работы
    • Да ладно. Им достаточно вместо синусоиды еще пяток функций добавить.
      • да, а потом пользователи мучайся за рядями кривых искать цифры
    • Чем сложней, тем интересней.
    • ни в коем случае не проклянут, а, напротив, будут благодарны.
      • ничего, они наймут на работу программиста — колдуна вуду и каждому, кто будет пытаться распознать капчу программно будет проклят :)
    • придумывать новые проклятья?
  • было интересно, спасибо :)
  • Вот так брейншторм)))
  • раскрыть комментарий
    • хехе. Сильно! :)
    • от блин, копипаст не дал картинку нормально вставить :( своё что-то вставил :(

      меня за это заминусовали так? :)

      здесь она (про arctg):
      copypast.ru/2009/05/15/15_samykh_strannykh_kaptch_15_foto.html
      • Простите за минус :) исправился. И других призываю. Человек же неспециально анимашку вставил!
      • Ответ 2, считается устно не смотря на страшный вид, отличная капча была бы для хабра.
    • а в чём смысл каптчи тогда?
  • мегабизон!
  • Эхх, жаль у меня капча с рапидшары не сохранилась, там раньше была капча что не каждый человек ее розберет.
    • Да, с этими их кошечками и собачками я раза с пятого только подбирал ее…
    • На капче vBulletin можно и сейчас тренироваться в распознавании. Иной раз, проще юзера через админку создать (или алгоритм капчи упростить), чем в капче разобраться :)
  • 2 капчи из 100? Изначальный план перевыполнен в 2 раза =).
    А почему это вообще должно представлять опасность для Яндекса? Вероятность меньше 5 процентов при времени распознавания 10 секунд? Эффективнее руками заполнять. Сколько автоматических успешных срабатываний будет, и за какой срок? 6 капч в минуту, 360 в час, 8640 за сутки, и распознается 200 капч. 200 капч быстрее заполнить за 10 минут руками.
    Яндексу нет причин что-либо усложнять :).
    • Автор же написал, что две капчи ис ста не предел, ведь сеть можно обучать дальше =)
      • Да, вопрос только в количестве образцов.
      • все равно предел есть. может он будет на 3х капчах?
        • Предел есть, конечно же — 100 из 100.
          • 150 нейронов на одном слое? сильно сомневаюсь что предел именно такой
            • Нейроны и слои добавить не проблема…
    • Руками вы за 8 часов устанете как собака. А робот может сутками ковыряться :)
      • Китайцы пока побеждают у робота. Они не устают)
        • устают конечно, просто меньше чем люди. помимо этого у них есть еще одно очень важное приемущество: они не заканчиваются.
          • «меньше, чем люди»
            браво! :)
        • Они тоже устают. Просто у них есть возможность заменить уставшего китайца другим китайцем (=
    • Всегда можно попробовать поставить машину быстрее или попробовать распараллелить. Через год, когда мощности подрастут, распознаваться будет куда быстрее.
      • Полагаю, если отказаться от скриптовых языков в пользу компилируемых, будет ещё быстрее.
    • С N разных ip — это 200*N капч в сутки.
  • ГА без кроссовера — это сильно. В чем отличие от случайного перебора? :)
    • В том, что мутация меняет особь лишь незначительно. Здесь у ГА выполняет только локальную оптимизацию.
      • Перепутал, это уже не случайный перебор получается, а случайное блуждание. В любом случае, ГА точно не причем
        • Механизм отбора-то не случайный.
          • Ну да. Движемся в случайном направлении, а потом отбираем лучшее. В ГА главное — кроссовер, мутации — это дополнительный элемент для борьбы с локальными минимумами
            • Так в природе тоже гермафродиты есть — смысл ГА в естественном отборе в первую очередь :)
              • Верно, смысл генетического алоритма в том что он градиентный, тоесь где лучше получается туда и стремимся и не важно каким способом, мутицией или кроссовером, кроссовер часто излишне усложняет реализацию и не помогает в решении.
                • Да нет, смысл генетического алгоритма в том что он генетический, а градиентный это градиентный. Не надо смешивать понятия.
                  • Генетический алгоритм не градиентен? :)
                    • Суть генетического алгоритма как раз в том, чтоб использовать генетические операции для достижения оптимального результата. В случае использования исключительно мутации это обыкновенный метод перебора. Основная соль ГА в кроссовере и операции выбора родителей для нового потомства. Кроссовер позволяет найти глобальный минимум гораздо быстрее, т.к. используются наиболее приспособленые особи (т.е. наиболее оптимальные) для создания нового поколения и из каждого родителя (их может быть 2 и более) берется только часть. Если из каждого родителя будет взята самая оптимальная его часть, то потомок будет ближе к глобальному минимуму.
                      • Почему только мутиции не генетический алгоритм? Вот в чем смысл генетического алгоритма? — Отбор лучших, более приспособленых, это и отличает от перебора, верно? Почему не подходят ГА только с мутациями? Они ведь реализуют все что нужно: изменение набора генов и отбор особей с лучшим набором.
                        • Если проводить аналогию с биологическими ГА, получается что новое поколение создается исключительно изменением некоторого количества генов, и родитель у него один. Какие-то гермофродиты выходят :)
                          • Да, так и есть. Коммент с которого началось :):
                            «Так в природе тоже гермафродиты есть — смысл ГА в естественном отборе в первую очередь :) „
                            • Согласен. Но гермафродит не есть оптимальный генетический алгоритм :)
                        • И еще, если использовать только мутацию, достаточно всего одного элемента, и его по кругу гонять пока не будет достигнута нужная точность. Нет никакого смысла использовать набор элементов, т.к. новое поколение все равно от него никак не зависит.
                          • Оп, насколько я понял, вот тут то и получается что если один элемент то он уже не генетический :) у нас нет нескольких веток из которых можно выбрать интересное решение :)
                          • Вы забыли про параллельность поиска. С одним элементом вы будуте оптимизировать один локальный экстремум. С популяцией из 100 особей — сразу несколько.
                    • Вы вообще хоть чуть чуть в теме?
                      • да, чуть-чуть в теме :)
            • а пробовали RANSAC с векторными кривыми?
              • что-что?
                • Да, ничего, в принципе. Тот же результат получился бы. Nevermind, поторопился с идеей.
  • Архив с исходниками выложу минут через 30.
    Сначала Яндексу их предложишь? :)
  • Очень интригующе!
  • Я так понимаю смысл капчи в том и заключается — чтобы капчу можно было бы взломать за безопасное для системы время. Точно так же как и в шифровании — если полный перебор занимает необозримо долгое время и нет возможности взломать как-то иначе — то алгоритм шифрования надежен и хорош.
    • Автор повысил вероятность распознавания с 0,0001% до 1%. То есть в 10 000 раз. И это не предел. Думаю, для Яндекса это чувствительно.
  • поломайте вот это:
    ocr-research.org.ua/teabag/0.X.html
    а что человек зазнался, говорит что это практически невозможно :)
    • не пойму, чего минусуете?
      я знаю автора этой капчи, он когда-то мне говорил что она невзламываемая…
      вот я и подумал что автору статьи может быть интересно было бы её сломать. чисто ради спортивного интереса
      • Я минусанул. Сначала попробуйте сами сломать. Чисто ради спортивного интереса.
        • так мне это не интересно, а вот автору статьи, как я понял, возможно будет интересно.
          странная у вас логика…
        • А я вот ломал её. Ради спортивного интереса :)
          img339.imageshack.us/gal.php?g=image5.gif
          Шаг1. Получаем картинку: img339.imageshack.us/img339/4084/image5.gif
          Шаг2. Бинаризируем изображение: img529.imageshack.us/img529/3653/image4x.gif
          Шаг3. Находим острые углы изображения и считаем их углами трансформированного прямоугольника: img111.imageshack.us/img111/74/image3.gif
          Шаг4. Трансформируем искажённый прямоугольник в нормальный: img188.imageshack.us/img188/7950/image1i.gif
          Ну, а это уже можно распознать обычным шаблоном. Это было описано в предыдущем посте по распознаванию капчи.
          P.S. Картинки вставлять в пост не могу, так что извиняйте
          • ух ты. нужно автору капчи отправить
            • Думаю, Колупаеву это уже неинтересно. Да и знает он об этих слабостях
    • Да там и я смогу разгадать только первую. Это не капча — это неуважение к пользователю.
      • соизвольте посмотреть на v1 и 2 они вполне читаемые
        ocr-research.org.ua/teabag/1.X.html
        ocr-research.org.ua/teabag/2.X.html
        • Я не углублялся в дебри данного сайта — мне это не интересно. Просто глянул ссылку которую вы привели и вставил свои пять копеек.
        • Я дошёл до 0.9, и чем больше номер версии, тем хуже читаемость. Выложил бы он случайные слова, а не однотипный «ver 0.x» текст, было бы лучше видно.
          • в версии 1.x картинки генерятся случайно.
            (похоже положили человеку сайт :))
            • Тоже кстати важный момент в создании капч :) Время генерации (и проверки) не должно быть слишком большим )
        • 1.x и 2.x выглядят не очень сложно.
          1.0.1 вообще тривиальная, на 2.0 у них генератора нет.

          Эксперименты в 0.х, увы, по большей части абсолютно нечитаемы.
    • Ага, учитывая, что когда эти капчи появились (первые модификации) — они распознавались файнридером.
      В дальнейшем я как-то раз видел обсуждение как их правильно вычистить, чтобы они распознавались.
    • Мда, версию 2.0 любой, кто знает хоть один алгоритм нахождения линий, сломает. Линии оси Y всегда вертикальны — детекция элементарна и сразу же отбрасываются. (Даже если их сделать не вертикальными — это не спасет, но подсказывать не буду :) )

      Далее отбрасываем все линии что на верхнем конце «вертикальных» линий. Далее остается два направления, направление идущее вверх вправо (cos(вектора(правый конец, левый конец)))>0,sin>0) восстанавливаем как X, другое как Y в плоскости. Используем алгоритм заливки полигонов для закраски. Превращаем в плоскую букву 3x5 пикселей и сравниваем с образцами (даже мутаций никаких не надо… можно даже 3x5 представить как 15 бит -> превратить в short int и сделать lookup таблицу)

      СЛИШКОМ просто.
    • А я вот ломал её. Ради спортивного интереса :)
      img339.imageshack.us/gal.php?g=image5.gif
      Шаг1. Получаем картинку: img339.imageshack.us/img339/4084/image5.gif
      Шаг2. Бинаризируем изображение: img529.imageshack.us/img529/3653/image4x.gif
      Шаг3. Находим острые углы изображения и считаем их углами трансформированного прямоугольника: img111.imageshack.us/img111/74/image3.gif
      Шаг4. Трансформируем искажённый прямоугольник в нормальный: img188.imageshack.us/img188/7950/image1i.gif
      Ну, а это уже можно распознать обычным шаблоном. Это было описано в предыдущем посте по распознаванию капчи.
      P.S. Картинки вставлять в пост не могу, так что извиняйте
      • а не подскажете где можно почитать про Бинаризируем изображение и Находим острые углы изображения и считаем их углами трансформированного прямоугольника

        заранее спасибо
        • Про бинаризацию — в любой книге по обработке изображений. А про нахождение острых углов нигде не написано, но можно и самому написать, здесь всё просто.
    • тоже в ганжаварс играете? )
  • при 1.5% срабатывании алгоритма особенно удобно ломать капчу с ботнета. для яндекса.
  • не выкладывай архив будь умницей
  • Вот сразу видно человек не зря программистом называется и кушает программерский хлеб! Учитесь сноровке школьнеги и студенты!
  • Отлично! :0)
    Единсвтенное, почему-то не упоминаются возможные пути улучшения результата работы алгоритма (уж слишком хорошо буковки вписываются в две синусоиды по снизу и по верху). Думается, если сделать обратную трансформацию, качество распознавания можно улучшить на порядок (по собственному опыту разработки системы распознавания речи).

    Хотя мне кажется, что после этой статейки этому варианту капчи на Яндексе осталось не больше двух недель…
    • Это я просто такой вариант взял для наглядности — линии могут и пересекаться и сливаться в одну даже.
      • Я имел в виду искажения самих цифр.
        Чем четче сигнал вы подаете в нейросеть, тем лучше результаты распознавания.
        Поэтому если можно минимизировать возможные искажения входного сигнала, надо прибегнуть к фильтрации до процедуры распознавания.
        В данном случае, я посмотрел несколько вариантов вывода капчи у Яндекса, и пришел к выводу, что искажение начертания цифр также определяется двумя синусоидами — сверху и снизу. Таким образом, их можно лекго выровнять, если применить обратное преобразование.
        • Я пробовал — нужно же ещё подобрать параметры этого преобразования и как-то оценить его эффективность. В любом случае — если они сделают случайные искажения, мой вариант будет универсальнее.
          • А подобрать параметры преобразования можно на основе уже сделанного вами алгоритма формирования синусоиды: надо подобрать еще две, снизу и сверху. Можно исходить из критерия «минимум точек с одной стороны — максимум с другой». После этого найти оси соответствующих синусоид и произвести «выравнивание» изображений.

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

            Вот сижу сейчас и понимаю что это был бы очень-очень хороший дипломный проект бы… Всучить-бы кому-нибудь на доработку… Причем как раз по приме ;0)
            • Это все правильно, но перестанет работать при незначительной смене алгоритма искажений.

              На диплом, имхо, не тянет. Максимум — курсовая на третьем курсе.
              • Ну да, с дипломом я переборщил.
                А насчет «незначительной смены алгоритма искажений»: все зависит от поставленной задачи. Если задача состоит в том, чтобы «распознать вот такой вот тип капчи у Яндекса», то любая заточка уместна. Незначительная смена — нашим легче, незначительно меняем алгоритм распознавалки.

                Вы же сами остановились на двух синусоидах в начале :0) Это ли не заточка?
                Ведь превратись две черты в логистические кривые, ваш алгоритм уже не заработает. А почему? Потому что задачу «распознать любую наперед заданную капчу» в обозримом будущем не решить. Поэтому и приходится только уповать на то, что новая капча будет из разряда тех, которые мы распознавать умеем.
                • Так у меня есть первый вариант ГА, который не зависит от формы кривой. Хоть он и тормозной немного :)
                  • Угу! :0)
                    Именно поэтому и невозможен на сегодняшний день «универсальный распознаватель капч». Он будет слишком сильно тормознутый, и будет не более полезен на практике чем «сферический конь в вакууме».
                    Суживаем задачу — получаем требуемый результат за приемлемое время.
  • На очереди матановые капчи!
    • это вот это?

      • теперь уже и комменты плагиатят? habrahabr.ru/blogs/infosecurity/63854/#comment_1775336
      • OCR + какой-нибудь MatLab :)
  • Попробуйсе синсоиду находить как кратчайший путь по черным точкам штрафуя за сильное откорнение. Будет работать за XxY шагов
    • Я имею в виду кратчайший в смычле «самый черный» путь от левого до правого края
      • Так первый вариант ГА примерно это и делал — «чернота» с цифрами одинаковая и кротчайший путь тоже через цифры обычно идет.
        • Я какое-то время назад тоже пытался ломать её, но забросил — времени не было. У меня была идея, что «синусоиды» на деле — прямые линии, из которых синусоида получается после искажений. И я пытался произвести трансформацию так, чтобы синусоиды стали прямыми. Пара лет прошла, так что я даже не помню сработала ли идея.
          • Я тоже пробовал — линии от цифр не зависят, накладываются поверх уже после искажений.
          • мне выпрямлять удавалось, линии удалял уже после, правда с тех пор капча могла уже измениться немного
            • да, точно изменилась — раньше линии накладывались перед искажением
  • Завтра в блоге Яндекса будет пост «Мы сменили капчу».
    • Или "@#$%, мы сменили капчу".
  • Можно начать обучать сеть на распознавание цельных образов, без предварительной обработки. Интересно, сколько времени займёт обучение, если задаться выходом в 1% распознавания ЛЮБОЙ капчи?
    • Очень много. Там скорость обучения экспоненциально зависит от количества входных нейронов.
  • Восемь-десять секунд на одну каптчу при вероятности распознавания в 1,5% — это примерно 5-7 штук в час, не слишком много.
    • Читайте внимательнее — довести даже до 50-80% можно простым увеличением базы образцов. Но я больше китайцем работать не хочу :)
      • Так 50-80% — это вероятность распознавания одной цифры или всей каптчи?
        • Довести можно до 50-80% всей каптчи.
      • надо вам помочь :)
    • Легче нанять леммингов на kolotibablo.com, которые будут разгадывать капчи за доли цента.
  • дельные мысли. не суть в 1,5% Главное, что автор верно и логично мыслит!
  • «Узнал расценки китайской фермы по вводу captcha. 1000 капч — 0.8 цента. Вы думаете кто-то использует алгоритмы для взлома? Зачем?»
    twitter.com/bobuk/status/2649880690
    • Они и используют! :)
    • ac-servise(ранее anti-captcha) для покупателей и kolotibablo для самих индусов.
    • Полагаю, имелось в виду все же 0.8 доллара, а не цента.
  • Давно интересовался, как же конкретно выглядит код антикаптчи.
    Примерно такого и ожидал :)
  • теперь яндекс может поцеловать блестящий зад бендера(:
  • В итоге бОльшая часть времени на распознавание потратилось на убирание синусов с помощью ГА.
    …
    • Да, но его тоже можно допилить до 1-2 секунд. Ещё нужно учитывать, что скрипт выполняется на одном ядре, т.е. параллельно на сервере с 4-8 ядрами будет быстрее дело идти…
  • интересно, сменят ли и когда теперь эту капчу?
    • Маловероятно.
      Любая каптча разгадываема, это вопрос времени и ресурсов.
      Как выше справедливо отметили, дешевле покупать разгаданные капчи за копейки, чем прогружать компьютеры.
  • а если просто создать «свою» капчу как у яндекса и сравнивать с исходной?
    тем бололее преобразования там несильнозамутнённые
    натаскать ту же нейронную
    • Можно, но на это тоже время уйдет — параметры искажений придется опытным путем подбирать.
  • Супер. Статья понравилась
  • Увы, чтобы достоверно отличить человека и бота при нынешних технологиях, пока ещё нужен человек
    =)
  • Спасибо, хорошая зарядка для мозга.

    А вот мои любимые:


    и от mail.ru:
    • Последнее напоминает сюжет «Кода да Винчи».
      • Или теста на IQ.
        • Хорошая идея кстати. Надо на хабре прикрутить обязательное прохождение теста на IQ при регистрации с расчетом проходного бала.
    • это чтобы люди не регистрировались наверное… неуважение это.
    • По сути эта каптча mail`а не отличается от других, здесь тоже нужно вводить образцы.
      Просто вместо цифр и букв здесь иероглифы. А у кого они на клавиатуре есть!? :) Только у НЛО.
      Поэтому и выводится блок с этими иероглифами, а докучи они перемешиваются %)
      Что в некоторой степени усложняет распознавание
    • В первых двух капчах вероятность правильного угадывания равна 1/N, где N — количество вариантов в выпадающем списке. Допустим, что там 5 ответов. 20% — отличный вариант для спаммеров (сравните с 1,5% в примере с яндексовской капчей)
    • Астральная капча с Блаватской — это просто невообразимо круто!
  • Я однажды покупал программу для iPhone (тогда еще не было apple store), она была на английском, а сайт на китайском. Так вот я сидел с Google translate переводил по шагам оплату, и когда уже ввел номер карты и все такое, мне выдали что оплата произведена и все что мне теперь надо — ввести емейл для получения серийника и капчу… на китайском…
    Пришлось искать в инете сервисы рисования иероглифов от руки, куда я 3 часа тщательно перерисовывал искаженные(!) иероглифы с капчи, копировал подходящий юникод и вставлял в поле ввода.
    Когда наконец я осилил 6 этих символов, мне сказали «извини, таймаут». И по новой…
    К 4му разу я, кажется, уже выучил китайский.
    • Респект! Я вспоминаю как я на денди изучал, что значат конкретные японские иероглифы в играх (особенно было актуально, когда типа кода для респавна выдавали) ^_^ От это был кавай, не то, что щас!
    • Это похоже на переписывание от руки синего экрана смерти винды =)
  • отличная статья. очень было интересно прочитать (8
  • честно скажу — думал такое сделать будет сложнее.
    Собственно думаю мою капчу если захотят поломают за 1 вечер =)))
    Нада придумать какой та способ защиты без капчи.
    • Есть такие, например скрытые для человека поля/чек-боксы, но видимые для бота
  • отличная статья! :)
    ждём новых постов по взлому каптч ;)
  • Отличная статья, спасибо.
    Правда если яндекс синусоиду поменяет на случайную кривую — все замедлится в разы.
    И еще мне кажется подавать в нейросеть вещественные числа для пикселей с 4-мя оттенками серого не экономично, можно в 8-16 раз уменьшить объем входных данных.
  • раскрыть комментарий
    • Вероятность возникновения нескольких независимых событий равно произведению их вероятностей.
      • бинго! :)

        это отличное, но неприменимое здесь правило
        • Учитывая, что цифры распознаются независимо, то это как раз то, что нужно.
          У вас есть 6 событий распознания, каждое с двумя исходами: распознано — нераспознано.
          Вероятность исхода «распознано» — 0.5
          Вероятность 6ти исходов «распознано» = 0.5 х 0.5 х 0.5 х 0.5 х 0.5 х 0.5 = 0.015
        • Купите учебник по терверам что ли :)
          • событие «распознавание капчи» не равно событию «6 цифр распознаны верно»
            прочитайте учебник, что ли :)
            • Ну, я не знаю, что оно для вас значит, но для меня «распознавание каптчи» — это когда верно определены все 6 цифр.
          • … если совсем точно, не равно вероятности наступления шести независимых событий.

            а равно как раз минимальной вероятности из набора событий. ибо если одно событие не наступило, то остальные события значения не имеют, и капча распознана не будет
            • ибо если одно событие не наступило, то остальные события значения не имеют

              Произведение вероятностей как раз это и учитывает — она отражает _одновременное_ возникновение _всех_ событий.
              • они не одновременные. вы их сами разделили, разрезав капчу.
                событие «выпадение орлов на всех десяти монетах» не равно событию «открытие сейфового замка из десяти цифр». которое, кстати, не равно событию «верная капча»

                но спор скучен
                • они не одновременные. вы их сами разделили, разрезав капчу.

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

                  событие «выпадение орлов на всех десяти монетах» не равно событию «открытие сейфового замка из десяти цифр»

                  Если у замка только цифры 1 и 0 — то равно. У нас же 50% вероятность угадать каждую цифру. Можете считать, что у нас только цифры 0 и 1 есть.

                  • тебе не только капчу разгадывать, но и тервер преподавать надо:)
      • А вот тут я хочу заметить про независимость. Если совсем уж строго, то события эти не совсем независимы. Меня смутил момент «Разделяем изображение на 6 равных частей». По ощущениям, кусок буквы может залезть в чужое «окошко». А это сделает две соседние буквы не независимыми.
        • В каком-то конкретном случае может быть, при многократных повторениях — уже не важно.
    • Писец… Вот к чему приводит прогуливание школы и засиживание в интернете…
      Так, выключай компьютер и срочно делать уроки!
      • раскрыть комментарий
        • Хорошо. Зато комбинаторику в нормальных школах преподают. Ну или возведение в степень (это уже во всех школах).

          У нас есть 6 чисел. У нас равновероятны события, угадали мы цифру или нет. Пусть 1 — угадали, 0 — не угадали. Какие у нас события для всей капчи?
          000000 — все 6 не угадали
          000001 — угадали тоолько последнюю
          000010 — угадали только предпоследнюю
          000011 — угадали 2 последние
          …
          (ничего не напоминает?)
          …
          111110 — угадали только первые 5 цифр
          111111 — угадали все 6 цифр.

          Под понятие «правильного распознавания каптчи» попадает только последний случай. Хочется обратить внимание на то, что все случаи равновероятны. Всего возможных событий 2^6 (IT мы или не IT???) = 64. Тогда вероятность «правильного распознавания каптчи» = 1/64 = 0.015625. Бинго!

          P.S. Как Хабрасообщество понимает этот комментарий не для habraname, а для тех школьников, которые попытаются его послушать.

          P.P.S. 0.015625 скорее 1,6% ;)
    • т-с-с-с. Пока не набежали.

      Здесь рассчитывается вероятность события «все 6 цифр распознаны верно» — только тогда значение каптчи удастся ввести.

      Минимальная вероятность из набора (0.5) здесь cовсем не при чём ;)
      • я же говорю про событие «распознавание капчи» :) которое и будет…

        но, т-с-с-с!
        • и как спорит, и как спорит =)
          • люблю хороший правильный диалог :) пока он не уныл
            а холивары не люблю

            но ведь как минусуют, как минусуют! ;)
  • в рекапче значимо только первое слово, второе можно писать от балды.
  • Возникла пара предположений по прочитанным комментариям и статье.

    1) Есть предположение, что большее число нейронов на внутреннем слое (или нескольких) заработает, причем лучше, если увеличить количество образцов.

    2) Есть подозрение. что если не просто замазывать синусоиды белым, а сохранять их там, где проходит линия под большими углами (близко к 90), то контуры букв лучше сохранятся, что сделает их лучше распознаваемыми.

    3) Очень интересна была бы статистика по тому, какие цифры лучше распознаются, а какие хуже. У меня, например, обычно проблемы с 1 и 7 (при человеческом распознавании :) )
    • 1) Есть предположение, что большее число нейронов на внутреннем слое (или нескольких) заработает, причем лучше, если увеличить количество образцов.

      Заработает, согласен. Я и так увеличивал немного, когда образцы добавлял.

      2) Есть подозрение. что если не просто замазывать синусоиды белым, а сохранять их там, где проходит линия под большими углами (близко к 90), то контуры букв лучше сохранятся, что сделает их лучше распознаваемыми.

      На общее количество «полезных» пикселей это не сильно повлияет. Хотя, конечно, немного получше будет.

      3) Очень интересна была бы статистика по тому, какие цифры лучше распознаются, а какие хуже. У меня, например, обычно проблемы с 1 и 7 (при человеческом распознавании :) )

      Для нормальной статистики нужна большая тестовая выборка. А так да, 1 и 7 и 3 и 5 путаются чаще всенго.
      • Вообще интересней подробнее почитать о параметрах нейросети. Мне кажется, 150 нейронов это даже черезчур, скажем, для радиально-базисной сети. А кохоненовская карта, по идее, на 150 нейронах должна бы давать куда лучшие результаты, хоть и значительно медленнее. Так какая сеть?
        • Обычный feedforward, три слоя: 600, 150 и 10 нейронов. Думаю, любая другая сеть на таком количестве образцов себя бы лучше не показала.
  • Никто не сломал капчу, потому что это не нужно. Чтобы яндекс не просил ее вводить, достаточно в user-agent добавить YB/3.5.4.0
    • Каптча нужна спамерам. Бот регистрирует ящик и с Яндекса шлет письма.
  • Расскажите поподробнее про нейронные сети лучше!)
    • Так про них и так столько всего написано…
  • Спасибо. Статья интересная. Больше применений ИИ, хороших и разных :)

    Небльшое дополнение. Чтобы модуль php для работы с fann встал нормально, мне пришлось собирать fann 2.0 из исходников (я про linux-окружение), т.е. качаем 2.0, распаковываем, заходим в папку, делаем ./configure, make, make install.
    После этого делаем pear install pecl.php.net/get/fann, и — вуаля — модуль поддержки fann для php установился.
    А вот с версией 1.2.0 мне подружить php-расширение не удалось. Что-то у них там напутано с путями установки по умолчанию.
    • Чтобы с 1.2.0 подружить надо скачать пакет fann-0.1.1.tgz в нем в файле php_fann.h закомментировать 28-ю строку (#define PHP_FANN_OO 1) и потом pear install путь_к_пакету.
      • А есть какие-нибудь существенные преимущества у 1.2 по сравнению с 2.0?
        Кстати, куда после make install кладется .so-шник? А то по dl('fann.so') не находит, собака.
      • И еще, следом:
        как вы боролись с
        /root/tmp/pear/cache/fann-0.1.1/fann.c:493: warning: assignment makes pointer from integer without a cast
        ?
        • т.е. не с самим варнингом, а с следующим за ним отказом мейка:
          make: *** [fann.lo] Error 1
          ?
      • Так, разобрался, биндинг к php вообще с 2.0 не собирается (и не должен, похоже), ясно.
        Все собралось, но теперь при попытке сделать fann_create php молча вылетает.
        У вас такого не было?
        • Было из-за неправильных параметров. Если fann_create из моего примера — проверьте есть ли доступ к файлу. Показывает ли phpinfo(); что fann включен?
          • А какая комбинация параметров приводит к вылету?
            fann_create из доков к php-биндингу.

            $ann = fann_create(array(2, 4, 1), 1.0, 0.7);

            phpinfo():

            fann
            Fast Artificial Neural Network (FANN) library support — enabled
            FANN object oriented API — disabled
            • Например, fann_create('ann.data'); и нету доступа на чтение ann.data — вылетит.
              • Разобрался. У меня в системе остались куски fann 2.0, с которой я экспериментировал. Очистка всего, что связано с fann, и пересборка правильных версий либы и биндинга решила проблему.

                В любом случае, спасибо за помощь.

                Резюме по установке fann+php (для linux систем):

                — с php нормально работает только версии 1.2.x
                — ставить нужно так:

                wget prdownloads.sourceforge.net/fann/fann-1.2.1.zip?download
                unzip fann-1.2.1.zip
                cd fann-1.2.1
                ./configure
                make
                make install
                cd…
                wget pecl.php.net/get/fann
                tar -xzf fann
                cd fann-0.1.1

                вот здесь мы правим любимым редактором файл php_fann.h (как уже говорилось выше, комментируем 28-ю строку)

                phpize && ./configure && make && make install

                все. после этого должно работать.
                • парсер слегка подпортил команды.
                  cd… = cd пробел дветочки
                  и во всех адресах в начале пишем http: / / без пробелов
  • Скучаю по генетическим алгоритмам и нейронным сетям.
    7 лет назад по этим темам курсовые писал.

    Спасибо и успехов.
  • Спасибо за статью! Было очень интересно почитать анализ нашей капчи.
    Конечно, сейчас мы меняем кое-что для того, чтобы затруднить работу этих скриптов.
    Добавлю, что защита не состоит только из капчи. Для спамеров есть и другие неприятные сюрпризы :)
    Олег Охотников.
  • А почему бы не заставить яндекс выступать в роли учителя. Если записывать угаданные каптчи, то вероятность отгадывания увеличится?
    • Я тоже об этом думал, но Яндекс, скорее всего, после некоторого числа попыток забанит мой IP.
  • Можете картинки перезалить?
    • А что с ними не так?
      • 403 Forbidden

        Захожу отсюда:
        serial0-0-0.otwaonnhd1-rtr1.nyroc.rr.com [24.92.224.14]
        • Попробовал с разных IP — все отображается.
          • Соглашусь с комментатором — не отображается.
            • Перезалил.
              • Всё заработало. Пасиб.
Только авторизованные пользователи могут оставлять комментарии. Авторизуйтесь, пожалуйста.