Пользователь
0,0
рейтинг
27 августа 2014 в 20:05

Разработка → Естественный отбор — враг бота

Интересный баг только что отловили. Рассказываю.

Имеем сервис с капчами. Чтобы уменьшить время отклика логично генерировать картинки по случайному коду в свободное время в час наименьшей нагрузки. Так и делаем — ставим в крон задачку, делаем 100500 капч (картинка + код в базе) и в течение дня их показываем. На тот случай если прегенерированные капчи все-же закончатся, делаем режим аварийного полета — если отгаданная и, в связи с этим, убираемая из базы капча уменьшает общее число капч до опасного уровня (например, остается меньше 50), то генерируем новую капчу вместо убранной.

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

Посыпались жалобы что капчу невозможно разгадать. Жалобы начинали поступать исключительно после 19:00 когда все разработчики уже закрывают IDE и запускают доту. Причем, при условии правильной реализации случайной генерации капч (проверили первым делом) в конце дня все (ну или почти все) капчи стали заканчиваться на D.

Оказалось, что происходит следующее: капчи кончаются. Но, поскольку мы не убираем из базы показанные, но не разгаданные капчи, то среди прегенерированных капч начинает работать естественный отбор и к концу дня мы имеем 50 самых злых и сложных капч в мире. Дальнейшее развитие ситуации, когда взамен разгаданной капчи мы добавляем случайную — не сильно улучшает дело. Попутно мы выяснили что самая потенциально неразгадываемая буква в капчах — D, потому что при достаточной степени искажения треть юзеров интерпретирует ее как D, треть как 0 (ноль) и треть как О. А еще 46% вводят русской буквой.

Вот он, естественный отбор в действии!
Андрей Малышев @k41n
карма
16,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (70)

  • 0
    Как в итоге исправили?
    • +3
      Сделали флажок «капча показана» и вешаем его при показе. Даже если юзер не разгадал капчу, плюнул и ушел — эту капчу уже никто не увидит. Плюс, добавили объем основного буфера, который нарабатывается ночью. Заодно с его генерацией чистим показанные, но не отгаданные капчи из базы.
  • +3
    Зачем убирать отгаданные капчи?
    • +3
      Чтобы нельзя было разгадав большую часть пула руками или через антигейт сделать бота который проходит капчу с вероятностью пропорциональной отгаданной части пула.
      • +3
        Не совсем понятно почему такая вероятность будет значимой, ведь раз вы это дело оптимизируете — значит у вас большая посещаемость и большой пул ( 100500 обычно символизирует большое количество ). К тому же у вас они и так каждый день генерятся.
        Просто при вашем подходе как не оптимизируй — к концу дня буду все равно самые сложные капчи, а значит пользователям будет нехорошо.
        • +2
          Дело в том, что, если не убирать капчу то можно даже тупо перебором или через автораспознавалку без оптимизации наугадывать столько капч, что это станет вероятностно значимым. А чтобы пользователям не было плохо — надо убирать не только успешно распознанные капчи, но и нераспознанные. Тогда вероятность того что капча доживет до вечера не будет зависеть от ее сложности. Именно так сейчас работает, завтра посмотрим…
          • 0
            Просто при количестве капч к примеру в 100к оно уже кажется не особо экономически целесообразным для спамера.
            Но я не знаю практических особенностей вашего проекта.
            • +2
              Боимся не спамера, боимся бота, который автоматизировав некоторые операции может осуществлять ресурсоемкие операции пачками. У нас сервера потекут, а злоумышленник будет держать DDoS злобно хохоча.
      • +3
        Собственно логично было бы удалять как отгаданные так и не отгаданные. В любом случае у вас же есть механизм генерации дополнительных в случае если капч осталось мало.
        • 0
          +1. Так и сделали сейчас. Только из-за того, что юзер не отгадавший капчу может в этом не сознаться, а просто уйти, мы удаляем (точнее помечаем) капчи как показанные при показе. Показанные больше не будут показаны.
      • 0
        Можно сделать следующую схему: отгаданная капча не убирается до тех пор, пока не запускается генерация новых капч. В процессе генерации старые капчи (отгаданные и просто просмотренные) удаляются и заменяются новыми. Таким образом допускается повторное появление капчи в течении дня, и при этом гарантировано не придется днем генерировать новые капчи. Зато ночью все использованные капчи удалятся.
        • 0
          И, кстати, эта схема решит проблему с просмотром капчей ботом, которая ниже упоминается.
  • +18
    Символы D, O, o, 0 в капче это зло! Будьте благоразумны, уберите их
    • +1
      Уже
      • +12
        Еще зло — 1, i, I, j, J, тоже убрали.
        • +10
          Имхо не убирать их надо, а считать одинаковым символом…
          • 0
            Это уже высший пилотаж, не для вечернего хотфикса :) А если серьезно — то не могу сказать навскидку как лучше. Учитывать надо то требование, что сложность для нелюдей должна быть как можно более высока.
            • +2
              Соединение разных букв в одну группу однозначно упрощает подбор. Убрать лучше.
              • 0
                Уменьшение ассортимента — лучше?
            • +2
              <теорвер>
              [A_Za_z0_9] -> шанс 1/62.
              [A_Za_z0_9] без [1, i, I, j, J, l], перебор без [1, i, I, j, J, l], [D, O, o, 0] -> Шанс 1/52.
              [A_Za_z0_9] без [1, i, I, j, J, l], перебор с [1, i, I, j, J, l], [D, O, o, 0] -> Шанс 1/((52/62*1/62) = 1/73.92
              [A_Za_z0_9], где [1, i, I, j, J, l] = [I'], [D, O, o, 0] = [0'] -> Шанс:
              1/P = (6/62*6/62) + (4/62*4/62) + (52/62*1/62) = 0.02705515088
              P = 1/36.96
              [A_Za_z0_9], где [1, i, I, j, J, l] = [I'], [D, O, o, 0] = [0'], Шанс появления символа из первой группы меньше в 6 раз, из второй — в 4 раза -> Шанс:
              1/P = (1/62*6/62) + (1/62*4/62) + (60/62*1/62) = 0.01821019771
              P = 1/54.91

              </теорвер>

              Итого:
              1) Оставить как есть: 1/62
              2) Убрать 10 символов, перебор без них: 1/52
              3) Убрать 10 символов, перебор с ними: 1/73.92
              4) Объединить: 1/36.96
              5) Объединить и подправить вероятность выпадения сгруппированных символов: 1/54.91

              1 вариант — исходный. Имеем проблемы с похожими символами.
              2 вариант — очевидное решение проблемы.
              3 вариант серьезно рассматривать нельзя — рано или поздно заметят, что 10 символов не падает вообще.
              На 4 мы очень сильно проседаем по сложности.
              5 вариант: и решаем задачу с похожестью, и чуть выше сложность относительно скучного 2.

              Как-то так.
              PS
              Шанс везде для капчи из одной буквы и идеальной случайной генерации/подбора.
              Возведение в степень длины капчи никто не отменял.
              • 0
                Кхм… кажется вы не поняли мою идею:
                — упростим жизнь пользователям и посчитаем это за один символ (хотя тут нужно ещё смотреть, какие считать за один, какие — нет… но как минимум 0 и О должны считаться синонимами, да и прочие подобные — тоже),
                — в матрицу генерации добавим любой один символ из синонимичных — т.е. увеличим базовый набор
                Т.е. например [A-Za-z0-9] без [O], с учётом того, что пользовательский ввод O даст нам при проверке 0.

                Думаю в этом случае мы избежим рассчитанную вами проблему с синонимами.
                • 0
                  Это как раз 5 вариант. Почти.
                  Давайте возьмем [A-Za-z0-9] без [O], и O будет давать 0.
                  А теперь давайте посмотрим, что получится, если вместо 0 в капче в половине случаев выводить нолик чуть потолще? Скажем, О? Введенные пользователем О и 0 все так же будут давать правильный ответ, с точки зрения вероятностей у нас совершенно ничего не изменилось. Просто визуально у нас появляется толстый нолик или тонкий нолик.
                  А теперь пойдем другим путем. Не будем убирать из кассы О, но порежем вероятность выпадения О и 0 в два раза. Введенные О и 0 все так же отвечают верно на любой из них.
                  Что мы имеем? У нас совершенно так же часто, как и любая другая буква, выпадает [О или 0]. Толстый нолик и тонкий нолик.
                  Другими словами, наши с вами варианты совершенно эквивалентны, просто в моем в капче у нолика периодически меняется форма. Но это все равно ни на что не влияет, потому что в капче у всего меняется форма — на то она и капча.

                  У меня, кстати, ошибка в расчетах в пятом варианте.
                  1 / p (1/54*6/62) + (1/54*4/62) + (52/54*1/62) = 0.0185185185
                  p = 1 / 54
                  Что, черт подери, равноценно извлечению 8 символов из кассы и перебора.
                  • 0
                    Ну в общем-то и идея в том, чтобы минимизировать извлечение символов из кассы — как вы заметили в такой ситуации мы выбрасываем не 10 а 8 символов, что в общем случае снижает потери сложности.

                    С другой стороны, нужно вообще задуматься, что такое капча: средство для усложнения НСД. Тогда и думать нужно не только/столько о шансе автоматического подбора (если картинка уникальна — то и подбор тут по сути не поможет), сколько о сложности распознания ботом, не забывая о сложности распознания человеком. В идеале — человек должен распознавать с полпинка, бот — только ну очень качественный (там стоимость бота и его работы сильно снижает риски).
                    Продолжение рассуждения... но не в ту степь
                    Но вот тут и начинаются проблемы — алгоритмы распознания постоянно улучшаются как и сложность капчей, из-за чего через некоторое время капчи станут защитой не от ботов, а от людей.
                    Таким образом в идеале как раз таки нужно использовать относительно похожие символы для того, чтобы спутать бота, но при этом есть потребность, чтобы и человек её по прежнему распознавал. В такой ситуации синонимы снижают безопасность сильнее, чем их отсутствие. Но и обличают при этом ввод человека. Поэтому над набором символов, шрифтов и преобразований надо думать, при этом опираясь не только на голую математику.

                    Фух… Надеюсь более-менее понятно выразился.
                    • 0
                      Я рассматривал вопрос исключительно с допущением, что перебор капчи идет случайным образом. Естественно, при подборе путем машинного распознавания нужно работать уже не инструментами теорвера — ну, как минимум не только ими.
                      Я был просто рад отвлечься на любопытную математическую задачку и пообщаться с умным человеком — на звание эксперта по капчам не претендую ни в раз.
                      • 0
                        Ну тут я просто заострил внимание, что с капчами всё хитрей, поэтому одной математикой не обойтись. В целом я и сам не эксперт, но несколько раз погружался в вопрос поглубже.

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

                        С тех пор появилось:
                        — появились механизмы генерации / исключения из списка капчей (повторно воспользоваться угаданной невозможно)
                        — появились различные графические преобразования (мешают распознанию простыми алгоритмами, но, как уже писал, алгоритмы на месте не стоят и скоро человеку будет капчу сложней отгадать, чем компьютеру)
                        — появились «хитрые»/тематические капчи (например «посчитайте сколько будет» и какой-нибудь простой математический пример на картинке)
                        — …
  • +90
  • +24
    Покажите пример самых злых капч, прошедших естественный отбор! Заингтригован
    • +6
      Присоединяюсь к просьбе. Давайте сделаем эту ветку комментариев длинной и автор её заметит.
    • +3
      С прода потерли уже, но всегда есть письма благодарных пользователей, в которых они обогащают наш лексикон! Во всех случаях капча в поле ввода — неправильная.

      image

      image

      image
      • 0
        o_O а разгадки?
        • +1
          UAD

          IUJ

          А третью перепутал, вот что хотел еще выложить:

          image

          Отгадка — VHD
          • 0
            А я бы подумал, что VXD
        • 0
          UAD, IUJ. Наверное…

          (Не обновил комменты, прежде чем отправлять. Уже ответили).
        • +1
          а разгадка одна — безблагодатность
      • +2
        Картинки поломались.
        • +5






          Перезалил на хабрасторадж
          • 0
            Прекрасно :) :). Спасибо!

            Вообще замечательная история :).
      • 0
        Deleted.
  • 0
    46% русской Д чтоль?
    Если так, то таких точно нельзя пускать на сайт
    • +1
      Нет, русской О в комбинации с двумя латинскими буквами. Не лень же переключать раскладку!
      • 0
        Видимо это после того, как латинскую O попробовали уже.
        • 0
          Можно несколько раз пробовать разгадать одну и ту же капчу?
          • 0
            Нет, но D встречается в 90% капч, которые доживают до конца дня. Точнее так было до сегодняшнего дня.
            • +11
              Пытаюсь представить мысли 46% пользователей:
              «Эту круглую хренотень уже видел — не ноль, не О… Может — русская?» :)
  • +1
    Странно, вы каждый день ожидаете «режим аварийного полета»? Почему тогда не генерируете больше капчей?
    • 0
      День на день не приходится. Давным-давно один раз сделали и забыли на год. Режим аварийного полета сделали для дней адского наплыва пользователей. А сейчас популярности прибавилось и цифра которая тогда казалась достижимой только в экстраординарной ситуации стала ежедневной нормой. Прибавили конечно сейчас, когда пришлось опять к этому обратиться
      • 0
        Получается, если уровень становится опасным и резко зайдет 50 посетителей и капчи не успеют перегенерироваться — они просто закончатся?
        • +2
          Тогда случится страшное — юзеру придется ждать пока его капча сгенерируется. +200-300мс. Ощутимо.
          • 0
            А, т.е. в опасной ситуации генерируется не по крону, а в рантайме? Ну придется ждать ведь каждому следующему юзеру до глобальной генерации капч? История, конечно, у вас получилась интересная (можно целый сервис придумать для сложных капч :-), но не понятно почему не генерировать кроном, когда число до половины доходит, например, а не просто на каждый день?
            • 0
              Решили так не делать. Непонятно что будет если в час наибольшей нагрузки число капч опустится до уровня 50% и начнется регенерация (а это вставки в базу, что есть дорого). Генерация «на лету» по крайней мере пропорциональна нагрузке, а крон отожрет все что сможет и сделать ему приоритет пониже не факт что получится — проблема не только в процессоре, но, главным образом, в базе.
              • 0
                Ну генерировать то не сразу все 50%, просто пачками. Но мне непонятно откуда берется такая нагрузка на базу? Вы картинки туда сохраняете?
                • 0
                  Нет, картинки на винт. А генерировать пачками можно, но лениво. Код получается сложнее наверное, хотя может и нет. Не пробовали потому что забоялись что все уснет.
  • +1
    Если изначально вы не удаляли и никак не помечали показанные капчи, то как вы боролись с ситуацией, когда одна капча показывается двум пользователям, зашедшим приблизительно одновременно? Для пользователя который нажмет «отправить» вторым она окажется невалидной, потому что была удалена после того как ее отправил первый пользователь. Конечно при большем количестве капч это маловероятно, но при 50 очень даже возможно.

    По-моему это очевидно, что удалять капчи нужно после показа независимо разгадана она или нет.
    • 0
      Согласен на 100%. Проблема то в том, что если она не разгадана, то не так-то просто это понять. Юзер (а тем более бот) вместо сабмита сомнительной капчи может уйти или запросить новую. Касаемо ситуации одновременных юзеров — скорее всего такое бывало, и не раз. Но бывало довольно редко и обновление страницы помогало, поэтому юзеры не жаловались. А сейчас все хуже было — у всех и обновление не помогает.
      • 0
        Вот кстати. Теперь боту достаточно будет быстро просматривать все ваши 100500 капч. КапДОС эдакий.
        О! Ниже ответ уже есть, пардон.
  • +2
    Если вы боитесь DDoS, то почему не боитесь что бот(ботнет) зайдет и будет запрашивать капчу, таким образом исчерпает ваш лимит, заставит сервер трудиться над генерацией кучи капч, попутно забивая мусором разделы? Я не знаю архитектуры вашего проекта, но мне кажется борясь с одной проблемой вы ее же и создаете только немного в другой реализации.
    • 0
      Генерация капчи плохая но не самая ресурсоемкая задача, которую вражеский бот может запустить. Пусть уж лучше капчи генерирует, то что ими защищено — куда тяжелее.
      • 0
        Ну, собственно, d3.ru одно время лежал именно из-за генерации капчи для ботов. Хотя не знаю нагрузки на ваш проект.
  • –5
    На 16 строчек текста 15 повторений слова «капча» в той или иной форме))
    • +22
      На одну строчку текста 12 пробелов, 5 букв «а» и 7 букв «о».
    • 0
      Так потому, что текст о капче как раз. И синонимов у этого слова не особо.
      • +1
        Думается мне, люди, разгадывая капчи, придумали очень много синонимов для этого слова, некоторые даже можно употреблять в приличном обществе.
  • 0
    А разве нельзя сделать таблицу символов, чтобы и D и 0 и O воспринимались, как правильная буква?
    Можно не сразу, а, например, если капча оказалась не отгаданной — добавляем ещё правильных вариантов в базу на основе таких подстановок. Соответственно, если она снова выпадет в следующий раз — бот будет уже более толерантен к «умеренно неправильным» ответам.
  • 0
    А можно где-то посмотреть самые «злые» ваши капчи? Просто интересно! Спасибо!
    • +1
      • 0
        Спасибо! Когда смотрел не отобразились картинки в коментарии и не заметил.
  • 0
    Вам можно было написать перед капчей «The 'D' is silent»
    • 0
      Silence of the D's
  • +1
    По иронии прочитал тайтл как «Естественный отбор — враг боГа».
  • 0
    Hадо из генератора вообще убрать такие символы как D-O-0, 1-I, v-U
    или настроить искажение так, чтоб человеку можно было что-то разобрать…
    если я не разгадываю капчу со 2-го раза (на некоторых я не мог разгадать даже с 7-го, а иногда даже прошу совета у жены) — я просто ухожу с сайта.

    Есть много достойных текстовых замен или двигать ползунки или крутить ручки.

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