В статье описываются структурные модификации иерархии ролей в политике ролевого разграничения доступа. Строятся и обосновываются алгоритмы преобразования ролевого графа с учетом различных критериев его оптимальности. При этом рассматриваются такие характеристики, как принципы распространения полномочий в системе, отсутствие дублирующих ролей, особенности ролевого графа, в частности, его древовидность. Основным результатом является доказательство возможности получения нескольких ролевых графов, соответствующих эквивалентным политикам ролевого разграничения доступа.
1. = {1, . . . , } – множество полномочий (прав доступа, привилегий) на действия в системе. Заметим, что так как множества , и конечны, то все рассматриваемые дискретные отображения могут быть представлены булевыми матрицами по правилу: если : → 2 , то элемент матрицы [F] = 1 ⇐⇒ ∈ ().
Ведущую роль в списке основных отображений играет отображение авторизации ролей друг на друга , которое должно сформировать иерархию ролей – отношение нестрогого частичного порядка на множестве (отношение авторизации ). Отношение авторизации обозначим оператором доминирования/подчинения ролей «≻ » («≺ »): ≻ ( ≺ ) ⇐⇒ ∈ () – в этом случае роль является доминирующей (старшей), а роль – подчиненной (младшей). Рефлективность, антисимметричность и транзитивность отношения авторизации определяют следующие свойства отображения : 1. ∈ (). 2. Если ∈ () ∧ ∈ (), то = .
3. Если ∈ () ∧ ∈ (), то ∈ (). Множество () называется множеством достижимости роли .
Основные требования РРД заключаются в том, что отображения и должны гарантировать выполнение условия наследования полномочий : а отображения и должны обеспечивать выполнение условия наследования авторизации : ( ≺ ) ⇒ ( () ⊆ ()), ( ≺ ) ∧ ( ∈ ()) ⇒ ( ∈ ()), () ⊆
⋃︁ ∈() ().
(
Исходя из вышесказанного, ролевой граф – это граф, порождаемый отображениями и , и обладающий следующими характеристиками : ∙ Ориентированный. ∙ Бесконтурный (отсутствуют ориентированные циклы) – в силу антисимметричности отношения порядка. ∙ Помеченный.
∙ Выполнено условие наследования меток – условие (
Заметим, что ролевой граф не обязан являться диаграммой Хассе. Одной и той же иерархии ролей в общем случае можно сопоставить несколько ролевых графов. Такие графы назовем -эквивалентными . Очевидно, -эквивалентные ролевые графы отличаются друг от друга множеством дуг. Транзитивные дуги могут появляться в ходе эквивалентных преобразований политики РРД. Определение 2. Ролевой граф назовем транзитивно-сокращенным , если он является диаграммой Хассе.
В большинстве работ посвященных РРД принято считать, что иерархия ролей имеет вид ориентированного дерева – бесконтурного ориентированного графа, у которого полустепень захода (число входящих дуг) любой вершины не больше 1 и существует ровно одна вершина (корень), полустепень захода которой равна 0. Определение 3. Древовидный ролевой граф будем называть ролевым деревом и обозначать = (, , ).
При иерархическом отношении ролей особое внимание уделяется процессу построения отображения . Важным является вопрос: возможно ли назначение одного и того же набора полномочий двум ролям, находящимся в иерархическом подчинении. Для построения используется ролевой граф и применяется механизм наследования «снизу – вверх»: расстановка меток (распределение полномочий) начинается с листьев или стоков (вершин без исходящих дуг) ролевого графа. Пусть ( ⊆ ) – множество стоков, ℎ() – множество вершин-сыновей вершины . Возможны два подхода к расстановке меток, порождающих, в свою очередь, две различные -характеристики ролевого графа. Определение 4. Листовой ролевой граф (листовая -характеристика). Каждому стоку отображение сопоставляет набор полномочий () так, чтобы Метки остальных вершин наследуются: ∀ ∈ ∖ : () =
⋃︁ Если ∀, ∈ : () ∩ () = ?, то листовой ролевой граф называется таксономическим , иначе – нетаксономическим . Если ∀ ∈ : | ()| = 1, то листовой ролевой граф называется единичным, иначе – общим. Определение 5. Охватный ролевой граф (охватная -характеристика). Допускается включение в наборы полномочий вершин «добавочных» полномочий, ненаследуемых от сыновей. Это означает, что ⋃︁ () = . ∈ ⋃︁ () ⊆ .
∈ Определение 6. Роли и назовем -эквивалентными , если они наделены одинаковыми наборами полномочий: ∀, ∈ : ( v ) ⇐⇒ ( () = ()). Тем самым множество ролей разбивается на классы эквивалентности – -классы. Определение 7. Ролевой граф назовем -сокращенным, если каждый его -класс содержит ровно одну роль (метки всех вершин различны).
Обобщая вышесказанное, можно выделить следующие дополнительные характеристики ролевого графа: ∙ Листовой (в том числе единичный и/или таксономический). ∙ -сокращенный. Последнее свойство непосредственно касается только ролевого графа и никак не характеризует иерархию ролей.
Для разработки алгоритмов преобразования ролевого графа и оценки их трудоемкости необходимо учитывать особенности представления (описания) графов.
Для задания наборов полномочий ролей (меток вершин ролевого графа) удобно использовать векторное
представление: метка вершины – это -мерный битовый вектор (массив, строка) .:
︂{ 1, ∈ ()
0, ∈/ () , ( = 1, . . . , ).
(
Формальное описание алгоритмов на графах удобно вести в терминах абстрактного типа данных (АТД) «Граф». Интерфейс этого АТД должен включать следующие операции (методы) работы с графом: ∙ добавить / удалить вершину; ∙ добавить / удалить ребро; ∙ задать метку вершины; ∙ «склеить» / «стянуть» вершины 1 и т. д. Кроме того, для обработки всех вершин, смежных с указанной, как правило используется АТД «Итератор». Если – итератор, созданный для вершины графа , то: метод .() возвращает номер первой вершины, смежной с вершиной ; метод .() переходит к следующей вершине, смежной с , и возвращает ее номер; метод .() возвращает 1, если есть непройденные вершины, смежные с , и 0 – в противном случае. Тогда, например, операция «обойти все вершины, смежные с вершиной » может быть реализована в виде цикла:
( = . (); !.(); = .()) Реализация интерфейса АТД «Граф» зависит от способа представления данных.
Одним из стандартов программного (внутреннего) представления графа являются списки смежности . Пусть – число вершин графа, – -мерный вектор (массив) списков смежности. Элемент [] вектора соответствует вершине графа и содержит список тех вершин, в которые ведут дуги из вершины (список смежности). На этом уровне детализации операция «обойти все вершины, смежные с вершиной » реализуется как обход (просмотр) списка смежности [].
Матрица смежности графа M – другой способ представления данных внутри АТД «Граф». Матрица имеет размерность × . Элемент [M] матрицы смежности равен 1, если в орграфе существует дуга (, ), и 0 – в противном случае. Для одних алгоритмов эффективнее списочная реализация графа, для других – матричная.
1Здесь и далее операции «склейки» и «стягивания» вершин понимаются в соответствии с определениями теории графов. Еще одной часто используемой структурой является матрица достижимости графа M+ (или транзитивное замыкание матрицы смежности). Эта матрица также имеет размерность × . Напомним, что элемент [M+] матрицы достижимости равен 1, если в орграфе существует ориентированный путь из вершины в вершину , и 0 – в противном случае. Для построения матрицы достижимости используется алгоритм Уоршелла [3]. Несложно заметить, что M+ представляет собой матрицу RR отображения авторизации ролей .
Часть алгоритмов работы с ролевым графом будет описана на уровне АТД «Граф», часть – на уровне внутреннего представления данных 2. 2 2.1 Локальная оптимизация РРД
Эквивалентные преобразования ролевого графа Под оптимизацией РРД будем понимать преобразования подсистемы безопасности информационной системы, повышающие эффективность ее функционирования. Эффективность может определяться одним или несколькими параметрами, такими как производительность, риски утечки полномочий и т.д. Оптимизация РРД может быть достигнута с помощью преобразования информационных структур, связанных с политикой разграничения доступа. При этом данные изменения должны быть прозрачными для пользователя. Отдельно взятый пользователь должен получать одни и те же полномочия до и после преобразований. Если две политики РРД предоставляют пользователям одни и те же полномочия, то они могут считаться эквивалентными. Более строго данный принцип может быть сформулирован следующим образом. Предположение 1. Две политики РРД эквивалентны, если у них совпадают множества и , а также отображения изоморфны.
Если в результате преобразований РРД будет получена политика разграничения доступа эквивалентная исходной, то можно говорить об эквивалентном преобразовании РРД. Следует отметить, что эквивалентность двух политик РРД накладывает ограничения только на отображение . Отображения , и могут отличаться. В реальных системах из требований непрерывности функционирования информационной системы как правило присутствуют ограничения и на изменения отображений , и . Наиболее распространенным является требование минимизации изменений вносимых в данные отображения. Определение 8. Эквивалентное преобразование РРД, вносящее минимальные изменения в отображения , и и направленное на оптимизацию РРД, будем называть локальной оптимизацией .
Локальная оптимизация РРД по сути представляет собой преобразование ролевого графа. Критерий «минимальные изменения отображений , и » является эвристическим и трудно поддается формализации. В дальнейшем будем руководствоваться следующими рассуждениями.
Одним из основных требований к построению политики РРД является выполнение условия (2), касающееся отображения : вместе с заданной ролью пользователь должен быть авторизован и на все подчиненные роли. Основными каналами утечки информации в политике РРД являются «избыточные полномочия», получаемые пользователем. Поэтому в процессе локальной оптимизации РРД: 1. Изменение подмножества ролей, подчиненных текущей роли, точнее семейства наборов полномочий подчиненных ролей, по возможности должно быть минимальным. 2. Не должно возникнуть ситуации, при которой пользователю для получения требуемого отображением набора полномочий пришлось бы авторизоваться на новую роль с более широкими возможностями. Введем ряд обозначений и определений. Пусть – преобразование ролевого графа, определяющее изменение множества ролей и ролевой иерархии:
(, , , ) = (′, ′, ′, ′).
2Дальнейшая детализация типов данных и методов работы с ними будет зависеть от особенностей объектной модели выбранного языка программирования. Примеры реализации АТД «Граф» на языке C++ можно найти в работе [4]. Определение 9. Преобразование ролевого графа в ролевой граф ′ назовем -допустимым, если: 1. ∀ ∈ ∃′ ∈ (): () = ′(′). Другими словами, множества -классов этих графов связаны отношением включения: (/ v ) ⊆ (′/ v ′).
2. Для любого ориентированного пути (, ) в графе найдется ориентированный путь (, ) в графе ′ такой, что () = ′() и () = ′().
Иногда возможно построить ролевой граф ′ удовлетворяющий более сильному требованию. Определение 10. -допустимое преобразование ролевого графа в ролевой граф ′ назовем -эквивалентным, если:
Из условия (
Исходя из вышесказанного, будем считать, что преобразование ролевого графа в ролевой граф ′ представляет собой локальную оптимизацию РРД, если: 1. Для графа ′ выполнены требования выбранного критерия оптимальности. 2. – -эквивалентное (или -допустимое) преобразование. 3. Число вершин и/или дуг ролевого графа либо не увеличилось, либо это увеличение минимально. Согласно выделенным в разделе 1 дополнительным характеристикам ролевого графа, рассмотрим следующие критерии локальной оптимизации. 3. «Древовидный РГ»: древовидный ролевой граф является оптимальным. 4. «Транзитивно-сокращенный РГ»: транзитивно-сокращенный ролевой граф является оптимальным. Далее будут представлены методики и алгоритмы локальной оптимизации РРД в соответствии с указанными критериями. Эти подходы частично изложены в работах [5, 6]. В данной статье они будут расширены и систематизированы. 2.2
Листовой ролевой граф Теорема 1. Существует -допустимое преобразование ролевого графа в единичный листовой ролевой граф. Доказательство. Пусть – произвольный ролевой граф. Построим ролевой граф ′ по следующему алгоритму. Все вершины, дуги и полномочия графа перенесем в граф ′.
Далее осуществим обход вершин графа . Под обходом графа понимается просмотр всех его вершин в некоторой последовательности. В данном алгоритме обход графа произволен. При этом будем различать листовые (стоковые) и нелистовые вершины. Пусть листовой вершине сопоставлен набор полномочий = {1, . . . , }. Если || = > 1, то в графе ′ к этой вершине присоединим листовых вершин, каждая из которых будет наделена полномочием ( ∈ {1, . . . , }). Каждую нелистовую вершину в графе ′ пополним сыновьями-листьями по числу полномочий из набора () графа , которые не были унаследованы (каждой новой вершине припишем соответствующее полномочие).
Граф ′ является ролевым по построению. В графе ′ каждая нелистовая вершина не получает ни одного полномочия непосредственно, а лишь наследует их от сыновей. Каждой листовой вершине графа ′ приписано одно единственное полномочие. Следовательно, ′ – единичный листовой ролевой граф. Так как является подграфом графа ′, то представленное преобразование ролевого графа является -допустимым Следствие 1.1. Существует -допустимое преобразование ролевого графа в листовой ролевой граф. Доказательство. Принцип построения листового ролевого графа аналогичен алгоритму, представленному в доказательстве предыдущей теоремы. Отличие заключается в том, что листовые вершины сыновьями не пополняются, а каждая нелистовая вершина при необходимости пополняется одним сыном-листом с полномочиями, которые не были унаследованы. Следствие 1.2. Рассмотренные в теореме 1 и следствии 1.1 преобразования ролевого графа являются локальной оптимизацией РРД. Доказательство. Из доказательства теоремы следует, что изменения, вносимые в иерархию ролей, ведут к минимальному «разрастанию» графа. Замечание 1. Доказательства теоремы 1 и следствия 1.1 конструктивны и определяют алгоритмы локальной оптимизации РРД в соответствии с критерием «[единичный] листовой РГ». Замечание 2. Очевидно, алгоритмы локальной оптимизации РРД в соответствии с критерием «[единичный] листовой РГ» сохраняют древовидность ролевого графа.
Заметим, что алгоритмы построения [единичного] листового ролевого графа не единственны. В представленном подходе избавление от «охватности» распределения полномочий происходит только за счет добавления новых вершин, метки которых соответствуют неунаследованным полномочиям. Можно было бы попытаться унаследовать эти полномочия от уже имеющихся вершин. Но такой подход также не однозначен и может привести не только к потере древовидности, но и к существенном изменению множества -классов. 2.3 -сокращенный ролевой граф В процессе локальной оптимизации РРД в соответствии с критерием «[единичный] листовой РГ» может увеличиться не только количество ролей и -классов, но и мощность самих -классов. Последнее свидетельствует о наличии в системе «дублирующих» ролей. В ряде случаев требование отсутствия «дублирующих» ролей является существенным. Тогда необходимо гарантировать -сокращенность ролевого графа, быть может отказавшись от листового принципа распределения полномочий или от древовидной структуры иерархии ролей. Теорема 2. Существует -эквивалентное преобразование ролевого графа в -сокращенный ролевой граф. Доказательство. В ролевом графе достаточно «склеить» вершины-роли, попадающие в один класс, если они не соединены дугами, либо попарно «стянуть», если такие дуги имеются. Полученный граф ′ будет ролевым по построению. Множество -классов останется прежним, но граф ′ будет сокращенным. Очевидно, что для любого ориентированного пути в одном из графов найдется ориентированный путь в другом графе такой, что совпадают метки начальных вершин и совпадают метки конечных вершин. Следовательно, представленное преобразование ролевого графа является -эквивалентным. Следствие 2.1. Рассмотренное в теореме 2 преобразование ролевого графа является локальной оптимизацией РРД. Доказательство. В процессе «склейки» и «стягивания» вершин графа число вершин и дуг не увеличивается. Замечание 3. Доказательство теоремы 2 конструктивно и определяет алгоритм локальной оптимизации ролевого графа в соответствии с критерием « -сокращенный РГ». Замечание 4. Несложно понять, что алгоритм локальной оптимизации ролевого графа в соответствии с критерием « -сокращенный РГ» сохраняет листовой принцип распределения полномочий. Более того, если исходный ролевой граф был единичным листовым, то результирующий станет единичным таксономическим листовым. Поэтому данный алгоритм целесообразно применять после алгоритма построения единичного листового ролевого графа (который может привести к появлению вершин с одинаковыми метками). Теорема 3. Существует -допустимое преобразование ролевого графа в единичный таксономический листовой -сокращенный ролевой граф. Доказательство. С учетом замечания 4 достаточно последовательно применить преобразования, описанные в теоремах 1 и 2. Следствие 3.1. Рассмотренное в теореме 3 преобразование ролевого графа является локальной оптимизацией РРД. Для доказательства следующей теоремы требуется, чтобы ролевой граф имел ровно один источник (вершину без входящих дуг). В противном случае ролевой граф может быть пополнен фиктивной вершинойсуперисточником , которая соединяется дугами со всеми существующими источниками 1, . . . , . Метка суперисточника формируется по правилу наследования: () = (1) ∪ . . . ∪ (). Заметим, что так как в ролевом графе отсутствуют ориентированные циклы, то требование единственности источника влечет за собой связность ролевого графа. Теорема 4. Существует -эквивалентное преобразование ролевого графа с единственным источником в ролевое дерево. Доказательство. Пусть дан ролевой граф . -эквивалентное ему ролевое дерево будем формировать последовательно. В начале каждому стоку графа сопоставляем +( ) листьев в графе : «оригинал» и (+( ) − 1) «ярлыков» (здесь и далее +() – полустепень захода вершины ). Эта операция называется расщеплением вершины. Если полустепень захода равна единице, то имеется только «оригинал».
Далее, двигаясь по графу от нижних ярусов к источнику в порядке возрастания длины самого протяженного из путей от текущей вершины до стоков, последовательно расщепляем все вершины. «Оригинал» и «ярлыки» наделяем теми же полномочиями, что были у вершины их образующей. К «оригиналу» присоединяем уже существующие вершины графа из тех, что не имеют входящих дуг, восстанавливая сыновей расщепляемой вершины графа (такие вершины в всегда найдутся по построению). К каждому «ярлыку» добавляем вершины и дуги так, чтобы подграф, порожденный «ярлыком», представлял собой копию поддерева, порожденного «оригиналом».
Очевидно, что построенный таким образом граф является ролевым деревом и имеет те же -классы, что и исходный ролевой граф . Кроме того для любого ориентированного пути в одном из графов найдется ориентированный путь в другом графе такой, что совпадают метки начальных вершин и совпадают метки конечных вершин. Таким образом рассмотренное преобразование ролевого графа является эквивалентным. Следствие 4.1. Рассмотренное в теореме 4 преобразование ролевого графа является локальной оптимизацией РРД. Доказательство. Предложенный в доказательстве порядок обхода вершин графа позволит минимизировать увеличение числа вершин и дуг. Следствие 4.2. Число вершин ′ результирующего ролевого дерева не превосходит O(3), где – число вершин исходного ролевого графа. Доказательство. Пусть – рассматриваемое преобразование ролевого графа. По построению ′ = + ∑︁ (︀ +() − 1︀) |′(′)|,
∈ где ′ ∈ () – произвольна. Так как поддеревья, присоединяемые к «ярлыкам», восстанавливают сыновей расщепляемой вершины исходного графа, то |′(′)| ≤ . Следовательно: ′ ≤ + ∑︁ (︀ +() − 1︀) ≤ + ( − 1) 2 = O(3).
∈ Замечание 5. Доказательство теоремы 4 конструктивно и определяет алгоритм локальной оптимизации ролевого графа в соответствии с критерием «древовидный РГ». Замечание 6. Несложно понять, что алгоритм локальной оптимизации ролевого графа в соответствии с критерием «древовидный РГ» сохраняет [единичный] листовой принцип распределения полномочий. Учитывая замечание 2, алгоритмы локальной оптимизации в соответствии с критериями «древовидный РГ» и «[единичный] листовой РГ» можно применять в любом порядке и получать [единичное] листовое ролевое дерево. Очевидно, что алгоритм построения ролевого дерева имеет большую трудоемкость, поэтому его целесообразно применять в первую очередь. Теорема 5. Существует -допустимое преобразование ролевого графа с единственным источником в [единичное] листовое ролевое дерево. Доказательство. С учетом замечания 6 достаточно последовательно применить преобразования, описанные в теоремах 4 и 1. Следствие 5.1. Рассмотренное в теореме 5 преобразование ролевого графа является локальной оптимизацией РРД. 2.5 Транзитивно-сокращенный ролевой граф Построение транзитивно-сокращенного ролевого графа заключается в получении графа, описывающего исходную иерархию ролей но не содержащего транзитивные дуги. Отсюда следует: Теорема 6. Переход к транзитивно-сокращенному ролевому графу является -эквивалентным преобразованием. Следствие 6.1. Переход к транзитивно-сокращенному ролевому графу является локальной оптимизацией РРД. Замечание 7. Очевидно, что если ролевой граф древовидный, то он не имеет транзитивных дуг и является транзитивно-сокращенным. В общем случае переход к транзитивно-сокращенному ролевому графу не изменяет метки вершин. Поэтому для упрощения ролевой иерархии оптимизация ролевого графа в соответствии с критерием «транзитивно-сокращенный РГ» должна предшествовать другим видам оптимизации. Вместе с тем, оптимизация в соответствии с критерием « -сокращенный РГ» может привести к появлению транзитивных дуг. В этом случае следует вновь перейти к транзитивно-сокращенному графу. 2.6
Алгоритмы и оценка трудоемкости
По-прежнему метку вершины будем представлять -мерным битовым вектором . (см. формулу (
Пусть ролевой граф задан -мерным вектором списков смежности . Элемент [] вектора соответствует вершине графа и содержит следующие поля 3:
1) []. – целочисленный список номеров тех вершин, в которые ведут дуги из вершины (список смежности); 2) []. – метка вершины .
3Для -й координаты вектора наряду с обозначением [ ] будем использовать запись []. Аналогично для матриц: [M] = M[, ].
. ⊕ {
⋁︁ . = . ⇔ . ⊕ . = ⃗0. Доказательство. Число шагов алгоритма оценивается сверху величиной (O() + O( · )) = O( · 2).
Алгоритм оптимизации ролевого графа по критерию «листовой РГ» отличается тем, что просматриваются только те элементы [] вектора , для которых список смежности []. не пуст. И если найден элемент с ненулевым вектором , то: в ′ добавляется один новый элемент, ему приписывается метка , список смежности ′[]. пополняется этим новым элементом. Очевидно, что трудоемкость этого алгоритма имеет ту же оценку, что и для алгоритма построения единичного листового ролевого графа. 2.6.2
Алгоритм оптимизации ролевого графа по критерию « -сокращенный РГ»
Пока в найдется два элемента [] и [] такие, что []. ⊕ []. = ⃗0 (см. формулу (
Иначе для этих вершин выполнить операцию «стянуть» АТД «Граф». Утверждение 3. Трудоемкость алгоритма оптимизации ролевого графа по критерию « сокращенный РГ» не превосходит O( · 4)), где – число ролей, – число полномочий. Доказательство. Число шагов алгоритма оценивается сверху величиной 2 · (O() · O(2)) = O( · 4). 2.6.3
Алгоритм оптимизации ролевого графа по критерию «древовидный РГ» Для реализации алгоритма необходимо сформировать два вектора. – -мерный целочисленный вектор. Элемент [] вектора – это полустепень захода (число входящих дуг) вершины ролевого графа. Алгоритм формирования вектора : 1. Вектор инициализировать нулями. 2. Для каждого = 1, . . . , обойти список смежности [].. 3. Для каждого – очередного элемента -го списка смежности: [] := [] + 1. – -мерный вектор. Элемент [] вектора состоит из двух целочисленных полей: 1) []. – номер вершины графа; 2) []. – длина самого протяженного из ориентированных путей от вершины с номером []. до стоков (для дерева – до листовых вершин).
Алгоритм формирования вектора : 1. Реализовать модифицированный алгоритм Флойда [3]: на вход алгоритму подается вектор списков смежности , на выходе формируется матрица H размерности × такая, что H[, ] есть длина самого
1. На каждом шаге строится ориентированный ациклический граф . На начальном этапе граф 0 пуст. Число шагов алгоритма равно порядку графа , то есть = . В процессе построения дерева в определенной последовательности обходятся все вершины орграфа и на каждом шаге ( = 1, . . . , ) граф пополняется вершинами и дугами. шины . После просмотра всех стоков 1 , . . . , графа , граф представляет собой ∑︀ =1 +( ) изолированных вершин. 5. Для каждого ярлыка 2 , . . . , добавляются новые вершины-ярлыки и дуги так, чтобы подграф ( = 2, . . . , ), порожденный ярлыком и всеми его потомками, представлял собой копию поддерева вы1м, ипонроомжердаенмнио,гво гвреарфшеи нойв-еорршиигинныа-лоромиг ин1аилывсзеамкиреаешпеонтыо,мвкеармшии;нмые-тякрилывекриш–иннезта)м.енены порядкоОбход графа следует вести в порядке, определяемом вектором : индекс очередного элемента вектора лежит в []. ( = 1, . . . , ). Для удобства далее очередной индекс будем обозначать .
Дерево также представляется вектором списков смежности . Но набор полей элементов вектора следует расширить. Каждый -й элемент вектора должен содержать:
1) []. – целочисленный список номеров тех вершин, в которые ведут дуги из -й вершины (список смежности); 2) []. – метка вершины – -мерный битовый вектор.
3) []. – индекс вершины исходного графа , которой была сопоставлена данная вершина в графе ; 4) []. – полустепень захода вершины.
Кроме того, вектор должен динамически наращивать размерность, так как заранее число вершин дерева не известно. Изначально вектор пуст. Процесс сопоставления вершине графа вершиныоригинала и ярлыков в графе будет заключаться в следующем.
Для построения вершины-оригинала 1 в вектор добавляется очередной элемент : []. := []., []. := , []. := 0, []. := 0 Чтобы построить исходящие из вершины-оригинала дуги, необходимо для каждого элемента списка смежности []. пройти по вектору , чтобы найти индекс такой, что []. = и []. = 0. Найденный индекс надо добавить в список смежности []., а также []. := 0. Утверждение 4. Трудоемкость алгоритм оптимизации ролевого графа по критерию «древовидный РГ» полиномиально зависит от числа вершин и числа полномочий. Доказательство. Обоснованием является следствие 4.2. Для реализации этого алгоритма используется матричное представление ролевого графа. Известно, что транзитивное сокращение ℛ− отношения порядка ℛ можно найти, используя его транзитивное замыкание ℛ+ и операции разности «− » и композиции «∘ » отношений: ℛ− = ℛ − (ℛ ∘ ℛ +). Переходя от отношений порядка к ориентированным графам, получаем, что матрица смежности M− диаграммы Хассе ролевого графа может быть вычислена через матрицы смежности M и достижимости M+ исходного ролевого графа:
M− = M − (M ∘ M+). При этом композиция и разность понимаются как «булево произведение» и «булева разность» бинарных матриц: (M1 ∘ M2)[, ] = M1[, 1] ∧ M2[1, ] ∨ . . . ∨ M1[, ] ∧ M2[, ],
(M1 − M2)[, ] = M1[, ] ∧ M2[, ]. Утверждение 5. Трудоемкость алгоритма оптимизации ролевого графа по критерию «транзитивносокращенный РГ» не превосходит O(3), где – число ролей. Доказательство. Очевидно, что искомая трудоемкость складывается из трудоемкости алгоритма построения матрицы достижимости и трудоемкости операций композиции и разности матриц. Алгоритм Уоршелла, используемый для построения матрицы достижимости, имеет трудоемкость O(3) [3]. Трудоемкость операций композиции и разности матриц равна O(3) и O(2), соответственно. 2.7 Выводы Удалось показать, что одной и той же политике РРД может соответствовать несколько ролевых графов. Причем возможна проверка эквивалентности ролевых графов с точки зрения распределения полномочий. Этот факт является существенным в развитии модели РРД, так как позволяет строить различные представления иерархии ролей, оптимальные в различных смыслах (см. табл. 1).
Критерий 1 2 3 4 1+2 3+1
Таблица 1: Алгоритмы локальной оптимизации Оптимальный ролевой граф Сохраняется
Листовой Древовидность -сокращенный Листовое распределение полномочий
Древовидный Листовое распределение полномочий Транзитивно-сокращенный Вся иерархия Листовой + -сокращенный
Листовой + Древовидный Список литературы [1] URL: http://graphml.graphdrawing.org/primer/graphml-primer.html . [2] N. F. Bogachenko. The Mutual Exclusion Relation on a Set of Roles in Access Control Models. CEUR
Workshop Proceedings, 1732, 2016. URL: http://ceur-ws.org/Vol-1732/paper4.pdf .
Local Optimization of the Role-Based Access Control Policy
Nadezda F. Bogachenko