Получение данных из турнирных систем олимпиад по информатике

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

1. Наборы тестов (входных данных) — мы в любом случае получаем самый первый тест, а если у нас есть хотя бы какое-нибудь мало-мальски рабочее (проходящее несколько тестов) решение, то получаем и следующие — это даёт занятные результаты:
   • Можно увидеть сами входные данные — это часто позволяет исправить ошибки в решении (к примеру, если мы и не предполагали подобных случаев);
   • Главное — можно, загрузив входные данные, подсовывать их программе с решением «в лоб» (например, полный перебор), которая не проходит в системе по причинам превышения допустимого времени выполнения или размера памяти (а ведь сейчас таких задач очень много — даже начинающий программист практически у всех задач видит элементарное решение, потому авторы заставляют придумывать новые, хитрые и быстрые алгоритмы), а затем отправлять результаты в программе «из if-ов» (то есть для каждого из предлагаемых тестов условными конструкциями выбирать уже готовый ответ);
   • Можно использовать не плохое решение, а решение, которое работает на неподдерживаемых сервером языке программирования или платформе;
   • Если задача заключается в написании программы, повторяющей естественные действия человека, такие, как распознавание текста или подсчёт объектов, можно передавать полученные тесты для решения автору;
2. Техническая информация о сервере, компиляторах или даже о таких серьёзных вещах, как локальная сеть.

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

Прежде чем мы перейдём к делу, хочу предупредить — пожалуйста, не применяйте этот метод на практике. Подробнее об этом Вы можете прочитать в конце статьи.

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

Попробуем передать данные в вердикте. Пусть «решение» передаёт нам данные по частям, например, беря очередной бит и вызывая вердикт в зависимости от его значения. Так, мы можем вызвать превышение допустимого времени выполнения (Time Limit exceed — TL) бесконечным циклом, памяти (Memory Limit exceed — ML) созданием огромного массива, неправильный ответ (Wrong Answer — WA) или ошибку типа вывода (Presentation Error — PE) выводом совершенно не относящейся к теме информации, ошибку выполнения (Runtime Error — Crash) делением на ноль, и так далее.

Каждому из вариантов вердикта мы сопоставим несколько бит, а один из вердиктов отведём под EOF (сигнал конца файла). Далее просто создадим скрипт, который будет формировать и отправлять «решения» на сервер, а затем собирать их результаты. То есть, отправляемое решение может быть таким:

#include <stdio.h>

const int position = $position$;

void call_wa_pe() {
    printf("vJLnKLnjkD\n");
}

void call_tl() {
    while (1) {}
}

void call_crashdvz() {
    int a = 0;
    printf("%d", 5/a);
}

void return_data(int data) {
    if (data == 0)
        call_crashdvz();
    else if (data == 1)
        call_wa_pe();
}

int main() {
    int ch, i = 0, j, tmp;
    while ((ch = getchar()) != EOF) {
        tmp = 1;
        for (j = 0; j < 8; j++) {
            if (i == position) {
                return_data(ch/tmp%2);
                return 0;
            }
            i++;
            tmp *= 2;
        }
    }
    call_tl();
    return 0;
}

Здесь при формировании решений мы просто будем увеличивать на один некую переменную, а затем подставлять в коде её вместо $position$, потом получать результат по битам, пока не получим EOF.

Может показаться, что это неэффективно — даже для нескольких байт понадобится очень много запросов к серверу. Но это не так — далее я приведу множество ухищрений, и в итоге будет достаточно вплоть до двух запросов на тест.

Кулхацкерам на заметку

• Часто системы представляют нам целый зоопарк возможных вердиктов. Например, кроме классических TL, VL, WA и PE иногда различаются Security Violation (SV — при обращении к запрещённым ресурсам) и разновидности Crash — stack overflow, access denied, math error и многие другие. Просто взгляните на монитор системы и в документацию.
• Приведённые в условии задачи примеры входных и выходных данных сразу же сообщите скрипту, чтобы не узнавать уже известное.
• Ограничьте количество вариантов — ведь вовсе не все возможные байты могут содержаться во входных данных, так, почти всегда можно отбросить старший бит — вряд ли в тесте будут русские буквы или различные специальные знаки. Главное — если в задаче на ввод подаются числа (так бывает в более чем половине задач), вариантов байта может быть только 11 — 12, то реально передавать даже по байту за раз.
• Можно передавать за один запрос информацию разной длины. Например, если вам не хватило вариантов, чтобы одним вердиктом всегда отправлять три бита (вариантов меньше восьми), зато избыток вариантов для двух бит (вариантов больше четырёх), сделайте варианты, которые отправляют часто используемые сочетания типа трёх бит 000 (остальные пусть так и будут отправлять по два бита).
• Пока не достигнут конец байта (восемь бит), можно (ведь в файле всегда целое число байт) сделать EOF посередине байта сигналом того, что оставшиеся биты — нули/единицы. Ещё лучше в это время добавлять вместо EOF ещё один вариант.
• Очевидно, если длина входных данных всегда одна и та же, либо она дана или её можно как-либо вычислить по остальным данным, EOF не нужен совсем. И наоборот — так, в задачах часто даётся количество строк, затем перечисляются строки. Тогда нужно передавать только строки, завершая их EOF, ведь количество даётся лишь для удобства. То естьпередаются или данные о длине, или EOF.
• Задействуйте простой алгоритм архивации при передаче входных данных в несколько десятков символов.
• Используйте обфускацию, а всё псевдо-решение сделайте под стиль кода новичка.
• Для WA стоит генерировать различные случайные строки (это туда, где в примере кода строка «vJLnKLnjkD»). Лучше, чтобы они были не зашиты в коде решения константой, а создавались из каких-либо составляющих.
• Чтобы добавить ещё один вариант вердикта, стоит отделить WA от PE (PE обычно возникает, если формат вывода совершенно отличен от нужного, но для этого нужно анализировать условие задачи).
• Можно передавать после EOF ещё и контрольную сумму, которая поможет вам проверить, передались ли данные правильно.
• Каждый раз меняйте «легенду» вердиктов — один раз TL означает 10, другой — вовсе EOF.
• Лучше сделать разные варианты псевдо-решения, да ещё и на нескольких языках программирования.
• Задействуйте несколько аккаунтов (естественно, заходя с разных IP и маскируясь под разные браузеры).
• Сделайте задержки между отправками большими, насколько это возможно.

А чтобы всё выглядело ещё более естественно, в последних четырёх пунктах следует применить генератор случайных чисел.

Все эти советы помогают скрыть факт проведения атаки и заметно сократить её время.

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

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

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

Подведём итоги. У нас есть способ за несколько десятков запросов получить «Зачтено» из большинства плохих решений, на любой системе. Что это даёт? Ничего — ведь подобные системы делаются только для саморазвития. Так, в этой статье мы просто рассмотрели один из методов обхода защиты, что полезно, например, для создателей такого программного обеспечения. Я никому не советую применять такие методы на практике — это очень не понравится организаторам и принесёт вам много проблем. Лучше сядьте и решите несколько задач. Решите честно. Станьте умнее, не переходите на тёмную сторону.