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

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

Пусть х, у О -различные объекты графа доступа Go = (So, Oo.Eo), . Определим предикат "возможен доступ"(,x,y,Go), который будет истинным тогда и только тогда, когда существуют графы ,….. такие, что:

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

Теорема 1. Пусть Go = (So, Оо, Ео) - граф доступов, содержащий толь­ко вершины-субъекты. Тогда предикат "возможен доступ" (a,x,y, Go) исти­нен тогда и только тогда, когда выполняются следующие условия 1 и 2.

Условие 1. Существуют субъекты ,..., , такие, что() для i=1,………..m и

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

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

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

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

Условие 2. Субъекты х и s соединены tg путем в графе . Необходимость. Пусть истинен предикат "возможен доступ" (a,x,y,Go). По определению истинности предиката существует последователь­ность графов доступов ,..., , такая, что:

 

при этом N является минимальным, т.е. (x,y,a) . Докажем необходимость условий 1 и 2 индукцией по N.

При N=0 очевидно (х,у,а) Ео. Следовательно, условия 1, 2 выпол­нены.

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

и )

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

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

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

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

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

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

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

Из перечисленных требований следует, что М<N-1, opM= = create({g,t},s",s), opN=take(a,x, ,y) и истинен предикат "возможен доступ" (a,s",y,Go). Отсюда - истинен предикат "возможен доступ" (t,x, s'.Gm), а так как s"- единственный субъект в графе Gm, имеющий права на субъект s', то по предположению индукции s" соединен с х tg-путем в гра­фе Go. Из истинности предиката "возможен доступ" (a,s",y,Go) и по пред­положению индукции s So: (s,y,a) Eo и s", s соединены tg-путем в гра­фе Go. Следовательно, s So: (s,y,a) E0 и х, s соединены tg-путем в графе Go. Выполнение условий 1 и 2 для случая s' Eo доказано. Индук­тивный шаг доказан.

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

Пусть N=0. Следовательно, x=s, (х,у,a) и предикат "возможен доступ" (a,x,y,Go) истинен. Пусть N = 1, т.е. существует (s,y,a) и субъекты х, s непосредст­венно tg-связны. Возможны четыре случая такого соединения х и s (рис.5), для каждого из которых указана последовательность преобразо­ваний графа, требуемая для передачи прав доступа.

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

и длина tg-пути между z и х равна N=1, что позволяет применить предположение индукции.

Рис.5.Возможные случаи непосредственной tg-связности x и s

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

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

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

Определение 3. Мостом в графе доступов Go называется tg-путь, концами которого являются вершины-субъекты;

Определение 4. Начальным пролетом моста в графе доступов Go на­зывается tg-путь, началом которого является вершина-субъект.

Определение 5. Конечным пролетом моста в графе доступов Go на­зывается tg-путь, началом которого является вершина-субъект.