В информатике формальные методы — это математически строгие методы спецификации , разработки, анализа и проверки программных и аппаратных систем. [1] Использование формальных методов проектирования программного и аппаратного обеспечения мотивировано ожиданием того, что, как и в других инженерных дисциплинах, выполнение соответствующего математического анализа может способствовать надежности и устойчивости проекта. [2]
Формальные методы используют различные теоретические основы информатики , включая логические исчисления, формальные языки , теорию автоматов , теорию управления , семантику программ , системы типов и теорию типов . [3]
Полуформальные методы — это формализмы и языки, которые не считаются полностью «формальными». Он откладывает задачу завершения семантики на более поздний этап, который затем выполняется либо посредством человеческой интерпретации, либо посредством интерпретации с помощью программного обеспечения, такого как генераторы кода или тестовых примеров . [4]
Формальные методы могут использоваться на нескольких уровнях:
Дополнительная информация об этом представлена ниже.
Как и в случае семантики языка программирования , стили формальных методов можно грубо классифицировать следующим образом:
Некоторые практики считают, что сообщество формальных методов придаёт слишком большое значение полной формализации спецификации или проекта. [5] [6] Они утверждают, что выразительность используемых языков, а также сложность моделируемых систем делают полную формализацию сложной и дорогостоящей задачей. В качестве альтернативы были предложены различные упрощенные формальные методы, в которых упор делается на частичную спецификацию и целенаправленное применение. Примеры этого облегченного подхода к формальным методам включают нотацию объектного моделирования Alloy , [7] синтез Денни некоторых аспектов нотации Z с разработкой на основе вариантов использования , [8] и инструменты CSK VDM . [9]
Формальные методы могут применяться на различных этапах процесса разработки .
Формальные методы могут использоваться для описания разрабатываемой системы на любом желаемом уровне детализации. Это формальное описание можно использовать для направления дальнейшей деятельности по разработке (см. следующие разделы); кроме того, его можно использовать для проверки того, что требования к разрабатываемой системе были полностью и точно определены, или для формализации системных требований путем выражения их на формальном языке с точным и однозначно определенным синтаксисом и семантикой.
Необходимость в формальных системах спецификаций отмечалась уже много лет. В отчете ALGOL 58 [10] Джон Бэкус представил формальную нотацию для описания синтаксиса языка программирования , позже названную нормальной формой Бэкуса, а затем переименованной в форму Бэкуса-Наура (BNF). [11] Бэкус также писал, что формальное описание значения синтаксически допустимых программ на Алголе не было завершено к моменту включения в отчет. «Поэтому формальная трактовка семантики юридических программ будет включена в следующую статью». Оно так и не появилось.
Формальная разработка — это использование формальных методов как неотъемлемой части процесса разработки системы, поддерживаемого инструментами.
После составления формальной спецификации ее можно использовать в качестве руководства при разработке конкретной системы в процессе проектирования (т. е. обычно реализуемой в программном обеспечении , но также потенциально и в аппаратном обеспечении ). Например:
Формальная проверка — это использование программных инструментов для доказательства свойств формальной спецификации или доказательства того, что формальная модель реализации системы удовлетворяет своей спецификации.
После разработки формальной спецификации ее можно использовать в качестве основы для доказательства свойств спецификации и, как следствие, свойств реализации системы.
Подтверждение подписи — это использование формального инструмента проверки, которому доверяют. Такой инструмент может заменить традиционные методы проверки (инструмент может даже быть сертифицирован).
Иногда мотивацией доказательства правильности системы является не очевидная потребность в подтверждении правильности системы, а желание лучше понять систему. Следовательно, некоторые доказательства правильности производятся в стиле математического доказательства : рукописные (или напечатанные) с использованием естественного языка , с использованием уровня неформальности, обычного для таких доказательств. «Хорошее» доказательство — это доказательство, которое читается и понятно другим читателям.
Критики таких подходов отмечают, что двусмысленность , присущая естественному языку, позволяет не обнаруживать ошибки в таких доказательствах; часто в деталях низкого уровня могут присутствовать тонкие ошибки, которые обычно упускаются из виду при таких доказательствах. Кроме того, работа по созданию такого хорошего доказательства требует высокого уровня математических знаний и опыта.
Напротив, растет интерес к доказательствам корректности таких систем с помощью автоматизированных средств. Автоматизированные методы делятся на три основные категории:
Некоторым автоматизированным средствам доказательства теорем требуется руководство относительно того, какие свойства достаточно «интересны», чтобы их исследовать, в то время как другие работают без вмешательства человека. Специалисты по проверке моделей могут быстро увязнуть в проверке миллионов неинтересных состояний, если им не будет предоставлена достаточно абстрактная модель.
Сторонники таких систем утверждают, что результаты имеют большую математическую достоверность, чем доказательства, созданные человеком, поскольку все утомительные детали были проверены алгоритмически. Обучение, необходимое для использования таких систем, также меньше, чем обучение, необходимое для создания хороших математических доказательств вручную, что делает эти методы доступными для более широкого круга практиков.
Критики отмечают, что некоторые из этих систем подобны оракулам : они провозглашают истину, но не дают объяснения этой истины. Существует также проблема « проверки проверяющего »; если программа, помогающая в проверке, сама по себе не проверена, могут быть основания сомневаться в достоверности полученных результатов. Некоторые современные инструменты проверки моделей создают «журнал доказательства», подробно описывающий каждый шаг доказательства, что позволяет при наличии подходящих инструментов выполнить независимую проверку.
Основная особенность подхода абстрактной интерпретации заключается в том, что он обеспечивает обоснованный анализ, т. е. не дает ложноотрицательных результатов. Более того, его можно эффективно масштабировать за счет настройки абстрактной области, представляющей анализируемое свойство, и применения расширяющих операторов [12] для достижения быстрой сходимости.
Формальные методы применяются в различных областях аппаратного и программного обеспечения, включая маршрутизаторы , коммутаторы Ethernet , протоколы маршрутизации , приложения безопасности и микроядра операционных систем , такие как seL4 . Есть несколько примеров, когда они использовались для проверки функциональности аппаратного и программного обеспечения, используемого в центрах обработки данных . IBM использовала ACL2 , средство доказательства теорем, в процессе разработки процессора AMD x86. [ нужна ссылка ] Intel использует такие методы для проверки своего оборудования и встроенного ПО (постоянное программное обеспечение, запрограммированное в постоянное запоминающее устройство ) [ нужна ссылка ] . Датский центр Datamatik в 1980-х годах использовал формальные методы для разработки системы компилятора для языка программирования Ada , который впоследствии стал долгоживущим коммерческим продуктом. [13] [14]
Есть несколько других проектов НАСА , в которых применяются формальные методы, такие как Воздушно - транспортная система следующего поколения , интеграция беспилотных авиационных систем в национальную систему воздушного пространства [15] и скоординированное разрешение и обнаружение конфликтов с воздуха (ACCoRD). [16] B-метод с Atelier B , [17] используется для разработки автоматики безопасности для различных метрополитенов, установленных по всему миру компаниями Alstom и Siemens , а также для сертификации по общим критериям и разработки системных моделей компаниями ATMEL и STMicroelectronics .
Формальная проверка часто используется в оборудовании большинством известных поставщиков оборудования, таких как IBM, Intel и AMD. Существует много областей аппаратного обеспечения, где Intel использовала формальные методы для проверки работы продуктов, такие как параметризованная проверка протокола когерентности кэша, [18] проверка механизма выполнения процессора Intel Core i7 [19] (с использованием доказательства теорем, BDD и символическая оценка), оптимизация для архитектуры Intel IA-64 с использованием средства доказательства легких теорем HOL [20] и проверка высокопроизводительного двухпортового контроллера Gigabit Ethernet с поддержкой протокола PCI Express и технологии расширенного управления Intel с использованием Cadence. [21] Точно так же IBM использовала формальные методы при проверке силовых вентилей, [22] регистров, [23] и функциональной проверке микропроцессора IBM Power7. [24]
В разработке программного обеспечения формальные методы — это математические подходы к решению проблем программного обеспечения (и аппаратного обеспечения) на уровнях требований, спецификаций и проектирования. Формальные методы, скорее всего, будут применяться к критически важному для безопасности или безопасности программному обеспечению и системам, таким как программное обеспечение авионики . Стандарты обеспечения безопасности программного обеспечения, такие как DO-178C, допускают использование формальных методов путем дополнения, а Общие критерии требуют формальных методов на самых высоких уровнях категоризации.
Для последовательного программного обеспечения примеры формальных методов включают B-Method , языки спецификаций, используемые в автоматизированном доказательстве теорем , RAISE и нотацию Z.
В функциональном программировании тестирование на основе свойств позволило математическую спецификацию и тестирование (если не исчерпывающее тестирование) ожидаемого поведения отдельных функций.
Язык объектных ограничений (и его специализации, такие как язык моделирования Java ) позволили формально определить объектно-ориентированные системы, хотя и не обязательно формально верифицировать их.
Для параллельного программного обеспечения и систем сети Петри , алгебра процессов и конечные автоматы (которые основаны на теории автоматов ; см. также виртуальный конечный автомат или конечный автомат, управляемый событиями ) допускают спецификацию исполняемого программного обеспечения и могут использоваться для создания и проверки поведение приложения.
Другой подход к формальным методам разработки программного обеспечения заключается в написании спецификации в некоторой форме логики (обычно в виде вариации логики первого порядка ) и затем непосредственном выполнении этой логики, как если бы это была программа. Примером может служить язык OWL , основанный на логике описания . Также ведется работа по автоматическому сопоставлению некоторой версии английского (или другого естественного языка) с логикой и обратно, а также непосредственному выполнению логики. Примерами являются Attempto Controlled English и Internet Business Logic, которые не стремятся контролировать словарный запас или синтаксис. Особенностью систем, поддерживающих двунаправленное отображение логики на английском языке и прямое выполнение логики, является то, что их можно заставить объяснять свои результаты на английском языке на деловом или научном уровне. [ нужна цитата ]
Существует множество формальных методов и обозначений.
Многие задачи формальных методов являются NP-трудными , но могут быть решены в случаях, возникающих на практике. Например, булева проблема выполнимости является NP-полной по теореме Кука – Левина , но решатели SAT могут решать множество больших задач. Существуют «решатели» множества задач, возникающих при использовании формальных методов, и периодически проводится множество соревнований по оценке современного состояния решения таких задач. [26]
{{cite journal}}
: Требуется цитировать журнал |journal=
( помощь ){{cite journal}}
: Требуется цитировать журнал |journal=
( помощь )