LINUX.ORG.RU

Спортивное программирование наоборот

 ,


0

1

Ни для кого не секрет, что задачи, которые решают на олимпиадах по спортивному программированию, не поощряют корректность и безопасность кода:

  • формат входных данных четко определен, поэтому нет смысла тратить время на secure input and output handling
  • программа может успешно пройти все тесты и уложиться в отведенное время, несмотря на наличие в ней серьезных ошибок и implementation-defined/undefined behaviour
  • программа, ровно как и программист, ограничены по времени и доступным ресурсам (память для программы, доступ к документации для программиста), поэтому всякие там проверки возвращаемых значений невыгодны в плане производительности

Собственно к чему я это: а существуют ли online judge системы (или сервисы, или же научные статьи, которые такие системы описывают), в которых основным критерием оценки является не скорость, а безопасность и корректность реализации?

★★★★★

Нашел кое-что: https://builditbreakit.org/

В фазе соревнования под названием «Built It» предлагается разработать систему умеренной сложности, например, веб-сервер или парсер определенного формата файлов, а в фазе «Break It» — найти дыры в программах соперников.

Правда правила участия у них, мягко говоря, странные:

You can participate in the contest if:

  1. You are enrolled as a graduate or undergraduate student anytime during the same calendar year that the contest takes place.
  2. You are either a US citizen or attend a US-based University.
  3. You do not have close relationships with any of the contest organizers.
edigaryev ★★★★★ ()

Где-то я на такое натыкался. Даже русскоязычное. Но убей не помню. Сайт такой совсем совсем простой был, без картинок почти, и на перле написан был, судя по линкам.

anonymous ()

Будь мужиком, запили свою!

anonymous ()

корректность реализации

Если программа выполнила свою задачу, значит она корректна, не?

aboutcard ()

Если попадёшь в OpenBSD base — считай, что ты тест прошёл. ;)

beastie ★★★★★ ()
Ответ на: комментарий от aboutcard

А если програма выполнила свою задачу и попутно, невзначай развязала 3-ю мировую? Что тогда?

beastie ★★★★★ ()

На первый взгляд кажется, что в таком соревновании любой сколько-нибудь вменяемый программист легко наберёт 100%. Сомневаюсь, что такое есть. Фишка спортивного программирования в том, что там сложные задачи, которые мало кто может решить. А в чём сложность бездумно понаставить миллион if-ов?

Legioner ★★★★★ ()
Ответ на: комментарий от beastie

Ну, если в задачу программы входило *не развязывать 2-ю мировую*, значит она не выполнила задачу. В остальных случаях виноваты разработчики, которые это допустили. rm -rf / корректная программа?

aboutcard ()
Ответ на: комментарий от beastie

Вот, кстати, хорошая аналогия. Многие дети гибнут в электроустановках. Почему? Потому что они туда залезают. Если бы электроустановки делались таким образом, чтобы проникнуть туда было невозможно, этого бы не происходило. Чья тут вина? Можем ли мы сказать, что в ребенке заложена неверная программа — любознательность, которой его наделила сама природа? Нет, потому что любознательность дает драгоценный опыт, который, в конечном итоге, увеличивает шансы на выживание. Поэтому виноваты тут именно те мрази, кто допускает проникновение.

aboutcard ()
Ответ на: комментарий от aboutcard

«Нашедшего выход затопчут первым.» ©

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

Но вернёмся к теме: self-ref — это именно то, что продуцируют на таких соревнованиях.

beastie ★★★★★ ()
Ответ на: комментарий от beastie

Если попадёшь в OpenBSD base — считай, что ты тест прошёл. ;)

OpenBSD base не резиновый, поэтому интересно скорее вот что: неужели кроме OpenBSD никто не пишет софт подобным образом (secure by default, privelege separation, и т.д.) и преследуя те же цели?

edigaryev ★★★★★ ()
Ответ на: комментарий от Legioner

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

А в чём сложность бездумно понаставить миллион if-ов?

Вопрос в том, как эти 100% будут определяться, и кто будет проверять решения участников — компьютер, или же непосредственно другие участники. Цитирую первое мое сообщение в этой теме:

В фазе соревнования под названием «Built It» предлагается разработать систему умеренной сложности, например, веб-сервер или парсер определенного формата файлов, а в фазе «Break It» — найти дыры в программах соперников.

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

edigaryev ★★★★★ ()
Ответ на: комментарий от beastie

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

например http://energocomplekt.com.ua/img/ktpm_1.jpg

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

Но вернёмся к теме: self-ref

Я, честно говоря, не особо понимаю, что значит тьюринг-полнота в данном контексте. У тьюринг машины, как раз, программа и данные четко разделены. Она не может интерпретировать как программу то, что пишется на ленте. Получается, что если в конфиге есть «исполняемые строки», это более сильная машина, нежели МТ:)

А что касается того, надо ли это делать, или нет, зависит от задачи. Это философский вопрос. Существует такое понятие, как «программа управляемая данными».

aboutcard ()
Ответ на: комментарий от beastie

Собственно, хотелось бы узнать, какую конкретно видят в этом опасность? Например. И при чем тут self-ref? Кто, в данном случае, обращается сам к себе, так сказать, семантически?

aboutcard ()
Ответ на: комментарий от aboutcard

А ещё есть такое понятие, как «странная машина» — что в ключе нашего разговора.

Т.е. нечто, что при верных входных данных вывоплняет свою задачу, а при неверных — всё что угодно, вплоть до 3-й мировой.

Об этом у ТС и речь.

beastie ★★★★★ ()

Тебе нужен онлайн эмулятор реальности?

anonymous ()

не поощряют корректность и безопасность кода

ну эт когда как: для того, чтобы не приходилось долго и безуспешно дебажить, как раз более-менее учат, как писать без ub и implementation-defined. ну а если программа успешно пройдёт все тесты при том, что в ней есть серьзные ошибки, то можно сделать вывод, что тесты — говно.

f1u77y ★★★ ()
Ответ на: комментарий от edigaryev

OpenBSD base не резиновый, поэтому интересно скорее вот что: неужели кроме OpenBSD никто не пишет софт подобным образом (secure by default, privelege separation, и т.д.) и преследуя те же цели?

Chrome, например, считается довольно защищённым браузером.

Legioner ★★★★★ ()
Ответ на: комментарий от edigaryev

Это ты к чему? Сравни с MSIE или FF.

Code Execution: 74/539/627

Gain Privileges: 5/25/34

А если за последние 3 года посчитать, а не за всю историю, то там отличие будет вообще колоссальное.

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

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

Legioner ★★★★★ ()
Последнее исправление: Legioner (всего исправлений: 1)
Ответ на: комментарий от Legioner

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

яснопонятно.

t184256 ★★★★★ ()
Ответ на: комментарий от Legioner

Сравни с MSIE или FF.

Зачем? С таким подходом еще долго не будет браузера, который хотя бы отдаленно не напоминает решето.

Ещё и смотреть надо, сколько из этих уязвимостей реально можно было эксплуатировать.

Колонка под названием «code execution» тебе ни о чем не говорит?

И этих CVE может быть тысячи

Arbitrary code execution там находят стабильно раз в два месяца, и это только паблик. Это же праздник просто какой-то!

edigaryev ★★★★★ ()
Ответ на: комментарий от edigaryev

Зачем? С таким подходом еще долго не будет браузера, который хотя бы отдаленно не напоминает решето.

Жизнь — боль? :) Браузер это самое используемое приложение в мире. Причём загружающее и исполняющее произвольный код без каких-либо подписей и проверок. Естественно все, кто может и не может, будут пытаться поломать именно его.

Arbitrary code execution там находят стабильно раз в два месяца, и это только паблик. Это же праздник просто какой-то!

Сode execution без привилегий ничего не может. Чтобы что-то смочь (например открыть локальный файл или запустить произвольную программу хотя бы от имени пользователя), надо повысить привилегии. А вот это уже очень редкий баг.

Legioner ★★★★★ ()
Последнее исправление: Legioner (всего исправлений: 1)
Ответ на: комментарий от edigaryev

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

А еще вспомнились фразы: «****-**** и в продакшн» и «всем *****».

deep-purple ★★★★★ ()
Ответ на: комментарий от deep-purple

Просто нужно первого посадить за мошенничество.

Deleted ()
Ответ на: комментарий от edigaryev

OpenBSD base не резиновый, поэтому интересно скорее вот что: неужели кроме OpenBSD никто не пишет софт подобным образом (secure by default, privelege separation, и т.д.) и преследуя те же цели?

Из открытых проектов ещё OpenWall есть. Остальное - коммерческие продукты. В опенсорце это не модно.

hateyoufeel ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.