close

Вход

Забыли?

вход по аккаунту

?

Прогнозирование надежности программного обеспечения на основе модели неоднородного пуассоновского процесса и бутстреп-методов.

код для вставкиСкачать
Программные продукты и системы
№ 3, 2012 г.
Существует и другой способ определения
групп путем задания условий на метаатрибуты
непосредственно в запросе. Например, запрос
SELECT sp1.persons.name FROM sp1.persons
WHERE sp1.orgname LIKE ‘%РАН‘
выдает атрибуты name из таблицы persons; состав
группы sp1, определяющей область поиска, специфицируется в конструкции WHERE: в группу
sp1 включаются БД организаций, в названии (метаатрибут orgname) которых указана принадлежность РАН.
В общем случае метаатрибуты могут использоваться в массовых запросах наряду с обычными
данными. Однако в отличие от элементов данных
метаатрибуты соотносятся не с таблицами, а с
группами и идентифицируются в формате <имя
группы>.<имя метаатрибута>.
подстановки адресов БД, производятся оптимизирующие преобразования, специфичные для массовых запросов, и подготавливается среда выполнения запроса.
Поддержка распределенных запросов – не
единственная задача, которую необходимо решить
для обеспечения работы с масштабными информационными инфраструктурами. MQ-DAI содержит административные средства интеграции данных – описания глобальной схемы и задания правил ее отображения в схемы интегрируемых БД.
Среди других задач выделим управление инфраструктурой (включение/отключение БД и вычислительных серверов) и обеспечение безопасности
данных на основе прав доступа.
В заключение следует отметить, что в статье
изложен подход к созданию масштабных информационных инфраструктур путем виртуальной
интеграции распределенных автономных БД реляционного типа. Рассмотрен способ использования таких инфраструктур, и предложено расширение языка SQL конструкциями массовых запросов.
Реализация подхода в системе MQ-DAI опирается на комплекс OGSA-DAI, в котором наряду с
классическими методами обработки распределенных запросов применяются архитектурные принципы грида.
Поддержка языка массовых запросов реализована в виде подсистемы управления запросами
MQ-DAI. Клиентская часть этой компоненты,
оформленная в виде библиотеки классов, используется при разработке приложений и содержит
средства для определения областей поиска, формирования и дистанционного выполнения запроса,
получения результатов.
Серверная часть является надстройкой над
комплексом OGSA-DAI: получая массовый запрос, она преобразует его в форму, которая далее
интерпретируется базовым комплексом. Помимо
1. Lenzerini M. Data Integration: A Theoretical Perspective.
PODS 2002, pp. 233–246.
2. Haas L.M., Lin E.T., Roth M.A. Data integration through
database federation. IBM Systems Journal. Vol. 41. Iss. 4 (October
2002), pp. 578–596.
3. Wiederhold G. Mediators in the Architecture of Future
Information Systems. IEEE Computer. 1992. № 25 (3), pp. 38–49.
4. Kossmann D. The State of the Art in Distributed Query
Processing. ACM Computing Surveys. 2000. № 32 (4), pp. 422–
469 (http://www.db.fmi.uni-passau.de/~kossmann).
5. Бездушный А.А. Математическая модель системы интеграции данных на основе онтологий // Вестн. НГУ: Сер. Информационные технологии. Новосибирск, 2008. Т. 6. Вып. 2.
С. 15–40.
6. Tomasic A., Raschid L., Valduriez P. Scaling Access to
Heterogeneous Data Sources with DISCO. IEEE Trans. Knowl.
Data Eng. 1998. № 10 (5), pp. 808–823.
Литература
References
1. Lencerini M., PODS 2002, pp. 233–246.
2. Haas L.M., Lin E.T., Roth M.A., IBM Systems Journ.,
2002, Vol. 41, Iss. 4, pp. 578–596.
3. Wiederhold G., IEEE Computer, 1992, no. 25 (3),
pp. 38–49.
4. Kossmann D., ACM Computing Surveys, 2000, no. 32 (4),
pp. 422–46.
5. Bezdushny A.A., Vestnik NGU, Informacionnye tehnologii, Novosibirsk, 2008, Vol. 6, Iss. 2, pp. 15–40.
6. Tomasic A., Raschid L., Valduriez P., IEEE Trans. Knowl.
Data Eng., 1998, no. 10 (5), pp. 808–823.
УДК 681.142.001.4
ПРОГНОЗИРОВАНИЕ НАДЕЖНОСТИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
НА ОСНОВЕ МОДЕЛИ НЕОДНОРОДНОГО
ПУАССОНОВСКОГО ПРОЦЕССА И БУТСТРЕП-МЕТОДОВ
(Работа выполнена при поддержке РФФИ, проекты №№ 11-07-13110-офи-м-2011-РЖД, 12-08-00798-а)
А.Н. Гуда, д.т.н.; С.В. Чубейко
(Ростовский государственный университет путей сообщения, г. Ростов-на-Дону,
guda@rgups.ru, greyc@mail.ru)
Описывается новая математическая модель надежности ПО, построенная на основе математической модели неоднородного пуассоновского процесса. Основной идеей предлагаемого в статье метода прогнозирования является
130
Программные продукты и системы
№ 3, 2012 г.
метод размножения выборок данных, содержащих два исходных набора: кумулятивное время исполнения программ
и количество ошибок, зафиксированных за это время. В качестве метода размножения рандомизированных выборок
взята бутстреп-технология, использующая формирование случайных величин, имеющих распределение Пуассона.
Предложены алгоритмы нахождения оценок параметров и прогнозирования показателей надежности ПО. Первый
алгоритм служит для оценки интенсивности ошибок, ожидаемых при последующих исполнениях программ. В алгоритме используется датчик случайных чисел, на основе которого строятся рандомизированные выборки и формируются массивы случайных чисел, распределенных по пуассоновскому закону. Второй алгоритм позволяет оценивать
интенсивность обнаружения ошибок. Он использует данные выборок из первого алгоритма и действует по методу
максимального правдоподобия. В статье описывается общая процедура прогнозирования ожидаемого количества
ошибок, которые могут проявиться при последующем исполнении программ на некотором интервале времени, следующем за кумулятивным интервалом наблюдения. Предложенный метод прогнозирования был реализован в виде
программы, написанной на языке программирования Паскаль в свободной среде программирования PascalABC.NET.
Кроме того, описаны примеры использования программы прогнозирования при некоторых тестовых данных.
Ключевые слова: надежность ПО, неоднородный пуассоновский процесс, бутстреп-технология.
SOFTWARE RELIABILITY ANALYSIS BASED ON THE MODEL
OF INHOMOGENEOUS POISSON PROCESS AND BOOTSTRAP METHODS
Guda A.N., Ph.D.; Chubeyko S.V. (Rostov State Transport University, guda@rgups.ru, greyc@mail.ru)
Abstract. A new mathematical model of software reliability is described, based on mathematical model of inhomogeneous Poisson process. The basic idea of the proposed in the article forecasting method is a method of reproduction of data
samplings, containing two original sets: the cumulative program execution time and number of errors committed during this
time. As a method of a randomized sampling reproduction a bootstrap technology is taking which uses random quantities,
having a Poisson distribution. Algorithms of parameter estimate and forecasting indicators of software reliability are suggested. The first algorithm is used to assess the intensity of errors expected in subsequent versions of the software. The algorithm
uses a random number sensor on which basis randomized sampling and random arrays are arranged under Poisson law. The
second algorithm makes it possible to evaluate the intensity of error detection. He uses data samples from the first algorithm
and operates according to the method of maximum likelihood. The article describes the general procedure for forecasting the
expected number of errors that can occur during a subsequent program run at a certain time interval, following a cumulative
period of observation. The proposed forecasting method was realized in the form of a program written in Pascal programming language in the free programming environment PascalABC.NET. It also describes examples of using forecasting software with some test data.
Keywords: reliability of the software, the non-homogenous Poisson process, bootstrap-technology.
За последнее десятилетие в области разработки
ПО произошли коренные изменения. Средства
разработки ПО позволяют автоматически генерировать исходный текст, использовать шаблоны
проектирования программ, повторно использовать
компоненты, объекты, выполнять рефакторинг, а
также имеют другие возможности, ускоряющие
проектирование ПО. В то же время все эти широкие возможности не только увеличивают количество программных подсистем в разрабатываемом
проекте, но и усложняют взаимосвязи между ними, неизбежно усложняя процесс поиска ошибок в
проекте и снижая его надежность. В связи с этим
основным инструментарием обеспечения надежности программного проекта являются методы
тестирования на разных стадиях жизненного цикла программ (особенно на завершающей) с целью
обнаружения ошибок при некорректно предоставляемых данных и построение упрощенных формальных спецификаций сложного «большого»
проекта, отражающих его основные свойства и
требования на том или ином формально-логическом языке для логического обоснования корректности исходного программного проекта. Однако
существует математическая теория надежности
ПО, строящаяся подобно математической теории
систем. Значительным плюсом такого подхода к
надежности ПО является не только возможность
констатации фактов вида «в ПО есть ошибки либо
с такой-то вероятностью нет ошибок», но и более
широкая постановка вопроса: как на основании
имеющихся и измеряемых в процессе работы ПО
показателей, не имея доступа к исходному тексту
программ, математически обоснованно рассчитать
вероятность появления или количество ошибок
через какое-либо время работы программы в будущем. Одному из таких способов посвящена
данная работа.
Математическая модель
Предлагаемая авторами модель будет опираться на математическую модель из работы [1], в основе которой лежит неоднородный пуассоновский
процесс {N(t), t0}, характеризующийся следующими допущениями. Во-первых, программы запускаются в неперекрывающиеся интервалы времени [(0, t1), (t1, t2), …, (ti–1, ti), …, (tm–1, tm)].
Во-вторых, количество ошибок (f1, f2, …, fm) на
каждом интервале не зависит от других интервалов, а каждая ошибка устраняется сразу после ее
выявления. В-третьих, кумулятивное количество
ошибок, обнаруженных на момент времени t, имеет пуассоновское распределение со средним m(t).
И наконец, каждая ошибка может быть обнаружена с одинаковой вероятностью, приводит к одинаковым негативным последствиям, интервалы обнаружения ошибок имеют одинаковую размерность (сутки, неделя, месяц и т.п.).
131
Программные продукты и системы
№ 3, 2012 г.
Функция m(t) является неубывающей и ограниченной сверху, то есть
m(t)=0 при t=0, m(t)=a при t,
(1)
где a – количество ошибок в ПО, которое в принципе в нем содержится и может быть обнаружено.
Если принять, что количество ошибок в ПО,
обнаруженных на интервале времени t, пропорционально количеству ошибок, имеющихся в ПО,
но пока не обнаруженных, то с учетом (1) имеем:
m  t  t   m  t   b a  m t  t  o  t  .
(2)
Из выражения (2) при t0 получаем дифференциальное уравнение
(3)
m  t   ab  bm  t  ,
решая которое с условиями (1), находим среднее
количество ошибок
m(t )  a 1  ebt .
(4)


Интенсивность ошибок из выражений (3) и (4)
получаем как
(5)
  t   m  t   abebt .
Процесс моделирования ошибок с функцией
интенсивности (t) выполняется в соответствии со
стохастическим процессом:
– если не возникают ошибки за время t, то
P N  t , t   N  t   0  1   t  t  o  t  ; (6)
– если за время t возникает одна ошибка,
P N  t , t   N t   1    t  t  o  t  ;
(7)
– если за время t возникают две (и более)
ошибки,
P{N(t, t)–N(t)=2}=o(t).
(8)
Таким образом, возникновение fi ошибок на
интервале времени (0, ti) будет
P  N  ti   f i  
m  ti  i e
f
 m  ti 
,
(9)
fi !
где i – некий интервал времени, в процессе которого программа загружена и исполняется; fi – число ошибок, возникших за период времени i; ti –
кумулятивное время исполнения программы,
включая интервал i, то есть совокупность всех
времен исполнения программы; m(ti) – функция
средней интенсивности ошибок для времени,
t
m  ti   E  N  ti      s  ds , где (s) – функция
0
интенсивности.
Для дальнейших численных расчетов среднюю
интенсивность ошибок можно приравнять к среднему количеству ошибок i, обнаруживаемых на
i-м интервале, и тогда выражение (9) будет представлять собой известную модель Гоэла–Окумото
 fi ei
P  N  ti   f i   i
(см. [1]):
.
fi !
Учитывая, что в данном случае рассматривается неоднородный пуассоновский процесс, а, сле132
довательно, для каждого ti-го интервала времени
функция интенсивности может изменяться, продолжим рассуждения следующим образом. Параметр i определяется по выражению (4) как
i    1  eti  1  eti1  
(10)
  eti1  eti ,

 



где  – интенсивность устранения ошибок.
Задача моделирования состоит в определении
параметров интенсивности обнаружения и устранения ошибок ( и  соответственно) в ПО в выражении (8), причем для каждого ti-го интервала
времени.
Очевидно, что в данном случае при наличии
выборки данных, содержащей кумулятивное количество обнаруженных ошибок к некоторому
ti-му интервалу времени, для определения параметров  и  подходящим оказывается метод максимального правдоподобия [2].
Функция правдоподобия имеет вид
I
 fi
L  ,  выборка    el i ,
(11)
fi !
i 1
где I – общее число временных интервалов наблюдения ошибок.
Прологарифмируем выражение (11):
L  ,  выборка   ln L  ,  выборка  
I
I
(12)
 
  i   fi ln  i .
i 1
i 1
 fi ! 
Подставив вместо i в выражении (12) функцию из выражения (10), получаем
L  ,  выборка  
I




I
   eti1  e ti   f i ln  
i 1
I
(13)
i 1
I
  fi  e ti1  e ti  f i ln  f i !.
i 1
i 1
Чтобы найти максимум для данной функции,
возьмем частную производную по переменной :
I
i
f
dL
  eti1  eti   i .
(14)
d
i 1
i 1 
Просуммировав выражение (14), получаем
dL
f 
 1  etI     ,
d

где f+ – кумулятивное число ошибок для всех i-х
периодов времени.
Приравнивая к нулю производную (14), получаем выражение для оценки интенсивности обнаружения ошибок
f
.
(15)
ˆ 
1  etI






Подставив ̂ из выражения (15) в выражение
(13), взяв производную по переменной  и приравняв ее к нулю, получаем
Программные продукты и системы


№ 3, 2012 г.

 f  eti1  eti




f

i

1  etI
i 1 

 t eti1  ti eti 
(16)
  i 1ti1
  0.
 eti 
 e
Рассмотрим нахождение начального значения
. Пусть
(17)
x  eti ;
ti 1
ti
I
 t e
 ti e 
1
(18)
s
fi  i 1ti1
.

f  ti i 1  e
 eti 
Из выражений (16)–(18) видно, что s и x связаны соотношениями s=[x/(1–x)], x=[s/(1+s)]. Начальное значение x0 можно отыскать по формуле
x  ft1 / ft2 ,
(19)
I

то есть разделив количество ошибок, полученных
за первую половину времени исполнения программы, на количество ошибок, полученных за
вторую половину времени исполнения программы. Далее подставляем полученное значение x в
формулу (17) и получаем начальное значение ,
для уточнения которого используется итеративный процесс
n 1  ˆ   ti e  t  ti 1e  t
I
n i
i 1
n i 1
  t  .
i
(20)
Алгоритмы нахождения оценок параметров
и прогнозирования показателей
надежности ПО
Для оценки  применим метод размножения
выборок, известный как метод бутстреппинга [3].
Исходной информацией является выборка наблюдаемых значений (массив данных), в данном случае содержащая три показателя (см. табл.).
День
1
2
3
Время исполнения, ч Количество ошибок
6
4
32
5
54
5
Таким образом, при методе бутстреппинга,
имея некоторую выборку конечной размерности n,
то есть эмпирическое распределение, и используя
датчики случайных чисел, из нее можно сформировать любое количество размноженных выборок.
Здесь вероятностное распределение в формируемых выборках должно подчиняться пуассоновскому распределению. Рассмотрим алгоритм формирования случайных чисел, распределенных по
закону Пуассона.
Алгоритм 1. Формирование бутстреп-выборок.
Входные параметры: массив наблюдаемых
значений M={m1, m2, …, mi, mn} количества ошибок за время исполнения программы; t=0 – текущее время; T – общее время моделирования; I=0 –
количество событий за время моделирования T; 
– интенсивность ошибок; j – текущий элемент
массива; n – размерность выборки.
1. Пока jn.
2. Генерация случайного числа с равномерным
распределением UU(0, 1) на отрезке (0, 1).
1
3. t  t  ln U .

4. Если t>T, то завершить моделирование и выдать результаты.
5. Генерация случайного числа с равномерным
распределением UU(0, 1) на отрезке (0, 1).
6. Если U    t  / , I  I  1, S j  I   t.
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. Нахождение оценки .
Входные параметры: начальное значение x0
(формула (19)); TF – общее кумулятивное количество ошибок за все время исполнения программы;
массив времени исполнения программы T – второй столбец из таблицы; массив сформированных
размноженных выборок M из алгоритма 1; n –
размерность массивов T и M; eps – точность; time
– общее время исполнения программ.
1. Mu : (((1)  ln x0 )) / time) .
2. Повторять
2.1. MuNew : Mu ;
2.2. Цикл от 1 до n (расчеты по формуле (20)):
2.2.1. t1  T [i]e1MuT [i ] ,
2.2.2. t2  T [i  1]e1MuT [i 1] ,
2.2.3. t3  e1MuT [i 1]  e1MuT [i ] ,


2.2.4. t4  t4  M [i]    t1  t2  / t3  ,
2.2.5. Конец цикла по n;
2.3. Если t4<0,01, тогда t4=0,01;
2.4. s   t4 / TF  time  ;
2.5. x   s / 1  s   ;
2.6. t4=0;
2.7. MuNew  (((1)  ln  x  / time;
2.8. Конец цикла. Повторять, пока
MuNew–Mueps.
3. Результат. Вывод Mu.
4. Конец алгоритма.
Опишем общую процедуру прогнозирования
ожидаемого количества ошибок, которые могут
проявиться при дальнейшем исполнении программ на интервале времени , следующем за
кумулятивным интервалом наблюдения tI. В соответствии с рассматриваемым неоднородным пуас133
Программные продукты и системы
№ 3, 2012 г.
соновским процессом среднее ожидаемое количество ошибок
m  , tI , ,    E  N  t I     N (t I )  
(21)
 etI  1  e  .
Оценка параметров по предложенным алгоритмам 1 и 2 позволяет записать выражение (21) с
использованием оцененных параметров ̂ и ̂ :


m  , tI , ,    m , t I , ˆ , ˆ 
ˆ
 ˆ eˆ tI  1  e
.
Шаги процедуры следующие.


ˆ  b   m , tI , ˆ  b  , ˆ  b  ,
1. Получить оценки m
ределенные временные интервалы (например, через 5 дней были обнаружены и исправлены 3
ошибки в ПО).
При запуске программы с данным тестовым
файлом можно увидеть результаты, например,
прогноза проявления ошибок в ПО с 95 %-ным
доверительным интервалом на будущие 10 дней.
При необходимости доверительный интервал
можно изменить.
Подводя итоги, отметим, что в статье предложен метод прогнозирования надежности ПО путем модификации модели, построенной на неоднородном пуассоновском процессе, в котором
впервые применен способ размножения выборок,
известный как бутстреп-метод. Предложены алгоритмы, позволившие реализовать программу для
прогнозирования надежности ПО.
где b=1, 2, …, B, размноженные методом бутстреппинга-выборки (всего B оценок средней интенсивности ошибок).
2. Отсортировать по возрастанию полученные
ˆ i (b) .
оценки средней интенсивности ошибок m
3. Определить требуемые доверительные интервалы (обычно нижнее значение =0,05, а верхнее значение =0,95) и отсечь не входящие в эти
интервалы оценки.
4. Используя оценку среднего значения и известные свойства функции распределения Пуассона, можно ожидать, что на интервале времени tI,
tI+ количество ошибок будет не более
k
K e  mˆ i  m
 ˆi 
.

k!
k 0
Литература
Реализация ПО
1. Hoang Pham. System Software Reliability. SpringerVerlag Limited. London, 2006, pp. 440.
2. Магнус Я.Р., Катышев П.К., Пересецкий А.А. Эконометрика. Начальный курс. М.: Дело, 2007. 504 с.
3. Эфрон Б. Нетрадиционные методы многомерного статистического анализа: сб. статей; [пер. с англ.; предисл. Ю.П.
Адлера, Ю.А. Кошевника]. М.: Финансы и статистика, 1988.
263 с.
4. URL: http://pascalabc.net (дата обращения: 20.06.2012).
Предложенный в статье метод прогнозирования был реализован в виде программы, написанной на языке Паскаль в свободной среде программирования PascalABC.NET [4]. Программа включает следующие функции: FirstValue – определение начального значения x0 (по выражению (19));
FindMu – определение оценки  (по алгоритму 2);
GenerateLambdas – определение оценки  по методу размножения выборок (алгоритм 1); AssignPoissons – нахождение случайных чисел по распределению Пуассона (элемент алгоритма 1).
Исходные данные читаются из файла, имеющего табличную структуру (см. рис.).
Первый столбец содержит кумулятивное время
исполнения программы (например в днях), а второй – количество ошибок, зафиксированных в оп-
References
1. Hoang Pham., System Software Reliability. SpringerVerlag Limited, London, 2006, pp. 440.
2. Magnus J.R., Katyshev P.K., Peresetskiy A.A., Ekonometrika. Nachalny kurs (Econometriks. Initial Course), Moscow, Delo,
2007, 504 p.
3. Efron B., Netradicionnye metody mnogomernogo statisticheskogo analiza, sb. statey (Nontraditional methods of multivariate statistical analysis. Collected works), Moscow, Finansy i statistika, 1988, 263 p.
4. Programming environment PascalABC.NET, available at:
www.pascalabc.net (accessed 20.06.2012).

Вниманию авторов!
Пристатейный список литературы (не менее 3 пунктов)
необходимо транслитерировать в соответствии с ГОСТ 7.79-2000 (ИСО 9-95).
Новые редакционные требования на сайте журнала www.swsys.ru.
134
1/--страниц
Пожаловаться на содержимое документа