The search for bridges in Take-Grant security model.pdf В настоящее время для разработки и исследования защищённых компьютерныхсистем широко используются дискреционные модели безопасности. Такие модели ос-нованы на субъектно-объектном подходе, согласно которому система представляетсяв виде активных сущностей (субъектов) и пассивных сущностей (объектов), при этоммножество субъектов является подмножеством множества объектов (S С O). Дис-креционные модели безопасности в явном виде задают разрешённые (запрещённые)правоотношения для каждой пары субъект - объект компьютерной системы.Разновидностью дискреционных моделей безопасности является модель Take-Grant [1-3]. В этой модели система правоотношений содержит два особых права:take (t) - брать права на объект (субъект) у другого объекта (субъекта) и grant (g) -давать права на объект (субъект) другому объекту (субъекту). Сама компьютернаясистема представляется в виде ориентированного графа (графа доступов), в которомвершинами являются субъекты и объекты, а дугами - права доступов, установленныемежду соответствующими субъектами и объектами. Анализ информационной безопас-ности в модели Take-Grant проводится путем исследования графа доступов и поискав нем определенных структур. Примеры таких структур - острова и мосты.Определение 1. Островом в графе доступов называется подграф, состоящий извершин-субъектов, причём эти вершины соединены между собой дугами, содержащи-ми права take либо grant (направление дуг не учитывается).Определение 2. Мостом в графе доступов называется проходящий по вершинам-объектам путь, каждая дуга которого содержит право take или grant, при этом сло-варная запись пути имеет вид t *, t *, t t * либо t t *.Согласно [1], отыскание данных структур в графе доступов необходимо для анали-за информационной безопасности, однако в классической модели Take-Grant методыпоиска не описаны. Ниже приводится алгоритм поиска мостов, если острова в графеуже найдены.Пусть в графе доступов G = (V, E) (где V = O - множество вершин, E - множе-ство дуг) уже известны острова и необходимо найти мост между островами 11 С Sи 12 С S. Будем искать мост между вершинами s Е 11 и f Е /2. Опишем алгоритмпоиска моста, основанный на поиске в глубину [4].Введем шесть цветов для раскраски вершин: красный, зеленый, синий, белый, серыйи чёрный. Пусть в начале работы алгоритма все вершины графа G окрашены в белыйцвет. Окраску вершины будем обозначать c(x).В ходе работы алгоритма требуется временно запоминать некоторые посещённыевершины. Для этих целей удобнее всего использовать память, организованную какстек: первым пришёл - последним вышел.Утверждение 1. Алгоритм 1 корректно распознает наличие моста в графе до-ступов и заканчивает свою работу за конечное число шагов, независимо от того, су-ществует мост в графе или нет.Доказательство. Покажем, что алгоритм закончит свою работу, если в графе несуществует моста. Число вершин и дуг в графе не меняется в ходе работы алгоритма.Алгоритм просматривает каждую вершину не более одного раза, это гарантируетсяпроверкой условия на шагах 5, 6 и 7 (просматриваются только белые вершины). Еслина некотором шаге рекурсии алгоритм не обнаружит для текущей вершины смежнойс ней вершины u, которую еще можно посетить (шаг 8), то алгоритм окрашиваеттекущую вершину в чёрный и возвращается к предыдущему шагу рекурсии. Такимобразом, если в графе не существует моста, то за некоторое число шагов вершина sбудет окрашена в чёрный цвет и алгоритм остановит свою работу. При этом будетпросмотрено не более |O| вершин.Алгоритм 1. Поиск моста1: Сделать текущей вершину s.2: Окрасить текущую вершину в серый.3: Если вершина f не белая, тозавершить алгоритм - мост существует.4: Для всех вершин u, смежных с текущей, выполнить:5: Если c(u) = белый и текущая вершина серая или красная, и существует дуга tот текущей вершины до u, тоокрасить u в красный и перейти на шаг 11.6: Если c(u) = белый и текущая вершина серая или красная, и существует дугаили дуга if от текущей вершины до u, тоокрасить u в зелёный и перейти на шаг 11.7: Если c(u) = белый и текущая вершина серая или зелёная, или синяя, и суще-ствует дуга t от текущей вершины до u, тоокрасить u в синий и перейти на шаг 11.8: В остальных случаях окрасить текущую вершину в чёрный.9: Если c(s) = чёрный, тозавершить алгоритм - моста не существует,10: иначесделать текущей первую вершину из стека, перейти на шаг 3.11: Положить текущую вершину в стек, сделать текущей вершину u, перейти нашаг 3.Предположим теперь, что в графе существует мост типа t *. Такой мост будетраспознан путём последовательного выполнения шага 5. Все вершины, входящие в этотмост, будут окрашены в красный цвет.Аналогично, если в графе существует мост типа t *, то он распознаётся путёмпоследовательного выполнения шага 7, и все вершины, входящие в этот мост, будутокрашены в синий цвет. Мосты t * f f t * и t t * распознаются путем последова-тельного выполнения шагов 5, 6 и 7. Разработка алгоритма поиска мостов является важным вкладом в развитие класси-ческой модели Take-Grant. Представленный алгоритм позволяет решать задачу поискамоста между известными островами графа доступов за полиномиальное время и можетбыть применен для автоматического анализа безопасности компьютерных систем.

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