Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Дисциплины:
2017-11-27 | 144 |
5.00
из
|
Заказать работу |
|
|
Данный способ характеризуется тем, что при передаче прав доступа не накладываются ограничения на кооперацию субъектов системы, участвующих в этом процессе.
Определение 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.
при этом 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-путь, началом которого является вершина-субъект.
|
|
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!