Можно ли программно оценить безопасность для произвольного кода?

В последнее время я много думал о безопасном коде. Потокобезопасна. Память-сейф. Сейф, который нельзя взорвать в вашем лице. Но для ясности в этом вопросе давайте используем модель безопасности Rust в качестве нашего определения.

Зачастую обеспечение безопасности представляет собой небольшую проблему, потому что, как показывает потребность Rust unsafe, существуют некоторые очень разумные идеи программирования, такие как параллелизм, которые нельзя реализовать в Rust без использования unsafeключевого слова. , Даже если параллелизм можно сделать совершенно безопасным с помощью блокировок, мьютексов, каналов и изоляции памяти или чего-то еще, для этого требуется работа вне модели безопасности Rust с unsafeпоследующим ручным заверением компилятора, что: «Да, я знаю, что делаю Это выглядит небезопасно, но я математически доказал, что это совершенно безопасно ".

Но, как правило, это сводится к тому, чтобы вручную создавать модели этих вещей и доказывать, что они безопасны с помощью доказателей теорем . Как с точки зрения компьютерной науки (возможно ли это), так и с точки зрения практичности (собирается ли она взять жизнь вселенной), разумно ли представить программу, которая принимает произвольный код на произвольном языке и оценивает, действительно ли это " Ржавчина безопасна "?

Предостережения :

• Легко сказать, что программа может быть небрежной, и поэтому проблема с остановкой нам не помогает . Допустим, любая программа, поданная к читателю, гарантированно остановится
• Хотя целью является «произвольный код на произвольном языке», я, конечно, осознаю, что это зависит от того, насколько программа знакома с выбранным языком, который мы примем как данность.

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

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

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

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

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

Другим хорошим примером может быть то, что пустые значения могут быть частью языка, поскольку исключения пустых указателей могут произойти, если вы разрешите пустые значения. Некоторые языки полностью устранили эту проблему, запретив переменным, которые не были явно объявлены, содержать пустые значения для объявления без немедленного присвоения значения (например, Kotlin). Хотя вы не можете устранить ошибку времени выполнения исключения нулевого указателя, вы можете предотвратить ее возникновение, удалив динамическую природу языка. В Kotlin вы, конечно, можете принудительно устанавливать нулевые значения, но само собой разумеется, что это метафорический «покупатель, остерегайтесь», поскольку вы должны явно заявить об этом.

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

Возвращаясь к вашей основной точке. Методы не являются автоматически потокобезопасными. Для этого есть практическая причина, которая заключается в том, что безопасные для потоков методы также медленнее, даже когда потоки не используются. Rust решает, что они могут устранить проблемы во время выполнения, сделав методы потокобезопасными по умолчанию, и это их выбор. Это приходит по цене, хотя.

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

Система типов - это автоматически проверяемые доказательства некоторых аспектов правильности. Например, система типов Rust может доказать, что ссылка не переживает ссылочный объект или что ссылочный объект не изменен другим потоком.

Но системы типов довольно ограничены:

• Они быстро сталкиваются с проблемами разрешимости. В частности, сама система типов должна быть разрешимой, однако многие практические системы типов случайно завершаются по Тьюрингу (включая C ++ из-за шаблонов и Rust из-за особенностей). Кроме того, определенные свойства программы, которую они проверяют, могут быть неразрешимыми в общем случае, наиболее вероятно, останавливается ли какая-либо программа (или расходится).

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

Из-за этих ограничений системы типов имеют тенденцию проверять только довольно слабые свойства, которые легко доказать, например, что функция вызывается со значениями правильного типа. Но даже это существенно ограничивает выразительность, поэтому обычно есть обходные пути (как interface{}в Go, dynamicв C #, Objectв Java, void*в C) или даже используются языки, которые полностью избегают статической типизации.

Чем сильнее мы проверяем свойства, тем менее выразительным будет язык. Если вы написали Rust, вы будете знать эти моменты «борьбы с компилятором», когда компилятор отклоняет, казалось бы, правильный код, потому что он не смог доказать правильность. В некоторых случаях невозможно выразить определенную программу в Rust, даже если мы считаем, что можем доказать ее правильность. unsafeМеханизм в Русте или C # позволяет избежать границ системы типа. В некоторых случаях откладывание проверок до времени выполнения может быть другим вариантом - но это означает, что мы не можем отклонить некоторые недействительные программы. Это вопрос определения. Программа Rust, которая паникует, безопасна для системы типов, но не обязательно с точки зрения программиста или пользователя.

Языки разрабатываются вместе с их системой типов. Редко когда новая система типов навязывается существующему языку (но см., Например, MyPy, Flow или TypeScript). Язык попытается упростить написание кода, который соответствует системе типов, например, предлагая аннотации типов или вводя легко проверяемые структуры потока управления. У разных языков могут быть разные решения. Например, в Java есть концепция finalпеременных, которые назначаются ровно один раз, аналогично mutпеременным Rust :

final int x;
if (...) { ... }
else     { ... }
doSomethingWith(x);

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

let x = if ... { ... } else { ... };
do_something_with(x)

Это выглядит как незначительный момент при определении назначения, но четкое определение объема чрезвычайно важно для доказательств, связанных с жизнью.

Если бы мы применили систему типов в стиле Rust к Java, у нас были бы гораздо большие проблемы: объекты Java не снабжены временами жизни, поэтому нам пришлось бы рассматривать их как &'static SomeClassили Arc<dyn SomeClass>. Это ослабит все полученные доказательства. Java также не имеет понятия типа уровня неизменности поэтому мы не можем различать &и &mutтип. Нам пришлось бы рассматривать любой объект как ячейку или мьютекс, хотя это может предполагать более строгие гарантии, чем на самом деле предлагает Java (изменение поля Java не является поточно-ориентированным, если оно не синхронизировано и не изменчиво). Наконец, у Rust нет концепции наследования реализации в стиле Java.

TL; DR: системы типов являются доказателями теорем. Но они ограничены проблемами решимости и проблемами производительности. Вы не можете просто взять одну систему типов и применить ее к другому языку, так как синтаксис языка цели может не предоставлять необходимую информацию, а семантика может быть несовместимой.

Насколько безопасно безопасно?

Да, почти можно написать такой верификатор: ваша программа просто должна возвращать константу UNSAFE. Вы будете правы в 99% случаев

Потому что даже если вы запускаете безопасную программу Rust, кто-то может отключить ее во время ее выполнения: так что ваша программа может остановиться, даже если теоретически это не предполагается.

И даже если ваш сервер работает в клетке Фарадея в бункере, соседний процесс может выполнить эксплойт с молотком и немного перевернуть одну из ваших предположительно безопасных программ на Rust.

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

Шутка в сторону, автоматическая проверка

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

Этот вид анализа, кстати, также выполняется некоторыми компиляторами для оптимизации.

Конечно, можно пойти еще дальше, а также проанализировать параллелизм и сделать выводы о распространении ограничений по нескольким потокам, условиям синхронизации и гонок. Однако очень быстро вы столкнетесь с проблемой комбинаторного разрыва между путями выполнения и многими неизвестными (ввод-вывод, планирование ОС, ввод пользователя, поведение внешних программ, прерывания и т. Д.), Которые ослабят известные ограничения до их полной свести к минимуму и сделать очень трудно делать какие-либо полезные автоматические выводы по произвольному коду.

Тьюринг обратился к этому вопросу еще в 1936 году со своим докладом о проблеме остановки. Одним из результатов этого является то, что просто невозможно написать алгоритм, который в 100% случаев может анализировать код и правильно определить, остановится он или нет, невозможно написать алгоритм, который может в 100% случаев правильно определить, имеет ли код какое-либо конкретное свойство или нет, включая «безопасность», как бы вы ни хотели его определить.

Тем не менее, результат Тьюринга не исключает возможности программы, которая может в 100% случаев либо (1) абсолютно определить, что код безопасен, (2) абсолютно определить, что код небезопасен, либо (3) антропоморфно поднять руки и сказать «Черт, я не знаю». Компилятор Rust, вообще говоря, находится в этой категории.

Если программа полная (техническое название программы, которая гарантированно останавливается), то теоретически возможно доказать любое произвольное свойство программы при наличии достаточных ресурсов. Вы можете просто изучить каждое потенциальное состояние, в которое может войти программа, и проверить, нарушает ли какое-либо из них вашу собственность. Язык проверки модели TLA + использует вариант этого подхода, используя теорию множеств для проверки ваших свойств по наборам потенциальных состояний программы, а не для вычисления всех состояний.

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

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

Таким образом, подавляющее большинство исследований сосредоточено на доказательствах. Соответствие Карри-Говарда утверждает, что доказательство правильности и система типов - это одно и то же, поэтому большая часть практических исследований проводится под названием системы типов. Особенно актуальными для этой дискуссии являются Coq и IdrissВ дополнение к Rust, о котором вы уже упоминали. Coq подходит к основной инженерной проблеме с другой стороны. Принимая доказательства правильности произвольного кода на языке Coq, он может генерировать код, который выполняет проверенную программу. В то же время Идрисс использует систему зависимых типов для доказательства произвольного кода на чистом языке, подобном Хаскеллу. То, что делают оба этих языка, это выдвигает трудные проблемы генерации работоспособного доказательства на писателя, позволяя контролеру типов сосредоточиться на проверке доказательства. Проверка доказательства - намного более простая проблема, но это делает языки более трудными для работы.

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