Как curl девять месяцев случайно был Тьюринг-полным

Утилита curl славится тем, что умеет почти всё, что связано с передачей данных по сети. Как выяснил Николя Сериó, какое-то время она умела и вообще всё, по крайней мере в теоретическом смысле. С версии 8.12 по 8.16 конфигурационные файлы curl составляли Тьюринг-полную систему.

Откуда взялась полнота

Сложились две возможности. Первая позволяет брать срез значения переменной по диапазону байтов. Вторая позволяет подключать из конфигурационного файла другие такие файлы, причём без явного ограничения глубины. Вместе их хватает, чтобы смоделировать любую программу для двухсчётчиковой машины Минского. При обычной идеализации, то есть с неограниченной длиной строк и неограниченными ресурсами, такая машина Тьюринг-полна.

Конструкция устроена так:

• значение счётчика n хранится в переменной как n символов x;
• инкремент дописывает к строке ещё один x, декремент отрезает первый байт срезом [1-];
• условный переход берёт срезом [0-0] первый байт, то есть либо x, либо пустую строку, и через expand-config подключает файл state_.conf или state_x.conf;
• безусловный переход сводится к подключению нужного файла, а остановка означает, что дальше ничего не подключается.

Имена файлов играют роль меток, и любую программу с двумя счётчиками можно «скомпилировать» в набор конфигов curl. В качестве доказательства автор приводит четыре файла, которые складывают 2 и 3. Если собрать curl 8.12.0 и запустить его с -K main.conf, программа выводит A=xxxxx B=. Сеть для этого не нужна.

Реальные ограничения

На практике бесконечности, конечно, не было. Каждое раскрытие ограничено 10 000 000 байт, это собственный лимит curl. Цикла в конструкции нет: каждый шаг представляет собой вложенный вызов --config, который возвращает управление только при остановке. Значит, каждый шаг занимает кадр стека и держит файл открытым. В минимальном цикле обратного отсчёта на стеке размером 8 МБ удалось выполнить 922 шага, после чего процесс упал с segfault. Кроме того, старые версии переменных при переприсваивании сохраняются до очистки, поэтому потребление памяти растёт с каждым шагом.

Хронология

Переменные появились в curl 8.3 в сентябре 2023 года, присваивание по диапазону байтов добавили в 8.12 в феврале 2025-го. В 8.17 в ноябре 2025-го ввели ограничение в пять уровней вложенности, и сведение перестало работать. Согласно pull request, ограничение защищает от бесконечного самовключения конфига. Регрессионный тест именно это и проверяет. О Тьюринг-полноте и о том, почему уровней именно пять, публичное объяснение не говорит.

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

Влияние на безопасность автор оценивает одним словом: никакого.

Источник: Lobsters