Формальные методы - Formal methods

В Информатика в частности программная инженерия и аппаратная инженерия, формальные методы особый вид математически строгие методы для Технические характеристики, развитие и проверка из программного обеспечения и оборудование системы.[1] Использование формальных методов для проектирования программного и аппаратного обеспечения мотивировано ожиданием того, что, как и в других инженерных дисциплинах, выполнение соответствующего математического анализа может способствовать надежности и устойчивости проекта.[2]

Формальные методы лучше всего охарактеризовать как применение довольно широкого разнообразия теоретическая информатика основы, в частности логика исчисления формальные языки, теория автоматов, дискретная событийная динамическая система и семантика программы, но также системы типов и алгебраические типы данных к проблемам в спецификации и проверке программного и аппаратного обеспечения.[3]

Задний план

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

Таксономия

Формальные методы могут использоваться на нескольких уровнях:

Уровень 0: Формальная спецификация может быть предпринята, а затем неформально разработана программа. Это было дублировано формальные методы lite. Во многих случаях это может быть наиболее рентабельным вариантом.

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

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

Дополнительная информация об этом расширена ниже.

Как и с семантика языка программирования стили формальных методов можно условно классифицировать следующим образом:

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

Легкие формальные методы

Некоторые практики считают, что сообщество формальных методов переоценило полную формализацию спецификации или дизайна.[5][6] Они утверждают, что выразительность задействованных языков, а также сложность моделируемых систем делают полную формализацию сложной и дорогостоящей задачей. В качестве альтернативы различные легкий были предложены формальные методы, которые подчеркивают частичную спецификацию и целенаправленное применение. Примеры этого облегченного подхода к формальным методам включают Сплав обозначение объектного моделирования,[7] Синтез Денни некоторых аспектов Обозначение Z с участием вариант использования управляемое развитие,[8] и ЦСК VDM Инструменты.[9]

Использует

Формальные методы могут применяться на различных этапах через процесс разработки.

Технические характеристики

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

Потребность в формальных системах спецификаций отмечалась годами. в АЛГОЛ 58 отчет[10] Джон Бэкус представил формальную нотацию для описания синтаксиса языка программирования, позже названного Бэкус нормальная форма затем переименован Форма Бэкуса – Наура (БНФ).[11] Бэкус также писал, что формальное описание значения синтаксически корректных программ на АЛГОЛе не было завершено вовремя для включения в отчет. «Поэтому формальная трактовка семантики юридических программ будет включена в следующую статью». Так и не появилось.

Развитие

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

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

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

Проверка

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

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

Подтверждение подписи

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

Человеческое доказательство

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

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

Автоматическое доказательство

Напротив, растет интерес к получению доказательств правильности таких систем с помощью автоматизированных средств. Автоматизированные методы делятся на три основные категории:

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

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

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

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

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

Приложения

Формальные методы применяются в различных областях аппаратного и программного обеспечения, включая маршрутизаторы, коммутаторы Ethernet, протоколы маршрутизации, приложения безопасности и микроядра операционной системы, такие как seL4. Есть несколько примеров, в которых они использовались для проверки функциональности оборудования и программного обеспечения, используемых в контроллерах домена.[требуется разъяснение ]. IBM используемый ACL2, доказатель теорем, в AMD Процесс разработки процессора x86.[нужна цитата ] Intel использует такие методы для проверки своего оборудования и прошивки (постоянное программное обеспечение, запрограммированное в постоянную память).[нужна цитата ]. Данск Датаматик Центр использовал формальные методы в 1980-х годах для разработки системы компиляции для Язык программирования Ада который стал долгоживущим коммерческим продуктом.[13][14]

Есть еще несколько проектов НАСА в которых применяются формальные методы, такие как Система воздушного транспорта нового поколения[нужна цитата ], Интеграция системы беспилотных летательных аппаратов в национальную систему воздушного пространства,[15] и скоординированное разрешение и обнаружение конфликтов с помощью воздушных судов (ACCoRD).[16]B-метод с участием Ателье Б,[17] используется для разработки автоматов безопасности для различных метрополитенов, установленных по всему миру. Alstom и Сименс, а также для сертификации Common Criteria и разработки моделей системы АТМЕЛ и STMicroelectronics.

Формальная проверка часто используется в оборудовании большинством известных поставщиков оборудования, таких как IBM, Intel, и AMD. Есть много областей аппаратного обеспечения, в которых Intel использует FM для проверки работы продуктов, таких как параметризованная проверка согласованного с кешем протокола,[18] Проверка механизма выполнения процессора Intel Core i7 [19] (используя доказательство теорем, BDD, и символическая оценка), оптимизация для архитектуры Intel IA-64 с использованием средства доказательства теорем HOL Light,[20] и проверка высокопроизводительного двухпортового контроллера Gigabit Ethernet с поддержкой протокола PCI Express и передовой технологии управления Intel с использованием Cadence.[21] Точно так же IBM использовала формальные методы для проверки силовых ворот,[22] регистры,[23] и функциональная проверка микропроцессора IBM Power7.[24]

В разработке программного обеспечения

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

Для последовательного программного обеспечения примеры формальных методов включают B-метод, языки спецификации, используемые в автоматическое доказательство теорем, ПОДНЯТЬ, а Обозначение Z.

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

В Язык объектных ограничений (и такие специализации, как Язык моделирования Java ) позволил формально специфицировать объектно-ориентированные системы, если не обязательно формально верифицировать.

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

Другой подход к формальным методам разработки программного обеспечения - это написание спецификации в некоторой форме логики - обычно это вариант логика первого порядка (FOL) - а затем напрямую выполнять логику, как если бы это была программа. В СОВА язык, основанный на Описание Логика (DL), является примером. Также ведется работа по автоматическому отображению некоторой версии английского (или другого естественного языка) на логику и обратно, а также прямое выполнение логики. Примеры Попытка контролируемого английского и Internet Business Logic, которые не стремятся контролировать словарный запас или синтаксис. Особенностью систем, поддерживающих двунаправленное отображение логики на английском языке и прямое выполнение логики, является то, что их можно заставить объяснять свои результаты на английском языке на деловом или научном уровне.[нужна цитата ]

Формальные методы и обозначения

Доступно множество формальных методов и обозначений.

Языки спецификации

Модельные шашки

Основная статья: Список инструментов проверки модели

Организации

Главная страница: Категория: Формальные методы организации

Смотрите также

использованная литература

  1. ^ Батлер, Р. В. (2001-08-06). "Что такое формальные методы?". Получено 2006-11-16.
  2. ^ Холлоуэй, С. Майкл. «Почему инженерам следует использовать формальные методы» (PDF). 16-я Конференция по системам цифровой авионики (27-30 октября 1997 г.). Архивировано из оригинал (PDF) 16 ноября 2006 г.. Получено 2006-11-16. Цитировать журнал требует | журнал = (Помогите)
  3. ^ Монин, стр.3-4
  4. ^ X2R-2, поставка D5.1.
  5. ^ Дэниел Джексон и Жаннетт Винг, «Легкие формальные методы», IEEE Computer, Апрель 1996 г.
  6. ^ Вину Джордж и Рэйфорд Вон, «Применение упрощенных формальных методов в разработке требований» В архиве 2006-03-01 на Wayback Machine, Перекрестные помехи: журнал оборонной программной инженерии, Январь 2003 г.
  7. ^ Дэниел Джексон, «Сплав: обозначение для моделирования легких объектов», ACM Transactions по разработке программного обеспечения и методологии (TOSEM), Том 11, Выпуск 2 (апрель 2002 г.), стр. 256-290
  8. ^ Ричард Денни, Успешное использование сценариев использования: разумная работа для обеспечения качества, Addison-Wesley Professional Publishing, 2005 г., ISBN  0-321-31643-6.
  9. ^ Стен Агерхольм и Питер Г. Ларсен, «Облегченный подход к формальным методам» В архиве 2006-03-09 на Wayback Machine, В Материалы международного семинара по современным тенденциям в прикладных формальных методах, Боппард, Германия, Springer-Verlag, октябрь 1998 г.
  10. ^ Backus, J.W. (1959). "Синтаксис и семантика предлагаемого международного алгебраического языка Цюрихской конференции ACM-GAMM". Материалы Международной конференции по обработке информации. ЮНЕСКО.
  11. ^ Кнут, Дональд Э. (1964), Нормальная форма Бэкуса против формы Бэкуса Наура. Коммуникации ACM, 7(12):735–736.
  12. ^ А. Кортези и М. Заниоли, Операторы расширения и сужения для абстрактной интерпретации. Компьютерные языки, системы и структуры. Том 37 (1), стр. 24–42, Elsevier, ISSN  1477-8424 (2011).
  13. ^ Бьёрнер, Дайнс; Грамм, Кристиан; Oest, Ole N .; Rystrøm, Лейф (2011). "Данск Датаматик Центр". В Impagliazzo, Джон; Лундин, Пер; Wangler, Benkt (ред.). История Nordic Computing 3: достижения IFIP в области информационных и коммуникационных технологий. Springer. С. 350–359.
  14. ^ Бьёрнер, Дайнс; Хавелунд, Клаус. «40 лет формальных методов: некоторые препятствия и некоторые возможности?». FM 2014: формальные методы: 19-й международный симпозиум, Сингапур, 12–16 мая 2014 г. Протоколы (PDF). Springer. С. 42–61.
  15. ^ Георге, А. В., и Ансель, Э. (2008, ноябрь). Интеграция беспилотных авиационных систем в Национальную систему воздушного пространства. В области «Инфраструктурные системы и услуги: построение сетей для более светлого будущего» (ИНФРА), Первая международная конференция 2008 г. (стр. 1-5). IEEE.
  16. ^ Скоординированное разрешение и обнаружение конфликтов с помощью воздушных судов, http://shemesh.larc.nasa.gov/people/cam/ACCoRD/
  17. ^ "Ателье Б". www.atelierb.eu.
  18. ^ К. Т. Чоу, П. К. Маннава, С. Парк, "Простой метод параметризованной проверки протоколов согласованности кеша ”, Формальные методы в автоматизированном проектировании, стр. 382–398, 2004.
  19. ^ Официальная проверка в процессе проверки механизма выполнения процессора Intel® Core ™ i7, http://cps-vo.org/node/1371, просмотрено 13 сентября 2013 г.
  20. ^ Дж. Гранди, «Проверенные оптимизации для архитектуры Intel IA-64», Доказательство теорем в логике высокого порядка, Springer Berlin Heidelberg, 2004 г., стр. 215–232.
  21. ^ Э. Селигман, И. Яром,Наиболее известные методы использования Cadence Conformal LEC ”, В Intel.
  22. ^ К. Эйснер, А. Нахир, К. Йорав, “Функциональная проверка конструкций с силовыми вентилями с помощью композиционных соображений ”, Компьютерная проверка, Springer Berlin Heidelberg, стр. 433–445.
  23. ^ П. К. Атти, Х. Чоклер, "Автоматическая проверка отказоустойчивых эмуляций регистров ”, Электронные заметки по теоретической информатике, т. 149, нет. 1. С. 49–60.
  24. ^ К. Д. Шуберт, В. Рознер, Дж. М. Лудден, Дж. Джексон, Дж. Бухерт, В. Парути, Б. Брок, «Функциональная проверка микропроцессора IBM POWER7 и многопроцессорной системы POWER7 ”, IBM Journal of Research and Development, vol. 55, № 3.
  25. ^ «ESBMC». esbmc.org.

дальнейшее чтение

внешние ссылки

Архивные материалы