Как стать автором
Обновить

Олимпиады по программированию, взгляд из НГУ. Статья 2 — тестирующая система

Спортивное программирование*
Я продолжаю свой цикл статей про спортивное программирование в НГУ. В прошлый раз я рассказал, как пишутся задачи для турниров, теперь же я хочу рассказать немного о тестирующей системе.

Первая статья — про составление задач.
Третья статья — про работу оргкомитета.
Четвёртая статья — про тур непосредственно.

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


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

Тестирующая система, что логично, имеет серверную и клиентскую часть. Серверная составляющая в случае NSUts написана на Perl-е. Собственно, выбор языка сильно долго не стоял. Поначалу ребята пытались оптимизировать ujudge (aka Великий и ужасный Goplan), но после того, как на отборочном Всесиба 2008 года система опять помахала в воздухе лапками, слово Ruby в кругу НГУшных олимпиадников было объявлено матерщинным. Было принято решение возродить систему Жени Четвертакова, которая долгое время справлялась со своими задачами, но была некогда заменена на более красивую и современную ujudge. Так что Perl сам напросился.

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

Клиентская часть состоит из программного комплекса:
1. WinKill – запуск программы с ресурсными ограничениями
2. Diff – посимвольное сравнение двух файлов
3. Noasm – поиск ассемблерных вставок
4. Estimator – программа, предназначенная для зачисления баллов за тесты
5. Набор bat-файлов для запуска компиляторов и программ
Про каждый элемент можно говорить очень долго, но слаженно они осуществляют проверку решений и выносят вердикт о том, верно ли решена задача. Параллельно тестирующих клиентов может быть запущенно несколько. Причём, их можно запускать параллельно не только на различных машинах, но и на одной машине с многоядерным процессором. Так же, Web-интерфейсов может быть много. Всё это многообразие объединяет одно — база данных MySQL, которая зачастую запускается вместе с Web-интерфейсом.

Теперь, когда мы уже обзорно знаем, как устроена тестирующая система, проследим, какой путь должно проследовать решение, написанное командой, чтобы она (команда) получила себе заслуженный плюсик (или минус) в рейтинг.

Получение решений участников олимпиады


Решения участников олимпиады хранятся на Web-сервере проведения олимпиады. На него возложен контроль максимального объёма кода решения, чтобы слишком большие решения пресекались ещё на стадии приёма. Список решений участников и параметры их запуска хранятся в базе данных.
Жизненный цикл работы изолирующей среды начинается с запроса тестирующего клиента к базе данных сервера олимпиады. В ответе на этот запрос клиент должен получить id номер хранящегося в базе сданного решения, в случае, если в базе есть решения для проверки. Если решений нет, то запрос должен быть повторён через некоторое время. Пауза между запросами необходима для того, чтобы излишне не нагружать базу данных.

Итак, у нас уже отсеялись слишком большие исходники. Зачем это делается? Можно просчитать ооооочень трудоёмкое решение минут за 5 на своём рабочем компьютере и загнать всё в одну большущую мапу в исходнике. А само решение будет выглядеть как read(a), write(res[a]). Вот такую хитрость мы уже обрезали.

Компиляция


Перед проверкой решения тестировщик должен собирать его программный код компилятором, определённым в параметрах, переданных от сервера. Чтобы удовлетворить требованиям безопасности, тестирующий клиент включает в себя урезанные версии библиотек компиляторов. Из компиляторов исключены потенциально опасные библиотеки для работы с операционной системой на низком уровне. Урезанные версии библиотек компиляторов только затрудняют доступ к сети и функциям WinAPI 32, однако у тестируемых приложений есть возможность использования библиотек через ассемблерные вставки. За это отвечает программа noasm. В случае, если будет найдено ассемблерное включение, программный код не будет скомпилирован, а, следовательно, потенциально вредоносный код не будет запущен, при этом сервер олимпиады будет оповещен об ошибке компиляции.

Отлично. Сейчас у нас уже есть готовый бинарник, который только и ждёт, что ему бросят пачку вкусных, свежих, сочных тестов. Это требуется проконтролировать, иначе простенькая ошибка в программе (или злые козни участников, решивших победить неспортивным путём) может свалить тестирующую систему в нокаут. На моей памяти, такие дерзкие попытки однажды были пресечены дисквалификацией. Ну да, это же не конкурс среди black hat-ов =) Да и тем более, большая часть пакостей, по типу killer #define, уже срезана нами на этой стадии, так что простора для бесчинств осталось очень мало.

Запуск программ


Для программного управления ограничениями ресурсов и контролем доступа в ОС Windows доступна библиотека WinApi 32. Контролировать права доступа, ресурсы компьютера и работы процесса, было решено, при помощи WinApi 32. В ОС Windows создаётся специальная учётная запись пользователя с ограниченными правами доступа, чтобы обеспечить безопасный запуск с ограничениями собранной программы. Она имеет только одну рабочую директорию с монопольными правами доступа.

Банк тестов (входных и выходных данных) хранится на сервере проведения олимпиады. Тестирующий клиент имеет собственную локальную копию тестов. Программа должна быть проверена на полном наборе тестов. Для этого тестер осуществляет запуск скомпилированной программы на каждом тесте. Входные данные передаются приложению в виде файла input.txt, помещённого в рабочую директорию. Запуск скомпилированной программы осуществляется при помощи программы WinKill. Она средствами WinAPI устанавливает ограничения на использование системных функций и запускает программу от имени учётной записи с ограниченными правами.

Контроль в момент исполнения


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

Возврат в исходное состояние.


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

Ну вот и всё по тестирующей системе. Работающую версию можно увидеть вот тут: olimpic.nsu.ru/tester/nsuts_olymp.cgi. Большое спасибо хочу сказать за помощь при написании статьи моему другу Саше Кирову, одному из авторов NSUts. Процентов 70 текста в этот раз — цитаты из его дипломной работы.

В следующей же статье мы вместе с Наташей Поповой постараемся рассказать, как происходит организационная часть олимпиады, ведь Всесибирская олимпиада — это не только ценный мех много крутых кодеров, но и достаточно серьёзный международный проект, где каждую мелочь надо продумать и организовать.
Теги:олимпиады по программированиюacm icpcНГУспортивное программирование
Хабы: Спортивное программирование
Всего голосов 31: ↑22 и ↓9+13
Просмотры7.5K
Комментарии Комментарии 23

Похожие публикации

Лучшие публикации за сутки