Алгоритм a

А₁. i:=1.

А₂. Вычислить значенияb_j,j=1,...,Nполиномаf(x)ⁱпутем перемноженияf(x)ⁱиf(x)^i-1: еслиf(x)=иf(x)^i-1=, тоb_j=.

А₃. Вычислитьm_i(h)=.

А₄. i:=i+1.

А₅. Еслиir/N, то переход на п.А₂. В противном случае алгоритм завершается.

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

Задача вычисления закона распределения F(y) в заданной точке y₀поLмоментам формулируется следующим образом.

Дано:m_i,i=1,...,L- начальные моментыF(y).

Необходимо:определить значения supF(y₀) и infF(y₀).

Метод вычисления sup F(y₀) и infF(y₀) по известным начальным моментамF(y) описан в [Че]. Алгоритм вычисления supF(y₀) и infF(y₀) дляL=2k-1,k=1,2..., и известныхаиb– конечных значений y, меньше и больше которых соответственно значения функции принимать не могут, реализуют данный метод с некоторыми модификациями.

Алгоритм б

Б₁. Сформировать ряд «подходящих» дробей к интегралу

Б₂. Преобразовать «подходящую дробь» в непрерывную вида

.

Б₃. Привести непрерывную дробь к дробно рациональному виду_L(z)/_L(z).

Б₄. Выполнить пункты Б₂и Б₃дляL=L-1 и вычислить_L-1(z)/_L-1(z).

Б₅. Определить функцию.

Б₆.Определить вещественные корни полинома₁(z).

Б₇. Вычисление интеграла с помощью вычетов. При этом infF(y₀) будет равно сумме вычетов₀(z)/₁(z) для всехy,y₀, а supF(y₀), будет равно сумме infF(y₀) и очередного вычета. Среднее значениеF_ср(y₀)=(supF(y₀)+infF(y₀))/2 и значение=(supF(y₀)+infF(y₀))/2, определяющее точность восстановления функции распределения, зависят отm_i,i=1,...,Lиy₀. Однако1/L+1.

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

4. Обоснование критериев принятия решения о наличии в программе рпс

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

Дано:

• множество G_iвероятностных характеристик случайных величин, снимаемых с заданного множества контрольных точек;

• эталонные значения этих ВХ G_i^*и их значения, полученные в результатеnиспытаний (прогонов) программы.

Необходимо:определить множествоL_iтаких, что если существуетi(G_i-G_i^*>L_i), то делается вывод о наличии в исследуемой программе РПС с вероятностьюР₀.

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

Дано:Р=F(y₀);q=1-P=P(y>y₀); задано число прогонов программыnи значения доверительной вероятностиР₀.

Необходимо:определить значение доверительного интервалаLчастоты появления события {A-y_j<y₀}, гдеy_j-j-е значение выходной величины.

Для независимых испытаний частота появления события А-y_i<y₀является случайной величиной, распределенной по биномиальному закону с математическим ожиданиемРи дисперсиейD=Pq/n. Вероятность появленияkсобытий приnиспытаниях в этом случае рассчитывается по формулеPk=C_n^kP^kq^n-k.

В качестве доверительного интервала [P₁^*,Р₂^*] целесообразно выбирать наименьший интервал, вероятность попадания за границы которого больше (1-Р)/2. Границы доверительных интервалов для различных значенийР,Р₀иnсведены в таблицы [Ве], что существенно облегчает задачу инженерного анализа результатов тестирования при контроле технологической безопасности программного обеспечения. С увеличениемnбиномиальное распределение будет стремиться к нормальному с теми же математическим ожиданием и дисперсией. При этом для вероятностного тестирования необходимо выбрать такие значенияy₀, чтобыР0,5, что позволяет заменять биномиальное распределение нормальным с максимальной точностью. Доверительный интервал в этом случае определяется по формуламP(P-P^*<L_экс)=P₀,L_экс=arg Z^*((1+P₀)/2), где argZ^*- функция, обратная нормальной функции распределенияZ^*, полученная по таблицам.

С учетом того, что значение F(y₀) вычисляется с точностью, доверительный интервалL=L_экс+, то есть если при проведении испытаний значений Р^*будет отличаться от аналогично рассчитанного на величину, большую, чемL_экс+, то принимается решение о наличии в исследуемой программе РПС с вероятностью Р₀.

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

Так как y_jпредставляет собой случайные величины с одинаковым законом распределения, то законы распределения и их суммы стремятся к нормальному с математическим ожиданиемm₁(y) и дисперсиейD(y)/n.

В этом случае доверительный интервал определяется по формуле L_экс=argZ^*((1+P₀)/2), .

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

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

2. Ограниченность числа испытаний (прогонов) программы.При известных значениях доверительного интервала с помощью методов статистики можно определить необходимое число испытаний, обеспечивающее достоверность результата не меньше Р₀.

3. Закон распределения входных случайных величин. Для заданного закона распределения аргументаw(x) функцииf₁(x) иf₂(x) будут неразличимы, если для каждой точкиy

F(y)=w(x) dx=w(x) dx

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

w(x) dx-w(x) dx,

где _i- интервалы аргумента, гдеf₁(x)<y;

_j- интервалы аргумента, гдеf₂(x)<y.

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