18. Модель системы безопасности HRU. Основные положения модели. Теорема об алгоритмической неразрешимости проблемы безопасности в произвольной системе.

Основные положения модели

Модель HRU (Харрисона – Руззо - Ульмана) используется для анализа системы защиты, реализую­щей дискреционную политику безопасности, и ее основного элемента - матрицы доступов. При этом система защиты представляется конечным ав­томатом, функционирующим согласно определенным правилам перехода.

Модель HRU была впервые предложена в 1971 г. В 1976 г. появилось формальное описание модели. Классическая Дискреционная модель реализует произвольное управление доступом субъектов и объектов и контроль за распространением прав доступа. В рамках этой модели система обработки информации представляется в виде совокупности активных сущностей субъектов / множество s/; которые осуществляют доступ к информации; пассивных сущностей объектов /множество о/, содержащих защищаемую информацию; конечного множества привилегированного доступа /множество R/, означающих полномочия на выполнение соответствующих действий.

Обозначим: О-множество объектов системы; S-множество субъек­тов системы

(S Í O); R- множество прав доступа субъектов к объектам, например права на чтение (read), на запись (write), владения (own); M-матрица доступа, строки которой соответствуют субъектам, а столбцы - объектам; М[s,o]ÍR- права доступа субъекта s к объекту о.

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

·        "Внести" право rÎR в M[s,о] - добавление субъекту s права доступа r объекту о. При этом в ячейку M[s,o] матрицы доступов добавляется элемент r.

·        "Удалить" право r Î R из М [s, о] - удаление у субъекта s права доступа r к объекту о. При этом из ячейки М [s, о] матрицы доступов удаляется элемент r.

·        "Создать" субъекта s'-добавление в систему нового субъекта s'. При этом в матрицу доступов добавляются новые столбец и строка.

·        "Создать" объект о'-добавление в систему нового объекта о'. При этом в матрицу доступов добавляется новый столбец.

·        "Уничтожить" субъекта s'-удаление из системы субъекта s'. При этом из матрицы доступов удаляются соответствующие столбец и строка.

·        "Уничтожить" объект о'- удаление из системы объекта о'. При этом из матрицы доступов удаляется соответствующий столбец.

В результате выполнения примитивного оператора α осуществляется переход системы из состояния Q = (S,O,M) в новое состояние O' = (S', О', M') (табл.). Данный переход обозначим через Q├_aQ'.

  Таблица

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

•    условия, при котором выполняется команда;

•    последовательности примитивных операторов.

Таким образом, запись команды имеет вид:

command С (x₁ .... х_k)

if r₁ Î M[x_s1,x_o1 and...and r_m ÎM[x_sm, х_om] then ;

a₁;

…

a_n

end

Здесь r,..., r_mÎR-права доступа, a₁…,a_n -последовательность примитивных операторов. Следует отметить, что условия в теле команды необязательны.

При выполнении команды С (x₁ .... х_k) система осуществляет переход из состояния Q в новое состояние Q'. Данный переход обозначим через Q├_{С (x1 .... хk)} Q'. При этом справедливо:

•    Q'=Q, если одно из условий команды С (x₁ .... х_k)не выполнено;

•    Q'=Q_n, если все условия команды С (x₁ .... х_k) выполняются и сущест­вуют состояния Q₁,..., Q_n: Q = Q₀├_a1 Q₁├_{a 2}...├_{a n} Q _n.

Теорема об алгоритмической неразрешимости проблемы безопасности в произвольной системы

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

Теорема. Задача проверки безопасности произвольных систем ал­горитмически неразрешима.

Доказательство. Для доказательства теоремы воспользуемся фак­том, доказанным в теории машин Тьюринга: не существует алгоритма проверки для произвольной машины Тьюринга и произвольного начально­го слова остановится ли машина Тьюринга в конечном состоянии или нет.

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

Обозначим элементы и команды машины Тьюринга: А={а₀,а₁,...,а_m}- внешний алфавит, где а₀=Ù-пустой символ; Q={q₀, q₁,..., q_k}-внутренний алфавит, где q₁-начальное состояние, q₀-конечное состояние; D={r,l,e}- множество действий, где r-шаг вправо управляющей головки, l-шаг влево, e-управляющая головка не перемещается; С: QxA®QxAxD - функция, задающая команды машины Тьюринга.

Запись C(q_i0, a_i0) = (q_i1, a_i1, d) означает, что когда машина находится в состоянии q_i0 и управляющая головка указывает на ячейку ленты, содер­жащую символ a_i0, то выполняется шаг машины, в результате которого в эту ячейку записывается символ a_i1, машина переходит в состояние q_i1, a управляющая головка смещается по ленте согласно действию d.

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

Пусть машина Тьюринга выполнила некоторое количество шагов. За­нумеруем все ячейки, пройденные считывающей головкой (включая те, в которые была изначально занесена информация) числами от 1 до n. Тогда (a_s1,,..., a_sn) - заполнение ленты, где a_siÎA s_i{0,1, ...,m} для i=1,...,n. Пусть считывающая головка указывает на ячейку с номером iÎ{1,....,n}, содержащую символ а_it ÎА, где i_t Î{0,1,.... m}, состояние машины q_ij ÎQ, где

i_j Î {1,..., k], и должна быть выполнена команда С(q_ij, a_it)= (q_ij', a_it', d), где

q_ij'ÎQ, a_it' ÎА, i_t' Î{0,1,..., m}, i_j' Î{1,....k}, dÎD.

Каждой ячейке ленты поставим в соответствие субъекта модели HRU, при этом будем считать, что О = S = {s₁,..., s_n}. Зададим матрицу дос­тупов М в текущем состоянии. Пусть множество прав доступа R =  Q ÈAÈ{own} и в матрицу доступов внесены права:

·        a_sjÎM[s_j, s_j] для j=1, ...,n-заполнение ленты;

·        ownÎM[s_j, s_j+1] для j=1,..., n-1 - упорядочивание субъектов, соответ­ствующих ячейкам ленты;

·        q_ijÎM[s_i, s_i] - управляющая головка указывает на ячейку с номером i.

Таким образом, текущему состоянию машины Тьюринга соответству­ет матрица доступов М модели HRU следующего вида:

Для каждой команды машины Тьюринга С(q_ij, a_it)= (q_ij', a_it', d)  зададим соответствующую ей команду cd(q_ij, a_it ,q_ij', a_it') модели HRU.

•   Если d=е, то

command ce(q_ij, a_it ,q_ij, a_it):

if(q_ijÎM[s, s]) and (a_ijÎM[s, s]) then

"удалить" право q_ij из M[s, s];

 "удалить" право a_it из M[s,s];

 "внести" право q_ij' в M[s,s];

 "внести" право a_it' в M[s,s];

 end;

•   Если d=r, то необходимо указать две команды cr1(q_ij, a_it ,q_ij', a_it') и

cr2 (q_ij, a_it ,q_ij', a_it')  для случаев соответственно, когда считывающая ловка не указывает на самую правую ячейку ленты и когда это так.

command cr1(q_ij, a_it ,q_ij', a_it')

if(q_ijÎM[s, s]) and (a_ijÎM[s, s]) and (own ÎM[s, s']) then

"удалить" право q_ij из M[s. s];

"удалить" право a_it из M[s, s];

"внести" право a_it' в M[s,s];

"внести" право q_ij' в M[s',s'];

end;

command cr2(q_ij, a_it ,q_ij', a_it'):

if(q_ijÎM[s, s]) and (a_ijÎM[s, s]) and (not $sÎS: own ÎM[s, s])) then

"удалить" право q_ij из M[s,s];

"удалить" право a_it из M[s,s];

"внести" право a_it' в M[s,s];

"создать" субъект s';

"внести" право own в M[s,s'];

"внести" право а₀ в M[s',s'];

внести" право q_ij' в M[s',s'];

 end;

•   Если d=l. то команды cl1(q_ij, a_it ,q_ij', a_it'), cl2(q_ij, a_it ,q_ij', a_it') задаются аналогично командам cr1(q_ij, a_it ,q_ij', a_it'), cr2(q_ij, a_it ,q_ij', a_it').

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

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

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