Какие барьеры мешают широкому распространению формальных методов? [закрыто]

14

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

Почему бы нам не использовать его чаще для повседневного программирования, для веб-приложений и т. Д ...?

Ссылки :

тото
источник
3
Мы могли бы строить дома со стенами толщиной 5 футов - как средневековые замки. В большинстве случаев это будет больше проблем, чем оно того стоит.
Балдрикк
5
Вы можете попробовать применить формальные методы к проекту веб-разработчика и посмотреть, как он работает. Скорее всего, вы заметите, что вы вкладываете много усилий в низкую ценность деятельности. Сравните это с быстрым тестированием дыма, которое уже выявит множество ошибок. Интересно, что статические системы типов - это простой вид системы доказательств, но в особенности веб-разработка избегает этих языков (вместо этого они предпочитают высокодинамичные языки, такие как Ruby, PHP или JavaScript). Корреляция не подразумевает причинно-следственную связь, но она заставляет задуматься.
Амон
1
Итак, вы бы предпочли указывать на языке спецификации вместо программирования на языке программирования? Хорошо, вы сможете доказать, что он работает в соответствии со спецификациями. Но как вы собираетесь доказать, что спецификация отражает истинную проблему?
Кристоф
3
@ к вопросу: делать вещи правильно (работать в соответствии со спецификациями) или делать правильные вещи (имея хорошие спецификации). В то время как в теории спецификация - это то, что мы хотим, на практике мы редко знаем наверняка, что действительно нужно: beyssonmanagement.com/2012/10/29/…
Кристоф
3
Для тех, кто разочарован тем, что это закрыто, теперь есть отличный пост в блоге: почему люди не используют формальные методы?
icc97

Ответы:

19

Инженер - это человек, который может делать с долларом то же, что любой идиот может делать с 10.

Ресурсные ограничения, бюджетные ограничения, временные ограничения, все они важны.

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

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

Йорг Миттаг
источник
1
Я также добавил бы, что введение формальных методов в язык программирования в настоящее время является областью активного исследования, то есть еще не готово для массового использования
jk.
1
Я принимаю этот ответ, но я также хотел найти подход, объясняющий, почему формальные методы по-прежнему считаются «дорогими» и «трудоемкими», особенно когда мы знаем, насколько дорого обходятся обслуживание и отслеживание / отладка кода в больших проектах.
до
1
TDD & BDD - это подходы, основанные на принципах логики Хоара, фундамент формальных подходов. Они улучшают эффективность, не умаляя ее.
Мартин Спамер
1
@toto Доказательства действительно, ДЕЙСТВИТЕЛЬНО трудны. Многое, что математики считают само собой разумеющимся в доказательствах, не применяется в программах. Например, в C ++ сложение не ассоциативно (-1 + 1) + INT_MAX = INT_MAX, -1 + (1 + INT_MAX)это неопределенное поведение.
Ховеркуш
1
@toto: Причина, по которой они считаются «дорогими» и «трудоемкими», заключается в том, что мы можем посмотреть на проекты, разработанные с использованием формальных методов, и эмпирически проверить, что на разработку этих проектов уходит гораздо больше времени. Посмотрите, например, время разработки seL4 / L4.verified по сравнению с любой другой реализацией L4.
Jörg W Mittag
12

Программировать или не программировать?

Чтобы решить проблему с программным продуктом, после понимания требований вы можете ЛИБО написать программу, используя языки программирования, ИЛИ указать программу, используя формальный язык, и использовать инструменты генерации кода. Последний просто добавляет уровень абстракции.

Делать вещи правильно или делать правильные вещи?

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

Требования, над которыми вы работаете, могут быть неполными или неоднозначными. Они могут даже глючить. В худшем случае реальные потребности даже не выражаются. Но картинка стоит тысячи слов, просто изображения Google для «Что хочет клиент», например, из этой статьи :

введите описание изображения здесь

Стоимость формальности

В идеальном мире у вас были бы полностью подробные и совершенные требования с самого начала. Затем вы можете полностью указать свое программное обеспечение. Если вы пойдете на формальный, ваш код будет сгенерирован автоматически, чтобы вы были более продуктивными. Повышение производительности компенсирует стоимость формальных инструментов. И теперь все будут использовать формальные методы. Так почему бы и нет?

На практике это редко бывает реальностью! Вот почему так много проектов с водопадом провалились, и почему итеративные методы разработки (agile, RAD и т. Д.) Взяли на себя инициативу: они могут обрабатывать неполные и несовершенные требования, проекты и реализации и совершенствовать их до тех пор, пока они не будут в порядке.

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

На практике

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

Обновление: измеренное усилие

В октябрьском выпуске Communications of ACM за 2018 год есть интересная статья о официально проверенном программном обеспечении в реальном мире с некоторыми оценками усилий.

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

С другой стороны, для получения программного обеспечения с высокой степенью защиты требуется в 2,3 раза меньше усилий, чем с традиционным программным обеспечением, если вы приложите усилия для сертификации такого программного обеспечения с высоким уровнем безопасности (EAL 7). Так что, если у вас высокие требования к надежности или безопасности, то есть определенное экономическое обоснование для того, чтобы стать формальным.

Разработка seL4 и разработка кода заняли два человека-года. Суммирование всех сероспецифических доказательств за эти годы дает в общей сложности 18 человеко-лет на 8 700 строк кода C. Для сравнения, L4Ka :: Pistachio, еще одно микроядро в семействе L4, сопоставимое по размеру с seL4, потребовалось шесть человеко-лет на разработку и не обеспечивает значительного уровня уверенности. Это означает, что существует только коэффициент 3.3 между проверенным программным обеспечением и программным обеспечением, разработанным традиционным способом . Согласно методу оценки Колберта и Бема 8, традиционная сертификация EAL7 по Common Criteria для 8 700 строк кода C потребует более 45,9 человеко-лет. Это означает, что формальная проверка реализации на двоичном уровне уже более чем в 2,3 раза менее дорогой, чем самый высокий уровень сертификации Common Criteria, но обеспечивает значительно более надежную гарантию.

Christophe
источник
Контрактное программирование использует хотя бы неофициальные доказательства.
Фрэнк Хайлеман
@FrankHileman да! А простой факт выяснения предусловий, постусловий и инвариантов в значительной степени помогает эффективно анализировать код, сокращать количество ошибок и систематизировать тесты.
Кристоф
Это должен быть лучший ответ на сегодняшний день.
Хашим
0

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

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

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

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

Льюис Прингл
источник