4.4.3. Методы оценки показателей надежности по, основанные на моделях «посева» и разметки ошибок и на моделях структуры входных данных.

Методы, основанные на моделях «посева» и разметки ошибок, рассмотрим на примере трех моделей (Миллса, Бейзина и простой эвристической модели). Методы, основанные на моделях структуры входных данных, базируются на модели Нельсона, которая практическое применение получила на база последовательного статистического анализа Вальда.

МОДЕЛИ «ПОСЕВА» И РАЗМЕТКИ ОШИБОК

Программу по методике Миллса сначала «засевают» (засоряют) известным числом M определенных ошибок. Основное допущение, положенное в основу модели, состоит в том, что считают распределение внесенных ошибок таким же, как и собственных, и, следовательно, вероятность обнаружения как собственных ошибок так и внесенных одинакова. Затем программу начинают тестировать. Пусть при тестировании обнаружено (m+v) ошибок, причем m – это часть засеянных ошибок, а v – собственных. Тогда, в соответствии с методом максимального правдоподобия, оценкой для числа оставшихся в ПО ошибок (первоначального числа ошибок) будет величина .

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

МОДЕЛЬ БЕЙЗИНА. Пусть ПО содержит команд. Случайным образом из этого числа выбираются n команд, в которые вводятся ошибки. Затем для тестирования случайным образом выбирают r команд. Если в ходе тестирования будет обнаружено v собственных и m посеянных ошибок, то оценка максимального правдоподобия полного числа ошибок, содержащихся в программе перед началом тестирования, может быть определена как:

где ]…[ - -целая часть числа в этих скобках.

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

ПРОСТАЯ ЭВРИСТИЧЕСКАЯ МОДЕЛЬ. Эта модель предложена Б.Руднером. В ней исключается основной недостаток, характерный для модели Миллса. Здесь тестирование осуществляется параллельно двумя независимыми группами программистов.

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

4.4.4. Методы оценки, основанные на моделях структуры входных данных

МОДЕЛЬ НЕЛЬСОНА.

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

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

С учетом оценка вероятности отказа может быть выражена следующей зависимостью:

Что позволяет, для оценки вероятности успешного прогона записать

Тогда вероятность успешного выполнения m прогонов при независимом для каждого прогона выборе входных данных в соответствии с функциональным разрезом будет равна

Эта модель позволяет дать определение надежности ПО. Надежность ПО – это вероятность безотказного выполнения m прогонов программы.

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

Учитывая эти обстоятельства, функциональный разрез следует переопределить в терминах вероятностей при выборе набора входных данных для прогона j из некоторой последовательности прогонов. Тогда вероятность того, что j– прогон закончиться отказом есть

Соответственно для вероятности безотказного выполнения m прогонов получим следующее выражение:

Это выражение можно также представить в другом виде

,

если Q то

Обозначим через время выполнения j-го прогона программы, а через - суммарное время выполнения j прогонов и примем для функции риска

тогда

Если величина будет устремлена к нулю с ростом m, то сумма в показателе экспоненты переходит в интеграл:

основного закона надежности.

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

На практике функциональный разрез определяется путем разбиения всего пространства значений входных переменных на подпространства и определения вероятностей того, что выбранный набор входных данных будет принадлежать конкретному подпространству. Определение этих вероятностей основано на оценке вероятностей появления тех или иных в реальных условиях функционирования ПО. После того как вероятности найдены, случайная выборка из m наборов входных данных, распределенных в соответствии с , реализуется с помощью синтезированного датчика случайных чисел. Следует отметить также, что процесс испытаний должен быть непрерывным и ошибки не должны исправляться до завершения всех m прогонов. Что касается второй трудности, то возможности ее смягчения изложены ниже. Здесь на помощь приходит применение давно известного в статистике метода последовательного анализа, предложенного Вальдом [29]. Изложим кратко суть этой теории применительно к надежности ПО [30]. В последовательном анализе вводится допущение о том, что если вероятность успешного прогона P находится в достаточно малой окрестности точки , то риск принятия неправильного решения допустимо мал. При этом под неправильным решением понимается решение отвергнуть надежную программу или решение принять ненадежную программу. Программист, тестирующий ПО, должен до начала испытания задать следующие величины:

1) минимальную приемлемую вероятность безотказной работы ПО ;

2) вероятность , при которой он почти уверен, что ПО пройдет испытания и, таким образом, ;

3) вероятность, а ошибки первого рода, т.е. вероятность отказа от надежной программы ( );

4) вероятность ошибки второго рода, т .е. вероятность принять ненадежную программу ( ).

Величины а и должны при этом назначаться исходя из разумного компромисса, так как с их уменьшением растет число испытаний.

Суть последовательного анализа гипотезы (надежность ПО ) состоит в проверке двух конкурирующих гипотез и . При этом под вероятность безотказной работы ПО понимается по- прежнему вероятность безотказного выполнения m прогонов.

Введем дихотомическую переменную :

Тогда по результатам m прогонов будем иметь выборку состоящую из нулей и единиц. Вероятность безотказного выполнения m прогонов может быть представлена вероятностью получения выборки , в которой элементов равны нулю:

.

Если верна гипотеза , то вероятность получения такой выборки будем

.

Аналогично, если верна гипотеза , то

Составим отношение правдоподобия

Последовательный анализ (т.е. продолжение тестирования) ведется до тех пор, пока не будут выполняться неравенства

.

Если на m-м прогоне окажется, что

то ПО можно считать ненадежным.

Если же окажется, что на m-м прогоне

то ПО можно принять как надежное.

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

In In In + In ;

=(In + In )/

(In -In )/

( In Ina)/

в координатах m, можно построить две прямые .

Теперь для числа неудовлетворительных испытаний (т.е. испытаний, завершившихся отказами) имеем соотношения .Если то ПО ненадежно, а если то ПО можно принять как надежное.

Таким образом, практически необходимо сделать следующее:

Если текущая точка попадает на графике выше линии , то испытания заканчиваются и ПО признается ненадежным (не удовлетворяющим заданным задать перед началом испытаний величины ;

построить на миллиметровой бумаге прямые и ;

нанести по ходу испытаний на построенный график точки .

требованиях по надежности).

Если текущая точка попадает на графике ниже линии то испытания завершаются и ПО признается надежным.

Если текущая точка попадает внутрь области, ограниченной прямыми и , то испытания продолжаются.

Можно оценить среднее число испытаний при истинности гипотезы и среднее число испытаний (прогонов программы) при истинности .

В первом случае имеем зависимость

[ In B+ In A]/ ,

где ; - математическое ожидание случайной величины In In при истинности гипотезы .

Можно показать , что In .

Во втором случае получаем

[aInA+(1-a)In B]/ ,

где - математическое ожидание при истинности гипотезы .

В этом случае =In .

Рассмотрим примеры по оценке среднего числа испытаний. Пусть , ; ; .Тогда:

; In ;

In

In ; In ;

Если поменять между собой значения для и , а и оставить без изменений, то получим следующий результат: ;

МОДЕЛЬ РОСТА НАДЕЖНОСТИ ЛАПАДУЛЫ

Суть предложений Л. Лападулы состоит в построении методом наименьших квадратов кривой надежности, учитывая результаты наблюдаемых чисел отказов на различных стадиях тестирования. Тестирование здесь ведется серией из N этапов. Каждый этап отмечен каким- либо изменением или модификация программы.

На каждом выполняется тестов, из которых закончилась успешно. Число тестов на данном этапе заранее не фиксируется.

По завершении N- го этапа (который сам по себе заранее неизвестен) данные подставляются в уравнение кривой роста

где - надежность ПО во время i-го этапа тестирования; P(u)- значение величины при i→∞; A- параметр роста.

Если A>0, то надежность ПО возрастает, если же A< 0 – снижается. Для оценки неизвестных и A воспользуемся методом наименьших квадратов. Будем минимизировать следующую навязку:

Взяв частные производные от s по и по A и приравняв их нулю, получим систему уравнений для нахождения оценок. Решив эту систему, найдем МНК:

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