Содержание к диссертации
Введение
Глава 1 Обзор существующих методов обеспечения качества программных систем и постановка задачи исследования 7
1.1 Жизненный цикл пс 7
1.2 Модели жизненного цикла по 10
1.3 Основные источники ошибок 14
1.4 Постановка задачи тестирования программных систем 26
1.5 Особенности тестового диагностирования пс 29
1.6 Методы построения тестов 35
1.7 Постановка задачи исследования 37
Глава 2 Математическая модель и стратегии определения состояния программных систем 40
2.1 Ориентированный упорядоченный граф 42
2.2 Матричная модель 45
2.3 Обобщённая вероятностно-структурная модель 53
2.4 Стратегия определения состояния системы 55
2.5 Выводы 56
Глава 3 Методы и алгоритмы обеспечения контролепригодности программных систем 57
3.1 Оптимизация принятия решения о состоянии пс 58
3.2 Оптимизация выбора множества тестов 63
3.3 Организация виртуальных программных модулей (впм) 70
3.4 Выводы 72
Глава 4 Практические аспекты проблемы обеспечения контролепригодности программного комплекса 74
4.1 Имитационная модель n-канальной системы массового обслуживания 74
4.2 Выводы 82
Библиографический список
- Модели жизненного цикла
- Обобщённая вероятностно-структурная модель
- Оптимизация выбора множества тестов
- Имитационная модель n-канальной системы массового обслуживания
Введение к работе
Актуальность работы
Создание программных систем (ПС) с постоянно расширяющимся составом программных модулей, приводит к необходимости правильного и своевременного решения проблемы обеспечения их надежной и эффективной работы.
В обеспечении требуемого уровня надежности и качества функционирования ПС особая роль принадлежит диагностированию, по результатам которого определяется их действительное состояние. Эффективность диагностирования ПС в свою очередь во многом определяется их контролепригодностью. Разработка ПС без учета требований контролепригодности приводит к большим затратам на тестирование, которые в среднем составляют 40-50% общих затрат на разработку программ, а в отдельных случаях и более.
Основной вклад в решение проблемы диагностирования ПС внесли П.П.Пархоменко, П.А.Правильщиков, В.А.Гуляев, В.В. Липаев, В.И.Сагунов, СИ. Беляева, Р. Гласе, Т. Тайер, Г. Майерс, C.V. Ramamoorthy и другие российские и зарубежные ученые. Тем не менее, остается еще обширная область нерешенных вопросов и проблем, например, не решена в общем виде задача локализации ошибок произвольной кратности. Кроме этого, на пути реализации известных алгоритмов возникают сложности, связанные с большим объемом вычислений.
Таким образом, проблема разработки методов и алгоритмов обеспечения контролепригодности ПС является актуальной.
В диссертационной работе обосновывается целесообразность применения/информационного подхода для решения данной проблемы и включение статистического моделирования в процесс диагностирования, что позволяет обойти трудности реализации, связанные с большим объемом вычислений.
Диссертационная работа выполнялась по межвузовской научно-технической программе «Диагностические и информационно-поисковые системы».
Цель работы.
Разработка диагностической модели программных систем (ПС) и методов локализации ошибок по информационному критерию. Задачи работы. Достижение намеченной цели требует решения следующих задач:
разработка математической модели для диагностирования программных систем на основе их структурных свойств;
разработка оптимальных методов принятия решения о состоянии ПС по результатам тестового контроля;
выбор оптимального множества тестов и последовательности их выполнения;
иерархическая организация программных модулей с целью повышения эффективности локализации ошибок. Методы исследования.
Для теоретических исследований применялись методы теории множеств, теории графов, теории информации, теории булевых функций, теории вероятностей.
Научная новизна работы.
Разработаны диагностическая модель и методы локализации ошибок. Новым в предлагаемых методах является:
использование информационного критерия качества локализации ошибок как универсального по отношению к различным классам систем;
локализация ошибок произвольной кратности с учетом вероятностей отказов программных модулей.
включение статистического моделирования ошибок в процесс выбора оптимального набора тестов.
- объединение программных модулей в виртуальные программные
модули (ВПМ) с целью повышения эффективности локализации
ошибок за счет соответствующей иерархической организации ПС.
Обоснованность и достоверность результатов обеспечена корректностью используемого математического аппарата и представленными результатами статистического моделирования. Практическая ценность работы.
Разработанные в диссертационной работе методы и алгоритмы выбора оптимального набора тестов позволили повысить эффективность отладки ПС.
Реализация результатов работы.
Разработанные в диссертационной работе методы и алгоритмы используются в Информационно-вычислительном центре Нижегородского государственного технического университета и в учебном процессе в виде фрагментов лекций по курсам «Прикладная теория информации», «Проектирование вычислительных систем и устройств» и пакета прикладных программ для проведения лабораторных работ.
Апробация работы.
Материалы диссертационной работы докладывались на следующих научных конференциях:
- V Международной конференции «НТИ-2000. Информационные
технологии и телекоммуникации» (Москва, ВИНИТИ, 2000);
VI Международной конференции «НТИ-2002. Информационное общество. Интеллектуальная обработка информации. Информационные технологии» (Москва, ВИНИТИ, 2002);
Международной научно-технической конференции «Современные информационные технологии» (Пенза, ПТИ, 2004);
14-ой Международной научно-практической конференции по графическим информационным технологиям и системам. КОГРАФ-2004. (Нижний Новгород, НГТУ, 2004);
Региональной научно-технической конференции . «Актуальные вопросы построения систем управления сложным распределенным оборудованием и предоставлением услуг» (Нижний Новгород, «ТЕКОМ», 2004).
Публикации.
По теме диссертационного исследования опубликовано 12 работ. Структура и объём работы.
Диссертационная работа состоит из введения, четырёх глав, заключения, библиографического списка и приложений.
Модели жизненного цикла
Основным недостатком каскадного подхода является существенное запаздывание с получением результатов. Согласование результатов с пользователями производится только в точках, планируемых после завершения каждого этапа работ, требования к ИС "заморожены" в виде технического задания на все время ее создания. Таким образом, пользователи могут внести свои замечания только после того, как работа над системой будет полностью завершена. В случае неточного изложения требований или их изменения в течение длительного периода создания ПО, пользователи получают систему, не удовлетворяющую их потребностям. Модели (как функциональные, так и информационные) автоматизируемого объекта могут устареть одновременно с их утверждением. Для преодоления перечисленных проблем была предложена спиральная модель ЖЦ (рис. 1.4), делающая упор на начальные этапы ЖЦ: анализ и проектирование. На этих этапах реализуемость технических решений проверяется путем создания прототипов. Каждый виток спирали соответствует созданию фрагмента или версии ПО, на нем уточняются цели и характеристики проекта, определяется его качество и планируются работы следующего витка спирали. Таким образом, углубляются и последовательно конкретизируются детали проекта, и в результате выбирается обоснованный вариант, который доводится до реализации.
Разработка итерациями отражает объективно существующий спиральный цикл создания системы. Неполное завершение работ на каждом этапе позволяет переходить на следующий этап, не дожидаясь полного завершения работы на текущем. При итеративном способе разработки недостающую работу можно будет выполнить на следующей итерации. Главная же задача - как можно быстрее показать пользователям системы работоспособный продукт, тем самым активизируя процесс уточнения и дополнения требований.
Основная проблема спирального цикла - определение момента перехода на следующий этап. Для ее решения необходимо ввести временные ограничения на каждый из этапов жизненного цикла. Переход осуществляется в соответствии с планом, даже если не вся запланированная работа закончена. План составляется на основе статистических данных, полученных в предыдущих проектах, и личного опыта разработчиков. Рис 1.4. Спиральная модель ЖЦ
Понятие ошибки в программе трактуется в среде программистов неоднозначно. Согласно Майерсу [48] считается, что в программе имеется ошибка, если она не выполняет того, что разумно ожидать от нее пользователю. "Разумное ожидание" пользователя формируется на основании документации по применению этой программы. Следовательно, понятие ошибки в программе является существенно не формальным.
Для выявления типов ошибок имеет смысл посмотреть на причины их появления и возможные источники. В [56] предлагается рассматривать первоначально ошибки в том порядке, в котором они чаще всего возникают на различных этапах ЖЦ ПО.
При разработке общих требований к вычислительной (управляющей) системе, которая должна управлять некоторым объектом, часто возникают ошибки, которые при создании ПО приводят, к так называемым, системным ошибкам. Их появление объясняется тем, что, как правило, заказчик не знает всех свойств управляемого объекта и процесс управления этим объектом с помощью вычислительной системы никогда ранее не был реализован. Кроме того, очень часто создание требований к вычислительной системе не формализовано и не автоматизировано, и отсюда эти требования могут содержать много ошибок, являются и неполными, и неоднозначными.
На этапе разработки требований к ПО управляющей системы часто возникают ресурсные ошибки, в результате которых неточно определяются распределения ресурсов ЭВМ по производительности. Для диагностирования этих ошибок могут быть применены различные виды моделирования и имитации будущего программного продукта и управления объектом в различных условиях.
На этапах эскизного проектирования чаще всего возникают алгоритмические ошибки, т. е. такие ошибки, которые приводят к разработке и описанию алгоритма, отличающегося от требуемого, корректного алгоритма. Причинами этого являются неполное и неоднозначное техническое задание, полученное на предыдущих этапах разработки ПО.
К ошибкам эскизного проектирования добавляются документационные ошибки и ошибки интерфейса между модулями при разработке детального проекта.
На этапах кодирования и автономной отладки чаще всего возникают программные ошибки — ошибки в командах, макрокомандах, стандартных блоках и связях между ними. Сюда же следует отнести и ошибки неадекватного, выборочного или интуитивного тестового диагностирования, которое проводит программист.
На этапе комплексной отладки возникают ошибки неправильного выбора критерия диагностирования, неправильного, определения вероятности (частоты) различных ситуаций при эксплуатации ПО.
К этапу эксплуатации в [56] относят два типа ошибок: технологические и вторичные. Технологические ошибки — это ошибки, возникающие при тиражировании ПС и при записи их на системные носители информации. Вторичные ошибки — это ошибки, порожденные исправлением обнаруженных во время эксплуатации ошибок ПО, а также ошибки, вносимые в него при различных его модификациях и усовершенствованиях. Кроме этого в литературе используются и другие подходы к классификации ошибок, например, в работе [56] также рассматривается классификация ошибок по структурному признаку, т.е. те ошибки, которые вносят некоторые изменения в структуру корректной программы.
Обобщённая вероятностно-структурная модель
Следующий этап в реализации процедуры тестирования - построение тестовых примеров. В этой области очень широко разрабатываются методы символического моделирования тестов. При этом вдоль каждого пути тестирования записываются условия прохождения программы по этому пути в виде некоторого предиката. Получаемая в итоге система предикатов решается методами математического программирования. Найденное таким образом решение определяет совокупность тестовых примеров обнаружения ошибки. Методы символического тестирования были предложены в работах [9-11,26,36,69]. Для решения систем неравенств, получаемых на путях тестирования в работе [11] применяется метод проб и ошибок, а в работах [9-10] - методы линейного и нелинейного программирования. В работе [69] решается одна из сложнейших задач символического тестирования определение функции программы. Функция программы рассматривается здесь как полная система функций путей тестирования программы.
В работах [26,36] рассмотрена система автоматизации тестирования программ, в основе которой лежит символическое моделирование тестов. В работе [58] сделана попытка объединить структурный подход и символическое моделирование.
Рассмотренные в работах [9-11,26,36,58,69] методы символического тестирования ориентированы главным образом на обнаружение, ошибок. В работе [56] указывается, как одно из главных направлений в диагностировании программных средств, разработка методов не только обнаружения, но и локализации ошибок. Эта задача аналогична задаче локализации дефектов в технических системах, однако имеет ряд существенных отличий, делающих ее более сложной. К ним относятся отсутствие эталонного описания функции, реализуемой программой, многообразие типов возможных ошибок, мест их возникновения и форм их проявления [52].
В ряде работ [49,64,65] рассматривается возможность использования дампов памяти для локализации некоторых ошибок. Однако, как указано в [49], общая методология выявления причины ошибки посредством анализа дампа памяти отсутствует. Не ясно, в каких точках распечатка состояния памяти способна дать информацию об имеющихся ошибках.
Второе направление развития методов отладки связано с введением в программу регистрирующих операторов в некоторых контрольных точках [12,49,52,66]. Однако метод выбора этих контрольных точек носит неформализованный характер, а поиск ошибки часто ограничивается лишь сужением области исследования
В некоторых работах [12,52,64-66] предлагается оценивать в контрольных точках результаты тестирования.
Помимо общих идей отладки программ, предложенных в работах [49,52,66] существуют методы, направленные на локализацию конкретных видов ошибок [27,38,39]. Так в работе [38] предложен комплекс программ диагностирования некоторых типов одиночных ошибок: логических, функциональных, ошибок прерывания. В работе [27] рассмотрен вопрос применения средств языка КОБОЛ для определения оператора, вызывающего несанкционированное прерывание или аварийное завершение. Интересным представляется использование аппарата сетей Петри для локализации информационной или вычислительной ошибки по результатам тестирования [37]. Однако модель, содержащая одновременно связи по управлению и по информации, в этом случае выглядит довольно громоздкой.
В работе [66] подробно изложен достаточно эффективный метод поиска устойчивых ошибок в программах (ПУО). Он заключается в поочередном обнаружении ошибок, разделенных на классы и включенных в каталог, по их описаниям. Множество локализуемых ошибок определяется размером каталога и количеством реализуемых алгоритмов поиска, т.е. может быть достаточно большим. Из анализа эффективности трех основных методов отладки (тестирования, ПУО, верификации) авторы работы [бб] делают важный вывод, что эти методы являются не альтернативными, а дополняют друг друга. Их совместное применение позволяет более эффективно и полно решать задачу отладки программ. Отсюда следует необходимость дальнейшего развития всех трех направлений.
Оптимизация выбора множества тестов
В качестве количественной меры глубины поиска ошибки введём коэффициент к _ I(SJ) H(S) который показывает, какую часть составляет доставляемая вектором У) информация от информации H(S), необходимой для определения состояния системы. Коэффициент характеризует относительный средний размер области локализации ошибки.
Для точного определения состояния системы необходимо, чтобы количество информации, которое в среднем доставляет диагностический эксперимент, определялось как I(S,Y)=H(S). В этом случае коэффициент глубины диагностирования К-1. Если же невозможно получить какую-либо информацию о состоянии системы, то /0=0.
Поскольку условная неопределённость появления результатов измерений Y при заданном состоянии системы Sk равна нулю, то условная энтропия Я( %)=0 и, следовательно, I(S,Y) = H(Y). При этом коэффициент глубины диагностирования К определяется по формуле К = Ш (3.2.3) H(S) Поскольку состояния отдельных блоков считаются статистически независимыми, то энтропия системы равна сумме энтропии отдельных блоков: H(S) = ±H(XJ)i где Xj - множество состояний j-ro блока, (есть ошибка/нет ошибки), принимающее значение нуля и единицы. Энтропия 7-го блока H(XJ) = -PJ logPy -(l-Pj)logQ.-Pj). Где Pj вероятность наличия ошибки BJ -OM блоке.
Если априорно известно, что в системе произошла по крайне мере одна ошибка, то исправное состояние S„ исключается из множества состояний системы. Обозначим через q вероятность ошибки в системе q = l-p{Su) , где р(5и) - вероятность исправного состояния. Тогда it=i Ч Ч Ч к=\ к=\ ч Поскольку 2j p(sk) 1 =i q и -2-p(Sk)\0ep(Sk) = H(Sk) + p(Su)\ogp(Su) \ получим ff(S) = -(H (S) + p(S.)logp(Su)) + log? (324) где //(5) - значение энтропии состояния системы, вычисленное по формуле (3.2.1). Оптимизацию матрицы путей можно реализовать по информационному критерию. При этом решаются две задачи: 1. определение минимального множества тестов, необходимого для обеспечения заданной глубины диагностирования; 2. определение глубины диагностирования при заданном множестве тестов.
Для решения указанных выше задач необходимо упорядочить пути по количеству информации, которое они доставляют.
В качестве первого пути выбираем путь, который доставляет максимальное количество информации, а в качестве каждой последующей выбираем путь, который доставляет максимальное дополнительное количество информации. Располагая упорядоченной последовательностью путей, можно определить их минимальное подмножество, которое обеспечивает заданную глубину диагностирования, или максимизировать глубину диагностирования при заданном количестве путей.
Для нахождения коэффициента глубины диагностирования необходимо вычислить энтропии векторов S и У. Энтропия вектора S при заданных значениях вероятностей отказов блоков находится априорно по формуле (3.2.1), если рассматривается всё множество состояний системы, включая исправное, или по формуле (3.2.4), если априорно известно, что в системе произошла ошибка.
На каждом шаге алгоритма вычисление энтропии вектора У производится следующим образом: 1. проводится Л/ испытаний, в каждом из которых генерируется вектор состояния S; 2. для каждого вектора состояния определяется вектор результатов измерений У; Y=BS; 3. с каждым появившимся вектором Y связывается счетчик, который увеличивается на единицу при очередном появлении такого вектора. 4. производится вычисление энтропии вектора У п п: H{Y) = -У -log tx N N где X - множество появившихся векторов У, л,- - значение счетчика вектора У/. Для определения упорядоченной последовательности путей представим матрицу путей В в виде ґи\ В= \bmJ где bir i = \,m - строки исходной матрицы В. На первом шаге в качестве матрицы путей выступают поочерёдно строки исходной матрицы. При выборе каждой строки производится вычисление энтропии вектора результатов тестирования по изложенному выше алгоритму. Окончательно, в качестве матрицы путей на первом шаге выбирается та строка исходной матрицы, которой соответствует максимальное значение энтропии H(Y), что равносильно выбору первого пути, номер которой определяется номером выбранной строки. При выборе к-го пути перебираются все возможные матрицы путей (В \ где V - множество номеров строк исходной матрицы В, не задействованных в матрице fl .j. В качестве окончательной матрицы Вк выбирается такая матрица Bj, для которой энтропия вектора Y окажется максимальной, а к множеству путей полученном за к-1 шагов добавляется очередной путь, соответствующий выбранной строке.
На каждом шаге алгоритма вычисляется коэффициент глубины диагностирования, соответствующий выбранному множеству путей. Результатом работы алгоритма является диаграмма зависимости коэффициента глубины диагностирования от номера пути. С помощью полученной диаграммы можно выбрать оптимальным образом множество путей, обеспечивающих заданную глубину диагностирования или определить максимальную глубину диагностирования, обеспечиваемую любым заданным множеством путей. Программная реализация данного алгоритма приведена в Приложении 1 данной работы.
Имитационная модель n-канальной системы массового обслуживания
При однократной ошибке, когда вектор S содержит одну единицу, между возможными состояниями системы, количество которых равно п, и блоками можно установить взаимно однозначное соответствие. В этом случае подмножества блоков, соответствующие разным У,- не будут пересекаться, и они могут быть объединены в один ВПМ. Таким образом, по результатам измерения Y) однозначно определяется ВПМ.
При многократной ошибке подмножества блоков, соответствующие разным Yj, будут пересекаться и поэтому блоки, попавшие в пересечение, целесообразно объединить в отдельные ВПМ. Формирование структуры указанных подмножеств осуществляется методом статистического моделирования.
Исходными данными для определения ВПМ являются матрица путей В и диаграмма, характеризующая изменение коэффициента глубины диагностирования на упорядоченном множестве путей. 1. Приближенно задаются размеры ВПМ посредством задания коэффициента глубины диагностирования, что эквивалентно заданию среднего числа блоков б, с точностью до которого может быть локализована ошибка. 2. Определяется минимальное множество путей, которое обеспечивает заданную глубину диагностирования и на полученном множестве путей строится соответствующая матрица путей. 3. Проводится серия испытаний, в каждом из которых с помощью генератора случайных чисел формируется вектор состояния системы. 4. По состоянию системы с использованием матрицы путей вычисляется соответствующий вектор результатов измерений Y-BS. 5. Для каждого вектора результатов измерений определяется множество подозреваемых на отказ блоков по изложенному выше алгоритму. 6. Каждому блоку системы ставится в соответствие счетчик, в который после очередного испытания прибавляется единица, если этот блок л , попал в подмножество подозреваемых на отказ (число исходов). 7. Для каждого блока системы определяются относительные частоты его появления во множестве блоков подозреваемых на отказ. Блоки, с близкими значениями относительных частот, объединяются в одну конструктивную единицу.
В процессе работы программы (Приложение 1), реализующей данный алгоритм, формируется диаграмма, на которой номера блоков отсортированы в соответствии с относительными частотами таким образом, что создаётся наглядное представление о множестве ВПМ системы.
Таким образом, распределение элементов системы по ВПМ с целью повышения контролепригодности определяется структурой системы и вероятностями отказов блоков при минимальном количестве путей.
Рассматривается л-канальная СМО общего вида. На вход системы поступает общий поток заявок, закон распределения которого известен. Заявки выстраиваются в очередь и обслуживаются в соответствии с заданной дисциплиной обслуживания. Система имеет п абсолютно надежных каналов, и дисциплина выбора канала задана. Длительность г" обслуживания каждой заявки случайна. Закон распределения длительности обслуживания известен и зависит от номера канала обслуживания. В результате имитации необходимо получить совокупность заданных характеристик обслуживания.
Полагаем, что программы реализации алгоритмов формирования потока заявок, длительностей обслуживания, записи времени поступления заявки в буфер и выбора из буфера, определения требуемых характеристик, выбора свободного канала в соответствии с требуемой дисциплиной имеются в виде проверенных программных модулей.
Тогда блок-схема алгоритма имитации л- канальной СМО может быть представлена в виде, изображенном на рис.4.1. Каждый блок этой схемы соответствует некоторому модулю, цепочке операторов или оператору программы. Сама блок-схема представляет некоторый программный комплекс.
Соответствующая элементарная структура в виде упорядоченного графа переходов представлена на рис.4.2. На схеме рис.4.1 вдоль дуг проставлены номера соответствующих вершин графа переходов. Минимальная матрица путей, покрывающих граф, представлена на рис.4.3. Формир. t
Данная диаграмма позволяет решить следующие задачи: определить максимальное значение коэффициента глубины диагностирования, достижимое на исходном множестве путей - /0=0,92; определить минимальное множество путей для получения требуемого коэффициента глубины диагностирования, например, для получения коэффициента глубины диагностирования /0=0,5 достаточно организовать 3 пути соответствующие 7,1 и 2 строкам матрицы путей. На рис.4.5 приведена диаграмма частот появления блоков во множестве подозреваемых на отказ, на основании которой можно выполнить разбиение объекта на ВПМ. В ВПМ объединяются блоки с равными значениями полученных частот. В ВПМ будут выделены блоки с номерами {1,30,7}, {28,3,8}, {2,29,27,5,10,9,26,4,6}, {19,14,20,15,12,17}, {11,16}, {25,18,24,13}, {22,23,21}.
Похожие диссертации на Структурно-статистические методы обеспечения контролепригодности программных систем
