Модель матрицы доступов Харрисона-Руззо-Ульмана 1 страница

Модель Харрисона-Руззо-Ульмана (ХРУ) используется для анализа систем защиты, реализующих дискреционную политику управления доступом.

В модели ХРУ используются следующие обозначения:

O ¾ множество объектов системы (сущности-контейнеры в модели ХРУ не рассматриваются);

S ¾ множество субъектов системы (S Í O);

R ¾ множество видов прав доступа субъектов к объектам, например, права на чтение (read), на запись (write), владения (own);

M ¾ матрица доступов, строки которой соответствуют субъектам, а столбцы соответствуют объектам. M [ s, o ] Í R ¾ права доступа субъекта s к объекту o.

Определение 4.1. Автомат, построенный согласно описанию модели ХРУ, назовем системой ХРУ.

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

В результате выполнения примитивного оператора a осуществляется переход из состояния q = (S, O, M) в результирующее состояние q ’ = (S ’, O ’, M ’). Данный переход обозначим через q ├_a q ’.

Таблица4.1. Примитивные операторы модели ХРУ

Примитивный оператор	Исходное состояние q = (S, O, M)	Результирующее состояние q ’ = (S ’, O ’, M ’)
«внести» право r в M [ s, o ]	s Î S, o Î O, r Î R	S ’ = S, O ’ =O, M ’[ s, o ] = M [ s, o ] È { r }, для (s ’, o ’) ¹ (s, o) выполняется равенство M ’[ s ’, o ’] = M [ s ’, o ’]
«удалить» право r из M [ s, o ]	s Î S, o Î O, r Î R	S ’ = S, O ’ = O, M ’[ s, o ] = M [ s, o ] \ { r }, для (s ’, o ’) ¹ (s, o) выполняется равенство M ’[ s ’, o ’] = M [ s ’, o ’]
«создать» субъекта s ’	s ’Ï O	S ’ = S È { s ’}, O ’ = O È { s ’}, для (s, o) Î S ´ O выполняется равенство M ’[ s, o ] = M [ s, o ], для o Î O ’выполняется равенство M ’[ s ’, o ] = Æ, для s Î S ’выполняется равенство M ’[ s, s ’] = Æ
«создать» объект o ’	o ’Ï O	S ’ = S, O ’ = O È { o ’}, для (s, o) Î S ´ O выполняется равенство M ’[ s, o ] = M [ s, o ], для s Î S ’выполняется равенство M ’[ s, o ’] = Æ
«уничтожить» субъекта s ’	s ’Î S	S ’ = S \ { s ’}, O ’ = O \ { s ’}, для (s, o) Î S ’´ O ’выполняется равенство M ’[ s, o ] = M [ s, o ]
«уничтожить» объект o ’	o ’Î O, o ’Ï S	S ’ = S, O ’ = O \ { o ’}, для (s, o) Î S ’´ O ’выполняется равенство M ’[ s, o ] = M [ s, o ]

HfИз примитивных операторов составляется конечное число команд системы ХРУ. Каждая команда включает две части:

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

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

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

command c (x ₁, …, x_k )

if (r ₁Î M [ x_{s 1}, x_{o 1}]) and … and (r_m Î M [ x_sm, x_om ]) then

a₁;

…

a _n;

endif

end,

где r ₁, …, r_m Î R ¾ права доступа, a₁, …, a _n ¾ последовательность примитивных операторов, параметрами которых являются параметры команды x ₁, …, x_k. Следует отметить, что наличие условия в теле команды не является обязательным.

При выполнении команды c (x ₁, …, x_k) система осуществляет переход из состояния q в новое состояние q ’. Данный переход обозначим:

q ├ _{c ( x 1, …, xk )} q ’,

при этом q ’= q, если одно из условий команды с (x ₁, …, x_k) не выполнено, q ’= q_n, если условие команды с (x ₁, …, x_k) выполнено и существуют состояния q ₁, …, q_n такие, что q = q ₀├ _a1 q ₁├ _a2 … ├ _{a n} q_n.

Пример 4.1. Команда создания субъектом s личного файла f.

command CreateFile (s, f)

«создать» объект f;

«внести» право владения own в M [ s, f ];

«внести» право на чтение read в M [ s, f ];

«внести» право на запись write в M [ s, f ];

end.

■

Пример 4.2. Команда передачи субъекту s ’права read к файлу f его владельцем субъектом s.

command GrantRead (s, s ’, f)

if (own Î M [ s, f ]) then

«внести» право read в M [ s ’, f ];

endif

end.

■

Анализ безопасности систем ХРУ

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

Определение 4.2. Будем считать, что в состоянии q системы ХРУ возможна утечка права доступа r Î R в результате выполнения команды с (x ₁, …, x_k), если при переходе системы q ├ _{c (x 1, …, xk)} q ’выполняется примитивный оператор, вносящий право доступа r в ячейке матрицы доступов M, до этого r не содержавшей.

Определение4.3. Начальное состояние q ₀системы ХРУ называется безопасным относительно некоторого права доступа r Î R, если невозможен переход системы в такое состояние q, в котором возможна утечка права r. Иные словами, начальное состояние q ₀системы ХРУ называется безопасным относительно некоторого права доступа r, если невозможен переход системы в состояние, в котором право доступа r появилось в ячейке матрицы доступов M, до этого r не содержавшей.

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

Определение 4.4. Система ХРУ называется монооперационной, если каждая команда системы содержит один примитивный оператор.

Теорема 4.1. Существует алгоритм, проверяющий является ли начальное состояние произвольной монооперационной системы ХРУ безопасным относительно некоторого права доступа r Î R.

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

Заметим, что нет необходимости строить последовательность с командами, содержащими примитивные операторы вида «удалить»… и «уничтожить»…, так как в условиях команд и при утечке проверяется наличие прав доступа, а не их отсутствие.

Возможны три случая.

Первый случай: в начальном состоянии системы q ₀= (S ₀, O ₀, M ₀) выполняются следующие условия:

- множество субъектов S ₀¹Æ;

- существует (s, o) Î S ₀´ O ₀ такой, что r Ï M ₀[ s, o ].

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

Число различных примитивных операторов вида «внести»… равно

n = |R| × | S ₀ | × | O ₀ |.

В каждой команде возможна проверка не более n различных условий на наличие в некоторой ячейке матрицы доступов некоторого права доступа. Следовательно, максимальное число различных команд, содержащих примитивный оператор вида «внести»…, с различными наборами параметров не превосходит n × 2 ⁿ.

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

Шаг 1. Проверить выполнение условий первого случая.

Шаг 2. Построить список L всех команд, содержащих примитивный оператор вида «внести»… с различными наборами параметров (| L | £ n × 2 ⁿ).

Шаг 3. Перейти к началу списка L.

Шаг 4. Если список L пройден или пуст, то утечка права доступа r невозможна. В этом случае закончить выполнение алгоритма. Иначе выбрать из списка L очередную команду. Если условие команды выполнено, то перейти на шаг 5, иначе перейти на шаг 4.

Шаг 5. Удалить выбранную на шаге 4 команду из списка L и применить ее. Если в результате этого произошла утечка права доступа r, то закончить выполнение алгоритма. Иначе перейти на шаг 3.

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

Второй случай: в начальном состоянии системы q ₀= (S ₀, O ₀, M ₀) выполняется условие S ₀=Æ. Тогда необходимо применить одну команду, содержащую примитивный оператор вида «создать» субъекта, и перейти к первому случаю.

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

Шаг 1. Проверить выполнение условий второго случая.

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

Шаг 3. Выполнить алгоритм, построенный для первого случая. При этом выполняется равенство n = |R| × (| S ₀ | + 1) × (| O ₀ | + 1).

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

Третий случай: в начальном состоянии системы q ₀= (S ₀, O ₀, M ₀) выполняются следующие условия:

- множество субъектов S ₀¹Æ;

- для всех (s, o) Î S ₀´ O ₀ выполняется условие r Î M ₀[ s, o ].

Так как нет необходимости включать в последовательность более одной команды, содержащей примитивный оператор вида «создать»…, следует на основе алгоритма для первого случая с использованием команд, содержащих примитивный оператор вида «внести»…, обеспечить (если это возможно) применение одной команды, содержащей примитивный оператор вида «создать»…, после чего перейти к первому случаю. Заметим, что максимальное число различных команд, содержащих примитивный оператор вида «создать»… («создать» субъекта и «создать» объект), с различными наборами параметров не превосходит 2 × 2 ^m, где m = |R| × | S ₀ | × | O ₀ |.

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

Шаг 1. Проверить выполнение условий третьего случая.

Шаг 2. Построить список L ₁ всех команд системы, содержащих примитивный оператор вида «внести»… с различными наборами параметров (| L ₁| £ k × 2 ^k, где m = |R| × | S ₀ | × | O ₀ |). Построить список L ₂ всех команд системы, содержащих примитивный оператор вида «создать»…, с различными наборами параметров (| L ₂| £ 2 ^{m + 1}, где m = |R| × | S ₀ | × | O ₀ |).

Шаг 3. Перейти к началу списка L ₁.

Шаг 4. Если список L ₁ пройден или пуст, то утечка права доступа r невозможна. В этом случае закончить выполнение алгоритма. Иначе выбрать из списка L ₁ очередную команду. Если условие команды выполнено, то перейти на шаг 5, иначе перейти на шаг 4.

Шаг 5. Удалить выбранную на шаге 4 команду из списка L ₁ и применить ее. Последовательно по списку L ₂ проверить возможность применения хотя бы одной команды, содержащей примитивный оператор вида «создать»…. Если такая команда найдена, то применить ее и перейти на шаг 6. Иначе перейти на шаг 3.

Шаг 6. Выполнить алгоритм, построенный для первого случая. При этом выполняются условия:

- если на шаге 5 применена команда, содержащая примитивный оператор вида «создать» субъекта, то выполняется равенство n = |R| × (| S ₀ | + 1) × (| O ₀ | + 1).

- если на шаге 5 применена команда, содержащая примитивный оператор вида «создать» объект, то выполняется равенство n = |R| × | S ₀ | × (| O ₀ | + 1).

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

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

Следствие 4.1. Алгоритм проверки безопасности монооперационных систем имеет экспоненциальную сложность.

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

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

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

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

A = { a ₀, a ₁, …, a_m } ¾ внешний алфавит, где a ₀= Ù ¾ пустой символ;

Q = { q ₀, q ₁, …, q_k } ¾ внутренний алфавит, где q ₁¾ начальное состояние, q ₀¾ конечное состояние;

D = { r, l, e } ¾ множество действий, где r ¾ шаг вправо управляющей головки, l ¾ шаг влево, e ¾ управляющая головка не перемещается;

С: Q ´ A ® Q ´ A ´ D ¾ функция, задающая команды машины Тьюринга. Если С (q_{i 0}, a_{i 0}) = (q_{i 1}, a_{i 1}, d), то это означает, что когда машина, находится в состоянии q_{i 0}и управляющая головка указывает на ячейку ленты, содержащую символ a_{i 0}, тогда выполняется шаг машины, в результате которого в эту ячейку записывается символ a_{i 1}, машина переходит в состояние q_{i 1}, а управляющая головка смещается по ленте согласно действию d.

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

Пусть машина Тьюринга выполнила некоторое количество шагов. Занумеруем все ячейки, пройденные считывающей головкой (включая те, в которые была изначально занесена информация) числами от 1 до n. Тогда (a_{s 1}, …, a_sn) ¾ заполнение ленты, где a_si Î A, s_i Î {0, 1, …, m }для i = 1, …, n. Пусть считывающая головка указывает на ячейку с номером i Î {1, …, n }, содержащую символ a_si Î A, где s_i Î {0, 1, …, m }, состояние машины q_ij Î Q, где i_j Î {1, …, k }, и должна быть выполнена команда С (q_ij, a_si) = (q_ij, a_{si ’}, d), где q_{ij ’}Î Q, a_{si ’}Î A, s_i ’Î {0, 1, …, m }, i_j ’Î {1, …, k }, d Î D.

Каждой ячейке ленты поставим в соответствие субъекта системы ХРУ, при этом будем считать, что O = S = { s ₁, …, s_n }. Зададим матрицу доступов M для текущего состояния. Пусть множество прав доступа R = Q È A È { own, left, right } и в матрицу доступов внесены права:

- 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;

- left Î M [ s ₁, s ₁] ¾ признак крайней левой из пройденных ячеек на ленте;

- right Î M [ s_n, s_n ] ¾ признак крайней правой из пройденных ячеек на ленте.

Таким образом, текущему состоянию машины Тьюринга соответствует матрица доступов M системы ХРУследующего вида (рис. 4.1).

	s 1	s 2	s 3	…	si	…	sn– 1	sn
s 1	as 1, left	own
s 2		as 2	own
s 3			as 3
…
si					asi, qij
…
sn– 1							as n– 1	own
sn								asn, right

Рис. 4.1. Заполнения матрицы доступов системы ХРУ

Построим гомоморфизм машины Тьюринга в систему ХРУ. Для каждой команды машины Тьюринга С (q_ij, a_it) = (q_{ij ’}, a_{it ’}, d) зададим соответствующую ей команду модели ХРУ:

- если d = e, то

command Eq_ija_itq_ij’a_{it ’} (s)

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

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

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

«внести» право q_{ij ’}в M [ s, s ];

«внести» право a_{it ’}в M [ s, s ];

endif

end;

- если d = r, то необходимо задать две командыдля случаев, когда считывающая головка указывает или не указывает на самую правую ячейку ленты:

command R 1 q_ija_itq_{ij ’} a_{it ’}(s, s ’)

if (q_ij Î M [ s, s ]) and (a_it Î 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 ’];

endif

end;

command R 2 q_ija_itq_{ij ’} a_{it ’}(s, s ’)

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

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

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

«удалить» право right из M [ s, s ];

«внести» право a_{it ’}в M [ s, s ];

«создать» субъект s ’;

«внести» право own в M [ s, s ’];

«внести» право a ₀в M [ s ’, s ’];

«внести» право q_{ij ’}в M [ s ’, s ’];

«внести» право right в M [ s ’, s ’];

endif

end;

- если d = l, то две команды для этого случая задаются аналогично командам для случая d = r.

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

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

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

Дальнейшие исследования модели ХРУвелись в основном в направлении определения условий, которым должна удовлетворять система, чтобы для нее задача проверки безопасности была алгоритмически разрешимой. Так в 1976 году в работе доказано, что задача проверки безопасности алгоритмически разрешима для систем, в которых нет примитивных операторов вида «создать»…. В 1978 году они показали, что таковыми могут быть системы монотонные и моноусловные, т.е. системы, команды которых не содержат операторов вида «уничтожить»…или «удалить»…, и содержат условия, состоящие из не более одной проверки вида r Î M [ s, o ]. В том же году в работе показано, что задача проверки безопасности для систем с конечным множеством субъектов разрешима, но вычислительно сложна.

Дата добавления: 2014-11-20