Обфусцируй это: конкурс по запутыванию кода на C

Чем проще и читабельнее код, тем лучше — такой совет дают всем начинающим программистам. И большинство старается ему следовать. Но есть и исключения — когда код запутывают намеренно, делая его непонятным и нечитаемым. Это называется обфускацией (от англ. obfuscate — сбивать с толку).

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

Сатирическое программирование, или Как всё началось

23 марта 1984 года два программиста, Лэндон Курт Нолл и Ларри Бассел, работавшие в компании National Semiconductor, столкнулись с особенно кривым кодом. Ларри в тот день пытался пофиксить баг в классической командной оболочке Unix (Bourne shell), а Лэндон работал с сетевым протоколом ранней версии BSD. В какой-то момент оба вышли из своих кабинетов проветрить мозги.

Вернувшись в офис, Лэндон Нолл опубликовал сообщение в Usenet-группах net.lang.c и net.unix-wizards с призывом запутать ещё больше тот код, который они только что обсуждали. Идею он взял из популярного тогда литературного конкурса, где нужно было написать самую ужасную первую строчку романа. Но вместо строки — худшая программа на C размером не более 512 байт.

На призыв Нолла откликнулось немало программистов, которые стали присылать свои запутанные программы. Тогда Нолл и Бассел решили превратить это в конкурс по обфускации кода — так появился The International Obfuscated C Code Contest (IOCCC).

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

Хакнуть правила и победить

IOCCC проводится не каждый год, а с перерывами — последний на момент написания статьи конкурс состоялся в 2020 году. Сейчас цели The International Obfuscated C Code Contest декларируются так:

• Написать наиболее запутанную программу на C в рамках правил.
• Показать важность хорошего стиля в программировании.
• Озадачить компиляторы C необычным кодом.
• Продемонстрировать тонкости языка C.
• Предоставить безопасный форум для обсуждения плохого кода на C.

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

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

За наихудшее нарушение правил на конкурсе есть даже отдельная номинация. Например, в 1994 году в ней победил Шимон Русинкевич, написавший самую маленькую программу, способную воспроизводить саму себя. Когда программа выполнялась, она выводила ноль байт, что эквивалентно её исходному коду.

После обнаружения «дыры» латают, поэтому правила следующего года уже немного отличаются от предыдущих.

Итоги конкурса обфускации подводит жюри, которое определяет победителей по нескольким основным номинациям: «Худшее злоупотребление препроцессором C», «Самое ошибочное поведение» и так далее. Список счастливчиков публикуется на официальном сайте, что и является наградой.

Куропатка на грушевом дереве: как создаются работы для конкурса

Одним из победителей 1988 года стал британский программист Иэн Филлиппс. По словам судей, его код выглядел так, будто автор просто тыкал пальцами в клавиатуру наугад. Так выглядит вступительный фрагмент кода Филлипса:

main( _, t,
"@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l,+,/n{n+,/+#n+,/#;\
#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/+k#;\
q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# ){nl]!/n{n#'; \
r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#\
\
n'wk nw' iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c ;;\
{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;\
#'rdq#w! nr'/ ') }+}{rl#'{n' ')# }'+}##(!!/")

Однако при запуске программа выводила вполне осмысленный текст песни The Twelve Days of Christmas, в которой поётся про «куропатку на грушевом дереве»:

Как это работает? Майк Марковский сделал подробный разбор устройства этой программы, мы же остановимся на основных моментах. Для начала заменим, тернарные операторы — записи вида a ? b : c — на конструкции if/else:

xmas(int t, int _, char *a) {

    if (t < -72) {
        return xmas(_, t, words);
    }

    if (t < -50) {
        if (_ == *a) {
            return putchar(a[31]);
        } else {
            return xmas(-65, _, a+1);
        }
    }

После этого становится понятно, что переменная t управляет направлением рекурсии. При этом первое условие if (t < -72) особенно не влияет на функциональность программы и добавлено, чтобы запутать читателя.

Читайте также:

Как работает рекурсия функции: объясняем на примере Python

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

Вот как выглядела дешифровка слов в коде:

"@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l+,/n{n+,/+#n+,/#\
 On the /first/second/third/fourth/fifth/sixth/seventh/eighth/ninth/tenth/e 

;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l \
leventh/twelfth/ day of Christmas my true love ga 

q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# \
ve to me0/twelve drummers drumming, /eleven pipers piping, /ten lords a-lea 

){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' \
ping,0/nine ladies dancing, /eight maids a-milking, /seven swans a\ 

iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c \
-swimming,0/six geese a-laying, /five gold rings;0/four ca

;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# \
lling birds, /three french hens, /two turtle doves0and /a partridge in a pea 

}'+}##(!!/";
r tree.00/ 

А вот как сам Майк прокомментировал итоги расшифровки:

Симулятор полёта, проклятый «Hello, world» и другие победители

Участники конкурса обфускации делают всё, чтобы максимально извратить и запутать код. Например, заставляют препроцессор C делать вещи, для которых он не предназначен, или намеренно избегают общепринятых подходов в языке C, находя наиболее сложные способы сделать какую-то банальную вещь.

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

Лучший «однострочник»

Дэвид Корн, автор оболочки Unix Korn Shell, написал программу длиной всего в одну строку для конкурса 1987 года. Благодаря обфускации его программа заставляет читателя думать, что она не скомпилируется. По словам Нолла, даже сам создатель языка C Деннис Ритчи изначально упустил тонкую логику программы.

main() { printf(&unix["\021%six\012\0"],(unix)["have"]+"fun"-0x60);}

Головокружительные полотна из кода

Некоторые участники любят форматировать исходный код в разные образы вроде ASCII-арта. Например, программа одного из победителей 27-го конкурса Юсуке Эндо рисует часы в зеркальном отображении.

А код Карла Бэнкса в виде самолёта — не что иное, как настоящий симулятор полёта. И нет, дело не только в форматировании кода в виде летательного средства. Запуская программу, вы становитесь пилотом одномоторного самолёта Piper Cherokee, который летит на высоте около километра над уровнем земли.

Самолёт управляется с клавиатуры с помощью стрелок и кнопок Page Up и Page Down. На вашем дисплее в левом нижнем углу есть три прибора: спидометр, компас и альтиметр, который измеряет высоту над уровнем земли в футах.

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

Самый «энигматичный»

Развлечения развлечениями, но есть работы, которые содержат в себе исторические отсылки и даже серьёзный философский посыл. Так, например, Коди Фергюсон, написал симулятор знаменитой немецкой шифровальной машины «Энигма», благодаря взлому которой прославился Алан Тьюринг.

Читайте также:

Алан Тьюринг: один из отцов IT, AI и победы во Второй мировой войне

Позорное упоминание

Автор этой программы пожелал остаться неизвестным. Это уникальная авторская интерпретация «Hello, world». Действительно, мало какой джун решится продолжить изучать язык, пережив такое «первое знакомство»:

int i;main(){for(;i["]<i;++i){--i;}"];read('-'-'-',i+++"hell\
o, world!\n",'/'/'/'));}read(j,i,p){write(j/p+p,i---j,i/i);}

Самый хитрый

Дон Янг выполнил обфускацию кода так, что его можно читать в любом направлении. Функционально это «поворачиватель» текста. Если дать ему текст через стандартный ввод (stdin), он выведет тот же текст в стандартный вывод (stdout), но повёрнутый на 90 градусов против часовой стрелки.

Лучший инструмент для рисования

Эта работа использует игровую механику Tetris для генерации изображений. Программа берёт изображение-источник, и её алгоритм преобразует пиксели этого изображения в геометрические фигуры на игровом поле «Тетриса».

Илья Курдюков: победитель из России

Отдельно стоит отметить, что в 27-м конкурсе, который прошёл в 2020 году, в четырёх из 15 номинаций победили программы, написанные российским программистом Ильёй Курдюковым. Вот что это за программы:

• Лучшая утилита. Ею стала программа для вычисления хешей MD5, которая динамически генерирует таблицу констант для расчёта этих хешей. Код форматирован в виде шара.

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

Илья согласился дать небольшой комментарий для Skillbox Media «Код» и рассказал о своём участии в конкурсе и его особенностях.

— Как вам пришла идея поучаствовать в этом конкурсе? В чём, на ваш взгляд, его важность?

— В 2020 году я сидел без работы, было много свободного времени. Решил поучаствовать, чтобы привлечь к себе внимание. Но на самом деле, никакой особой профессиональной ценности в победе в таком конкурсе нет, она производит впечатление лишь на ценителей жанра. Возможно, когда-то давно польза была, а сейчас язык C не так популярен. Мало того, это не показатель, что ты умеешь писать понятный код, а совсем наоборот.

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

Из-за ограничений на размер работы в 2–4 КБ вытекает, что сложные программы будут разрабатываться как поиск колмогоровской сложности. Но про этот термин мало кто знает, больше известно понятие Code Golf — именно к такому формату можно отнести IOCCC.

— Насколько хорошо нужно владеть языком C, чтобы участвовать в конкурсе?

— Для игры в Code Golf (на любом языке) надо иметь определённый «оптимизирующий» склад ума, когда тебе интересно улучшать алгоритм по разным критериям — чтобы он быстрее работал или меньше занимал места. А в процессе улучшается знание языка — например, я запомнил приоритет операторов (operator precedence) в C, чтобы тратить меньше скобок.

Ещё добавлю, что опыт написания короткого кода на C не пригодится для практического программирования, эти приёмы ухудшают читабельность кода и не соответствуют почти ни одному соглашению о стиле. Только в коде OpenCV я видел использование оператора «запятая» — думаю что многие программисты на С/C++, даже с большим стажем, не слышали о таком операторе.

В юности я развлекался с Code Golf на языке ассемблера, причём даже не знал этого названия. Но и до сих пор, бывает, балуюсь подобным. Например, в прошлом году написал LZMA-декомпрессор на x86_64-ассемблере, пытаясь достичь минимального размера кода и бинарного файла.

Кстати, есть игра Human Resource Machine, которая позволяет писать на ассемблероподобном языке, там у каждого уровня есть достижения за минимальный размер или максимальную производительность кода.

— Работы каких конкурсантов вы могли бы выделить и почему?

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

Заключение

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

Среди побочных следствий конкурса — выявление структурных особенностей языка C и слабостей стандартных компиляторов. Например, Фонд свободного программного обеспечения использовал конкурсные работы для регрессионного тестирования своего компилятора C.

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