Модель распространения прав доступа Take - Grant

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

Перейдем к формальному описанию модели Take-Grant.

Обозначим:

O - множество объектов ( например, файлов или сегментов памяти )

S ≤ O - множество активных объектов - субъектов ( например, пользователей или процессов )

R = {r₁, ... r_m} {t, g} - множество прав доступа, где t ( take ) - право брать права доступа, g ( grant ) – право давать права доступа

G = (S, O, E) - конечный помеченный ориентированный граф без петель, представляющий текущие доступы в систем, множества S, O соответствуют вершинам графа, которые обозначим: ○ - объекты ( элементы множества O \ S ); ● - субъекты ( элементы множества S )

Элементы множества E ≤ O × O × R представляют дуги графа, помеченные непустыми подмножествами из множества прав доступа R.

Состояние системы описывается его графом доступов. Переход системы из состояния в состояние определяется операциями или правилами преобразования графа доступов. Преобразование графа G в граф G' в результате выполнения правила op обозначим через G ├_op G'.

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

Правило "Брать" – take(α, x, y, z). Пусть x S, y, z O - различные вершины графа G. β ≤ R, α ≤ β. Правило определяет порядок получения нового графа доступов G' из графа G.
Правило "Давать" – grant(α, x, y, z). Пусть x S, y, z O - различные вершины графа G. β ≤ R, α ≤ β. Правило определяет порядок получения нового графа G' из графа G.
Правило "Создать" - create(β, x, y). Пусть x S, β ≤ R, β ≠ 0. Правило определяет порядок получения нового графа G' из графа G, y O - новый объект или субъект.
Правило "Удалить" – remove(α, x, y). Пусть x S, y O - различные вершины графа G. β ≤ R, α ≤ β. Правило определяет порядок получения нового графа G' из графа G.

Перечисленные правила "Брать", "Давать", "Создать", "Удалить" для отличия от правил расширенной модели Take-Grant будем называть де-юре правилами .

Правило де-юое модели take-grant	Условия	Результирующее состояние системы G’ = (S’, O’, E’)
"Брать" take(α, x, y, z)	x S, (x, y, t) E, (y, z, β) E, x ≠ z, α ≤ β	S’ = S, O’ = O, E’ = E { (x, y, α) }
"Давать" grant(α, x, y, z)	x S, (x, y, g) E, (x, z, β) E, y ≠ z, α ≤ β	S’ = S, O’ = O, E’ = E { (y, z, α) }
"Создать" create(β, x, y)	X S, y O	O’ = O {y}, S’ = S {y} если у субъекта E’ = E { (x, y, β) }
"Удалить" remove(α, x, y)	X S, y O, ( x, z, β ) E, α ≤ β	S’= S, O’ = O, E’ = E \ { (x, y, α) }

Таблица 4.2

В модели Take-Grant основное внимание уделяется определению условий, при которых в системе возможно распространение прав доступа определенным способом. Мы рассмотрим условия реализации:

способа санкционированного получения прав доступа
способа похищения прав доступа

Санкционированное получение прав доступа

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

Пусть x, y O - различные объекты графа доступа G₀ = (S₀, O₀, E₀), α ≤ R. Определим предикат "возможен доступ" (α, x, y, G₀), который будет истинным тогда и только тогда, когда существуют графы G₁ = (S₁, O₁, E₁), .... G_n = (S_n, O_n, E_n), такие, что: G₀ ├_op1 G₁ ├_op2 … ├_opn G_n и (x, y, α) E_n

Определение 1. Говорят, что вершины графа доступов являются tg - связными или что они соединены tg - путем, если ( без учета направления дуг ) в графе между ними существует такой путь, что каждая дуга этого пути помечена t или g. Будем говорить, что вершины непосредственно tg - связны, если tg - путь между ними состоит из единственной дуги.

Теорема 1. Пусть G₀ = (S₀, O₀, E₀) - граф доступов, содержащий только вершины - субъекты. Тогда предикат "возможен доступ" (α, x, y, G₀) истинен тогда и только тогда, когда выполняются следующие условия 1 и 2.

Условие 1. Существуют субъекты s₁,... s_m такие, что (s_i, y, γ_i) E₀ для i = 1... m и α = γ₁ ... γ_m

Условие 2. Субъект x соединен в графе G₀ tg – путем с каждым субъектом s_i для i = 1… m.

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

При m =1 условия 1 и 2 формулируются следующим образом:

Условие 1. Существует субъект s, такой, что справедливо (s, y, α) E₀.

Условие 2. Субъекты x и s соединены tg – путем в графе G₀.

Необходимость. Пусть истинен предикат "возможен доступ" (α, x, y, G₀). По определению истинности предиката существует последовательность графов доступов G₁ = (S₁, O₁, E₁) ... G_n = (S_n, O_n, E_n), такая, что: G₀ ├_op1 G₁ ├_op2 … ├_opn G_n и (x, y, α) E_n, при этом n является минимальным, т. е. (x, y, α) E_n-1. Докажем необходимость условий 1 и 2 индукцией n.

При n = 0 очевидно (x, y, α) E₀. Следовательно, условия 1, 2 выполнены.

Пусть n > 0 и утверждение теоремы истинно для всех k < n. Тогда (x, y, α) E₀ и дуга (x, y ,α) появляется в графе доступов G_n в результате применение к графу G_n-1 некоторого правила opn. Очевидно, что не правило "Создать" или "Удалить". Если opn правило "Брать" ( "Давать" ), то по его определению существует s' S_n-1: (x, s', t) E_n-1 (s', x, g ) E_n-1 (s', y, α) E_n-1 и opn = take(α, x, s', y) ( opn = grant (α, s', x, y) ).

Возможно два случая: s' S₀ и s' S₀.

Пусть s' S₀. Тогда истинен предикат "возможен доступ" (α, s', y, G₀), при этом число преобразований графов меньше n. Следовательно, по предположению индукции существует s S₀: (s, y, α) E₀ и s' соединен с s tg - путем в графе G₀. Кроме этого, истинен предикат "возможен доступ" (t, x, s’, G₀) ( "возможен доступ" (g, s’, x, G₀) ), при этом число преобразований графов меньше n. Следовательно, по предположению индукции существует s'' S₀: (s'', s’, t) E₀ и s'' соединен с x tg - путем в графе G₀ ( (s'', x, g) E₀ и s'' соединен с s' tg - путем в графе G₀ ). Таким образом, существует s S₀: (s, y, α) E₀ и субъекты x, s соединены tg - путем в графе G₀. Выполнение условий 1 и 2 для случая s’ E₀ доказано.

Пусть s' S₀. Заметим, что число преобразований графов n минимально, поэтому новые субъекты создаются только в тех случаях, когда без этого невозможна передача прав доступа. Следовательно, преобразования графов отвечают следующим требованиям:

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

Из перечисленных требований следует, что существует M < n – 1, существует s'' S₀: opM = create({g, f}, s’’, s’), opn = take(α, x, s', y) истинен предикат "возможен доступ" (α, s'', y, G₀). Отсюда – истинен предикат "возможен доступ" (t, x, s', G_M), а так как s'' – единственный субъект в графе G_M, имеющий права на субъект s', то по предложению индукции s'' соединен с x tg – путем в графе G₀. Из истинности предиката "возможен доступ" (α, s'', y, G₀) и по предложению индукции существует s S₀: (s, y, α) E₀ и s'', s соединены tg – путем в графе G₀. Следовательно существует s S₀: (s, y, α) E₀ и x, s соединены tg – путем в графе G₀. Выполнение условий 1 и 2 для случая s' E₀ доказано. Индуктивный шаг доказан.

Достаточность.Пусть выполнены условия 1 и 2. Доказательство проведем индукцией по длине tg – пути, соединяющего субъекты x и s.

Пусть n = 0. Следовательно x = s, (x, y, α) E₀ и предикат "возможен доступ" (α, x, y, G₀) истинен.

Пусть n = 1, т. е. существует (s, y, α) E₀ и субъекты x, s непосредственно tg – связаны. Возможны четыре случая такого соединения x и s, для каждого из которых указана последовательность преобра- зований графа, требуемая для передачи прав доступа.

Пусть n > 1. Рассмотрим вершину z, находящуюся на tg – пути между x и s и являющуюся смежной с s в графе G₀. Тогда по доказанному для случая n = 1 существует последовательность преобразований графов доступов G₀ ├_op1 G₁ ├_op2... ├_opk G_k: ( z, y, α ) E₀ и длина tg – пути между z и x равна n-1, что позволяет применить предложение индукции. Теорема доказана.

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

Определение 2.Островом в произвольном графе доступов G₀ называется его максимальный tg - связный подграф, состоящий только из вершин субъектов.

Определение 3.Мостом в графе доступов G₀ называется g - путь, концами которого являются вершины – субъекты, при этом словарная запись tg - пути должна иметь вид t^→*, t^←*, t^←*g^→ t^←*, t^→*g^→ t^←*, где символ * означает многократное ( в том числе нулевое ) повторение.

Определение 4.Начальным пролетом моста в графе доступов G₀ называется tg - путь, началом которого является вершина – субъект, при этом словарная запись tg - пути должна иметь вид t^→*g^→.

Определение 5. Конечным пролетом моста в графе доступов G₀ называется tg - путь, началом которого является вершина - субъект, при этом словарная запись tg - пути должна иметь вид t^→*.

Теорема 2. Пусть G₀ = (S₀, O₀, E₀) - произвольный граф доступов. Предикат "возможен доступ" (α, x, y, G₀) истинен тогда и только тогда, когда выполняются условия 3, 4 и 5.

Условие 3. Существуют объекты s₁ ... s_m, такие, что (s_i, y, γ_i) E₀, i = 1... m и α = γ₁ ... γ_m.

Условие 4. Существуют вершины – субъекты x₁’ ... x_m’ и s₁’ ... s_m’, такие что:

x = x_i’ или x_i’ соединен с x начальным пролетом моста для i= 1 … m
s_i = s_i’ или s_i’ соединен с s_i конечным пролетом моста для i = 1 … m

Условие 5. Для каждой пары (x_i’, s_i’), i = 1 ... m, существуют острова l_{i, 1},... l_{i, ui}, ui ≥ 1, такие, что x_i l_{i, 1}, s_i l_{i, ui} и мосты между островами l_{i, j} и l_{i, j+1}, 1 ≤ j < ui.

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

При m = 1 условия 3, 4, 5 формулируются следующим образом:

Условие 3. Существует s O₀: (s, y, α) E₀.

Условие 4. Существует x’, s’ S₀:

x = x’ или x’ соединен с x начальным пролетом моста
s = s’ или s’ соединен с s конечным пролетом моста

Условие 5. Существуют острова l₁, ... l_u, u ≥ 1 такие, что x’ l₁, s’ l_u и мосты между островами l_j и l_j+1 для j = 1…u-1.

Необходимость. Пусть истинен предикат “возможен доступ” (α, x, y, G₀). По определению истинности предиката существует последовательность графов доступов G₀ = (S₀, O₀, E₀) ... G_n = (S_n, O_n, E_n) , такая, что G₀ ├_op1 G₁ ├_op2 ... ├_opn G_n и (x, y, α) E_n, при этом n является минимальным, т. е. (x, y, α) E_n-1. Докажем необходимость условий 3, 4, 5 индукцией n.

При n = 0 очевидно (x, y, α) E₀. Следовательно, условия 3, 4, 5 выполнены.

При n > 0 утверждение теоремы истинно для всех k < n, тогда (x, y, α) E₀ и дуга (x, y, α) появляется в графе G_n в результате применения к графу G_n-1 некоторого правила opn. Возможны два случая x S₀ и x S₀.

Если x S₀ то существует x₁ S_n-1: opn = grant (α, x₁, x, y). С учетом минимальности n и замечаний, сделанных при доказательстве теоремы 1, можно считать, что x₁ S₀. Следовательно:

Истинен предикат "возможен доступ" (g, x₁, x, G₀) с числом преобразований графов, меньшим n, тогда по предложению индукции выполнены условия 3, 4, 5:

существует x₂ O₀ : (x₂, x, g) E₀
существует x’ S₀, соединенный с x₂ конечным пролетом моста
существуют острова l₁, ... l_t, t ≥ 1, такие, что x₁ l_t, x’ l₁, и мосты между островами l_j и l_j+1 для j = 1 ... t-1

Истинен предикат “возможен доступ” (α, x₁, y, G₀) с числом преобразований графов, меньшим n. Тогда по предложению индукции выполнены условия 3, 4, 5:
- существует s O₀: ( s, y, α ) E₀
- существует s’ S₀: s = s’ или s’ соединен с s конечным пролетом моста
- существуют острова l_t, ... l_u, t – u ≥ 1, такие, что x₁ l_t, s’ l_u и между островами l_j и l_j+1 для j = t ... u-1

Заметим, что путь, соединяющий вершины x’, x₂, x есть начальный пролет моста. Таким образом, для случая x S₀ условия 3, 4, 5 выполняются, и индуктивный шаг доказан.

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

Достаточность. Условия 3, 4, 5 конструктивны.

По условию 3 существует объект s, который обладает правами α на объект y. По п. 2 условия 4 существует s’, который, либо совпадает с s, либо по конечному пролету моста может забрать у субъекта s права α на объект y.

По теореме 1 права доступа, полученные одним субъектом, принадлежащим острову, могут быть переданы любому другому субъекту острова. По условию 5 между островами существуют мосты, по которым возможна передача прав доступа. t^→ g^→ t^←. По п.1 условия 4 теоремы 2 существует субъект x’, который или совпадает с x, или, получив права доступа, может передать их x по начальному пролету моста. Теорема доказана.

Возможность похищения прав доступа

Способ передачи прав доступа, рассмотренный в главе 3, предлагает идеальное сотрудничество субъектов. В случае похищения прав доступа предлагается, что передача прав доступа объекту осуществляется без содействия субъекта, изначально обладавшего передаваемыми правами. Пусть x, y O – различные объекты графа доступа G₀ = (S₀, O₀, E₀), α ≤ R Определим предикат "возможно похищение" (α, x, y, G₀), который будет истинным тогда и только тогда, когда (x, y, α) E₀ и существуют графы G₁ = (S₁, O₁, E₁) ... G_n = (S_n, O_n, N_n), такие, что G₀ ├_op1 G₁ ├_op2 ... ├_opn G_n и (x, y, α) E_n, при этом, если существует (s, y, α) E₀, то для любого z S_j, j = 0 ... n выполняется opK ≠ grant (α, s, z, y), K = 1 ... n.

Теорема 3.Пусть G₀ = (S₀, O₀, E₀) – произвольный граф доступов. Предикат "возможно похищение" (α, x, y, G₀) истинен тогда и только тогла, когда выполняется условия 6, 7, 8.

Условие 6.(x, y, α) E₀

Условие 7. Существуют объекты s₁ ... s_m такие, что (s_i, y, γ_i) E₀ для i = 1 ... m и α = γ₁ ... γ_m.

Условие 8. Является истинным предикаты "возможен доступ" (t, x, s, G₀) для i = 1 .. m.

Доказательство. Аналогично доказательству теоремы 2.

Расширенная модель Take-Grant

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

В классической модели Take-Grant по существу рассматриваются два права доступа: t и g, а также четыре правила ( правила де-юре ) преобразования графа доступов: take, grant, create, remove. В расширенной модели дополнительно рассматриваются два права доступа: на чтение r ( read ) и на запись w ( write ), а также шесть правил ( правила де-факто ) преобразования графа доступов: post, spy, find, pass и два правила без названия.

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

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

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

Чтобы пояснить смысл правил де-факто рассмотрим ряд примеров.

Пример 1. Пусть субъект x не имеет право r на объект z, но имеет это право на субъект y. Пусть, кроме этого, x имеет право r на y. Тогда x может, просматривая информацию в y, пытаться искать в нем информацию из z. Таким образом, в системе может возникнуть информационный канал от объекта z к субъекту x, что демонстрирует правило де-факто spy. Очевидно также, если бы y был объектом, т. е. пассивным элементом системы, то информационный канал от z к .x возникнуть не мог.

Пример 2. Пусть субъект y имеет право r на объект z и право w на объект x. Прочитанная субъектом y информация в z может быть записана в x. Следовательно, в системе может возникнуть информационный канал от объекта z к объекту z, что демонстрирует правило де-факто pass.

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

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

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

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

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

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

Стоимость пути в этом случае определяется как сумма стоимостей примененных правил.

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