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

Операнды многократной точности для данного алгоритма представляются в виде одномерного массива целых чисел. Для знака можно зарезервировать элемент с нулевым индексом. Особенности представления чисел при организации взаимодействия алгоритма с другими рабочими программами, при организации ввода-вывода и т.д. рассматриваются, например, в работе [Hu]. В алгоритме использован известный вычислительный метод «разделяй и властвуй» и реализован способ вычисления «цифра-за-цифрой». Прямое умножение не следует делать по нескольким причинам: во-первых, произведение A*B

требует в два раза больше памяти, чем при методе «цифра-за-цифрой»; во-вторых, умножение двух многоразрядных чисел труднее организовать, чем умножение числа многократной точности на число однократной точности. Так, в работе [BW] приводятся расчеты на супер-ЭВМ «CRAY-2» для 100-разрядных десятичных чисел: модулярное умножение методом «цифра-за-цифрой» выполняется примерно на 10% быстрее, чем прямое умножение и следующая за ним модульная редукция. Алгоритм модулярного умножения (алгоритм P) приведен на рис.2.2, а на рис.2.1 представлен псевдокод процедуры ADDK.

Алгоритм 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.1. Псевдокод алгоритма вычисления P+k*N

(процедура ADDK)

Так как B[i]Î[0,...,2l/2-1], то проверку «if B[i]<>0» в алгоритме P можно не вводить потому, что вероятность того, что B[i] будет равняться 0 пренебрежимо мала, если значение l

не достаточно мало. Ошибка затем все равно будет алгоритмом обнаружена. Проверка

«if p_short-k*n_short>n_short DIV 2»

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

Теорема 2.1.

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

Доказательство.

Доказательство теоремы проведем методом индукции.

Если k=abs(p_short) DIV n_short, где DIV - целочисленное деление, то

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

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

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

d>0.5                                                                               (2.1.7)

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

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

Алгоритм 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.2. Псевдокод алгоритма модулярного умножения A*B modulo N

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

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

abs(Pi)<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=d*N,                            если d£0.5                               (2.1.11)

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

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

Вариант B:

p_short>0                                                                        (2.1.13)

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

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

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

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

Во всех случаях (2.1.11), (2.1.12), (2.1.14) и (2.1.15), так как 0£d<1, то abs(Pi)<N.

Теорема доказана n.

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

«if p_short-k*n_short>n_short DIV 2» ?

Пусть в конце каждой итерации P

принимает максимально возможное значение Pi-1=N-1, а N, A и B[i] заведомо тоже велики: N=rn+1-1, A=rn+1-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*rn+2), по условию же m+1. Если же ввести проверку (2.1.7), то даже при d=0,5 т.е.

Pi-1=(N-1)/2 и с учетом того, что если неравенство (2.1.7) выполняется, то Pi

меняет знак на противоположный (сравн. (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

в работе [Кн, стр.291-295]). Чем больше основание системы счисления r, тем меньше вероятность того, что пробное частное k от деления первых цифр больших чисел не будет соответствовать действительному частному.

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

www.kiev-security.org.ua

BEST rus DOC FOR FULL SECURITY

Алгоритм маркирования

Алгоритм создания 2-3-дерева аутентификационных признаков (алгоритм маркирования) работает следующим образом.

Алгоритм САП2-3

1. Получить для каждого i, признак (a,F[i])АУТ=(T(w)), где w

– i-тый концевой узел.

2. Получить для каждого неконцевого узла w, признак (a,(L1,L2,L3),рзм)АУТ=(Т(w)), где Li

- метка i-того дочернего узла w (в случае, если w имеет только два дочерних узла, то L3=g) и рзм - число узлов в поддереве с корнем w).

3. Получить для корня дерева признак (a,(L1,L2,L3),Id,счт)АУТ=(Т(l)), где Id - название документа и счт – соответствующее показание счетчика (связанное с этим документом).

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

В основу алгоритмов приближенных вычислений ВХ положен принцип расчета ВХ по функциям распределения выходных и промежуточных величин. При этом законы их распределения вычисляются как распределения функции от случайных аргументов[ЕУ].

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

Дано: совместная плотность распределения вероятностей wn(x1,...,xn) непрерывных случайных величин e1,...,en

и совокупность функций f1,...,fm от n переменных. С помощью этих функций определены m случайных величин h1=f1(x1,...,xn),...,hm=fm(x1,...,xn), где xi – значения случайных величин ei.

Необходимо: определить закон распределения каждой полученной случайной величины hj и их совместную плотность Wm(y1,...,ym), где yi - значения случайных величин hj.

Решение этой задачи точными методами [КК] даже для одномерного случая возможно только при жестких ограничениях на вид функции и закон распределения аргумента. Например, применение метода обратной функции требует вычисления на каждом участке монотонности f(x) обратной функции и производной от обратной функции.

Вычисление W(y) методом характеристической функции [КК] ограничено таким набором w(x) и f(x), для которых можно вычислить характеристическую функцию в явном виде, а по характеристической функции вычислить W(y).

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

mk(h)=

...

f(x1,...,xn)kw(x1,...,xn) dx1...dxn

или для одномерного случая h=f(x)

mk(h)=

f(x)kw(x) dx

при условии, что этот интеграл сходится абсолютно [КК].

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

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

Алгоритм A

А1. i:=1.

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

и f(x)i-1=

, то bj=

.

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

.

А4. i:=i+1.

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

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

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

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

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

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

Алгоритм Б

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

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

.

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

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

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

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

.

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

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

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

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

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

Анализ алгоритма «Квадратного корня»

Как обсуждалось выше, последовательность фактических операций доступа к памяти забывающей RAM-машины действительно не открывает никакой информации относительно последовательности виртуальных операций доступа к памяти оригинальной RAM-машины. Это действительно так, потому что во время шагов 1, 2a, 2d и 3 фактическая модель доступа фиксирована, в то время как во время шагов 2b и 2c фактические модели доступа неразличимы и «случайны».

Теперь остается вычислить затраты на моделирование (т.е., отношение числа операций доступа, выполненных на забывающей RAM-машиной к числу оригинальных операций доступа). Далее мы вычисляем общее число фактических операций доступа, выполняемых на период (т.е., m+2

виртуальных операций доступа). Число фактических операций доступа на шаге 1 определено числом сравнений в сортирующей сети Батчера, а именно, O(mlog2m). То же самое делается на шаге 3. Что касается шага 2, каждая виртуальная операция доступа выполняется за 2

+log2(m+

)=O(

) фактических операций доступа. Это составляет амортизационные затраты O(log2m

). Фактически, вышеупомянутый выбор параметров (то есть, размер памяти зщт) не оптимален.

При использовании памяти зщт размера s, мы получаем амортизационные затраты

которые минимизированы установкой s=Q(logm

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

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

Количественная оценка сложности программы при помощи управляющего графа вычисляется [Лип0] как сумма V=e-n+2p, где e

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

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

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

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

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

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

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

Алгоритм А

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

А2. В графе программы ищется структурированная конструкция. Если такой нет, то выполняется переход к шагу А4.

А3. В дереве образуется вершина структурированной конструкции. Эта конструкция сворачивается в вершину, тип которой указывается. Выполняется переход к шагу А2.

А4. Если в графе осталась только одна вершина, то работа алгоритма заканчивается.

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

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

S(V(i)-1), где NS - множество вершин неструктурируемого типа в структурном дереве; V(i) - топологическая сложность конструкции, соответствующей i-й вершине дерева.

Вычисление V(i) производится на шаге А5 алгоритма по формуле V(i)=e(i)-n(i)+2, где e(i) - количество дуг, а n(i) - количество вершин рассматриваемой конструкции.

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

Анализ моделей надежности программ

В моделях Шумана и Джелинского-Моранды в качестве независимой переменной фигурируют время и надежность, вычисляемая по формуле R(t)=e-ht.

Значение интенсивности отказов h предполагается постоянным в течение всего периода функционирования системы и изменяется только при обнаружении и устранении ошибок, после чего время t снова отсчитывается от нуля. Поскольку эта формула может быть получена как частный случай рассматриваемой ниже модели Нельсона при некоторых допущениях целесообразно определить условия, при которых верны модели Шумана и Джелинского-Моранды. Эти условия таковы:

время t

должно интерпретироваться как суммарное время работы программы относительно некоторого определенного начального момента времени;

время t

должно быть больше средней длительности выполнения одного прогона программы Dt;

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

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

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

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

Анализ программ на этапе их эксплуатации

В данном разделе будут рассмотрены методы исследования программ нарушителем с помощью дизассемблеров и отладчиков на этапе эксплуатации программ с целью внесения в них РПС. То есть задача защиты в отличие от задач защиты, рассмотренных в предыдущем подразделе, здесь решается «с точностью до наоборот». Этот подраздел необходим для понимания процесса исследования программ, но не специалистами в области защиты ПО (см. главу7), которые пытаются обнаружить и устранить программные дефекты, а потенциальными нарушителями, которые пытаются внести в исследуемую программу РПС. Т.е. цель, объекты и субъекты обеспечения безопасности ПО здесь разные.

Основная схема анализа нарушителем исполняемого кода, в данном случае, может состоять из следующих этапов [ПБП]:

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

· лексический анализ;

· дизассемблирование;

· семантический анализ;

· перевод в форму, удобную для следующего этапа (в том числе и перевод на язык высокого уровня);

· синтаксический анализ.

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

www.kiev-security.org.ua

BEST rus DOC FOR FULL SECURITY

При синтаксическом анализе могут встретиться следующие трудности (хотя - это проблема нарушителя):

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

·     порядок следования лексем может быть известен с некоторой вероятностью или вообще не известен;

·     грамматика языка может пополняться, так как могут возникать новые типы РПС или механизмы их работы.

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

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

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

Аппроксимирующие функции

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

|P(x)-f(x)|£d. Это обозначается следующим образом: P(x)»df(x). Будем также считать, что Р(d,e) аппроксимирует функцию f на области D, если

|P-f|£d

на 1-e

элементах области D.

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

В таблице 4.3 показаны некоторые теоремы сложения для функциональных уравнений, где верна следующая форма f(x+y)=G[f(x),f(y)].

Таблица 4.3.

G[f(x),f(y)]		f(x)
f(x)+f(y)		Ax
		tg Ax
		ctg Ax


		A th Bx

f(x)f(y)-		cos Ax




f(x)f(y)+		ch Ax

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

Архитектура безопасности Взаимосвязи открытых систем

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

В 1986 г. рядом международных организаций была принята Архитектура безопасности ВОС (АБ ВОС). В архитектуре ВОС выделяют семь уровней иерархии: физический, канальный, сетевой, транспортный, сеансовый, представительный и прикладной. Однако в АБ ВОС предусмотрена реализация механизмов защиты в основном на пяти уровнях. Для защиты информации на физическом и канальном уровне обычно вводится такой механизм защиты, как линейное шифрование. Канальное шифрование обеспечивает закрытие физических каналов связи с помощью специальных шифраторов. Однако применение только канального шифрования не обеспечивает полного закрытия информации при ее передаче по сети, так как на узлах коммутации пакетов информация будет находиться в открытом виде. Поэтому НСД нарушителя к аппаратуре одного узла ведет к раскрытию всего потока сообщений, проходящих через этот узел. В том случае, когда устанавливается виртуальное соединение между двумя абонентами сети и коммуникации, в данном случае, проходят по незащищенным элементам сети, необходимо сквозное шифрование, когда закрывается информационная часть сообщения, а заголовки сообщений не шифруются. Это позволяет свободно управлять потоками зашифрованных сообщений. Сквозное шифрование организуется на сетевом и/или транспортном уровнях согласно ЭМ ВОС. На прикладном уровне реализуется большинство механизмов защиты, необходимых для полного решения проблем обеспечения безопасности данных в ИВС.

АБ ВОС устанавливает следующие службы безопасности (см. табл.15.1).

· обеспечения целостности данных (с установлением соединения, без установления соединения и для выборочных полей сообщений);

· обеспечения конфиденциальности данных (с установлением соединения, без установления соединения и для выборочных полей сообщений);

Таблица 15.1

Назначение службы	Номер службы	Процедура защиты	Номер уровня
Аутентификация: Одноуровневых объектов источника данных	1 2	Шифрование, цифровая подпись Обеспечение аутентификации Шифрование Цифровая подпись	3,4 3,4,7 3,4 3,4,7
Контроль доступа	3	Управление доступом	3,4,7
Засекречивание: соединения в режиме без соединения выборочных полей потока данных	4 5 6 7	Шифрование Управление трафиком Шифрование Управление трафиком Шифрование Шифрование Заполнение потока Управление трафиком	1-4,6,7 3 2-4,6,7 3 6,7 1,6 3,7 3
Обеспечение целостности: соединения с восстановлением соединения без восстановления выборочных полей без установления соединения выборочных полей без соединения	8 9 10 11 12	Шифрование, обеспечение целостности данных Шифрование, обеспечение целостности данных Шифрование, обеспечение целостности данных Шифрование Цифровая подпись Обеспечение целостности данных Шифрование Цифровая подпись Обеспечение целостности данных	4,7 3,4,7 7 3,4,7 4 3,4,7 7 4,7 7
Обеспечение невозможности отказа от факта: отправки доставки	13 14	Цифровая подпись, обеспечение целостности данных, подтверждение характеристик данных Цифровая подпись, обеспечение целостности данных, подтверждение характеристик данных	7 7

·        контроля доступа;

·        аутентификации (одноуровневых объектов и источника данных);

·        обеспечения конфиденциальности трафика;

·        обеспечения невозможности отказа от факта отправки сообщения абонентом - передатчиком и приема сообщения абонентом - приемником.

АБ ВОС устанавливает следующие службы безопасности (см. табл.15.1).

·        обеспечения целостности данных (с установлением соединения, без установления соединения и для выборочных полей сообщений);

·        обеспечения конфиденциальности данных (с установлением соединения, без установления соединения и для выборочных полей сообщений);

Таблица 15.1

Назначение службы	Номер службы	Процедура защиты	Номер уровня
Аутентификация: Одноуровневых объектов источника данных	1 2	Шифрование, цифровая подпись Обеспечение аутентификации Шифрование Цифровая подпись	3,4 3,4,7 3,4 3,4,7
Контроль доступа	3	Управление доступом	3,4,7
Засекречивание: соединения в режиме без соединения выборочных полей потока данных	4 5 6 7	Шифрование Управление трафиком Шифрование Управление трафиком Шифрование Шифрование Заполнение потока Управление трафиком	1-4,6,7 3 2-4,6,7 3 6,7 1,6 3,7 3
Обеспечение целостности: соединения с восстановлением соединения без восстановления выборочных полей без установления соединения выборочных полей без соединения	8 9 10 11 12	Шифрование, обеспечение целостности данных Шифрование, обеспечение целостности данных Шифрование, обеспечение целостности данных Шифрование Цифровая подпись Обеспечение целостности данных Шифрование Цифровая подпись Обеспечение целостности данных	4,7 3,4,7 7 3,4,7 4 3,4,7 7 4,7 7
Обеспечение невозможности отказа от факта: отправки доставки	13 14	Цифровая подпись, обеспечение целостности данных, подтверждение характеристик данных Цифровая подпись, обеспечение целостности данных, подтверждение характеристик данных	7 7

Асинхронная схема глобального проверяемого разделения секрета

Протокол асинхронного глобального проверяемого разделения секрета, обозначаемый как АГРз, состоит из двух этапов. Сначала, каждый процессор делит секрет среди других процессоров, а затем процессоры используют протокол СОАМ, чтобы договориться о множестве С размером не менее чем из n-t процессоров, которые успешно разделили свои секреты. Выход процессора Pi в протоколе АГРз

– это множество процессоров, которые успешно разделили свои входы, вместе с i-той долей входа каждого процессора в этом множестве. Протокол АГРз

имеет параметр безопасности d. Исходя из контекста, этот параметр будет устанавливаться либо в t, либо в 2t.

Протокол АГРз

Код для процессора Pi по входу xi, d.

1. Осуществить разделение xi:

1.1. Выбрать случайным образом полином hi(·) степени d такой, что hi(0)=xi.

1.2. Для каждого 1£j£n

послать hi(j) процессору Pj.

1.3. Разослать сообщение «Сторона Pi завершила разделение».

2. После получения доли si,j секрета процессора Pj и сообщения «Сторона Pj завершила разделение» добавить j к множеству Ci процессоров, которые успешно разделили свои секреты. Установить (n,t,Ci)СОАМ=С.

3. Подать на выход C и {si,j½jÎC}.

Необходимо отметить, что аккумулируемые множества C1,...,Cn на шаге 2 определяют (n-t,t)-однородную коллекцию. Таким образом, все несбоящие процессоры завершают протокол СОАМ

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

В протоколе АГВс, описываемом ниже процессоры восстанавливают секрет из долей. Параметры этого протокола – параметр безопасности d и множество R процессоров, для которого секрет может быть вскрыт. Вход процессора Pi является i-той долей секрета, обозначаемой как si.

Протокол АГВс

Код для процессора Pi по входу si и параметрам dÎ{t,2t} и RÍ{P1,...,Pn}.

1. Послать si всем процессорам из R.

2. Если процессор PiÏR, подать на выход 0. В противном случае после получения d+1 значений (значение vj

от процессора Pj) интерполировать полином pi(·) степени d такой, что p(j)=vj

для каждого полученного значения vj. Подать на выход pi(0).

Асинхронная схема глобального проверяемого разделения секрета (АГПРС), описанная ниже, является обобщением предыдущей схемы для случая By-сбоев. Схема состоит из двух этапов: сначала, каждый процессор разделяет вход, используя протокол АРзПр схемы АПРС, а затем процессоры используют субпротокол СОАМ для того, чтобы договориться о множестве C не менее чем n-t процессорами, которые объединили свои входы. Выход процессора Pi

в субпротоколе АГПРС и есть это множество C и i-тая доля каждого секрета включена процессором Pi

в C. В данном протоколе параметр безопасности фиксирован: d=t.

Субпротокол АГПРС

Код для процессора Pi по входу xi.

1. Инициировать АРзПр(xi) с Pi в качестве дилера. Для 1£j£n

участвовать в протоколе в АРзПрj. Пусть vj – есть выход АРзПрj.

2. Пусть Ui={j½АРзПрj был завершен}. Множество C вычислить как: (n,t,Ui)СОАМ=С.

3. Как только множество C вычислено, подать на выход (C,vj½jÎC).

Асинхронные идеальный и реальный сценарии

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

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

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

и входах процессоров из С. (Здесь для корректности может использоваться следующее предопределенное оценивание: установить входы из C

в 0 и вычислить данную функцию). Затем доверенный процессор посылает значение оценочной функции обратно процессорам совместно с базовым множеством С. Наконец несбоящие процессоры выдают то, что они получили от доверенного процессора. Сбоящие процессоры выдают значение некоторой независимой функции, информацию о которой они «собирали» в процессе вычислений. Эта информация может состоять из их собственных входов, случайных значений, используемых при вычислениях и значения оценочной функции.

Так же как и в синхронной модели, вычисления в реальной асинхронной модели безопасны, если эти вычисления «эквивалентны» вычислениям в сценарии с доверенным процессором.

Далее в соответствии с работой [BCG] сделаем попытку формализовать понятия полноты и безопасности протокола асинхронных конфиденциальных вычислений.

Базовые примитивы

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

Безопасность

Свойство инкрементальности вводит новые проблемы безопасности [Ва3], а, следовательно, «назревает» необходимость новых определений. Рассмотрим случай схем подписи или аутентификации сообщений. Разумно предположить, что противник не только имеет доступ к предыдущим подписанным версиям фалов, но также способен выдавать команды на модификацию текста в существующих файлах и получать инкрементальные подписи для измененных файлов. Такая атака на основе выбранного сообщения (см. приложение) для инкрементальных алгоритмов подписи может вести к «взлому» используемой оригинальной схемы подписи, которая не может быть взломана при проведении противником атак, когда инкрементальные алгоритмы не используются. Кроме того, в некоторых сценариях, например, при вирусных атаках можно предположить, что противник может вмешиваться не только в содержание существующих документов, но и в соответствующие аутентификационные признаки, полученные посредством применения схемы подписи (или схемы аутентификации сообщений). Соответственно рассматриваются два определения безопасности: базовое, когда необходимо противостоять первому вышеописанному противнику, и более сильное понятие безопасности, когда доказывается стойкость защиты от вмешательств.

Безопасность асинхронных вычислений

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

Для вектора

и множества CÍ[n]@{1,...,n}, пусть

определяет вектор

, спроектированный на индексы из C. Для подмножества BÍ[n] и вектора

, пусть

определяет вектор, полученный из

подстановкой входов из B соответствующими входами из

. Используя эти определения, можно определить оценочную функцию f с базовым множеством CÍ[n] как

Пусть A – область возможных входов процессоров и пусть R

– область случайных входов. ТР-противник

это кортеж А=(B,h,c,O), где BÍ[n] – множество сбоящих процессоров, h:AïBï´R®AïBï - функция подстановки входов, с:AïBï´R®{CÍ[n]½ôCô³n-t} – функция выбора базового множества и O:AïBï´R´A®{0,1}* - функция выхода для сбоящих процессоров.

Функции h

и O представляют собой программы сбоящих процессоров, а функция c – комбинацию планировщика и программ сбоящих процессоров.

Пусть f:An®A для некоторой области A. Выход функции вычисления f в ТР-сценарии по входу

и с ТР-противником А=(B,h,c,O) – это

n-размерный вектор

...

случайных переменных, удовлетворяющих для каждого 1£i£n:

где r - объединенный случайный вход сбоящих процессоров, C=

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

Далее формализуем понятие вычисления «в реальной жизни».

1. Пусть B=(B,b) – коалиция нечестных процессоров, где BÌ[n] – множество нечестных процессоров и b

- их совместная стратегия.

2. Пусть pi(

,B,D) определяет выход процессора Pi

после выполнения протокола pi по входу

, с планировщиком D и коалиции B. Пусть также P(

,B,D)=p1(

,B,D)...pn(

,B,D).

Кроме того, пусть f:An®A для некоторой области A и пусть P

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

Условие завершения (условие полноты).

По всем входам все честные процессоры завершают протокол с вероятностью 1.

Условие безопасности. Существует ТР-противник A такой, что для каждого входа

векторы t(

,A) и P(

,B,D) идентично распределены (эквивалентны).

Безопасные протоколы для получестной модели

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

Сначала определяется соответствующее понятие редукции

и показывается, как получить протокол для конфиденциального вычисления функцииg по данной редукции (конфиденциально вычислимой) функции g к (конфиденциально вычислимой) функции f

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

Затем, без потери общности, рассматриваются булевы схемы с логическими вентилями and и xor с коэффициентом объединения по входу равным 2. В общем случае можно представить следующий сценарий. Первый процессор «содержит» параметры a1,b1, а второй процессор - a2,b2, где a1+a2 - значение одной входной линии и b1+b2 - значение другой входной линии. Необходимо обеспечить каждый из процессоров «случайной» долей значения выходной линии, то есть долей значения (a1+a2)·(b1+b2). Другими словами нас интересует конфиденциальное вычисление следующей рандомизированной вычислимой функции:

((a1,b1),(a2,b2))®(c1,c2), (3.1)

где c1+c2=(a1+a2) ·(b1+b2). (3.2)

То есть значения (с1,с2) равномерно выбраны среди всех решений c1+c2=(a1+a2)·(b1+b2). Вышеупомянутая вычислимая функция имеет конечную область значений и может быть вычислена (в общем случае) сведением к одному из вариантов забывающего обмена (OT). Ниже показывается, как это может быть сделано при условии существования односторонней перестановки с секретом (см. Приложение).

Целочисленная арифметика и арифметика многократной точности

Пусть M(n) – время выполнения программы P на входе размером n. В работе [BLR] были разработаны программные чекеры для функций, представленных в таблице 4.1. Там же приведены ресурсозатраты на выполнение самотестирующейся/ самокорректирующейся программной пары для указанных целочисленных (в том числе модулярных с операндами многократной точности) функций. Во второй колонке показано время выполнения самотестирующейся/ самокорректирующейся программной пары без учета времени вызова программы, реализующей функции, приведенные в первой колонке. В третьей колонке приведено общее время выполнения с учетом времени вызовов программы P. В это время не включается время выполнения программ реализации функций, зависящее от параметра безопасности k, который обычно составляет O(log(1/k)).

Таблица 4.1.

Центральный процессор, имитирующий взаимодействие

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

противник экспериментирует с оригинальным защищенным центральным процессором, который пытается выполнить зашифрованную программу, используя память;

противник экспериментирует с «поддельным» (фальсифицированным) центральным процессором.

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

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

Чекер для задачи «Изоморфизм графа»

Пусть G и H – два графа и k

– некоторый параметр безопасности. Чекер CGIP(G,H,k) проверяет программу P

на входных графах G и H. На выходе чекера будет результат «Норма», если графы изоморфны и «Сбой», если неизоморфны.

Следующая теорема [BK] определяет эффективность и корректность чекера для решения задачи «ИЗОМОРФИЗМ ГРАФОВ» - IG.

Пусть P – программа, которая останавливается на всех входах и всегда выдает либо «Норма», либо «Сбой». Пусть также G и H - два любых графа и пусть CGIP(G,H;k) – вышеуказанный чекер.

Теорема 4.1. Если P корректная программа для решения задачи IG, тогда чекер CGIP(G,H;k) всегда выдаст на выходе «Норма». Если P - некорректна, т.е. P(G,H)GI(G,H), тогда вероятность Prob{CGIP(G,H;k)=«Норма»}<1/2k.

Доказательство.

Достаточно очевидно и приведено в работе [BK].

Интерактивные системы доказательств и интерактивные системы доказательств с нулевым разглашением [Ва1,Ва2] могут эффективно применяться в системах защиты информации от несанкционированного доступа, например, в схемах интерактивной идентификации пользователей системы [Ка14,КУ4,КУ6]. В целом интерактивный протокол доказательств для задачи IG

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

Чекер CGIP(G,H,k)

1. Вычислить P(G,H).

2. Если P(G,H)=«Изоморфизм», тогда использовать P для поиска изоморфизма их G в H. Проверить, является ли результирующее соответствие изоморфизмом. Если нет, тогда подать на выход «Сбой», если является, тогда подать на выход «Норма».

3. Если P(G,H)=«Не изоморфизм», тогда выполнить следующие шаги k раз.

3.1. Выработать случайный бит b.

3.2. Если b=1, тогда

3.2.1. Сгенерировать случайную перестановку G¢

графа G.

3.2.2. Вычислить P(G,G¢).

3.2.3. Если P(G,G¢)=«Не изоморфизм», тогда подать на выход «Сбой».

3.3. Если b=0, тогда

3.3.1. Сгенерировать случайную перестановку H¢

графа H.

3.3.2 Вычислить P(G,H¢).

3.4. Если P(G,H¢)=«Изоморфизм», тогда подать на выход «Сбой».

4. Подать на выход «Норма».

Человеческий фактор

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

С некоторой степенью условности злоумышленников в данном случае можно разделить на два основных класса:

злоумышленники-любители (будем называть их хакерами);

· злоумышленники-профессионалы.

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

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

Хакеры и группы хакеров

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

www.kiev-security.org.ua

BEST rus DOC FOR FULL SECURITY

Существуют несколько типов хакеров. Это хакеры, которые:

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

·     получают удовольствие, оставляя явный след того, что он проник в систему;

·     желают воспользоваться оборудованием, к которому ему запрещен доступ;

·     охотятся за конфиденциальной информацией;

·     собираются модифицировать определенный элемент данных, например баланс банка, криминальную запись или экзаменационные оценки;

·     пытаются нанести ущерб «вскрытой» (обезоруженной) системе.

Группы хакеров, с некоторой степенью условности, можно разделить на следующие:

·     группы хакеров, которые «получают удовольствие» от вторжения и исследования больших ЭВМ, которые используются в различных государственных учреждениях;

·     группы хакеров, которые специализируются на телефонной системе;

·     группы хакеров - коллекционеров кодов, - это хакеры, запускающие перехватчики кода, которые ищут карты вызовов (calling card) и номера PBX (private branch exchange - частная телефонная станция с выходом в общую сеть);

·     группы хакеров, которые специализируются на операциях в финансово-кредитной сфере (Они используют компьютеры для кражи денег, вычисления номеров кредитных карточек и другой ценной информации, а затем продают свои услуги и методы другим, включая членов организованных преступных группировок. Эти хакеры могут скупать у коллекционеров кодов номера PBX и продавать их за 200-500$, и подобно другим видам информации неоднократно. Архивы кредитных бюро, информационные срезы баз данных уголовных архивов правоохранительных органов и баз данных других государственных учреждений также представляют для них большой интерес. Хакеры в этих группах, как правило, не находят взаимопонимания с другими хакерами);

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

Действия процессоров в злонамеренной модели

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

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

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

· процессоры подменяют свои локальные входы (и могут участвовать в протоколе с входами других процессоров);

· процессоры преждевременно прерывают протокол (например, перед посылкой своего последнего сообщения).

Доказательство безопасности схемы АПРС

Теорема3.7. Пара протоколов (АРзПр, АВсПр) является t-устойчивой схемой АПРС в сети из n процессоров, если n³4t+1.

Доказательство.

Из определения 3.6 видно, что нам необходимо доказать условия завершения, корректности и конфиденциальности. Начнем с доказательства корректности схемы АПРС.

Корректность. С каждым несбоящим процессором Pi, который завершает протокол АРзПр мы ассоциируем уникальный полином hi(·,·) степени t от двух переменных и показываем, что каждые два несбоящих процессора Pi

и Pj имеют hi(·,·)=hj(·,·). Затем, мы показываем, что условия 1 и 2 корректности выполняются, относительно r=hi(0,0) (для некоторого несбоящего процессора Pi). Кроме того, мы показываем, что выход процессора Pi протокола АРзПр есть hi(i,0).

Для демонстрации этого мы используем две технических леммы, которые приведем без доказательства [BCG]. В лемме 3.5 показывается, что если 4t+1 долей несбоящих процессоров, находящихся в звезде в графе ОK

определяют единственный полином степени t от двух переменных. Лемма 3.6 демонстрирует тот факт, что полиномы индуцированные звездами каждой из двух процессоров одинаковы. Таким образом, только несбоящий процессор находит звезду, и, следовательно, секрет определяется единственным образом.

Лемма 3.5.

Пусть m³d+1, и пусть f1(·),...,fm(·) и g1(·),...,gm(·) - полиномы степени d над полем F с |F|³m

такие, что для каждого 1£i£d+1 и каждого 1£j£m мы имеем fi(j)=gj(i) и gi(j)=fj(i). Тогда существует единственный полином h(·,·) степени d от двух переменных такой, что для каждого 1£i£m мы имеем h(·,i)=fi(·) и h(i,·)=gi(·).

Лемма 3.6.

Пусть h(·,·), h¢(·,·) – два полинома степени d от двух переменных над полем F с |F|³d и пусть v1,...,vd+1 - различные элементы в F. Предположим, что для каждого 1£i,j£d+1 мы имеем h(vi,vj)=h¢(vi,vj). Тогда h(·,·)=h¢(·,·).

Далее, пусть Pi – несбоящий процессор, который завершил протокол АРзПр и пусть (Ci,Di) - звезда, найденная процессором Pi. Пусть Di¢ - множество несбоящих процессоров в Di пусть Ci¢ - множество несбоящих процессоров в Ci и, таким образом, |Di¢|³|Di|-t³n-2t и |Ci¢|³|Ci|-t³n-3t³t+1 (так как 4t+1). В соответствии с леммой 3.5 полиномы fj(·),gj(·) процессоров jÎDi¢ определяют единственный полином степени t от двух переменных. Пусть hi(·,·) обозначает этот полином. А именно, hi(·,·) - полином, ассоциированный с Pi. Отметим также, что hi(·,·) фиксирован, как только Pi завершает протокол АРзПр. Для каждого другого несбоящего процессора Pj

пусть Ii,j - множество несбоящих процессоров из DiÇDj. Так как n³4t+1, мы имеем |DiÇDj|n-2t³2t+1 и, таким образом, |Ii,j|³t+1. Для каждых двух процессоров k,lÎIi,j, мы имеем hi(k,l)=vk,l=hj(k,l), где vk,l – верификационная часть, посланная Pk к Pl на шаге 2 протокола АРзПр. Применяя результаты леммы 3.6, мы имеем hi(·,·)=hj(·,·). Значение r, требуемое в условии корректности, является равным hi(0,0).

Мы утверждаем, что условие 1 (а именно, что если дилер честен и выдает значение s, то r=s). Если дилер честен и он выбрал полином h(·,·) на шаге 1, тогда для каждых двух процессоров Pk,PlÎDi¢ мы имеем hi(k,l)=h(k,l). В соответствии с леммой 3.6 мы снова можем получить hi(·,·)=h(·,·). Далее нижний индекс в полиноме h(·,·) опускается.

Далее мы показываем, что выход каждого несбоящего процессора Pi протокола АРзПр есть h(i,0). Полином h(i,·) - интерполируемый полином аккумулируемого множества Ui процессора Pi на шаге 6. Следовательно, выход процедуры СКОП на шаге 6 будет h(i,·) и выход протокола АРзПр будет h(i,0).

В заключение мы показываем, как выполняется условие 2 (а именно, что выход Pi протокола АВсПр есть r).

Каждый несбоящий процессор Pj распространяет h(j,0) на шаге 7 и, таким образом, h(·,0) - интерполируемый полином аккумулируемого множества Ui

процессора Pi на шаге 8. Следовательно, выход процедуры СКОП на шаге 8 будет h(·,0) и выход протокола АВсПр будет h(0,0)=r.

Завершение. Условие 1. Если дилер честен, то для каждых двух несбоящих процессоров Pj и Pk, оба сообщения (ОК,j,k) и (ОК,k,j) будут распространены так как fj(k)=h(k,j)=gk(j) и gj(k)=h(j,k)=fk(j). Таким образом, каждый несбоящий процессор Pi будет в конечном счете иметь клику размера n-t в графе OKi. Поэтому процедура ЗВЗ будет находить звезду в OKi и шаг 4 будет завершен. Шаг 6 будет завершен, так как вход процедуры СКОП (а именно, аккумулируемое множество Ui, которое базируется на звезде, найденной на шагах 4 или 5) - событийно (t,t)-интерполируем.

Условие 2. Пусть Pi – несбоящий процессор, который завершил протокол АРзПр и пусть (Ci,Di) - звезда, найденная процессором Pi. Тогда (Ci,Di) будет в конечном счете звездой в графе OKj для каждого несбоящего процессора Pj, даже если Pj не завершил протокол АРзПр. Кроме того, процессор Pj получит (Ci,Di) сообщение (посланное Pi на шаге 4), и будет проверять на шаге 5, что множества (Ci,Di) формируют звезду в OKj. После нахождения звезды процессор Pj

выполнит шаг 6 и завершит протокол АРзПр.

Условие 3. Если все несбоящие процессоры начали выполнять протокол АВсПр, тогда аккумулируемое множество Si на шаге 8 для каждого несбоящего процессора Pi, событийно (t,t)-интерполируемо. Таким образом, все несбоящие процессоры завершат процедуру СКОП и протокол АВсПр.

Конфиденциальность. Мы используем следующую систему обозначения. Для значения v пусть Hv

обозначает множество полиномов степени t

от двух переменных со свободным коэффициентом v. Будем говорить, что последовательность f1(·),...,ft(·), g1(·),...,gt(·) полиномов чередуемы, если для каждых 1£i,j£t мы имеем fi(j)=gj(i).

Пусть I обозначает множество чередуемых последовательностей 2t полиномов степени t.

Лемма 3.7.

Пусть F – поле с |F|³d

и пусть sÎF. Тогда для каждой чередуемой последовательности f1(·),...,fd(·), g1(·),...,gd(·) в I существует единственный полином h(·,·)ÎHs такой, что для каждого 1£i£d мы имеем h(·,i)=fi(·) и h(i,·)=gi(·).

Доказательство.

См. работу [BCG].

Далее предположим, что дилер честен и пусть s

– разделяемое значение. Тогда дилер имеет на шаге 1 протокола АРзПр полином h(·,·) с равномерным распределением вероятностей над Hs. Кроме того, вся необходимая информация о множестве из t

процессоров, полученная во время выполнения протокола АРзПр, является чередуемой последовательностью f1(·),...,ft(·), g1(·),...,gt(·) в I такой, что для каждого 1£i£t мы имеем h(·,i)=fi(·) и h(i,·)=gi(·).

Из леммы 3.7 следует, что для каждого разделяемого значения sÎF это соответствие между полиномами в Hs и чередуемыми последовательностями в I

– является взаимнооднозначным. Следовательно, равномерное распределение над полиномами из Hs индуцирует равномерное распределение вероятностей над чередуемыми последовательностями в I. <

Доказательство безопасности схемы проверяемого разделения секрета

Теорема 3.1.

Схема ПРСК является (n/3-1)-устойчивой.

Доказательство. Пусть

g((w1,...,wn-1,s

r),(

,...,

))=((s1,...,sn-1,wn),(

,...,

))

h((s1,...,sn-1,wn),(

,...,

))=((s,s,...,s,wn),(

,...,

)),

где si=f0(i), f0(x)=s+a1x+...+at+1xt+1 и r=a1

....

(то есть полином, созданный, с использованием случайного параметра r дилера Д).

При рассмотрении протокола РзПр

напомним, что ti – трафик процессора Pi. Ясно, что для всех процессоров Pi, i£n, функция входа всегда возвращает пустую строку Ii(ti)=e, так как процессоры не вносят никакие входы в процессе вычисления функции g. Для дилера Д, Д=Pn+1, функция входа немного сложнее. Пусть mi

- сообщение, которое дилер распространяет процессору Pi в 5-м раунде, если Pi сообщил об ошибке в 4-м раунде или сообщение, которое дилер послал процессору Pi в 1-м раунде, если Pi не заявлял об ошибке. Тогда ID(tD)=f(0), где f=BW(m1,...,mn) – полином степени t+1, следующий из интерполяции Берлекампа-Велча. Функция выхода более простая: Oi(ti)=mi, где mD=e.

При рассмотрении протокола ВсПр, определим вход и выход функции g. Функция входа Ii для процессора Pi определена как следующая: пусть mi,j – сообщение, посланное процессором Pi

процессору Pj

в 1-м раунде; Ii(ti)=hi(0), где hi=BW(mi,1,...,mi,n) - многочлен степени t+1, следующий из интерполяции Берлекампа-Велча. Если такого полинома не существует, то Ii(ti)=0. Функция выхода следующая: пусть Mi – сообщение, распространяемая процессором Pi в раунде 9; Oi(ti)=F(0)=s, где F=BW(M1,...,Mn) – полином степени t+1, следующий из интерполяции Берлекампа-Велча.

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

Полнота. Если дилер Д - честный, исходя из свойств схемы ПРСК, любой несбоящий процессор может восстановить секрет s с вероятностью 1, так как посредством определенных выше функций g и h

g((w1,...,wn-1,s

r),(

,...,

))=((s1,...,sn-1,wn),(

,...,

)),

h((s1,...,sn-1,wn),(

,...,

))=((s,s,...,s,wn),(

,...,

))

реализуется

f(w1,...,wn-1,s)=((s,s,...,s,wn),(

,...,

)).

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

Лемма 3.1. Пусть функция g имеет вид

g((w1,...,wn-1,s

r),(

,...,

))=((s1,...,sn-1,wn),(

,...,

)).

Тогда g корректно вычисляет доли секрета s1,...,sn-1.

Доказательство. Сначала мы должны доказать, что для всех несбоящих процессоров Pi, значение Ii(ti) равно корректному входу. Если дилер Д - честный, то mi=f(i), где f - многочлен степени t+1 со свободным членом s

(секретом). Таким образом, ID(tD)=s, если дилер честный. Второе условие корректности состоит в том, что с высокой вероятностью должно выполняться O(t)=g(I(t)). В нашем случае это означает, что с высокой вероятностью значения mi, находящиеся у несбоящих процессоров, должны предназначаться для единственного полинома степени t+1. Это справедливо с вероятностью ³

, где не менее

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

Лемма 3.2. Пусть функция h имеет вид

h((s1,...,sn-1),(

,...,

))=((s,s,...,s,wn),(

,...,

)).

Тогда h корректно восстанавливает секрет s.

Доказательство. Понятно, что для всех несбоящих процессоров Ii(ti)=si – корректная доля входа. В этом случае необходимо проверить, что с высокой вероятностью O(t)=h(I,t), а это означает, что необходимо доказать, что

h((s1,...,sn-1),(

,...,

))=((s,s,...,s,e),(

,...,

)).

Это равенство не выполняется, если:

· любой сбоящий процессор Pl «преуспевает» в получении случайного «мусора» вместо значений pl(j) в раунде 2 (в этом случае, сообщения Mi не будут интерполировать полином);

· процессор Pi распределяет pl(j) в раунде 2 и использует полином со свободным членом, отличным от нуля (в этом случае, Mi

восстановит другой секрет).

Так как мы уже знаем, что Pl «преуспевает» в любом из двух описанных случаев с вероятностью

, то, следовательно, имеется не более, чем n/3 сбоящих процессоров и вероятность того, что протокол вычисляет неправильный выход не более, чем n/3(

), что для достаточного большого K, является экспоненциально малым.

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

Лемма 3.3. Пусть функция g имеет вид g((w1,...,wn-1,s

r),(

,...,

))=

=((s1,...,sn-1,wn),(

,...,

)).

Тогда g конфиденциально вычислима в отношение долей секрета s1,...,sn-1.

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

Необходимо рассмотреть два случая.

Случай A:

Дилер нечестен до начала 1-ого раунда. Моделирующее устройство будет следовать только командам процессоров с единственным исключением, что оно будет «передавать» их в какое-либо время противнику в случае «сговора». Так как процессоры не сотрудничают по любому входу, то это сводит моделирование к работе схемы проверяемого разделения секрета с нечестным дилером. Так что моделирование будет неразличимо с точки зрения противника.

Случай B:

Дилер честен до начала 1-ого раунда. Моделирующее устройство в 1-м раунде будет создавать случайный «ложный» секрет s'

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

Если дилер нечестен после

1-ого раунда противник и моделирующее устройство получит из оракула истинный вход s дилера. В этом случае моделирующее устройство передает управление от дилера к противнику и меняет полином, используемый для разделения на новый полином f" такой, что f"(0)=s и f"(i)=f'(i) для всех процессоров Pi, которые были «подкуплены» противником. Изменения моделирующего устройства в соответствии со случайным полиномом fi, используемым для доказательств с нулевым разглашением (см, например, [Ка14,КУ4] и приложение) делает их совместимыми с любым широковещательным каналом. Моделирующее устройство может всегда сделать это, так как противник имеет не более t точек полинома степени t+1. Далее моделирующее устройство использует полином f"

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

Лемма 3.4. Пусть функция h имеет вид

h((s1,...,sn-1),(

,...,

))=((s,s,...,s,wn),(

,...,

)).

Тогда h конфиденциально вычислима в отношение секрета s.

Доказательство. Работа моделирующего устройства M

сводится к следующему.

Описание работы моделирующего устройства M

1. В раунде 1, M

моделирует процессор Pi, выбирая случайный полином h'i степени t+1 и посылает h'i(j) к Pj. В этом месте моделирующему устройству позволено получить из оракула выход функции, так что M будет изучать истинный секрет s. Если такой процессор является «подкупленным» противником Прот в конце этого раунда (или в следующих раундах), то и M, и Прот узнают истинную долю sl и M должен изменить полином h'l в соответствии с тем, что h'l(0)=sl, но без изменения значения в точках, уже известных противнику.

Моделирующее устройство M

может всегда cделать это, потому что противник имеет не более t точек полинома степени t+1.

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

10.                 Моделирующее устройство M выбирает полином g степени t+1 такой, что g(0)=s и затем для каждого процессора Pi, устройство M

распространяет g(i)+pi(i)+...+pn(i), где pj - полином, распределенный процессором Pj

в течение раундов 2-8 моделирования. Интерполяция Рида-Соломона этих значений даст как результат секрет s. Если процессор Pl является сбоящим в конце этого раунда, тогда и M, и Прот узнают из оракула истинную долю входа sl. Если sl¹g(l), тогда M только изменит значение pl в точке l так, чтобы сделать полную сумму соответствующей такой широковещательной передаче.

Моделирование неотличимо от реального выполнения с точки зрения противника. Фактически, в раундах 2-8 все сообщения случайны и не связаны с входом, так что моделирующее устройство может легко играть роль несбоящих процессоров. В раунде 1 противник просматривает не более t долей реального входа несбоящих процессоров. В соответствии со свойствами схемы разделения секрета Шамира, эти доли полностью случайны и, таким образом, могут моделироваться даже без знания реального входа (как и в случае с моделирующим устройством). В раунде 9 реальная доля распространена «скрытым образом» как случайный «мусор», а это позволит моделирующему устройству распространять сообщение несбоящих процессоров с необходимым распределением даже без знания реального входа.       -

С доказательством лемм 3.1 – 3.4 доказательство теоремы 3.1 следует считать законченным.               -

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

Дополнения к базовой модели и вероятностные RAM-машины

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

Определение 5.2. Для каждого kÎN определим оракульный

CPUk как CPUk с двумя дополнительными лентами, названными оракульными лентами. Одна из этих лент является «только-для-чтения», а другая «только-для-записи». Всякий раз, когда машина входит в специальное состояние вызова оракула, содержимое оракульной ленты «только-для-чтения» изменяется мгновенно (т.е., за единственный шаг) и машина переходит к другому специальному состоянию. Строка, записанная на оракульной ленте «только-для-записи» между двумя вызовами оракула называется запросом, соответствующим последнему вызову. Будем считать, что CPUk имеет доступ к функции f, если делается запрос q и оракул отвечает и изменяет содержимое оракульной ленты «только-для-чтения» на f(q). Вероятностная

машина CPUk – это оракульная машина CPUk с доступом к однородно выбранной функции f:{0,1}O(k) ®{0,1}.

Определение 5.3. Для каждого kÎN определим оракульную RAMk-машину

как RAMk-машину, в которой машина CPUk

заменена на оракульную CPUk. Скажем, что эта RAMk-машина имеет доступ к функции f, если CPUk имеет доступ к функции f и будем обозначать как

. Вероятностная RAMk-машина – это RAMk-машина, в которой машина CPUk заменена вероятностной CPUk. (Другими словами, вероятностная RAMk-машина – это оракульная RAMk-машина с доступом к однородно выбранной функции).

Другие модели надежности программного обеспечения

Модели Джелинского-Моранды и Шика-Волвертона могут быть обобщены, если допустить возможность возникновения на рассматриваемом интервале более одной ошибки и считать, что исправление ошибок производится лишь после истечения интервала времени, на котором они возникли.

В модели Вейса[ТЛН] помимо предположения об экспоненциальном распределении интервала времени между отказами считается, что существует M причин возможных отказов в начале процесса разработки программного обеспечения. Таким образом, рассмотренная модель может быть полезной для оценки надежности ПО, если принять предположение, что каждая из М причин (источников) отказов представляет собой ошибки некоторого типа, многократно встречающиеся в ПО, например «недостаточен выделенный объем памяти для массива данных».

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

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

Модели, предложенные Коркореном и др. [ТЛН] заслуживают внимания по следующим причинам. Во-первых, они содержат изменяющиеся вероятности отказов для различных источников ошибок и соответственно разные вероятности их исправления. Во-вторых, они относительно просты с математической точки зрения и допускают простую интерпретацию данных об ошибках в ПО. В этих моделях не используется такой параметр, как время тестирования, а учитывается только результат N испытаний, в которых наблюдается Ni ошибок i-ro типа (относящихся к i-тому источнику отказов).

Другие направления

В работе [BM] был построен псевдослучайный генератор, в котором центральным звеном является конструкция, которую можно рассматривать как самокорректирующуюся программу для решения задачи, эквивалентной проблеме дискретных логарифмов[BLR]. В работе [BLR] указывается, что Р. Рубинфилд ввел понятия программных чекеров для параллельных программ и использовал идею самотестирования для построения схемы константной глубины для проверки мажоритарных функций. В работе [BK] показаны методы построения программных чекеров для решения некоторых задач сортировки. В частности для двух массивов целых X и Y, представляющих некоторые мультимножества, чекер выдает «Сбой», если множество Y не упорядочено или если X¹Y. В противном случае, если данная программа выполняет корректную сортировку, чекер выдает «Норма».

Функция

Без вызова

программы

Общее время выполнения

Amult B

M(n)

A div B

n log n

Без вызова

программы

Общее время выполнения

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

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

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

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

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

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

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

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

Сначала рассмотрим вопросы анализа подобия последовательностей операторов в программе, поскольку этот подход не чувствителен к поверхностной маскировке, которую мог бы попытаться внести нарушитель, изменяя некоторые атрибуты программы, например, имена переменных, нумерацию строк и т.п. Для этого необходимо написать программу - анализатор, которая будет тестировать исследуемую программу и выделять операторы, накапливая их в файле как данные, отражающие порядок их использования. Введем для последовательности операторов программы с номером n обозначение seq n. Тогда последовательность операторов для программ 1 и 2 будет обозначаться seq1 и seq2 соответственно. Одна из характеристик последовательности операторов - частота появления отдельного оператора. Анализ последовательности операторов оказывается эффективным в тех случаях, когда нарушитель изменяет или перемещает отдельные части программы, добавляет дополнительные операторы или погружает скопированную программу в некоторый модуль. При таких манипуляциях значительные участки последовательности операторов сохраняются неизменными, так как попытка изменить их равносильна переписыванию программы с сопутствующей трудоемкой операцией отладки.

Рассмотрим распределение частот появления операторов в программе. Если программа скопирована целиком, но при этом замаскирована, число появлений каждого оператора в копии будет аналогично числу появлений в оригинале. Нарушитель может изменить некоторые операторы и добавить новые, но в целом процент изменений в программе, вероятно, будет мал, и распределение частот появления операторов ожидается одинаковым как для копии, так и для оригинала.

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

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

Информационная война

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

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

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

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

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

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

·     глобальная информационная война;

·     информационные операции;

·     преднамеренное изменение замысла стратегической и тактической операции;

·     дезорганизация жизненно важных для страны систем;

·     нарушение телекоммуникационных систем;

·     обнуление счетов в международной банковской системе;

·     уничтожение (искажение) баз данных и знаний важнейших государственных и военных объектов.

К методам и средствам информационной борьбы в настоящее время относят:

·     воздействие боевых компьютерных вирусов и преднамеренных дефектов диверсионного типа;

·     несанкционированный доступ к информации;

·     проявление непреднамеренных ошибок ПО и операторов компьютерных систем (в т.ч. за счет использования средств информационно-психологического воздействия на личный состав);

·     воздействие радиоэлектронными излучениями;

·     физические разрушения систем обработки информации.

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

Инкрементальные алгоритмы

Зафиксируем базовое криптографическое преобразованиеT (например, цифровая подпись документа с некоторым ключом). Каждой элементарной операции модификации текста (например, вставки) будет соответствовать инкрементальный алгоритм I. На вход этого алгоритма подаются: исходный файл, значения преобразования T на нем, описание операций модификации и, возможно, соответствующие ключи или другие параметры. Это позволяет вычислить значение T для результирующего файла. Основная проблема здесь заключается в проектировании схем обработки файлов, с включенными в них эффективными инкрементальными алгоритмами. Предположим, что имеется подпись sстар

для файла Dстар и файл D¢стар, измененный посредством вставки в файл Dстар

некоторых данных. Необходимо получить новую цифровую подпись путем подписывания строки, состоящей из sстар и описания операций модификации над документом Dстар. Это схема называется схемой, зависящей от истории. Могут иметься приложения, когда такие действия могут применяться. В большинстве же случаев это не желательно, так как когда делается большое количество изменений, то затраты на верификацию подписи (а эти затраты пропорциональны числу изменений) резко увеличиваются. В связи с этим размеры подписи растут со временем. Чтобы избежать таких затрат необходимо использовать схемы, свободные от истории или HF-схемы. Все нижеприведенные схемы являются схемами, свободными от истории.

Инкрементальный алгоритм маркирования

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

Алгоритм ИАМ2-3

Пусть u0,...uh - путь из корня u0=l

к j-тому концевому узлу обозначается как uh. Тогда:

1. Проверить, что алгоритм ВЕРa

при верификации принимает Т(l) как корректный АП строки (a,(L1,L2,L3),Id,счт)АУТ=Т(l), где Id - название документа и счт - текущее значение счетчика (связанного с этим документом).

2. Для i=1,...,h-1 проверить, что ВЕРa

принимает Т(ui) как корректный АП строки ((L1,L2,L3),рзм), где Li

- метка i-того дочернего узла w (в случае, если w имеет только два дочерних узла, то L3=g) и рзм - число узлов в поддереве с корнем w)).

3. Проверить, что ВЕРa

принимает Т(uh) как корректный АП блока F[j].

4. Если все эти проверки успешны, тогда совокупный АП файла F получается следующим образом.

4.1. Установить Т(uh):=АУТ(F(s)).

4.2. Для i=h-1,...,1 установить Т(ui):=АУТ(Т(ui1),Т(ui2),Т(ui3)).

4.3. Установить Т(l):=АУТ((Т(ui0),Т(ui1),Т(ui1)),Id,счт+1).

Следует подчеркнуть, что значения Т на всех других вершинах (то есть, не стоящих на пути u0,...,uh) остаются неизменяемыми.

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

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

Интерактивные системы доказательств

Пусть А и В

- две интерактивные, т. е. взаимодействующие через общую коммуникационную ленту, вероятностные машины Тьюринга. Через [В(х),А(х)] обозначается случайная величина - выходное слово машины А, когда А и В работают на входном слове х. Через |х| обозначается длина слова х.

Интерактивным доказательством для языка L называется пара интерактивных машин Тьюринга (P,V) такая, что выполняются следующие два условия.

1. (Полнота). Для всех хÎL вероятность Prob{[P(x),V(x)]=1}=1.

2. (Корректность). Для любой машины Тьюринга Р*, для любого полинома р и для всех хÎL достаточно большой длины Prob{[P*(x),V(x)]=1}<l/p(|x|).

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

Инверсия матрицы

M(n)

Определение ранга

матрицыС

M(n)

Определение ранга

матрицы Т

M(n)

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

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

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

В общем случае отказы программного обеспечения определяются как отклонения от правильного хода выполнения программы вследствие ошибок, допущенных в процессе преобразования исходного алгоритма в действующую программу, а ошибка – это регистрируемый пользователем факт неудовлетворенности качеством программы и определяется как причина дефекта системы программного обеспечения; и наоборот, дефект рассматривается как проявление допущенной ранее ошибки [ТЛН].

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

www.kiev-security.org.ua

BEST rus DOC FOR FULL SECURITY

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

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

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

Под определенными условиями внешней среды

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

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

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

множества E представляет собой набор значений данных, необходимый для выполнения прогона программы: E=(Ei:i=1,2,...,N);

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

выполнение программы П

приводит к получению для каждого Ei

определенного значения функции F(Ei);

множество E

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

наличие дефектов в программе П приводит к тому, что ей на самом деле соответствует функция F', отличная от заданной функции F;

для некоторого Ei

отклонение выхода F'(Ei), полученного в результате выполнения программы не должно превышать некоторый установленный уровень безопасности программного обеспечения S(Ei), то есть безопасность обеспечивается при соблюдении ограничения: F'(Ei)£S(Ei).

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

Используемая терминология

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

Термины и определения

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

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

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

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

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

Нарушитель (злоумышленник, противник)

- субъект (субъекты), совершающие несанкционированный доступ к информационному ресурсу.

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

Оценка безопасности ПО - процесс получения количественных и/или качественных показателей информационной безопасности при учете преднамеренных и непреднамеренных дефектов в системе.

Система обеспечения информационной безопасности

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

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

Технологическая безопасность

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

Эксплуатационная безопасность

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

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

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

y= fAM (x) = Ax modulo M.

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

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

Для этого были определены следующие ST-пары функций:

;

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

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

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

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

Эксперименты с RAM-машиной

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

Для простоты, основное внимание будет уделяться противникам с экспоненциально ограниченным временем выполнения. Кроме того, время выполнения противника ограничено сверху 2n, где n - размер рабочей ленты ЦП. На практике противник будет ограничен по времени некоторым полиномом от длины рабочей ленты ЦП.

Определение5.4. Невмешивающийся противник, обозначаемый как ADV, является вероятностной машиной, которая на входе k и завуалированной программе a, которая имеет доступ к оракульной RAMk-машине. Машина ADV инициирует повторные выполнения RAMk-машины на входах по своему выбору до тех пор, пока общее время выполнения не стане равным 2k. В процессе каждого из этих выполнений, машина ADV имеет доступ «только-для-чтения» к коммуникационным лентам между CPUk и MEMk.

Определение 5.5. Вмешивающийся противник определяется аналогично невмешивающемуся противнику за исключением того, что в процессе повторных выполнений противник имеет доступ для чтения и записи к коммуникационным лентам между CPUk и МЕМk.

Элементы модели угроз эксплуатационной безопасности ПО

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

Вариант общей структуры набора потенциальных угроз безопасности информации и ПО на этапе эксплуатации КС приведен в табл.1.1.

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

Рис.1.1. Схема угроз технологической безопасности ПО

Классификация методов защиты от компьютерных вирусов

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

регламентацию проведения работ на ПЭВМ;

· применение программных средств защиты;

· использование специальных аппаратных средств защиты.

При этом количество уровней защиты зависит от ценности информации, которая обрабатывается на ПЭВМ.

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

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

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

детекторов (несколько последовательно запускаемых программ). Набор детекторов достаточно широк, и постоянно пополняется по мере появления новых вирусов. Однако при этом могут быть обнаружены не все вирусы, а только распознаваемые детектором. Следующим элементом входного контроля является контекстный поиск в файлах слов и сообщений, которые могут принадлежать вирусу (например, Virus, COMMAND.COM, Kill и т.д.). Подозрительным является отсутствие в последних 2-3 килобайтах файла текстовых строк - это может быть признаком вируса, который шифрует свое тело.

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

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

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

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

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

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

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

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

Автоконтроль целостности.

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

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

·     входной контроль новых программ;

·     сегментация информации на магнитном диске;

·     защита операционной системы от заражения;

·     систематический контроль целостности информации.

Необходимо отметить, что не следует стремиться обеспечить глобальную защиту всех файлов, имеющихся на диске. Это существенно затрудняет работу, снижает производительность системы и, в конечном счете, ухудшает защиту из-за частой работы в открытом режиме. Анализ показывает, что только 20-30% файлов должно быть защищено от записи.

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

Кроме того, для защиты операционной системы может применяться нестандартный командный процессор (например, командный процессор 4DOS, разработанный фирмой J.P.Software), который более устойчив к заражению. Размещение рабочей копии командного процессора на виртуальном диске позволяет использовать его в качестве программы-ловушки. Для этого может использоваться специальная программа, которая периодически контролирует целостность командного процессора, и информирует о ее нарушении. Это позволяет организовать раннее обнаружение факта вирусной атаки.

В качестве альтернативы MS DOS было разработано несколько операционных систем, которые являются более устойчивыми к заражению. Из них следует отметить DR DOS и Hi DOS. Любая из этих систем более «вирусоустойчива», чем MS DOS. При этом, чем сложнее и опаснее вирус, тем меньше вероятность, что он будет работать на альтернативной операционной системе.

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

·     Семейство (батарея) детекторов.

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

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

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

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

·     Резидентные средства защиты. Эти средства могут резидентно разместиться в памяти и постоянно контролировать целостность системных файлов и командного процессора.Проверка может выполняться по прерываниям от таймера или при выполнении операций чтения и записи в файл.

КОДИРОВАНИЕ

Архитектура программной системы, взаимодействие ее с внешней средой и взаимодействие подпрограмм программной системы

Доступ к «чужим» подпрограммам и данным.

Нерациональная организация вычислительного процесса.

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

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

Функции и назначение кодируемой части программной системы, взаимодействие этой части с другими подпрограммами

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

Организация замаскированного спускового механизма программной закладки.

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

Технология записи программного обеспечения и исходных данных

Поставка программного обеспечения и технических средств со встроенными дефектами.

Продолжение рис.1.2.

ОТЛАДКА И ИСПЫТАНИЯ

Назначение, функционирование, архитектура программной системы

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

Формирование программной закладки с динамически формируемыми командами.

Неправильная организация переадресации отдельных команд программной системы.

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

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

Поставка вычислительных средств, содержащих программные, аппаратные или программно-аппаратные закладки.

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

Вербовка сотрудников коллектива, проводящих испытания.

Продолжение рис.1.2.

Конфиденциальное вычисление

Необходимо отметить, что арифметика над GF(2) реализует также, что –1=+1.

Имеют место следующие соотношения:

= =(m-2)·

Из этого соотношения можно увидеть, что каждый процессор может сам вычислить элемент (m-2)aibi, в то время как каждые два процессора из двухэлементного подмножества {i,j} могут конфиденциально вычислить доли по элементам (ai+aj)·(bi+bj) (в соответствии с теоремой 3.2). Отсюда следует алгоритм сведения вычисления на основании (3.3) и (3.4) m-арной функции к вычислению на основании (3.1) и (3.2) функции для двух аргументов.

Редукция к КВm=2

Вход.

Процессор i

содержит (ai,bi)Î{0,1}´{0,1}, i=1,...,m.

1. Редукция. Каждая пара процессоров (i,j), где i<j, вызывает

2-арную функцию (см. (3.1)-(3.2)). Процессор i обеспечивает входную пару (ai,bi), в то время как процессор j обеспечивает - (aj,bj). Кроме того, определим ответ оракула процессору i

как cj{i,j}.

2. Процессор i устанавливает ci=(m-2)aibi+

3. Процессор i выдает ci.

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

Предложение 3.1.

Алгоритм «Редукция к КВm=2» конфиденциально сводит вычисления на основании (3.3) и (3.4) m-арной функции к вычислению на основании (3.1) и (3.2) функции для двух аргументов.

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

Теорема 3.4.

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

конфиденциальным образом) этой вычислимой функции

Теперь мы непосредственно обращаемся к вычислимой функции, определенной в равенствах (3.1)-(3.2). Все арифметические операции выполняются в поле GF(2). Ниже приводится алгоритм редукции ( конфиденциальным образом) этой вычислимой функции к вычислению OT41.

Редукция к ОТ41

Вход.

Процессор i содержит (ai,bi)Î{0,1}´{0,1}, i=1,2.

1. Первый процессор равномерно выбирает c1ÎR{0,1}.

2. Оба процессора вызывают субпротокол OT41, где первый процессор играет роль отправителя S, а второй процессор играет роль получателя R.

Тогда вход для отправителя – это 4-элементный кортеж (c1+a1·b1,c1+a1·(b1+1),c1+(a1+1)·b1,c1+(a1+1)·(b1+1)), а вход получателя - 1+2a2+b2Î{1,2,3,4}.

Выход.

Первый процессор выдает c1, в то время как второй процессор выдает результат, полученный при вызове OT41.

В столбцах таблицы 3.1 приведены значения выходов процессора 2 как функции от значений его собственных входов и входы и выходы процессора 1 (то есть, a1,b1,c1). Значения, с которыми процессор 2 инициализирует субпротокол ОТ (то есть, 1+2a2+b2) показаны во второй строке и значения выходов (и OT, и всего протокола) показаны в третьей строке. Отметим, что в каждом случае, выход процессора 2 равняется c1+(a1+a2)·(b1+b2).

Таблица 3.1

Значения (a2,b2)	(0,0)	(0,1)	(1,0)	(1,1)
Выход ОТ	1	2	3	4
Значения выхода	c1+a1·b1	c1+a1·(b1+1)	c1+(a1+1) · b1	c1+(a1+1)· (b1+1)

Вначале отметим, что вышеупомянутая редукция корректна, так как выход процессора 2 равняется c1+(a1+a2)·(b1+b2). Это следует из анализа вышеприведенной таблицы истинности, которая описывает значения выхода процессора 2, как функции от ее собственных входов a1,b1,c1. Необходимо подчеркнуть, что выходная пара (c1,c2) равномерно распределена среди всех пар, для которых c1+c2=(a1+a2) ·(b1+b2).

Таким образом, каждый из локальных выходов (т.e., либо процессора 1, либо процессора 2) равномерно распределен, хотя оба локальных выхода зависимы друг от друга (как в уравнении (3.2). Таким образом, легко увидеть, что редукция конфиденциально вычислима. Формальные аргументы приведены в [Go2].

Конфиденциальное вычисление функции

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

Пусть в сети N, состоящей из n процессоров P1,P2,...,Pn со своими секретными входами x1,x2,...,xn, необходимо корректно (даже при наличии t

сбоящих процессоров) вычислить значение функции (y1,y2,...,yn)=f(x1,x2,...,xn) без разглашения информации о секретных аргументах функции, кроме той, информации, которая может содержаться в вычисленном значении функции.

По аналогии с идеальным и реальным сценариями, приведенными выше, можно ввести понятия «реальное и идеальное вычисление функции f» [MR].

Пусть множество входов и выходов обозначается как X и Y соответственно, размерности этих множеств ½X½=c и ½Y½=m. Множество случайных параметров, используемых всеми процессорами сети, обозначается через R, размерность - ½R½=n. Кроме того, через W

обозначим рабочее пространство параметров сети. Через T(r) обозначается трафик в r-раунде, через ti(r) – трафик для процессора i в r-том раунде, r0 и rk – инициализирующий и последний раунды протокола P соответственно и r* - заданный неким произвольным образом раунд выполнения протокола P.

Пусть функцию f

можно представить как композицию d

функций (суперпозицию функций) g1

...

gh+1

...

gd:

f(x1,...,xn)=

=g1((w1,...,wn),(

,...,

))

...

gh((w1,...,wn),(

,...,

))

...

gd((w1,...,wn),(

,...,

)).

Аргументы функции gh

являются рабочими параметрами w1,...,wn участников протокола с трафиком (t1,...,tn) в r раунде. Значения данной функции gh

являются аргументами (рабочими параметрами протокола с трафиком (t1,...,tn) в r+1 раунде) для функции gh+1.

Из определения следует, что функция f:(XnÄRnÄW)®Y, где Ä

- декартово произведение множеств, реализует:

f(x1,...,xn)=gd((w1,...,wn),(

,...,

))=((y1,...,yn),(

,...,

)).

Введем понятие моделирующего устройства M. Здесь можно проследить некоторые аналогии с моделирующей машиной в интерактивных системах доказательств с нулевым разглашением (см., например, [Ка14,КУ4]).

Пусть рQПрот

- распределение вероятностей над множеством историй (трафика Т и случайных параметров) сбоящих процессоров во время выполнения протокола Р.

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

между М и сбоящим процессорами.

Протокол P конфиденциально вычисляет функцию f(x), если выполняются следующие условия:

Условие корректности. Для всех несбоящих процессоров Pi

функция

f(x1,...,xn)=

=g1((w1,...,wn),(

,...,

))

...

gh((w1,...,wn),(

,...,

))

gh+1((w1,...,wn),(

,...,

))

...

gd((w1,...,wn), (

,...,

))=

=((y1,...,yn),(

,...,

))

вычисляется с вероятностью ошибки близкой к 0.

Условие конфиденциальности.

Для заданной тройки (x,r,w)Î(XnÄRnÄW) распределения рQПрот

и иQПрот

являются статистически не различимыми.

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

КОНТРОЛЬ

Используемые процедуры и методы контроля

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

Маскировка программной закладки путем внесения в программную систему ложных «непреднамеренных» дефектов.

Формирование программных закладок в ветвях программной системы, не проверяемых при контроле.

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

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

Сведения о персональном составе контролирующего подразделения и испытываемых программных системах

Внедрение злоумышленников в контролирующее подразделение.

Вербовка сотрудников контролирующего подразделения.

Сбор информации об испытываемой программной системе.

Сведения об обнаруженных при контроле программных закладках

Разработка новых программных закладок при доработке программной системы.

Сведения об обнаруженных незлоумышленных дефектах и программных закладках

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

Сведения о среде функционирования программной системы и ее изменениях.

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

Продолжение рис.1.2.

Таблица 1.1

Угрозы	Несанкционированные действия
нарушения	Случайные	Преднамеренные
безопас-ности ПО		Пассивные	Активные
Прямые	Невыявленные ошибки программного обеспечения КС; отказы и сбои технических средств КС; ошибки операторов; неисправность средств защиты информации; скачки электропитания на технических средствах; старение носителей информации; разрушение информации под воздействием физических факторов (аварии, неправильная эксплуатация КС и т.п.).	Маскировка несанкционированных запросов под запросы ОС; обход программ разграничения доступа; чтение конфиденциальных данных из источников информации; подключение к каналам связи с целью получения информации («подслушивание» и/или «ретрансляция»); анализ трафика; использование терминалов и ЭВМ других операторов; намеренный вызов случайных факторов.	Включение в программы РПС, выполняющих функции нарушения целостности и конфиденциальности информации и ПО; ввод новых программ, выполняющих функции нарушения безопасности ПО; незаконное применение ключей разграничения доступа; обход программ разграничения доступа; вывод из строя подсистемы регистрации и учета; уничтожение ключей шифрования и паролей; подключение к каналам связи с целью модификации, уничтожения, задержки и переупорядочивания данных; несанкционированное копирование, распространение и использование программных средств КС; намеренный вызов случайных факторов.
Косвенные	нарушение пропускного режима и режима секретности; естественные потенциальные поля; помехи и т.п.	перехват ЭМИ от технических средств; хищение производственных отходов (распечаток, отработанных дискет и т.п.); использование визуального канала, подслушивающих устройств и т.п.; дистанционное фотографирование и т.п.	помехи; отключение электропитания; намеренный вызов случайных факторов.

Э

К

С

П

Л

У

А

Т

А

И

Я

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· подмножества ограничений на использование ресурсов аппаратуры и операционной системы, например оперативной памяти, процессорного времени, ресурсов ОС, возможностей интерфейса и других ресурсов;

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

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

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

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

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

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

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

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

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

Криптографические методы

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

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

· запись криптографически преобразованных эталонных характеристик аппаратно-программной среды компьютера на винчестер.

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

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

· в зарезервированные сектора системной области винчестера;

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

Можно выделить два основных метода защиты от копирования с использованием криптографических приемов:

· с использованием односторонней функции;

· с использованием шифрования (которое также может использовать односторонние функции).

Односторонние функции это функции, для которых при любом x

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

Если эталонные характеристики программно-аппаратной среды представить в виде аргумента односторонней функции x, то y - есть «образ» этих характеристик, который хранится на винчестере и по значению которого вычислительно невозможно получить сами характеристики. Примером такой односторонней функции может служить функция дискретного экспоненцирования, описанная ранее, с размерностью операндов не менее 512 битов.

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

Криптопрограммирование посредством использования инкрементальных алгоритмов

www.kiev-security.org.ua

BEST rus DOC FOR FULL SECURITY

Одним из основных инструментов методологии криптопрограммирования являются инкрементальные криптографические алгоритмы. Цель инкрементальной криптографии заключается в разработке криптографических алгоритмов обработки электронных данных, обладающих следующим принципиальным свойством. Если алгоритм применяется к электронным данным D для достижения каких-либо их защитных свойств, то применение инкрементального алгоритма к данным D, подвергнувшихся модификации – D¢, должно осуществляться быстрее, чем необходимость заново обработать первоначальный электронный документ. В тех приложениях, когда указанные алгоритмы используют, например, алгоритмы шифрования электронных документов или их цифровой подписи, требование повышения эффективности инкрементальных алгоритмов является основным. Один из основных методов применения инкрементальных алгоритмов заключается в использовании их аутентификационных признаков для антивирусной защиты [BGG].

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

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

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

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

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

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

Линейные рекуррентные соотношения

В работе [KS] исследовались вопросы построения самотестирующихся и самокорректирующихся программ для линейных рекуррентных соотношений, т.е. соотношений вида f(n)=

. Такие последовательности являются основными для многих комбинаторных и теоретико-числовых последовательностей, таких как последовательность Фибоначчи и последовательность Лукаша.

Линейные рекуррентные соотношения часто рассматриваются в неявном виде в качестве однородных линейных уравнений вида:

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

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

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

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

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

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

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

На основании полученных результатов можно сделать заключение о степени безопасности программы. Ключевыми понятиями здесь являются «способ представления» и «модель программы».
Дело в том, что на компьютерную программу можно смотреть с очень многих точек зрения - это

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

Рис. 7.2. Схема анализа безопасности ПО с помощью

логико-аналитических методов

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

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

·          лексический верификационный анализ;

·          синтаксический верификационный анализ;

·          семантический анализ программ.

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

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

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

·          сигнатуры вирусов;

·          сигнатуры элементов РПС;

·          сигнатуры «подозрительных функций»;

·          сигнатуры штатных процедур использования системных ресурсов и внешних устройств.

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

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

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

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

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

M(n)log n

A modulo N

M(n)

AB modulo N

M(n)

Ab modulo N

(с известной факторизацией модуля)

M(n)

Ab modulo N

(с неизвестной факторизацией модуля)

n log4n

M(n)log4n

Манипуляции с кодом программы

При манипуляциях с кодом программы можно привести два следующих способа:

включение в тело программы «пустых» модулей;

· изменение защищаемой программы.

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

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

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

Метод наименьших квадратов и задача самотестирования

Рассмотрим метод наименьших квадратов применительно к задачам двух типов: детерминированной и стохастической с известными вторыми моментами.

Детерминированная задача состоит в выборе вектора х

таким образом, чтобы минимизировать значение

в уравнении:

=||Ах-у||2 =хТАТАх-2уTАх+||у||2, (4.1)

где А — известная матрица, а у — известный вектор, индекс Т обозначает транспонирование матрицы или вектора.

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

=E(wTz-d)2=wTzRzw-2RTdzw+E(d2), (4.2)

где z — случайный вектор; d — случайная величина. Скалярная случайная величина wTz представляет собой линейную комбинацию компонентов случайного вектора z

и используется как линейная оценка случайной величины d. Математическое ожидание обозначается символом Е, через Rz обозначена матрица вторых моментов случайного вектора z: Rz=EzzТ. Аналогично вектор Rdz определяется как Rdz=E(dz).

В работе [УСБ] показана вычислительная эквивалентность стохастической задачи наименьших квадратов с оценкой вторых моментов и соответствующей детерминированной задачи. Поэтому достаточно для наших целей рассматривать вычислительные методы только для детерминированной задачи наименьших квадратов.

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

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