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

       

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


Таким образом, самотестирование должно лишь незначительно замедлять время выполнения программы P.

Самокорректирующаяся программа это вероятностная программа Cf, которая помогает программе P скорректировать саму себя, если только P выдает корректный результат с низкой вероятностью ошибки, то есть для любого x, Cf вызывает программу P для корректного вычисления f(x), в то время как собственно сама P обладает низкой вероятностью ошибки.

Самотестирующейся/самокорректирующейся программной парой называется пара программ вида (Tf,Cf). Предположим пользователь может взять любую программу P, которая целенаправленно вычисляет f и тестирует саму себя при помощи программы Tf. Если P проходит такие тесты, тогда по любому x, пользователь может вызвать программу Cf, которая, в свою очередь, вызывает P для корректного вычисления f(x). Даже если программа P, которая вычисляет значение функции f некорректно для некоторой небольшой доли входных значений, ее в данном случае все равно можно уверенно использовать для корректного вычисления f(x) для любого x. Кроме того, если удастся в будущем написать программу P' для вычисления f, тогда некоторая пара (Tf,Cf) может использоваться для самотестирования и самокоррекции P' без какой-либо ее модификации. Таким образом, имеет смысл тратить определенное количество времени для разработки самотестирующейся/ самокорректирующейся программной пары для прикладных вычислительных функций.

Перед тем как перейти к более формальному описанию определений самотестирующихся и самокорректирующихся программ необходимо дать определение вероятностной оракульной программе (по аналогии с вероятностной оракульной машиной Тьюринга).

Вероятностная программа M является вероятностной оракульной программой, если она может вызывать другую программу, которая является исполнимой во время выполнения M. Обозначение MA означает, что M может делать вызовы программы A.

Пусть P - программа, которая предположительно вычисляет функцию f. Пусть I является объединением подмножеств In, где n принадлежит множеству натуральных чисел N и пусть Dp={Dn|n


Далее, пусть err(P,f,Dn) это вероятность того, что P(x) ?12

    - если err(P,f,Dn)

    - если err(P,f,Dn)

Оракульная программа Cf с параметром 0 In и ?. Если err(P,f,Dn)

(?1,?2,?)-самотестирующейся/ самокорректирующейся программной парой для функции f называется пара вероятностных программ (Tf,Cf) такая, что существуют константы 0 ? < 1 и множество распределений Dp при которых Tf -есть (?1,?2)-самотестирующаяся программа для функции f в отношении Dp и Cf - есть ?-самокорректирующаяся программа для функции f в отношении распределения Dp.

Свойство случайной самосводимости. Пусть x



Метод создания самотестирующейся расчетной программы с эффективным тестирующим модулем

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




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

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

Пусть для функции Y = f (X) существует пара функций (gc, hc)Y таких, что:

Y = gc (f (a1), ..., f (ac)), X = hc (a1, ..., ac).

Легко увидеть, что если значения ai выбраны из In в соответствии с распределением Dp, тогда пара функций (gc, hc)Y обеспечивает выполнение для функции Y = f (X) свойства случайной самосводимости. Пару функций (gc, hc)Y будем называть ST-парой функций для функции Y = f (X).

Метод верификации расчетных программ на основе ST-пары функций.

Предположим, что на ST-пару функций можно наложить некоторую совокупность ограничений на сложность программной реализации и время выполнения. В этом случае, пусть длина кода программ, реализующих функции gc и hc , и время их выполнения составляет константный мультип-ликативный фактор от длины кода и времени выполнения программы P. Предлагаемый метод верификации расчетной программы P на основе ST-пары функций для некоторого входного значения вектора X* заключа-ется в выполнении следующего алгоритма. (Всюду далее, если осуществ-ляется случайный выбор значений, этот выбор выполняется в соответствии с распределением вероятностей Dp).




Алгоритм ST

Определить множество A*={a1*,...,ac*} такое, что X*=hc{a1*,...,ac*} , где a1*,...,ac* выбраны случайно из входного подмножества In.

Вызвать программу P для вычисления значения Y0*=f(X*)

Вызвать c раз программу P для вычисления множества значений {f(a1*),...,f(ac*)}

Определить значения Y1*=gc{f(a1*) ,...,f(ac*)}

Если Y0*=Y1* , то принимается решение, что программа P корректна на множестве значений входных параметров {X*,a1*,...,ac*} в противном случае данная программа является некорректной.

Таким образом, данный метод не требует вычисления эталонных значений и за одну итерацию позволяет верифицировать корректность программы P на (n+1) значении входных параметров. При этом время верификации можно оценить как

где ti и tx - время выполнения программы P при входных значениях ai и X* соответственно;

tg и th-1 - время определения значения функции gc и множества A* соответственно:

TP (X) - временная (не асимптотическая) сложность выполнения программы P;

Kgh (X, c)- коэффициент временной сложности программной реализации функции gc и определения A* по отношению ко временной сложности программы P (по предположению он составляет константный мульти-пликативный фактор от TP (X), а его значение меньше 1). Для традиционного вышеуказанного метода тестирования время выполнения и сравнения полученного результата с эталонным значением составляет:

где tie и txe - время определения эталонных значений функции Y = f (X) при значениях ai и X* соответственно (в общем случае, не может быть меньше времени выполнения программы).

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

Так как, коэффициент Kgh < 1, а c

Исследования процесса верификации расчетных программ

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




y = fAM (x) = Ax modulo M.

Выбор данной функции обусловлен тем, что она является одной из основных функций в различных теоретико-числовых конструкциях, например, в схемах электронной цифровой подписи, системах открытого распределения ключей и т.п. Это, в свою очередь, демонстрирует возможность применения предложенного метода при исследовании расчетных программ, решающих конкретные прикладные задачи. Кроме того, очевидно, что данная функция обладает свойством случайной самосводимо-сти, а исходя из результатов работы можно показать, что для данной функции существует (1/288, 1/8)-самотестирующаяся программа.

Для экспериментальных исследований была выбрана программа EXP из библиотеки базовых криптографических функций CRYPTOOLS , которая реализует функцию дискретного возведения в степень (размерность переменных и констант не превышает 64 байтов). Была разработана интегрированная оболочка для проведения верификации, включающая ин-терфейс с пользователем и программные процедуры, реализующие некоторую совокупность проверочных тестов. Экспериментальные исследования состояли из определения временных характеристик процесса верифи-кации на основе использования ST-пары функций и определения возмож-ности обнаружения предложенным методом преднамеренно внесенных программных ошибок. Для этого были определены следующие ST-пары функций:

В процессе исследований менялась используемая ST-пара функций и варьировалась размерность параметров A, M и аргумента X. Результаты экспериментов полностью подтвердили приведенные выше временные за-висимости (технические результаты исследований авторы в данной работе опускают).

Исследование возможности обнаружения предложенным методом преднамеренно внесенных ошибок заключалось в написании программы EXPZ. Спецификация для программ EXP и EXPZ одна и та же, отличие же заключается в том, что программа EXPZ содержит программную закладку деструктивного характера. Преднамеренно внесенная закладка при иссле-дованиях гарантировала сбой работы программы вычисления значения функции y = fAM (x) = Ax modulo M (то есть обеспечивала получение непра-ильного значения функции) примерно на каждой восьмой части входных значений экспоненты x.




Было проведено свыше 2000 экспериментов . Все входные значения, на которых произошел сбой программы, были обнаружены, что в дальнейшем подтвердилось проверочными тестами, основанными на использовании малой теоремы Ферма и теореме Эйлера. Этот факт, в свою очередь, экспериментально показал, что программа, реализующая алгоритм ST, является (1/8,1/288)-самотестирующейся программой.

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

Метод создания самокорректирующейся процедуры вычисления теоретико - числовой функции дискретного экспоненцирования

Обозначения и определения для функции дискретного возведения в степень вида gxmoduloM. Пусть In=Zq представляет собой множество {1,...,q}, где q= ?(M) - значение функции Эйлера для модуля M, а Z*M - множество вычетов по модулю M, где n= |log2M|. Пусть распределение Dp есть равномерное распределение вероятностей. Тогда равновероятный случайный выбор элемента a из множества ? будет обозначаться как a

Алгоритм Axmodulo N можно вычислить многими способами [,], один из наиболее общеизвестных и применяемых, - это алгоритм, основанный на считывании индекса (значения степени) слева направо. Этот метод достаточно прост и нагляден, история его восходит еще к 200 г. до н.э. Пусть x[1,...,n] - двоичное представление положительного числа x и A, B и N - положительные целые числа в r-ичной системе счисления, тогда псевдокод алгоритма Axmodulo N, реализованного программой Exp(') имеет следующий вид.




Псевдокод алгоритма AxmoduloN

Program Exp(x,N,A,R); {вход x,N,A, выход R} begin B:=1; for i:=1 to n do begin B:=(B*B)modN; if [i]=1 then B:=(A*B)modN; end; R:=B; end.

Из описания алгоритма видно, что число обращений к операции вида (A*B)moduloN будет logx+ ?(x), где ?(x) число единиц в двоичном представлении операнда x или вес Хэмминга x.

Построение самотестирующейся/самокорректирующейся программной пары для функции дискретного экспоненцирования.

Сначала рассмотрим следующие 4 алгоритма (см. рис.2.6 - 2.9). Для доказательства полноты и безопасности указанной пары доказывается сле-дующая теорема.

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

Для доказательства теоремы необходимо доказать следующие две леммы.

Лемма 2.1. Программа S_K_exp(M,q,g,?) является (1/8)-самокорректирующейся программой для вычисления функции gxmoduloM в отношении равномерного распределения Dn.

Доказательство. Полнота программы S_K(') означает, что если оракульная программа P(x), обозначаемая как Exp(') выполняется корректно, то и самокорректирующаяся программа S_K(') будет выполняться кор-ректно. В данном случае полнота программы очевидна. Если P(x) коррект-но вычислима, то из

Рис. 2.6. Псевдокод алгоритма S_K_exp

Рис. 2.7. Псевдокод алгоритма S_T_exp

Program L_T(n,R); {вход g,M,q, выход Rl} begin x1:=random(q); x2:=random(q); x:=(x1+x2)modq; Exp(g,x1,M,R1); Exp(g,x2,M,R2); Exp(g,x,M,R); if R1 R2=R then Rl:=1 else Rl:=0; end.

Рис. 2.8. Псевдокод алгоритма теста линейной состоятельности L_T

Program N_T(n,R); {вход g,M,q, выход Re} begin x1:=random(q); x2:=(x1+1)modq; Exp(g,x1,M,R1); Exp(g,x2,M,R2); if R1 g=R2 then Re:=1 else Re:=0; end.

Рис. 2.9. Псевдокод алгоритма теста единичной состоятельности N_T

Для доказательства безопасности сначала необходимо отметить, что так как x1




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

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

Доказательство. Полнота теста линейной состоятельности доказыва-ется аналогично доказательству полноты в лемме й, где x1,x2

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

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

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

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




Используя ту же технику доказательств, как и для функции дискретного возведения в степень, можно построить (1/576,1/36,1/36)-самокорректирующуюся/ самотестирующуюся программ-ную пару для вычисления функции модулярного умножения. Это справед-ливо исходя из следующих соображений. Вычисление функции fM(ab)=fM((a1+a2)(b1+b2)) следует из корректного выполнения программы с 4-х кратным вызовом оракульной программы P(a,b), то есть:

[PM(a1,b1)+PM(a1,b2)+PM(a2,b1)+PM(a2,b2)](mod M).

Алгоритм вычисления Axmodulo N выполняется для c=2. Однако, декомпозиция x, как следует из свойства самосводимости функции Axmodulo N, может осуществляться на большее число слагаемых. Хотя это приведет к гораздо большему количеству вызовов оракульной программы, но в то же время позволит значительно снизить вероятность ошибки.

Применение самотестирующихся и самокорректирующихся программ

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

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




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

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

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



Содержание раздела