Модель Нельсона. 
Надежность и безопасность программного обеспечения

Общее описание модели.

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

Для описания данной модели прежде всего введем следующие обозначения. Совокупность действий, включающая ввод ?, выполнение программы П, которое заканчивается получением результата ?'(?,) называется прогоном программы П. Необходимо также отметить, что значения входных переменных, образующие ?,-, не должны все одновременно подаваться на вход программ П. Таким образом, вероятность Р того, что прогон программы приведет к обнаружению дефекта, равна вероятности того, что набор данных ?, используемый в данном прогоне, принадлежит множеству ?_е. Если обозначить через п_е число различных наборов значений входных данных, содержащихся в ?_е, то Р = n_e/N есть вероятность того, что прогон программы на наборе входных данных ?, случайно выбранном из? среди равновероятных, закончится обнаружением дефекта. При этом R = 1 — Р есть вероятность того, что прогон программы П на наборе входных данных ?_г, случайно выбранном из? среди априорно равновероятных, приведет к получению приемлемого результата.

Однако в процесс функционирования программы выбор входных данных из? обычно осуществляется не с одинаковыми априорными вероятностями: он диктуется определенными условиями работы. Последние характеризуются некоторым распределением вероятностей Pi того, что будет выбран набор входных данных ?,. Распределение Р может быть определено через р, с помощью величины у_{. При этом У; = 0, если прогон программы на наборе ?, заканчивается вычислением приемлемого значения функции, и у, = 1, если этот прогон заканчивается обнаружением дефекта. Поэтому.

есть вероятность того, что прогон программы на наборе входных данных? j, выбранных случайно с распределением вероятностей р_;, закончится обнаружением дефекта. При этом.

есть вероятность того, что прогон программы П на наборе входных данных ?" выбранных случайно с распределением вероятностей р" приведет к получению приемлемого результата.

Так как R — вероятность того, что единичный прогон программы не закончится отказом на наборе входных данных, выбранных в соответствии с распределением р_1У то вероятность успешного выполнения п прогонов этой программы при независимом для каждого прогона выборе входных данных в соответствии с распределением Р представима как.

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

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

С учетом введенного определения функциональный разрез^[1] должен быть переопределен в терминах вероятностей р_;1 выбора E_t в качестве входных данных при ;-м прогоне из некоторой последовательности прогонов. Тогда вероятность того, что j-й прогон закончится проявлением ошибки в программе, может быть записана в виде.

Надежность R (n) программы П равна вероятности того, что в последовательности из п прогонов ни один из них не закончится проявлением программной ошибки:

Формула (4.6) может быть представлена в виде.

Некоторые из свойств функции R (n), представленной выражением (4.7), могут стать более наглядными при следующих допущениях:

ДЛЯ Pj « 1.

если Pj = Р для всех j, то С помощью соответствующих замен переменных и подстановок можно выразить функцию R (n) через время функционирования t. Для этого введем следующее обозначение: tj — суммарное время выполнения первых) прогонов программы;

где — время выполнения г'-го прогона.

Далее определяется функция интенсивности ошибок:

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

Формула (4.8) хорошо известна в теории надежности технических устройств. В случае _Pj «1 функция /i (t-) может быть интерпретирована как функция интенсивности ошибок, которая, будучи умноженной на Atj, дает условную вероятность появления программной ошибки в интервале (tj, tj + Atj) при отсутствии такого рода ошибок до момента t,.

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

Если выборка включает п наборов входных данных из Е и осуществляется в соответствии с распределением вероятностей р" то расчетное значение R' будет представлять собой несмещенную оценку надежности R в том смысле, что для р_; «1 ожидаемое значение на всем множестве наборов входных данных в пределах выборки равно R. Это может быть показано, если ввести характеристику выборки Zy, которая определяется так, что Zy = 1, если E_i входит в выборку j, и Zy = 0 в противном случае.

Число различных наборов входных данных п_;, входящих в некоторую выборку j, может быть меньше, чем п, так как некоторые наборы Ej могут быть включены в нее более одного раза. Поэтому.

Однако в большинстве случаев число возможных наборов входных данных N настолько больше размера выборки, что повторный выбор каких-либо наборов маловероятен. Если s — вероятность того, что взята выборка; и М — количество возможных выборок, то.

Так как R' можно представить в виде то математическое ожидание R' имеет вид

При р « 1.

Для получения оценки R должен быть определен функциональный разрез р, программы. На практике этот разрез определяется путем разбиения всего пространства значений входных переменных на подпространства и нахождения вероятностей того, что выбранный набор входных данных будет принадлежать конкретному подпространству. Определение этих вероятностей основано на оценке вероятностей появления тех или иных входов в реальных условиях функционирования, относительно которых оценивается надежность программы.

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

• [1] Под функциональным разрезом понимаются входные данные для испытуемой программы, которые формируются программными средствами испытателя и отражаютреальные условия функционирования программы [10].