Что такое тестирующая система

Олимпиады по программированию, взгляд из НГУ. Статья 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
• НГУ
• спортивное программирование

Что такое тестирующая система

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

Для добавления информации о новой тестирующей системе необходимо:

1. В справочнике Тестирующие системы из контекстного меню вызвать процедуру Создать.
2. Заполнить следующую форму параметров: где в первую очередь необходимо:
3. В полях Идентификатор системы и Наименование системы указать идентификатор и наименование тестирующей системы.
4. В поле Пользователь из списка или справочника выбрать пользователя, под которым будет делать запросы тестирующая система.

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

• Интернет адреса тестирующей системы, который указывается в полях URL для основного тестирования и URL для пробного тестирования.
• Для идентификации участника олимпиады, определения предмета состязания и т.д. служит строка шаблона, содержащая идентификаторы (параметры) в знаках процента, которые будут заменены на соответствующие значения для каждого отдельного участника тестирования, предмета и т.д. Строка шаблона вводится в поле Шаблон подстановки параметров.

• %UserPersonID% — будет заменен на идентификатор учащегося.
• %BachSubject% — будет заменен на идентификатор предмета состязания.
• %ExamID% — будет заменен на идентификатор испытания (используется для обратной загрузки результатов испытаний в систему)

При необходимости в полях Текст ссылки для пробного тестирования и Текст ссылки для основного тестирования ввести текст ссылки-приглашения на проведение пробного/основного тестирования, который будет отображаться в поле Ссылка на тестирование личного кабинета школьника.

Тестирующая система для проверки олимпиадных задач по информатике

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

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

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

До 2010-2011 учебного года, при проведении школьных олимпиад по информатике, я не использовал тестирующих систем для проверки задач. В этом учебном году, при проверке решений, я решил использовать тестирующую систему. Первоначально я планировал предложить участникам решать задачи на одном из специализированных сайтов, например, школа программиста. Однако, в этом случае, была большая вероятность того, что кто-то из участников уже решал, ранее, предложенные задачи. По этой причине, было принято решение использовать автономную тестирующую систему. Выбор пал на тестирующую систему TSystem загруженную с сайта http://www.olympiads.ru.

Все необходимы файлы вы можете скачать с этого сайта. Тексты задач содержатся в файлах htm соответствующих архивов.

Инсталляционный пакет для системы (1,6 Мб) скачать>>

Документация для тестирующей системы (11 Кб) скачать>>

Задачи по информатике для 8 класса (2,9 Мб) скачать>>

Задачи по информатике для 9 класса (3,6 Мб) скачать>>

Тестирующую систему TSystem я опробовал в работе с операционными системами Windows Xp и Vista. Никаких сбоев не наблюдалось. После установки и запуска необходимо указать где находится откомпилированный файл (расширение exe) и файл необходимый для проверки решения (xls).

После этого необходимо нажать кнопку «Test», после чего результат тестирования будет отображен в окне браузера.

Как видно из рисунка, из 9 тестов успешно пройдено только три, т.е. в решении задачи допущена ошибка.

Использование данной системы при проведении школьной олимпиады, исключило человеческий фактор, что немаловажно при проведение любых олимпиад. К тому же, использование тестирующей системы было одобрено и участниками олимпиады.

При копировании материалов обратная ссылка обязательна

Что такое тестирующая система

Для входа в систему необходимо на сайте acm.petrsu.ru щелкнуть справа на ссылку «тестирующая система«. Далее нажать «вход в тестирующую систему«, откроется страница, в которой в поле «имя пользователя» ввести номер (логин), выданный вам заранее, и затем — пароль. В выпадающем списке «Контест» выбрать «Базовые задачи по основам программирования«(Если в имени не присутствует симола «@» то никакой контест выбитрать не надо). Нажать кнопку «вход«. Слева вы увидите ссылки:

• Информация о контесте
• Отправить решение
• Результат тестирования
• Положение команд
• Сообщения

Если вы перейдёте по первой ссылке, вы получите список предложенных задач. Для каждой задачи написано максимальное ограничение на время работы программы (Time Limit ), максимальное ограничение на объём используемой памяти (Memory Limit) и ссылка на условие задачи.

Для отправки решения необходимо перейти по ссылке «Отправка решения«, в поле «Задача» выбрать задачу, решение по которой вы хотите послать, в поле «Компилятор» необходимо выбрать компилятор, который переобразует вашу программу в исполняемый файл (есть несколько компиляторов для разных языков программирования, так как вы пишите на языке С/C++, вам пока что достаточно выбирать Microsoft Visual C++ 2005), для передачи исходного кода, необходимо либо вставить написанный вами код в поле «Исходный код«, либо выбрать файл с исходным кодом в поле «Файл с исходным кодом«, затем нажать отправить.

После отправки задачи, страница автоматически перейдёт на страницу по ссылке «Результат тестирования«. Здесь отображается журнал ваших посылок, по каждой задаче написан контест, в котором вы отправили задачу, ваш логин, время отправки решения, написан номер задачи, название компилятора в сокращенном виде, вердикт к решению, номер теста, максимальное время работы вашей программы и максимальный использованный объем памяти. Вердиктов по задаче бывает несколько, только один из них указывает на ваше верное решение.

• NT — (Not Tested) ваше решение отправлено, но ещё не встало в очередь на тестирование.
• CO — (Compilation Operation) выше решение компилируется.
• CE — (Compilation Error) ваше решение не компилируется на данном компиляторе (в поле Compiler указано под каким компилятором вы послали задачу).
• RU — (Running) решение отправлено, но ещё не протестировано до конца, либо находится в очереди на тестирование.
• OK — (OK) решение прошло все тесты и считается зачтенным.
• FT — (Failed Test) произошла ошибка системы связанная с этой задачей, возможные варианты такой ошибки:
  1) Ваше решение «лучше», чем решение жюри 🙂
  2) Жюри забыло положить файл, для проверки решения жюри с вашим решением, такой файл называется «чекер» (checker).
• WA — (Wrong Answer) ваше решение получает неверный ответ на некотором тесте, тест указывается в поле «Test#». Решение не зачтено.
• PE — (Presentation Answer) ошибка представления ответа, тест указывается в поле «Test#». Решение не зачтено. (Очень часто можно расценивать как WA) Возможные причины получения ошибки:
  1) Неправильный формат вывода (требовалось строку выдали число, или наоборот)
  2) Выведено значение не из того диапозона
  3) Вообще ничего не выведено.
• RE — (Run-Time Error) ошибка времени выполнения, также написан тест на котором это произошло. Возможные причины получения такой ошибки:
  1) Ваше решение выходит за пределы выделенной памяти (за пределы массива, переход по несуществующим указателям, освобождение не существующей памяти)
  2) Переполнение аппаратного стека. Например, у вас используется рекурсия. Как известно, для поддержки рекурсии промежуточные данные в функции запоминаются в стеке, а по возвращении восстанавливаются, в случае если количество шагов рекурсии очень большое, то памяти стека не хватит, поэтому программу может «вылететь», то есть не корректно завершится. Решение не зачтено.
• TL — (Time Limit Exceeded) превышено время выполнения, тест, на котором это произошло, указан в поле «Test#«. По каждой задаче указано максимальное время работы на каждом тесте, выше решение превысило это ограничение. Решение не зачтено.
• ML — (Memory Limit Exceeded) превышен объем используемой памяти, тест, на котором это произошло, указан в поле «Test#«. По каждой задаче указано максимальный допустимый объем используемой памяти на каждом тесте, выше решение превысило это ограничение. Решение не зачтено.
• AC — (ACcepted for manual validation) решение прошло все тесты, однако ожидает ручной проверки (например на правильность стиля кодирования).
• SV — (Style Violation) решение прошло все тесты, но не прошло ручную проверку (например стиль кодирования неверный).

На странице «Сообщение» выможете увидеть окончательные ответы системы по вашим решениям. Сообщение посылается системой автоматически по каждому посланному решению. В ответе к решению написано в начале по какой задаче высылается сообщение, номер посылки решения по задаче и развернутая форма вердикта. Если задача зачтена, то вердикт будет содержать фразу «Accepted». На этой же странице можно посылать вопросы жюри. Жюри так же может вам посылать ответ.

Перейдя по ссылке «Положение команд«, вы получите список участников, и количество решённых задач. Для получения списка решенных задач какого-то участника необходимо щелкнуть по его имени.

Ссылка «Выход» нужна для выхода из тестирующей системы, не забывайте это делать, когда уходите из аудитории, где у вас проводится практика.