Общая картина формальной проверки в программном обеспечении

Question

Я пытаюсь собрать общую картину состояния формальной проверки программного обеспечения, и у меня хорошая проблема. Для контекста я прихожу из основного математического фона. Я вполне знаком с состоянием автоматизированной теоремы и доказательными помощниками в отношении их использования для доказательства хорошо сформированных математических утверждений (например, в кок, Изабель, склоняется и т. Д.). То, что у меня проблемы с пониманием - это то, что происходит с «формальными методами» в практических приложениях CS.

Я обнаружил, что такие компании, как Microsoft и AWS, использовали TLA + как «формальный метод» в своем разработке программного обеспечения несколько существенно. Но когда я начал читать книгу Partive TLA + > $ с записями между 1 и $ n $ для некоторых фиксированных $ n $ , т.е. мы просто проверяем конечно много случаев и говорим, что поэтому алгоритм должен работать в целом. Это не кажется особенно интересным; просто пример особо строгого тестирования подразделения. Примечательно, что это не формальное доказательство правильности.

С другой стороны, я видел шум о Isabelle и Coq, чтобы доказать вещи о программном обеспечении, как они могут доказать математические теоремы. Хотя, когда я смотрю в книги, которые, кажется, обещают это, например, Chlipala's Сертифицированное программирование с зависимыми типами , я вижу много абстрактных вещей, которые, кажется, смутно относятся к формально проверки программ, но никаких примеров принимает реальную программу, написанную на языке, который имеет широкое использование (например, C ++ , Python, Java и т. Д.) Или даже просто псевдокод и «проверка его», что бы это ни значило.

Может кто-нибудь попытается прояснить мою путаницу?

Answer 1

формально проверенная программа - это формально проверенная программа, независимо от того, какой язык он находится. Точно потому, что программа написана в CoQ и, возможно, извлечен к Ocaml или haskell, а не написано более" предпринимаемым "языком, таким как c ++ или java, не делает его меньшее из программы.

Доказательные программы, написанные в языках программирования общего назначения, даже «ручные» такие как haskell, сложно, потому что эти языки обычно включают много удобств, темных углов для производительности и интерфейса с операционной системой, и богатыми и сложными Библиотеки. Чтобы доказать свойство программы, сначала необходимо указать это свойство, и оператор встраивает семантику языка, в которой программа написана. Когда вы пытаетесь формализовать языки, которые были изначально разработаны без формальной семантики (что почти Все они), вы очень быстро попали в темные углы, которые английское описание листья невыразится, или где он неоднозначен, или где он прямой самоопределяющий, или где справочная реализация не делает то, что говорит описание, и это считается ошибкой в английский, а не в реализации. Состояние искусства доказывания свойств программ, написанных на предкисительском языке, заключается в ограничениях программ в подмножество языка.

Что идет в это подмножество, очень переменная. Синтаксический сахар не слишком сложен: семантика просто нужно перевести его в более простые конструкции. Свойства отражения не особенно сложны для моделирования, но могут сделать модель намного сложнее рассуждать (например, она недействительна свойства, такие как «этот фрагмент кода, не имеет никакого способа ссылаться на эту переменную, поэтому она не может Измените его значение «), так что многие рамки исключают это. Взаимодействия с операционной системой (обычно через библиотеки) являются проблематичными, поскольку они требуют моделирования операционной системы, которая будет чрезвычайно сложной. Операции с плавающей точкой трудно, потому что отслеживание приближений в последовательных операциях вызывает огромный взрыв.

для C, один из главных крупных подмножеств с формальной моделью является Compcert C, язык compcert Compcert - это формально проверенный компилятор (написанный в CoQ), поэтому, если вы докажете свойство программы C, вы можете дополнительно получить доказательство сгенерированного машинного кода. Compcert C является очень большим подмножеством C99, но формализация исключает большую часть стандарта библиотека и некоторые причуды языка.

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

Это довольно распространено, что окончательная программа не написана вручную, но механически извлечена с языка более высокого уровня. Например, написание CoQ, которое извлечено в Ocaml или написание f * , который добывается в C. Но Противоположный подход также возможен, например, написание («ручные») c, аннотация его со свойствами функций и других подразделений кода, а также использование FRAMA-C Чтобы доказать эти свойства (и подразумеваемое свойство, которое программа C не имеет неопределенного поведения).

Если у вас есть формальная семантика языка программирования и способ выражения свойств программ, доказывая эти свойства, является математической теоремой. Как правило, эти теоремы не связаны с любой сложной математикой, такой как исчисление (если не привезены доменом приложений, например, отслеживание движения физического объекта), но их трудно доказать, что включает в себя очень большие формулы и содержат арифметические заявления ( $ x ^ n + y ^ n= z ^ n $ не является сложным уравнением, но решение его не элементарно!). Это Теоретически невозможно написать программу, которая может доказать нетривиальное семантическое свойство всех программ И практически невозможно написать программу, которая может доказать много интересных свойств типичных программ. Формальная проверка включает в себя комбинацию нарушения задачи в достаточно небольшие шаги (написание небольших функций и достаточное количество точных свойств этих функций), наличие инструмента автоматически доказать некоторые из этих свойств (такие

Как a SAT Solver для пропозициональной логики), а имеющие у людей, которые могут писать доказательства, где компьютер может Это делаю (но компьютер проверит доказательство человека). Доказательными помощниками, такие как Coq и Isabelle, приходят для этого последнего шага.

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

Если мы просто проверяем, скажем, алгоритм сортировки в списках длины

Это не будет формальным доказательством, если программа не имела предел n элементов для его ввода. Я не знаю эту книгу, но я подозреваю, что вы что-то неправильно. Формально проверка программы сортировки будет включать доказательство его правильности для всех N.