19. Мо­дель рас­про­стра­не­ния прав дос­ту­па Take-Grant. Тео­ре­мы о пе­ре­да­че прав в гра­фе дос­ту­пов, со­стоя­щем из субъ­ек­тов, и про­из­воль­ном гра­фе дос­ту­пов. Рас­ши­рен­ная мо­дель Take-Grant и ее при­ме­не­ние для ана­ли­за ин­фор­ма­ци­он­ных по­то­ков в АС.

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

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

Перейдем к формальному описанию модели Take-Grant. Обозначим: О - множество объектов (например, файлов или сегментов памяти); S Í О - множество активных объектов - субъектов (например, пользователей или процессов); R = {r₁, r₂,..., r_m} È {t,g}-множество прав доступа, где t(take)-право брать права доступа, g(grant)-право давать права доступа; G = (S, О, E)-конечный помечен­ный ориентированный граф без петель, представляющий текущие досту­пы в системе; множества S, О соответствуют вершинам графа, которые обозначим: Ä-объекты (элементы множества O\S); ·-субъекты (элемен­ты множества S); элементы множества EÍOxOxR представляют дуги графа, помеченные непустыми подмножествами из множества прав дос­тупа R.

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

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

1.       Правило "Брать"- take(a,x,y,z). Пусть хÎS, у, zÎО - различные вершины графа G,bÍR,aÍb. Правило определяет порядок получения нового графа доступов G' из графа G .

G                                G'

Субъект х дает объекту у права aÍbна объект z

2.       Правило "Давать"- grant(a,x,y,z). Пусть хÎS, у, zÎО -различные вершины графа G,bÍR,aÍb. Правило определяет порядок получения нового графа G' из графа G (рис.4.2)

Субъект х дает объекту у права aÍb на объект z

Правило "Создать"- create(b,х.у). Пусть xÎS, bÍR, b¹0. Правило определяет порядок получения нового графа G' из графа G; уÎ О- новый объект или субъект.

Субъект х создает новый b-доступный объект у

4. Правило "Удалить"-remove(a,х,у). Пусть xÎS,yÎО - различные вершины графа G.bÍR,aÍb. Правило определяет порядок получения нового графа G' из графа G.

Субъект х удаляет права доступа a  на объект у.

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

                                                                                                                         Таблица

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

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

•   способа похищения прав доступа.

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

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

Пусть х, уÎО - различные объекты графа доступа G₀=(S₀,O₀,E₀), aÍR. Определим предикат "возможен доступ" (a,х,у,G₀), который будет истинным тогда и только тогда, когда существуют графы G₁=(S₁,O₁,E₁),.... G_N=(S_N,O_N,E_N), такие, что:

G₀├_op1 G₁├_op2…├_opN G_N и   (x,y,a)ÎE_N.

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

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

Условие 1. Существуют субъекты s_l .... s_m, такие, что

(s_i,y,g_i,)ÎE₀  для  i=1,...,m  и  a = g₁È…È g_m.

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

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

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

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

Условие 2. Субъекты х и s соединены tg-путем в графе G₀. Необходимость. Пусть истинен предикат "возможен доступ" (a,x,y,G₀). По определению истинности предиката существует последователь­ность графов доступов G₁=(S₁,O₁,E₁), ...., G_N=(S_N,O_N,E_N), такая, что: G₀├_op1 G₁├_op2…├_opN G_N и   (x,y,a)ÎE_N, при этом N является минимальным, т.е. (x,y,a)ÏE_N-1. Докажем необходимость условий 1 и 2 индукцией по N.

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

Пусть N>0, и утверждение теоремы истинно для "k<N. Тогда (x,y,a)ÏE₀ и дуга (x,y,a) появляется в графе доступов G_N в результате применения к графу G_N-1 некоторого правила opN. Очевидно, это не пра­вила "Создать" или "Удалить". Если opN  правило "Брать" ("Давать"), то по его определению

$s' ÎE_N-1: (x,s',t) Î E_N-1 ((s',x,g)Î E_N-1 ), (s',y,a)Î E_N-1 и opN = take(a,x,s',y)(opN= = grant(a,s',x,y)).

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

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

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

1) субъект-создатель берет на созданный субъект максимально не­обходимый набор прав {t,g};

2) каждый имеющийся в графе G₀ субъект не создает более одного субъекта;

3) созданный субъект не создает новых субъектов;

4) созданный субъект не использует правило "Брать для получения
прав доступа на другие субъекты. 

Из перечисленных требований следует, что $М<N-1, $s"ÎS₀:opM =

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

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

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

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

Пусть N>1. Рассмотрим вершину z, находящуюся на tg-пути между х и s и являющуюся смежной с s в графе G₀. Тогда по доказанному для слу­чая N=1 существует последовательность преобразований графов досту­пов

 G₀├_op1 G₁├_op2…├_opK G_K (z,y,a)ÎE_K и длина tg-пути между z и х равна N-1, что позволяет применить предположение индукции.

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

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

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

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

!!!!( ^← и^→должны быть над t и g )!!!!! .

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

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

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

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

a = g₁È…È g_m.

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

·        х=х_i или х_i, соединен с х начальным пролетом моста для i=1,...,m;

·        s_i=s_i или s_i соединен с а конечным пролетом моста для i=1,.... m.

Условие 5. Для каждой пары (х_i, s_i), i=1, ...,m, существуют острова l_i,1… l_i,ui, u_i³1, такие, что х_iÎ l_i,1, s_iÎ l_i,ui и мосты между островами l_i,j и l_i,j+1,u_i>j³1.

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

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

Условие 3. $sÎO₀: (s,y,a) ÎE_0s.

Условие 4. $х', s'ÎS₀:

•   х =х' или х' соединен с х начальным пролетом моста;

•   s = s' или s' соединен с s конечным пролетом моста.

Условие 5. Существуют острова l_i,...,l_u, u>1, такие, что x'Îl_i, s'Îl_u, и мосты между островами l_j и l_j+1  для j=1,...,u-1.

Необходимость. Пусть истинен предикат "возможен доступ" (a,x,y,G₀). По определению истинности предиката существует последователь­ность графов доступов G₁=(S₁,O₁,E₁),...,G_N=(S_N,O_N,E_N), такая, что, G₀├_op1 G₁├_op2…├_opN G_N (x,y,a)ÎE_N при этом N является минимальным, т.е(x,y,a)ÏE_N-1. Докажем необходимость условий 3, 4. 5 индукцией по N.

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

Пусть N>0 и утверждение теоремы истинно для "k<N. Тогда (x,y,a)ÏE₀ и дуга (x,y,a)появляется в графе доступов G_N в результате применения к графу G_N-1 некоторого правила орN. Возможны два случая xÎS₀ и xÏS₀

Если xÏS₀, то $x₁ÎS_N-1= grant(a,x₁,x,y). С учетом минимально­сти N и замечаний, сделанных при доказательстве теоремы 1, можно счи­тать, что x₁ÎS₀. Следовательно:

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

•   $x₂ÎO₀:(х₂,х,g) ÎЕ₀;

•   $x'ÎS₀, соединенный с х₂ конечным пролетом моста;

•  существуют острова l_1,…,l_t t³1, такие, что x₁Îl_t, x'Îl₁, и мосты между островами l_j и l_j+1 для j=1,.... t-1;

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

• sÎO₀: (s,y, a)ÎЕ₀;

• $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ÏS₀ условия 3, 4, 5 выполня­ются, и индуктивный шаг доказан.

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

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

По теореме 1 права доступа, полученные одним субъектом, принад­лежащим острову, могут быть переданы любому другому субъекту остро­ва. По условию 5 между островами существуют мосты, по которым воз­можна передача прав доступа. В качестве примера на рис.4.7 разобрана последовательность преобразований графа доступов при передаче прав по мосту вида ^→t^→g^←t. По п.1 условия 4 теоремы 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 (реальными дугами), мнимые дуги указывают на направления ин­формационных каналов в системе.

Рис. Правила де-факто (везде вместо реальных дуг могут быть мнимые дуги)

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

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

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

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

•    быть константой;

•    зависеть от специфики правила;

•   зависеть от числа участников при применении правила;

•   зависеть от степени требуемого взаимодействия объектов.

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

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