Теория и практика защиты программ


Алгоритмы приближенных вычислений вероятностных характеристик наличия в программах РПС - часть 2


В этом случае если f(x)=
 (общий вид), то определение первых t=r/N моментов случайных величин h=f(k) выполняется по следующему алгоритму (r – число первых начальных моментов закона распределения w(x), принимающих значения m1(e),...,mr(e)).

 

Алгоритм A

А1. i:=1.

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

 и f(x)i-1=
, то bj=
.

А3. Вычислить mi(h)=

.

А4. i:=i+1.

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

 

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

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

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

Необходимо: определить значения sup F(y0) и inf F(y0).

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

 

 

Алгоритм Б

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

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

.

Б3. Привести непрерывную дробь к дробно рациональному виду jL(z)/yL(z).

Б4. Выполнить пункты Б2 и Б3 для L=L-1 и вычислить

jL-1(z)/yL-1(z).

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

.

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

Б7. Вычисление интеграла

 с помощью вычетов. При этом inf F(y0) будет равно сумме вычетов f0(z)/f1(z) для всех y,y0, а sup F(y0), будет равно сумме inf F(y0) и очередного вычета.Среднее значение Fср(y0)=(sup F(y0)+inf F(y0))/2 и значение d=(sup F(y0)+inf F(y0))/2, определяющее точность восстановления функции распределения, зависят от mi, i=1,...,L и y0. Однако d£1/L+1.

 

Таким образом, с помощью алгоритмов А

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




- Начало -  - Назад -  - Вперед -