SELF: прототип меняет ELF на SQLite в исполняемых файлах

Идея выросла из диссертации автора поста (блог fzakaria.com). Ещё во время работы над диссертацией он писал sqlelf, инструмент, который позволяет исследовать уже готовый ELF-файл SQL-запросами (например, SELECT name FROM elf_symbols вместо readelf и grep). По итогам той работы вышла статья (arXiv:2405.03883), которую не приняли к публикации, а реакция на саму идею была прохладной: радикальные предложения трудно продвигать против инерции устоявшегося решения. Идею автор не оставил и с появлением больших языковых моделей вернулся к ней снова, но теперь предлагает не «базу данных, которая описывает исполняемый файл», а заменить сам формат ELF на SQLite целиком: чтобы файл, который получает права на выполнение (chmod +x) и запускается, буквально был базой SQLite.

Центральный тезис поста: ELF и так устроен как база данных, только собранная вручную. Например, для поиска символов ELF использует фильтр Блума и другие самодельные структуры данных вместо готового индекса. При этом сам формат крайне компактен, он проектировался в эпоху, когда место на диске и канал передачи стоили дорого, поэтому модифицировать ELF трудно: секции приходится обнулять и добавлять заново, единой самоописывающей схемы у формата нет, а то, как именно интерпретировать данные, держится на соглашении, а не на формальном описании. SQLite, по мысли автора, снимает обе проблемы: это самоописывающий и при этом стабильный формат, который можно расширять, не ломая существующих потребителей.

Формат называется SELF, Structured Executable & Linkable Format (то есть «структурированный исполняемый и компонуемый формат»). Чтобы программа запустилась, файлу SELF хватает двух таблиц: self_meta хранит заголовок ELF в виде пар «ключ, значение», а segments, образ загрузки, по одной строке на каждый заголовок программы, с самими байтами в поле BLOB. Единая таблица symbols с одним индексом, настоящим B-деревом SQLite, а не самодельным фильтром Блума, заменяет сразу несколько секций ELF и таблицу .gnu.hash; заодно исчезает отдельная таблица строк .dynstr (SQLite и так хранит строки интернированно), а версионирование символов становится обычным столбцом вместо конструкции из .gnu.version_r и .gnu.version_d. Остальные таблицы, sections, notes, dynamic_entries, нужны не самой программе, а внешним инструментам вроде отладчиков; их можно удалить, и программа всё равно запустится, а значит команда strip превращается в транзакцию DELETE и VACUUM. В демонстрации автора «hello»-бинарник после такой чистки уменьшился с 57 344 до 49 152 байт и по-прежнему запускался.

Чтобы ядро Linux вообще могло запустить такой файл, автор использует зарезервированное поле SQLite application_id, 4 байта по смещению 68 в заголовке базы: туда записывается сигнатура «SELF» (0x53454c46), которая отличает такой файл от обычной базы SQLite. Дальше подключается binfmt_misc, подсистема ядра Linux, которая умеет запускать произвольный файл как «нативный», если его байты совпали с зарегистрированной сигнатурой. Для NixOS автор приводит готовый конфиг: система ищет магические байты SQLite по смещению 0 и сигнатуру SELF по смещению 68, а интерпретатором назначает программу self-exec. Готовый ELF-файл в SELF превращает инструмент elf2self, он читает заголовки программы и таблицу символов исходного ELF и переносит их в базу SQLite; на NixOS это подключается как хук postFixup для отдельного пакета. Расширить gcc или ld для прямой генерации SELF автор пока не пытался, сегодня это только пост-обработка уже собранного ELF-файла. Сам self-exec, небольшая C-программа, слинкованная с libsqlite3 и устроенная похоже на ld.so: она так же достаёт заголовки программы и таблицу символов, но не из ELF, а из базы данных, отображает загружаемые сегменты в память, релоцирует их и передаёт управление в точку входа. При этом self-exec обязан сам оставаться обычным ELF-файлом: подпади он тоже под регистрацию SELF, запуск ушёл бы в бесконечную рекурсию с ошибкой ELOOP.

Статическую программу автор запустил быстро, но по-настоящему интересной задачей оказалось динамическое связывание, тут база данных раскрывается полнее. Первый вариант сохраняет ld.so как есть, но подменяет поиск библиотек через интерфейс rtld-audit glibc: библиотека аудита перехватывает каждый поиск объекта ещё до обращения к файловой системе (включая dlopen) и отвечает на вопрос, какая библиотека нужна, SQL-запросом вместо обхода RUNPATH и LD_LIBRARY_PATH; дальше ld.so как обычно отображает файл в память и релоцирует его, поэтому продолжают работать все стандартные механизмы glibc, отложенная привязка через PLT, IFUNC, TLS и версионирование символов, а хранением и поиском библиотек занимаются таблицы и SQL-запросы. В демонстрации автор удаляет .so-файл с диска и всё равно запускает программу: инструмент self scan строит базу зависимостей системы, а переменная окружения LD_AUDIT подключает библиотеку аудита. Второй, более радикальный вариант, self-ld, написанный с нуля динамический линковщик, который целиком реализует поиск и связывание символов на SQL. Автор описывает его как proof-of-concept (черновой прототип для проверки идеи), который тем не менее работает: self-ld отображает сегменты каждого объекта в память, публикует его экспортируемые символы и для каждой релокации патчит GOT, а затем передаёт управление в точку входа, конкретный адрес символа находится одним JOIN-запросом по таблицам relocations, symbols и objects.

Автор напрямую сравнивает SELF с ELF по двум параметрам, которые обычно решают судьбу нового формата, размеру и задержке. По размеру несжатый SELF-файл несёт накладные расходы B-дерева SQLite и получается примерно вдвое больше эквивалентного ELF, но большая часть этого веса приходится на необязательные таблицы для отладки и служебных инструментов, а их удаление, обычная транзакция. После такой чистки coreutils в формате SELF занимает 1 794 048 байт против 1 768 632 байт у ELF-версии, расхождение в пределах 1%, пишет автор. По задержке он прогнал бинарники разного размера, от 15 KiB hello до 42 MiB gdb, слинкованного с 47 библиотеками, и получил фиксированные примерно 5 миллисекунд на открытие SQLite и запуск интерпретатора, плюс копирование, пропорциональное размеру образа. Это копирование обходится дороже, чем кажется: страницы B-дерева не отображаются в память напрямую, поэтому, в отличие от обычного ELF, который отображается в память через mmap, два процесса, запускающие один и тот же SELF-бинарник, не разделяют страницы кода, байты каждый раз копируются из B-дерева, а не отображаются. Из-за этого же curl (274 KiB, 27 библиотек) в замерах автора стартует медленнее, чем ELF-версия git (4,6 MiB, 5 библиотек): время запуска self-exec зависит от числа связываемых объектов, а не от размера в байтах.

Отдельная идея, которую автор успевает наметить дальше в посте, превратить базу SQLite не просто в один исполняемый файл, а в замыкание (в терминологии Nix, closure): единый файл, который несёт в себе программу и все её транзитивные зависимости. Обычный вывод ldd неоднозначен, он называет только имена (soname) нужных библиотек, а не конкретные файлы, которые их удовлетворяют; Nix решает эту проблему, явно прописывая путь к нужному файлу в хранилище через RUNPATH. Автор предлагает делать то же самое внутри SELF: таблица objects хранит путь и soname каждого объекта, а таблица needs, для каждой зависимости конкретный resolved_path, внешний ключ на objects.path, который снимает всякую неоднозначность в том, какая именно библиотека будет подключена.

По статусу всё описанное, рабочий, но ранний прототип одного автора: код выложен на GitHub, ядро идеи компилятор и линковщик пока напрямую не поддерживают (SELF получают только конвертацией уже готового ELF-файла), а более ранняя попытка защитить близкую идею как научную работу успеха не имела.

Ключевые факты

• SELF (Structured Executable & Linkable Format) хранит программу в виде базы SQLite вместо формата ELF: команда file показывает такой файл как «SQLite 3.x database», но он всё равно получает права на выполнение (chmod +x) и запускается как обычный бинарник.
• Чтобы программа запустилась, достаточно двух таблиц, self_meta (заголовок ELF как пары «ключ, значение») и segments (по одной строке на заголовок программы, байты в поле BLOB); таблица symbols с индексом на основе B-дерева SQLite заменяет сразу несколько секций ELF, включая фильтр Блума .gnu.hash.
• Необязательные таблицы (sections, notes, dynamic_entries) можно удалить без вреда для запуска программы, поэтому команда strip превращается в транзакцию DELETE и VACUUM, в демонстрации автора «hello»-бинарник уменьшился с 57 344 до 49 152 байт и по-прежнему работал.
• Файл запускается через подсистему ядра Linux binfmt_misc благодаря сигнатуре «SELF» (0x53454c46), записанной в зарезервированное поле application_id заголовка SQLite; для динамической линковки автор сделал два прототипа, SQL-надстройку rtld-audit поверх штатного ld.so и написанный с нуля линковщик self-ld.
• По замерам автора: несжатый SELF-файл примерно вдвое больше эквивалентного ELF, но после чистки coreutils в формате SELF (1 794 048 байт) укладывается в пределах 1% от ELF-версии (1 768 632 байт); фиксированные около 5 мс уходят на старт интерпретатора, но, в отличие от ELF с mmap, разные процессы одного SELF-бинарника не делят страницы кода в памяти.

Почему это важно

Тезис поста в том, что ELF и так устроен как база данных, только собранная вручную: свой фильтр Блума для поиска символов, свои конструкции для версионирования, свой неформальный контракт вместо схемы. Каждый инструмент, который разбирает ELF, ядро, ld.so, binutils, LIEF, goblin, readelf, заново реализует один и тот же парсер, а каждый производитель файлов пишет свой сериализатор. SQLite убирает этот дубляж: это самоописывающий и при этом стабильный формат, который можно расширять, не ломая существующих потребителей, и который сразу даёт SQL-доступ ко всем данным вместо набора разрозненных утилит. Это не абстрактная идея на бумаге, автор довёл её до работающего прототипа с интерпретатором, конвертером и двумя вариантами динамического линковщика.

Кому это важно

В первую очередь, тем, кто пишет или поддерживает инструменты для разбора и модификации бинарных файлов: авторам отладчиков, анализаторов, линковщиков, упаковщиков пакетов, вместо ручного разбора смещений им предлагается писать SQL-запросы. Отдельно это интересно сообществу Nix и NixOS, на площадке которого построен прототип: автор напрямую переиспользует принцип Nix, явное разрешение пути к каждой зависимости через RUNPATH, для описания SELF-файла со всеми его транзитивными зависимостями внутри одной базы SQLite. В более широком смысле это касается разработчиков компиляторов и системного ПО под Linux, которые сталкиваются с теми же ограничениями формата ELF, о которых пишет автор.

Как это применить

Готовый ELF-файл в SELF превращает инструмент elf2self: он читает заголовки программы и таблицу символов исходного файла и переносит их в базу SQLite; на NixOS это подключается как хук postFixup для отдельного пакета. Чтобы такой файл вообще можно было запустить, нужна регистрация в binfmt_misc, автор приводит готовый конфиг для NixOS, который ищет магические байты SQLite и сигнатуру SELF по фиксированным смещениям и назначает интерпретатором программу self-exec. Для программ с динамическими библиотеками есть два пути: более простой, оставить ld.so как есть и подключить SQL-поиск библиотек через интерфейс rtld-audit glibc и переменную окружения LD_AUDIT; более радикальный, перейти на self-ld, написанный с нуля линковщик, который целиком работает на SQL-запросах. Прямой поддержки в gcc и ld пока нет, сегодня это только конвертация уже собранного ELF-файла, и весь механизм работает только на Linux.

Можно ли доверять

Это единоличный экспериментальный прототип, а не решение, уже встроенное в компилятор, линковщик или ядро Linux: сам автор пишет, что расширять gcc и ld для прямой генерации SELF пока не пытался. Более ранняя попытка формализовать близкую идею как научную работу (sqlelf, статья arXiv:2405.03883) не была принята к публикации. При этом доверие подкрепляется не только словами: код выложен на GitHub, приведены точные размеры файлов до и после очистки (57 344 → 49 152 байт для тестового бинарника, 1 794 048 против 1 768 632 байт для coreutils) и результаты замеров задержки на бинарниках от 15 KiB до 42 MiB. Пост уже вызвал заметную дискуссию на Hacker News, 409 баллов и 83 комментария на момент подготовки материала. Статус при этом остаётся ранним: один автор, без интеграции в существующие системы сборки.

Риски и подводные камни

Главный компромисс, память и производительность: страницы B-дерева SQLite не отображаются в память напрямую, поэтому, в отличие от обычного ELF, который отображается в память через mmap, два процесса, запускающие один и тот же SELF-бинарник, не разделяют страницы кода, каждый раз происходит копирование байт из базы. Несжатый SELF-файл занимает примерно вдвое больше места, чем ELF; это частично лечится тем, что необязательные таблицы для отладки и служебных инструментов можно удалить транзакцией, но по умолчанию накладные расходы есть. Время запуска зависит не от размера файла, а от числа связанных библиотек: в замерах автора curl с 27 библиотеками стартовал медленнее, чем более крупный по байтам git с 5 библиотеками. Есть и структурные ограничения: интерпретатор self-exec обязан сам оставаться обычным ELF-файлом, иначе регистрация в binfmt_misc уйдёт в рекурсию с ошибкой ELOOP; весь механизм завязан на Linux и его специфичные подсистемы, а self-ld, по признанию самого автора, лишь proof-of-concept (черновой прототип для проверки идеи). Вопросы безопасности новой схемы, например, что означает возможность выполнять обычные SQL-операции записи над исполняемым файлом, в посте не поднимаются.

«ELF и так уже является базой данных, просто она реализует многие принципы баз данных вручную.»

— автор поста на fzakaria.com