Безопасность программного обеспечения компьютерных систем


Методы создания самотестирующихся


Так как вероятность ошибки ? 1/8, то в одном цикле вероят-ность Prob[Rk=fM,g(x)] 3/4. Чтобы вероятность корректного ответа была не менее чем 1- ?, исходя из оценки Чернова , необходимо выполнить не менее 12ln(1/? ) циклов

Лемма 2.2. Программа S_T_exp(n,M,q,g,?) является (1/288,1/8)-самотестирующейся программой, которая контролирует результат вычисления значения функции gxmoduloM с любым модулем M.

Доказательство. Полнота теста линейной состоятельности доказыва-ется аналогично доказательству полноты в лемме й, где x1,x2 RZq. Полнота теста единичной состоятельности вытекает исходя из следующего очевид-ного факта. Корректное выполнение теста [PM,g(x1)'PM.g(1)](mod M) соответствует вычислению функции:

Для доказательства условия самотестируемости необходимо отметить, что так как и в лемме 1 для того, чтобы вероятность корректных ответов Rl и Re в обоих тестах была не более 1-? достаточно выполнить тест линейной состоятельности 576ln(4/?) раз и тест единичной состоятельности 32ln(4/?) раз.

Можно показать, основываясь на теоретико - групповых рассуждени-ях, что возможно обобщение программы S_T(') и для других групп (алгоритмы данной программы основываются на вычислениях в мультипликативной группе вычетов над конечным полем). То есть для всех yG, P(y)G*, где G* -представляет собой любую группу, кроме групп G**. К группам последнего вида относятся бесконечные группы, не имеющие конечных подгрупп за исключением {О`}, где О` - тождество группы. Таким образом, можно показать (при использовании в вышеуказанных алгорит-мах параметров с их независимым, равновероятным и случайным выбо-ром), что программа вида S_T(') является (?/36,?)-самотестирующейся программой. Отсюда следует доказательство утверждения леммы

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

Замечания. Как видно из псевдокода алгоритма Axmodulo N в нем используется операция ABmodulo N.




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



Книжный магазин