Имитационное моделирование процессов возникновения ошибок для оценки надежности программного обеспечения

УДК 681.3

ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ВОЗНИКНОВЕНИЯ ОШИБОК ДЛЯ ОЦЕНКИ НАДЕЖНОСТИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

© 2012 г. М.А. Бутакова, С.В. Чубейко

Ростовский государственный университет Rostov State Transport

путей сообщения University

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

Ключевые слова: модель надежности программного обеспечения; неоднородный пуассоновский процесс; имитационное моделирование.

Article is devoted to aspects of simulation offault rate processes by stochastic processes theory methods for software reliability assessment. The task of simulation is considered within model of reliability based on the non-homogeneous Poisson process. Algorithms of simulation modeling of stochastic Poisson processes in the one-dimensional and two-dimensional cases, including models ofprocesses on a circle and irregular form region are offered. The offered algorithms are provided in the detailed steps, allowing to execute their practical program implementation.

Keywords: software reliability model; non-homogeneous Poisson process; simulation modeling.

Введение

Большинство систем, применяемых в качестве средств автоматизации технологических процессов на производстве, в промышленности, на транспорте и в других отраслях, являются программно-управляемыми. Качество функционирования таких систем зависит не только от качества аппаратных средств, применяемых в их составе, но и от качества программного обеспечения (ПО), важнейшей характеристикой которого является надежность. Вопросы анализа и моделирования надежности ПО привлекают внимание исследователей, начиная с 1970-х гг., а результатами многолетних усилий является разработка более пятидесяти моделей [1]. Авторы также ранее рассматривали общую постановку задачи оценки качества программного обеспечения в условиях возникновения пиковых информационных нагрузок [2].

Несмотря на такое внушительное количество математических моделей, предназначенных для оценки надежности ПО, следует отметить наличие близкого сходства между многими из них. Это сходство заключается в применении наиболее распространенных в математической теории надежности систем вероятностных распределений экспоненциального вида для моделирования средних значений интенсивностей ошибок в ПО и пуассоновских процессов для моделирования процедур повышения надежности ПО. Гораздо меньшее количество моделей построено на других видах вероятностных распределений или имеет в основе нестационарные модели случайных процессов.

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

С общеинженерной точки зрения надежность программного обеспечения рассматривается как его способность сохранять свой уровень качества функционирования за определенный период времени. Большинство математических моделей трактуют надежность ПО как вероятность корректного исполнения функций, заложенных в спецификацию ПО при разных входных наборах значений и программном окружении различных пользователей. Специфика исследований в области надежности ПО заключается также в том, что оно не подвергается старению в процессе эксплуатации, а большинство ошибок ПО возникает из-за дефектов проектирования и реализации. Также активизация и проявление ошибок зависит от входных данных, и при некоторых из них ошибки могут оставаться латентными. Если некоторые программные модули в процессе эксплуатации ПО не используются либо не исполняются, то даже при наличии в них ошибок не возникает возможности их проявления. Напротив, наибольшее количество ошибок обнаруживается в процессе тестирования программ, и если ошибка успешно исправляется, то в ПО наблюдается увеличение, рост надежности. В связи с этим многие

вероятностные модели классифицируются как модели роста надежности ПО [3]. Заметим также, что существуют модели, которые строятся на изучении отказов, которые могут последовать из-за возникновения ошибок в ПО, что является актуальным для информационно-управляющих систем, так как программные ошибки могут повлечь некорректное функционирование и отказы аппаратуры.

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

Алгоритмы моделирования на основе одномерных случайных процессов

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

Пусть N ^) обозначает число ошибок (событий), проявившихся на интервале времени (0, t], и пусть ^ обозначает время проявления / -й ошибки.

Наблюдаемая последовательность времен фиксации появившихся ошибок составляет точечный случайный процесс, а ^ ^), t > 0} является соответствующим

ему считающим случайным процессом. Считающий случайный процесс является случайным процессом с непрерывным временем (N ^)) с пространством состояний Ъ + и выступает также неотрицательной и неубывающей функцией времени t. В таком виде N (/) показывает число событий, имевших место до наступления времени t. Вследствие этого время наступления событий является случайной величиной из М + в моменты, когда N ^) скачкообразно изменяет свои значения. Для ПО данные факты означают, что считающий случайный процесс N ^) имеет смысл

некоторой целочисленной случайной величины, которая равна количеству проявившихся (например, при тестировании) ошибок вплоть до момента времени t. Заметим, что хотя возможно рассматривать начальное состояние считающего процесса отличным от нуля, обычно подразумевается, что траектория процесса выходит из нуля: N(0) = 0 . Также при рассмотрении

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

считающего процесса N (t) равна единице. С другой

стороны, данное обстоятельство понимается как возможность только конечного числа событий, возникающих на некотором конечном интервале времени. Как было указано ранее, N (t) является неубывающей функцией, а переменная Ti, обозначающая время возникновения (либо проявления) i -й ошибки, есть случайная величина Ti = inf {t > 0 N (t) = i}, i > 1. Приняв, что T0 = 0, естественным образом определяются величины времени между интервалами возникновения ошибок Xi = Ti - Ti-1, i > 1. Последовательности случайных величин {Tn}n>0 и |Xn}n>0 составляют случайные процессы (не являющиеся считающими) с дискретным временем со значениями из К. + . Ясно, что для любого n > 1 вероятностное распределение Tn определяет вероятностное распределение для Xn и наоборот. Также, если нам известен процесс {Tn}n>0, можно определить N(t) как

N(t) = max{i е Ti < t}. Более того, для n > 1, k > 1

и 0 < A < ... < lk процессы {N(t))t>0 , {Tn}n>0 , (Xn)n>0 требуют для моделирования лишь одно из следующих вероятностных распределений:

- совместное распределение N (li),..., N (lk);

- совместное распределение Tl,...,Tn;

- совместное распределение Xj,...,Xn.

Считающие процессы могут также быть определены посредством функции среднего значения процесса, которую обозначим A(t), являющегося математическим ожиданием числа событий вплоть до момента времени t: A(t) = E [N (t)] .

Для класса процессов, рассматриваемых в данной работе, функция A(t) имеет смысл кумулятивной

интенсивности обнаружения ошибок, а производная этой функции по времени является мгновенной, либо просто интенсивностью X (t) = A' (t).

ПО с точки зрения надежности относится к восстанавливаемым системам, поэтому наиболее распространенной моделью является случайный пуассонов-ский процесс. Рассмотрим более детально алгоритм его моделирования. Процесс N (t), t > 0 , - однородный пуассоновский процесс с интенсивностью X > 0, если:

1) N (0) = 0 ;

2) события N (s2)- N () и N (t2)- N (t1) на

не-

перекрывающихся временных интервалах (51,52 ] и t2 ] являются независимым друг от друга, т. е.

выполняется требование независимости приращений процесса;

3) распределение числа событий на некотором интервале зависит только от длины интервала, т. е. выполняется требование стационарности приращений;

Р

4) Пт ' '—= X ;

л^о Лг

Р

5) Пт ' '-= 0.

лг^о Лг

В пуассоновском процессе число событий на интервале длины г является случайной величиной, имеющей пуассоновское вероятностное распределение. Одним из методов имитационного моделирования пуассоновского процесса служит генерация интервалов времени между возникновением ошибок X^, I = 1,2,...,п, в соответствии с методом инверсии по

формуле Х{ =—-1пиг, где и{ являются случайными

X

величинами, имеющими равномерное распределение

и (0,1). Для п временных интервалов возникновения

]

ошибок Т = 2XI, ] = 1,...,п. Число ошибок на ин-

тервале

i=1

определяется

выражением

п: 2 XI > г > — 1. Алгоритм имитационного моделирования пуассоновского процесса следующий.

Алгоритм 1. Имитационное моделирование пуас-соновского процесса на интервале (0, г).

1. 5 =0. I = 0. Ввод г.

2. Генерация случайной равномерной величины

U ~ U (0,1) .

1

3. X =--1пи .

X

4. 5 = 5 + X .

5. Если 5 > г, то конец алгоритма, п. 8.

6. I = I +1; Ti = 5.

7. Переход к п. 2.

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

Как следует из алгоритма 1, формула генерации пуассоновского процесса Т = ^Т-1 — ^^^^ ' = 1,2,...,п,

иг ~ и (0,1) .

Рассмотрим теперь случайный процесс, который является одним из основных в моделях роста надежности ПО - неоднородный пуассоновский процесс [4]. С помощью данного процесса определяются модели надежности ПО как с непрерывным временем, так и с дискретным. В моделях роста надежности ПО с непрерывным временем, например, одной из самых известных, называемой моделью Гоэла - Окумото [5], устанавливается, что в результате тестирования ПО ошибки проявляются либо в экспоненциальной, либо в форме кривой, имеющей ^-образный вид, либо имеют некоторый смешанный вид [6]. Для моделей, разработанных на основе неоднородного пуассоновского процесса, характерны следующие особенности:

- программно-управляемая система является подверженной ошибкам в результате исполнения программ и необнаруженным в них ошибкам;

- количество выявляемых ошибок в любой момент времени пропорционально количеству не выявленных ошибок;

- невыявленные ошибки в одинаковой мере влияют на интенсивность обнаруживаемых ошибок;

- любые ошибки являются независимыми друг от друга, а также от их разновидностей;

- после обнаружения ошибка устраняется немедленно, поэтому отношение числа обнаруженных и устраненных ошибок является постоянной величиной.

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

Пуассоновский процесс ^(г),г > 0} является неоднородным с функцией интенсивности Х(г), г > 0, если

1) N (0) = 0;

2) ^(г),г > 0} имеет независимые приращения;

Р

3) Ит —-—---^-= 0.

лг^0 лг

Важным следствием перечисленных свойств является то, что число ошибок на интервале (5, г], г > 5,

имеет пуассоновское распределение с параметром

(\ k

05Х(«) ии, Р (« (г )— N (5)= * )= 5 'е^1^ *.

k!

Очевидно, что в отличие от пуассоновского процесса, данный неоднородный случайный процесс не требует условия стационарности приращений, а при Х (г) = Х неоднородный пуассоновский процесс становится однородным пуассоновским процессом.

Наиболее распространенный метод имитационного моделирования неоднородного пуассоновского процесса состоит в генерации считающего процесса, который на интервалах (0, г1], (г1, г2 ] и далее 0 < гi < Т подсчитывает количество событий, сгенерированных в соответствии с пуассоновским процессом с интенсивностью X с вероятностью Х(г) / X.

Процедура в общем виде состоит из следующих этапов: 1) определяется интервал моделирования 0 < г < Т и вводятся интенсивности обнаружения ошибок X; 2) генерируются события в соответствии с однородным пуассоновским процессом с интенсивностью X; 3) считается количество событий, произошедших к моменту времени г, и сохраняется с вероятностью X(г) / X .

Алгоритм 2. Имитационное моделирование неоднородного пуассоновского процесса:

1. t = 0. п = 0. Ввод X, Т .

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

1

3. X = — ln U; X

4

5

6

7

8 9

t = t + X.

Если t > Т, то конец алгоритма, п. 9. Если X(t)/X > и , то п = п +1; Тп = t. Сохранить Тп. Перейти к п. 2. . Конец алгоритма.

В результате исполнения алгоритма 2 формируется последовательность Тх,Т2,...,Тп времен обнаружения ошибок, подчиняющихся неоднородному пуассо-новскому процессу. Для того чтобы обеспечить лучшее качество генерации, можно применить несколько модифицированный алгоритм 3 с двумя датчиками равномерного распределения случайных величин.

Алгоритм 3. Имитационное моделирование неоднородного пуассоновского процесса (2 датчика):

1. t = 0. п = 0. Ввод X, Т .

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

3. t = t - ь^.

X

4. Цикл, пока t < Т.

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

4.2. Если и2 <X(t)/X, то п = п +1; Тп = t.

4.3. Генерация их ~ и (0,1).

4.4. t = t - 1п и1.

X

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

Алгоритмы моделирования, основанные на двумерных случайных процессах

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

П/-ЛГ/ \ \

P ( N (s, u ) = n ) = -—--— ey v n = 0,1,2....

сти, например в работе [7] рассматривается модель, построенная на двух метриках: кумулятивном количестве ошибок ПО и тестовом покрытии. При этом модель надежности ПО рассматривается как двумерный стохастический процесс типа неоднородного пуассо-новского процесса вида ^(5,и),5 > 0,и > 0}, где 5 -

количество обнаруженных ошибок, а и - величина тестового покрытия:

(т (5, и)) п ~п\

где т (5, и) - математическое ожидание процесса,

т(5,и) = /^(С,§) d^

00

Дадим формальное определение двумерного однородного пуассоновского процесса. Считающий процесс {N^),t > 0} является двумерным однородным случайным пуассоновским процессом на С е М2 с интенсивностью X > 0, если:

1) число событий в области R с С имеет пуассо-новское распределение с параметром Л(R) = fXdV = XЛ(Я), где Л(Я) - это площадь об-

я

ласти Я ;

2) число событий на любом множестве неперекрывающихся областей является независимым.

Генерация двумерного однородного пуассонов-ского процесса с интенсивностью X в области, имеющей форму круга с радиусом г > 0, опирается на теорему из работы [8].

Теорема 1

Пусть (Я1,©1),(Я2,©2),...,(ЯN,©N) - полярные координаты N > 0 событий пуассоновского процесса на круге С = |(х,у): х2 + у2 <г21. Тогда для N = п упорядоченные радиусы Я(1),Я(2),...,Я(п) являются

порядковыми статистиками плотности f (z) = 2z /г2, z е[0,z]. Величины ©1,©2,...,©п - независимые, одинаково распределенные на [0,2л] случайные величины, независимые от Я1,Я2,...,Яп .

В общем виде процедура генерации включает: генерацию п событий по пуассоновскому закону распределения с параметром лг2X, далее генерацию радиусов Я(1),Я(2),...,Я(п) как порядковых статистик

из плотности f (z), а затем генерацию величин углов ©1,©2,...,©п равномерно на отрезке [0,2л].

Алгоритм 4. Имитационное моделирование двумерного однородного пуассоновского процесса на круге:

1. Ввод г, X .

2. Генерация п событий пуассоновского процесса с интенсивностью лг \ .

3. Генерация равномерно распределенных величин и1,и2,...ип ~ и (0,1).

4. Вычислить R1r^ju~1, R2r^/u7,..., Rnr^|u~n.

5. Отсортировать R1,R2,...,Rn в возрастающем порядке и получить R(1),R(2),...,R(n).

6. Генерировать п равномерно распределенных величин ип+1,ип+2,...,и2п ~ и(0,1).

7.

Вычислить

©1 = 2яии+1, © 2 = 2nUn+2,...,

© п = 2nU 2п.

8. Сформировать пары (R(1), Q1), (R(2-), Q2) ,...,1

(R( п), Qn ).

В работе [9] предлагается способ имитационного моделирования, подходящий для генерации процесса при условии, что область моделирования имеет менее регулярную форму. Рассмотрим алгоритм моделирования для области, ограниченной первым квадрантом и проходящей в нем положительнозначной функцией /(х), т. е.

С = {(х,у): х > 0,у > 0,у < /(х),х < Т}.

Алгоритм использует свойство порядковых статистик X,1^,X,1\,...,X,)* такое, что |х^ /(х)их имеет

экспоненциальное распределение со средним значением 1/ X. Соответствующие координаты Xг имеют равномерное распределение на интервале

f (--,)].

Алгоритм 5. Имитационное моделирование двумерного однородного пуассоновского процесса в области, ограниченной функцией / (х) в первом

квадранте:

1. Ввод X, Т .

2. у = 1. п = 0. ю = 0. X0 = 0.

3. Генерация равномерно распределенных случайных величин и у ~ и (0,1).

4. ю=-(1/X)ln(1 - U}).

5. ю = ю + ю .

6. Если ю < |/(х)их, тогда п = п +1, переход к п. 3.

0

7. Найти х^), I = 1,2,...,п, удовлетворяющие ус-

x

ловию | / (х) их = ю .

х

8. Генерация ип+1,ип+2,...,и2п ~ и(0,1) равномерно распределенных случайных величин.

9. у1 = ип+1/(х).

10. Формировать пары (х^,у1), I = 1,2,...,п .

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

Перейдем к более детальному рассмотрению определения имитационных алгоритмов моделирования двумерных неоднородных пуассоновских процессов. Считающий процесс ^ (г), г > 0} является двумерным неоднородным пуассоновским процессом на С е К.2 с функцией интенсивности X(х,у) > 0, если:

1) число событий в области R с С является распределенным по пуассоновскому закону с параметром

= 11н XIх, у) ихиу ;

2) число событий на любом множестве непере-кр ывающихся областей является независимым.

Процедура генерации процесса использует идею формирования координат (х, у) событий в области С

в соответствии с функцией плотности вероятности следующего вида:

f ( x, y ) =

X

J Je X( x, У ) dxdy

(x, y )e e .

Тогда, с учетом первого из вышеперечисленных свойств двумерных неоднородных пуассоновских процессов, основные этапы процедуры генерации сводятся к следующему:

1) генерация случайной величины п , распределенной по пуассоновскому закону со средним значением | |СX(х,у)ихиу;

2) генерация п случайных величин (хi, yi), I = 1,2,...,п, которые распределены в области С с плотностью

f ( x, У ) =

X

J Je X( x, y ) dxdy '

Заметим, что данная процедура существенно зависит от трудоемкости нахождения интеграла по области С .

Более эффективный и конкретизированный метод имитационного моделирования двумерного неоднородного пуассоновского процесса можно предложить, опираясь на следующую теорему [8].

Теорема 2

Пусть (хi,yi), I = 1,2,...,п, являются декартовыми координатами двумерного пуассоновского процесса с интенсивностью X* (х, у )> 0. Если

I -е событие независимо удаляется с вероятностью 1 — X(х, у) / X* (х, у), где 0 ^(х, y)<X* (х, у) х, у)е С является пуассоновским процессом на С с интенсивностью X(х, у). Требуются также два следующих свойства рассматриваемого процесса:

1) для координат (Xi ) двумерного случайного

процесса абсцисса Xi соответствует одномерному неоднородному пуассоновскому процессу с интенсив-

ностью

xx (x)=je(x)x( x у) dy, где e (x)={у : (x У) 6 e};

0

2) для координат (Xi ,Yi) двумерного случайного процесса ордината Yi имеет вероятностное распределение с плотностью X (х, y) / XX (x).

Алгоритм 6. Имитационное моделирование двумерного неоднородного случайного пуассоновского процесса.

1. i = 0 . Ввод n .

2. Генерировать xi по алгоритму 2 (алгоритму 3) для одномерного неоднородного пуассоновского процесса с интенсивностью XX (х).

3. Генерировать yi в соответствии с плотностью X( X, y) / X X ( X ).

4. Формировать последовательность {(xi,yi)}.

5. Если i < n , то i = i +1. Перейти к п. 2.

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

Эффективность данного алгоритма зависит от вида функций интенсивности X(х,y) и XX (х).

В заключение следует отметить, что представленные в работе алгоритмы достаточно просто реализуются в любой современной среде программирования. Авторами была выполнена реализация данных алгоритмов в среде Embarcadero Rad Studio XE2.

Исследование выполнено при финансовой поддержке РФФИ в рамках научных проектов 11-07-13110-офи-м-2011 -РЖД, 12-08-00798-а.

Поступила в редакцию

Литература

1. Yadav A., Khan R.A. Critical Review on Software Reliability Models // International Journal of Recent Trends in Engineering. 2009. Vol. 2, № 3. P. 114 - 116.

2. Бутакова М.А., Гуда А.Н., Чубейко С.В. Моделирование и оценка качества функционирования сетевого программного обеспечения информационно-управляющих систем на транспорте в условиях предельных нагрузок // Вест. Донского гос. техн. ун-та. 2011. Т. 11, № 6 (57). С. 875 -883.

3. HoangPham. System Software Reliability (Springer series in reliability engineering). L., 2006.

4. Lai R., Garg M. A Detailed Study of NHPP Software Reliability Models // J. of Software, Academy Publisher. 2012. Vol. 7, № 6. P. 1296 - 1306.

5. Goel A.L., Okumoto K. Time-Dependent Error Detection Rate Model for Software Reliability and other Performance Measures // IEEE Transactions on Reliability. 1979. R-28(3). P. 206 - 211.

6. Asad Ch.A., Ullah M.I., Rehman M.Y. An Approach for Software Reliability Model Selection // International Computer Software and Applications Conference (COMPSAC). 2004. P. 534 - 539.

7. Anni Princy B., Sridhar S. An Efficient Software Reliability Growth Models with Two Types of Imperfect Debugging // European J. of Scientific Research. 2012. Vol. 72, № 4. P. 490 - 503.

8. Lewis P.A. W., Shedler G.S. Simulation of nonhomogenous Poisson process with log-linear rate function. Biometrika. 1976. № 63. P. 501 - 505.

9. Ross S. Simulation. Elsevier, Burlington, M.A. 2006.

27 августа 2012 г.

Бутакова Мария Александровна - д-р техн. наук, профессор, кафедра «Информатика», Ростовский государственный университет путей сообщения. Тел. 8-918-597-66-71. E-mail: butakova@rgups.ru

Чубейко Сергей Валерьевич - аспирант, кафедра «Информатика», Ростовский государственный университет путей сообщения. Тел. 8-951-524-97-00. E-mail: greyc@mail.ru

Butakova Maria Alexandrovna - Doctor of Technical Sciences, professor, department «Informatics» Rostov State Transport University. Ph. 8-918-597-66-71. E-mail: butakova@rgups.ru

Chubeiko, Sergei Valerievich - post-graduate student, department «Informatics» Rostov State Transport University. Ph. 8-951-524-97-00. E-mail: greyc@mail.ru_