Методы установления формальной корректности ПО широко используются в современных системах автоматизации программирования. Прежде всего это синтаксический и семантический контроль входных текстов программ, обеспечивающий выявление и локализацию значительного количества разнообразных ошибок, включая проверку корректности базовых конструкций языка программирования. Для контроля правильности структуры программы может быть эффективно использован метод с применением матрицы достижимости, о которой сказано в п. 4.5.2. Большинство алгоритмов построения этой
матрицы имеет временную сложность не выше t(n) = г? шагов. Метод позволяет выделить лишние и тупиковые вершины и циклические участки управляющего графа программы [18].
Каждая программа в принципе может быть задана описанием отношений между входными и выходными данными, записанных с помощью исчисления предикатов первого порядка и так называемыми утверждениями. Верификация, т. е. формальное доказательство правильности программы, состоит в последовательной демонстрации того, что из входного утверждения (предиката) и цепочки преобразований над ним следует истинность выходного утверждения. Кроме того, необходимо доказать завершимость всех циклов за конечное число шагов. Таким образом, верификация программы потенциально может исключить ее отладку и тестирование. Не вдаваясь в детали метода и предполагая, что он может быть широко использован на практике (что пока совершенно невозможно), легко обнаружить следующие недостатки.
Podlodka #268 – Формальные методы и верификация программ
- 1. Правильность программ доказывается только по отношению к входному и выходному предикатам. Ошибки, сделанные на ранних этапах проектирования (цели, внешние спецификации), не будут обнаружены при доказательстве.
- 2. Ошибки в сопряжении (порядок параметров не соответствует порядку аргументов и т. п.) не обнаруживаются при доказательстве.
- 3. Системные и машинные ограничения, как правило, игнорируются (вместе с возможными последствиями).
Этот список содержит как минимум десяток пунктов [21] и оканчивается констатацией того факта, что доказательство всегда гораздо длиннее самой программы. Очевидно, что в ручном варианте метод для практики непригоден. Поэтому интенсивно ведутся работы по созданию автоматизированных верификаторов программ, которые в силу вышеприведенных соображений, если и не заменят тестирование и отладку, то потенциально могут снизить их трудоемкость.
Источник: studref.com
Управление процессом тестирования
Все способы тестирования ПС объединяются базой данных, где помещаются результаты тестирования системы. В ней содержатся все компоненты, тестовые контрольные данные, результаты тестирования и информация о документировании процесса тестирования.
База данных проекта поддерживается специальными инструментальными средствами типа CASE, которые обеспечивают ведение анализа ПрО, сборку данных об их объектах, потоках данных и тому подобное. База данных проекта хранит также начальные и эталонные данные, которые используются для сопоставления данных,накопленных в базе, с данными, которые получены в процессе тестирования системы.
Лекция 1 | Программный анализ и формальные методы верификации | Наталья Шарыгина | Лекториум
При тестировании выполняются разные виды расчетов характеристик этого процесса и способы планирования и управления.
1. Расчет продолжительности выполнения функций путем сбора средних показателей скорости выполнения операторов без выполнения программы на машине. Выявляются компоненты, которые требуют большого времени выполнения в реальной среде.
2. Управление выполнением тестирования путем подбора тестов проверки, их выполнения, селекции результатов тестирования и проведения сопоставления с эталонными значениями. Результаты данного процесса отображаются на дисплее, например, в графической форме (пути прохождения по графу программы), в виде диаграмм UML, данных об отказах и ошибках или конкретных значений исходных параметров программы. Эти данные анализируются разработчиками для формулирования выводов о направлениях дальнейшей проверки правильности программы или их завершении.
3. Планирование тестирования предназначено для распределения сроков работ по тестированию, распределения тестировщиков по отдельным видам работ и составления ими тестов проверки системы. Определяются стратегия и пути тестирования. В диалоге запрашиваются данные о реальных значениях процесса выполнения системы, структуре ветвления вершин графа и параметрах циклов. Проверенные циклы, как правило, изымаются из путей выполнения программы. При планировании путей выполнения создаются соответствующие тесты, критерии и входные значения.
Документирование результатов тестирования в соответствии с действующим стандартом ANSI/IEEE 829 включает:
· технологии разработки системы;
· планов тестирования различных объектов, необходимых ресурсов, соответствующих специалистов для проведения тестирования и технологических способов;
· тестов, контрольных примеров, критериев и ограничений, оценки результатов программного продукта, а также процесса тестирования;
· учета процесса тестирования, составление отчетов об аномальных событиях, отказах и дефектах в итоговом документе системы.
Таким образом, были рассмотрены современные методы и процессы верификации и тестирования ПС, основанные на понятии программы — «белый ящик» и «черный ящик», а также на анализе реализованных в ПС функций. Определены критерии тестирования, типы ошибок, обнаруживаемых в программах, а также отказы и ошибки на этапах ЖЦ процесса тестирования. Сформулированы цели и задачи группы тестировщиков.
Контрольные вопросы и задания
1. Назовите формальные методы проверки правильности программ.
2. Какие процессы проверки зафиксированы в стандарте?
3. Какие функции у процесса верификации программ?
4. Назовите основные задачи процесса валидации программ.
5. Сравните задачи процессов верификации и валидации программ.
6. В чем отличие верификации и валидации?
7. Определите процесс тестирования.
8. Назовите методы тестирования.
9. Объясните значения терминов «черный ящик», «белый ящик».
10. Назовите объекты тестирования и подходы к их тестированию.
11. Какая существует классификация типов ошибок в программах?
12. Определите основные процессы ЖЦ тестирования ПО.
13. Наведите классификацию тестов для проверки ПО.
14. Какие задачи выполняет группа текстовиков?
15. Какая организация работ в проведении тестирования?
Тема 4. Формальные спецификации, доказательство и верификация программ
Современные направления в области проверки правильности программ — формальные спецификации и методы доказательства их правильности. Для доказательства того, что спецификация программы задает правильное решение некоторой задачи, для которой она разработана, привлекается математический аппарат.
В формальных методах нет рутинного написания спецификации на ЯП, а есть анализ текста и описание поведения программы в стиле, близком математической нотации, путем рассуждений и доказательств, принятых в математике. Формальные методы в программировании появились одновременно с самим программированием, на которое повлияли работы по теории алгоритмов А.А. Маркова [6.1], А.А. Ляпунова [6.2], схемы Ю.И.Янова [6.3], формальные нотации языка описания взаимодействующих процессов К.А. Хоара [6.4] и др.
В 70-х годах прошлого столетия появились формальные спецификации, которые близки ЯП и предоставляют средства, облегчающие проводить рассуждение о свойствах формальных тестов и сближающие их с математической нотацией. Несмотря на это, исследования формальных методов носили в основном академический, теоретический характер, поскольку извлечь из них практическую пользу в программировании не удавалось в силу огромных затрат на формальную спецификацию программ и разработку дополнительных [6.5-6.10] аксиом, утверждений и условий, называемых предварительными условиями (предусловиями) и постусловиями, определяющими заключительные правила получения правильного результата.
Под спецификацией понимается формальное описание функций и данных программы, с которыми эти функции оперируют. Различают видимые данные, т.е. входные и выходные параметры, а также скрытые данные, которые не привязаны к реализации и определяют интерфейс с другими функциями.
Предусловия — это ограничения на совокупность входных параметров и постусловия — ограничения на выходные параметры. Предусловие и постусловие задаются предикатами, т.е. функциями, результатом которых будет булевская величина ( 
/ 
). Предусловие истинно тогда, когда входные параметры входят в область допустимых значений данной функции. Постусловие истинно тогда, когда совокупность значений удовлетворяет требованиям, задающим формальное определение критерия правильности получения результата.
Доказательство проводится с помощью утверждений, которые составляются в формальном языке и служат способом проверки правильности программы в заданных точках. Набор утверждений использует предусловия и последовательность операций, приводящих к проверке результата относительно отмеченной точки программы, для которой сформулировано заключительное утверждение. Если утверждение соответствует конечному оператору программы, где требуется получить окончательный результат, то с помощью заключительного утверждения и постусловия делается окончательный вывод о частичной или полной правильности работы программы.
Источник: studopedia.org
Организация процесса тестирования
Все способы тестирования ПС объединяются базой данных, где помещаются результаты тестирования системы. В ней содержатся все компоненты, тестовые контрольные данные, результаты тестирования и информация о документировании процесса тестирования.
База проекта поддерживается специальными инструментальными средствами типа CASE, которые обеспечивают ведение анализа ПрО, сборку данных об их объектах, потоках данных и тому подобное. База проекта хранит также начальные и эталонные данные, которые используются для сопоставления данных, накопленных в базе с данными, которые получены при тестировании.
При тестировании выполняются разные виды расчета характеристик этого процесса и способы планирования и управления:
1. Расчет продолжительности выполнения функций путем сбора средних значений о скорости выполнения операторов без выполнения программы на машине. Выявляются компоненты, которые требуют большого времени выполнения в реальной среде.
2.Управления выполнением состоит в организации подбора тестов проверки, их выполнении, селекции результатов тестирования и проведении сопоставления с эталонными значениями. Результаты процесса отображаются на дисплеи, например, в графической форме (пути прохождения по графу программы), в виде последовательности диаграмм UML, а также в виде информации об отказах и ошибках или конкретных значениях исходных параметров программы. Эти данные анализируются разработчиками для формулирования выводов о направлениях дальнейшей проверки правильности программы или их завершение.
3. Планирование тестирования предназначено для распределения сроков работ по тестированию, распределения тестировщиков по отдельным видам работ и составления ими тестов проверки работы системы. Практически определяется стратегия и пути тестирования. В диалоге запрашиваются реальные значения процесса выполнения или выдачи структуры о разветвления вершин графа и параметров циклов. Проверенные циклы, как правило, изымаются из путей выполнения программы. При планировании путей выполнения создаются соответствующие тесты, критерии и входные значения.
4. Документирование результатов тестирования в соответствии с действующим стандартом ANSI/IEEE 829, включает описание:
– технологии разработки системы;
– планов тестирования различных объектов, необходимых ресурсов, соответствующих специалистов для проведения тестирования и технологических способов;
– тестов, контрольных примеров, критериев и ограничений оценки результатов программного продукта, а также процесса тестирования;
– учета процесса тестирования, составление отчетов об аномальных событиях, отказах и дефектах в итоговом документе системы.
Контрольные вопросы и задания
1. Назовите формальные методы проверки правильности программ.
2. Какие процессы проверки зафиксированы в стандарте?
3. Какие объекты входят в доказательство правильности программ?
4. Назовите основные методы доказательства корректности программ и базис этих методов.
5. Определите типы логических операций, используемых при логическом доказательстве корректности программ.
6. В чем состоит отличие техники формального доказательства от символьного выполнения программ?
7. Сформулируйте основные задачи верификации и валидации программ.
8. В чем отличие верификации и валидации?
9. Определите процесс тестирования.
10. Назовите методы тестирования.
11. Объясните значения терминов «черный ящик», «белый ящик».
12. Назовите объекты тестирования и подходы к их тестированию.
13. Какая существует классификация типов ошибок в программах?
14. Определите основные этапы ЖЦ тестирования ПО.
15. Наведите классификацию тестов для проверки ПО.
16. Какие задачи выполняет группа тестировщиков?
17. Какая организация работ проводится для проведения тестирования.
Литература к теме 7
1. Майерс Г. Искусство тестирования программ. – Пер.с англ.M: Финансы и статистика. – 1982. – 176 с.
2. Липаев В.В. Отладка сложных программ.–М.: Энергоатомиздат, 1993.–296с.
3. Липаев В.В. Тестирование программ.–М: Радио и связь,–1986.–295с.
4. Канер С., Фолк Д., Нгуен Е.К. Тестирование программного обеспечения: Пер с англ. – К.: DiaSoft. – 2000. – 544 с.
5. Weyuker E.J., Ostrand T.J. Theories of program testing and the application of revealing subdomains // IEEE Trans.Soft.Eng. – 1980, –V.6, –№. 3, – P. 236–246.
6. Software unit test coverage and adequacy. / Zhu H., Hall P. A. // ACM Computing Surveys, 29, –№ 4, Dec. 1997. –P. 336–427.
7. Коул Дж., Горем Т. и др. Принципы тестирования ПО //Открытые системы. – 1998.– №2. www.osp.ru/os/1998/02/60.htm
8. Burstall R.M. Program proving as hand simulation with a little induction. – Proc. IFIP Congress 74, North–Holland, 1974. –P.80 – 89.
9. Dijkstra T.W. Finding the Correctness proof of a concurrent program. – Proc.Konf. Nederland Acad.Wetenach, 1978. – 81. – N2. – p.207– 215.
10. Clint M., Hoare C.A.R. Program proving: jumps and functions. — Acta Informatikee, 1972. — 1. — N3. — P.214—224.
11. Pfleeger S.L. Software Engineering. Theory and Practice. – Prentice Hall, 1998. – 576p.
12. Grossman D., McCobe C. Perfomance Testing a Large Finance Аpplication. – IEEE Software. – 1996. – Sept. – P.50 –60.
13. Y.Wang, J.King, J.Kourt, M.Ross, S.Staples. On testable odject–oriented programming// Software Engineering Notes, volume 22, N4. –1997.– pp.84–90
14. Perry D.E. and Kaiser C.E. Adequate testing and object–oriented programming // Journal of Object–Oriented Programming, January /Febrary. –1990. – p.13–19.
15. ANSI / IEEE Std. 10122–1986. Standard for Software Verification and Validation Plans // IEEE . – New York . – 1986. – 61p.
16. Dolores R. Wallase M. Ippolito, b. Cuthill. Reference Information for the Software Verification and Validation Process // NIST Special Publication . – 1996 . – 500–234. – 80p.
17. Herhart S.L. Program Verification in the 90’s.// Proc.Conf. on Computing in the 1980’s, 1978.– P.80–89.
18. ISO/IEC 12207: 1995.– Information technology — Software life cycle processes) Информационные технологии — Процессы жизненного цикла программного обеспечения..
19. CASE–93. Proceeding Sixth Intern.//Workshopon Computer Aided Software Engineering.– Singapure. –1993. – July 19–23.–418p.
20. Jacobson J. Object–oriented Software Engineering. – Revised Printing. – Addison– Wesley. – 1995. – 528p.
21. Коротун Т.М. Совершенствование процессов тестирования программного обеспечения // Проблемы программирования.–1998.–№3.–С.59–64.
22. Бабенко Л.П., Лаврищева Е.М. Основы программной инженерии.– Киев, 2001.– Знання.– 269с.
23. Koomen, T., and M. Pol. 1998. Improvement of the test process using TPI. http://www.iquip.nl
24. Андон Ф.И., Лаврищева Е.М. Методы инженерии распределенных компьютерных систем. –К.: Наукова думка, 1997. –229с.
25. Липаев В.В. Методы обеспечения качества крупномасштабных программных средств. – М.: СИНТЕГ.– 2003.–520 с.
26.Drabick R. Growth of maturity in the testing process. International Software Testing Institute 1999. http://www.softtest.org/articles/rdrabick3.htm.
27. Software Engineering Body of Knowledge (SWEBOK). // ISO/IEC JTC1/SC7 N2517.
Software https://megaobuchalka.ru/3/11668.html» target=»_blank»]megaobuchalka.ru[/mask_link]