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

Помните zip-бомбы? На Stack Exchange тоже помнят. Там решили устроить соревнование, кто напишет лучшую компиляторную бомбу. Выбрали для вас 7 самых-самых.

Наверное, всем знакомы zip-бомбы, XML-бомбы и подобные им. Для тех, кто не в курсе, это такие относительно небольшие файлы, которые, если подать их на вход программе, не защищённой от такой атаки, могут потребить невообразимое количество памяти. Соревнование, проведённое на Stack Exchange, как раз заключается в использовании компилятора тем же образом. Задача состоит в том, чтобы написать программу весом до 512 байт, которая компилируется в файл, занимающий как можно больше места. Наибольший выходной файл побеждает!

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

В результате компиляции на выходе должен получиться ELF-файл, Windows Portable Executable (.exe), байт-код для JVM или .Net CLR (другие типы байт-кода тоже, скорее всего, можно использовать, если попросить) и файлы Python .pyc/.pyo;
Если выбранный вами язык не поддерживает компиляцию в один их этих форматов напрямую, то можно использовать транспиляцию, а следом за ней — компиляцию. Транспилировать можно много раз, главное, чтобы вы не использовали один и тот же язык более одного раза;
Ваш код может состоять из нескольких файлов, в том числе и файлов ресурсов, но их общий размер не должен превышать 512 байт;
Нельзя пользоваться никакими источниками, кроме ваших исходных файлов и стандартной библиотеки выбранного языка. Если ваша система это поддерживает, вы можете статически прилинковать стандартную библиотеку. Нельзя использовать сторонние библиотеки или библиотеки операционной системы;
Должна быть возможность компиляции путём вызова команды или нескольких команд. Если вы используете особые флаги для компиляции, они учитываются при подсчёте общего размера. Например, если вы компилируете с помощью команды gcc bomb.c -o bomb -O3 -lm, часть -O3 -lm (7 байт) прибавится к общему размеру файлов (обратите внимание, самый первый ведущий пробел не считается);
Препроцессоры можно использовать только в том случае, если они являются стандартной опцией для компиляции в вашем языке;
Вы можете выбрать любую среду, однако, чтобы всё можно было проверить, придерживайтесь последних (то есть доступных) версий компиляторов и операционных систем. Само собой, нужно указать, что конкретно вы используете;
Компиляция может проходить с предупреждениями, но обязательно без ошибок;
Что конкретно делает ваша программа не имеет значения, главное, чтобы ничего вредоносного. Возможность её запуска вовсе не обязательна.

Пример 1

Программа на Си

			main(){return 1;}

Скомпилирована с помощью Apple LLVM version 7.0.2 (clang-700.1.81) на OS X 10.11 (64-bit):

			clang bomb.c -o bomb -pg

Выдаёт файл размером в 9228 байт. Общий размер исходных файлов 17+3 ( -pg) = 20 байт, что вполне вписывается в ограничение.

Прим.перев. В этом примере создаётся исполняемый файл в формате Mach-O (используемом системой OS X), хотя технически разрешены только ELF и PE (используемые Linux и Windows соответственно). Это не должно значительно повлиять на размер выходного файла.

Пример 2

Программа на Brainfuck:

			++++++[->++++++++++++<]>.----[--<+++>]<-.+++++++..+++.[--->+<]>-----.--
-[-<+++>]<.---[--->++++<]>-.+++.------.--------.-[---<+>]<.[--->+<]>-.

Транспилирована с помощью awib в Си следующей командой:

			./awib < bomb.bf > bomb.c

Затем скомпилирована с помощью Apple LLVM version 7.0.2 (clang-700.1.81) на OS X 10.11 (64-bit):

			clang bomb.c

Выдаёт файл размером в 8464 байт. Здесь общий размер исходников составляет 143 байта, так как @lang_c по умолчанию доступен в awib, и нужды добавлять эту строку в исходный файл нет. Кроме того, ни в одной из команд не использовались особые флаги.

Обратите внимание, в данном случае есть временный файл bomb.c размером в 802 байта, однако это не учитывается при подсчёте ни исходных, ни выходных размеров.

Если кто-то получит выходной файл размерами более 4 ГБ (вдруг кто-нибудь найдёт полный по Тьюрингу препроцессор), задачей будет достичь как можно меньшего размера исходных файлов, которые на выходе дают файл как минимум того же размера, так как проверять варианты со слишком большими выходными файлами не очень практично.

Среди всех решений мы выбрали 7 самых-самых.

Хотите понимать, почему это всё работает? Учите матчасть — подборка книг о компиляторах.

Решения

Си

14 + 15 = 29 байт исходников, 17 179 875 837 (16 ГБ) байт на выходе

main[-1u]={1};

Эта строка определяет функцию main как огромный массив и инициализирует его первый элемент. В итоге GCC приходится сохранить весь массив в итоговом исполняемом файле.

Прим.перев. Из информации о массиве, инициализированном нулевыми значениями, в исполняемом файле сохраняется (в секции bss) только размер, а память под сам массив выделяется при выполнении; иначе начальное значение массива полностью помещается в исполняемый файл (в секцию data).

Поскольку этот массив больше 2 ГБ, при компиляции нужно использовать флаг -mcmodel=medium. Согласно правилам, это добавляет 15 байт к общему размеру исходных файлов.

Не ожидайте чего-то сверхъестественного при запуске этой программы.

Компиляция с помощью команды:

			gcc -mcmodel=medium cbomb.c -o cbomb

C#

Около минуты на компиляцию, 28 МБ на выходе

			class X<A,B,C,D,E>{class Y:X<Y,Y,Y,Y,Y>{Y.Y.Y.Y.Y.Y.Y.Y.Y y;}}

Добавление большего количества Y увеличит размер экспоненциально.

Здесь используется трюк с наследованием и параметрами типа для создания рекурсии. Чтобы понять происходящее, давайте немного упростим выражение. Представим, что у нас есть class X<A> { class Y : X<Y> { Y y; } }, который создаёт обобщённый класс X<A>, у которого есть внутренний класс Y. Класс X<A>.Y наследует X<Y>, поэтому у X<A>.Y тоже есть внутренний класс Y, и в итоге получаем X<A>.Y.Y. Этот класс, в свою очередь, тоже имеет внутренний класс Y, у которого также есть внутренний класс Y, который тоже содержит внутренний класс Y и т.д. Это значит, что вы можете использовать разрешение области (.) до бесконечности, и каждый раз при его использовании компилятор должен вывести новый уровень наследования и параметризации типов.

Чем больше мы добавляем параметров типа, тем больше работы компилятору нужно выполнить на каждом этапе.

Посмотрим на разные варианты:

В class X<A> { class Y : X<Y> { Y y;} } параметр типа A имеет тип X<A>.Y;
В class X<A> { class Y : X<Y> { Y.Y y;} } параметр типа A имеет тип X<X<A>.Y>.Y;
В class X<A> { class Y : X<Y> { Y.Y.Y y;} } параметр типа A имеет тип X<X<X<A>.Y>.Y>.Y;
В class X<A,B> { class Y : X<Y,Y> { Y y;} } параметр типа A имеет тип X<A,B>.Y и B имеет тип X<A,B>.Y;
В class X<A> { class Y : X<Y> { Y.Y y;} } параметр типа A имеет тип X<X<A,B>.Y, X<A,B>.Y>.Y и B имеет тип X<X<A,B>.Y, X<A,B>.Y>.Y;
В class X<A> { class Y : X<Y> { Y.Y.Y y;} } параметр типа A имеет тип X<X<X<A,B>.Y, X<A,B>.Y>.Y, X<X<A,B>.Y, X<A,B>.Y>.Y>.Y и B имеет тип X<X<X<A,B>.Y, X<A,B>.Y>.Y, X<X<A,B>.Y, X<A,B>.Y>.Y>.Y.

Таким образом, можно только представить, какую работу должен проделать компилятор, чтобы понять, чем A является для E в Y.Y.Y.Y.Y.Y.Y.Y.Y в определении class X<A,B,C,D,E>{class Y:X<Y,Y,Y,Y,Y>{Y.Y.Y.Y.Y.Y.Y.Y.Y y;}}.

Python 3

1. 13 байт исходного кода, 9 057 900 463 байт (8.5 ГБ) .pyc-файл

			(1<<19**8,)*2

Такой вариант был предложен после того, как пользователь осознал, что выходные размеры больше 4 ГБ не имеют значения, поэтому он решил чуть укоротить код. Ниже его первоначальный вариант с объяснениями.

2. 16 байт исходного кода, >32 ТБ .pyc-файл (если у вас достаточно памяти, пространства на диске и терпения)

			(1<<19**8,)*4**7

Python 3 выполняет свёртку констант, что даёт вам возможность быстро получать большие числа путём возведения в степень. Формат, используемый .pyc-файлами, хранит длину представления целого числа, используя 4 байта, хотя на самом деле похоже, что лимит составляет 2**31. Поэтому при просто возведении числа в степень максимальный размер выходного .pyc-файла, который можно получить с исходниками размером в 8 байт, составляет 2 ГБ. 19**8 приблизительно равно 8*2**31, поэтому 1<<19**8 имеет двоичное представление в районе 2 ГБ. На 8 умножаем, чтобы получить байты, а не биты.

Однако кортежи неизменяемы и при их умножении также происходит свёртка констант, поэтому мы можем повторить эти 2 ГБ столько раз, сколько захотим, вплоть до как минимум 2**31 раз, наверное. 4**7 для получения 32 Тб был выбран просто для того, чтобы превзойти планку в 16 Тб, поставленную одним из ответов.

Haskell

Если кто-то получит выходной файл размерами более 4 ГБ (вдруг кто-нибудь найдёт полный по Тьюрингу препроцессор), задачей будет достичь как можно меньшего размера исходных файлов, которые на выходе дают файл как минимум того же размера, так как проверять варианты со слишком большими выходными файлами не очень практично.

Расширение Template Haskell позволяет генерировать Haskell-код с помощью Haskell на этапе компиляции, поэтому это полный по Тьюрингу препроцессор.

Вот как это сделал один из пользователей с помощью произвольного числового выражения FOO:

			import Language.Haskell.TH;main=print $(ListE .replicate FOO<$>[|0|])

Вся магия заключается в коде внутри вклейки $(...). Он выполняется во время компиляции для генерации AST Haskell-кода, которым заменяется AST программы в месте вклейки.

В данном случае мы делаем простой AST, представляющий литерал 0, повторяем его FOO раз, чтобы получить список. Затем мы используем ListE из модуля Language.Haskell.TH, чтобы превратить список из AST’ов в один большой AST, представляющий литерал [0, 0, 0, 0, 0, ...].

Конечная программа эквивалентна main = print [0, 0, 0, ...] с FOO количеством повторений 0.

Компилируем в ELF:

			$ ghc -XTemplateHaskell big.hs
[1 of 1] Compiling Main             ( big.hs, big.o )
Linking big ...
$ file big
big: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /nix/store/mibabdfiaznqaxqiy4bqhj3m9gaj45km-glibc-2.21/lib/ld-linux.so.2, for GNU/Linux 2.6.32, not stripped

Размер составляет 83 байта: 66 байт весит Haskell-код и 17 байт добавляет аргумент -XTemplateHaskell, плюс длина FOO.

Мы можем не использовать аргумент для компиляции и просто скомпилировать с помощью ghc, но тогда в начале кода придётся добавить {-# LANGUAGE TemplateHaskell#-}, что увеличит его размер до 97 байт.

Вот несколько примеров с разными выражениями для FOO и размерами выходного файла:

			FOO        Размер FOO  Общий размер  Выходной размер
-----------------------------------------------------
(2^10)      6Б          89Б           1.1MБ
(2^15)      6Б          89Б           3.6MБ
(2^17)      6Б          89Б           12MБ
(2^18)      6Б          89Б           23MБ
(2^19)      6Б          89Б           44MБ

При компиляции с (2^20) у автора решения закончилась оперативная память.

C++

250 + 26 = 276 байт

			template<int A,int B>struct a{static const int n;};
template<int A,int B>const int a<A,B>::n=a<A-1,a<A,B-1>::n>::n;
template<int A>struct a<A,0>{static const int n=a<A-1,1>::n;};
template<int B>struct a<0,B>{static const int n=B+1;};
int h=a<4,2>::n;

Это функция Аккермана, реализованная с помощью шаблонов. Автор решения не смог скомпилировать код с h=a<4,2>::n;, имея 6 ГБ оперативной памяти, но смог с h=a<3,14> и получил на выходе файл размером 26 МБ. Вы можете настроить константы таким образом, чтобы они соответствовали ограничениям вашей платформы — загляните в статью на Википедии по ссылке выше.

Для компиляции с GCC требуется флаг -g (поскольку место, в основном, занимается отладочными символами), а также указание глубины шаблона больше стандартной. В итоге код был скомпилирован так образом:

			g++ -ftemplate-depth=999999 -g -c -o 69189.o 69189.cpp

Информация о платформе:

			g++ (Ubuntu 4.8.2-19ubuntu1) 4.8.2
Linux 3.13.0-46-generic #79-Ubuntu SMP x86_64 GNU/Linux

ASM

29 + 32 = 61 байт, 4 294 975 320 байт (4 ГБ) на выходе

			.globl main
main:
.zero 1<<32

Скомпилировано с помощью gcc the_file.s -mcmodel=large -Wl,-fuse-ld=gold.

Kotlin

90 байт исходного кода, 177416 байт (173 КБ) скомпилированный JVM-файл

			inline fun a(x:(Int)->Any){x(0);x(1)}
fun b()=a{a{a{a{a{a{a{a{a{a{a{println(it)}}}}}}}}}}}

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

Может, у вас есть вариант побомбезней? Делитесь в комментариях!

17К открытий17К показов