Безопасность -> Защита информации -> Безопасность ПО компьютерных систем

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

Автор: Казарин О.В.
Источник: www.cryptography.ru

ГЛАВА 2. ОБЕСПЕЧЕНИЕ ТЕХНОЛОГИЧЕСКОЙ БЕЗОПАСНОСТИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

2.1. ФОРМАЛЬНЫЕ МЕТОДЫ ДОКАЗАТЕЛЬСТВА ПРАВИЛЬНОСТИ ПРОГРАММ И ИХ СПЕЦИФИКАЦИЙ

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

Фундаментальный вклад в теорию верификации внес Ч. Хоор, высказавший идеи проведения доказательства частичной правильности программы в виде вывода в некоторой логической системе, а Э. Дейкстра ввел понятие слабейшего предусловия, позволяющее одновременно как соответствие друг другу предусловия и постусловия, так и завершимость. Методы доказательства правильности программ принесли определенную пользу программированию. Было отмечено, что эти методы указывают способ рассуждения о ходе выполнения программ, дают удобную систему комментирования программ и устанавливают взаимосвязи между конструкциями языков программирования и их семантикой. Если принять более широкое толкование термина "анализ программ", подразумевая доказательство разнообразных свойств программ или доказательство теорем о программах, то ценность методов анализа станет более ясной. В частности можно исследовать характер изменения выходных значений программы, количество операций при выполнении программы, наличие зацикливаний, незадействованных участков программы. Таким образом, в некоторых частных случаях методы верификации могут применяться и для доказуемого обнаружения программных дефектов.

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

integer r, dd;
	r:=a; dd:=d;
	while ddr do dd:=2*dd;
	while ddd do dd:=2*dd;
		begin dd:=dd/2;
			if ddr do r:=r-dd;
			end.
			

Должно соблюдаться условие, что целые константы a и d удовлетворяют отношениям ad и d>0.

Рассмотрим последовательность значений, заданную выражениями для:

i=0	ddi=d
i>0	ddi=2*ddi-1.

ddn=d*2n				(2.1.1)

Кроме того, поскольку d>0, можно сделать вывод, что для любого конечного значения r отношение dd_r>r будет выполняться при некотором конечном значении k; первый цикл завершается при dd=d*2^k. Решая уравнение d_i=2*d_i-1 относительно d_i-1, получаем d_i-1=d_i/2, что позволяет утверждать, что второй цикл тоже завершится. По окончании первого цикла dd=dd_k и поэтому выполняется соотношение

0  r < dd 			(2.1.2)

Это соотношение сохраняется при выполнении повторяемого оператора второго заголовка. После завершения повторений (в соответствии с заголовком while ddd do) мы получаем dd=d. Отсюда и из соотношения (2) следует, что

0  r < d  			(2.1.3)

Далее мы доказываем, что после начала работы программы всегда выполняется отношение:

dd0(mod d)		    (2.1.4)

Это следует, например, из того, что возможные значения dd имеют вид (см. (1)) d*2ⁱ при 0 i k.

Следующая задача состоит в том, чтобы показать, что после присваивания r начального значения всегда выполняется отношение

ar(mod d)		     (2.1.5)

Оно выполняется после начальных присваиваний.

Повторяемый оператор первого заголовка (dd:=2*dd) сохраняет отношение (2.1.5), и поэтому весь первый цикл сохраняет отношение (2.1.5).

Повторяемый оператор из второго цикла состоит из двух операторов. Первый (dd:=2*dd) сохраняет инвариантность (2.1.5); второй тоже сохраняет отношение (2.1.5), так как он либо не изменяет значение r, либо уменьшает r на текущее dd, а эта операция в силу (2.1.4) также сохраняет справедливость отношения (2.1.5). Таким образом, весь повторяемый оператор второго цикла сохраняет отношение (2.1.5).

Объединяя отношения (2.1.3) и (2.1.5), получаем, что окончательное значение r удовлетворяет условиям 0 r < d и ar(mod d), то есть r - наименьший неотрицательный остаток от деления a на d.

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

Большинство известных алгоритмов электронной цифровой подписи в качестве основной алгоритмической операции используют дискретное возведение в степень. Стойкость соответствующих криптографических схем основывается (как правило, гипотетически) или на сложности извлечения корней в поле GF(n), n - произведение двух больших простых чисел, или на трудности вычисления дискретных логарифмов в поле GF(p), p - большое простое число. Чтобы противостоять известным на данный момент методам решения этих задач операнды должны иметь длину порядка 512 или 1024 битов. Понятно, что выполнение вычислений над операндами повышенной разрядности (еще будет употребляться термин "операнды многократной точности" по аналогии с операндами однократной и двукратной точности) требует высокого быстродействия рабочих алгоритмов криптографических схем.

Представление чисел

Алгоритм использует вычислительную систему с фиксированной длиной слова, то есть A, B, N, P и S будут также рассматриваться как векторы A[1,m], B[1,m], N[1,m], P[1,m'] и S[1,m'], где каждый элемент вектора (элемент одномерного массива) есть цифра r-ичной системы счисления, m'=m+h, величина h будет изменяться в зависимости от вида алгоритма. Основание r такой системы будет ограничено длиной машинного слова λ и цифры такой системы имеют вид 0,1,...,r-1 (r выбирается как целое положительное основание с неотрицательной базой). При этом n и m связаны соотношением n=s*m, где s=log₂r (в дальнейших рассуждениях log - логарифм по основанию 2). Наиболее целесообразно выбрать основание r=2^λ как наиболее экономное представление чисел в машине, ибо при r < 2^λ на представление чисел уходит больше памяти. Например, широко принятое на практике представление десятичных чисел в двоично-десятичном коде требует на 20 % большего объема памяти, чем двоичное представление тех же чисел.

Тем не менее, иногда полезно представлять ситуацию, когда r=10 или r=10^k, например, при отладке программ.

Следует также обратить внимание на тот факт, что при выполнении арифметических операций над числами многократной точности, например, по классическим алгоритмам Кнута, основание r следует уменьшать, чтобы не возникло переполнение разрядной сетки. Так, для операции сложения уменьшение выполняется до r=2^λ-1, для умножения - до r=2^λ/2. Однако если архитектурой вычислительной системы предусмотрен флаг переноса или хранение промежуточного результата с двойной точностью, то можно возвращаться к основанию r=2^λ.

Алгоритм A*B modulo N - алгоритм выполнения операции модулярного умножения

Операнды многократной точности для данного алгоритма представляются в виде одномерного массива целых чисел. Для знака можно зарезервировать элемент с нулевым индексом. Особенности представления чисел при организации взаимодействия алгоритма с другими рабочими программами, при организации ввода-вывода и т.д. рассматриваются, например, в работе. В алгоритме использован известный вычислительный метод "разделяй и властвуй" и реализован способ вычисления "цифра-за-цифрой". Прямое умножение не следует делать по нескольким причинам: во-первых, произведение A*B требует в два раза больше памяти, чем при методе "цифра-за-цифрой"; во-вторых, умножение двух многоразрядных чисел труднее организовать, чем умножение числа многократной точности на число однократной точности. Так, в работе приводятся расчеты на супер-ЭВМ "CRAY-2" для 100-разрядных десятичных чисел: модулярное умножение методом "цифра-за-цифрой" выполняется примерно на 10% быстрее, чем прямое умножение и следующая за ним модульная редукция. Алгоритм модулярного умножения (алгоритм P) приведен на рис.2.1, а на рис.2.2 представлен псевдокод процедуры ADDK.

Так как B[i] [0,...,2 ^λ/2-1], то проверку "if B[i]<>0" в алгоритме P можно не вводить потому, что вероятность того, что B[i] будет равняться 0 пренебрежимо мала, если значение λ не достаточно малым. Ошибка затем все равно будет алгоритмом обнаружена. Проверка

"if p_short-k*n_short>n_short DIV 2"

позволяет представлять k числом однократной точности и работать с наи-меньшими абсолютными остатками в каждой итерации. Значение операнда P_i на каждом шаге итерации должно быть ограничено величиной N.

Теорема 2.1. Пусть P_i - частичное произведение P в конце i-той итерации (т.е. в конце i-того цикла FOR алгоритма P). Тогда для любого i (i=[1,...,n]) abs(P_i)<N, r^m-1 N r^m.

Доказательство теоремы 2.1. Доказательство теоремы проведем методом индукции. Если k=abs(p_short) DIV n_short, где DIV - целочисленное деление, то

p_short=(k+δ)*n_short,		(2.1.6)

где k - целое, 0 k < r-1 и 0 δ < 1.

Проверка "if p_short-k*n_short>n_short DIV 2" есть ни что иное, как проверка

 δ > 0.5			           (2.1.7)

На i-том шаге алгоритм вычисляет:

P'=Pi-1*r+A*B[i]			      (2.1.8)

Возможны два варианта:

Вариант 1. Если k=0, т.е. n_short>abs(p_short) (см. алгоритм), то суммирование при помощи процедуры ADDK не производится и утверждение теоремы выполняется, т.е. abs(P_i) < N .

Вариант 2. Если k > 0, т.е.

n_short < abs(p_short)	(2.1.9)

Здесь также возможны два варианта:

Вариант A:

p_short < 0		(2.1.10)

Из (2.1.9) и (2.1.10) следует P'<-N и так как Pi=-P'+k*N (см. алгоритм), то согласно (2.1.7)

Pi= δ*N,	если δ  0.5  (2.1.11)

и так как P_i=-P'+(k+1)*N, то

Pi=-(1-δ)*N,	если δ > 0.5 (2.1.12)

Алгоритм P

m_shifts:=0;
while n[m_shifts]=0 do
   begin
     shift_left(N and A);
     m_shifts:=m_shifts+1;
   end;
m:=m_shifts;
reset(P);
n_short:=N[m];
for i:=n downto 1 do
   begin
     shift_left(P); 

	{сдвиг на 1 элемент влево или
 умножение P*r}
     if b<>0 then
        addk(A*B[i],{to}P);
     let p_short represent the 2 high

	  assimilated digits of P;
     k:=abs(p_short) div n_short;
     if p_short-k*n_short > n_short div 2 then

	  k:=k+1;
     if k>0 then
        begin
          if p_short < 0 then
             addk(k*N,{to} P)
          else
             addk(-k*N,{to} P);
        end;
     end;{for}
right shift P, N by m_shifts;
if P < 0 then
    P:=P+N;
write(P); {P - результат}

Рис. 2.1. Псевдокод алгоритма модулярного умножения A*B modulo N

Алгоритм ADDK

carry:=0;
for i:=1 to m do
    begin
      t:=P[i]+k*N[i]+carry;
      P[i]:=t mod r;
      carry:=t div r;
    end;
P[m+1]:=carry;
write(P); {P - результат}

Рис.2.2. Псевдокод алгоритма вычисления P+k*N (процедура ADDK)

Вариант B:

p_short>0	(2.1.13)

Из (2.1.9) и (2.1.13) следует P'>N и так как P_i=P'-k*N, то согласно (2.1.7)

Pi=-δ *N,			если  δ   0.5 (2.1.14)

и так как P_i=P'-(k+1)*N, то

Pi=(1-δ)*N, если δ > 0.5 (2.1.15)

Во всех случаях (2.1.11), (2.1.12), (2.1.14) и (2.1.15), так как 0 δ < 1, то abs(P_i) < N. Теорема доказана

Примечание. Для чего нужна проверка (2.1.7)

"if p_short-k*n_short>n_short DIV 2" ?

Пусть в конце каждой итерации P принимает максимально возможное значение P_i-1=N-1, а N, A и B[i] заведомо тоже велики: N=rⁿ⁺¹-1, A=rⁿ⁺¹-2, B[i]=r-1. Тогда на i-том шаге согласно (2.1.8):

Pi'=(rn+1-2)*r+(rn+1-2)*(r-1)=2*rn+2-rn+1-4*r+2(2.1.16)

   (2.1.17)

При достаточно большом m, если не введена проверка (2.1.6), то k < 2*r-1, по условию же 0< k < r -1. И из (2.1.16) и (2.1.17) видно, что P придется представлять m+2 разрядами (что определяется слагаемым 2*rⁿ⁺²), по условию же m+1. Если же ввести проверку (2.1.7), то даже при δ=0,5 т.е.

P_i-1=(N-1)/2 и с учетом того, что если неравенство (2.1.7) выполняется, то P_i меняет знак на противоположный (сравн. (2.1.11), (2.1.12), (2.1.14) и (2.1.15)), из (2.1.6) и (2.1.7) получим, что 0 k < (1/2)*r-1, что удовлетворяет наложенному на k условию, и для представление P достаточно m+1 разряда.

В алгоритме P используется также известный метод, когда для получения частного от деления двух многоразрядных чисел, используются только старшие цифры этих чисел (см., например, алгоритм D в работе [36, стр.291-295]). Чем больше основание системы счисления r, тем ниже вероятность того, что пробное частное k от деления первых цифр больших чисел не будет соответствовать действительному частному.

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

2.2. МЕТОДЫ И СРЕДСТВА АНАЛИЗА БЕЗОПАСНОСТИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

Широко известны различные средства программного обеспечения обнаружения элементов РПС - от простейших антивирусных программ-сканеров до сложных отладчиков и дизассемблеров - анализаторов и именно на базе этих средств и выработался набор методов, которыми осуществляется анализ безопасности ПО.

Авторы работ [17,45] предлагают разделить методы, используемые для анализа и оценки безопасности ПО, на две категории: контрольно-испытательные и логико-аналитические (см. рис.2.3). В основу данного разделения положены принципиальные различия в точке зрения на исследуемый объект (программу). Контрольно-испытательные методы анализа рассматривают РПС через призму фиксации факта нарушения безопасного состояния системы, а логико-аналитические - через призму доказательства наличия отношения эквивалентности между моделью исследуемой программы и моделью РПС.

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

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

2.2.1. Контрольно-испытательные методы анализа безопасности программного обеспечения

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

Рис. 2.3. Методы и средства анализа безопасности ПО

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

Пусть задано множество ограничений на функционирование программы, определяющих ее соответствие требованиям по безопасности в системе предполагаемой эксплуатации. Эти ограничения задаются в виде множества предикатов С={c_i(a₁,a₂,...a_m)|i=1,...,N} зависящих от множества аргументов A={a_i|i=1,...,M}.

Это множество состоит из двух подмножеств:

• подмножества ограничений на использование ресурсов аппаратуры и операционной системы, например оперативной памяти, процессорного времени, ресурсов ОС, возможностей интерфейса и других ресурсов;
• подмножества ограничений, регламентирующих доступ к объектам, содержащим данные (информацию), то есть областям памяти, файлам и т.д.

Для доказательства того, что исследуемая программа удовлетворяет требованиям по безопасности, предъявляемым на предполагаемом объекте эксплуатации, необходимо доказать, что программа не нарушает ни одного из условий, входящих в С. Для этого необходимо определить множество параметров P={p_i|i=1,...,K}, контролируемых при тестовых запусках программы. Параметры, входящие в это множество определяются используемыми системами тестирования. Множество контролируемых параметров должно быть выбрано таким образом, что по множеству измеренных значений параметров Р можно было получить множество значений аргументов А.

После проведения Т испытаний по вектору полученных значений параметров P_i,i=1,...,T можно построить вектор значений аргументов A_i, i=1,...,T.

Тогда задача анализа безопасности формализуется следующим образом.

Программа не содержит РПС, если для любого ее испытания i=1,...,T множество предикатов C={c_j(a_1i,a_2i...a_Mi)|j=1,...,N} истинно.

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

Рассмотрим схему анализа безопасности программы контрольно-испытательным методом (рис.2.4).

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

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

2.2.2. Логико-аналитические методы контроля безопасности программ

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

Формальная постановка задачи анализа безопасности логико-аналитическими методами может быть сформулирована следующим образом.

Рис.2.4. Схема анализа безопасности ПО с помощью контрольно-испытательных методов

Рис. 2.5. Схема анализа безопасности ПО с помощью логико-аналитических методов

Выбирается некоторая система моделирования программ, представленная множеством моделей всех программ - Z. В выбранной системе исследуемая программа представляется своей моделью М, принадлежащей множеству Z. Должно быть задано множество моделей РПС V={v_i|i=1,...,N}, полученное либо путем построения моделей всех известных РПС, либо путем порождения множества моделей всех возможных (в рамках данной модели) РПС. Множество V является подмножеством множества Z. Кроме того, должно быть задано отношение эквивалентности определяющее наличие РПС в модели программы, обозначим его Е(x,y). Это отношение выражает тождественность программы x и РПС y, где x - модель программы, y - модель РПС, и y принадлежит множеству V.

Тогда задача анализа безопасности сводится к доказательству того, что модель исследуемой программы М принадлежит отношению E(M,v), где v принадлежит множеству V.

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

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

В целом полный процесс анализа ПО включает в себя три вида анали-за:

• лексический верификационный анализ;
• синтаксический верификационный анализ;
• семантический анализ программ.

Каждый из видов анализа представляет собой законченное исследование программ согласно своей специализации.

Результаты исследования могут иметь как самостоятельное значение, так и коррелироваться с результатами полного процесса анализа.

Лексический верификационный анализ предполагает поиск распознавания и классификацию различных лексем объекта исследования (программа), представленного в исполняемых кодах. При этом лексемами являются сигнатуры. В данном случае осуществляется поиск сигнатур следующих классов:

• сигнатуры вирусов;
• сигнатуры элементов РПС;
• сигнатуры (лексемы) "подозрительных функций";
• сигнатуры штатных процедур использования системных ресурсов и внешних устройств.

Поиск лексем (сигнатур) реализуется с помощью специальных про-грамм-сканеров.

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

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

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

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

2.3. МЕТОДЫ ОБЕСПЕЧЕНИЯ НАДЕЖНОСТИ ПРОГРАММ ДЛЯ КОНТРОЛЯ ИХ ТЕХНОЛОГИЧЕСКОЙ БЕЗОПАСНОСТИ

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

Исходные данные, определения и условия

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

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

Интуитивное определение безопасности ПО может быть уточнено в статистическом смысле на основе следующих простых соображений:

• машинная программа p может быть определена как описание некоторой вычислимой функции F на множестве E всех значений наборов входных данных, таких что каждый элемент E_i множества E представляет собой набор значений данных, необходимый для выполнения прогона программы: E=(E_i:i=1,2,...,N);
• выполнение программы p приводит к получению для каждого Ei определенного значения функции F(E_i);
• множество E определяет все возможные вычисления в программе p, то есть каждому набору входных данных E_i соответствует прогон программы p, и наоборот, каждому прогону соответствует некоторый набор входных данных E_i;
• наличие дефектов в программе p приводит к тому, что ей на самом деле соответствует функция F', отличная от заданной функции F;
• для некоторого E_i отклонение выхода F'(E_i), полученного в результате выполнения программы не должно превышать уровень безопасности программного обеспечения S(E_i), то есть безопасность обеспечивается при соблюдении ограничения: F'(E_i), S(E_i). (Вопрос о том, приводит ли некоторое отклонение выхода к нарушению условия безопасности, должен решаться в каждом конкретном случае отдельно, поскольку все определяется конкретными особенностями поведения системы после нарушения ее работы) .

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

Однако в процесс функционирования программы выбор входных данных из E обычно осуществляется не с одинаковыми априорными вероятностями, а диктуется определенными условиями работы. Эти условия характеризуются некоторым распределением вероятностей p_i, того, что будет выбран набор входных данных E_i. Распределение P может быть определено через p_i с помощью величины y_i, которая принимает значение 0, если прогон программы на наборе E_i заканчивается вычислением приемлемого значения функции, и значением 1, если этот прогон заканчивается обнаружением дефекта. Поэтому - есть вероятность того, что прогон программы на наборе входных данных E_i, выбранных случайно с распределением вероятностей p_i, закончится обнаружением дефекта. При этом R=1-P есть вероятность того, что прогон программы p на наборе входных данных E_i, выбранных случайно с распределением вероятностей p_i, приведет к получению приемлемого результата.

Введем также определения и обозначения, связывающие структурные характеристики программ с их безопасностью. Структурными характеристиками программы p являются множество ветвей L_j (j=1,...,n), подмножества входных наборов данных G_j, соответствующие ветвям L_j, множества сегментов Seg_j, из которых состоят отдельные ветви, совокупность операторов ветвления, которые обеспечивают переход от одного сегмента к другому при движении по отдельной ветви программы.

Оценка технологической безопасности программ на базе метода Нельсона

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

1. Определение множества E входных массивов.
2. Выделение в E подмножеств G_j, связанных с отдельными ветвями программы.
3. Определение для каждого G_j в предполагаемых условиях функционирования значений вероятности P_j.
4. Определение подмножества G_j для каждого входного набора данных, используемого в контрольных примерах.
5. Выявление проверенных пар и непроверенных в ходе испытаний сегментов и пар сегментов.
6. Определение для каждого j величины P'=a_jP_j, где a_j определяется в соответствии со следующими правилами [56].
   • a_j=0,99, если подмножество G_j включает более одного контрольного примера;
   • a_j=0,95, если подмножество G_j включает ровно один контрольный пример;
   • a_j=0,90, если подмножество G_j не включает ни одного контрольного примера, но в процессе проверки программы были найдены все сегменты и все сегментные пары ветви L_j;
   • a_j=0,80, если в ходе испытаний были опробованы все сегменты, но не все сегментные пары;
   • a_j=0,80-0,20m, если m сегментов (1 m 4) ветви L_j не были опробованы в ходе испытаний;
   • a_j=0, если более чем 4 сегмента не были опробованы в процессе испытаний.
7. Вычисление грубой оценки R" осуществляется по формуле , где k представляет собой общее число ветвей программы.

Приведенные выше параметры a_j были определены интуитивно [56] на основе анализа теоретических результатов исследования и экспериментальных результатов тестирования различных программ. Для того, чтобы получить более точные оценки величины R необходимо провести измерения с использованием подходящего метода формирования выборки.

Оценка технологической безопасности ПО осуществляется посредством проверки условия R" S", где S" установленная нормативными документами граница безопасности ПО. Отметим также, что для систем критических приложений такая граница должна быть достаточно высокой, то есть стремится к 1.

2.4. МЕТОДЫ СОЗДАНИЯ АЛГОРИТМИЧЕСКИ БЕЗОПАСНЫХ ПРОЦЕДУР

2.4.1. Постановка задачи

Основной отличительной особенностью подхода, связанного с созданием алгоритмически безопасного ПО является то, что начало процесса обеспечения безопасности программ при их разработке можно перенести на более ранние этапы жизненного цикла программного обеспечения, например, на этапы, предшествующие этапу испытания программ, тем самым увеличив общее время на внесение в программы защитных функций. Здесь уместно процитировать слова Э.В. Дейкстра, одного из основоположников современной методологии программирования, сказанные им еще в 1972 году ([14], стр.41): "В настоящее время общепринятой техникой является составление программы, а затем ее тестирование. Однако тестирование программ может быть очень эффективным способом демонстрации наличия ошибок, но оно безнадежно неадекватно для доказательства их отсутствия... Не следует сначала писать программу, а потом доказывать ее правильность, поскольку в этом случае требование найти доказательство только увеличит тяготы бедного программиста". Эти слова как нельзя лучше подходят и к современной проблематике, связанной, в данном случае, не столько с разработкой правильных, сколько безопасных программ. Иными словами, ключом к созданию безопасного программного обеспечения является стремление защищаться от дефектов с самого начала жизненного цикла программ, а не после факта их создания.

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

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

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

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

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

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

При использовании контрольно-испытательных методов анализа безопасности программ, когда анализу подвергается только исполняемый код программы [17,45] можно получить (как правило, экспертным путем) либо приближенные количественные характеристики обнаружения дефектов в контролируемых программах, либо стратификационные характеристики ненарушения программой некоторых условий безопасности. В этом случае постановка 1 задачи разработки программы P принципиально не меняется. (Естественно не рассматриваются простейшие случаи, когда при тестировании возможен контроль результата программы при полном переборе всех входных значений, при всех ограничениях и допущениях и т.п.).

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

Постановка 2. "При некоторых условиях и ограничениях необходимо разработать программу P*, которая корректно вычисляет результат для всех своих входных значений с пренебрежимо малой вероятностью ошибки". На примере постановок 3, 4 и 5, 6 можно также проследить существенную разницу в парадигме разработки безопасных программ. Постановки 3 и 4 в отличие от постановок 1 и 2 учитывают не "содержание" наборов входных значений программы P, а их распределения вероятностей, а постановки 5 и 6 являются в некотором смысле обобщенными и учитывают заданный структурный критерий тестирования.

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

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

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

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

Одним из принципиальных условий решения задачи в постановке 2, 4 и 6 является наличие некоего свойства алгоритмической трансформации, позволяющего переходить от традиционного пути создания программ, которые будут затем проверяться на наличие дефектов, к априорно безопасным программам. К числу таких примеров можно отнести самокорректирующиеся и самотестирующиеся программы [23,26,31,33,62,63] (п.2.6.1.), обладающие свойством случайной самосводимости и программы, созданные на базе методов конфиденциальных вычислений [24,25,32] (п.2.6.2), начало изучения которых было положено в работах [61,67]. Рассмотренные до этого методы анализа безопасности ПО связаны с попытками обезопасить фактически уже разработанное программное обеспечение от действий злоумышленника. Это означает, что разработка безопасного ПО возможна за счет создания средств противодействия программным закладкам для продуктов, созданных на основе существующих информационных технологий создания программного обеспечения. То есть, только после факта разработки программ начинается верификационный анализ, тестирование или контроль их на технологическую безопасность. В этом смысле проблема обеспечения технологической безопасности программного обеспечения более близка к фундаментальной проблеме его надежности.

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

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

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

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

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

2.4.2. Методы создания самотестирующихся и самокорректирующихся программ для решения вычислительных задач

Общие принципы создания двухмодульных вычислительных процедур и методология самотестирования Пусть необходимо написать программу P для вычисления функции f так, чтобы P(x)=f(x) для всех значений x.Традиционные методы верификационного анализа и тестирования программ не позволяют убедиться с вероятностью близкой к единице в корректности результата выполнения программы, хотя бы потому, что тестовый набор входных данных, как правило, не перекрывают весь их возможный спектр. Один из методов решения данной проблемы заключается в создании так называемых самокорректирующихся и самотестирующихся программ, которые позволяют оценить вероятность некорректности результата выполнения программы, то есть, что P(x) f(x) и корректно вычислить f(x) для любых x, в том случае, если сама программа P на большинстве наборах своих входных данных (но не всех) работает корректно.

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

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

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

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

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

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

Пусть P - программа, которая предположительно вычисляет функцию f. Пусть I является объединением подмножеств I_n, где n принадлежит множеству натуральных чисел N и пусть D^p={D_n|n N} есть множество распределений вероятностей D_n над I_n. Далее, пусть err(P,f,D_n) это вероятность того, что P(x) f(x), где x выбрано случайно в соответствии с распределением D_n из подмножества I_n. Пусть β - есть некоторый параметр безопасности. Тогда (ε₁, ε₂)-самотестирующейся программой для функции f в отношении D^p с параметрами 0 ε₁<ε₂ 1 - называется вероятностная оракульная программа T_f, которая для параметра безопасности β и любой программы P на входе n имеет следующие свойства:

- если err(P,f,D_n)ε₁, тогда программа T_f^P выдаст на выходе ответ "норма" с вероятностью не менее 1-β .
- если err(P,f,D_n)ε₂, тогда программа T_f^P выдаст на выходе "сбой" с вероятностью не менее 1-β .

x I_n

err(P,f,D_n)ε

Свойство случайной самосводимости. Пусть x I_n и пусть c > 1 - есть целое число. Свойство случайной самосводимости заключается в том, что существует алгоритм A₁, работающий за время пропорциональное n^O(1), по-средством которого функция f(x) может быть выражена через вычислимую функцию F от x, a₁,...,a_c и f(a₁),...,f(a_c) и алгоритм A₂, работающий за время пропорциональное n^O(1), посредством которого по данному x можно вычислить a₁,...,a_c, где каждое a_i является случайно распределенным над I_n в со-ответствии с D^p.

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

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

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

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

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

Легко увидеть, что если значения a_i выбраны из I_n в соответствии с распределением D^p, тогда пара функций (g_c, h_c)^Y обеспечивает выполнение для функции Y = f (X) свойства случайной самосводимости. Пару функций (g_c, h_c)^Y будем называть ST-парой функций для функции Y = f (X).

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

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

Алгоритм ST

Определить множество A*={a₁*,...,a_c*} такое, что X*=h_c{a₁*,...,a_c*} , где a₁*,...,a_c* выбраны случайно из входного подмножества I_n.
Вызвать программу P для вычисления значения Y₀*=f(X*)
Вызвать c раз программу P для вычисления множества значений {f(a₁*),...,f(a_c*)}
Определить значения Y₁*=g_c{f(a₁*) ,...,f(a_c*)}

Если Y₀*=Y₁* , то принимается решение, что программа P корректна на множестве значений входных параметров {X*,a₁*,...,a_c*} в противном случае данная программа является некорректной.

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

t_g и t_h^-1 - время определения значения функции g_c и множества A* соответственно:

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

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

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

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

Так как, коэффициент K_gh < 1, а c 2, то получаем относительный вы-игрыш по оперативности испытания расчетных программ указанного типа (обладающих свойством случайной самосводимости) более чем в 1.5 раза.

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

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

y = f_AM (x) = A^x modulo M.

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

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

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

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

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

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

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

Обозначения и определения для функции дискретного возведения в степень вида g^xmoduloM. Пусть I_n=Z_q представляет собой множество {1,...,q}, где q= φ(M) - значение функции Эйлера для модуля M, а Z*_M - множество вычетов по модулю M, где n= |log₂M|. Пусть распределение D^p есть равномерное распределение вероятностей. Тогда равновероятный случайный выбор элемента a из множества Ω будет обозначаться как a_RΩ . Оракульной программой, в данном случае, является программа вы-числения функции g^xmoduloM, по отношению к исследуемым самотестирующейся и самокорректирующейся программам.

Алгоритм A^xmodulo N можно вычислить многими способами [34,64], один из наиболее общеизвестных и применяемых, - это алгоритм, основанный на считывании индекса (значения степени) слева направо. Этот метод достаточно прост и нагляден, история его восходит еще к 200 г. до н.э. Пусть x[1,...,n] - двоичное представление положительного числа x и A, B и N - положительные целые числа в r-ичной системе счисления, тогда псевдокод алгоритма A^xmodulo 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.

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

Сначала рассмотрим следующие 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)-самокорректирующейся/ самотестирующейся про-граммной парой для функции g^xmoduloM, с входными значениями, выбранными случайно и равновероятно из множества I_n.

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

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

Доказательство. Полнота программы 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

Для доказательства безопасности сначала необходимо отметить, что так как x_{1 R}Z_q, то и x₂ имеет равномерное распределение вероятностей над Z_q. Так как вероятность ошибки ε 1/8, то в одном цикле вероят-ность Prob[R_k=f_M,g(x)] 3/4. Чтобы вероятность корректного ответа была не менее чем 1- β, исходя из оценки Чернова [62], необходимо выполнить не менее 12ln(1/β ) циклов

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

Доказательство. Полнота теста линейной состоятельности доказыва-ется аналогично доказательству полноты в лемме й, где x₁,x_{2 R}Z_q. Полнота теста единичной состоятельности вытекает исходя из следующего очевид-ного факта. Корректное выполнение теста [P_M,g(x₁)'P_M.g(1)](mod M) соответствует вычислению функции:

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

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

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

Замечания. Как видно из псевдокода алгоритма A^xmodulo N в нем используется операция ABmodulo N. Используя ту же технику доказательств, как и для функции дискретного возведения в степень, можно построить (1/576,1/36,1/36)-самокорректирующуюся/ самотестирующуюся программ-ную пару для вычисления функции модулярного умножения. Это справед-ливо исходя из следующих соображений. Вычисление функции f_M(ab)=f_M((a₁+a₂)(b₁+b₂)) следует из корректного выполнения программы с 4-х кратным вызовом оракульной программы P(a,b), то есть:

[P_M(a₁,b₁)+P_M(a₁,b₂)+P_M(a₂,b₁)+P_M(a₂,b₂)](mod M).

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

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

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

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

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

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

2.4.3. Создание безопасного программного обеспечения на базе методов теории конфиденциальных вычислений

Постановка задачи

Задачу конфиденциальных вычислений, которая решается посредством многостороннего интерактивного протокола можно описать в следующей постановке. Имеется n участников протокола или n процессоров вычислительной системы, соединенных сетью связи. Изначально каждому процессору известна своя "часть" некоторого входного значения x. Требуется вычислить f(x), f - некоторая известная всем участникам вычислимая функция, таким образом, чтобы выполнились следующие требования:

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

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

Общие замечания по проблематике конфиденциальных вычислений

Задача конфиденциального вычисления была впервые сформулирована А.Яо для случая с двумя участниками в 1982 г. В 1987 г. О. Голдрайх, С. Микали и А. Вигдерсон показали, как безопасно вычислить любую функцию, аргументы которой распределены среди участников в вычисли-тельной установке (то есть в конструкции, где потенциальный противник ограничен в действиях вероятностным полиномиальным временем). В их работе рассматривалась синхронная сеть связи из n участников, где каналы связи небезопасны и стороны, также как и противник, ограниченны в сво-их действиях вероятностным полиномиальным временем. В своей модели вычислений они показали, что в предположении существования односто-ронних функций с секретом можно построить многосторонний протокол (с n участниками) конфиденциальных вычислений любой функции в присут-ствие пассивных противников (т.е., противников, которым позволено толь-ко "прослушивать" коммуникации). Для некоторых типов противников (для византийских сбоев) авторы привели протокол для конфиденциально-го вычисления любой функции, где ( n/2 -1) участников протокола явля-ются нечестными (или ( n/2 -1)-протокол конфиденциальных вычислений).

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

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

В работе [61], авторы начали комплексные исследования асинхронных конфиденциальных вычислений. Они рассмотрели полностью асинхрон-ную сеть (т.е., сеть, где не существует глобальных системных часов), в ко-торой стороны соединены защищенными каналами связи. Автор привел первый асинхронный протокол византийских соглашений с оптимальной устойчивостью, где противник может "подкупать" n/3 -1 из n участников вычислений.

Определение односторонней функции, описание используемых примитивов, схем и протоколов

В качестве одного из основных математических объектов в данной работе используются односторонние функции, то есть вычислимые функции, для которых не существует эффективных алгоритмов инвертирова-ния. Необходимо отметить, что односторонняя функция - гипотетический объект, поэтому называть конкретные функции односторонними матема-тически некорректно. Впервые такую гипотетическую конструкцию для конкретного криптографического приложения, - открытого распределения ключей, предложили У. Диффи и М. Хеллман в 1976 г. (см, например, оп-ределения в работе [6]). Они показали, что вычисление степеней в мульти-пликативной группе вычетов над конечным полем является простой зада-чей с точки зрения состава необходимых вычислений, в то время как из-влечение дискретных логарифмов над этим полем - предположительно сложная вычислительная задача.

Неформально говоря, для двух независимых множеств X и Y функция f:X- > Y называется односторонней, если для каждого x X можно легко вычислить f(x), в то время как почти для всех y Y вычислительно трудно по-лучить такой x X, что f(x)=y, при условии , что такой x существует.

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

Функция f называется односторонней, если существует полиномиальная машина Тьюринга T, которая на любом входе x вычисляет f(x) и для любого полиномиального алгоритма A справедливо следующее.

Пусть x _{R n} и слово y=f(x) подано на вход алгоритма A. Тогда для любого полинома p и для всех достаточно больших n вероятность Prob(f(A(y))=y)<1/p(n).

Вероятность берется по выбору значения x из _n и, если A - это веро-ятностная машина Тьюринга, - по вырабатываемым ею случайным величинам.

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

• любая группа из менее чем t участников не может получить любую информацию о секрете;
• любая группа из не менее чем t участников может вычислить сек-рет за полиномиальное время.

Пусть секрет s - элемент поля F. Чтобы распределить s среди участни-ков P₁,...,P_n, (где n< |F| ) дилер выбирает полином f F[x] степени не более t-1, удовлетворяющий f(0)=s. Участник P_i получает s_i=f(x_i) как свою долю секрета s, где x_i F\{0} - общедоступная информация для P_i (x_i x_j для i j).

Вследствие того, что существует один и только один полином степени не менее k-1, удовлетворяющий f(x_i)=s_i для k значений i, схема Шамира удовлетворяет определению (n,t)-пороговых схем. Любые t участников могут найти значение f по формуле:

Следовательно

где a₁,...,a_k получаются из

Таким образом, каждый a_i является ненулевым и может быть легко вычислен из общедоступной информации. Проверяемая схема разделения секрета. Пусть имеется n участников вычислений и t* (значение t* не более порогового значения t) из них могут отклоняться от предписанных протоколом действий. Один из участников назначается дилером Д, которому (и только ему) становится известен секрет (секретная информация) s. На первом этапе дилер вне зависимости от действий нечестных участников осуществляет привязку к уникальному параметру u. Идентификатор дилера известен всем абонентам системы. На втором этапе осуществляется открытие (восстановление) секрета s всеми честными участниками системы. И если дилер Д - честный, то s=u.

Проверяемая схема разделения секрета ПРС представляет собой пару многосторонних протоколов (РзПр,ВсПр), - а именно протокола разделения секрета и проверки правильности разделения РзПр и протокола восстановления и проверки правильности восстановления секрета ВсПр, при реализации которых выполняются следующие условия безопасности. Условие полноты. Для любого s, любой константы c>0 и для достаточно больших n вероятность Prob((n,t,t*)РзПр=(Да,s) t* < t & Д - честный)>1-n^-c.

Условие верифицируемости. Для всех возможных эффективных алгоритмов Прот, любой константы c>0 и для достаточно больших n вероятность

Prob((t*,(Да,u))ВсПр=(s=u)| (n,t,t*)РзПр=(Да,u)& t* < t & Д - честный)<n^-c.

Условие неразличимости. Для секрета s* _RS вероятность

Prob(s*=s |(n,t,t*)РзПр=(Да,s*) & Д - честный)< 1/ |S| .

Свойство полноты означает, что если дилер Д честный и количество нечестных абонентов не больше t, тогда при любом выполнении протокола РзПр завершится корректно с вероятностью близкой к 1. Свойство верифицируемости означает, что все честные абоненты выдают в конце протокола ВсПр значение u, а если Д - честный, тогда все честные абоненты восстановят секрет s=u. Свойство неразличимости говорит о том, что при произвольном выполнении протокола РзПр со случайно выбранным секретом s*, любой алгоритм Прот не может найти s*=s лучше, чем простым угадыванием.

Широковещательный примитив (Br-субпротокол). Введем следующее определение. Протокол называется t-устойчивым широковещательным протоколом, если он инициализирован специальным участником (дилером Д), имеющим вход m (сообщение, предназначенное для распространения) и для каждого входа и коалиции нечестных участников (числом не более t) выполняются условия.

Условие завершения. Если дилер Д - честный, то все честные участники обязательно завершат протокол. Кроме того, если любой честный участник завершит протокол, то все честные участники обязательно завершат протокол.

Условие корректности. Если честные участники завершат протокол, то они сделают это с общим выходом m*. Кроме того, если дилер честный, тогда m*=m.

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

Br-протокол

Код для дилера (по входу m):

1. Послать сообщение (сбщ,m) всем процессорам и завершить протокол с выходом m.
   Код для процессоров:
2. После получения первых сообщений (сбщ,m) или (эхо,m), послать (эхо,m) ко всем процессорам и завершить протокол с выходом m.

Предложение 2.1. Br-протокол является t-усточивым широковещательным протоколом для противников, которые могут приостанавливать отправку сообщений.

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

Протокол BB

Код для дилера (по входу m):

1. Послать сообщение (сбщ,m) ко всем процессорам.
   Код для процессора P_i:
2. После получения сообщения (сбщ,m`), послать сообщение (эхо,m`) ко всем процессорам.
3. После получения n-1 сообщений (сбщ,m` ), которые согласованы со значением m` послать сообщение (гот,m` ) ко всем процессорам.
4. После получения t+1 сообщений (гот,m` ), которые согласованы со значением m` , послать (гот,m` ) ко всем процессорам.
5. После получения n-1 сообщений (сбщ,m` ), которые согласованы со значением m , послать сообщение (OK,m` ) ко всем процессорам и принять m` как распространяемое сообщение.

Протокол византийского соглашения (BA-субпротокол). Введем следующее определение. При византийских соглашениях для любого начального входа x_i, i [1,...,n] участника i и некоторого параметра d (соглашения) должны быть выполнены следующие условия.

Условие завершения. Все честные участники вычислений в конце протокола принимают значение d.

Условие корректности. Если существует значение x такое, что для честных участников x_i=x, тогда d=x.

Обобщенные модели вычислений для сети синхронно и асинхронно взаимодействующих процессоров

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

В модели вводится дополнительный параметр t, t < n, - максимальное число участников, которые могут отклоняться от предписанных протоколом действий, то есть максимальное число злоумышленников. Поскольку злоумышленники могут действовать заодно, обычно предполагается, что против протокола действует один злоумышленник, который может захва-тить и контролировать любые t из n процессоров по своему выбору.

Модель сбоев и модель противника

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

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

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

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

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

Противник называется t-противником, если он сотрудничает с t процессорами.

Модель взаимодействия

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

Взаимодействие в сети характеризуется трафиком T, который может представлять собой совокупность сообщений, полученных участниками вычислений в r-том раунде в установленной модели взаимодействия.

Синхронная модель вычислений

Рассматривается сеть процессоров, функционирование которой синхронизируется общими часами (синхронизатором). Каждое локальное (внутреннее) вычисление соответствует одному моменту времени (одному такту часов). В данной модели отрезок времени между i и i+1 тактами называется раундом при синхронных вычислениях. За один раунд протокола каждый процессор может получать сообщения от любого другого процессора, выполнять локальные (внутренние) вычисления и посылать сообщения всем другим процессорам сети. Имеется входная лента "только-для-чтения", которая первоначально содержит строку Λ (k) (например вида 1^k), при этом k является параметром безопасности системы. Каждый процессор имеет ленту случайных значений, конфиденциальную рабочую ленту "только-для-чтения" (первоначально содержащую строку Λ), конфиденциальную входную ленту "только-для-чтения" (первоначально содержащую строку x_i), конфиденциальную выходную ленту "только-для-записи" (первоначально содержащую строку Λ) и несколько коммуникационных лент. Между каждой парой процессоров i и j существует конфиденциальный канал связи, посредством которого i посылает безопасным способом сообщение процессору j. Данный канал (коммуникационная лента) исключает запись для i и исключает чтение для j. Каждый процессор i имеет также широковещательный канал, представляющий собой ленту, исключающую запись для i и являющийся каналом "только-для-чтения" для всех остальных процессоров сети.

Предполагается, что в раунде r для каждого процессора i существует однозначно определенное сообщение (возможно пустое), которое распространяет процессор i в этом раунде и для каждой пары процессоров i и j существует единственное сообщение, которое i может безопасным образом послать j в данном раунде. Все каналы являются помеченными так, что каждый получатель сообщения может идентифицировать его отправителя.

Процессор i запускает программу π_i, совокупность которых, реализует распределенный алгоритм П. Протоколом работы сети называется n-элементный кортеж P=( π₁, π₂,.., π_n). Протокол называется t-устойчивым, если t процессоров являются сбоящими во время выполнения протокола. Историей процессора i являются: содержание его конфиденциального и общего входа, все распространяемые им сообщения, все сообщения, полученные i по конфиденциальным каналам связи, и все случайные параметрами, сгенерированные процессором i во время работы сети.

Идеальный и реальный сценарии

Для доказуемо конфиденциального вычисления вводятся понятия идеального и реального сценария [10]. В идеальном сценарии дополнительно вводится достоверный процессор (TP-процессор). Процессоры конфиденциально посылают свои входы ТР-процессору, который вычисляет необходимый результат (выход) и также конфиденциально посылает его обратно процессорам сети. Противник может манипулировать с этим результатом (вычислить или изменить его) следующим образом. До начала вычислений он может подкупить один из процессоров и изучить его секретный вход. Основываясь на этой информации, противник может подкупить второй процессор и изучить его секретный вход. Это продолжается до тех пор пока противник не получит всю необходимую для него информацию. Далее у противника есть два основных пути. Он может изменить входы нечестных процессоров. После чего те, вместе с корректными входами честных процессоров, направляют свои новые измененные входы ТР-процессору. По получению от последнего выходов (значения вычисленной функции) противник может приступить к изучению выхода каждого нече-стного процессора. Второй путь заключается в последовательном изучении входов и выходов процессоров, подключая их всякий раз к числу нечестных. В данном случае рассматривается противник, который не только может изучать входы нечестных процессоров, но и менять их, изучать по полученному значению функции входы честных процессоров.

В реальном сценарии не существует ТР-процессора, и все участники вычислений моделируют его поведение посредством выполнения многостороннего интерактивного протокола.

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

Асинхронная модель вычислений

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

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

Сценарий в асинхронной модели с ТР-участником заключается в добавлении ТР-процессора в существующую асинхронную сеть при наличии t потенциальных сбоев (сбоящих процессоров). При этом честные процессоры, также как и ТР-процессор не могут ожидать наличия более, чем n-t входов для вычислений с целью получения их выхода, так как t процессоров (сбоящие процессоры) могут никогда не присоединиться к вычислениям.

Асинхронный ТР-сценарий

В начале вычислений процессоры посылают свои входы ТР-процессору. В то же время, существует планировщик D, который доставляет сообщения участников некоторому базовому подмножеству процессоров, мощностью не меньше n-t, обозначаемому как C и являющемуся независимым от входов честных процессоров. ТР-процессор по получению входов - аргументов функции (возможно некорректных) из множества C, предопределенно оценивает значение вычисляемой функции, основываясь на C и входах участников из С. (Здесь для корректности может использоваться следующее предопределенное оценивание: установить входы из C в 0 и вычислить данную функцию). Затем ТР-процессор посылает значение оценочной функции обратно участникам совместно с базовым множеством С. Наконец честные процессоры вычислений выдают то, что они получили от ТР-участника. Нечестные у