Формальные методы тесно связаны с математическими техниками спецификаций, верификацией и доказательством правильности программ. Эти методы содержат математическую символику, формальную нотацию и аппарат вывода. Правила доказательства громоздки, и поэтому на практике редко используются рядовыми программистами. Однако с теоретической точки зрения они развивают логику применения математического метода индукции при проверке правильности программ. На основе спецификации программ проводится частичное и полное доказательство правильности программ [1] .
Под доказательством частичной правильности понимается проверка выполнения свойств данных программы с помощью утверждений, которые описывают то, что должна получить эта программа, когда закончится се выполнение, в соответствии с условиями заключительного утверждения. Полностью правильной программой по отношению к ее описанию и заданным утверждениям будет такая программа, которая частично правильная и заканчивается ее выполнение при всех данных, удовлетворяющих ей.
1.2 Формальные методы верификации. Тестирование.
Для доказательства частичной правильности используется метод индуктивных утверждений, сущность которого состоит в следующем. Пусть утверждение А связано с началом программы, В — с конечной точкой программы и утверждение С отражает некоторые закономерности получения значений переменных в одной из точек каждого пути в программе. Если при выполнении программа попадает в г-ю точку и справедливо утверждение А,, а затем она проходит от точки i к точке j, то будет справедливо и утверждение .
Теорема 6.1. Если выполнены все действия программы методом индуктивных утверждений, то она частично правильна в соответствии с утверждениями А, В, С.
Требуется доказать, что если выполнение программы закончится успешно, то утверждение В будет справедливым. Согласно индукции, если при проходе через некоторую точку программы утверждение С будет справедливым, то при прохождении n-точек оно также будет справедливым. Таким образом, если программа прошла и-точку и утверждения А и В справедливы, то тогда всякий проход из п-й точки в п + 1 точку и утверждение Л„+1 будут справедливыми, что и требовалось доказать.
- [1] См.: Ноаге Г., Misra J. Verified software: Theories, Tools, Experiments. Vision of GrantChallenge project. Microsoft Research Ltd and the University of Texas at Austin, 2005, Jacobson /.,Booch G.y RumbaughJ. The Unified Software Development Process. N. Y.: Addison-Wesley, 1999.
Источник: studme.org
Способы проверки правильности программы: теоретический (аналитический) и экспериментальный (эмпирический)
Использование компьютеров для решения возникающих перед человеком проблем ставит новые вопросы. К числу таких вопросов относится надежность программного обеспечения.
Универсальные вычислительные машины могут быть запрограммированы для решения самых разных задач – от арифметических вычислений до доказательства теорем, от редактирования текстов до обучения иностранному языку. Однако успешное решение этих и многих других задач возможно лишь при условии, что программа правильна, т.е. не содержит ошибок. Как убедиться, что ошибки на самом деле отсутствуют? Факт безаварийного завершения программы еще ни о чем не говорит: возможно, что программа делает совсем не то, что было задумано и для чего она была написана.
Виталий Брагилевский — Формальная верификация операционных систем
Алгоритм (программа) будет правильным, если в результате его выполнения достигается тот результат, для получения которого и был написан алгоритм.
Способы проверки правильности программы: теоретический (аналитический) и экспериментальный (эмпирический).
Теоретически — доказательство правильности программы состоит в предъявлении такой цепочки аргументов, которые убедительно свидетельствуют о том, что программа действительно решает поставленную задачу. Более строгий путь проверки программы – верификация, которая представляет собой теоретическое обоснование правильного вычисления программы и включает логико-математическое доказательство того, что вычислительное поведение программы правильно.
Для экспериментальной проверки в практике программирования используют прием тестирования программ: проверяемую программу неоднократно запускают с теми входными данными, относительно которых результат известен заранее. Затем сравнивают машинный результат с ожидаемым, если результаты совпадают, то появляется небольшая уверенность, что и последующие вычисления не приведут к ошибкам.
Для сложных программ удачное тестирование не дает гарантии того, что программа не содержит ошибок.
Недостаточно доказать правильность алгоритма. Все мы можем сделать ошибки при доказательстве и при переводе правильного алгоритма в программу. Каждый может забыть некоторый частный случай задачи. Мельчайшие особенности операционной системы могут вызвать для некоторых входных данных такое действие части вашего алгоритма, о котором вы и не подозревали.
Программа должна быть проверена для широкого спектра допустимых входных данных. Этот процесс может быть утомительным и сложным. Аналитический и экспериментальный анализ дополняют друг друга. Аналитический анализ может быть неточным, если сделаны слишком сильные упрощающие допущения. В этом случае могут быть получены только грубые оценки.
Экспериментальные результаты, особенно когда используются случайно сгенерированные данные, могут оказаться слишком односторонними. Чтобы получить достоверные результаты, следует проводить как аналитическое, так и экспериментальное исследование там, где это возможно.
Однако правильность — далеко не единственное качество, которым должен обладать хороший алгоритм. Одним из важнейших является эффективность.
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Источник: studopedia.ru
Презентация на тему Современные направления проверки правильности программ (лекция 9 )
Современные направления проверки правильности программ — это формальные спецификации, методы доказательства, верификация, валидация и тестирование Формальные спецификации появились в программировании в 70-х годах прошлого столетия. Они предоставляют средства, облегчающие описание
- Главная
- Информатика
- Современные направления проверки правильности программ (лекция 9 )
Слайды и текст этой презентации
Слайд 1Лекция 9
Современные направления проверки правильности программ
Слайд 2
Современные направления проверки правильности программ — это
формальные спецификации, методы доказательства, верификация, валидация и
тестирование
Формальные спецификации появились в программировании в 70-х годах прошлого столетия. Они предоставляют средства, облегчающие описание рассуждения о свойствах и особенностях программ в математической нотации.
На формальных спецификациях базируются методы доведения программ, которые были начаты работами по теории алгоритмов А.А. Маркова [1], А.А. Ляпунова [2], схемами Ю.И.Янова [3] и формальными нотациями описания взаимодействующих процессов К.А. Хоара [4] и др..
Слайд 3
Для проверки формальной спецификации программы применяют математический
аппарат для описания правильного решения некоторой задачи,
для которой она разработана.
Вместе со спецификацией разрабатываются дополнительные аксиомы, утверждение о описание операторов и условий, так называемые предварительные условия или предпосылки, и постусловием, определяющие заключительные правили получения правильного результата.
Слайд 4
Доказательство программ производится с помощью утверждений, состоящих
в формальном языке и служат для проверки
правильности программы в заданных ее точках. Если утверждение соответствует конечному оператору программы, то делается окончательный вывод о частичной или полной правильность работы программ.
Верификация и валидация — это методы обеспечения проверки и анализа правильности выполнения заданных функций программы в соответствии с заданными требованиями заказчика к ним и системы в целом.
Тестирование — это метод выявления ошибок в ПС путем выполнения исходного кода на тестовых данных, сбора рабочих характеристик в динамике выполнения в конкретном операционной среде, выявления различных ошибок, дефектов, отказов и сбоев, вызванных нерегулярными, аномальными ситуациями или аварийным прекращением работы системы.
Слайд 5
Теоретические средства реализуются как процессы программирования и
проверки правильности программного продукта.
В настоящее время
процессы верификации, валидации и тестирования ПС регламентированы стандартом ISO/IEC-12207 из жизненного цикла ПС.
В некоторой зарубежной литературе процессы верификации и тестирования на практике отождествляются, они ориентированы на достижение правильности программы.
Слайд 6 Языки спецификации программ и их классификация
Языки формальной
спецификации, которые используются для формального описания свойств
выполнения программ путем задания утверждений, являются языками высокого уровня.
В общем случае формальная спецификация программы — это однозначный специфицированный описание программы с помощью математических понятий, терминов, правил синтаксиса и семантики формального языка.
Слайд 7Категории формальных языков спецификации
Слайд 8 Универсальные языки спецификации имеют общую математическую основу
с такими средствами:
2) арифметические операции;
3) множества и
операции над множествами;
4) описания последовательностей и операции над ними;
5) описания функций и операций над ними;
6) описания древовидных структур;
7) средства построения моделей областей;
8) процедурные средства языков программирования (операторы присваивания, цикла, выбора, выхода);
9) операции композиции, аргументами и результатами которых могут быть функции, выражения, операторы;
10) механизм конструирования новых структур данных.
Слайд 9 Языки спецификации предметных областей (доменов) в программировании:
1)
спецификации доменов;
2) описания взаимодействий и параллельного выполнения;
спецификации языков программирования и трансляторов;
4) спецификации баз данных и знаний;
5) спецификации пакетов прикладных программ.
Слайд 10
Языки спецификации специфики доменов DSL (Domain Specific
Language) предназначены для формализованного описания задач в
терминах предметной области, подлежащей моделированию. Эти языки можно подразделить на внешние и внутренние.
Внешние языки (типа UML) По уровню выше языков программирования, например, предметно-ориентированный язык DSL, который используется для представления абстрактных понятий и задач ПрО. Их описание трансформируется к понятиям некоторой внутренней речи или языка программирования специальными генераторами или текстовыми редакторами.
Внутренние языки — языки описания специфических задач ограниченных синтаксисом и семантикой
Слайд 11
Языки программирования предметной области, дополнены средствами и
механизмами технологий. Метапрограммирование является эффективным средством автоматизации
спецификаций разработанных программ и в настоящее время находят широкое применение в области информационных технологий.
Слайд 12классификация спецификаций по способу выполнения
Кроме приведенной классификации
языков спецификаций, существуют другие. Например, возможна классификация
спецификаций по способу выполнения:
— Сценарная (use case or scenarios),
— В ограничениях (constraints).
Слайд 13классификация спецификаций по способу выполнения
Выполняемые спецификации предполагают
разработку прототипов систем для достижения установленной цели
Алгебраические спецификации, включают в себя механизмы описания аксиом и утверждений, предназначенные для доведения специфицированных программ.
Сценарные спецификации (UML) позволяют описывать различные способы возможного применения системы.
Слайд 14Верификация и валидация программ
Верификация ПО — процесс
обеспечения правильной реализации ПО в соответствии со
спецификациями, выполняется в течение всего жизненного цикла. Верификация дает ответ на вопрос, правильно создается система. Валидация — процесс проверки соответствия ПО функциональным и нефункциональным требованиям и ожидаемым потребностям заказчика. Верификация и валидация — это методы анализа, проверки спецификаций и правильности выполнения программ в соответствии с заданными требованиями и формального описания программы
Слайд 15
Метод верификации помогает сделать вывод о корректности
созданной программной системы при ее проектировании и
после завершения ее разработки.
Валидация позволяет установить выполнимость заданных требований путем их просмотра, инспекции и оценки результатов проектирования на процессах ЖЦ для подтверждения того, что осуществляется корректная реализация требований, соблюдение заданных условий и ограничений к системе.
Верификация и валидация обеспечивают проверку полноты, непротиворечивости и однозначности спецификации и правильности выполнения функций системы.
Слайд 16
Верификация и валидация, как методы, обеспечивают соответственно
проверку и анализ правильности выполнения заданных функций
и соответствия ПО требованиям заказчика, а также заданным спецификациям. Они представлены в стандартах] как самостоятельные процессы ЖЦ и используются, начиная от этапа анализа требований и кончая проверкой правильности функционирования программного кода на заключительном этапе, а именно, тестировании.
Для этих процессов определены цели, задачи и действия по проверке правильности создаваемого продукта (рабочие, промежуточные продукты) на этапах ЖЦ. Рассмотрим их трактовку в стандартном представлении.
Слайд 17
Верификации и валидации подвергаются:
— Компоненты системы, их
интерфейсы (программные, технические и информационные) и взаимодействие
объектов (протоколы, сообщения) в распределенных средах;
— Описания доступа к базам данных, средства защиты от несанкционированного доступа к данным различных пользователей;
— Документация к системе;
— Тесты, тестовые процедуры и входные наборы данных.
Слайд 18Процесс верификации.
Цель процесса — убедиться, что
каждый программный продукт проекта отражает согласованные требования
к их реализации.
Этот процесс основывается:
— На стратегии и критериям верификации всех рабочих программных продуктов на ЖЦ;
— На выполнении действий по верификации в соответствии со стандартом;
— На устранении недостатков, выявленных в программных (рабочих, промежуточных и конечных) продуктах;
— На согласовании результатов верификации с заказчиком.
Слайд 19Процесс верификации
Процесс верификации может проводиться исполнителем
программы или другим сотрудником той же организации
или сотрудником другой организации, например представителем заказчика. Этот процесс включает в себя действия по его внедрению и исполнению.
Внедрение процесса заключается в определении критических элементов (процессов и программных продуктов), которые должны подвергаться верификации, в выборе исполнителя верификации, инструментальных средств поддержки процесса верификации, в составлении плана верификации и его утверждения. В процессе верификации выполняются задачи проверки условий: контракта, процесса, требований, интеграции, кода и документации.
Соответствии с планом и требованиями заказчика проверяется правильность выполнения функций системы, интерфейсов и взаимосвязей компонентов, а также доступ к данным и к средствам защиты.
Слайд 20Процесс валидации.
Цель процесса — убедиться, что
специфические требования для программного выполнено, и осуществляется
— Разработанной стратегии и критериев проверки всех рабочих продуктов;
— Оговоренных действий по проведению валидации;
— Демонстрации соответствия разработанных программных продуктов требованиям заказчика и правилам их использования;
— Согласование с заказчиком полученных результатов валидации продукта.
Слайд 21
Процесс валидации может проводиться самим исполнителем или
другим лицом, например, заказчиком, осуществляет действия по
внедрению и проведению этого процесса по плану, в котором отражены элементы и задачи проверки. При этом используются методы, инструментальные средства и процедуры выполнения задач процесса для установления соответствия тестовых требований и особенностей использования программных продуктов проекта на правильность реализации требований.
На других процессах ЖЦ выполняются дополнительные действия:
— Проверка и контроль проектных решений с помощью методик и процедур обзора хода разработки;
— Обращение к CASE-систем, которые включают в себя процедуры проверки требований к продукту;
— Просмотры и инспекции промежуточных результатов на соответствие требованиям для подтверждения того, что они удовлетворяет условиям выполнения системы.
Слайд 22
Таким образом, основные задачи процессов верификации и
валидации состоит в том, чтобы проверить и
подтвердить, что конечный программный продукт соответствует назначению и удовлетворяет требованиям заказчика. Эти процессы взаимосвязаны и определяются, как правило, одним общим термином «верификация и валидация» или «Verification and Validation» (V
2. Создание модели требований;
3. Создание специальных сценариев для валидации требований;
4. Применение валидационных сценариев в модели требований;
5. Оценка результатов поведения модели требований;
6. Проверка условий завершения процесса валидации и при обнаружении каких-либо неточностей повторение шагов, начиная с п. 2.
При выполнении сценариев могут возникнуть ошибочные ситуации, при которых поведения системы становится не детерминированным. В этих целей проводится контроль покрытия сценариев в модели требований валидационных сценариям с целью выявления ошибок или рисков
Источник: thepresentation.ru