Из этой статьи читатель узнает о том, как написать робота, проходящего тесты, и немножко «разомнет мозги» в теории вероятностей, разбираясь вместе с автором, почему при кажущейся сложности задачи автоматический подбор решения сходится за очень короткое время. Предупреждение: половина статьи ― «матан».
Введение
Несколько лет назад я сделал тест для программистов, который многим, скорее всего, не понравится. Если вы пишете на языке PHP, ваша любимая СУБД ― MySQL, а в качестве операционной системы вы предпочитаете Linux ― попробуйте его пройти. Заранее предупреждаю, тест своеобразный. Успешно его проходит всего несколько процентов испытуемых. Так что не стоит переживать. Если вы его не пройдете ― ничего страшного. Тест «заточен» под определенные навыки, которые требуются далеко не везде.
Получить отличный результат в тесте сложно. Поэтому некоторые испытуемые прибегают к черной магии ― пишут бота. Хорошее дело, между прочим. «Настойчивость и храбрость, отвага и удача, в беде не растеряться ― вот главная задача!» Поэтому капчи в тесте не было. Никогда. Наоборот, мне хотелось, чтобы ботов писали. Чтобы боты приходили. Чтобы тест выстоял, боты обломались, а «ботописатели» не жульничали, а учились.
В тесте 80 вопросов, из которых для каждого испытания случайным образом выбирается 25. У меня был простой (и, как потом выяснилось, абсолютно неверный) расчет. Чтобы тест нельзя было пройти, заучив или подобрав ответы, общая база вопросов изначально должна быть существенно больше, чем количество вопросов в одном испытании. Общее количество комбинаций тестов составляет число порядка 1020. «Раз число такое большое, значит, и подобрать ответы будет очень сложно», ― думал я. Конечно, число сочетаний ― очень грубая оценка. Но задача автоматического подбора интуитивно казалась мне если и решаемой, то такими затратами, на которые ботописатель не пойдет. Думать так было большой ошибкой. Битву с ботами я проиграл. Дальше расскажу, почему.
Атаки
Всех атак, конечно, сейчас и не вспомнить. Успешных было две ― о них и пойдет речь.
Первый успешный подбор был тривиальным (не считая миллиона http-запросов, но это мелочи). Подбор стал результатом моей глупой ошибки. Его осуществил мой знакомый, Игорь Ш. Однажды я увидел его фамилию на первом месте в рейтинге. С очень высоким баллом и временем прохождения теста в районе 5 секунд. Я позвонил ему и спросил, как он это сделал.
Сначала Игорь попробовал решать задачу подбором. Как я уже написал, парень он оказался весьма упорный, в логах было около миллиона запросов. Но задача была сложнее, чем казалась вначале ― подбирать было слишком долго. И вдруг нашлась «дырка». Оказалось, что можно передавать заведомо неверный ответ, который будет принят и засчитан как неверный, а тест перейдет к следующему вопросу. Это позволяет подбирать ответ на конкретный вопрос, отвечая на все остальные заведомо неверно. Множество вариантов для перебора становится ничтожным, а задача ― элементарной.
Бот Игоря был первым, кто прошел тест. Баг я исправил, Игоря из рейтинга пришлось удалить. Все остальные атаки успешностью не отличались. Прошло несколько скучных лет, пока не появился Семен К.
Это была вторая и последняя серьезная атака, после которой я всё про себя понял и поставил капчу. К тому же это была отличная разминка для , сподвигнувшая меня и на этот пост. Но обо всём по порядку.
В середине ноября 2013 года с какого-то швейцарского хостера прилетели двести пятьдесят тысяч запросов. Уже на второй день бот красовался в рейтинге на первых местах и продолжал дальше. 250 000 запросов, примерно 10 000 прохождений теста ― и на первом месте. Это меня совершенно смутило. Почему так быстро? Какое там число сочетаний, какие 1020, подбор сошелся значительно быстрее! Неужели опять какой-то баг? Если нет, то как я мог так ошибиться в оценке?
Бот оставлял электронный адрес автора, и мне ничего не оставалось делать, как признать поражение и написать автору письмо. В течение следующего дня я выяснил, как работал бот.
Никаких дырок он не использовал, а работал адаптивно: на основе результатов уточнял гипотезы о верности варианта ответа, отбрасывал наихудшие, постоянно уточняя решения и снижая диапазон поиска. Также время от времени автор бота вручную редактировал ответы, помечая новые точно правильные и точно неправильные, сильно упрощая задачу сходимости.
У меня уже не было сомнений, что надо ставить капчу. Но как я мог так сильно недооценить адаптивный подбор? Почему такая сходимость, всего 10 000 запросов? Короче, пришлось взять ручку, листок бумаги и думать.
Оценка сходимости
Теперь тот самый «матан». Нас интересует грубая оценка, поэтому ограничимся нестрогими выкладками. Наша задача ― показать, что бот найдет решение за значительно меньшее число попыток, чем «топорная» оценка по общему числу уникальных комбинаций (нам ведь известно по крайней мере об одном решении, которое сошлось за 104 попыток).
Для начала мы воспользуемся методом, на который меня натолкнул коллега из лондонского офиса, Евгений Кучера. Он предложил смотреть на задачу как на решение системы случайных линейных уравнений: каждое прохождение теста дает одно уравнение вида «сумма таких-то ответов на такие-то вопросы равна такому-то результату». Каждое прохождение теста дает +1 уравнение. Для простоты будем считать, что каждый вопрос имеет по 5 вариантов ответа. Все уравнения линейные, и система может иметь решение, если число независимых уравнений будет равно числу неизвестных. Число неизвестных ― это, грубо говоря, число вопросов, помноженное на число вариантов ответов, N = 80*5 = 400. А необходимая зависимость уравнений ― нюанс, возможно, знакомый читателю из курса линейной алгебры. Нельзя просто так получить первые же N уравнений и считать, что система имеет решение: одно уравнение может быть линейной комбинацией других уравнений, не нести никакой дополнительной информации. Но мы схитрим и просто покажем на пальцах, что за число тестов порядка N не получить систему независимых уравнений ― тут надо очень постараться.
Действительно, после того как число испытаний M превысит N = 400, число возможных комбинаций из уравнений будет расти как число сочетаний из N по M, то есть невероятно быстро. Уже при M = 2N это число будет составлять (2*400)!/(400!)2. И это очень большое число, без специальных ухищрений его уже даже не посчитать из-за переполнения обычных 64-битовых типов с плавающей точкой double, оно превышает 10+308. При этом скорость «перемешивания» вопросов тоже очень большая: вероятность встретить в одном тесте любую пару вопросов невелика, это примерно (25/80)2 = 0.0977, но уже при M = 2N испытаний вероятность не встретить эту пару ни в одном испытании равна (1 — 0.0977)2*400 = 10-36! Таким образом, вероятность того, что среди M>2N испытаний мы сможем выбрать такие N уравнений, чтобы с одной стороны там были все переменные, а с другой стороны система была независима, очень большая. Более строгое доказательство можно провести через анализ детерминанта случайной квадратной матрицы из нулей и единиц, но математические упражнения такого уровня выходят за рамки этой статьи, к тому же я попросту не уверен в том, что в состоянии достойно завершить это интеллектуальное путешествие.
В итоге понятно, что за число испытаний, сравнимое с числом переменных, получить систему независимых уравнений вроде бы можно. Даже если мы где-то ошиблись, пусть даже на порядок, всё равно эта оценка дает удивительный результат: мы получили никакие не числа сочетаний, а практически мгновенную сходимость, линейную относительно числа вопросов.
Рассуждения выше, конечно, довольно грубые. Давайте рассмотрим другой метод, куда более строгий, наглядный и очень красивый. Наверняка этот метод даже носит какое-то название и много где используется, но автор этого не знает в силу своей темноты.
Суть метода в следующем: бот отвечает совершенно случайно, но учитывает только те испытания, которые дали результаты с определенным количеством баллов. Чтобы метод заработал, это определенное количество баллов должно быть больше наиболее вероятного (на самом деле, можно и меньше, лишь бы заметно отличалось). Каждому использованному варианту ответа прибавляется вес ― получается рейтинг гипотез о правильности вариантов ответов. Со временем правильные ответы получают высокий рейтинг, а неправильные ― низкий, и правильные ответы можно легко отличить от неправильных. Звучит странно, да и поверить в это дело с первого раза сложно. Покажем подробнее, как работает метод.
Рассмотрим вероятность выпадения определенного количества баллов s в тесте из n вопросов — p (s, n). Для простоты будем считать, что каждый вопрос имеет одинаковое число ответов m, все ответы — случайные. В этом случае вероятность угадывания ответа или выпадения единицы P(1) = 1/m, а вероятность неверного ответа, или выпадения нуля, P(0) = (m — 1)/m. Искомая вероятность выпадения s баллов ― что-то типа числа сочетаний из s по n, да еще с какими-нибудь множителями типа P(1) в степени s и P(0) в степени n — s (вероятность выпадение s раз единицы и n — s раз нуля умножаем на общее число комбинаций). Не утомляя пока читателя формулами, приведем график вероятности для n = 24 (почему 24, а не 25, расскажем позже):
Теперь применим метод пристального всматривания к следующему выражению:
p (s, n) = p (s — 1, n — 1) * P(1) + p (s, n — 1) * P(0) (1)
Физический смысл этого выражения следующий: вероятность того, что в тесте из n вопросов выпадет s баллов, равна сумме вероятностей двух событий:
- на предыдущем (n — 1) шаге выпало s — 1 баллов, и затем выпала единица
- на предыдущем (n — 1) шаге выпало s баллов, и затем выпал ноль
И теперь самое интересное. Напомним, наш бот работает следующим образом:
бот учитывает только те испытания, которые дали ровно s баллов;
каждому варианту ответа в таких испытаниях бот прибавляет в специальном рейтинге +1.
Таким образом, каждый раз мы будем прибавлять рейтинг и правильным ответам, и неправильным, и вроде бы на первый взгляд в поведении бота логики нет. Но давайте снова посмотрим на (1) и зададимся вопросом: а с какой вероятностью мы прибавляем рейтинг действительно правильному ответу? Представим, что вероятность выпадения единицы выше, чем выпадение каждого из нулей по отдельности (пока просто представим, это будет показано ниже). Тогда со временем, от одного испытания к другому, рейтинг действительно правильного ответа будет расти быстрее, чем у неправильного. При достаточном числе испытаний правильный ответ наберет ощутимо больший рейтинг по сравнению с остальными вариантами, и его будет очень легко отличить от неправильных.
Итак, чтобы метод заработал, нам нужны такие s, чтобы вероятность выпадения единицы была «заметно» больше вероятности выпадения одного из нулей:
p (s — 1, n — 1) > p (s, n — 1) (2)
Снова взглянем на распределение (теперь должно быть понятно, почему это распределение для n — 1 = 24, а не для n = 25). Видно, что искомые s расположены справа от максимума распределения s = 5. Интересно, что слева от максимума выполняется обратное условие: вероятность выпадения единицы заметно меньше, поэтому при расчете рейтинга только для испытаний с таким числом баллов рейтинг правильного ответа будет заметно меньше, и правильный ответ будет так же легко отличим от неправильных.
Таким образом, бот может фиксировать сумму баллов слева от максимума распределения, например для s = 6. Если каждый вариант ответа попадется нам хотя бы несколько десятков раз, то рейтинг правильного ответа и неправильного будет заметно отличаться. Это, конечно, снова нестрогая оценка, но нет желания занудствовать насчет погрешности ― считаем, что за несколько десятков испытаний погрешность будет уже несущественна. Теперь оценим число испытаний, при котором верные ответы определяются с достаточной точностью.
Для этого нам всё-таки придется записать формулу вероятности ответа ровно на s баллов в серии из n вопросов, где в каждом вопросе есть m вариантов ответа. Число вариантов испытаний, которые дадут s баллов ― это произведение числа сочетаний s из n вопросов C(n, s), в которых мы угадаем ответ, и числа вариантов расположить неверные ответы в оставшихся позициях (m — 1)n — s, ведь неправильных ответов на каждый вопрос останется m — 1, а позиций ― n — s. Общее число комбинаций ― mn. Отношение числа годных комбинаций к общему числу и есть искомая вероятность:
p (s, n, m) = n!/(s!(n-s)!) * (m-1)n-s /mn (3)
Внимательный читатель может проверить эту формулу иначе: это вероятность встретить s единиц P(1)s = m-s и n — s нулей P(0)n — s = ((m — 1)/m)n — s, помноженная на общее число комбинаций ― число сочетаний из n по s.
Вернемся к оценке сходимости. Допустим, мы зафиксировали число баллов s = 6. Вероятность выпадения 6 баллов в тесте из 25 вопросов по 5 вариантов ответов по формуле (3) равна 0.163. Следовательно, чтобы набрать 1 «годное» испытание, надо прогнать тест примерно 1/0.163 = 6 раз. Каждый вариант ответа надо прогнать по несколько десятков раз, пусть это будет 30. Тогда каждый вопрос должен встретиться 5*30 = 150 раз. Вероятность встретить определенный вопрос в тесте ― 25/80 = 1/3.2, и значит, очень приблизительно для поиска всех ответов нужно пройти 6 * 150 * 3.2 =~ 3000 тестов!
Чтобы совсем уж убедить читателя в том, что это никакой не фокус, и что решение действительно находится очень быстро, приведем результат численного эксперимента. Ниже изображен рост рейтингов для одного из вопросов при подборе. Как видите, уже при 5000 итераций рейтинг правильного ответа значительно опережает рейтинг неправильных. За 104 итераций разница более чем заметна.
Выводы
Мы убедились, что написать бота ― дело несложное, все рассмотренные методы показывают очень хорошую сходимость. Вернемся на светлую сторону и зададимся вопросом: как усложнить жизнь «ботоводу»?
Часть ответов лежит на поверхности. Во-первых, конечно, нужно ставить капчу, защищать тест через отсылку смс-сообщения, т.е. делать прохождение теста как можно более дорогой операцией, а всю затею с автоматизацией ― нерентабельной.
Во-вторых, нужно увеличивать общую базу ответов. Правда, сходимость решений линейная. И для бота что 100 вопросов, что 1000 вопросов ― вычислительная сложность будет отличаться несильно, а составить 1000 вопросов ― большой труд. Тем не менее, базу вопросов лучше иметь как можно больше. База моего теста постоянно растет, и вы можете помочь в этом деле за вознаграждение (все подробности можно выяснить в личной переписке).
Нетривиальный шаг видится только один: давать испытуемому как можно более «расплывчатую» обратную связь, ведь именно на нее ориентируется бот. Например, не говорить точного количества набранных баллов. Это затруднит сходимость адаптивного решения и сделает невозможным подбор методами типа решения систем линейных уравнений.
Есть одна трудность: неточный результат входит в противоречие со здравым смыслом. Допустим, мы разделили результаты на уровни, например, от «Новичка» до «Эксперта». Этих уровней не может быть два-три, их должно быть не менее пяти. Иначе зачем пользователю проходить тест, который дает совсем уж неточный результат? Но даже в случае ответа в виде уровня адаптивный бот все равно может сходится. Связано это с тем, что адаптивный алгоритм хорошо работает не только на каком-то точном числе баллов, но и на интервале типа s > const, где const ― наиболее вероятное число баллов, максимум распределения. На всем этом интервале вероятность монотонно убывает, а это, как было показано выше, достаточное условие сходимости адаптивного алгоритма. Остается только одно: подобрать такие разделения на уровни, чтобы, с одной стороны, их было достаточно, чтобы тест выглядел вменяемым, а с другой ― чтобы полностью автоматический адаптивный переход с одного уровня на другой был бы практически невозможен.
Вспомним распределение для модели 25 вопросов по 5 вариантов ответа: вероятность правильного случайного ответа на 12 вопросов и выше ― ничтожная. Что если сделать первый уровень, скажем, с 12-ти баллов, или даже выше? Тогда все наиболее вероятные испытания дадут лишь один ответ: «Не прошел», и бот с «холодного» старта не заработает. Если делать следующую границу уровня достаточно далеко, то продраться с уровня на уровень можно будет только при дополнительном разделении вариантов ответов на «Скорее всего верные» или «Скорее всего неверные», то есть ботовод должен помогать своему боту самостоятельно, обучаясь в процессе. А это уже само по себе неплохо.
Вот и все выводы. Если у вас есть еще идеи, как защитить тесты от роботов, будет интересно увидеть их в комментариях.
Алексей Рыбак, Badoo
Автор: fisher
