Software & Systems

За последнее десятилетие в области разработки ПО произошли коренные изменения. Средства разработки ПО позволяют автоматически генерировать исходный текст, использовать шаблоны проектирования программ, повторно использовать компоненты, объекты, выполнять рефакторинг, а также имеют другие возможности, ускоряющие проектирование ПО. В то же время все эти широкие возможности не только увеличивают количество программных подсистем в разрабатываемом проекте, но и усложняют взаимосвязи между ними, неизбежно усложняя процесс поиска ошибок в проекте и снижая его надежность. В связи с этим основным инструментарием обеспечения надежности программного проекта являются методы тестирования на разных стадиях жизненного цикла программ (особенно на завершающей) с целью обнаружения ошибок при некорректно предоставляемых данных и построение упрощенных формальных спецификаций сложного «большого» проекта, отражающих его основные свойства и требования на том или ином формально-логичес­ком языке для логического обоснования корректности исходного программного проекта. Однако существует математическая теория надежности ПО, строящаяся подобно математической теории систем. Значительным плюсом такого подхода к надежности ПО является не только возможность констатации фактов вида «в ПО есть ошибки либо с такой-то вероятностью нет ошибок», но и более широкая постановка вопроса: как на основании имеющихся и измеряемых в процессе работы ПО показателей, не имея доступа к исходному тексту программ, математически обоснованно рассчитать вероятность появления или количество ошибок через какое-либо время работы программы в будущем. Одному из таких способов посвящена данная работа.

Математическая модель

Предлагаемая авторами модель будет опираться на математическую модель из работы [1], в основе которой лежит неоднородный пуассоновский процесс {N(t), t³0}, характеризующийся следующими допущениями. Во-первых, программы запускаются в неперекрывающиеся интервалы времени [(0, t1), (t1, t2), …, (ti–1, ti), …, (tm–1, tm)]. Во-вторых, количество ошибок (f1, f2, …, fm) на каждом интервале не зависит от других интервалов, а каждая ошибка устраняется сразу после ее выявления. В-третьих, кумулятивное количество ошибок, обнаруженных на момент времени t, имеет пуассоновское распределение со средним m(t). И наконец, каждая ошибка может быть обнаружена с одинаковой вероятностью, приводит к одинаковым негативным последствиям, интервалы обнаружения ошибок имеют одинаковую размерность (сутки, неделя, месяц и т.п.).

Функция m(t) является неубывающей и ограниченной сверху, то есть

m(t)=0 при t=0, m(t)=a при t®¥,                       (1)

где a – количество ошибок в ПО, которое в принципе в нем содержится и может быть обнаружено.

Если принять, что количество ошибок в ПО, обнаруженных на интервале времени Dt, пропорционально количеству ошибок, имеющихся в ПО, но пока не обнаруженных, то с учетом (1) имеем:

.     (2)

Из выражения (2) при Dt®0 получаем дифференциальное уравнение

,                                              (3)

решая которое с условиями (1), находим среднее количество ошибок

.                                                 (4)

Интенсивность ошибок из выражений (3) и (4) получаем как

.                                          (5)

Процесс моделирования ошибок с функцией интенсивности l(t) выполняется в соответствии со стохастическим процессом:

– если не возникают ошибки за время Dt, то

; (6)

– если за время Dt возникает одна ошибка,

;       (7)

– если за время Dt возникают две (и более) ошибки,

P{N(t, Dt)–N(t)=2}=o(Dt).                                    (8)

Таким образом, возникновение fi ошибок на интервале времени (0, ti) будет

,                          (9)

где i – некий интервал времени, в процессе которого программа загружена и исполняется; fi – число ошибок, возникших за период времени i; ti – кумулятивное время исполнения программы, включая интервал i, то есть совокупность всех времен исполнения программы; m(ti) – функция средней интенсивности ошибок для времени, , где l(s) – функция интенсивности.

Для дальнейших численных расчетов среднюю интенсивность ошибок можно приравнять к среднему количеству ошибок li, обнаруживаемых на i-м интервале, и тогда выражение (9) будет представлять собой известную модель Гоэла–Окумото (см. [1]):           .

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

                       (10)

где m – интенсивность устранения ошибок.

Задача моделирования состоит в определении параметров интенсивности обнаружения и устранения ошибок (l и m соответственно) в ПО в выражении (8), причем для каждого ti-го интервала времени.

Очевидно, что в данном случае при наличии выборки данных, содержащей кумулятивное количество обнаруженных ошибок к некоторому ti-му интервалу времени, для определения параметров l и m подходящим оказывается метод максимального правдоподобия [2].

Функция правдоподобия имеет вид

,                         (11)

где I – общее число временных интервалов наблюдения ошибок.

Прологарифмируем выражение (11):

       (12)

Подставив вместо li в выражении (12) функцию из выражения (10), получаем

                 (13)

Чтобы найти максимум для данной функции, возьмем частную производную по переменной l:

.                        (14)

Просуммировав выражение (14), получаем

,

где f+ – кумулятивное число ошибок для всех i-х периодов времени.

Приравнивая к нулю производную (14), получаем выражение для оценки интенсивности обнаружения ошибок

.                                                       (15)

Подставив  из выражения (15) в выражение (13), взяв производную по переменной m и приравняв ее к нулю, получаем

                                    (16)

Рассмотрим нахождение начального значения m. Пусть

;                                                                 (17)

.                     (18)

Из выражений (16)–(18) видно, что s и x связаны соотношениями s=[x/(1–x)], x=[s/(1+s)]. Начальное значение x0 можно отыскать по формуле

,                                                           (19)

то есть разделив количество ошибок, полученных за первую половину времени исполнения программы, на количество ошибок, полученных за вторую половину времени исполнения программы. Далее подставляем полученное значение x в формулу (17) и получаем начальное значение m, для уточнения которого используется итеративный процесс

.                (20)

Алгоритмы нахождения оценок параметров и прогнозирования показателей надежности ПО

Для оценки l применим метод размножения выборок, известный как метод бутстреппинга [3]. Исходной информацией является выборка наблюдаемых значений (массив данных), в данном случае содержащая три показателя (см. табл.).

Таким образом, при методе бутстреппинга, имея некоторую выборку конечной размерности n, то есть эмпирическое распределение, и используя датчики случайных чисел, из нее можно сформировать любое количество размноженных выборок. Здесь вероятностное распределение в формируемых выборках должно подчиняться пуассоновскому распределению. Рассмотрим алгоритм формирования случайных чисел, распределенных по закону Пуассона.

Алгоритм 1. Формирование бутстреп-выбо­рок.

Входные параметры: массив наблюдаемых значений M={m1, m2, …, mi, mn} количества ошибок за время исполнения программы; t=0 – текущее время; T – общее время моделирования; I=0 – количество событий за время моделирования T; l – интенсивность ошибок; j – текущий элемент массива; n – размерность выборки.

1. Пока j£n.

2. Генерация случайного числа с равномерным распределением U~U(0, 1) на отрезке (0, 1).

3. 

4. Если t>T, то завершить моделирование и выдать результаты.

5. Генерация случайного числа с равномерным распределением U~U(0, 1)  на отрезке (0, 1).

6. Если

7. Сформировать строки массива M1={S1(I), m2, …, mj, mn}, поочередно заменяя значение в исходной выборке сгенерированным значением, получая тем самым массивы M2={m1, S2(I), …, mj, mn}, …, Mj={m1, m2, …, Sj(I), mn}, Mm={m1, m2, …, mj, …, Sn(I)}.

8. Конец алгоритма.

Алгоритм 2. Нахождение оценки m.

Входные параметры: начальное значение x0 (формула (19)); TF – общее кумулятивное количество ошибок за все время исполнения программы; массив времени исполнения программы T – второй столбец из таблицы; массив сформированных размноженных выборок M из алгоритма 1; n – размерность массивов T и M; eps – точность; time – общее время исполнения программ.

1. .

2. Повторять

2.1. ;

2.2. Цикл от 1 до n (расчеты по формуле (20)):

2.2.1. 

2.2.2. 

2.2.3. 

2.2.4. 

2.2.5. Конец цикла по n;

2.3. Если t4<0,01, тогда t4=0,01;

2.4. 

2.5. 

2.6. t4=0;

2.7. 

2.8. Конец цикла. Повторять, пока

½MuNew–Mu½£eps.

3. Результат. Вывод Mu.

4. Конец алгоритма.

Опишем общую процедуру прогнозирования ожидаемого количества ошибок, которые могут проявиться при дальнейшем исполнении программ на интервале времени t, следующем за кумулятивным интервалом наблюдения tI. В соответствии с рассматриваемым неоднородным пуассоновским процессом среднее ожидаемое количество ошибок

            (21)

Оценка параметров по предложенным алгоритмам 1 и 2 позволяет записать выражение (21) с использованием оцененных параметров  и :

Шаги процедуры следующие.

1. Получить оценки , где b=1, 2, …, B, размноженные методом бутстреппинга-выборки (всего B оценок средней интенсивности ошибок).

2. Отсортировать по возрастанию полученные оценки средней интенсивности ошибок .

3. Определить требуемые доверительные интервалы (обычно нижнее значение a=0,05, а верхнее значение a=0,95) и отсечь не входящие в эти интервалы оценки.

4. Используя оценку среднего значения и известные свойства функции распределения Пуассона, можно ожидать, что на интервале времени tI, tI+t количество ошибок будет не более .

Реализация ПО

Предложенный в статье метод прогнозирования был реализован в виде программы, написанной на языке Паскаль в свободной среде программирования PascalABC.NET [4]. Программа включает следующие функции: FirstValue – определение начального значения x0 (по выражению (19)); FindMu – определение оценки m (по алгоритму 2); GenerateLambdas – определение оценки l по методу размножения выборок (алгоритм 1); Assign­Poissons – нахождение случайных чисел по распределению Пуассона (элемент алгоритма 1).

Исходные данные читаются из файла, имеющего табличную структуру (см. рис.).

Первый столбец содержит кумулятивное время исполнения программы (например в днях), а второй – количество ошибок, зафиксированных в определенные временные интервалы (например, через 5 дней были обнаружены и исправлены 3 ошибки в ПО).

При запуске программы с данным тестовым файлом можно увидеть результаты, например, прогноза проявления ошибок в ПО с 95 %-ным доверительным интервалом на будущие 10 дней.

При необходимости доверительный интервал можно изменить.

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

Литература

1.     Hoang Pham. System Software Reliability. Springer-Verlag Limited. London, 2006, pp. 440.

2.     Магнус Я.Р., Катышев П.К., Пересецкий А.А. Эконометрика. Начальный курс. М.: Дело, 2007. 504 с.

3.     Эфрон Б. Нетрадиционные методы многомерного статистического анализа: сб. статей; [пер. с англ.; предисл. Ю.П. Адлера, Ю.А. Кошевника]. М.: Финансы и статистика, 1988. 263 с.

4.     URL: http://pascalabc.net (дата обращения: 20.06.2012).