he search of tg-paths and islands for Take-Grant security model.pdf Минимальным требованием безопасности компьютерных систем является наличиев них разграничения доступа к информации [1], то есть организация системы такимобразом, что пользователи системы получают доступ лишь к той информации, котораянеобходима им для выполнения своих функциональных обязанностей. Для достиженияэтих целей разработан ряд математических моделей.Одной из наиболее проработанных моделей является модель дискреционного доступаTake-Grant [2-4]. Компьютерная система в модели Take-Grant представляетсяв виде ориентированного графа (графа доступов), вершинами которого являютсясубъекты и объекты системы, а дугами - установленные права субъектов на объекты.Помимо стандартного набора прав, таких, как, например, право чтения или право записи,в модели Take-Grant вводятся два дополнительных права: Take (t) - право братьправа у какого-либо субъекта и Grant (g) - право передавать свои права какому-либодругому субъекту. Анализируя исходный граф системы, можно выяснить, возможноли получение доступа каким-либо субъектом к какому-либо объекту за некоторое числошагов, то есть существует ли возможность модифицировать исходный граф так,что между двумя вершинами появится дуга с правом, которого нет в исходном графе.В рамках модели сформулированы две теоремы, которые оговаривают условия длявозникновения возможности доступа.Из теоретического описания модели ясны условия, при которых возникает возможностьдоступа, однако способы проверки наличия этих условий не оговариваются.При оценке безопасности состояний системы, для которой граф доступов состоиттолько из вершин-субъектов, необходимо проверить наличие tg-пути между двумявершинами (путь в графе, все дуги которого содержат права t или g) [2, 3].Для графа из вершин-субъектов необходимо проверить наличие tg-пути междудвумя вершинами; воспользуемся для этих целей алгоритмом Дейкстры [5].Построим по исходному графу доступов Go граф G0 следующим образом:1) множество вершин графа G0 совпадает с множеством вершин графа G0W = Vo);2) ребра в графе G0 не ориентированы; множество ребер графа включает лишь теребра из G0, которые содержат права Take или Grant (Eq = E0 \ Ea, где Ea -множество ребер графа G0, не содержащих прав Take или Grant);3) все ребра графа G0 имеют одинаковый вес.Для графа G0 применим алгоритм Дейкстры для поиска кратчайшего пути в графе.Кратчайший путь между двумя указанными вершинами, найденный алгоритмомДейкстры в графе G0, будет являться tg-путем между этими вершинами в графе G0.Оценка времени работы алгоритма Дейкстры в зависимости от числа вершин исходногографа будет O(N2) [6], где N - число вершин. Для построения графа G0 потребуетсятакже O(N2) операций.Для произвольного графа доступов необходимо найти острова в нем, а также мосты,их начальный и конечный пролеты [2-4]. Для поиска островов воспользуемсяалгоритмом Флойда для поиска всех кратчайших путей [5].Построим граф G0 по исходному графу доступов G0 следующим образом:1) множество вершин графа G0 совпадает с множеством вершин графа G0(V* = V0);2) ребра в графе G0 не ориентированы; множество ребер графа включает лишь теребра из G0, для которых началом и концом дуги является вершина-субъект икоторые содержат права Take или Grant (E* = E0 \ (E0-0 U Ea), где E^- ° - множестворебер графа G0, для которых начало и конец не являются субъектами;Ea - множество ребер графа G0, не содержащих прав Take или Grant);3) все ребра графа G0 имеют одинаковый вес.Для графа G0 применим алгоритм Флойда. Алгоритм обнаружит кратчайшиепути между каждой парой вершин в графе G0. Кратчайшие пути в графе G0 будутtg-путями, проходящими через вершины-субъекты в графе G0. А сами вершины-субъекты, объединенные tg-путями, будут являться островами в графе G0. Трудоемкостьалгоритма Флойда - O (N3) [6]; граф G0 можно будет построить за O(N2)операций.Зная критерии безопасности состояний информационной системы и способы проверкиэтих критериев, можно проанализировать исходное состояние системы на предметналичия нежелательных доступов.

Скачать электронную версию публикации