Локальная оптимизация политики ролевого разграничения доступа Н.Ф. Богаченко nfbogachenko@mail.ru Омский государственный университет им. Ф.М. Достоевского, Омск, Россия Аннотация В статье описываются структурные модификации иерархии ролей в политике ролевого разграничения доступа. Строятся и обосновы- ваются алгоритмы преобразования ролевого графа с учетом раз- личных критериев его оптимальности. При этом рассматриваются такие характеристики, как принципы распространения полномочий в системе, отсутствие дублирующих ролей, особенности ролевого графа, в частности, его древовидность. Основным результатом яв- ляется доказательство возможности получения нескольких роле- вых графов, соответствующих эквивалентным политикам ролевого разграничения доступа. 1 Ролевой граф Ролевое разграничение доступа (РРД) основывается на запрещении или разрешении действий в системе в целом, без привязки к отдельным объектам системы. Возможность осуществлять такие действия называ- ется полномочием (правом, привилегией). Каждая роль представляет собой некоторый типовой набор пол- номочий. Роли ассоциируются с субъектами (пользователями ) компьютерной системы. При этом одному пользователю может приписываться несколько ролей, и наоборот, на одну роль может быть авторизовано несколько пользователей. В процессе авторизации пользователя на роль он получает и набор полномочий, закрепленный за выданной ролью. Выделим основные элементы модели РРД, которые понадобятся для дальнейшего описания. Основные множества: 1. 𝑃 = {𝑝1 , . . . , 𝑝𝑚 } – множество полномочий (прав доступа, привилегий) на действия в системе. 2. 𝑅 = {𝑟1 , . . . , 𝑟𝑛 } – множество ролей, возможных в системе. 3. 𝑈 = {𝑢1 , . . . , 𝑢𝑠 } – множество пользователей системы. Основные отображения: 1. 𝑅𝑃 : 𝑅 → 2𝑃 . 𝑅𝑃 (𝑟) предоставляет набор полномочий роли 𝑟. При этом ∀ 𝑝 ∈ 𝑃 ∃ 𝑟 ∈ 𝑅 : 𝑝 ∈ 𝑅𝑃 (𝑟). 2. 𝑅𝑅 : 𝑅 → 2𝑅 . 𝑅𝑅(𝑟) определяет роли, на которые должна быть авторизована роль 𝑟. c by the paper’s authors. Copying permitted for private and academic purposes. Copyright ○ In: Sergey V. Belim, Nadezda F. Bogachenko (eds.): Proceedings of the Workshop on Data, Modeling and Security 2017 (DMS-2017), Omsk, Russia, October 2017, published at http://ceur-ws.org 3. 𝑈 𝑅 : 𝑈 → 2𝑅 . 𝑈 𝑅(𝑢) определяет набор ролей, на которые может быть авторизован пользователь 𝑢. Возможно существование ролей, на которые не авторизован ни один пользователь. 4. 𝑈 𝑃 : 𝑈 → 2𝑃 . 𝑈 𝑃 (𝑢) задает набор полномочий, необходимых пользователю 𝑢 для работы в системе. Заметим, что так как множества 𝑃 , 𝑅 и 𝑈 конечны, то все рассматриваемые дискретные отображения могут быть представлены булевыми матрицами по правилу: если 𝐹 : 𝑋 → 2𝑌 , то элемент матрицы [F]𝑖𝑗 = 1 ⇐⇒ 𝑦𝑗 ∈ 𝐹 (𝑥𝑖 ). Ведущую роль в списке основных отображений играет отображение авторизации ролей друг на друга 𝑅𝑅, которое должно сформировать иерархию ролей – отношение нестрогого частичного порядка на множе- стве 𝑅 (отношение авторизации ). Отношение авторизации обозначим оператором доминирования/подчи- нения ролей «≻» («≺»): 𝑟𝑖 ≻ 𝑟𝑗 (𝑟𝑗 ≺ 𝑟𝑖 ) ⇐⇒ 𝑟𝑗 ∈ 𝑅𝑅(𝑟𝑖 ) – в этом случае роль 𝑟𝑖 является доминирующей (старшей), а роль 𝑟𝑗 – подчиненной (младшей). Рефлективность, антисимметричность и транзитивность отношения авторизации определяют следующие свойства отображения 𝑅𝑅: 1. 𝑟𝑖 ∈ 𝑅𝑅(𝑟𝑖 ). 2. Если 𝑟𝑗 ∈ 𝑅𝑅(𝑟𝑖 ) ∧ 𝑟𝑖 ∈ 𝑅𝑅(𝑟𝑗 ), то 𝑟𝑖 = 𝑟𝑗 . 3. Если 𝑟𝑗 ∈ 𝑅𝑅(𝑟𝑖 ) ∧ 𝑟𝑘 ∈ 𝑅𝑅(𝑟𝑗 ), то 𝑟𝑘 ∈ 𝑅𝑅(𝑟𝑖 ). Множество 𝑅𝑅(𝑟) называется множеством достижимости роли 𝑟. Основные требования РРД заключаются в том, что отображения 𝑅𝑅 и 𝑅𝑃 должны гарантировать выполнение условия наследования полномочий : (𝑟𝑗 ≺ 𝑟𝑖 ) ⇒ (𝑅𝑃 (𝑟𝑗 ) ⊆ 𝑅𝑃 (𝑟𝑖 )), (1) а отображения 𝑅𝑅 и 𝑈 𝑅 должны обеспечивать выполнение условия наследования авторизации : (𝑟𝑗 ≺ 𝑟𝑖 ) ∧ (𝑟𝑖 ∈ 𝑈 𝑅(𝑢)) ⇒ (𝑟𝑗 ∈ 𝑈 𝑅(𝑢)), (2) Заметим, что описанные отображения должны быть взаимнокорректны, то есть связаны соотношением: ⋃︁ 𝑈 𝑃 (𝑢) ⊆ 𝑅𝑃 (𝑟). (3) 𝑟∈𝑈 𝑅(𝑢) Рассмотрим более подробно отношение порядка, введенное на множестве ролей. Традиционно для анали- за структуры частично упорядоченного множества используется диаграмма Хассе – теоретико-графовое представление отношения порядка «≻», в котором дуга (𝑟𝑖 , 𝑟𝑗 ) существует тогда и только тогда, когда 𝑟𝑖 ≻ 𝑟𝑗 и не существует ориентированного пути 𝜌(𝑟𝑖 , 𝑟𝑗 ) такого, что его длина строго больше единицы (в противном случае дуга (𝑟𝑖 , 𝑟𝑗 ) называется транзитивной ). Диаграмма Хассе имеет наименьшее число дуг среди всех графов, порождаемых заданным отношением порядка. Диаграмму Хассе называют транзитив- ным сокращением отношения порядка или транзитивной редукцией ориентированного графа. В рамках модели РРД также будем использовать графовую интерпретацию иерархии ролей. Определение 1. Помеченный ориентированный граф 𝐺 = (𝑅, 𝐸, 𝑅𝑃 ) назовем ролевым графом, если множество его вершин определяется множеством ролей 𝑅; множество дуг порождается отношением авто- ризации, заданным на множестве ролей (отображением 𝑅𝑅); метки вершин определяются отображением 𝑅𝑃 . Исходя из вышесказанного, ролевой граф – это граф, порождаемый отображениями 𝑅𝑅 и 𝑅𝑃 , и обла- дающий следующими характеристиками : ∙ Ориентированный. ∙ Бесконтурный (отсутствуют ориентированные циклы) – в силу антисимметричности отношения по- рядка. ∙ Помеченный. ∙ Выполнено условие наследования меток – условие (1). При решении ряда задач требуется выполнение еще одного ограничения – ролевой граф должен быть связным. Это свойство возможно получить путем добавления фиктивной вершины, связанной дугами со всеми источниками (вершинами без входящих дуг) ролевого графа. Заметим, что ролевой граф не обязан являться диаграммой Хассе. Одной и той же иерархии ролей в общем случае можно сопоставить несколько ролевых графов. Такие графы назовем 𝑅𝑅-эквивалентными. Очевидно, 𝑅𝑅-эквивалентные ролевые графы отличаются друг от друга множеством дуг. Транзитивные дуги могут появляться в ходе эквивалентных преобразований политики РРД. Определение 2. Ролевой граф назовем транзитивно-сокращенным, если он является диаграммой Хассе. В большинстве работ посвященных РРД принято считать, что иерархия ролей имеет вид ориентиро- ванного дерева – бесконтурного ориентированного графа, у которого полустепень захода (число входящих дуг) любой вершины не больше 1 и существует ровно одна вершина (корень), полустепень захода которой равна 0. Определение 3. Древовидный ролевой граф будем называть ролевым деревом и обозначать 𝑇 = (𝑅, 𝐸, 𝑅𝑃 ). При иерархическом отношении ролей особое внимание уделяется процессу построения отображения 𝑅𝑃 . Важным является вопрос: возможно ли назначение одного и того же набора полномочий двум ролям, на- ходящимся в иерархическом подчинении. Для построения используется ролевой граф и применяется меха- низм наследования «снизу – вверх»: расстановка меток (распределение полномочий) начинается с листьев или стоков (вершин без исходящих дуг) ролевого графа. Пусть 𝑅𝐿 (𝑅𝐿 ⊆ 𝑅) – множество стоков, 𝐶ℎ(𝑟) – множество вершин-сыновей вершины 𝑟. Возможны два подхода к расстановке меток, порождающих, в свою очередь, две различные 𝑅𝑃 -характеристики ролевого графа. Определение 4. Листовой ролевой граф (листовая 𝑅𝑃 -характеристика). Каждому стоку 𝑟 отображение 𝑅𝑃 сопоставляет набор полномочий 𝑅𝑃 (𝑟) так, чтобы ⋃︁ 𝑅𝑃 (𝑟) = 𝑃. 𝑟∈𝑅𝐿 Метки остальных вершин наследуются: ⋃︁ ∀𝑟 ∈ 𝑅 ∖ 𝑅𝐿 : 𝑅𝑃 (𝑟) = 𝑅𝑃 (𝑟′ ). 𝑟 ′ ∈𝐶ℎ(𝑟) Если ∀𝑟𝑖 , 𝑟𝑗 ∈ 𝑅𝐿 : 𝑅𝑃 (𝑟𝑖 ) ∩ 𝑅𝑃 (𝑟𝑗 ) = ∅, то листовой ролевой граф называется таксономическим, иначе – нетаксономическим. Если ∀𝑟 ∈ 𝑅𝐿 : |𝑅𝑃 (𝑟)| = 1, то листовой ролевой граф называется единичным, иначе – общим. Определение 5. Охватный ролевой граф (охватная 𝑅𝑃 -характеристика). Допускается включение в наборы полномочий вершин «добавочных» полномочий, ненаследуемых от сыновей. Это означает, что ⋃︁ 𝑅𝑃 (𝑟) ⊆ 𝑃. 𝑟∈𝑅𝐿 Определение 6. Роли 𝑟𝑖 и 𝑟𝑗 назовем 𝑅𝑃 -эквивалентными, если они наделены одинаковыми наборами 𝑅𝑃 полномочий: ∀𝑟𝑖 , 𝑟𝑗 ∈ 𝑅 : (𝑟𝑖 v 𝑟𝑗 ) ⇐⇒ (𝑅𝑃 (𝑟𝑖 ) = 𝑅𝑃 (𝑟𝑗 )). Тем самым множество ролей 𝑅 разбивается на классы эквивалентности – 𝑅𝑃 -классы. Определение 7. Ролевой граф назовем 𝑅𝑃 -сокращенным, если каждый его 𝑅𝑃 -класс содержит ровно одну роль (метки всех вершин различны). Обобщая вышесказанное, можно выделить следующие дополнительные характеристики ролевого гра- фа: ∙ Листовой (в том числе единичный и/или таксономический). ∙ 𝑅𝑃 -сокращенный. ∙ Древовидный. ∙ Транзитивно-сокращенный. Последнее свойство непосредственно касается только ролевого графа и никак не характеризует иерархию ролей. Для разработки алгоритмов преобразования ролевого графа и оценки их трудоемкости необходимо учи- тывать особенности представления (описания) графов. Для задания наборов полномочий ролей (меток вершин ролевого графа) удобно использовать векторное представление: метка вершины 𝑟 – это 𝑚-мерный битовый вектор (массив, строка) 𝑟.𝑝: {︂ 1, 𝑝𝑘 ∈ 𝑅𝑃 (𝑟) [𝑟.𝑝]𝑘 = , (𝑘 = 1, . . . , 𝑚). (4) 0, 𝑝𝑘 ∈ / 𝑅𝑃 (𝑟) Рассматривая способы описания графа, необходимо различать файловое и программное (внутреннее) представления. При программно-технической реализации политики РРД возникает подзадача файлово- го представления ролевого графа, одновременно удобного и для машинной обработки, и для восприятия человеком. Возможны два подхода: разработка собственного языка представления помеченного ориентиро- ванного графа или выбор одного из общепризнанных стандартов для представления теоретико-графовых моделей. Предпочтение следует отдать второму подходу, так как использование стандартизованного языка для описания ролевого графа позволит сократить время разработки и обеспечит совместимость со многи- ми прикладными программами и библиотеками для работы с графами. В большинстве стандартов граф задается двумя списками [1, 2]: 1. Список вершин графа; каждой вершине приписана метка – битовая строка длины 𝑚 (см. формулу 4). 2. Список дуг графа; каждая дуга задана начальной и конечной вершинами. Формальное описание алгоритмов на графах удобно вести в терминах абстрактного типа данных (АТД) «Граф». Интерфейс этого АТД должен включать следующие операции (методы) работы с графом: ∙ добавить / удалить вершину; ∙ добавить / удалить ребро; ∙ задать метку вершины; ∙ «склеить» / «стянуть» вершины 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. Множества 𝑅𝑃 -классов этих графов совпадают: (𝐺/ v ) = (𝐺′ / v ). 2. Для любого ориентированного пути в одном из графов найдется ориентированный путь в другом графе такой, что совпадают метки начальных вершин и совпадают метки конечных вершин. Из условия (3) о взаимной корректности основных отображений РРД следует: Утверждение 1. 𝑅𝑃 -допустимое (𝑅𝑃 -эквивалентное) преобразование ролевого графа приводит к по- строению эквивалентной политики РРД. Исходя из вышесказанного, будем считать, что преобразование 𝐹 ролевого графа 𝐺 в ролевой граф 𝐺′ представляет собой локальную оптимизацию РРД, если: 1. Для графа 𝐺′ выполнены требования выбранного критерия оптимальности. 2. 𝐹 – 𝑅𝑃 -эквивалентное (или 𝑅𝑃 -допустимое) преобразование. 3. Число вершин и/или дуг ролевого графа либо не увеличилось, либо это увеличение минимально. Согласно выделенным в разделе 1 дополнительным характеристикам ролевого графа, рассмотрим сле- дующие критерии локальной оптимизации. 1. «[Единичный] листовой РГ»: [единичный] листовой ролевой граф является оптимальным. 2. «𝑅𝑃 -сокращенный РГ»: 𝑅𝑃 -сокращенный ролевой граф является оптимальным. 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 преобразование ролевого графа является локальной опти- мизацией РРД. 2.4 Ролевое дерево Для доказательства следующей теоремы требуется, чтобы ролевой граф имел ровно один источник (вер- шину без входящих дуг). В противном случае ролевой граф может быть пополнен фиктивной вершиной- суперисточником 𝑠, которая соединяется дугами со всеми существующими источниками 𝑠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 Алгоритмы и оценка трудоемкости По-прежнему метку вершины 𝑟 будем представлять 𝑚-мерным битовым вектором 𝑟.𝑝 (см. формулу (4)). Пусть для битовых векторов перегружены следующие операции: ∨ – побитовая дизъюнкция, ⊕ – побитовое сложение по mod 2. Нулевой вектор обозначим ⃗0. Заметим, что вектор 𝑟𝑖 .𝑝⊕𝑟𝑗 .𝑝 предоставляет полномочия, которыми различаются вершины 𝑟𝑖 и 𝑟𝑗 . Следовательно, вектор ⋁︁ 𝑟.𝑝 ⊕ { 𝑟′ .𝑝} (5) 𝑟 ′ ∈𝐶ℎ(𝑟) определяет полномочия, которые вершина 𝑟 получает непосредственно, а не за счет наследования (𝐶ℎ(𝑟) – множество вершин-сыновей вершины 𝑟). Для проверки того, что ролевой граф является 𝑅𝑃 -сокращенным, удобно использовать свойство меток: 𝑟𝑖 .𝑝 = 𝑟𝑗 .𝑝 ⇔ 𝑟𝑖 .𝑝 ⊕ 𝑟𝑗 .𝑝 = ⃗0. (6) Пусть ролевой граф задан 𝑛-мерным вектором списков смежности 𝑆 . Элемент 𝑆[𝑖] вектора 𝑆 соответ- ствует вершине 𝑟𝑖 графа и содержит следующие поля3 : 1) 𝑆[𝑖].𝑙𝑖𝑠𝑡 – целочисленный список номеров тех вершин, в которые ведут дуги из вершины 𝑟𝑖 (список смежности); 2) 𝑆[𝑖].𝑝 – метка вершины 𝑟𝑖 . 3 Для 𝑖-й координаты вектора 𝑉 наряду с обозначением [𝑉 ] будем использовать запись 𝑉 [𝑖]. Аналогично для матриц: 𝑖 [M]𝑖𝑗 = M[𝑖, 𝑗]. 2.6.1 Алгоритм оптимизации ролевого графа по критерию «единичный листовой РГ» Создать копию 𝑆 ′ вектора 𝑆 . Последовательно просмотреть все элементы вектора 𝑆 . Если список смежно- сти 𝑆[𝑗].𝑙𝑖𝑠𝑡 очередного элемента пуст (вершина 𝑟𝑗 является стоком или листом) и вектор 𝑆[𝑗].𝑝 содержит более одной единичной координаты, то: – в 𝑆 ′ добавить новые элементы по числу единичных координат вектора 𝑆[𝑗].𝑝, – приписать новым элементам метки, каждая из которых определяется одной единичной координатой вектора 𝑆[𝑗].𝑝, – пополнить список смежности 𝑆 ′ [𝑗].𝑙𝑖𝑠𝑡 новыми элементами. Если список смежности 𝑆[𝑗].𝑙𝑖𝑠𝑡 очередного элемента не пуст (вершина 𝑟𝑗 нелистовая), то сформировать 𝑚-мерный битовый вектор 𝑉 в соответствии с формулой (5): при этом просмотр всех сыновей вершины 𝑟𝑗 заключается в просмотре списка смежности 𝑆[𝑗].𝑙𝑖𝑠𝑡. Если 𝑉 ̸= ⃗0, то: – в 𝑆 ′ добавить новые элементы по числу единичных координат вектора 𝑉 , – приписать новым элементам метки, каждая из которых определяется одной единичной координатой вектора 𝑉 , – пополнить список смежности 𝑆 ′ [𝑗].𝑙𝑖𝑠𝑡 новыми элементами. Утверждение 2. Трудоемкость алгоритм оптимизации ролевого графа по критерию «единичный ли- стовой РГ» не превосходит O(𝑚 · 𝑛2 )), где 𝑛 – число ролей, 𝑚 – число полномочий. Доказательство. Число шагов алгоритма оценивается сверху величиной 𝑛(O(𝑚) + O(𝑚 · 𝑛)) = O(𝑚 · 𝑛2 ).  Алгоритм оптимизации ролевого графа по критерию «листовой РГ» отличается тем, что просматрива- ются только те элементы 𝑆[𝑗] вектора 𝑆 , для которых список смежности 𝑆[𝑗].𝑙𝑖𝑠𝑡 не пуст. И если найден элемент с ненулевым вектором 𝑉 , то: в 𝑆 ′ добавляется один новый элемент, ему приписывается метка 𝑉 , список смежности 𝑆 ′ [𝑗].𝑙𝑖𝑠𝑡 пополняется этим новым элементом. Очевидно, что трудоемкость этого алго- ритма имеет ту же оценку, что и для алгоритма построения единичного листового ролевого графа. 2.6.2 Алгоритм оптимизации ролевого графа по критерию «𝑅𝑃 -сокращенный РГ» Пока в 𝑆 найдется два элемента 𝑆[𝑖] и 𝑆[𝑗] такие, что 𝑆[𝑖].𝑝 ⊕ 𝑆[𝑗].𝑝 = ⃗0 (см. формулу (6)), выполнять: Если индекс 𝑖 содержится в списке 𝑆[𝑗].𝑙𝑖𝑠𝑡 или индекс 𝑗 содержится в списке 𝑆[𝑖].𝑙𝑖𝑠𝑡 (вершины 𝑟𝑖 и 𝑟𝑗 смежны), то для вершин 𝑟𝑖 и 𝑟𝑗 выполнить операцию «склеить» АТД «Граф». Иначе для этих вершин выполнить операцию «стянуть» АТД «Граф». Утверждение 3. Трудоемкость алгоритма оптимизации ролевого графа по критерию «𝑅𝑃 - сокращенный РГ» не превосходит O(𝑚 · 𝑛4 )), где 𝑛 – число ролей, 𝑚 – число полномочий. Доказательство. Число шагов алгоритма оценивается сверху величиной 𝑛2 · (O(𝑚) · O(𝑛2 )) = O(𝑚 · 𝑛4 ).  2.6.3 Алгоритм оптимизации ролевого графа по критерию «древовидный РГ» Для реализации алгоритма необходимо сформировать два вектора. 𝐷 – 𝑛-мерный целочисленный вектор. Элемент 𝐷[𝑖] вектора 𝐷 – это полустепень захода (число входящих дуг) вершины 𝑟𝑖 ролевого графа. Алгоритм формирования вектора 𝐷: 1. Вектор 𝐷 инициализировать нулями. 2. Для каждого 𝑖 = 1, . . . , 𝑛 обойти список смежности 𝑆[𝑖].𝑙𝑖𝑠𝑡. 3. Для каждого 𝑗 – очередного элемента 𝑖-го списка смежности: 𝐷[𝑗] := 𝐷[𝑗] + 1. 𝑄 – 𝑛-мерный вектор. Элемент 𝑄[𝑖] вектора 𝑄 состоит из двух целочисленных полей: 1) 𝑄[𝑖].𝑟 – номер вершины графа; 2) 𝑄[𝑖].𝑙 – длина самого протяженного из ориентированных путей от вершины с номером 𝑄[𝑖].𝑟 до стоков (для дерева – до листовых вершин). Алгоритм формирования вектора 𝑄: 1. Реализовать модифицированный алгоритм Флойда [3]: на вход алгоритму подается вектор списков смежности 𝑆 , на выходе формируется матрица H размерности 𝑛 × 𝑛 такая, что H[𝑖, 𝑗] есть длина самого протяженного ориентированного пути из вершины 𝑟𝑖 в вершину 𝑟𝑗 (под длиной маршрута понимается число входящих в него дуг; если вершина 𝑟𝑗 не достижима из вершины 𝑟𝑖 , то H[𝑖, 𝑗] := −1). 2. Начальная инициализация: 𝑄[𝑖].𝑟 := 𝑖, 𝑄[𝑖].𝑙 := 0 (𝑖 = 1, . . . , 𝑛). 3. Для каждого 𝑖 = 1, . . . , 𝑛: 𝑄[𝑖].𝑙 := max(𝑗=1,...,𝑛)∧(𝑆[𝑗].𝑙𝑖𝑠𝑡=0) {H[𝑖, 𝑗]}. 4. Упорядочить элементы вектора 𝑄 по неубыванию величины 𝑄[𝑖].𝑙. Очевидно, что вершины-стоки (листья) расположены в начале вектора 𝑄, далее следуют вершины, связанные со стоками только дугой, и т.д. Описание алгоритма удобно провести в теоретико-графовой постановке, а затем пояснить особенности программной реализации. Пусть задан ролевой граф с одним источником 𝐺. 𝑅𝑃 -эквивалентное ему ролевое дерево 𝑇 формируется последовательно. 1. На каждом шаге строится ориентированный ациклический граф 𝑇 𝑖 . На начальном этапе граф 𝑇 0 пуст. Число шагов алгоритма равно порядку 𝑛 графа 𝐺, то есть 𝑇 𝑛 = 𝑇 . В процессе построения дерева в определенной последовательности обходятся все вершины орграфа 𝐺 и на каждом шаге 𝑖 (𝑖 = 1, . . . , 𝑛) граф 𝑇 𝑖 пополняется вершинами и дугами. 2. В начале просматриваются стоки графа 𝐺. Каждому стоку 𝑟𝑡𝑗 сопоставляется 𝑑+ (𝑟𝑡𝑗 ) листьев в 𝑇 : вершина-оригинал и (𝑑+ (𝑟𝑡𝑗 ) − 1) вершин-ярлыков. Оригиналу и ярлыкам приписывается метка вер- ∑︀𝑙 шины 𝑟𝑡𝑗 . После просмотра всех 𝑙 стоков 𝑟𝑡1 , . . . , 𝑟𝑡𝑙 графа 𝐺, граф 𝑇 𝑙 представляет собой 𝑗=1 𝑑+ (𝑟𝑡𝑗 ) изолированных вершин. 3. Далее обход вершин графа 𝐺 осуществляется в порядке возрастания длины самого протяженного из путей от текущей вершины до стоков 𝑟𝑡1 , . . . , 𝑟𝑡𝑙 . Пусть 𝑟𝑖 – очередная вершина графа 𝐺 с меткой 𝑟𝑖 .𝑝, просматриваемая на 𝑖-том шаге алгоритма, и 𝑑+ (𝑟𝑖 ) = 𝑘𝑖 . В графе 𝑇 𝑖 ей сопоставляется 𝑘𝑖 вершин: вершина-оригинал 𝑜1𝑖 и (𝑘𝑖 − 1) ярлыков 𝑜2𝑖 , . . . , 𝑜𝑘𝑖 𝑖 . Вершинам 𝑜1𝑖 , . . . , 𝑜𝑘𝑖 𝑖 приписывается метка 𝑟𝑖 .𝑝. 4. Вершина-оригинал 𝑜1𝑖 соединяется дугами с уже существующими вершинами графа 𝑇 𝑖 по правилу: дуга (𝑜1𝑖 , 𝑜𝑗𝑠 ) присоединяется к графу 𝑇 𝑖 тогда и только тогда, когда 𝑑+ (𝑜𝑗𝑠 ) = 0 и вершине 𝑜𝑗𝑠 соответ- ствует такая вершина 𝑟𝑠 в графе 𝐺, что в 𝐺 существует дуга (𝑟𝑖 , 𝑟𝑠 ). Другими словами среди вершин графа 𝑇 𝑖 выбираются вершины, соответствующие непосредственным потомкам вершины 𝑟𝑖 в графе 𝐺, которые и становятся сыновьями вершины 𝑜1𝑖 . 5. Для каждого ярлыка 𝑜2𝑖 , . . . , 𝑜𝑘𝑖 𝑖 добавляются новые вершины-ярлыки и дуги так, чтобы подграф 𝑇𝑜𝑗 𝑖 (𝑗 = 2, . . . , 𝑘𝑖 ), порожденный ярлыком 𝑜𝑗𝑖 и всеми его потомками, представлял собой копию поддерева 𝑇𝑜1𝑖 , порожденного вершиной-оригиналом 𝑜1𝑖 и всеми ее потомками; метки вершин заменены порядко- выми номерами, в графе 𝑇 вершины-оригиналы закрашены, вершины-ярлыки – нет). Обход графа 𝐺 следует вести в порядке, определяемом вектором 𝑄: индекс очередного элемента вектора 𝑆 лежит в 𝑄[𝑖].𝑟 (𝑖 = 1, . . . , 𝑛). Для удобства далее очередной индекс будем обозначать 𝑖. Дерево 𝑇 также представляется вектором списков смежности 𝑆𝑇 . Но набор полей элементов вектора 𝑆𝑇 следует расширить. Каждый 𝑗 -й элемент вектора 𝑆𝑇 должен содержать: 1) 𝑆𝑇 [𝑗].𝑙𝑖𝑠𝑡 – целочисленный список номеров тех вершин, в которые ведут дуги из 𝑗 -й вершины (список смежности); 2) 𝑆𝑇 [𝑗].𝑝 – метка вершины – 𝑚-мерный битовый вектор. 3) 𝑆𝑇 [𝑗].𝑖𝑛𝑑 – индекс вершины исходного графа 𝐺, которой была сопоставлена данная вершина в графе 𝑇; 4) 𝑆𝑇 [𝑗].𝑑 – полустепень захода вершины. Кроме того, вектор 𝑆𝑇 должен динамически наращивать размерность, так как заранее число вершин дерева 𝑇 не известно. Изначально вектор 𝑆𝑇 пуст. Процесс сопоставления вершине 𝑟𝑖 графа 𝐺 вершины- оригинала и ярлыков в графе 𝑇 будет заключаться в следующем. Для построения вершины-оригинала 𝑜1𝑖 в вектор 𝑆𝑇 добавляется очередной элемент 𝑗 : 𝑆𝑇 [𝑗].𝑝 := 𝑆[𝑖].𝑝, 𝑆𝑇 [𝑗].𝑖𝑛𝑑 := 𝑖, 𝑆𝑇 [𝑗].𝑑 := 0, 𝑆𝑇 [𝑗].𝑙𝑖𝑠𝑡 := 0 Чтобы построить исходящие из вершины-оригинала дуги, необходимо для каждого элемента 𝑘 списка смежности 𝑆[𝑖].𝑙𝑖𝑠𝑡 пройти по вектору 𝑆𝑇 , чтобы найти индекс 𝑙 такой, что 𝑆𝑇 [𝑙].𝑖𝑛𝑑 = 𝑘 и 𝑆𝑇 [𝑙].𝑑 = 0. Найденный индекс 𝑙 надо добавить в список смежности 𝑆𝑇 [𝑗].𝑙𝑖𝑠𝑡, а также 𝑆𝑇 [𝑙].𝑑 := 0. Для построения поддеревьев с корневыми вершинами-ярлыками формируется 𝐷[𝑖] − 1 новых векторов списков смежности 𝑆𝑇2 , . . . , 𝑆𝑇𝐷[𝑖] , подобных вектору 𝑆𝑇 . Далее можно реализовать обход «в ширину» всех вершин, достижимых из вершины 𝑆𝑇 [𝑗], и сформировать векторы 𝑆𝑇2 , . . . , 𝑆𝑇𝐷[𝑖] как копии элементов, пройденных в векторе 𝑆𝑇 . Заполненные векторы 𝑆𝑇2 , . . . , 𝑆𝑇𝐷[𝑖] присоединяются к вектору 𝑆𝑇 с учетом перенумерации новых вершин. Более детальное описание алгоритма зависит от выбранного языка программирования и от способа реализации динамических структур данных. Утверждение 4. Трудоемкость алгоритм оптимизации ролевого графа по критерию «древовидный РГ» полиномиально зависит от числа вершин и числа полномочий. Доказательство. Обоснованием является следствие 4.2.  2.6.4 Алгоритм оптимизации ролевого графа по критерию «транзитивно-сокращенный РГ» Для реализации этого алгоритма используется матричное представление ролевого графа. Известно, что транзитивное сокращение ℛ− отношения порядка ℛ можно найти, используя его транзитивное замыкание ℛ+ и операции разности «−» и композиции «∘» отношений: ℛ− = ℛ − (ℛ ∘ ℛ+ ). Переходя от отношений порядка к ориентированным графам, получаем, что матрица смежности 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: Алгоритмы локальной оптимизации Критерий Оптимальный ролевой граф Сохраняется 1 Листовой Древовидность 2 𝑅𝑃 -сокращенный Листовое распределение полномочий 3 Древовидный Листовое распределение полномочий 4 Транзитивно-сокращенный Вся иерархия 1+2 Листовой + 𝑅𝑃 -сокращенный 3+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. [3] A. V. Aho, J. E. Hopcroft, J. D. Ullman. Data Structures and Algorithms. Addison-Wesley, 1987. [4] URL: http://www.intuit.ru/studies/courses/12181/1174/lecture/25264 [5] S. Belim, N. Bogachenko, E. Ilushechkin. An Analysis of Graphs that Represent a Role-Based Security Policy Hierarchy Journal of Computer Security, 23(5):641–657, 2015. URL: http://content.iospress. com/articles/journal-of-computer-security/jcs532. [6] S. V. Belim, N. F. Bogachenko Distribution of Cryptographic Keys in Systems with a Hierarchy of Objects. Automatic Control and Computer Sciences, 50(8):777–786, 2016. URL: http://link.springer. com/article/10.3103/S0146411616080071. Local Optimization of the Role-Based Access Control Policy Nadezda F. Bogachenko Modifications of the role hierarchy in the role-based access control policy are described in this paper. The role- graph conversion algorithms wich use different optimality criterions are constructed and proved. The principles of the permission distribution, the absence of the roles-counterparts and the role-graph acyclicity are considered as the optimality criterions. A possibility to obtain the several role-graphs wich correspond to the equivalent role-based access control models is prooved.