Схема АПРС

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

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

Схема АПРС

Схема АПРС

имеет следующее свойство. Существует полином p(·) степени t

такой, что каждый выход несбоящего процессора Pi, протокола АРзПр – p(i) и p(0) является разделенным секретом. Это свойство лежит в основе построения схемы АРзПр в условиях By-сбоев.

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

Вычисления дилера (по входу s):

1. Выбрать случайный полином h(·,·) степени t

от двух переменных такой, что h(0,0)=s (Т.е. h(x,y)=

, где h0,0=s и все другие коэффициенты h0,1,...,ht,t выбраны однородно и независимо над F). Для каждого 1£i£n посылает полиномы fi(·)=h(·,i) и gi(·)=(hi, ·) процессору Pi.

Вычисления процессора Pi:

2. После получения fi(·) и gi(·) от дилера и для каждого 1£j£n посылает fi(j) процессору Pj.

3. После получения vi,j от процессора Pj

проверяет, если vi,j=gi(j), тогда этот процессор распространяет (OK,i,j).

4. После получения (OK,j,k), контролирует существование звезды в OK, используя процедуру ЗВЗ, описанную выше. Если звезда (Ci,Di) найдена, переходит к шагу 6 и посылает (Ci,Di) всем процессорам.

5. После получения сообщения (Cj,Dj) добавляет (Cj,Dj) к множеству «предлагаемых звезд».
Пока звезда не найдена, всякий раз, когда получено распространяемое сообщение (OK,k,l), проверяет, формируют ли (Cj,Dj) звезду в графе OKi.

6. После нахождения звезды (Ci,Di) и если iÏDi скорректировать полином gi(·), основываясь на сообщении о верификации, полученном от процессоров из Di и с использованием кодов c исправлением ошибок (процедуры СКОП, описанной ниже). А именно, пусть Vi={(j,vi,j)½jÎDi}, тогда установить (t,Vi)СКОП=(gi(·)).

7. Как только gi(·) локально скорректирован, выдает g

(0).

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

Вычисления для процессора Pi (по входу i и с параметрами RÍ{P1,...,Pn}).

7. Посылает ai процессорам из R.

9.     Пусть Si={(j,aj)½aj получен из Pj. Если PiÎR, заканчивает без выхода. В противном случае установить (t,Si)СКОП=zi(·) и выдает zi(0).

Схема, корректирующая ошибки

Схема, корректирующая ошибки, работающая в префиксном режиме, обозначаемая в дальнейшем СКОП, позволяет каждому процессору вычислить полином p(·) степениd, удовлетворяющий p(j)=aj для каждого полученного им сообщения aj. А именно, процессор будет исследовать этот полином после получения сообщений от других процессоров и определять единственным образом интерполируемый полином степени d [BCG].

Определение 3.4.

Пусть d

и r

- целые числа и пусть множество SÍ[n]´F такое, что для каждых двух элементов (i,a) и (i¢,a¢ ) из S, получаем i=i¢. Будем считать, что S

является (d,r)-интерполируемым, если существует полином p(·) степени d такой, что не более r элементов (i,a)ÎS не удовлетворяет p(a)=e. Будем говорить, что p(·) является (d,r)-интерполируемым полиномом множества S.

Определение 3.1.

Пусть I – аккумулируемое множество (см. выше). Тогда I называется событийно (d,r)-интерполируемым, если для каждого планировщика, каждой коалиции из не более чем t сбоящих процессоров и каждого запуска алгоритма существует целое число 0£r£t

такое, что I будет событийно содержать (d,r)-интерполируемое множество мощностью не менее d+t+r+1.

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

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

Процедура СКОП состоит из t+1 итераций. На итерации r процессор ожидает, пока мощность аккумулируемого множества I станет не менее d+t+r+1.
Затем, каждый процессор запускает ниже описываемую процедуру, которая определяет, является ли множество I - (d,r)-интерполируемым и вычисляет соответствующий интерполируемый полином. Если

(d,r)-интерполируемый полином найден, тогда оно подается на выход и работа завершается. В противном случае, мы переходим к итерации r+1 (так как I – является событийно интерполируемым, он ограничен, по крайней мере, еще одним элементом и, таким образом, итерация r+1 будет завершена).

Далее описывается, как определить, является ли данное множество (d,r)-интерполируемым и как вычислять интерполируемый полином, используя теорию кодирования. Рассмотрим следующий код. Слово W=(i1,a1)...(il,al) является ключевым, тогда и только тогда, когда существует полином p(·) степени d такой, что p(ij)=aj для каждый 1£j£l. Такой код является обобщенным кодом Рида-Соломона, имеющим эффективную процедуру, корректирующую ошибки. Данная процедура обнаруживает и исправляет не менее r

ошибок во входном слове W, где ½W½³d+2r+1 (см., например, [КС]).

Пусть ПКО обозначает следующую процедуру. А именно, пусть S - (d,r)-интерполируемое множество мощностью не менее d+2r+1. Тогда процедура ПКО по входу (d,r,S), выдает (d,r)-интерполируемый полином из множества S.

Процедура СКОП

Выполняется в t циклах по r.

1.     Пусть Ir

определяет содержимое аккумулируемого множества I, где I содержит d+t+r+1 элементов.

2.     Ожидать пока ½I½³d+t+r+1. Тогда, запустить процедуру ПКО со входом (d,r,Ir), и пусть p(·) – выходной полином.

3.     Если p(·) - (d,r)- интерполируемый полином Ir (а именно, если для d+t+1 элементов (i,a)ÎIr, мы имеем p(i)=a), выдать p(·). В противном случае, перейти к следующей итерации.

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

Пусть I – событийно (d,t)-интерполируемое аккумулируемое множество.Тогда процедура СКОП

останавливается и выдает (d,t)-интерполируемый полином множества I.

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

Пусть r¢, являющийся наименьшим из r, такой, что Ir¢

является (d,Ir¢)-интерполируемым. Так как I – является событийно (d,t)-интерполируемым, то r¢£t. Все итерации вплоть до r¢ будут неудачно завершены. Тогда (d,t)-интерполируемый полином I будет найден на итерации r¢.        <

Схема (n,t)-звезды

Пусть OKi-граф – это неориентированный граф с вершинами [n], где ребро (j,k) существует тогда и только тогда, когда процессор Pi

завершил распространение двух сообщений (OK,j,k), инициированное Pj и (OK,k,j), инициированное Pk.

Определение 3.3.

Пусть G - граф с вершинами [n]. Тогда пара множеств (C,D) такая, что CÍDÍ[n] является (n,t)-звездой в G, если выполняются следующие условия:

·     ½C½³n-2t и ½D½³n-t;

·     для каждого jÎC и для каждого kÎD в G существует ребро (j,k).

Процессор Pi получает доступ к разделенному секрету, когда находит звезду по OKi-графу. Лемма 3.5 (см. далее) реализует, что если n³4t+1, доли несбоящих процессоров в звезде OKi- графа, определяют единственным образом полином степени t от двух переменных. Лемма 3.6. говорит о том, что полиномы, определенные звездами для каждой из двух сторон равны. Таким образом, только несбоящие процессоры могут найти звезду, определяющую уникальный секрет.

В принципе, можно было бы допустить процессор, ждущий клику размера n-t взамен звезды. Если дилер честен, то OKi

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

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

Далее описывается процедура нахождения (n,t)-звезды в графе с n вершинами (см. определение 3.3), где граф содержит клику размера n-t. А именно, нижеописываемая процедура ЗВЗ, в качестве выхода выдает либо звезду в графе, либо выдает сообщение «звезда не найдена». Как только граф содержит клику размера n-t, процедура выдает звезду в графе. Аналогичная процедура описана в [ГДж].

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

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

вершин, такие, что ½C½³n-2t ½D½³n-t и не существует ребер между вершинами из C и вершинами из CÈD. Эта пара множеств будет называться -звездой. Далее находится максимальное паросочетание в графе (см., например, [Ал, стр.18]).

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

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


Пусть C - множество вершин, которые не являются трехглавыми и B - множество вершин, которые имеют соседние вершины из C

и пусть D=[n]-B.

Алгоритм ЗВЗ

Вход:

неориентированный граф G с вершинами [n] и параметром t.

Выход:

-звезда в графе G, или сообщение «звезда не найдена».

1.   Найти максимальное паросочетание M

в G. Пусть N - множество согласованных вершин (а именно, концевые точки ребер в M) и пусть =[n]-N.

2.   Проверить, что паросочетание M

имеет свойство L:

2.1. Пусть Т

– множество трехглавых вершин, а именно T={iν$ j,k такие, что (i,j),(i,k)ÎG}. Пусть

C=-T.

2.2. Пусть B – множество вершин, имеющих соседние вершины в C, а именно B:={jÎN½$ iÎC такие, что (i,j)ÎG}. Пусть D:=[n]-B.

2.3. Если ½C½³n-2t и ½D½³n-t выдать (C,D), в противном случае выдать «звезда не найдена».

 

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

Предположим, что процедура ЗВЗ

выдает (C,D) на входном графе G. Тогда, (C,D) формирует -звезду в G.

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

Ясно, если алгоритм ЗВЗ выдает (C,D), тогда затем ½C½³n-2t ½D½³n-t и CÍD. Мы показываем, что для каждого iÎC и для каждого jÎD вершины i и j не являются соседними в G.

Предположим, что iÎC и jÎD и что (i,j) – ребро в G. Так как jÎD, мы имеем jÏB. По определению множества B, мы имеем jÏN (если iÎC и jÎN, тогда jÎB). Кроме того, iÎCÍ. Таким образом, и i, и j не входят в паросочетание. Следовательно, ребро (i,j) может быть добавлено к паросочетанию для создания наибольшего паросочетания, и, следовательно, паросочетание не является максимальным.                   <

Предложение 3.4. Пусть G

- граф с n вершинами, содержащий независимое множество мощностью n-t.


Тогда процедура ЗВЗ выдает

-звезду в G.

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

Сначала покажем, что если входной граф G

содержит независимое множество мощности n-t, тогда множества C и D, определенные на шагах 2.а и 2.b. алгоритма ЗВЗ являются достаточно большими. Следовательно, алгоритм выдает (C,D). В предложении 3.3 утверждается, что (C,D) формирует звезду в G. Далее покажем, что ½C½³n-2t.  Пусть IÍ[n] – независимое множество мощности n-t в G и пусть =[n]-I. Далее необходимо конкретизировать значения N, T и C в алгоритме ЗВЗ.

Пусть

F=I-C. Далее покажем, что ½F½£½½. В то же время ½½£t. Следовательно, ½C½³½I½-½F½³n-2t.

Так как ½F½£½½, покажем взаимно однозначное соответствие  f:F®. Пусть iÎF и так как iÏC, мы имеет либо iÎN, либо iÎT.

Случай 1: iÎN. Тогда, пусть f(i) - вершина, сочетаемая с i в множестве М. Ясно, что f(i)Î, в противном случае мы имели бы ребро (i,f(i)), где и i и f(i) принадлежит независимому множеству.

Случай 2: iÎT. По определению множества T, вершина i имеет две соседние вершины j и k

такие, что (j,k)ÎM. Произвольно множество f(i)=j. Понятно, что и j, и k принадлежат .

Покажем, что f - взаимно однозначная функция. Рассматривая две различные вершины l,mÎF, мы различаем три случая.

Случай 1: l,mÎN. В этом случае, f(l)¹f(m), так как М - паросочетание.

Случай 2: lÎN и mÎT. Так как mÎT, то существует ребро между m и вершиной, сочетаемой с f(m). Так как lÎN вершина, сочетаемая с f(l) – это вершина l. Далее, предположим, что f(l)=f(m). Таким образом, (l,m) – ребро в G. Однако и l, и m принадлежат множеству I.


Что противоречит условию.

Случай 3: l,mÎT. Предположим, что f(l)=f(m). Пусть a - вершина, сочетаемая с f(m) из М. Тогда и l, и m – соседние вершины для f(m) и a. Однако, в этом случае паросочетание М

- не является максимальным, например, M-{(f(m),a)}È{(f(m),l),(a,m)} – является наибольшим паросочетанием.

В заключение покажем, что D³n-t. Напомним, что D=[n]-B. Далее покажем, что ½B½£½M½. Так как G содержит независимое множество мощности n-t, мы имеем ½M½£t. Таким образом, ½D½=n-½B½³n-½M½³n-t.

Для того, чтобы понять, что ½B½£½M½, мы покажем, что не более одной концевой точки каждого ребра (a,b)ÎM находится в B. От обратного предположим, что и a, и b имеют соседние вершины в C и пусть c,dÎC – соседние вершины a и b, соответственно. Конечно, c¹d (в противном случае, вершина c была бы трехглавой, и мы имели бы cÏC). Однако в этом случае паросочетание M не является максимальным. Например,

M-{(a,b)}È{(a,c),(b,d)} является наибольшим паросочетанием.   <

Схема подписи с верификацией по запросу

В работах Д. Шаума (см., например, [Ка5,Ка14]) впервые была предложена схема подписи с верификацией по запросу, в которой абонент V

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

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

 

Схема ПВЗ

Пусть каждый пользователь S

имеет один открытый ключ P и два секретных ключа S1 и S2. Ключ S1 всегда остается в секрете, - он необходим для генерации подписи. Ключ S2

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

Вместе с обозначениями секретного и открытого ключей xÎRZq и yÎRZ*p (взятых из отечественного стандарта на электронную цифровую подпись) введем также обозначения S1=x и S2=u, uÎRZq, а также открытый ключ P=(g,y,w), где wºgu(mod p). Открытый ключ P публикуется в открытом сертифицированном справочнике.

Протокол ГП

Подпись кода m вычисляется следующим образом. Выбирается kÎRZq и вычисляется

. Затем вычисляется sº[xr+mku](mod q). Пара (r,s) является подписью для кода m. Подпись считается корректной тогда и только тогда, когда , где wºm-1(mod q).

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

Протокол верификации ПВ

Абонент V вычисляет  и просит абонента S доказать, что пара (r,s) есть его подпись под кодом m. Эта задача эквивалентна доказательству того, что дискретный логарифм g по основанию r равен (по модулю p) дискретному логарифму w по основанию g, то есть, что logg(p)wºlogr(p)g. Для этого:

                    Абонент V

выбирает a,bÎRZq, вычисляет  и посылает d абоненту S.

    Абонент S выбирает tÎRZq, вычисляет ,  и посылает h1 и h2 абоненту V.

    Абонент V высылает параметры a и b.

    Если , то абонент S

посылает V параметр t; в противном случае - останавливается.

    Абонент V проверяет выполнение равенств  и .

Если проверка завершена успешно, то подпись принимается как корректная.

Протокол ОП

 В отвергающем протоколе S доказывает, что logg(p)w¹logr(p)g. Следующие шаги выполняются в цикле l раз.

                    Абонент V

выбирает d,eÎRZq, d¹1, bÎR{0,1}. Вычисляет , , если b=0 и , , если b=1. Посылает S значения a, b, d.

                    Абонент S

проверяет соотношение . Если оно выполняется, то a=0, в противном случае a=1. Выбирает RÎRZq, вычисляет  и посылает V

значение c.

                    Абонент V

посылает абоненту S значение e.

                    Абонент S проверяет, что выполняются соотношения из следующих двух их пар: ,  и , . Если да, то посылает V значение R. Иначе останавливается.

                    Абонент V

проверяет, что .

Если во всех l циклах проверка в п.5 выполнена успешно, то абонент V принимает доказательства.

Таблица 13.1. Протокол верификации является интерактивным протоколом доказательств с абсолютно нулевым разглашением.



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

Требуется доказать, что вышеприведенный протокол удовлетворяет трем свойствам: полноты, корректности и нулевого разглашения [Ка5, Ка14].

Полнота означает, что если оба участника (V

и S) следуют протоколу и (r,s) - корректная подпись для сообщения m, то V примет доказательство с вероятностью близкой к 1. Из описания протокола верификации очевидно, что абонент S всегда может надлежащим образом ответить на запросы абонента V, то есть доказательство будет принято с вероятностью 1.

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

доказать, что logg(p)wºlogr(p)g, когда на самом деле эти логарифмы не равны.

Предположим, что logg(p)w¹logr(p)g. Ясно, что для каждого a существует единственное значение b, то которое дает данный запрос d. Поэтому d не содержит в себе никакой информации об a. Если S смог бы найти h1, h2, t1

и t2 такие, что



и

,

где a1¹a2, то тогда выполнялось бы соотношение

logg(p)rº[(a1-a2)-1((b2-b1)+(t2-t1))](mod q)ºlogw(p)g.

Отсюда, очевидно, следует, что logg(p)wºlogr(p)g. В самом деле, пусть logw(p)gºlogg(p)r ºl. Тогда

,

что противоречит предположению. Следовательно, какие бы h1, h2, t1 и t2

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

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


Для доказательства нулевого разглашения необходимо для любого возможного проверяющего V* построить моделирующую машину , которая является вероятностной машиной Тьюринга, работает за полиномиальное в среднем время и создает на выходе (без участия S) такое же распределение случайных величин, которое возникает у V* в результате выполнения протокола. В нашем случае, случайные величины, которые «видит» V*, - это h1, h2, и t. Необходимо доказать, что протокол верификации является доказательством с абсолютно нулевым разглашением, то есть моделирующая машина создает распределение случайных величин (h1,h2,t), которое в точности совпадает с их распределением, возникающим при выполнении протокола. Моделирующая машина  использует в своей работе V* в качестве «черного ящика».

Моделирующая машина

    Запоминает состояние машины V*, то есть содержимое всех ее лент, внутреннее состояние и позиции головок на лентах. Затем получает от V*

значение d

и после этого снова запоминает состояние машины V*.

    Выбирает hÎRZq и вычисляет  и .

    Получает от V* значения a и b. Если , то  останавливается.

    Машина  «отматывает» V*

на состояние, которое было запомнено в конце шага 1. Выбирает tÎRZq

и вычисляет  и .

    Машина  передает V*

h1, h2 и получает ответ (a¢,b¢). Возможны два варианта:

    5.1.    a=a¢, b=b¢. В этом случае моделирование закончено и  записывает на выходную ленту тройку (h1,h2,t) и останавливается.

    5.2.    a¹a¢ или b¹b¢. Отсюда следует, что . Предположим, что b¹b¢. Из этого следует, что a¹a¢. Следовательно,  может вычислить . Отсюда (b¢-b)/(a-a¢)=l - дискретный логарифм r по основанию g.

6. Машина  «отматывает» V*

на состояние, которое было заполнено в начале шага 1. Получает от V* значение d.

7. Выбирает hÎRZq вычисляет  и  и передает их V*.

8. Получает от V* значения a и b. Если , то  останавливается.


В противном случае вычисляет

t=[h-al-b](mod q), выдает (h1,h2,t) на выходную ленту и останавливается.

К пп. 7 и 8 необходимо сделать следующее пояснение. Поскольку logg(p)wºlogr(p)g, из этого следует, что logw(p)gºlogg(p)r. Отсюда

.

Из описания моделирующей машины  очевидно, что она работает за полиномиальное время. Величины (h1,h2,t) на шаге 5.1 выбираются в точности как в протоколе и поэтому имеют такое же распределение вероятностей. Кроме того, значения (h1,h2), выбираемые на шаге 7, имеют такое же распределение, как и в протоколе. Чтобы показать что и t имеет одинаковое распределение, достаточно заметить, что машина V*

не может по h1 и h2 определить, с кем она имеет дело - с S или . Поэтому, даже если бы V* могла каким-либо «хитрым» образом строить a и b с учетом (h1,h2), распределение вероятностей величин a

и b в обоих случаях одинаковы. Но значение t определяется однозначно четверкой величин a, b, h1, h2, при условии выполнения проверки на шаге 5 протокола.     n

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

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

Полнота протокола очевидна. Если абоненты S

и V следуют протоколу, тогда абонент V всегда примет доказательства абонента S.

Для доказательства корректности прежде всего заметим, что если logg(p)wºlogr(p)g, то a и b, выбираемые абонентом V

на шаге 1, не несут в себе никакой информации о значении b. Поэтому, если S может “открыть” c, сгенерированное им на шаге 2, лишь единственным образом (то есть выдать на шаге 4 единственное значение R, соответствующее данному a), то проверка на шаге 5 будет выполнена с вероятностью 1/2 в одном цикле и с вероятностью 1/2l во всех l циклах.

Если же S может сгенерировать c таким образом, что с вероятностью, которая не является пренебрежимо малой, он может на шаге 4 “открыть” оба значения a, то есть найти R1 и R2 такие, что  и , то алгоритм, который использует S для этой цели, можно использовать для вычисления дискретных логарифмов: loggd=R2-R1.


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

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

построить моделирующую машину , которая создает на выходе (без участия S) такое же распределение случайных величин (в данном случае, c и R), какое возникает у V* в результате выполнения протокола.

Моделирующая машина

Следующие шаги выполняются в цикле l раз.

    Машина  запоминает состояние машины V*.

Получает от V*

значения a, b и d.

Выбирает aÎR{0,1}, RÎRZq и вычисляет . Посылает V* значение c.

Получает от V*

значение e.

Проверяет, было ли «угадано» на шаге 2 значение a (это значение было «угадано», если ,  и a=0, либо ,  и a=1). Если да, то записывает на входную ленту значение (c,R). В противном случае «отматывает» V* на то состояние, которое было запомнено на шаге 1, и переходит на шаг 2.

Легко видеть, что распределения случайных величин (c,R), возникающее в процессе выполнения протокола и создаваемые моделирующей машиной , одинаковы, поскольку R в обоих случаях - чисто случайная величина, а величина c

записывается на выходную ленту машины  только тогда, когда a совпало с b.

Поскольку значение a выбирается машиной  на шаге 3 случайным образом, а c не дает V*

никакой информации о значении a, на каждой итерации a

будет угадано с вероятностью 1/2. Отсюда следует, что машина  работает за полиномиальное в среднем время. n

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

Схемы инкрементального шифрования

Предлагаемые решения используют стойкую схему вероятностного шифрования E [GM] (см. также приложение). Предположим, что Е может использоваться для шифрования символов из S

и пар (i,d), где dÎS и i - целое число не большее, чем длина блоков данных в системе. При использовании Е

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

и Е2. Первая последовательность Е1

является результатом блочного шифрования некоторого файла D=D[1]...D[l], в то время как вторая Е2, шифрует последовательность изменений, обозначаемую M=М[1]...M[t] , посредством которых текущий документ был получен из D. Тогда инкрементальный алгоритм шифрования заключается в конкатенации шифртекста модифицированного документа с Е2. Каждые l шагов алгоритм восстанавливает модифицированные данные и заново шифрует их, используя блочное шифрование и, таким образом, формирует новую последовательность шифртекстов Е1

(одновременно устанавливая Е2

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

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

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

изменениями, в то время как М

увеличивается до размера 2l. Таким образом, мы имеем шифртекст, обозначаемый Е' данных D'

(конечно, теперь текущие данные другие).
При замене Е1 на Е'

и при исключении первых l

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

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

Выше мы предположили, что пользователь может хранить промежуточные результаты (которые требуют памяти размером О(l)) в локальной памяти, невидимой противником. Это предположение нереалистично в некоторых сценариях и несовместимо с вышеприведенными определениями для схем инкрементального шифрования. Далее мы используем вышеупомянутые идеи без этого предположения (идеи берутся из [GO,O], см. предыдущую главу). Для этого нам необходимо шифровать данные, используя три последовательности, обозначаемые Е1,Е2 и Е3. Первые две последовательности Е1

и Е2, является точно такими же, как определенные выше. Их достаточно для дешифрования данных. Дополнительная последовательность Е3

– является «шифрованием рабочей области» и обозначается как W=W[1]...W[2l].

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

Сначала, мы устанавливаем элементы последовательности W следующим образом: W[i]:=(i+D[i]) для i£l и W[i]:=M[i-l] для l+1£i£2l. Здесь мы предполагаем, что записи изменений имеют форму (i,d), где i – номер ячейки памяти и d

символ, который размещен в этой ячейке. Затем, мы сортируем пары из W по их левым элементам в соответствии с так называемыми ключами сортировки

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


Определяющим является то, что сортировка выполняется посредством использования эффективной сети сортировки такой, например, как сеть сортировки Батчера [BGG]. Следует подчеркнуть, что всякий раз, когда две пары сравниваются и переставляются (или нет), тогда они заново шифруются посредством Е

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

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

При использовании AKS-сети сортировки [BGG] вышеприведенная реализация инкрементального алгоритма шифрования требует O(llog l) шагов (в то время как, если мы используем сеть Батчера, то получаем сумму из О(l)+(llоg2l) шагов). Эти шаги могут быть распределены равномерно среди l операций модификации, обеспечивающих желаемую сложность.

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

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

Широковещательный примитив (Br-протокол)

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

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

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

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

 

Br-протокол

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

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

Код для участников:

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

 

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

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

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

Ниже описывается ë(n-1)/3û-устойчивый широковещательный протокол, который именуется BB, где t£ë(n-1/3)û - количество участников, которые могут быть нечестными. В протоколе принимается, что идентификатор дилера содержится в параметре m.

Протокол BB

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

1. Послать сообщение (сбщ,m) ко всем участникам.

Код для участника Pi:

2. После получения сообщения (сбщ,m), послать сообщение (эхо,m) ко всем участникам.

3. После получения n-1 сообщений (сбщ,m¢), которые согласованы со значением m¢, послать сообщение (гот,m¢) ко всем участникам.

4. После получения t+1 сообщений (гот,m¢), которые согласованы со значением m¢, послать (гот,m¢) ко всем участникам.

5. После получения n-1 сообщений (сбщ,m¢), которые согласованы со значением m¢, послать сообщение (OK,m¢) ко всем участникам и принять m¢ как распространяемое сообщение.

Сокрытие модели доступа

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

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

Цель при решении задачи сокрытия модели доступа состоит в том, чтобы сделать невозможным для противника получить о программе что-либо полезное из модели доступа. В этом случае центральный процессор не будет выполнять программу обычным способом, - он будет заменять каждый оригинальный цикл «выборки/запоминания» многими циклами «выборки/запоминания». Это должно «запутывать» противника и предупреждать его от изучения оригинальной последовательности операций доступа к памяти, т.е. от фактической последовательности. Следовательно, противник не должен улучшить свои возможности по реконструкции оригинальной программы.

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

Предположим, что односторонние функции существуют и пусть

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

битами внутренней защищенной памяти и соответствующей завуалированной программы такой, что центральный процессор имитирует взаимодействие с завуалированной программой, реализуемое за время, ограниченное poly(k). Кроме того, взамен t

команд оригинальной программы будет выполняться менее чем tkО(1) команд завуалированной программы, а увеличение размера внешней памяти ограничивается фактором k.

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

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

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

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

1.Техническое обоснование, системный анализ, проектирование и стратегическое планирование работ по созданию комплекса программ с учетом характеристик всех структур КС на основе систем имитационного моделирования и САSЕ-средств.

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

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

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

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

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


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

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

1. Средства экспертизы и организации тестирования ПО.

2. Средства проведения тестирования.

3. Средства ликвидации дефектов.

4. Средства обеспечения тестирования.

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

·          экспертного анализатора контроля безопасности;

·          блока прогнозирования участков воздействия дефектов;

·          моделей угроз безопасности ПО;

·          планировщика тестов контроля технологической безопасности.

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

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

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


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

 

Рис.7.4 Структурно-функциональная схема инструментального комплекса

поддержки создания безопасного ПО.

 

Продолжение рисунка 7.4

Средства проведения тестирования состоят из следующих элементов:

·          средств обнаружения дефектов в ПО;

·          средств локализации дефектов;

·          системы генерации тестов;

·          базы данных тестирования.

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


В зависимости от назначения ПО обнаружение дефектов производится следующим образом.

В интересах контроля безопасности ОСПО осуществляется:

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

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

·          определение наличия сбоев в управлении информационно-вычислительным процессом,

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

·          контроль нарушения управления прикладными программами,

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

·          обнаружение нарушений целостности структур данных,

·          выявление возможностей упрощения алгоритмов программ.

В целях контроля безопасности СПО выполняется:

·          сравнение характеристик разработанных программ с параметрами эталона,

·          тестирование программных средств в расширенных интервалах входных данных,

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

·          расчет вероятностных характеристик наличия дефектов по выходным данным,

·          анализ устойчивости значений вероятностных характеристик,

·          выявление случаев искажения параметров программ и результатов их выполнения,

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



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

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

·          составление спецификаций с учетом целевого применения этих средств,

·          построение функциональных диаграмм и таблиц решений,

·          определение дефектных участков в структуре программных средств,

·          выявление отклонений от документированных штатных функций,

·          дублирование и сверка объектного кода путем итерационных трансляций программ,

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

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

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

·          самоликвидируемость;

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

·          изменяемость (неизменяемость) объема программ;

·          модифицируемость информационных структур;

·          самомодифицируемость.

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


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

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

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

·          блок ликвидации модулей формирования дефектов;

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

·          блок удаления нарушенных информационных структур и восстановления их целостности.

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

Средства обеспечения тестирования состоят из следующих компонентов:

·          блока сбора статистики о дефектах и их каталогизации;

·          блока оценки уровня безопасности ПО;

·          генератора отчетов контроля безопасности ПО.

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

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

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

В состав инструментальных средств проведения испытания программного обеспечения могут входить:

·

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

·          анализатор объектных кодов программ;

·          программы модельных испытаний;

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

·          программы оценки показателей безопасности ПО;

·          программы экспертизы выполнения требований;

·          программы интерфейса эксперта;

·          программы принятия решений;

·          программы расчета рисков.

Состав методического обеспечения проведения испытаний программ

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

А. Базовые методики.

А.1. Методики испытаний:

·          методика моделирования программ;

·          методика модельных испытаний;

·          методика испытаний по требованиям качества;

·          методика испытаний по требованиям безопасности.

А.2. Методика оценки показателей качества (ПК):

·           методика выбора номенклатуры ПК;

·           методика автоматизированной оценки ПК;

·           методика экспертной оценки ПК.

А.3. Методики экспертизы ПО:

·          методика экспертизы качества ПО;

·          методика экспертизы безопасности ПО.

А.4. Методики оценки требований к ПО:

·          методика экспертизы требований.

А.5. Методики принятия решений:

·          методика расчета относительных оценок ПК;

·          методика принятия решения о качестве ПО;

·          методика принятия решения о безопасности ПО;

·          методика принятия решения о выдаче сертификата качества;

·          методика расчета страховых рисков.

Б. Частные методики.

Б.1. По показателям качества:

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

Б.2. По видам ПО:

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

Состояние международной нормативно-методической базы

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

1) Общие принципы управления информационной безопасностью.

2)    Модели безопасности ИТ.

3)    Методы и механизмы безопасности ИТ (такие, как, например: методы аутентификации, управления ключами и т.п.).

4)    Криптографические алгоритмы.

5)    Методы оценки безопасности информационных систем.

6)    Безопасность EDI-технологий.

7)    Безопасность межсетевых взаимодействий (межсетевые экраны).

8)    Сертификация и аттестация объектов стандартизации.

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

Частоту появления операторов в программе можно изобразить в виде гистограммы. Для этого достаточно написать подпрограмму, которая будет подсчитывать каждое появление операторов в последовательности зафиксированных операторов программы. На рис.10.1 приведена гистограмма операторов для информационно - поисковой системы (ИПС) [ЗПО]; на абсциссе графика отмечено количество возможных операторов интерпретатора языка, используемого в этих текстах. Было выявлено [ЗПО], что некоторые операторы очень часто встречаются в программах различного назначения, некоторые редко, а некоторые вообще не встречаются. Для сравнения на рис.10.2 приведена гистограмма для программы редактирования текстов (РТ), которая отличается от гистограммы на рис.10.1.

Рис. 10.1. Гистограмма частоты появления операторов в программе для поисково-информационной системы

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

Рис. 10.2. Гистограмма частоты появления операторов в программе

для редакторов текстов

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

для одного оператора записывается в виде

,                                             (10.1)

где ,  - частоты появления оператора с номером n в программах 1 и 2 соответственно; Sn средняя сумма частот появления операторов с номером n

в обеих программах; Dn

- разность между частотами появления оператора с номером n в программах 1 и 2.

Мера для всей последовательности операторов получается путем суммирования по всем операторам и нормировки (чтобы снять зависимость от длины программы, сумму делят на полное число операторов в обеих программах). Такая мера подобия A(1,2) для программ 1 и 2 имеет вид:

,                                                                      (10.2)

где N - число операторов в языке.

Если частота появления операторов в обеих программах одинакова, мера подобия A(1,2)=1, если операторы, присутствующие в программах, образуют пересекающие множества A(1,2)=-1. Для рассмотренных последовательностей операторов мера подобия равна A(ИПС,РТ)=-0,8. Статистическая формула для корреляции имеет вид:

,

где , - средние значения частот появления всех операторов в программах 1 и 2 соответственно.

Значения коэффициентов корреляции, вычисленных по формуле (10.2) всегда находятся в пределах от 0 до 1. Если программы имеют почти один и тот же вид подобия, то коэффициент корреляции близок к 1, в случае вычисления коэффициента корреляции для программ ИПС и РТ, коэффициент корреляции равен C(ИПС,РТ)=0,56.

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

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


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

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

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

Расчет корреляции (которая в данном случае называется взвешенной взаимной корреляцией) продолжается путем перехода к следующему (второму) элементу последовательности. В этом случае соответствующая выборка увеличивается с 2 до n-1.

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


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

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

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

Способы внедрения РПС посредством инструментальных средств

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

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

compile:

  get (line);

translate(line);

Согласно этой структуры компилятор сначала «получает строку», а затем транслирует ее. Конечно, настоящий компилятор устроен намного сложнее, чем эта схема, но этой иллюстрации отдано предпочтение потому, что она в виде некой модели разъясняет фазы лексического анализа трансляции компилятора. Целью РПС будет поиск новых текстовых участков во входных программах, которые будут транслироваться, и вставление в эти участки различного кода. В примере, представленном ниже, компилятор ищет текстовый участок «read_pwd(p)», наличие которого в функции входа в данную компьютерную систему известно, как мы предполагаем, нападающей программе. Когда этот участок будет найден, компилятор не будет транслировать «read_pwd(p)», а вместо этого буде транслировать вставку из РПС, которая может устанавливать «лазейку», которая потом позволит злоумышленнику легко получить доступ к системе.
Измененный код компилятора следующий:

compile;

get (line)

if line=«readpwd(p)» then

translate (destructive means insertion);

else

translate(line);

fi;

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

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

Более изощренный метод внедрения РПС заключается в реализации следующего алгоритма [То].

compile;

get (line)

if line=«pattern_1» then

translate (destructive means insertion_N1);

if line=«pattern_2» then

translate (destructive means insertion_N2);

else

translate(line);

fi;

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


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

Таким образом, по мнению лауреата премии Тьюринга К. Томпсона [То]: «Нельзя доверять программе, которую вы не написали полностью сами. Сколько бы вы не исследовали и не верифицировали исходный текст - это не защитит вас от троянской программы. Для демонстрации атаки такого рода я выбрал компилятор Си. Я мог бы выбрать любую программу, обрабатывающую другие программы - ассемблер, загрузчик или даже микропрограмму, зашитую в аппаратуру. Чем ниже уровень программы, тем труднее и труднее обнаруживать подобные «жучки». Мастерски встроенный «жучок» в микропрограмме будет почти невозможно обнаружить».

Способы встраивания защитных механизмов в программное обеспечение

Встраивание защитных механизмов можно выполнить следующими основными способами:

·

вставкой фрагмента проверочного кода в исполняемый файл;

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

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

·     комбинированием указанных методов.

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

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

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

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

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

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

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

Способы защиты программ от исследования

Способы защиты от исследования можно разделить на четыре класса [ПАС].

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

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

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

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

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

2. Влияние на работу отладочного средства путем использован~ особенностей его аппаратной или программной среды. Например:

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

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

·     перехода микропроцессора в защищенный режим.

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

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

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

Рассмотрим данный метод подробнее. Пусть имеется некоторое полноцикловое преобразование из N состояний t: Т=t1,t2,...,tN (Например, обычный двоичный счетчик либо, рекуррента). Значение N

выбирается не слишком большим. Например, для k-битового счетчика N=2k. Участок кода, защищаемый от изучения, динамически преобразуется (шифруется) с использованием криптографически стойкого алгоритма на ключе t, который выбирается случайно и равновероятно из множества состояний Т.

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

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



Для численной оценки данного метода введем следующие значения. Предположим, что i в среднем равно N/2. Пусть w0 - время выполнения цикла алгоритма (установка текущего значения, дешифрование, проверка правильности дешифрования) в штатном режиме функционирования (без отладки); w1

- время выполнения того же цикла в режиме отладки; z —предельное время задержки при штатной работе защищенной программы. Тогда N=z/w0. Затраты времени злоумышленника исчисляются средней величиной Тзл=Nw1/2. Для приблизительных расчетов w1/w0»10000.

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

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

Преобразование кода программы во время ее выполнения может преследовать три основные цели:

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

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

·     противодействие считыванию кода программы в файл из оперативной памяти.

Перечислим основные способы организации преобразования кода программы [ПАС]:

1.       Замещение фрагмента кода функцией от находящейся на данном месте команды и некоторых данных.

2.       Определение стека в области кода и перемещение фрагментов кода с использованием стековых команд.



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

4.       Преобразование кода в зависимости от (внешней к программе) информации.

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

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

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

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

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

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


При этом либо блокируется работа отладчика, либо неверно преобразуется в исполняемые команды код программы.

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

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

2.       Активная защита первого типа - замыкание цепочек обработки событий минуя программы трассировки.

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

Например, для защиты от трассировки по дисковым прерываниям для ОС MS DOS при чтении некопируемой метки с дискеты или винчестера можно использовать следующие приемы:

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

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

·        прямой вызов соответствующих функций в ПЗУ (BIOS) после восстановления различными способами их физического адреса (активная защита первого типа);

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

При операциях с жестким диском, как правило, используется преры­вание int 13h. Для предотвращения трассировки программы по заданному прерыванию (в данном случае прерыванию int 13h) можно также исполь­зовать указанные выше способы, а именно:

·        переопределение исходного прерывания в BIOS на неиспользуемый вектор прерывания;

·        прямой вызов функций BIOS.

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

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

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

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

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

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

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

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

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

Разделение методов, их особенности и преимущества показаны в табл.7.1.

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

Для полного решения проблемы анализа безопасности программ необходимо осуществить следующие действия [ПБП].

Таблица 7.1

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

Продолжение таблицы 7.1

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

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

2.     Создать методы анализа безопасности ПО, используя выбранные формальные определения, доказать их эффективность и реализуемость;

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

4.     Создать методики применения этих средств и оценить их эффективность.

Стандартизация методов и механизмов безопасности ИТ

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

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

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

·     контроля целостности, предназначенные для обеспечения того, чтобы информация не была искажена или подменена;

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

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

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

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

·        ISO/IEC 9798-91 – «Информационные технологии. Защита информации. Аутентификация объекта».

Часть 1. Модель.

Часть 2. Механизмы, использующие симметричные криптографические алгоритмы.

Часть 3. Аутентификация на базе алгоритмов с открытыми ключами.

Часть 4. Механизмы, использующие криптографическую контрольную функцию.

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

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

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

·     контроля целостности, предназначенные для обеспечения того, чтобы информация не была искажена или подменена;

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

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

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

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

·        ISO/IEC 9798-91 – «Информационные технологии. Защита информации. Аутентификация объекта».

Часть 1. Модель.

Часть 2. Механизмы, использующие симметричные криптографические алгоритмы.

Часть 3. Аутентификация на базе алгоритмов с открытыми ключами.

Часть 4. Механизмы, использующие криптографическую контрольную функцию.

Часть 5. Механизмы, использующие алгоритмы с нулевым разглашением.

·        ISO/IEC 09594-8-88 – « Взаимосвязь открытых систем. Справочник. Часть 8. Основы аутентификации»;

·        ISO/IEC 11577-94 – «Информационные технологии. Передача данных и обмен информацией между системами. Взаимосвязь открытых систем. Протокол защиты информации на сетевом уровне»;

·        ISO/IEC DTR 10736 – «Информационные технологии. Передача данных и обмен информацией между системами. Протокол защиты информации на транспортном уровне»;

·        ISO/IEC CD 13888 – «Механизмы предотвращения отрицания».

Часть 1. Общая модель.

Часть 2. Использование симметричных методов.

Часть 3. Использование асимметричных методов;

·        ISO/IEC 8732-88 – «Банковское дело. Управление ключами»;

·        ISO/IEC 11568-94 – «Банковское дело. Управление ключами».

Часть 1. Введение. Управление ключами.

Часть 2. Методы управления ключами для симметричных шифров.

Часть 3. Жизненный цикл ключа для симметричных шифров;

·        ISO/IEC 11166-94 – «Банковское дело. Управление ключами посредством асимметричного алгоритма».

Часть 1. Принципы процедуры и форматы.

Часть 2. Принятые алгоритмы, использующие криптосистему RSA;

·        ISO/IEC DIS 13492 – «Банковское дело. Управление ключами, относящимися к элементам данных»;

·        ISO/IEC CD 11770 – «Информационные технологии. Защита информации. Управление ключами».

Часть 1. Общие положения.

Часть 2. Механизмы, использующие симметричные методы.

Часть 3. Механизмы, использующие асимметричные методы;

·        ISO/IEC DTR 10181- «Информационные технологии.


Взаимосвязь открытых систем. Основы защиты информации для открытых систем».

Часть 1. Общее описание основ защиты информации в ВОС.

Часть 2. Основы аутентификации.

Часть 3. Управление доступом.

Часть 4. Безотказность получения.

Часть 5. Конфиденциальность.

Часть 6. Целостность.

Часть 7. Основы проверки защиты.

К этому же уровню следует отнести стандарты, описывающие интерфейсы механизмов безопасности ИТ:

·        ISO/IEC 10164-7-92. «Информационные технологии. Взаимосвязь открытых систем. Административное управление системы. Часть 7. Функции уведомления о нарушениях информационной безопасности».

·        ISO/IEC DTR 11586. «Информационные технологии. Взаимосвязь открытых систем. Общие функции защиты верхних уровней».

Часть 1. Общее описание, модели и нотация.

Часть 2. Определение услуг сервисного элемента обмена информацией защиты.

Часть 3. Спецификация протокола сервисного элемента обмена информацией защиты.

Часть 4. Спецификация синтаксиса защищенной передачи.

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



Часть 5. Механизмы, использующие алгоритмы с нулевым разглашением.

·        ISO/IEC 09594-8-88 – « Взаимосвязь открытых систем. Справочник. Часть 8. Основы аутентификации»;

·        ISO/IEC 11577-94 – «Информационные технологии. Передача данных и обмен информацией между системами. Взаимосвязь открытых систем. Протокол защиты информации на сетевом уровне»;

·        ISO/IEC DTR 10736 – «Информационные технологии. Передача данных и обмен информацией между системами. Протокол защиты информации на транспортном уровне»;

·        ISO/IEC CD 13888 – «Механизмы предотвращения отрицания».

Часть 1. Общая модель.

Часть 2. Использование симметричных методов.

Часть 3. Использование асимметричных методов;

·        ISO/IEC 8732-88 – «Банковское дело. Управление ключами»;

·        ISO/IEC 11568-94 – «Банковское дело. Управление ключами».

Часть 1. Введение. Управление ключами.

Часть 2. Методы управления ключами для симметричных шифров.

Часть 3. Жизненный цикл ключа для симметричных шифров;

·        ISO/IEC 11166-94 – «Банковское дело. Управление ключами посредством асимметричного алгоритма».

Часть 1. Принципы процедуры и форматы.

Часть 2. Принятые алгоритмы, использующие криптосистему RSA;

·        ISO/IEC DIS 13492 – «Банковское дело. Управление ключами, относящимися к элементам данных»;

·        ISO/IEC CD 11770 – «Информационные технологии. Защита информации. Управление ключами».

Часть 1. Общие положения.

Часть 2. Механизмы, использующие симметричные методы.

Часть 3. Механизмы, использующие асимметричные методы;

·        ISO/IEC DTR 10181- «Информационные технологии.


Взаимосвязь открытых систем. Основы защиты информации для открытых систем».

Часть 1. Общее описание основ защиты информации в ВОС.

Часть 2. Основы аутентификации.

Часть 3. Управление доступом.

Часть 4. Безотказность получения.

Часть 5. Конфиденциальность.

Часть 6. Целостность.

Часть 7. Основы проверки защиты.

К этому же уровню следует отнести стандарты, описывающие интерфейсы механизмов безопасности ИТ:

·        ISO/IEC 10164-7-92. «Информационные технологии. Взаимосвязь открытых систем. Административное управление системы. Часть 7. Функции уведомления о нарушениях информационной безопасности».

·        ISO/IEC DTR 11586. «Информационные технологии. Взаимосвязь открытых систем. Общие функции защиты верхних уровней».

Часть 1. Общее описание, модели и нотация.

Часть 2. Определение услуг сервисного элемента обмена информацией защиты.

Часть 3. Спецификация протокола сервисного элемента обмена информацией защиты.

Часть 4. Спецификация синтаксиса защищенной передачи.

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

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

Организация ISO стандартизировала ряд криптографических алгоритмов в таких международных стандартах, как, например:

·

ISO/IEC 10126-2-91 – «Банковское дело. Процедуры шифрования сообщения. Часть 2. Алгоритм DEA»;

·     ISO/IEC 8732-87 – «Информационные технологии. Защита информации. Режимы использования 64-битного блочного алгоритма»;

·     ISO/IEC 10116-91- «Банковское дело. Режимы работы n-битного блочного алгоритма шифрования»;

·     ISO/IEC 10118-1,2-88 – «Информационные технологии. Шифрование данных. Хэш-функция для цифровой подписи»;

·     ISO/IEC CD 10118-3,4 – «Информационные технологии. Защита информации. Функции хэширования»;

·     ISO/IEC 9796-91 – «Информационные технологии. Схема электронной подписи, при которой производится восстановление сообщения»;

·     ISO/IEC CD 14888 – «Информационные технологии. Защита информации. Цифровая подпись с добавлением».

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

Организация ISO стандартизировала ряд криптографических алгоритмов в таких международных стандартах, как, например:

·

ISO/IEC 10126-2-91 – «Банковское дело. Процедуры шифрования сообщения. Часть 2. Алгоритм DEA»;

·     ISO/IEC 8732-87 – «Информационные технологии. Защита информации. Режимы использования 64-битного блочного алгоритма»;

·     ISO/IEC 10116-91- «Банковское дело. Режимы работы n-битного блочного алгоритма шифрования»;

·     ISO/IEC 10118-1,2-88 – «Информационные технологии. Шифрование данных. Хэш-функция для цифровой подписи»;

·     ISO/IEC CD 10118-3,4 – «Информационные технологии. Защита информации. Функции хэширования»;

·     ISO/IEC 9796-91 – «Информационные технологии. Схема электронной подписи, при которой производится восстановление сообщения»;

·     ISO/IEC CD 14888 – «Информационные технологии. Защита информации. Цифровая подпись с добавлением».

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

Стандартизация моделей безопасности ИТ

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

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

Можно выделить следующие международные стандарты и другие документы, в которых определяются основные модели безопасности ИТ:

·

ISO/IEC 7498-2-89 -  «Информационные технологии. Взаимосвязь открытых системы. Базовая эталонная модель. Часть 2. Архитектура информационной безопасности» (кратко описанная выше);

·     ISO/IEC DTR 10181-1 – «Информационные технологии. Взаимосвязь открытых систем. Основы защиты информации для открытых систем. Часть 1. Общее описание основ защиты информации ВОС»;

·     ISO/IEC DTR 10745 – «Информационные технологии. Взаимосвязь открытых систем. Модель защиты информации верхних уровней»;

·     ISO/IEC DTR 11586-1 – «Информационные технологии. Взаимосвязь открытых систем. Общие функции защиты верхних уровней. Часть 1. Общее описание, модели и нотация»;

·     ISO/IEC DTR 13335-1 – «Информационные технологии. Руководство по управлению безопасностью информационных технологий. Часть 1. Концепции и модели безопасности информационных технологий».

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

Отечественные стандарты [ГОСТ1-ГОСТ4] описывают криптографические алгоритмы, достаточные для решения большинства прикладных задач:

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

·     ГОСТ Р 34.10-94 «Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма»;

·     ГОСТ Р 34.11-94 «Информационная технология. Криптографическая защита информации. Функция хэширования»$

·     ГОСТ Р 34.10-2002 «Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма».

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

Стандартизация в области защиты информации от НСД

К основным стандартам и нормативным техническим документам по безопасности информации, в первую очередь, относится комплект руководящих документов Гостехкомиссии России (1998г), которые в соответствии с Законом «О стандартизации» можно отнести к отраслевым стандартам, в том числе «Средства вычислительной техники. Защита от несанкционированного доступа к информации. Показатели защищенности средств вычислительной техники»», «Автоматизированные системы. Защита от несанкционированного доступа к информации. Классификация автоматизированных систем и требования по защите информации», «Временное положение по организации разработки, изготовления и эксплуатации программных и технических средств защиты информации от несанкционированного доступа в автоматизированных системах и средствах вычислительной техники», «Средства вычислительной техники. Межсетевые экраны. Защита от несанкционированного доступа к информации. Показатели защищенности от НСД к информации», ГОСТ Р 50739-95 «Средства вычислительной техники. Защита от несанкционированного доступа к информации. Общие технические требования».

Особенности защиты программ нашли свое отражение в следующих руководящих документах: РД «Защита информации от несанкционированного доступа к информации. Программное обеспечение средств защиты информации. Классификация по уровню контролю отсутствия недекларированных возможностей» и проект РД «Антивирусные средства. Показатели защищенности и требования по защите от вирусов».

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

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

Кроме того, следующие нормативные документы, так или иначе косвенно регламентируют отдельные вопросы обеспечения безопасности ПО:

·     ГОСТ 28195-89. Оценка качества программных средств. Общие положения;

·     ГОСТ 21552-84. Средства вычислительной техники. ОТТ, приемка методы испытаний, маркировка, упаковка, транспортировка и хранение;

·     ГОСТ ВД 21552-84. Средства вычислительной техники. ОТТ, приемка методы испытаний, маркировка, упаковка, транспортировка и хранение;

·     ТУ на конкретный вид продукции (ПО).

Стандартизация вопросов управления информационной безопасностью

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

На роль такого документа претендует, находящийся в стадии утверждения проект международного стандарта ISO/IEC DTR 13335-1,2,3 – «Информационная технология. Руководство по управлению безопасностью информационных технологий». Данный документ содержит:

·     определения важнейших понятий, непосредственно связанных с проблемой управления безопасностью ИТ;

·     определения важных архитектурных решений по созданию систем управления безопасностью ИТ (СУБ ИТ), в том числе, определение состава элементов, задач, механизмов и методов СУБ ИТ;

·     описание типового жизненного цикла и принципов функционирования СУБ ИТ;

·     описание принципов формирования политики (методики) управления безопасностью ИТ;

·     методику анализа исходных данных для построения СУБ ИТ, в частности методику идентификации и анализа состава объектов защиты, уязвимых мест информационной системы, угроз безопасности и рисков и др.;

·     методику выбора соответствующих мер защиты и оценки остаточного риска;

·     принципы построения организационного обеспечения управления в СУБ ИТ и пр.

Статистические и динамические способы исследования ПО

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

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

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

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

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

Задача первого этапа решается известными методами дизассемблирования.

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

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

Помимо этих двух основных инструментов исследования, можно использовать:

·        «дискомпиляторы», генерирующие из исполняемого кода программу на языке высокого уровня;

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

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

Структура и принципы построения

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

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

Испытательный стенд должен удовлетворять следующим требованиям:

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

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

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

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

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

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

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

·          обеспечивать взаимозаменяемость отдельных элементов стенда и расширение его новыми компонентами;

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

·          обеспечивать диспетчеризацию, управление и администрирование информационно-вычислительным процессом в сети ПЭВМ;

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

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

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

www.kiev-security.org.ua BEST rus DOC FOR FULL SECURITY

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



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

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

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

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

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

6. Защищенность, под которой понимается изолированность штатных программно-аппаратной среды стенда от деструктивных воздействий со стороны испытываемых программ.

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

·          сектора макетов комплексов программ КС;

·          автоматизированного рабочего места (АРМ) обнаружения и ликвидации дефектов;

·          АРМ экспертного тестирования;

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

·          сектора планирования и анализа результатов тестового контроля;

·          сектора проектного анализа объектов контроля безопасности;



·          сервера эталонов КП;

·          сервера тестов;

·          АРМ администратора стенда.

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

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

АРМ экспертного тестирования предназначено для статического тестирования вероятностных характеристик наличия закладок в программах и оценки показателей их качества независимыми экспертами по специальным методикам и в соответствии с ГОСТ 28195-89.

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

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


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

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

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

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

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

АРМ администратора стенда реализует следующие общесистемные функции:

·          многоуровневая защита и изоляция элементов сети стенда и циркулирующей в нем информации от несанкционированного доступа как от абонентов сети, так и тестируемого ПО;



·          управление сетевым доступом;

·          конфигурирование и реконфигурирование архитектуры стенда;

·          координация и диспетчеризация работы стенда, восстановление процесса его функционирования в случае возникновения отказов и сбоев;

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

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

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

·          высокое быстродействие, качество и значительный объем средств тестирования и разработки ПО;

·          наличие встроенных высокоуровневых протоколов обмена, обеспечивающих взаимодействие «клиент-сервер»;

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

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

·          приемлемая стоимость;

·          экспериментально проверенная согласованность по протоколам обмена с другими распространенными ОС;

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

Сведение защиты программ к забывающему моделированию на RAM-машине

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

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

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

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

RAM-машины остается только скрыть содержимое «области значений» в сообщениях, обмениваемых между ЦП и МП. Это делается посредством шифрования, которое использует случайный оракул.

Теорема5.1. Пусть {RAMk}kÎN - вероятностная RAM-машина, которая выполняет забывающее моделирование универсальной RAM-машины. Кроме того, предположим, что t шагов оригинальной RAM-машины моделируются за менее чем g(t)t шагов забывающей RAM-машины. Тогда существует компилятор, который защищает программы от невмешивающихся противников с затратами не боле O(g(t)).

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

Информация, доступная невмешивающемуся противнику состоит из сообщений, обмениваемых между ЦП и МП. Напомним, что сообщения от CPUk к MEMk имеют форму (i,a,v), где iÎ{выборка, сохранить, стоп}, aÎ{1,2,...,2k} и vÎ{0,1}O(k), в то время как сообщения от MEMk к CPUk имеют форму vÎ{0,1}O(k). При забывающем моделировании, по определению, «область адресов» (т.е., a) не вскрывает никакой информации относительно входа y=(Пf,x).
Просто необходимо устранить возможность, когда «область команд» (т.е., i) «давала бы» какой-либо полезную информацию для противника. Следовательно,  осталось только завуалировать содержимое области значений (т.е., v) так, чтобы ЦП мог восстанавливать оригинальные значения. Идея состоит в том, чтобы выполнить завуалировать v, используя оракул, доступный ЦП.

www.kiev-security.org.ua BEST rus DOC FOR FULL SECURITY

Для завуалирования машина CPUk

содержит специальный счетчик, обозначаемый счт, инициализированный нулевым значением. Мы модифицируем RAMk добавлением случайного оракула, обозначаемого f. Понятно, что новый случайный оракул может быть объединен со случайным оракулом, используемым при забывающем моделировании. Всякий раз, когда CPUk должен сохранять значение в памяти MEMk, счетчик счт увеличивается и значение v шифруется посредством пары (vÅf(счт),счт), где Å обозначает поразрядную операцию «исключающую или». При восстановлении пары (u,j), завуалированное значение восстанавливается посредством вычисления uÅf(j). Подчеркнем, что и завуалирование, и восстановление может быть легко выполнены, когда имеется доступ к оракулу f.

Компилятор C, защищающий программное обеспечение, функционирует следующим образом. На входе параметр k и программы П, состоящей из последовательности команд p1,..,pn, компилятор однородно выбирает функцию f

и множества Пf=(p1Åf(2k+1),2k+1),...,(pnÅf(2k+n),2k+n).

Так как общее время выполнения машины RAMk

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



Напомним, что на практике можно заменять случайный оракул на псевдослучайный. Следовательно, результат теоремы будет верен только для противников, ограниченных по времени некоторым полиномом. В этом случае, компилятор на входном параметре k и программе П равномерно выбирает псевдослучайную функцию f. Функция f может быть аппаратно реализовано в CPUk. Таким образом, ЦП способен вычислять f на входах длины k и poly(k)-временной противник не может различать поведение этого ЦП

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

Теорема 5.2. Пусть {RAMk}kÎN - вероятностная RAM-машина, которая выполняет забывающее моделирование с метками времени универсальной RAM-машины. Кроме того, предположим, что t шагов оригинальной

RAM-машины моделируются меньше, чем за g(t)t шагов забывающей

RAM-машины. Тогда существует компилятор, который защищает программное обеспечение от вмешивающихся противников, с затратами не более O(g(t)).

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

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

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

Центральный процессор CPUk, рассмотренный в предыдущей теореме, далее модифицируется следующим образом. Модифицированная машина CPUk

имеет доступ к еще одной случайной функции, обозначаемой f.


Эта функция может быть объединена с другими. В случае если CPUk желает сохранить завуалированное значение v

в ячейке памяти он сначала определяет текущий номер верси(a). Отметим, что номер версии(a) может быть вычислен CPUk в соответствии с определением моделирования с метками времени. Модифицированная машина CPUk теперь посылает сообщение (сохранить, a, (v,f(a,версия(a),v))) вместо сообщения («сохранить»,a,v), посланного первоначально. После получения сообщения (v,t) из МП

в ответ на запрос («выборка»,a,·), модифицированная машина CPUk определяет текущее значение номера версия(a) и сравнивает t с f(a, версия(a),v). В случае, если эти два значения равны CPUk

работает как и прежде. В противном случае, CPUk

немедленно останавливается, предотвращая, таким образом, защиту от вмешательства. Таким образом, попытки изменить сообщения от МП к ЦП

будут обнаружены с очень высокой вероятностью.   <

Теоретические основания

Пусть обфускатор – это (эффективный, вероятностный) «компилятор», который по входу программы (схеме) P выдает новую программу О(P), удовлетворяющую следующим условиям:

1.     Условие функциональности. Обфусктор O(P) должен вычислять ту же самую функцию, что и программа P.

2.     Условие (свойство) «виртуального черного ящика». «Все, что может быть вычислено эффективным образом из обфускатора O(P), может быть эффективно вычислено при оракульном доступе к программе P».

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

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

в том смысле, что существует свойство p :F®{0,1} такое, что:

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

·     по данному оракульному доступу к (случайно выбранной) функции fÎF, никакой эффективный алгоритм не может вычислять p(f) лучше, чем случайным угадыванием.

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

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

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

Теоретико-групповые и теоретико-числовые вычисления

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

Проблема эквивалентного поиска.

Пусть S – множество и G – группа, групповые действия в которой, осуществляются над элементами множестваS. Для a,bÎS элемент aºGb, тогда и только тогда, когда g(a)=b для некоторого g из  G. Проблема эквивалентного поиска заключается в нахождении g

такого, что g(a)=b, если aºGb для a и b, принадлежащих множеству S. Если существует эффективный вероятностный алгоритм поиска gÎG, тогда существует [BK] эффективный программный чекер для данной проблемы. Примеров решения задач эффективного эквивалентного поиска достаточно много. К ним относятся проблема поиска изоморфизма графов (см. дальше), решение задачи квадратных вычетов, обобщенная проблема дискретных логарифмов, задачи подобные «Кубику Рубика», ряд задач из теории кодирования и др. [BK].

Проблема пересечения групп.

Пусть G и H – группы перестановок, определенные некоторыми генераторами групп. Генераторы представляются как перестановки над [1,...,n]. Проблема пересечения групп заключается в нахождении генераторов для GÇH. В работе показывается [BK], что можно построить программный чекер для данной проблемы.

Проблема расширенного нахождения НОД.

Проблема расширенного нахождения наибольшего общего делителя (которая отличается от нахождения НОД посредством алгоритма Евклида) заключается в нахождении для двух положительных целых a и b

целого d=НОД(a,b) и целых u и v таких, что au+bv=d.

Чекер для решения расширенного нахождения НОД по входу двух положительных целых a и b, целого d и целых u и v

выдать «Сбой», если d не делит a или d

не делит b или au+bv¹d. В противном случае выдать «Норма». Эффективность и корректность данного чекера легко доказывается.

Типовой потрет хакера

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

В первом случае отмечается, что многие хакеры обладают следующими особенностями [СМ]:

·     мужчина: большинство хакеров - мужчины, как и большинство программистов;

·     молодой: большинству хакеров от 14 до 21 года, и они учатся в институте или колледже. Когда хакеры выходят в деловой мир в качестве программистов, их программные проекты источают большую часть их излишней энергии, и корпоративная обстановка начинает менять их жизненную позицию. Возраст компьютерных преступников показан на рис. 15.1 [СМ];

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

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

·     увлечен компьютерами: для многих пользователей компьютер - это необходимый рабочий инструмент. Для хакера же - это «удивительная игрушка» и объект интенсивного исследования и понимания;

·     отсутствие преступных намерений: по данным [СМ] лишь в 10% рассмотренных случаев компьютерной преступности нарушения, совершаемые хакерами, привели к разрушению данных компьютерных систем. В связи с этим можно предположить, что менее 1% всех хакеров являются злоумышленниками.

Рис. 15.1. Возрастное распределение обнаруженных



компьютерных преступников

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

Криминальные сообщества и группы, сценарий взлома

компьютерной системы

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

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

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

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

Умножение матриц

N

M(n)

Определение детерминанта

N

Устойчивость, линейная и единичная состоятельность

Пусть свойствоI выражается уравнением I(x1,...,xk)=0, где кортеж (áx1,...,xk) выбирается с распределением E из пространства Dk. Пара (I,E) характеризует семейство функций F, где fÎF тогда и только тогда, когда для всех (x1,...,xk) с ненулевой выборкой элементов кортежа из E, I f(x1,...,xk)=0. Базовой техникой самотестирования является идентификация свойства устойчивости для семейства функций F. Неформально (D,D¢)-устойчивость пары (I,E) для семейства функций G

реализует, что если для программы PÎG, свойство IP(x1,...,xk)=0 удовлетворяется с высокой вероятностью, когда áx1,...,xkñ выбрано с распределением E из Dk, тогда существует функция gÎFÇG, которая согласуется с P на большей части входов из D¢.

Рассмотрим некоторое свойство линейности (I,E), где свойство I f(x1,x2,x3) тождественно f(x1)+f(x2)=f(x3) и E означает (x1ÎRZp,x2ÎRZp,x1+x2). Пара (I,E) характеризует F={f(x)=cx½cÎZp} – множество всех линейных функций над Zp. В этом примере G – тривиальное множество всех функций и пара (I,E) устойчива для G.

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

Существует два базовых теста для самотестирующихся программ – тест линейной состоятельности и тест единичной состоятельности [BLR]. Продемонстрируем построение таких тестов на примере следующей тривиальной модулярной функции. Пусть x,R – положительные целые, тогда fR(x)ºx (mod R), где R - фиксировано.

Пусть x1 и x2 случайно, равновероятно и независимо от других событий выбраны из ZR2n и x принимает значение: x:ºx1+x2(mod R2n). Необходимо отметить, что fR(x)º[fR(x1)+fR(x2)](mod R) – линейная функция по всем входам (аргументам). Тогда тест линейной состоятельности заключается в выполнении или не выполнении равенства: PR(x)º[PR(x1)+PR(x2)](mod R), а ошибка линейной состоятельности – есть вероятность того, что данный тест не выполнился.

Пусть z случайно выбрано из ZR2n в соответствии с распределением

 и z принимает значение: z¢:ºz+1(mod R2n). Отметим также, что fR(z¢)º[fR(z)+1](mod R). Тогда тест единичной состоятельности заключается в выполнении или не выполнении равенства: PR(z¢)º[PR(z)+1](mod R), а ошибка единичной состоятельности – есть вероятность того, что данный тест не выполнился.

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

www.kiev-security.org.ua BEST rus DOC FOR FULL SECURITY

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

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

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

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

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

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

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

участников протокола или n

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

·     корректности,

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

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

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

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

Задача конфиденциального вычисления была впервые сформулирована А. Яо для случая с двумя участниками в 1982 г. [Y1]. В 1987 г. О. Голдрайх, С. Микали и А. Вигдерсон показали [GMW], как безопасно вычислить любую функцию, аргументы которой распределены среди участников в вычислительной установке (то есть в конструкции, где потенциальный противник ограничен в действиях вероятностным полиномиальным временем).


В их работе рассматривалась синхронная сеть связи из n

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

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

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

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

Вопросы стойкости инкрементальных схем

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

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

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

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

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

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

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

Возможные методы защиты программ от потенциально опасных инструментальных средств

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

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

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

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

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

Для упорядочения операций с функциональными диаграммами вводится понятие ранга функциональных связей. Выходная функциональная связь (ФС) относится к рангу r=1. К рангу (i+1) относится ФС, выходы которых являются входами ФС ранга i. Ранжирование ФС завершается после определения рангов для всех связей. Необходимо отметить, что если в функциональной диаграмме выход некоторой ФС разветвляется, то может оказаться, что ФС, уже отнесенная к некоторому рангу, в соответствии с описанным правилом должна быть отнесена к другому, большему рангу. В этом случае ФС относится к большему рангу. Максимальное значение ранга ФС называется рангом функциональной диаграммы.

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

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


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

(неопределенное). Если значение аргумента y

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

www.kiev-security.org.ua BEST rus DOC FOR FULL SECURITY

Функциональная диаграмма характеризуется вектором состояния P, размерность которого равна сумме числа ФС и числа входных условий. Каждый разряд вектора P

представляет значение либо команды, либо ФС и может принимать одно из 3-х значений: 0, 1 или х. Считается, что значение разряда вектора P

определено, если в нем записан 0 или 1.

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

·        алгоритм построения вырожденного покрытия функциональной диаграммы (алгоритм А);

·        алгоритм определения множества комбинаций входных команд для заданной совокупности событий (алгоритм Б);

·        алгоритм вычисления эталонных значений событий для заданных тестовых наборов команд (алгоритм В).

 

Алгоритм А

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

состоит из следующих процедур.

1. Любым известным методом [Н] находится минимальная дизъюнктивная нормальная форма (МДНФ) функции f и ее отрицания.

2. Находятся кубы ВП, соответствующие значениям f=1. Для этого каждый простой импликанте ставится в соответствие куб, значения разрядов которого формируются по следующим правилам:



2.1. Если переменная входит в импликанту без отрицания, то в кубе, в котором f=1, ей соответствует 1, если же переменная входит с отрицанием, то значение 0;

2.2. Если переменная не входит в импликанту, то в кубе ей соответствует х.

3. Находятся кубы ВП, соответствующие значениям f=0. Для этого к МДНФ отрицания функции f

применяют правила, определенные пунктом 2 алгоритма А.

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

Таблица 9.1

Функции
И	ИЛИ	НЕ
y1	y2	f	y1	y2	f	y	f
0	x	0	1	x	1	0	1
x	0	0	x	1	1	1	0
1	1	1	0	0	0	-	-

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

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

а) номера 1,...,а присваиваются входным командам в произвольном порядке;

б) номера а+t,...,b, t³1 присваиваются функциональным связям так, что номер выходного условия ФС (события) всегда больше номера ее любого входного условия (команды).

2. Строится таблица, имеющая d столбцов (d

- количество ФС).

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

Для реализации алгоритма Б

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



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

Алгоритм Б

1. Начальная установка номера шага j:=0.

2. Из вектора Рj состояния ФД выбирается ФС Sh с наибольшем номером, ранее не рассматривавшаяся, значение которой в Рj определено (0 или 1).

3. Если Sh есть входное условие ФД, то алгоритм завершается, т.е. значения входных условий, определенных в Рj, являются искомыми.

В противном случае выполняется п.4.

4. Из таблицы вырожденных покрытий ФС выбираются кубы Kh(1),...,Kh(k), в которых значения ФС совпадают со значениями, определенными в Рj, а значения входных условий ФС не противоречат их значениям в Рj. Противоречие имеет место тогда и только тогда, когда значение входного условия в кубе Kn(i) равно 0(1), а в Рj противоположное - 1(0). Если h больше наименьшего номера ФС, значение которого определено в Рj, но из вырожденного покрытия ФС Sh нельзя выбрать ни одного куба, удовлетворяющего указанным условиям, то Рj не реализуем, т.е. не существует комбинации входных условий, при которой значение следствий соответствует Рj.

5. Находится множество векторов Pj(1),...,Pj+1(k) за счет поразрядного пересечения расширенных кубов Kh(1),...,Kh(k) вырожденного покрытия Sh с вектором Рj: Pj+1(i) =PjP{Kh(i)}, i=1,...,k, причем операция П выполняется по следующим правилам: выбранные кубы расширяются за счет присвоения всем неопределенным ФС значения х, 1П1=1, 0П0=0, 1Пх=1, 0Пх=хП0=0, 1П0=0П1=d.

6. j:=j+1; пункты 2-5 выполняются для каждого из найденных векторов Pg(i), i=1,...,k.

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



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

·        Е(x1,...,xn) - запрещены комбинации входных условий, в которых более одной переменной равны 1;

·        I(x1,...,xn) - запрещена комбинация входных условий, в которых все xi=0;

·        О(х1,х2) - одно и только одно из значений х1 и х2 должно иметь место, т.е. запрещены комбинации (х1=1, х2=1) или (х1=0, х2=0);

·        R(x1,x2) - запрещена комбинация (х1=0, х2=0).

Возможны комбинации ограничений, например, Е(x1,...,xn) и R(xi,xj), (i,j)=1,...,n. В общем случае ограничение может быть задано указанием произвольного множества запрещенных комбинаций команд (входных условий). Учет ограничений может быть осуществлен следующими способами.

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

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



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

Алгоритм В

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



Задача, решаемая данным алгоритмом, формируется следующим образом.

Дано:

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

·        вектор Р(0) состояния функциональной диаграммы, соответствующий тестовому набору ХТ.

Требуется: найти для исследуемых средств значения реакций, соответствующие вектору Р(0).

Решение данной задачи осуществляется следующим образом.

Алгоритм В

1. Начальная установка номера шага алгоритма j:=1.

2. В векторе Рj-1 определяется функциональная связь Sg

с минимальным номером, значение которой не определено, а хотя бы одно входное условие этой ФС имеет значение 0 или 1. Так как в соответствии с принятым правилом нумерации номер ФС всегда больше номера любого ее входного условия, то g³V+j, где V

- число входных условий ФС. Поэтому при выполнении этой операции следует анализировать значения ФС с номерами V+j,V+j+1,...,V+N-1, где N

- число ФС.

3. Из вырожденного покрытия ФС Sg

выбирается куб Khg, значения компонентов которого не противоречат значениям соответствующих компонентов вектора состояния Рj-1. Противоречие отсутствует, если для всех компонентов куба Khg выполняются следующие условия:

3.1. Если в кубе компонент а имеет значение х, то в векторе Р(j-1) значение компонента а может быть 0, 1 или х;

3.2. Если в кубе Khg компонент а имеет значение d, d=0,1, то и в векторе Рj-1

этот компонент должен иметь значение d.

4. Если не выбрано ни одного куба, то Рj=Рj-1 и осуществляется переход к п.6,  в противном случае – к п.5.

5. Формируется вектор Рj состояния ФД, разряды которого образуются с помощью операций П поразрядного пересечения (см. п.5 алгоритма Б) компонентов выбранного куба Kgh с соответствующими компонентами вектора Рj-1

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

6. Если g<N+V, то осуществляется переход к п.7. В противном случае алгоритм завершается.

7. j:=j+1, переход к п.2.

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

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

Рис.4.8. Псевдокод алгоритма самокорректирующейся

программы умножения матриц

Время выполнения программы S_K_multAB составляет О(M(n)+n2log(1/k)), где M(n) – время выполнения программы умножения матриц размером n´n [BLR].

Самотестирующаяся программа для умножения матриц строится достаточно просто.

 

Program S_T_multAB(A,B,k); {вход A,B,k, выход («Норма»,«Сбой»)}

         begin

               for i=1 to O(log(1/k))¥ do

            begin

                       A:=random(F);            {random - функция случайного равновероятного и независимого выбора матрицы размером (n´n) из F};

                       B:=random(F);            {random - функция случайного равновероятного и независимого выбора матрицы размером (n´n) из F};

                       C:=P(A,B);

                       if C_F(A,B,C,1/4)=«Норма» then output 0 and goto 1;

                       if C_F(A,B,C,1/4)=«Сбой» then output 1 and goto 1;

          end;

1:end.

Вводная часть

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

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

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

Помимо этих двух основных инструментов исследования, можно использовать:

·

«дискомпиляторы», программы, генерирующие из исполняемого кода программу на языке высокого уровня;

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

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

Вводные замечания

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

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

Будем говорить, что инкрементальное шифрование является стойким относительно некоторой операции модификации, если (для данной последовательности шифртекстовЕ1,...,Et  над соответствующими открытыми данными Di, i=1,...,t и при инкрементальном получении каждой последовательности Еi, из предыдущих шифртекстов Ei-1) извлечение какой-либо информации об оригинальном документе D1, также как и его измененных версиях D2,.., Dt (за исключением того факта, что Di получено посредством применения этой операции модификации к открытым данным Di-1) не возможно. Аналогично, рассмотрим любые две последовательности А=(А1,...,Аt) и В=(В1,...,Bt) так, что A1,B1ÎSl, где S - используемый алфавит. Данные Аi

(отн., Вi) получены заменой единственного символа в Ai-1

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

и соответствующих «команд замены» данных В.

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

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

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

- произведение двух больших простых чисел, или на трудности вычисления дискретных логарифмов в поле GF(p), p

- большое простое число. Чтобы противостоять известным на данный момент методам решения этих задач операнды должны иметь длину порядка 512 или 1024 битов. Понятно, что выполнение вычислений над операндами повышенной разрядности (еще будет употребляться термин «операнды многократной точности» по аналогии с операндами однократной и двукратной точности [Кн]) требует высокого быстродействия рабочих алгоритмов криптографических схем.

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

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

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

www.kiev-security.org.ua BEST rus DOC FOR FULL SECURITY

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

в 1993 г. были введены в работах [BLR,L1]. В свою очередь, методология самотестирования явилась результатом объединения трех основных идей из криптографии, вероятностных алгоритмов и тестирования программ [BK]. К ним относятся интерактивные системы доказательств и интерактивные системы доказательств с нулевым разглашением [GMR]. Кроме этого, большое значение имели работы М.О. Рабина по вероятностным вычислениям (см., например, [Ра]) и работа латышского математика Р. Фрейвалдса [F], написанная им еще в 1979 году. Он предложил простой и элегантный чекер для задачи умножения матриц, который можно также эффективно применить и для целочисленного умножения и для умножения полиномов.

В этом разделе рассматриваются теоретические аспекты защиты программ от копирования. Эта задача защиты может сводиться к задаче эффективного моделирования RAM-машины (машины с произвольным доступом к памяти(см. приложение и [АХУ]) посредством забывающей RAM-машины. Следует заметить, что основные результаты по данной тематике принадлежат О. Голдрайху и Р. Островски [GO,O] и эти исследования активно продолжаются в настоящее время.

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

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

Отметим, что тривиальное решение для забывающего моделирования RAM-машины заключается в полном сканировании фактической памяти RAMk-машины для каждой операции доступа к виртуальной памяти (которая должна быть выполнена для оригинальной RAM-машины). Далее описывается первое нетривиальное решение [GO,O] задачи забывающего моделирования RAMk-машины посредством вероятностной RAM'k'. Это решение еще называется решением задачи «Квадратного корня»[GO].

Пусть заранее известен объем памяти, обозначаемый m, требуемый для соответствующей программы. Ниже мы показываем, как моделировать такую RAM-машину посредством забывающей RAM-машиной с объемом памяти m+2

 таким образом, что t шагов оригинальной RAM-машины моделируются за O(t) шагов на забывающей RAM-машине.

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

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

Выбор номенклатуры показателей качества

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

·

определение нормативно-технических документов, устанавливающих систему показателей качества ПО;

·          формирование из установленной системы показателей номенклатуры показателей качества оцениваемого ПО по i-ому уровню иерархии и установление логических связей между показателями;

·          определение каждого выбранного показателя качества ПО i-го уровня;

·          доказательство полноты и непротиворечивости выбранной номенклатуры показателей качества i-го уровня.

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

1). Объединение всех множеств Q1

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

2). Множество Q1 показателя качества верхнего уровня должно совпадать или быть вложенным в объединение множеств Q1 подчиненных показателей всех нижних уровней.

3). Множество Q2 показателей верхнего уровня должно соответствовать цели оценки качества ПО.

4). Должна существовать измеримая функция, ставящая в соответствие каждому элементу множества Q2

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

5). Между элементами множества Q2

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

6). Множество Q3 показателя i-го уровня должно совпадать с объединением множеств Q3

подчиненных показателей i-го уровня.

7). Для множеств Q4 справедливо правило 1.

Расширение и уточнение этих правил устанавливается в методиках (методических материалах) по оценке качества конкретных ПО.

Вычисления на линейном вентиле

Ниже описывается вычисления на линейном вентиле вместо простого аддитивного вентиля. Это более обобщенное описание будет удобно для протокола вычисления на мультипликативном вентиле.

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

 - линейный вентиль, где a1,...,ak – входные линии вентиля, a1,...,ak

- фиксированные коэффициенты и c

– выходная линия. Пусть Aj(·) – полином, ассоциированный с j-той входной линией. А именно доля процессор Pi на этой линии – есть ai,j=Aj(i). Каждый процессор Pi локально устанавливает свою долю выходной линии в

. Можно легко увидеть, что доли c1,...,cn определяют случайный полином C(·) степени t с корректным свободный коэффициентом и с C(i)=Ci для всех i.

Вычисления на мультипликативном вентиле

Пусть c=a·b – мультипликативный вентиль и пусть A(·), B(·) – полиномы, ассоциированные с входными линиями, а именно доли каждого процессора Pi

этих линий - A(i) и B(i) соответственно. Процессоры совместно вычисляют свои доли случайного полинома C(·) степени t, удовлетворяющий C(0)=A(0)·B(0), а именно доля каждого несбоящего процессора Pi на выходной линии будет C(i).

Сначала каждый процессор локально вычисляет свою долю полинома E(·)=A(·)·B(·), устанавливая E(i)=A(i)·B(i). Ясно, что E(·) имеет требуемый свободный коэффициент. Однако, полином E(·) имеет степень 2t и, кроме того, полином не является равномерно распределенным. Процессоры используют свои доли полинома E(·), чтобы вычислить свои доли требуемого полинома C(·) безопасным способом. Вычисления осуществляются в два этапа: на первом этапе процессоры совместно генерируют случайный полином D(·) степени 2t такой, чтобы D(0)=E(0). А именно, каждый процессор Pi будет иметь D(i). Затем, стороны используют их доли D(·), чтобы совместно вычислить свои доли полиномаC(·). Эти шаги описаны ниже.

Рандомизация. Сначала покажем, как генерируется полином D(·). Сначала процессоры генерируют случайный полином H(·) степени 2t и с H(0)=0; а именно, каждая сторона Pi будет иметь H(i). Мы сначала описываем, как полином H(·) делится в синхронной модели вычислений [BGW].

Каждый процессор Pi выбирает случайный полином Hi(·) степени 2t с Hi(0)=0 и делит его среди процессоров; а именно, каждый процессор Pj

получает Hi(j). Полином H(·) – устанавливается в H(·)=

j(·); а именно каждый процессор Pi вычисляет H(i)=j(i).

В асинхронной модели вычислений процессор не может ждать, пока получит свою долю от всех других процессоров. Вместо этого, стороны соглашаются, используя субпротокол СОАМ, о множестве C процессоров, которые успешно разделили полиномы Hi. Затем полином H(·) будет установлен в H(·)=

(·). Другими словами, процессоры запускают протокол АГПРС, получают на выходе (C,f{Hj(i)½jÎC}) и каждый процессор Pi вычисляет H(i)=(i).

Полином D(·)теперь определен как D(·)=E(·)+H(·); а именно каждый процессор Pi вычисляет D(i)=E(i)+H(i). Ясно, что D(0)=A(0)·B(0) и все другие коэффициенты D(·) равномерно и независимо распределены над F.

Редукция степени. На этом этапе процессоры используют свои доли полинома D(·), чтобы совместно и безопасно вычислить свои доли случайного полинома C(·) степени t с C(0)=D(0). Полином C(·) будет устанавливать «усечение» полинома D(·) к степени t; а именно t+1 коэффициентов C(·) являются коэффициентами t+1 более низкой степени полинома D(·). Важный момент здесь состоит в том, что информация, которую накапливают сбоящие процессоры (а именно t долей полинома D(·) вместе с t долями усеченного полинома C(·)), независима от C(0).

Пусть =D(1),...,D(n) и пусть =C(1),...,C(n). В работе [BGW] отмечено, что существует фиксированная матрица M

размерностью n´n такая, что =. Отсюда следует, что требуемый выход каждого процессора Pi - линейная комбинация входов процессоров: C(i)=[]i=. Будем называть такую операцию «умножение входов на фиксированную матрицу». В этом случае, входы процессоров являются их долями полинома D(·).

В синхронной модели вычислений умножение входов на фиксированную матрицу может быть выполнено посредством безопасного вычисления соответствующих n фиксированных линейных комбинаций входов таких, что значение i-той линейной комбинации вскрываемо только процессором Pi. Линейные комбинации безопасно вычисляются следующим образом. Сначала каждый процессор разделяет свой вход; затем каждый процессор вычисляет линейную комбинацию своих долей и открывает эту линейную комбинацию специальному процессору; в заключение специальный процессор вычисляет значение выхода, интерполируя полином степени t из полученных комбинаций [Ca2].

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


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

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

Определение 3.7.

Пусть A – матрица размерностью n´n и пусть SÍFn - множество входных векторов. Будем говорить, что S – t-умножаемо на A, если для каждого множества GÍ[n] с |G|³n-t существует (легко вычислимая) матрица AG размером |G|´n такая, что для каждого входа ÎS мы имеем G·AG=A.

Пусть S – t-умножаемо на A. Тогда протокол, описанный ниже, «умножает входы из множества S

на матрицу». Пусть ÎS. Процессоры сначала выполняют протокол АГПРС (с входным вектором ). Как только общее множество G

вычислено, каждый процессор локально вычисляет AG. Затем, процессоры запускают n протоколов восстановления секрета АВс, где в i-том протоколе АВс процессоры позволяют процессору Pi вычислить G·AG, посылая ему соответствующую линейную комбинацию своих долей. Ниже описывается протокол для умножения входа на фиксированную матрицу.

Протокол МАТ (xi,A)

Процессор Pi на входе xi и матрице A работает следующим образом.

1. Устанавливает (t,xi)АГПРС=(G,{si,j½G}).

2. Нумерует G=g1,...,g|G| и пусть в этом случае =.

3. Вычисляет AG.

4. Для 1£k£n

устанавливает ([·AG]k,t,{k})Авс=yk.

Подает на выход yi.

Далее будем говорить, что входной вектор  есть – d-сгенерирован, если существует полином P(·) степени d, удовлетворяющий xi=P(i) для каждого i; множество возможных входов на шаге редукции степени – это множество 2t-сгенерированных векторов.

Для дальнейших рассуждений нам необходима матрица особого вида. Эта матрица, назовем ее M, описана в работе [BGW] и строится как



М=V-1TV, где V – матрица Вандермонда размерностью n´n (см, например, [Кн, стр.474]), определенная как Vi,j=ij, а T построена установкой всех элементов, кроме элементов первых t+1 столбцов, единичной матрицы в нули. (Пусть , - вектора, определенные выше). Для того чтобы увидеть, что ·М= необходимо заметить, что ·V -1

– это вектор коэффициентов полинома D(·) и, таким образом, V -1T – вектор коэффициентов полинома C(·) и V-1TV=).

Пусть GÍ[n] с |G|³n-t и пусть

G=g1,...,g|G|. Матрица MG строится следующим образом. Пусть матрица VG

размерностью |G|´|G| - это матрица V, спроектированная на индексы из матрицы G; а именно =(gi)j.Далее строиться матрица  размерностью |G|´n, присоединением n-|G| нулевых столбцов к (VG)-1. В итоге установить MG=TV, где T – определена выше.

Так как n³3t+1 мы имеем |G|³2t+1. Можно проверить, что в этом случае ·- тоже вектор коэффициентов полинома D(·), а именно ·=·V-1. Таким образом, TV=V-1TV=M.                  <

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

Субпротокол MUL(ai,bi)

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

1. Установить (t)АГПРС=(C¢,{hi,j½jÎC¢}).

2. Пусть di=ai·bi+.

3. Пусть Mn´n – матрица, определенная выше как M.

4. Установить (di,M)MAT=ci.

Подать на выход ci.

Вычисления над матрицами

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

Program P_S_T(P,e,b,x,f(x)); {вход P,e,b,(x1,f(x1)),...,xd+1,f(xd+1))),

выход («Норма»,«Сбой»)}

  begin

        for i=1 to O((1/k)log(1/b)) do

            begin

               x,t:=random(Zp);          {random - функция случайного равновероятного выбора из множества вычетов по модулю р};

                       if

(более, чем в e

итерациях) then output «Сбой»;

          end;

  output «Норма»;

        for j=0 to d do

            begin

                       for i=1 to O(log(d/b)) do

begin

                                  t:=random(Zp); {random - функция случайного равновероятного выбора из множества вычетов по модулю р};

                                  if

(более, чем в ¼

итерациях) then output «Сбой»;

                            end;

          end;

          output «Норма»;

end.

Вычисления над полиномами

Существует достаточно простой способ построения самокорректирующейся программы, который основывается на существовании следующего интерполяционного тождества, соответствующего значения функций между точками: для всех одномерных полиномов f степени не более d, для всех x,tÎF,

, где ai – различные элементы из F, ai=-1 и ai зависит от F,d и не зависит от x,t. Тогда самокорректирующаяся программа для вычисления f()=f(x1,...,xn) заключается в выполнении следующего алгоритма. Случайно и равновероятно выбирается =(t1,...,tn) и выдается . С вероятностью не менее 2/3 все вызовы программы будут возвращать корректные результаты и, следовательно, выход программы будет корректным. Рис.4.6 демонстрирует самотестирующуюся программу для полинома f.

В ряде работ было показано, как строить самотестирующиеся и самокорректирующиеся программы для задач сложения и умножения полиномов [BLR,GLR] и аппроксимирующие чекеры для полиномов [EKR] (см. далее).

Вычисления при By-сбоях

Как и в случае FS-сбоев нам необходимо вычислить функцию f:Fn®F. Предположим, что процессоры имеют общую арифметическую схему для вычисленияf. Ниже описывается n-сторонний протокол для безопасного

t-вычисления f в асинхронной сети с произвольными (то есть, при By-сбоях) противниками, при условии n³4t+1.

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

Пусть c=a·b – мультипликативный вентиль и пусть A(·), B(·) – полиномы, ассоциированные с входными линиями, а именно доли каждого процессора Pi

этих линий - A(i) и B(i) соответственно и A(0)=a и B(0)=b. Как и в случае FS-сбоев процессоры совместно вычисляют свои доли случайного полинома C(·) степени t, где C(0)=A(0)·B(0), так, что доля каждого несбоящего процессора Pi

на выходной линии будет C(i).

Процедура умножения при By-сбоях следует из соответствующей процедуры, но для FS-сбоев. А именно, процессоры сначала генерируют случайный полином D(·) степени 2t со свободными коэффициентами D(0)=A(0) ·B(0). Тогда процессоры вычисляют свои доли усеченного полинома D(·) степени t

и этот усеченный полином есть выходной полином C(·).

Собственно сама процедура умножения начинается с описания двух модифицированных шагов: умножения и редукции степени.

Рандомизация. Отличие от случая для FS-сбоев состоит в том, как каждый процессор Pi

делит полином Hi(·) степени 2t с Hi(0)=0. Для этого используется следующий метод [BGW]. Каждый процессор Pi делит t равномерно выбранных значений, используя t вызовов субпротокола АРзПр. Пусть zi,j,k, - выход процессора Pk

при j-том вызове АРзПр, где Pi - дилер. После завершения всех t вызовов АРзПр, каждый процессор Pk локально вычисляет Hi(k)=

.

Для этого пусть Si,j(·) – полином степени t определенный j-тым вызовом АРзПр, инициированным Pi (а именно, Si,j(k)=zi,j,k для каждого несбоящего процессора Pk).
Полином Hi(·) теперь определен как Hi(x)=

. Каждый процессор Pk

локально вычисляет Hi(k)==. Пусть si,j,l

- коэффициент xl в Si,j(x). Это можно показать как

Hi(x)=

=si,1,0x

+

si,1,1x2

+

...

+

si,1,t-1xt

+

si,1,txt+1

+

si,2,0x2

+

...

+

si,2,t-2xt

+

si,2,t-1xt+1

+

si,2,txt+2

+

...

si,t,0xt

+

si,t,1xt+1

+

...

+

si,t,tx2t

Свободный коэффициент Hi(·) равен 0 и, таким образом, Hi(0)=0. Каждый полином Si,j(·) имеет степень t и, таким образом, Hi(x) имеет степень 2t. Кроме того, можно заметить, что коэффициенты членов x,...,xt в Hi(x) равномерно распределены над F. Следовательно, коэффициенты всех ненулевых степеней усеченного полинома C(·) равномерно распределены над F.

Ясно, что сбоящие процессоры накапливают некоторую дополнительную информацию относительно t

долей Hi(·). Однако эта информация независима от A(0)·B(0), так как процессор Pi выбирает t2+t случайных коэффициентов, а сбоящие процессоры получает только t2 значений.

Редукция степени. Процессоры используют свои доли полинома D(·) для совместного и конфиденциального вычисления своих долей «усечения» полинома D(·) степени t. А именно t+1 коэффициентов выходного полинома C(·) являются коэффициентами D(·) с более низкой степенью.

В протоколе для FS-сбоев процессоры вычисляли свои доли C(·), вызывая протокол для «умножения вектора входов на  фиксированную матрицу».

В протоколе для By-сбоев процессоры используют субпротоколы АРзПр и АВсПр вместо простой схемы разделения секрета для FS-сбоев.


Однако проблема заключается в том, что согласованное множество  G может содержать сбоящие процессоры Pi, совместно использующие некоторое значение, отличное от ожидаемого значения D(i). В этом случае, процессоры не будут иметь требуемых выходов.

Далее мы описываем, как процессоры Pi могут удостовериться в том, что значение, связанное с каждым процессором Pi в согласованном множестве (а именно, свободный коэффициент полинома степени t, определенного долями несбоящих процессоров Pi) – действительно D(i).

Для процессоров Pi пусть si - значение, связанное с Pi; для множества A процессоров, пусть SA=f{(i,si)½PiÎA}. Cначала отметим, что достаточно договориться о множестве G из, по крайней мере, 3t+1 процессоров, такое, что SG

является (2t,0)-интерполируемым (а именно, все значения, общедоступные для процессоров из G «находятся на полиноме степени 2t»). Это так, потому, что множество G размером 3t + 1, содержит, по крайней мере, 2t+1 несбоящих процессоров. Таким образом, интерполируемый полином SG

связан (ограничен) с полиномом D(·).

Далее описывается протокол для соглашения по множеству A процессоров такому, что SA является (2t,0)-интерполируемым. Этот протокол, обозначаемый СОИМ - Соглашения об интерполируемом множестве, является «распределенным вариантом» схемы СКОП, описанной выше.

Протокол СОИМ состоит из t итераций. На итерации r (0£r£t), процессоры сначала используют протокол СОАМ

(см. выше) чтобы договориться о множестве Gr, состоящее из, по крайней мере, 3t+1+r процессоров, которые успешно объединяют свои входы. Затем, стороны выполняют вычисления, описываемые ниже, для проверки, является ли множество  (2t,r)-интерполируемым. Если  является (2t,r)-интерполируемым, тогда существует множество Gr¢ÍGr размером из, по крайней мере, 3t+1 процессоров такое, что  является (2t,0)-интерполируемым. Тогда процессоры вычисляют и выдают Gr¢.


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

Остается только описать, как проверить по данному множеству G размера 3t+1+r является ли SG (2t,r)-интерполируемым, и как вычислить соответствующее множество G¢ (то есть, G¢ÍG, ½G¢½³3t+1 и SG¢

является (2t,0)-интерполируем). Как и в процедуре СКОП, мы используем обобщенные коды с исправлением ошибок Рида-Соломона. Однако, в процедуре СКОП «слово» SG, было (динамическим) входом для одного процессора и, таким образом, каждый процессор мог бы локально запускать процедуру, реализующую схему с исправлением ошибок. В данной установке, каждый процессор имеет только одну долю каждого элемента SG; стороны будут вызывать совместные вычисления, выполняющее специфическую процедуру, реализующую схему с исправлением ошибок и использовать это для проверки, является ли G - (2t,r)-интерполируемым и вычисления G¢.

Сначала опишем частичную процедуру с исправлением ошибок. Входы для этой процедуре - (d,r,W). Если ½W½³d+2r+1 и W является

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

Процедура СОИМ

Вычисление синдрома.

Для входного слова W=(i1,s1)...(il,sl), пусть Vl´l – матрица Вандермонда (см., например, [Кн, стр.474]), определенная как Vj,k=(ik)j. Пусть =s1...sl. Синдром W

есть

l-(d+1) наибольших правых элементов l-размерного вектора произведения ·V-1. Таким образом, на этом шаге вычисляется синдром W.

Вычисление вектора погрешности. Вектор погрешности – это l-размерный вектор =e1...el, где ej

– «смещение sj от правильного значения».


А именно, предположим, что W

- (d,r)-интерполируем и пусть P(·) - (d,r)-интерполируемый полином W. Тогда ej=P(ij)- sj алгоритм для каждого элемента (ij,sj)ÎW. Вектор погрешности уникален, так как интерполируемый полином P(·) – уникален. (Отметим, что вектор погрешности может быть вычислен только на основании синдрома. Если входное слово W - не является (d,r)-интерполируемым, тогда вычисленный вектор погрешности может быть ошибочным).

Вычисление выходного полинома. Выбрать 2t+1 корректных элементов из W (а именно, элементы (ij,aj) такие, что ej=0) для использования их, чтобы интерполировать P(·). (Этот шаг не будет выполнен).

Важно отметить, что синдром может быть представлен как функция только от вектора погрешности и, таким образом, он не содержит никакой информации относительно (d,r)-интерполируемого полинома P(·). А именно, пусть  (в отн. ) - вектор коэффициентов полинома P(·) (в отн.  Q(·)) длины l. (Полином Q(·) - полином, удовлетворяющий Q(i)=a для каждой пары (i,a)ÎW). Тогда =·V-1=(·V+)·V-1=+·V-1.

Последние l-(d+1) элементов из  является нулевыми. Так как

l-(d+1)<i£l, мы имеем Qi=[·V]i. Следовательно, последние l-(d+1) элементов из  (т.е. синдром) являются линейной комбинацией  и, таким образом, процессоры могут совместно вычислять синдром. То есть для данного согласованного множества G, каждый элемент синдрома SG

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

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

Как только синдром вычислен, каждый процессор использует алгоритм Берлекампа-Месси, чтобы локально вычислить вектор погрешности. Если на итерации r  является (2t,r)-интерполируем, тогда вычисленный вектор погрешности является «истинным» вектором погрешности множества , однако, если  не является (2t,r)-интерполируемым, тогда вычисленный вектор погрешности может быть некорректным.


Следовательно, процессоры должны выполнить следующие действия. (Каждый выполняет эти операции локально, а все несбоящие процессоры выполняют одни и те же действия). Если вычисленный вектор погрешности, обозначаемый ¢ содержит более чем r ненулевых элементов, то несомненно  не является (2t,r)-интерполируемым и процессоры переходят к следующей итерации. Если ¢ содержит не более r ненулевых элементов, то процессоры все еще должны проверять, что ¢ - корректный вектор погрешности. Для этого пусть Gr¢ - множество процессоров Pi такое, что ei¢=0, тогда процессоры повторно вычисляют синдром, основанный только на Gr¢. Если повторно вычисленный синдром представляет собой одни нули, тогда  является (2t,0)-интерполируем и процессоры выдают Gr¢ и заканчивают. Если повторно вычисленный синдром ненулевой, тогда процессоры заключают, что  - не является (2t,r)-интерполируемым и переходят к следующей итерации.

Далее опишем непосредственно протокол СОИМ. Пусть zi,j - доля Pi' значения общего с Pj. Динамический вход каждого процессора Pi является следующим аккумулируемым множеством, обозначаемым как Zi: как только Pi успешно завершил субпротокол АРзПр для Pj, пара (j,zi,j) добавляется к Zi. Общий выход сторон – это множество G из, по крайней мере, 3t+1 процессоров такое, что каждый несбоящий процессор Pi завершает субпротокол АРзПр для каждой стороны из G (а именно, GÍ{Pj½(j,zi,j)ÎZi}) и SG – является (2t,0)-интерполируем.

Утверждение 3.1.

Предположим, что протокол СОИМ

инициализируется с динамическими входами Z1,...,Zn как описано выше. Тогда все несбоящие процессоры завершают протокол СОИМ

с общим множеством G из, по крайней мере, 3t+1 процессоров, такое, что SG является (2t,0)-интерполируемым.

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

Приведено в работе [Ca1].

 

Протокол СОИМ(Zi)

Код для процессора Pi на динамическом входе Zi.

Выполнить для 0£r£t.

1. Пусть Ui={Pj½(j,zi,j)ÎZi}.


Установить (t,r,n,Ui)СОБМ=G.

2. Как только G вычислено, вычислять синдром SG.

    2.1. Пусть V

- матрица индексов Вандермонда из G. А именно пусть G=k1...k½G½, тогда Vi,j=(kj)i.

2.2. Пусть .

2.3. Для 2t+1<j£½G½ установить ([·V-1]j,[n])АВсПр=sj.

2.4. Пусть , где s - синдром SG.

3. Инициализировать алгоритм Берлекампа-Месси для  и пусть ¢ - выход.

    3.1. Если ¢ имеет более чем r ненулевых элементов, продолжить следующую итерацию (в этом случае SG, не является (2t,r)-интерполируемым).

3.2. Если ¢ имеет не более чем r ненулевых элементов, проверить, что ¢ корректен.

3.2.1. Пусть G¢ - множество процессоров из G, чьи соответствующие записи в ¢ являются нулевыми. Повторить шаг 2 в отношении G¢.

3.2.2. Если синдром SG¢ является нулевым вектором, выдать G¢ и остановиться. В противном случае перейти к следующей итерации (SG не является (2t,r)-интерполируемым).

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

Протокол ByMUL

Код для процессора Pi, на входах ai и bi.

1. Рандомизация.

1.1.    Для 1£k£t выполнить АРзПрi,k по входу rk, где rkÎRF и Pi - дилер.

1.2.    Для 1£j£n и для 1£k£t участвуют в субпротоколах АРзПрj,k.

1.3.    Пусть hi,j,k – выход процессора Pi для субпротокола АРзПрj,k.

1.4.    Пусть Ui={Pj½АРзПрj,k завершен для всех 1£k£n}.

1.5.    Установить (n,t,Ui)СОАМ=G.

1.6.    Установить  и di=ai·bi+hi.

2. Редукция степени.

2.1. Как только di вычислено, выполнить АРзПрi(di), где Pi - дилер. Для 1£j£n

участвовать в субпротоколе АРзПрj.



2.2. Пусть zi,j – доля (процессора Pi) общего с Pj секрета и пусть Zi¢={(j,zi,j)½АРзПрj

был завершен}. Установить (Zi)СОИМ=G¢.

2.3. Пусть  - матрица, используемая на шаге умножения для FS-сбоев и пусть , где j1...j½G¢½

- индексы процессоров из G¢. Для 1£j£n

установить ([]j,{j})АРзПр=cj.

2.4. Как только ci вычислен, выдать ci.

Полная структура протокола для By-сбоев точно такая же, как для FS-сбоев. А именно, в таком протоколе, обозначаемом ByВыч, процессоры выполняют аналогичные инструкции протокола для FS-сбоев, за исключением того, что протоколы АГРз, MUL, и АГВс

заменены на протоколы АГПРС, ByMUL и АВсПр

соответственно.

Теорема 3.9.

Пусть f:Fn®F

для некоторой области F с ½F½>n

и пусть А - схема, вычисляющая f. Тогда протокол ByВыч по входу A асинхронно

(én/4ù-1)-безопасно вычисляет f в установке с ограниченно защищенными каналами и в присутствии адаптивных противников.

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

Приведено в работе [Сa2].

Вычисления при FS-сбоях

В данном разделе показывается, как надежно при наличии FS-сбоях

t-вычислить любую функцию, вход которой разделен между n

процессорами, когда n³3t+1.

Пусть F – конечное поле, известное всем процессорам и |F|>n. Пусть также f:Fn®F - вычислимая функция. Предположим, что процессоры имеют арифметическую схему, вычисляющую функциюf. Схема состоит из вентилей сложения и умножения степени 2. Добавление константы рассматривается как частный случай сложения. Все вычисления в выполняются в поле F.

Общее описание протокола выглядит следующим образом [BCG]. Пусть xi - вход процессора Pi. На первом шаге каждый процессор разделяет вход среди других процессоров, используя, например, схему разделения секрета Шамира (см. выше). А именно, для каждого процессора Pi, который успешно разделил свой вход, случайным образом генерируется полином pi(·) степени t, сгенерирован такой, что каждый процессор Pj имеет pi(j) и pi(0) - значение входа процессор Pi. Будем говорить, что pi(j) - доля pi(0) процессора Pi. Затем, стороны договариваются, используя протокол СОАМ,

о множестве С процессоров, которые успешно разделили свои входы. Как только C вычислено, процессоры начинают вычислять fC(

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

зафиксировано.

Для каждого вентиля процессоры используют свои доли входных линий для совместного и безопасного «генерирования» случайного полинома p(·) степени t, такого, что каждый процессор Pi вычисляет p(i) и p(0) - является выходным значением этого вентиля. А именно, p(i) - доля процессора Pi на выходной линии этого вентиля. Как только процессоры вычислили свои доли на выходных линиях всей схемы, процессоры восстанавливают свои доли на выходной линии и интерполируют выходное значение.

Вычисления в идеальной модели

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

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

Вычисления в идеальной модели

Вход.

Каждый из двух процессоров получает вход z.

Посылка входов доверенному процессору. Несбоящий процессор всегда посылает z доверенному процессору. Сбоящий процессор может, в зависимости от z, или прервать, или послать некоторый z¢Î{0,1}½z½ доверенному процессору.

Доверенный процессор «отвечает» первому процессору. В случае если была получена входная пара (x,y) доверенный процессор, вычисляя f, сначала отвечает первому процессору f1(x,y). В противном случае (то есть, когда получен только один вход) доверенный процессор отвечает обеим сторонам с специальным символом Ñ.

Доверенный процессор «отвечает» второму процессору. В случае если первый процессор нечестен, то доверенный процессор посылает Ñ второму процессору и останавливается. В противном случае (то есть, если не останавливается) доверенный процессор посылает f2(x,y) второй стороне.

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

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

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

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

Вычислительная математика

www.kiev-security.org.ua BEST rus DOC FOR FULL SECURITY

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

Зачем и от кого нужно защищать программное обеспечение компьютерных систем

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

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

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

·

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

·     каковы возможные мотивы действий субъекта, осуществляющего разработку таких дефектов?

·     как можно идентифицировать наличие программного дефекта?

·     как можно отличить преднамеренный программный дефект от программной ошибки?

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

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

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

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

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

·

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

·     каковы возможные мотивы действий субъекта, осуществляющего разработку таких дефектов?

·     как можно идентифицировать наличие программного дефекта?

·     как можно отличить преднамеренный программный дефект от программной ошибки?

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

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


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

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

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

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

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

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

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

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

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



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

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

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

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

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

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


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

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

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

·     что может сделать злоумышленник («пират») в ходе попыток изучения программы?

·     что является существенными знаниями о программе?

·     что является спецификацией программы?

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

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



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

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

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

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

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

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

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

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

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



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

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

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

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

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

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


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

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

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

·     что может сделать злоумышленник («пират») в ходе попыток изучения программы?

·     что является существенными знаниями о программе?

·     что является спецификацией программы?

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

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

Спектральный анализ методом

z
d
Подавление шума
z1,...,zs
(эталонные источники

шума)
Сигнал +шум
Подавление помех

(адаптивная обработка с фиксированными

лучами)
b1,...,bs
(эталонные источники

шума)
b0
(выходной сигнал луча,

ориентированного в данном направлении)
Спектральный анализ методом максимума

энтропии
x1,...,xs
(эталонные источники

шума)
xs+1

Задача «Изоморфизм графа»

Приведем в качестве примера протокол доказательства с абсолютно нулевым разглашением для языка «Изоморфизм графов» из работы[GMW]. Входным словом является пара графов G1=(U,Е1) и G0=(U,E0). Здесь U - множество вершин, которое можно отождествить с множеством натуральных чисел {1,...,n}, Е1

и Е0 множества ребер такие, что |Е1|=|Е0|=m. Графы G1 и G2 называются изоморфными, если существует перестановка на множестве U такая, что (u,v)ÎЕ0

тогда и только тогда, когда (j(u),j(v))ÎЕ1

(обозначается G1=jG0). Задача распознавания изоморфизма графов хорошо известная математическая задача, для которой на данный момент неизвестно полиномиальных алгоритмов ее решения. С другой стороны, неизвестно, является ли эта задача NР-полной, хотя есть веские основания предполагать, что не является.

Протокол IG

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

1. Р

выбирает случайную перестановку p на множестве U, вычисляет Н=-тG1 и посылает этот граф V.

2. V

выбирает случайный бит a и посылает его Р.

3. Если a=1, то Р посылает V перестановку p, в противном случае - перестановку p°j.

4. Если перестановка, полученная V, не является изоморфизмом между Ga

и Н, то V останавливается и отвергает доказательство. В противном случае выполнение протокола продолжается.

Если проверки п.4 дали положительный результат во всех m циклах, то V

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

Необходимо отметить, что если в протоколе IG машина Р

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

Теорема 4.1. Протокол

IG является доказательством с абсолютно нулевым разглашением для языка «Изоморфизм графов».

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

Подробно приведено в работе [Ва1].

Заключительные замечания

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

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

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

Жизненный цикл программного обеспечения

Необходимость определения этапов жизненного цикла (ЖЦ) ПО обусловлена стремлением разработчиков к повышению качества ПО за счет оптимального управления разработкой и использования разнообразных механизмов контроля качества на каждом этапе, начиная от постановки задачи и заканчивая авторским сопровождением ПО. Наиболее общим представлением жизненного цикла ПО является модель в виде базовых этапов – процессов[Лип1], к которым относятся:

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

·     предварительное (эскизное) и детальное (техническое) проектирование ПО;

·     разработка программных компонент, их комплексирование и отладка ПО в целом;

·     испытания, опытная эксплуатация и тиражирование ПО;

·     регулярная эксплуатация ПО, поддержка эксплуатации и анализ результатов;

·     сопровождение ПО, его модификация и совершенствование, создание новых версий.

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

Графическое представление моделей ЖЦ позволяет наглядно выделить их особенности и некоторые свойства процессов. Первоначально была создана каскадная модель ЖЦ [Лип1], в которой крупные этапы начинались друг за другом с использованием результатов предыдущих работ. Наиболее специфической является спиралевидная модель ЖЦ [Лип1]. В этой модели внимание концентрируется на итерационном процессе начальных этапов проектирования. На этих этапах последовательно создаются концепции, спецификации требований, предварительный и детальный проект. На каждом витке уточняется содержание работ и концентрируется облик создаваемого ПО.

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

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

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

Этой совокупности этапов ЖЦ ПО соответствует процесс внесения в разрабатываемые программы определенных защитных функций. Этот процесс называется обеспечением технологической безопасности

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

Вторая часть ЖЦ, отражающая поддержку эксплуатации и сопровождения ПО, относительно слабо связана с характеристиками объекта и среды разработки. Номенклатура работ на этих этапах более стабильна, а их трудоемкость и длительность могут существенно изменяться, и зависят от массовости применения ПО. Для любой модели ЖЦ обеспечение высокого качества программных комплексов возможно лишь при использовании регламентированного технологического процесса на каждом из этих этапов. Такой процесс поддерживается CASE-средствами (средствами автоматизации разработки ПО), которые целесообразно выбирать из имеющихся или создавать с учетом объекта разработки и адекватного ему перечня работ.

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

Злоумышленники в профессиональных коллективах программистов-разработчиков

Согласно существующей статистики в коллективах людей занятых той или иной деятельностью, как правило, только около 85% являются вполне лояльными (честными), а остальные 15% делятся примерно так: 5% - могут совершить что-нибудь противоправное, если, по их представлениям, вероятность заслуженного наказания мала; 5% - готовы рискнуть на противоправные действия, даже если шансы быть уличенным и наказанным складываются 50 на 50; 5% - готовы пойти на противозаконный поступок, даже если они почти уверены в том, что будут уличены и наказаны. Такая статистика в той или иной мере может быть применима к коллективам, участвующим в разработке и эксплуатации информационно-технических составляющих компьютерных систем.

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

По другим данным[СМ] считается, что от 80 до 90% компьютерных нарушений являются внутренними, в частности считается, что на каждого «... подлого хакера приходится один обозленный и восемь небрежных работников, и все они могут производить разрушения изнутри».

---

---