Неожиданная полнота по Тьюрингу повсюду

в 13:06, , рубрики: FRACTRAN, вычислительная сложность, делегация доверия, ИИ, информационная безопасность, искусственный интеллект, Компьютерное железо, Настольные компьютеры, полнота по Тьюрингу, Процессоры, странные машины, теория алгоритмов, тьюринг-полные системы

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

Приложение

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

Некоторые увязают в спорах о странных машинах или о том, насколько «большим» станет агент ИИ: будет создан один такой, два, десять или миллионы. Неважно, поскольку это просто организационный вопрос. На самом деле важны входы и выходы системы: насколько работоспособна система в целом и какие ресурсы потребляет? Никого не волнует, если 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 и т.д.

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

↑

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

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

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

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

Автор: m1rko

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js