Каталог программных конструкций, языков и API, которые неожиданно являются полными по Тьюрингу; последствия этого для безопасности и надёжности. Приложение: сколько компьютеров в вашем компьютере?

Любая достаточно сложная программа на Си или Фортране содержит заново написанную, неспецифицированную, глючную и медленную реализацию половины языка Common Lisp. — Десятое правило Гринспена

Полнота по Тьюрингу (Turing-completeness, TC) — это свойство системы при некотором простом представлении ввода и вывода реализовать любую вычислимую функцию.

Тьюринг-полнота — фундаментальное понятие в информатике. Она помогает ответить на многие ключевые вопросы, например, почему невозможно создание идеальной антивирусной программы. Но в то же время она является поразительно распространённым явлением. Казалось бы, компьютерной системе трудно достичь такой универсальности, чтобы выполнять любую программу, но получается наоборот: трудно написать полезную систему, которая немедленно не обратится в полную по Тьюрингу. Оказывается, что даже небольшой контроль над входными данными и преобразованием их в результат, как правило, позволяет создать тьюринг-полную систему. Это может быть забавным, полезным (хотя обычно нет), вредным или чрезвычайно небезопасным и настоящим подарком для хакера (см. о «теоретико-языковой безопасности», которая изучает методы взлома «странных машин»¹). Удивительные примеры такого поведения напоминают нам о том, что полнота по Тьюрингу таится повсюду, а защитить систему чрезвычайно сложно.

«Слишком мощные» языки программирования тоже могут спровоцировать неприятные DoS-атаки. Фаззер afl нашёл в OpenBSD такой roff, что способен на генерацию бесконечного цикла, злоупотребляя некоторыми правилами подстановки строк.

Вероятно, эти неожиданные примеры тьюринг-полных систем лучше рассматривать как подмножество «обнаруженных» или «найденных» эзотерических языков программирования. Так что эктраординарно минималистичный по своей сути FRACTRAN не считается², как и специально обфусцированный язык Malbolge (где написание тривиальной программы займёт годы), потому что это специально разработанные эзотерические ЯП. Также не входит в наше подмножество игра «Жизнь», потому что вопросы о тьюринг-полноте появились сразу после её выхода, и признание её полной по Тьюрингу не стало сюрпризом. А учитывая сложность сетей с маршрутизацией и коммутацией пакетов неудивительно, что на этих сетях можно построить клеточный автомат или программировать логические схемы, а планирование/валидация авиабилетов — не только NP-трудная и даже EXPSPACE-трудная задача, но и вовсе неразрешимая (из-за сложных правил авиакомпаний).

Многие конфигурации, специальные языки, инструменты или сложные игры, как выясняется, нарушают правило наименьшей власти и «случайно становятся полными по Тьюрингу», как шаблоны MediaWiki, sed или многократное повторение команд regexp/find-replace в редакторе. Вообще, любая форма замены строк или шаблонирования, или компиляции на лету с высокой вероятностью является тьюринг-полной системой сама или при повторении, так как они часто поддерживают лямбда-исчисление или переписывание термов языка или метки, например, эзотерические языки «///» или Thue.

XSLT, Infinite Minesweeper, Dwarf Fortress³, Starcraft, Minecraft, Ant, Transport Tycoon, шаблоны C++ и обобщения Java, ДНК-вычисления и так далее — всё это полные по Тьюрингу системы, и это тоже не удивительно. Многие игры поддерживают скрипты для упрощения разработки и пользовательских модов. Поэтому сделать игру тьюринг-полной элементарно: достаточно включить синтаксис для вызова более известных языков, таких как Perl.

Полнота по Тьюрингу может просто быть малоизвестной частью стандартного формата. Наверное, в наше время многие не знают, что TrueType и многие шрифты — это программы PostScript на стековых машинах, похожие на метаданные ELF и отладочную информацию DWARF. Или что некоторые музыкальные форматы выходят за рамки MIDI, поддерживают скрипты и нуждаются в интерпретации. Если знать о тьюринг-полноте шрифтов, то уже не удивляет полнота по Тюрингу документов TeX, что естественно вызывает многие серьёзные и интересные уязвимости в безопасности шрифтов и медиа, такие как BLEND или Linux-эксплоиты SNES и NES. В других форматах вроде PDF просто ужасное количество уязвимостей⁴. Опять же, выдающиеся достижения вроде создания небольшой машины Тьюринга из кубиков «Лего» или домино⁵, не считаются, поскольку нам уже давно известно, как работают механические компьютеры.

С другой стороны, направление исследований компьютерной безопасности под названием «странные машины» (weird machines) часто выявляет поистине поразительные тьюринг-полные системы. Причём у разных людей они вызывают удивление в разной степени: одним кажется необычным то, что других не удивляет.

• Арифметика Пеано: сложения и умножения натуральных чисел достаточно для полноты по Тьюрингу. Напротив, арифметика Пресбургера лишена умножения и, следовательно, не является полной по Тьюрингу.
• Плитки Вана: разноцветные квадраты, размещение которых задаётся правилом, что соседние стороны двух плиток должны быть одного цвета (исторически понятно для Вана, но система удивила меня, и наверное, многих других людей).
• x86-махинации:
  • MMU тасует RAM, чтобы упростить программирование. Если программа правильно особым образом присвоит адреса в памяти, то сможет выполнять произвольные вычисления на MMU с помощью исключений page-faults (комментарии; научная работа), вообще не запуская сам код. Механизм исключений MMU превращается в компьютер с одной инструкцией.
  • mov является полной по Тьюрингу системой: безобидная на первый взгляд ассемблерная инструкция mov, которая переносит данные между CPU и RAM, позволяет реализовать компьютер с одной инструкцией на триггер-транспортной архитектуре TTA. На таком компьютере можно играть в Doom (в качестве бонуса: и на инструкциях xor тоже).
  • «x86 — тьюринг-полный набор без регистров».
• «Атаки return-into-libc»: программные библиотеки предоставляют предварительно упакованные функции, каждая из которых предназначена для выполнения одной полезной вещи. Из вызовов этих функций можно составить тьюринг-полный «язык», который сможет обойти механизмы безопасности, потому что злоумышленник не запускает собственного узнаваемого кода. Среди многих других примеров, см. «Геометрию невинной плоти на кости: return-into-libc без вызовов функций (на x86)» и «О выразительности атак return-into-libc».
• Pokemon Yellow: «Полный хак управления Pokemon Yellow» описывает атаку с повреждением памяти, которая позволяет создавать произвольные программы на ассемблере Game Boy путём ходьбы туда-сюда и покупки предметов в игре. Есть и аналогичные достижения поклонниками спидрана (скоростного прохождения), но я обычно игнорирую их как «нечистые»: например, можно превратить Super Mario World на SNES в произвольную игру типа «Змейки» или «Понга», но новые программы нужно загружать в дополнительное оборудование. На мой взгляд, это не позволяет назвать Super Mario World «неожиданно» тьюринг-полной системой и отличается от других примеров в этой статье. Например, можно выйти от Super Game Boy к SNES и к произвольному коду, такому как IRC. Это спорное различие.
  • Аналогичная проблема повреждения памяти возникает в printf из POSIX, в опции %n, как и в других библиотечных функциях C (Карлини и др., 2015). Отсюда и «интерпретатор printbf-Brainfuck в printf.
  • Сообщество StarCraft эксплуатировало переполнение буфера в игре для реализации сложных карт, игр жанра «оборонка», игры Mario и редакторов уровней для неё. Эмуляция взлома для защиты модов в обновлённых версиях SC доставила Blizzard много проблем.
• Игра Braid является тьюринг-полной
• Музыкальная нотация с инструкциями для переноса последующих нот становится эзотерическим языком Choon.
• Мышечные клетки сердца (кардиомиоцит) взаимодействуют таким образом, что допускают программирование через логические вентили, следовательно, представляют тьюринг-полную систему (возможно, это не слишком удивительно, ведь клеточные автоматы созданы на биологическом примере)
• Одна категория странных машин считается не совсем тьюринг-полной, поскольку пользователь должен щелкать механическим переключателем или делать единственный возможный выбор, чтобы система перешла на следующий шаг. В данном случае пользователь не вносит никакой логики и не производит вычислений, поэтому такая категория не полностью удовлетворяет определению тьюринг-полных систем:
  • Magic: the Gathering: это тьюринг-полная система, исходя из предположения, что игроки механически соглашаются на предложенный вариант, но в противном случае все действия подчиняются правилам игры
  • CSS разработан как декларативный язык разметки для настройки визуального внешнего вида HTML-страниц, но на декларациях CSS можно закодировать элементарный клеточный автомат Правило 110, который меняет состояние механическими кликами мыши в браузере
  • Анимации Microsoft PowerPoint (исключая макросы, VBScript и т. д.) со специальными связями могут реализовать машину Тьюринга (Вильденхайн, 2017: видео; PPT), если пользователь нажимает на активные триггеры анимации

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

• CSS без щелчков мышью
• SVG: PostScript — это TC по дизайну, но как насчёт более современного формата векторных графических изображений SVG, который написан на XML, то есть на языке документов, который (обычно) не является тьюринг-полным? Похоже, в сочетании с XSLT он всё-таки может быть таковым, но я не нашел никаких доказательств или демонстраций этого в обычном контексте веб-браузера. Стандарт SVG велик и иногда ужасает: неудачная версия стандарта SVG 1.2 пыталась добавить в изображения SVG возможность открытия сетевых сокетов.
• Unicode: Николас Сериот предполагает, что двунаправленные алгоритмы Unicode (предназначенные для отображения письменностей справа налево, таких как арабский или иврит) могут оказаться достаточно сложны для поддержки системы тегов через правила приведения регистра (например, турецкий язык)

См. также

• Внутриплатформенный эффект

Ссылки

• Обсуждение на HN: 1, 2
• Accidentally Quadratic
• «Кодирующие машины»; «Размышления о делегации доверия», Кен Томпсон, 1984
• «Состязательное перепрограммирование нейронных сетей», Эльсайед и др., 2018

Приложение

Сколько компьютеров в вашем компьютере?

Некоторые увязают в спорах о странных машинах или о том, насколько «большим» станет агент ИИ: будет создан один такой, два, десять или миллионы. Неважно, поскольку это просто организационный вопрос. На самом деле важны входы и выходы системы: насколько работоспособна система в целом и какие ресурсы потребляет? Никого не волнует, если Google работает на 50 суперкомпьютерах, 50 000 мейнфреймах, 5 миллионах серверов, 50 млн встроенных/мобильных процессоров или на сочетании всего перечисленного. Неважно, что Google использует разнообразные чипы: от самодельных «тензорных процессоров» до уникальных кремниевых процессоров (Intel реализует их на чипах на процессоры Xeon для ряда крупнейших клиентов), FPGA, GPU, CPU до ещё более экзотического оборудования вроде квантовых компьютеров D-Wave. Важно только, чтобы она сохраняла конкурентоспособность и могла предоставлять услуги за умеренную плату. В конце концов, сегодня суперкомпьютер выглядит обычно как большое количество серверов в стойках с огромным количеством GPU и необычно высокоскоростными соединениями InfiniBand. То есть суперкомпьютер не так уж сильно отличается от дата-центра, как можно подумать. Любое из перечисленного оборудования может поддерживать многочисленные странные машины в зависимости от своей внутренней динамики и связности.

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

Вот пример плохо определённого вопроса: сколько компьютеров сейчас у вас в карманах и на столе? Сколько компьютеров в вашем «компьютере»? Думаете, только один? Давайте посмотрим внимательнее.

Речь идёт не только о CPU: в наше время транзисторы и процессорные ядра настолько дёшевы, что теперь часто имеет смысл выделять отдельные ядра на задачи реального времени, для повышения производительности, для безопасности, чтобы избежать нагрузки на основную ОС, для совместимости со старой архитектурой или существующего программным пакетом. Просто потому что DSP или ядро быстрее запрограммировать, чем создать специализированный ASIC, или потому что это самое простое из возможных решений. Кроме того, многие из этих компонентов могут использоваться в качестве вычислительных элементов, даже если они не предназначены или вообще скрывают эту функциональность.

Итак:

• В обычном процессоре Intel миллиарды транзисторов выполняют множество задач:
  • Каждое из 2−8 основных ядер процессора способно работать независимо, включаясь и выключаясь по мере необходимости, у него собственный кэш (больший, чем RAM в большинстве компьютеров до недавнего времени), и его следует рассматривать как независимый компьютер.
  • CPU в целом перепрограммируется через микрокод, например, для устранения ошибок дизайна микросхем, и щеголяет всё более непрозрачными объектами, такими как Intel Management Engine (с JVM для программирования; Руан, 2014 и SGX) или Platform Security Processor (PSP) от AMD, или Android TEE. Эти аппаратные модули, как правило, являются полноценными компьютерами в собственном праве, работают независимо от хоста и могут вмешиваться в его работу.
  • Любой FPU может стать тьюринг-полной системой через кодирование в операции с плавающей запятой в духе FRACTRAN.
• MMU можно запрограммировать в странную машину page-fault, как упомянуто выше.
• Блоки DSP, кастомные чипы. Наверное, ASIC для видеоформатов вроде h.264 не будут тьюринг-полными системами (несмотря на поддержку сложных дельт и методов сжатия, которые могут допустить нечто вроде плиток Вана). Но вот мобильный SoC Apple A9 выходит далеко за рамки обычного двухъядерного ARM-процессор со встроенным GPU. Как и настольные чипы Intel или AMD, он включает в себя безопасное окружение Secure Enclave (физически выделенные ядра процессора), но также содержит сопроцессор для изображений, сопроцессор для распознавания голоса (частично для поддержки Siri), и, видимо, несколько других ядер. Эти ASIC иногда существуют для задач ИИ и, по-видимому, специализируются на матричных умножениях для нейронных сетей, а поскольку рекуррентные нейронные сети полные по Тьюрингу, то… сами понимаете. Motorola, Qualcomm и другие компании тоже бросились расширять свои SoC.
• BIOS материнской платы и/или чипы управления с доступом к сети.
  • Марк Ермолов отмечает:
    

    «Удивительно, как много разнородных ядер процессора интегрированы в Intel Silvermont Moorefield SoC (ANN): x86, ARC, LMT, 8051, Audio DSP, каждый на своей прошивке и с поддержкой интерфейса JTAG

  Эти чипы управления или отладки могут «случайно» остаться активированными на устройствах после продажи, как встроенный ARM в Via C3 CPU.

• В GPU несколько сотен или тысяч простых ядер, каждое из которых очень хорошо работает с нейронными сетями или выполнять вычисления общего назначения (хотя и медленнее, чем процессор).
• Контроллеры ленточных накопителей, жёстких дисков, флэш-накопителей и SSD обычно работают на процессорах ARM для запуска встроенных утилит для таких задач как скрытие повреждённых секторов от операционной системы. Их можно взломать. Но процессоры ARM используются в большинстве встроенных приложений, поэтому компания ARM любит хвастаться тем, что «современный смартфон содержит от 8 до 14 процессоров ARM, один из которых — процессор приложений (под управлением Android или iOS), а другой — процессор для стека полосы частот (baseband stack)».
• сетевые чипы выполняют независимую обработку для DMA (благодаря такой независимости работают функции вроде Wake-on-LAN для netboot).
• смартфоны: кроме всех упомянутых блоков, есть ещё независимый baseband-процессор, работающий под управлением собственной ОС реального времени для обработки связи с сотовыми вышками/GPS/др. Или даже более одного, если используется виртуализация вроде L4. В baseband-процессорах уже обнаружены бэкдоры, вдобавок к остальным уязвимостям.
• SIM-карты для смартфонов — это гораздо больше, чем просто карты памяти с записью ваших абонентских данных. Это смарт-карты, которые могут независимо запускать приложения Java Card (вероятно, чипы NFC тоже). Это как JVM в IME. Естественно, SIM-карты можно взломать и использовать для слежки и т.д.
• Устройства, подключённые по USB или к материнской плате могут оснащаться собственными процессорами. Например, адаптеры WiFi, клавиатуры, мыши и др. Теоретически, большинство из них изолированы от прямого вмешательства в работу хоста через DMA и IOMMU, но дьявол кроется в деталях…
• случайные странные чипы вроде MacBook Touch под управлением WatchOS.
• …

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

Здесь нет ничего необычного в историческом контексте, ведь даже самые первые мейнфреймы обычно включали в себя несколько компьютеров, где основной компьютер выполняет пакетную обработку, о вспомогательные компьютеры обеспечивают высокоскоростные операции ввода/вывода, которые в противном случае помешают основной машине своими прерываниями.

На практике же, кроме сообщества информационой безопасности (поскольку все эти компьютеры небезопасны и, следовательно, полезны для АНБ и вирусописателей), всем остальным пользователям всё равно, что под капотом наших компьютеров скрываются безумно сложные системы, которые более точно рассматривать как пёстрый зверинец из сотен компьютеров, неловко связанных друг с другом (непонятно, «сеть — это компьютер» или «компьютер — это сеть»…?). Пользователь воспринимает и использует это как один компьютер.

---

1. Активная область исследований — создание языков и систем, которые тщательно спроектированы и гарантированно не являются тьюринг-полными (например. тотально функциональное программирование). Зачем прилагать столько усилий для создания языка, на котором невозможно написать многие программы? Дело в том, что полнота по Тьюрингу тесно связана с теоремой Гёделя о неполноте и теоремой Райса. Поэтому если разрешить TC, то мы теряем всевозможные свойства доказуемости. Наоборот, в не полном по Тьюрингу языке легко доказываются разные полезные вещи: например, что программа завершена, типобезопасная она или нет, что её легко преобразовать в логическую теорему, что она потребляет ограниченное количество ресурсов, что реализация протокола верна или эквивалентна другой реализации. Легко доказывается отсутствие побочных эффектов и что программу можно преобразовать в логически эквивалентный, но более быстрый вариант (это особенно важно для декларативных языков вроде SQL, где способность оптимизатора преобразовать запросы — ключ к приемлемой производительности. Хотя, конечно, на SQL можно делать удивительные вещи, такие как градиентный спуск для моделей машинного обучения, а некоторые расширения SQL делают его тьюринг-полным в любом случае, позволяя либо закодировать циклическую систему тегов, либо model DSL, либо вызвать PL/SQL и т.д.

Вот некоторая литература о странных машинах:

• «Программирование эксплоитов: от переполнений буфера до странных машин и теории вычислений», Братус и др., 2011
• «Проблема остановки в безопасности сетевого стека», Сассамэн и др., 2011
• «Странная машина Page-Fault: уроки вычислений без инструкций», Бангерт и др., 2013
• «Странные машины в ELF: фокус на недооценённые метаданные», Shapiro et al 2013
• «Ориентированное на прерывания программирование багдоров: минималистический подход к внедрение багдоров в прошивки встроенных систем», Тан и др., 2014
• «Странные машины в доказательном коде», Ванег, 2014
• «Сигналы цикловой синхронизации — возвращение к портируемому шеллкоду», Босман и Бос, 2014

↑

2. Хотя линейные нейросети эксплуатируют режим плавающей точкой с округлением до нуля для кодирования потенциально тьюринг-полного поведения (для RNN), но это незаметно в нормальной работе, что одновременно является случайным тьюринг-полным поведением и наглядным примером безопасного языка. ↑

3. Dwarf Fortress даёт часовые механизмы, поэтому полнота по Тьюрингу неудивительна. Но и вода реализована как простой клеточный автомат, поэтому есть даже больше способов получить тьюринг-полноту! Сейчас игровая вики называет четыре потенциальных способа создания логических вентилей: жидкости, механизмы часового механизма, минные тележки и логические вентили существ/животных с участием дверей и датчиков давления. ↑

4. Полная спецификация PDF исключительно раздута. Например, в простой программе просмотра PDF с поддержкой достаточного количества спецификации PDF, как браузер Google Chrome, можно играть в Breakout (потому что PDF включает собственное странное подмножество JavaScript). Официальная программа просмотра Adobe PDF поддерживает функциональность вплоть до трёхмерного САПР. ↑

5. См. логические вентили из домино на Think Math и демо 4-битного сумматора из костяшек домино. ↑