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

Заметим, что путь, соединяющий вершины x ’, x ₂, x, есть начальный пролет моста.

Если x ₁Ï S _0, то с учетом замечаний, сделанных при доказательстве теоремы 1.5, получаем, что существуют M < N – 1, x ₂Î S ₀ такой, что op_M = create ({ t, g }, x ₂, x ₁). Среди всех последовательностей преобразований длины N можно выбрать такую, что M = 1. Далее используем технику доказательства теоремы 5.1 и доказательства индуктивного шага для случая x ₁Î S ₀. Таким образом, для случая x Ï S ₀условия1-3 выполняются, и индуктивный шаг доказан.

Если x Î S ₀, то условие2(а) очевидно выполняется. Многократно применяя технику доказательства, использованную выше и в теореме 5.1, доказываем индуктивный шаг и в данном случае.

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

Замечание 5.1. При доказательстве теоремы 5.2 можно показать, что не существует путей, отличных от мостов между двумя субъектами, проходящих через вершины объекты, по которым возможна передача прав доступа. Для этого рассмотрим все пути (с учетом симметрии) длины 2 между двумя субъектами, проходящие через вершины объекты, по которым возможна передача прав доступа (рис. 5.13(а)) и невозможна передача прав доступа (рис. 5.13(б)).

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

Похищение прав доступа

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

Определение 5.7. Пусть x, y Î O ₀, x ¹ y ¾ различные объекты графа доступов G ₀= (S ₀, O ₀, E ₀), a Í R. Определим предикат can_steal (a, x, y, G ₀), который будет истинным тогда и только тогда, когда (x, y, a) Ç E ₀= Æ и существуют графы G ₁= (S ₁, O ₁, E ₁), …, G_N = (S_N, O_N, E_N) такие, что G ₀├ _{op 1} G ₁├ _{op 2}… ├ _opN G_N и (x, y, a) Ì E_N, при этом, если существует (s, y, g) Ì E ₀, где g Í a, то справедливо неравенство op_K ¹ grant (g, s, z, y), где z Î O_{K – 1}, для K = 1, …, N.

Теорема 5.3. Пусть G ₀= (S ₀, O ₀, E ₀) ¾ произвольный граф доступов, x, y Î O ₀, x ¹ y. Предикат can_steal (a, x, y, G ₀) истинен тогда и только тогда, когда выполняются условия1-4.

Условие 1. (x, y, a) Ç E ₀= Æ.

Условие 2. Существуют объекты s ₁, …, s_m Î O ₀:

(s_i, y, g _i ) Ì E ₀для i = 1, …, m и a = g₁ È … È g _m.

Условие 3. Являются истинными предикаты can_share ({ t }, x, s_i, G ₀), где i = 1, …, m.

Условие 4. Для i = 1, …, m граф доступов G ₀не является графом вида, приведенного на рис. 5.14.

Доказательство. Доказательство осуществляется аналогично доказательству теоремы2.2. ■

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