Содержание к диссертации
ВВЕДЕНИЕ 8
ГЛАВА 1 МЕТОДЫ И СРЕДСТВА ИСПЫТАНИЙ ПРОГРАММНОГО
ОБЕСПЕЧЕНИЯ. ОСНОВНЫЕ ПОНЯТИЯ 15
1.1 Оценка качества и измерения программного обеспечения 15
-
Качество программного средства 16
-
Метрики свойств программных продуктов 16
-
Методы измерений программного обеспечения 17
-
Граф потока управления 18
1.2 Испытания программного обеспечения 19
1.2.1 Методы испытаний программного обеспечения 19
1.2.2 Программные средства поддержки испытаний программного обеспечения.... 2 О
1.3 Традиционные методы покрытия испытаниями потока управления в
программной единице 21
1.3.1 Методы покрытия испытаниями семантических языковых конструкций
программной единицы і 22
1.3.2 Методы покрытия испытаниями компонентов графа поток^ управления 25
1.4 Языково-ориентированный подход к измерениям и оцениванию
качества программных продуктов 28
-
Характеристика языково-ориентированного подхода 28
-
Измерительная модель конструкции простой оператор 30
-
Определение графа потока управления в терминах измерительной языковой модели 32
-
Динамические измерения программных продуктов 33
-
Метод частотных счетчиков 34
-
Трасса исполнения программной единицы 35
-
Измерительный языковой процессор 36
-
Построение измерительных языковых анализаторов с использованием систем построения трансляторов 36
-
Статический измерительный анализатор языка программирования Турбо Паскаль версии 7.0 39
Содержание
1.5 Задачи диссертационной работы 40
ГЛАВА 2 ФОРМАЛЬНЫЕ ОПРЕДЕЛЕНИЯ ТРАДИЦИОННЫХ
МЕТОДОВ И МЕТРИК СТРУКТУРНЫХ ИСПЫТАНИЙ
ПРОГРАММНОЙ ЕДИНИЦЫ В ТЕРМИНАХ
ИЗМЕРИТЕЛЬНОЙ ЯЗЫКОВОЙ МОДЕЛИ 42
2.1 Формальное определение множества трасс исполнения программной
единицы 43
-
Формальное определение метода покрытия операторов 44
-
Формальное определение метода покрытия циклов 45
2.3.1 Определение множества циклов 47
2.3.2 Определение множества покрытых циклов 48
2.4 Формальное определение метода покрытия ветвей в программной
единице 50
-
Определение множества ветвей в программной единице 50
-
Определение множества покрытых ветвей в программной единице 51
2.5 Формальное определение метода покрытия путей между определением
и использованием значений переменных 52
-
Определение множества путей между определением и использованием значений переменных 52
-
Определение множества покрытых путей между определением и использованием значений переменных 61
2.6 Формальное определение метода покрытия всех путей в программной
единице 62
-
Определение множества всех путей в программной единице 62
-
Определение множества покрытых путей в программной единице 64
2.7 Формальное определение метода покрытия вершин 64
2.7.1 Определение множества вершин 64
2.7.2 Определение множества покрытых вершин 67
2.8 Формальное определение метода покрытия дуг 67
2.8.1 Определение множества дут 67
2.8.2 Определение множества покрытых дуг 70
Содержите А
2.9 Формальное определение метода покрытия ветвей в графе потока
управления 70
2.9.1 Определение множества ветвей в графе потока управления 70
2.9.2 Определение множества покрытых ветвей в графе потока управления.... 71
2.10 Формальное определение метода покрытия линейно-независимых
путей 72
-
Определение графа потока управления, преобразованного в сильно связный граф 72
-
Определение множества элементарных контуров в преобразованном графе потока управления 73
-
Определение базисного множества линейно-независимых путей графа потока управления 76
2.10.4 Определение множества покрытых линейно-независимых путей 77
2.11 Формальное определение метода покрытия простых путей 78
2.11.1 Определение множества простых путей 78
2.11.2 Определение множества покрытых простых путей 79
2.12 Формальное определение метода покрытия всех путей в каждом цикле 79
-
Определение множества всех путей в каждом цикле 80
-
Определение множества покрытых путей в циклах 83
2.13 Выводы ко второй главе 85
ГЛАВА 3 КОНТЕКСТ В ПРОГРАММЕ 86
-
Понятие контекст в естественном языке 86
-
Интерпретация в терминах языка программирования понятий, используемых при определении контекста в естественном языке 88
-
"Единица языка" 88
-
"Точно определенный смысл и значение единицы языка" 89
-
"Законченная по смыслу часть текста" 90
-
Основные отличия текста на языке программирования от текста на естественном языке 92
-
Определение понятия контекст в программе 94
-
Принципы построения модели множества потенциальных контекстов. 96
-
Модель множества потенциальных контекстов фрагмента программы 98
-
Построение моделей множества потенциальных контекстов в простом операторе 103
-
Модель простого оператора с одним выходным потоком управления -МПКПО-1 103
-
Модель простого оператора с несколькими выходными потоками управления - МПКПО-2 104
3.8 Построение модели множества потенциальных контекстов в
последовательности простых операторов 104
3.9 Построение модели множества потенциальных контекстов в блоке 112
ЗЛО Построение модели множества потенциальных контекстов в
программной единице 115
3.11 Выводы к третьей главе 117
ГЛАВА 4 МЕТОД ПОКРЫТИЯ ИСПЫТАНИЯМИ ПОТЕНЦИАЛЬНЫХ
КОНТЕКСТОВ ПРОГРАММНОЙ ЕДИНИЦЫ 118
4.1 Определение метода покрытия испытаниями множества
потенциальных контекстов программной единицы 118
-
Множество потенциальных контекстов программной единицы 118
-
Множество потенциальных контекстов, покрытых испытаниями 119
4.2 Равнозначные методы покрытия испытаниями 121
-
Метод покрытия операторов и метод покрытия вершин графа потока управления 122
-
Метод покрытия ветвей в программной единице и метод покрытия ветвей в графе потока управления 122
4.3 Сравнение степени проверенности программной единицы,
обеспечиваемой применением различных методов покрытия
испытаниями 124
-
Метод покрытия потенциальных контекстов, метод покрытия операторов и метод покрытия вершин графа потока управления 124
-
Метод покрытия потенциальных контекстов и метод покрытия дуг 125
-
Метод покрытия потенциальных контекстов и метод покрытия ветвей ... 127
Содержание (^
-
Метод покрытия потенциальных контекстов и метод покрытия циклов... 128
-
Метод покрытия потенциальных контекстов и метод покрытия простых путей 129
-
Метод покрытия потенциальных контекстов и метод покрытия линейно-независимых путей 130
-
Метод покрытия потенциальных контекстов и метод покрытия всех путей в каждом цикле 133
-
Метод покрытия потенциальных контекстов и метод покрытия путей между определением и использованием значений переменных (метод покрытия def-use путей) 135
-
Метод покрытия потенциальных контекстов и метод покрытия всех путей. ..136
4.3.10 Результаты сравнения степени проверенности программной единицы,
обеспечиваемой применением различных методов покрытия
испытаниями 137
4.4 Достоинства и недостатки метода покрытия потенциальных
контекстов программной единицы 140
-
Степень проверенности программной единицы, обеспечиваемая применением метода покрытия потенциальных контекстов 140
-
Создание средств поддержки покрытия потенциальных контекстов 141
-
Ресурсоемкость тестирования программной единицы при использовании метода покрытия потенциальных контекстов 142
4.5 Выводы к четвертой главе 143
ГЛАВА 5 МЕТОДЫ РЕАЛИЗАЦИИ ФУНКЦИЙ ДИНАМИЧЕСКИХ
ИЗМЕРЕНИЙ ИЗМЕРИТЕЛЬНОГО ЯЗЫКОВОГО
ПРОЦЕССОРА. СОЗДАНИЕ ПРОГРАММНЫХ СРЕДСТВ
ИЗМЕРЕНИЯ ПРОЦЕССА ИСПОЛНЕНИЯ ПРОГРАММ,
ПОДДЕРЖИВАЮЩИХ СТРУКТУРНЫЕ ИСПЫТАНИЯ. 144
5.1 Измерение динамических свойств программ 144
-
Расширение исходного текста измеряемой программы средствами сбора динамической информации 145
-
Библиотека подпрограмм генерации расширенной программы 147
Содержание П
-
Библиотека подпрограмм сбора динамической информации 148
-
Создание с использованием систем построения трансляторов ТР Lex и ТР Yacc измерительного анализатора, обеспечивающего выполнение динамических измерений 150
-
Выполнение динамических измерений программ с использованием измерительного анализатора 154
5.2 Создание программных средств измерения процесса исполнения
программ, поддерживающего структурные испытания 155
-
Определение степени покрытия программ испытаниями с использованием измерительного анализатора 155
-
Построение множеств покрываемых испытаниями компонентов 157
-
Построение множеств покрытых испытаниями компонентов и вычисление значений метрик покрытия 160
5.3 Выводы К ПЯТОЙ ГЛАВЕ 162
ЗАКЛЮЧЕНИЕ ; 163
ЛИТЕРАТУРА [ 165
ПРИЛОЖЕНИЕ 1. Акты внедрения результатов работы 175
ПРИЛОЖЕНИЕ 2. Определения используемых в работе терминов 176
ПРИЛОЖЕНИЕ 3. Обзор программных средств поддержки испытаний
программного обеспечения 180
ПРИЛОЖЕНИЕ 4. Определение объединения модели множества потенциальных контекстов в последовательности простых операторов и модели множества
потенциальных контекстов в простом операторе 185
ПРИЛОЖЕНИЕ 5. Определение объединения модели множества потенциальных
контекстов в последовательности простых операторов и модели множества
потенциальных контекстов в блоке 194
Внсдешн; g
Введение к работе
Актуальность работы. Успехи технологии программирования последних лет привели к смещению акцента с просто разработки программного обеспечения на разработку высококачественного программного обеспечения. На достижение этой цели направлены усилия специалистов различного профиля, принимающих участие в разработке программных средств. Одним из основных видов деятельности в процессах разработки и сопровождения программного обеспечения являются испытания. Цель испытаний — убедиться, что программное средство функционирует в соответствии с требованиями заказчика и их спецификациями, и этим удостоверить его качество. Испытания программного обеспечения выполняются не только при создании новых компонентов программ, но и при всех их последующих изменениях. Следствием этого является высокая потенциальная стоимость испытаний, что, в итоге, ведет к уменьшению объема испытаний, а потому недостаточной проверенное программных средств, поставляемых заказчику или предлагаемых "на рынке". і Одним из традиционных путей снижения стоимости и повышения эффективности испытаний является автоматизация их проведения, охватывающая все аспекты деятельности испытателей.
Автоматические средства, зачастую, позволяют уменьшить затраты на испытания и повысить вероятность обнаружения дефектов. Однако автоматические средства (во всяком случае, в настоящее время) способны установить только правильность использования средств языка программирования и, возможно, правильность определенных математических преобразований, выполняемых в программе. Убедиться в правильности программы с точки зрения семантики решаемой задачи может только человек.
В работах Майерса (G. J. Myers) [35], Пратера (R. Е. Prather) [98], Мак-Кейба (T.J. McCabe) [94], Канера (С. Капег) [89, 90] и других авторов описаны различные методы испытаний программного обеспечения, применяемые в настоящее время на практике. Однако эти методы имеют определенные недостатки и не гарантируют полную правильность программы по завершению их применения. Существующие методы и средства являются взаимодопол-
Введение О, няющими, и появление новых методов и средств позволяет либо получать "более правильные" программы, либо достигать этого более дешевым путем.
Основы испытаний программного обеспечения могут быть условно разделены на методы создания тестов и методы испытаний. В рамках данной работы рассматриваются только методы испытаний программной единицы, основанные на изучении ее структуры, потока управления и потока данных между операторами.
Данная работа является частью исследований, проводившихся в контексте автоматизации измерения и оценивания программного обеспечения в рамках предложенного в Институте автоматики и процессов управления (ИАПУ) ДВО РАН языково-ориентироеанного подхода (ЯОП) к измерению и оцениванию качества программного обеспечения. Основным требованием ЯОП является строгое, семантически обоснованное определение понятий предметной области качество программного обеспечения, что позволяет достичь единства в толковании этих понятий и связей между ними. В работах Б.И. Когана, Т.О. Матвеевой, С.Н. Остроуховой и Е.А. Шалфеевой были определены принципы применения ЯОП к специфицированию требований к качеству программного средства, измерению составляющих его программных продуктов и оцениванию достигнутого в них уровня качества [16, 17, 19, 22, 36, 63, 64, 66, 68, 69]; построены обобщенная модель современного алгоритмического языка программирования [18, 20, 67, 70, 71] и обобщенные статические модели программ, обеспечивающие интерпретацию метрик качества в терминах этих моделей [48, 72]; разработаны методы реализации функций статических измерений измерительных языковых процессоров [44].
Цель работы. Целью диссертационной работы являлось создание моделей, методов и средств структурных испытаний программ в рамках языково-ориентированного подхода к измерению и оцениванию качества программного обеспечения.
Для достижения цели работы было необходимо решить следующие задачи.
1. Формально определить систему понятий, в терминах которых принято представлять результаты структурных испытаний программ.
Введение J Л
Разработать метод покрытия испытаниями потенциальных контекстов программной единицы.
Разработать методы реализации функций динамических измерений программ при использовании средств автоматизации построения трансляторов (языковых процессоров).
Разработать и исследовать средства измерения процесса исполнения программ, поддерживающие структурные испытания, для одного из широко используемых языков программирования.
Методы исследований. Для решения указанных задач использовались элементы теории графов, методы технологии программирования, методы измерения и оценивания качества программного обеспечения, методы системного программирования.
Научная новизна работы заключается в следующем.
Формально определены в терминах измерительной модели алгоритмического языка программирования традиционные методы и метрики покрытия испытаниями семантических языковых конструкций (компонентов) программной единицы и компонентов графа потока управления. Полученные определения позволяют целостно встроить эти методы и метрики в программные средства поддержки языково-ориентированного подхода к измерению и оцениванию программных средств.
На основе анализа особенностей алгоритмических языков программирования и написанных на них текстов программ даны определения понятий контекст и потенциальный контекст в программе или ее фрагменте. Понятие потенциальный контекст позволяет до начала испытаний программной единицы на комплекте тестов выявлять семантические дефекты "неинициализированные переменные", т.е. реализовать такую статическую проверку семантической правильности программ, которая обычно выполняется при их динамических испытаниях - тестировании.
Разработана модель множества потенциальных контекстов фрагмента программы. Эта модель является универсальным представлением
Впадение ^ 1 множеств потенциальных контекстов в различных фрагментах программ, написанных на любом из алгоритмических языков.
4. Разработан новый метод структурных испытаний программного обеспечения - метод покрытия испытаниями потенциальных контекстов программной единицы. Применение только одного метода покрытия испытаниями потенциальных контекстов обеспечивает большую или равную степень проверенности программной единицы по сравнению с обычно используемыми на практике традиционными методами покрытия испытаниями программной единицы. Средства поддержки применения этого метода могут быть относительно легко встроены в стандартный языковой процессор.
Практическая ценность работы состоит в том, что полученные в диссертации научные результаты имеют конкретную прикладную направленность, связанную с обеспечением качества программных средств. Разработанные методы применены при реализации экспериментального программного средст- i ва измерения процесса исполнения программ, поддерживающего структурные испытания. I
В работе получены следующие основные практические результаты.
Разработан универсальный формат представления потенциальных контекстов в программах, написанных на алгоритмических языках программирования - модель множества потенциальных контекстов фрагмента программы. Этот формат может использоваться и в тех случаях, когда средство измерения отлично от измерительного языкового процессора.
Разработаны и экспериментально проверены методы реализации функций динамических измерений измерительных языковых процессоров алгоритмических языков программирования, созданных с использованием систем автоматизации построения трансляторов (языковых процессоров).
Разработанное программное средство измерения процесса исполнения программ, написанных на языке Турбо Паскаль версии 7.0, включающее в себя метод покрытия потенциальных контекстов, используется в ИАПУ ДВО РАН как компонент измерительной среды для исследования
Введение J 2 языково-ориентированного подхода к измерению и оцениванию качества программ, написанных на алгоритмических языках программирования.
4. Вышеуказанное программное средство измерения процесса исполнения программ, написанных на языке Турбо Паскаль версии 7.0, используется в учебном процессе на кафедре программного обеспечения ЭВМ Института математики и компьютерных наук ДВГУ при выполнении курсовых и дипломных работ по специальности "Программное обеспечение вычислительной техники и автоматизированных систем".
Реализация результатов работы. Представленные в работе исследования по созданию моделей, методов и средств структурных испытаний программ в рамках языково-ориентированного подхода выполнены в рамках научно-исследовательских тем ИАПУ ДВО РАН: "Развитие методов и инструментальных средств решения задач математического моделирования, исследования операций, математического программирования, автоматизированной обработки знаний и графической информации с использованием параллельных вычислений и многопроцессорных вычислительных комплексов", № гос. регистрации 01200205277; "Методы и средства технологии автоматизированной обработки знаний, специфицирования и анализа программного обеспечения, распределенных вычислительных систем, обработки и визуализации графической информации с применением параллельных вычислений", № гос. регистрации 01.99.00 05772; "Методы и средства технологии создания экспертных систем, основанных на системах логических соотношений", № гос. регистрации 01.9.50006915.
В указанных работах автор принимал участие в качестве исполнителя.
Апробация работы. Основные научные и практические результаты работы докладывались и обсуждались на следующих конференциях и семинарах:
IV Международной конференции "Качество программного обеспечения информационных технологий" (Дагомыс, 1992);
Впадение J 2
IV Международной конференции "Измерения, контроль и автоматизация производственных процессов" (Барнаул, 1997);
Региональной научной конференции "Молодежь и научно-технический прогресс" (Владивосток, 1998);
Дальневосточной математической школе-семинаре им. Е.В.Золотова (Владивосток, 1999 и 2000 гг.);
IV Всероссийской научной Internet-конференции "Компьютерное и математическое моделирование в естественных и технических науках" (Тамбов, 2002);
10-й Международной конференции SoftCOM-2002 "Программное обеспечение, телекоммуникации и компьютерные сети" (Сплит (Хорватия), Венеция, Анкона (Италия), Дубровник (Хорватия), 2002); совместных научных семинарах отдела экспертных систем ИАПУ ДВО РАН и факультета компьютерных наук Института математики и компьютерных наук ДВГУ. і
Публикация результатов работы. По теме диссертации опубликовано 14 печатных работ [21, 23, 24, 25, 26, 27, 28, 37, 38, 39, 40, 41, 42, 73]. I
Личный вклад автора. Все результаты, составляющие основное содержание диссертационной работы, получены автором самостоятельно. В работе [25] автором диссертационной работы разработаны определения понятий контекст и потенциальный контекст в программе или ее фрагменте и модель множества потенциальных контекстов фрагмента программы. В работах [26, 73] автором разработаны формальные определения традиционных методов и метрик покрытия испытаниями семантических языковых конструкций программной единицы. В работе [27] автором разработаны формальные определения традиционных методов и метрик покрытия испытаниями компонентов графа потока управления.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы и пяти приложений. Основная часть работы содержит 164 страницы текста, 24 рисунка. Список литературы содержит 106 наименований.
Первая глава диссертационной работы посвящена рассмотрению основных используемых в работе понятий, связанных с измерениями, испытаниями и оценкой качества программного обеспечения. Приведены неформальные определения из наиболее известных литературных источников традиционных, т.е. чаще других описываемых в специальной литературе и/или используемых на практике, методов покрытия испытаниями потока управления и потока данных в программной единице.
Вторая глава посвящена решению первой задачи диссертационной работы. В ней формально в терминах измерительной языковой модели определены традиционные методы и метрики структурных испытаний программной единицы.
В третьей главе на основе анализа особенностей императивных языков программирования и написанных на них текстов программ даны определения понятий контекст и потенциальный контекст в программе или ее фрагменте. Здесь же определены принципы построения модели множества потенциальных контекстов фрагмента программы, представлена разработанная модель и определен процесс построения моделей множеств потенциальных контекстов в различных видах фрагментов.
В четвертой главе диссертационной работы определен метод покрытия испытаниями потенциальных контекстов программной единицы и проведено сравнение традиционных методов структурных испытаний и метода покрытия испытаниями потенциальных контекстов.
Пятая глава посвящена решению третьей и четвертой задач диссертации. В ней описаны разработанные методы реализации функций динамических измерений программ при использовании систем построения трансляторов и программное средство измерения процесса исполнения программ, поддерживающее структурные испытания программных единиц, написанных на языке программирования Турбо Паскаль 7.0.
Пиша J
