Добрый день.
На контесте http://codeforces.com/contest/977 отправлено существенное количество решений, содержащих ошибки вроде выхода за границы массива или чтения неинициализированной памяти. Многие из этих решений сейчас являются принятыми, поскольку эти ошибки не приводят к падению: переменные "удачно" расположились в памяти.
Многие из этих решений сейчас отмечены как зачтенные. Соответственно, их можно попробовать "взломать", то есть составить тест, который выявит некорректность решения.
В режиме запуск (http://codeforces.com/contest/977/customtest), при указании компилятора в режиме Diagnostics (DrMemory) ошибки детектируются.
Вопрос — как сделать так, чтобы отправленный "взлом" проверялся в режиме DrMemory, то есть чтобы ошибки в обращении с памятью были детектированы и в режиме "взлома" также как в режиме customtest?
Хороший вопрос. Сам с подобным не раз сталкивался (http://codeforces.com/blog/entry/50683). Было бы хорошо включить такие виды взломов, только тогда всё зависит от того, все ли указанные ошибки Diagnostic утилиты трактовать как ошибки.
Ага, а ещё можно будет ввести макстест и они по ТЛю упадут.
Решение участника -- это пара языка и решения на нем и его вам и нужно сломать. Если нет тестов, на котором оно падает, значит оно верно.
Это легко решается — time limit в таком режиме можно не проверять.
Совершенно согласен с тем, что это пара "язык + исходный код".
Проблема в том, что язык не все определяет.
В частности, выход за границу массива это undefined behavior, зависящий от многих факторов — в числе прочего, от версии компилятора, стандартных библиотек и операционной системы.
В каком-то окружении решение с undefined behavior проходит, при этом не проходя в другом окружении.
Ну я имел ввиду язык в широком смысле (то есть язык+платформа+настройки компилятора). Так можно дойти до того, что sizeof(int)==2 это разрешено по стандарту, а значит половина решений в задачах с 10^9 неверные
Понимаю вашу мысль, но давайте попробуем найти решение. Все-таки, это два разных случая:
Чем плох вариант "фиксированный компилятор(заранее известный) компилирует код и мы смотрим на его поведение?"
Не знаю, сейчас однозначного ответа у меня нет. Может быть, и все в порядке с этим вариантом.
В теории, некоторые undefined behavior могут проявляться не на каждом запуске — это было бы проблемой.
К примеру, ASLR повлиял на расположение данных в памяти, и теперь непосредственно за концом массива нет отображенной памяти, так что out-of-bounds ведет к Runtime Error. В другом случае, за концом массива оказалось что-нибудь, что мы и считали/переписали без внешне видимых проявлений, и решение засчитано.
Если условия запуска каждого отправленного решения идентичны, то все выглядит более-менее. Иначе, проверка решений становится случайным процессом.
Насколько я помню в тех ситуацииях, когда я сталкивался, то что после данного куска памяти что-то есть или нету (то есть падает ли вылезание за массив при фиксированном n) почти всегда воспроизводится стабильно.
Сходу я не понимаю, почему это может быть часто не так.
Никак, такой функциональности нет.
Я считаю это особенностью использования unmanaged-языков вроде C++ на соревнованиях.
Например, если разрешить такие взломы, то также кажется логичным запускать системные тесты тоже в диагностическом режиме. А ещё требуется, чтобы в диагностическом режиме гарантировалось ноль ложных срабатываний на любом корректном коде. В частности, это требует идеально написанных стандартных библиотек, что обычно неправда.
То есть, undefined behavior обрабатываются "как повезет", если я верно понял мысль.
На мой взгляд, это также кажется логичным, но не необходимым продолжением. Запуск системных тестов в таком режиме потребует существенно больших вычислительных ресурсов, чего не требуется в режиме ручного "взлома".
Это требуется в случае системных тестов, в диагностическом режиме можно пустить только "взломы", тогда есть возможность дополнительно проверять их в режиме review.
К примеру, посылка "взлома" в режиме диагностики должна сопровождаться комментарием о том, где конкретно в программе есть ошибка.
Не знаю, насколько обычно это сегодня, ведь в последнее время AddressSanitizer и Valgrind становятся более-менее рутинными инструментами.
Совершенно верно, undefined behavior на то и undefined, что обрабатывается "как повезёт". Как и в реальном мире. Хорошо это или плохо — вопрос философский. С одной стороны, участникам-авторам кода надо тренироваться ловить UB, а с другой стороны хорошо бы уметь указывать во взломах на этот самый UB.
Если разрешать взломам ловить undefined behavior, но не разрешать то же самое системным тестам, то это катастрофически нечестно по отношению к участникам, чьи решения просто никто не посмотрел. Получается, что корректность решения для разных участников оценивается по-разному. Сейчас этой проблемы нет, потому что взломы решений обычно добавляются в системные тесты (если они поймали что-то, что не поймали системные).
Ручное review всех взломов на контесте — это ужас, имхо, потому что полностью убьёт масштабируемость контестов. Сейчас количество участников ограничено количеством машин, но если потребовать ручную работу от жюри, то потребуется сильно больше людей. К тому же добавит ещё больше субъективных факторов в оценке. Возможно, на учебных контестах можно сделать какую-нибудь систему апелляций и открытой проверки, конечно...
В любом случае к каждому динамическому анализатору прилагается стандартная пачка настроек "вот на это в стандартной библиотеке не ругайся, это ложное срабатываение". Можно поискать по багтрекеру более простые примеры ложных срабатываний, которые могут вылезти и на олимпиадах, например.
Я не знаю ни одного инструмента, который бы ставил себе цель "ноль ложных срабатываний" или "найти все undefined behavior" (последнее, например, невозможно сделать, глядя только на машинный код, надо серьёзное содействие со стороны компилятора — чтобы проверять всякие переполнения, "реальные" размеры массивов по указателям, арифметику указателей...).
Выше yeputons и riadwaw дело написали.