Учебно-методический комплекс теоретические основы компьютерной безопасности

take(α, x, y, z)	x ∈ S, (x, y, t)∈ E, (y, z, β )^1∈ E x≠ z, α ⊆ β
S'=S, O'=O, E= E' ∪{(x, z, α)}
grant(α,x,y, z)	x ∈ S, (x, y, g)∈E, (y, z, β )∈ E x≠ z, α ⊆ β	S'=S, O'=O, E= E' ∪{(y, z, α)}
create(β, x, y)	x ∈ S, y∉ O	O'=O ∪{y}, S'=S ∪{y}, если y – субъект E= E' ∪{(y, z, β )}
remove(α,x,y)	x ∈ S, y∈ O, (x, y, β)∈ E, α ⊆ β	S'=S, O'=O, E= E' \ {(x,y,α)}∪{(x, y, β )}

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

Определение 2.1.6. Для исходного состояния системы Γ₀ (O₀, S₀, E₀) и прав доступа α ⊆ R предикат "возможен доступ(α, x, y, Γ₀)" является истинным тогда и только тогда, когда существуют графы доступов системы Γ₁ (O₁, S₁, E₁), Γ₂ (O₂, S₂, E₂), …, Γ_N (O_N, S_N, E_N), такие, что:
Γ₀(O₀,S₀,E₀)├с₁ Γ₁(O₁,S₁,E₁)├с₂…├с_N Γ_N(O_N,S_N,E_N) и (x, y,α)∈ E_N
где c₁, c₂, …, c_N – команды вида 2.1, 2.2, 2.3 и 2.4.
Говоря иначе, доступ субъекта x к объекту y с правом α ⊆ R, отсутствующий в начальном состоянии системы (x, y, α) ∉ E₀, возможен тогда и только тогда, когда существует последовательность перехода системы из состояния в состояние (Γ₀, Γ₁,…, Γ_N) под воздействием команд 2.1, 2.2, 2.3 и 2.4.
Определение 2.1.7. Вершины графа доступов являются tg-связными (соединены tg-путем), если в графе между ними существует такой путь, что каждая дуга этого пути выражает право t или g (без учета направления дуг).
Вершины непосредственно tg-связаны, если tg-путь между ними состоит из единственной дуги.
Справедлива следующая теорема.
Теорема 2.1.3. В графе доступов Γ₀ (S₀,O₀, E₀), содержащем только вершины-субъекты, предикат "возможен доступ(α, x, y, Γ₀)" истинен тогда и только тогда, когда выполняются следующие условия:
Условие 2.1.3.1. Существуют субъекты s₁,…,s_m такие, что (s_i, y, γ_i)∈E₀ для i=1, …, m и α =γ₁ ∪…∪γ_m.
Условие 2.1.3.2. Субъект х соединен в графе Γ₀ tg-путем с каждым субъектом s_i для i=1, …, m.
Доказательство. Доказательство теоремы проводится для m=1, так как схема доказательства для этого случая легко обобщается на случай m>1.
При m=1 условия 2.1.3.1 и 2.1.3.2 формулируются следующим образом:
Условие 2.1.3.1. Существует субъект s такой, что справедливо (s, y, α) ∈ E_0.
Условие 2.1.3.2. Субъекты x и s соединены tg-путем в графе Γ_0.
Необходимость. Пусть истинен предикат "возможен дос-
туп(α, x, y, Γ₀)". Тогда по определению 2.6 существует последовательность графов доступов Γ₁ (O₁, S₁, E₁), Γ₂ (O₂, S₂, E₂),…, Γ_N (O_N, S_N, E_N) такая, что: Γ₀├с₁ Γ₁├с₂…├с_N Γ_N и (x, y, α) ∈ E_N, при этом N является минимальным, т. е. (x, y, α) ∉ E_{N -1}. Необходимость условий 2.1.3.1 и 2.1.3.2 можно доказать индукцией по N.
При N=0 очевидно (x, y, α) ∈ E₀. Следовательно, условия 2.1.3.1,
2.1.3.2 выполнены.
Пусть N>0, и утверждение теоремы истинно для ∀ k < N. Тогда (x, y, α) ∉E ₀ и дуга (x, y, α) появляется в графе доступов Γ_N в результате применения к графу Γ_{N -1} некоторой команды с_N. Очевидно, это не команда "Создать" или "Удалить". Если с_N является командой "Брать" (или "Давать"), то по его определению ∃ s′∈ S_{N -1}: (x, s′, t) ∈ E_{N -1} (или (s′, x, g) ∈ E_{N -1}), (s′, y, α) ∈ E_{N -1} и с_N = take(α, x, s′, y) (или с_N = grant (α, s′, x, y)).
Возможны два случая: s′∈ S₀ и s′∉ S_0.
s′∈ S₀. Тогда истинен предикат "возможен доступ (α, s′, y, Γ₀)", при
этом число преобразований графов меньше N. Следовательно, по предположению индукции ∃ s∈ S₀: (s, y, α) ∈ E₀ и s′ соединен с s tg-путем в графе Γ₀. Кроме этого, истинен предикат "возможен доступ (t, x, s′, Γ₀)" (или "возможен доступ(g, s′, x, Γ₀)"), при этом число преобразований графов меньше N. Следовательно, по предложению индукции
∃ s′′∈S₀: (s′′, s′, t)∈E₀ и s′′ соединен с x tg-путем в графе Γ₀(или (s′′, x, g) ∈ E₀ и s′′ соединен с s′ tg-путем в графе Γ₀). Таким образом, ∃ s∈ S₀: (s, y, α) ∈ E₀ и субъекты x, s соединены tg–путем в графе Γ₀. Выполнение условий 2.1.3.1 и 2.1.3.2 для случая s′∈ S₀ доказано.
s′∉ S₀. Число N преобразований графов минимально, поэтому новые
субъекты создаются только в тех случаях, когда без этого невозможна передача прав доступа. Следовательно, преобразования графов отвечают следующим требованиям:

1. 
   субъект-создатель берет на созданный субъект максимально необходимый набор прав{t, g};
   
2. 
   каждый имеющийся в графе Γ₀ субъект не создает более одного субъекта;
   
3. 
   созданный субъект не создает новых субъектов;
   
4. 
   созданный субъект не использует правило "Брать" для получения прав доступа на другие субъекты.
   

Из перечисленных требований следует, что ∃ М< N –1,
∃ s′′∈ S₀: c_М = create({g, t}, s′′, s′), c_N = take(α, x, s′, y) и истинен предикат "возможен доступ (α, s′′, y, Γ₀)". Отсюда следует, что истинен предикат "возможен доступ (t, x, s', Γ_M)" , а так как s'' – единственный субъект в графе Γ_M, имеющий права на субъект s', то по предположению индукции s'' соединен с x tg-путем в графе Γ₀. Из истинности предиката "возможен доступ (α, s′′, y, Γ₀)" и по предположению индукции следует, что s и s'' соединены tg–путем в графеΓ₀. Следовательно, ∃ s∈S₀: (s, y, α) ∈ E₀ и x, s соединены tg–путем в графе Γ₀. Выполнение условий 2.1.3.1 и 2.1.3.2 для случая s′∉ S₀ доказано. Индуктивный шаг доказан.
Достаточность. Пусть выполнены условия 2.1.3.1 и 2.1.3.2 Доказательство проведем индукцией по длине tg–пути, соединяющего субъекты x и s.
Пусть N = 0. Следовательно, x = s, (x, y, α) ∈E₀ и предикат "возможен доступ(α, x, y, Γ₀)" истинен.
Пусть N = 1, т. е. ∃ s∈S₀: (s, y, α) ∈E₀ и субъекты x, s непосредственно tg-связаны. Тогда возможны четыре случая такого соединения x и s, для каждого из которых нетрудно указать последовательность преобразований графа, требуемую для передачи прав доступа (см. рис. 2.7).

Рис. 2.7. Возможные случаи непосредственной tg-связности x и s, а также последовательность преобразований графаΓ₀ до получения доступа (x, y, α) ∈ E_N
Таким образом, при N =1 предикат "возможен доступ(α, x, y, Γ₀)" истинен.
Пусть N >1. Рассмотрим вершину z, находящуюся на tg–пути между x и s, и являющуюся смежной с s в графе Γ₀. Тогда по доказанному для случая N =1 существует последовательность преобразований графов доступов Γ₀├с₁ Γ₁├с₂…├с_K Γ_K : (z, y, α) ∈ E_K и длина tg–пути между z и x равна N –1, что позволяет применить предположение индукции.
Теорема доказана. ■
Несмотря на кажущуюся сложность теоремы 2.1.3, она иллюстрирует вообще говоря довольно простой и интуитивно понятный порядок вещей – если кто-либо желает получить какие-либо права на кого-то, то при отсутствии ограничений на взаимоотношения субъектов, он может скооперироваться с третьим(ми) субъектом, кто такие права уже имеет, и позаимствовать их у него.
Авторы модели провели анализ санкционированного получения прав доступа также и в графе произвольного вида, состоящего как из субъектов, так и объектов. Для рассмотрения предиката "возможен доступ" в произвольном графе вводится ряд дополнительных понятий.
Определение 2.1.8. Островом в произвольном графе доступов Γ называется его максимальный tg-связный подграф, состоящий только из вершин субъектов.
Заметим, что остров, по сути, характеризует некую группу субъектов, кооперация которых в правах доступа не ограничена и процессы получения доступа внутри группы описываются теоремой 2.3.
Определение 2.1.9. Мостом в графе доступов Γ называется tg–путь, концами которого являются вершины_r * _s-*субъекты_r * _gr _s * _r; * _gприs _s * этом словарная* запись tg-пути должна иметь вид t ,t ,t t ,t t , где символ означает многократное (в том числе нулевое) повторение.
Определение 2.1.10. Начальным пролетом моста в графе доступов Γ называется tg-путь, началом которого является вершинаr * gr -субъект; при этом словарная запись tg-пути должна иметь вид t .
Определение 2.1.11. Конечным пролетом моста в графе доступов Γ называется tg-путь, началом которого является вершинаr * -субъект; при этом словарная запись tg-пути должна иметь вид t .
Справедлива следующая теорема.
Теорема 2.1.4. В произвольном графе доступов Γ₀ (S₀, O₀, E₀) предикат "возможен доступ(α, x, y, Γ₀)" истинен тогда и только тогда, когда выполняются условия 2.1.4.1, 2.1.4.2 и 2.1.4.3:
Условие 2.1.4.1. Существуют объекты s₁,…,s_m такие, что (s_i, y, γ_i)∈E₀ для i=1, …, m и α=γ₁ ∪…∪γ_m.
Условие 2.1.4.2. Существуют вершины-субъекты x₁',…, x_m' и s₁',…, s_m' такие, что:

•