=Paper=
{{Paper
|id=Vol-1732/paper4
|storemode=property
|title=
Отношение взаимоисключения
на множестве ролей в моделях
управления доступом
(The Mutual Exclusion Relation on a Set of Roles in Access Control Models)
|pdfUrl=https://ceur-ws.org/Vol-1732/paper4.pdf
|volume=Vol-1732
|authors=Nadezda Bogachenko
}}
==
Отношение взаимоисключения
на множестве ролей в моделях
управления доступом
(The Mutual Exclusion Relation on a Set of Roles in Access Control Models)
==
https://ceur-ws.org/Vol-1732/paper4.pdf
Îòíîøåíèå âçàèìîèñêëþ÷åíèÿ íà ìíîæåñòâå ðîëåé
â ìîäåëÿõ óïðàâëåíèÿ äîñòóïîì
Í.Ô. Áîãà÷åíêî
nfbogachenko@mail.ru
Îìñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò èì. Ô.Ì. Äîñòîåâñêîãî, Îìñê, Ðîññèÿ
Àííîòàöèÿ
 äàííîé ðàáîòå ïîäðîáíî ðàññìîòðåíî íàèáîëåå ðàñïðîñòðàíåííîå
îãðàíè÷åíèå ìîäåëè RBAC2 ¾âçàèìîèñêëþ÷àþùèå ðîëè¿. Ýòî
îãðàíè÷åíèå èíòåðïðåòèðîâàíî â òåðìèíàõ áèíàðíûõ îòíîøåíèé.
Èññëåäîâàíû ñâîéñòâà ïîñòðîåííîãî îòíîøåíèÿ.  ÷àñòíîñòè, ðàñ-
ñìîòðåíû âàðèàíòû òðàíçèòèâíîãî è íåòðàíçèòèâíîãî îòíîøåíèé.
 êà÷åñòâå ÿçûêà îïèñàíèÿ îãðàíè÷åíèÿ ¾âçàèìîèñêëþ÷àþùèå ðî-
ëè¿ ïðåäëîæåíî èñïîëüçîâàòü XML-ïîäîáíûé ÿçûê GraphML.
Ââåäåíèå
Îñíîâíûå ýëåìåíòû ìàòåìàòè÷åñêîé ìîäåëè ðîëåâîãî óïðàâëåíèÿ äîñòóïîì (Role Base Access Control,
RBAC) èçëîæåíû â ðàáîòàõ [1, 2, 4, 5]. Ïðèíÿòî ãîâîðèòü î ñåìåéñòâå ðîëåâûõ ìîäåëåé. Ìîäåëü RBAC0
áàçîâàÿ ìîäåëü, ïðåäúÿâëÿþùàÿ ìèíèìóì òðåáîâàíèé ê ñèñòåìå, êîòîðàÿ ìîæåò ïîääåðæèâàòü ðîëåâîå
ðàçãðàíè÷åíèå äîñòóïà. RBAC1 âêëþ÷àåò òðåáîâàíèÿ ìîäåëè RBAC0 è êîíöåïöèþ èåðàðõèè ðîëåé. RBAC2
ñîäåðæèò òðåáîâàíèÿ ìîäåëè RBAC0 è îãðàíè÷åíèÿ, íàëàãàåìûå íà ðàçëè÷íûå êîìïîíåíòû ìîäåëè. Íà-
ïðèìåð, âçàèìîèñêëþ÷àþùèå ðîëè, êîëè÷åñòâåííûå îãðàíè÷åíèÿ ïî ðîëÿì, êîíöåïöèÿ óñëîâíûõ ðîëåé è
ò.ä. RBAC3 îáúåäèíÿþùàÿ ìîäåëü, âêëþ÷àåò òðåáîâàíèÿ ìîäåëåé RBAC1 è RBAC2 è, ïî òðàíçèòèâíî-
ñòè, ìîäåëè RBAC0 . Êðîìå îáû÷íûõ ðîëåé â ñèñòåìó ìîãóò áûòü ââåäåíû àäìèíèñòðàòèâíûå ðîëè, ÷òî
ïðèâîäèò ê âîçìîæíîñòè îïèñàíèÿ ñèñòåì ñ èçìåíÿåìîé çàùèòîé [3].
 äàííîé ðàáîòå ïîäðîáíî ðàññìàòðèâàåòñÿ íàèáîëåå ðàñïðîñòðàíåííîå îãðàíè÷åíèå ìîäåëè RBAC2
¾âçàèìîèñêëþ÷àþùèå ðîëè¿. Íàïðèìåð â ñîâðåìåííûõ ñèñòåìàõ óïðàâëåíèÿ ðåñóðñàìè ïðåäïðèÿòèÿ
(Enterprise Resource Planning Systems, ERP-ñèñòåìàõ) ïîíÿòèå âçàèìîèñêëþ÷àþùèõ ðîëåé ââåäåíî â ðàì-
êàõ RBAC-ìîäåëè óïðàâëåíèÿ äîñòóïîì äëÿ ðåàëèçàöèè êîíöåïöèè ðàçäåëåíèÿ ïîëíîìî÷èé.
1 Áèíàðíûå îòíîøåíèÿ ìîäåëè RBAC2
Îðãàíèçàöèÿ ðîëåâîé ñèñòåìû óïðàâëåíèÿ äîñòóïîì ñîñòîèò èç äâóõ ýòàïîâ:
1. Âûäåëåíèå ìíîæåñòâà ðîëåé è îïðåäåëåíèå èõ ïîëíîìî÷èé.
2. Íàçíà÷åíèå ðîëåé ïîëüçîâàòåëÿì ñèñòåìû.
Äëÿ ôîðìàëüíîãî îïèñàíèÿ ìîäåëè RBAC0 íåîáõîäèìî îïðåäåëèòü ñëåäóþùèå ìíîæåñòâà è îòîáðàæåíèÿ:
• Ìíîæåñòâî ðîëåé R, ìíîæåñòâî ïîëíîìî÷èé P , ìíîæåñòâî ïîëüçîâàòåëåé U .
Copyright c by the paper's authors. Copying permitted for private and academic purposes.
In: Sergey V. Belim, Nadezda F. Bogachenko (eds.): Proceedings of the Workshop on Data Analysis and Modelling (DAM 2016),
Omsk, Russia, October 2016, published at http://ceur-ws.org
• Îòîáðàæåíèå RP : R −→ 2P , êîòîðîå êàæäîé ðîëè r ñîïîñòàâëÿåò ìíîæåñòâî ïîëíîìî÷èé r.p ⊆ P .
• Îòîáðàæåíèå U R : U −→ 2R , êîòîðîå êàæäîìó ïîëüçîâàòåëþ u ñîïîñòàâëÿåò ìíîæåñòâî ðîëåé u.r ⊆ R,
íà ýòè ðîëè ïîëüçîâàòåëü ìîæåò áûòü àâòîðèçîâàí.
Íåòðóäíî çàìåòèòü, ÷òî îòîáðàæåíèÿ RP è U R ñîîòâåòñòâóþò ïåðâîìó è âòîðîìó ýòàïàì ïîñòðîåíèÿ
ìîäåëè RBAC0 .
Óïðàâëåíèå äîñòóïîì îñóùåñòâëÿåòñÿ ïðè ïîìîùè îòîáðàæåíèÿ Fsession roles : U −→ 2R , êîòîðîå ïîëü-
çîâàòåëþ u ñîïîñòàâëÿåò ïîäìíîæåñòâî ðîëåé u.sr ⊆ u.r ⊆ R, íà ýòè ðîëè ïîëüçîâàòåëü ìîæåò áûòü
àâòîðèçîâàí â òåêóùåì ñåàíñå ðàáîòû ñ ñèñòåìîé.
 ðàìêàõ ìîäåëè RBAC2 îãðàíè÷åíèå ¾âçàèìîèñêëþ÷àþùèå ðîëè¿ êàê ïðàâèëî ïðåäñòàâëÿåò ñîáîé
çàäàíèå ñïåöèàëüíîãî îòîáðàæåíèÿ Fmutually exclusive : R −→ 2R , êîòîðîå êàæäîé ðîëè r ñîïîñòàâëÿåò ïîä-
ìíîæåñòâî ¾íåñîâìåñòíûõ¿ ñ íåé ðîëåé r.mer ⊆ R [1]. Ðàçëè÷àþò ñòàòè÷åñêèé è äèíàìè÷åñêèé ìåòîäû
ðàñïðåäåëåíèÿ îáÿçàííîñòåé.  ïåðâîì ñëó÷àå îòîáðàæåíèå Fmutually exclusive íàêëàäûâàåò îãðàíè÷åíèÿ íà
îòîáðàæåíèå U R:
(r ∈ u.r) ∧ (r0 ∈ r.mer) =⇒ (r0 ∈/ u.r), (1)
âî âòîðîì íà îòîáðàæåíèÿ Fsession roles :
(r ∈ u.sr) ∧ (r0 ∈ r.mer) =⇒ (r0 ∈
/ u.sr). (2)
Äðóãèìè ñëîâàìè, ïîëüçîâàòåëü u, àâòîðèçîâàííûé íà ðîëü r, íå ìîæåò áûòü îäíîâðåìåííî àâòîðèçîâàí
íà ¾íåñîâìåñòíóþ¿ ñ íåé ðîëü r0 íè íà ýòàïå îðãàíèçàöèè ðîëåâîé ìîäåëè (îãðàíè÷åíèå (1)), íè â ïðîöåññå
óïðàâëåíèÿ äîñòóïîì (îãðàíè÷åíèå (2)).
 äàëüíåéøåì áóäåì ðàññìàòðèâàòü äèíàìè÷åñêèé ìåòîä. Òåì íå ìåíåå ïîñëåäóþùèå ðàññóæäåíèÿ î÷å-
âèäíûì îáðàçîì ïåðåíîñÿòñÿ è íà ñòàòè÷åñêèé ñëó÷àé. Îãðàíè÷åíèå (2) ìîæíî èíòåðïðåòèðîâàòü â òåð-
ìèíàõ áèíàðíûõ îòíîøåíèé: ïóñòü íà ìíîæåñòâå ðîëåé R çàäàíî áèíàðíîå îòíîøåíèå âçàèìîèñêëþ÷åíèÿ
¾=¿:
r = r0 ⇐⇒ (r ∈ u.sr) ∧ (r0 ∈
/ u.sr).
Î÷åâèäíî, ÷òî ýòî îòíîøåíèå îáëàäàåò ñëåäóþùèìè ñâîéñòâàìè:
• Àíòèðåôëåêñèâíîñòü: ∀r ∈ R : ¬(r = r), òàê êàê ¬((r ∈ u.sr) ∧ (r ∈
/ u.sr)).
• Ñèììåòðè÷íîñòü: ∀r, r0 ∈ R : (r = r0 ) =⇒ (r0 = r), â ñèëó êîììóòàòèâíîñòè êîíúþíêöèè.
Åñëè ñ÷èòàòü, ÷òî àâòîðèçàöèÿ ïîëüçîâàòåëÿ îñóùåñòâëÿåòñÿ ïî ïðèíöèïó ¾âñå, ÷òî íå çàïðåùåíî ðàçðå-
øåíî¿, òî äîïîëíåíèåì ê îòíîøåíèþ âçàèìîèñêëþ÷åíèÿ áóäåò ÿâëÿòüñÿ îòíîøåíèå ñîâìåñòèìîñòè ¾↔¿:
r ↔ r0 ⇐⇒ (r ∈ u.sr) ∧ (r0 ∈ u.sr).
Äåéñòâèòåëüíî, íåñëîæíî ïîíÿòü, ÷òî ¬(r = r0 ) ⇐⇒ (r ↔ r0 ). Ñâîéñòâà, êîòîðûìè î÷åâèäíûì îáðàçîì
îáëàäàåò îòíîøåíèå ñîâìåñòèìîñòè:
• Ðåôëåêñèâíîñòü: ∀r ∈ R : (r ↔ r).
• Ñèììåòðè÷íîñòü: ∀r, r0 ∈ R : (r ↔ r0 ) =⇒ (r0 ↔ r).
Òàêèì îáðàçîì äîñòàòî÷íî çàäàòü îäíî èç îòíîøåíèé: ñîâìåñòèìîñòü èëè âçàèìîèñêëþ÷åíèå, òîãäà âòîðîå
îòíîøåíèå ñòðîèòñÿ êàê äîïîëíåíèå çàäàííîãî äî óíèâåðñóìà äåêàðòîâà ïðîèçâåäåíèÿ R × R.
Òàê êàê ìíîæåñòâî ðîëåé êîíå÷íî, òî äëÿ çàäàíèÿ áèíàðíûõ îòíîøåíèé ìîæíî èñïîëüçîâàòü ãðàôîâîå
ïðåäñòàâëåíèå. Îòíîøåíèþ R ñîïîñòàâëÿåòñÿ îðèåíòèðîâàííûé ãðàô G = G(V, E), â êîòîðîì ìíîæå-
ñòâî âåðøèí V ñîâïàäàåò ñ ìíîæåñòâîì ðîëåé R, à ìíîæåñòâî äóã E îïðåäåëÿåòñÿ ñëåäóþùèì ïðàâèëîì:
(u, v) ∈ E ⇐⇒ uRv . Òàêîé ãðàô äîïóñêàåò íàëè÷èå ïåòåëü. Åñëè îòíîøåíèå R ÿâëÿåòñÿ ñèììåòðè÷íûì,
òî îðèåíòèðîâàííûé ãðàô ìîæíî çàìåíèòü íåîðèåíòèðîâàííûì.
Ãðàô îòíîøåíèÿ âçàèìîèñêëþ÷åíèÿ îáîçíà÷èì G= . Íåñëîæíî ïîíÿòü, ÷òî îòîáðàæåíèå Fsession roles
ñâÿçàíî ñ ãðàôîì G= ïðàâèëîì: ïîëüçîâàòåëü u íå ìîæåò áûòü àâòîðèçîâàí íà ñìåæíûå âåðøèíû-ðîëè â
îäíîì ñåàíñå ðàáîòû â ñèñòåìå.
Íà ýòîì ýòàïå âîçíèêàåò çàäà÷à ïîèñêà ïîäìíîæåñòâà ðîëåé, íà êîòîðûå îäíîâðåìåííî ìîæåò áûòü
àâòîðèçîâàí ïîëüçîâàòåëü u. Ñ òî÷êè çðåíèÿ òåîðåòèêî-ãðàôîâîé ìîäåëè íåîáõîäèìî íàéòè íåçàâèñèìîå
ìíîæåñòâî âåðøèí (ìíîæåñòâî, â êîòîðîì íèêàêèå äâå âåðøèíû íå ñìåæíû) ïðàâèëüíîãî ïîäãðàôà ãðàôà
G= , ïîðîæäåííîãî ìíîæåñòâîì âåðøèí u.sr. Òî÷íûé àëãîðèòì ïîèñêà âñåõ íåçàâèñèìûõ ìíîæåñòâ âåðøèí
ïðåäñòàâëÿåò ñîáîé ïîëíûé ïåðåáîð ýëåìåíòîâ áóëåàíà ìíîæåñòâà u.sr è èìååò òðóäîåìêîñòü O(n2 · 2n ).
×àùå çàäà÷à ôîðìóëèðóåòñÿ â îïòèìèçàöèîííîé ïîñòàíîâêå: òðåáóåòñÿ íàéòè ìàêñèìàëüíîå íåçàâèñèìîå
ìíîæåñòâî âåðøèí. Òðóäîåìêîñòü òî÷íîãî àëãîðèòìà îñòàåòñÿ ïðåæíåé, òàê êàê è â ýòîì ñëó÷àå òðåáóåòñÿ
îðãàíèçîâàòü ïîëíûé ïåðåáîð. Åñëè æå âîçìîæíî ïðèìåíåíèå ïðèáëèæåííîãî àëãîðèòìà, òî èñïîëüçóåòñÿ
¾æàäíàÿ¿ ñòðàòåãèÿ: íà êàæäîì øàãå âûáèðàåòñÿ âåðøèíà ñ ìèíèìàëüíîé ñòåïåíüþ è óäàëÿþòñÿ ñìåæíûå
ñ íåé âåðøèíû. Èçâåñòíî, ÷òî ýòà ýâðèñòèêà èìååò òðóäîåìêîñòü O(n) ïðè óñëîâèè, ÷òî ãðàô íà âõîä
ïîäàåòñÿ â âèäå ñïèñêà ñìåæíîñòè è âåðøèíû óïîðÿäî÷åíû ïî íåóáûâàíèþ ñòåïåíåé.
2 Ñâîéñòâî òðàíçèòèâíîñòè îòíîøåíèÿ âçàèìîèñêëþ÷åíèÿ
Îäíèì èç ïðèíöèïèàëüíûõ âîïðîñîâ, êîòîðûå ñëåäóåò îáñóäèòü ïðè ïîñòðîåíèè îòíîøåíèÿ âçàèìîèñêëþ-
÷åíèÿ ýòî ñâîéñòâî òðàíçèòèâíîñòè. Ðàññìîòðèì ñíà÷àëà òðàäèöèîííûé ïîäõîä, ïðè êîòîðîì îòíîøåíèå
âçàèìîèñêëþ÷åíèÿ ñ÷èòàåòñÿ òðàíçèòèâíûì: ∀r1 , r2 , r3 ∈ R : (r1 = r2 ) ∧ (r2 = r3 ) =⇒ (r1 = r3 ). Åñëè
èñêóññòâåííî èçìåíèòü ñâîéñòâî àíòèðåôëåêñèâíîñòè îòíîøåíèÿ âçàèìîèñêëþ÷åíèÿ íà ðåôëåêñèâíîñòü
(÷òî ïðèíöèïèàëüíî íå ñêàæåòñÿ íà ðåøàåìîé çàäà÷å àâòîðèçàöèè ïîëüçîâàòåëÿ), òîãäà îòíîøåíèå âçàè-
ìîèñêëþ÷åíèÿ áóäåò îòíîøåíèåì ýêâèâàëåíòíîñòè íà ìíîæåñòâå ðîëåé.  êàæäûé êëàññ ýêâèâàëåíòíîñòè
ïîïàäóò ðîëè ïîïàðíî íåñîâìåñòíûå, à ãðàô G= áóäåò îáëàäàòü ñëåäóþùèì ñâîéñòâîì: êàæäàÿ åãî êîì-
ïîíåíòà ñâÿçíîñòè ïîëíûé ïîäãðàô. Âîçâðàùåíèå ê òðåáîâàíèþ àíòèðåôëåêñèâíîñòè ïðèâåäåò ê òîìó,
÷òî â ãðàôå G= èñ÷åçíóò ïåòëè.
Óäîáíûì ñïîñîáîì ïðåäñòàâëåíèÿ áèíàðíîãî îòíîøåíèÿ íà êîíå÷íîì ìíîæåñòâå ÿâëÿåòñÿ ìàòðè÷íàÿ
ôîðìà. Ïóñòü |R| = n. Òîãäà ìàòðèöà M= îòíîøåíèÿ âçàèìîèñêëþ÷åíèÿ èìååò ðàçìåðíîñòü n × n è
îïðåäåëÿåòñÿ ïî ïðàâèëó:
1, åñëè ri = rj ,
=
[M ]ij =
0, èíà÷å.
Íåñëîæíî çàìåòèòü, ÷òî ìàòðèöà áèíàðíîãî îòíîøåíèÿ åñòü ìàòðèöà ñìåæíîñòè åãî ãðàôîâîãî ïðåäñòàâ-
ëåíèÿ.
Óòâåðæäåíèå 1. Òðóäîåìêîñòü àëãîðèòìà ïðîâåðêè òîãî ôàêòà, ÷òî íåîðèåíòèðîâàííûé ãðàô ïîðÿäêà
n ÿâëÿåòñÿ ãðàôîì íåêîòîðîãî òðàíçèòèâíîãî îòíîøåíèÿ âçàèìîèñêëþ÷åíèÿ, íå ïðåâîñõîäèò O(n3 ).
Äîêàçàòåëüñòâî. Ïóñòü íåîðèåíòèðîâàííûé ãðàô G çàäàí ìàòðèöåé ñìåæíîñòè M ðàçìåðíîñòè n × n.
Íåîáõîäèìî ïðîâåðèòü, ÿâëÿåòñÿ ëè îòíîøåíèå R, ïîðîæäàåìîå ðåáðàìè ãðàôà G, àíòèðåôëåêñèâíûì,
ñèììåòðè÷íûì è òðàíçèòèâíûì. Îòíîøåíèå R áóäåò àíòèðåôëåêñèâíûì, åñëè íà ãëàâíîé äèàãîíàëè ìàò-
ðèöû ñìåæíîñòè ñòîÿò íóëè. Òðóäîåìêîñòü ïðîâåðêè ýòîãî ôàêòà ðàâíà O(n). Ñèììåòðè÷íîñòü îòíîøåíèÿ
R ñëåäóåò èç ñèììåòðè÷íîñòè ìàòðèöû ñìåæíîñòè íåîðèåíòèðîâàííîãî ãðàôà. ×òîáû ïðîâåðèòü òðàíçè-
òèâíîñòü îòíîøåíèÿ R íåîáõîäèìî ïîñòðîèòü ìàòðèöó M∗ = M◦M, ãäå ïîä îïåðàöèåé ¾◦¿ ïîäðàçóìåâàåòñÿ
òàêîå ïðîèçâåäåíèå ìàòðèö, ïðè êîòîðîì óìíîæåíèå ýëåìåíòîâ ñîîòâåòñòâóåò ëîãè÷åñêîé îïåðàöèè êîíú-
þíêöèÿ, à ñëîæåíèå ýëåìåíòîâ ëîãè÷åñêîé îïåðàöèè äèçúþíêöèÿ. Îòíîøåíèå R ÿâëÿåòñÿ òðàíçèòèâíûì,
åñëè [M∗ ]ij 6 [M]ij (i, j ∈ {1, ..., n}). Òàêèì îáðàçîì òðóäîåìêîñòü ïðîâåðêè òðàíçèòèâíîñòè îïðåäåëÿåò-
ñÿ òðóäîåìêîñòüþ àëãîðèòìà ïðîèçâåäåíèÿ äâóõ ìàòðèö è íå ïðåâîñõîäèò O(n3 ). Â èòîãå òðóäîåìêîñòü
àëãîðèòìà àíàëèçà ãðàôà G òàêæå íå ïðåâîñõîäèò O(n3 ).
Îäíîé èç îáúåêòèâíûõ ïðè÷èí ïîñòðîåíèÿ îòíîøåíèÿ âçàèìîèñêëþ÷åíèÿ ÿâëÿåòñÿ âîçìîæíîñòü ïîëó-
÷åíèÿ ïîëüçîâàòåëåì íåäîïóñòèìîãî, ñ òî÷êè çðåíèÿ áåçîïàñíîñòè ñèñòåìû, íàáîðà ðîëåé èëè ïîëíîìî÷èé.
 ÷àñòíîñòè, íåëüçÿ â îäíîì ñåàíñå ðàáîòû ñ ñèñòåìîé ñîâìåùàòü ðîëè àäìèíèñòðàòîðà è àóäèòîðà áåç-
îïàñíîñòè, íåëüçÿ çàíèìàòü ñðàçó äâå äîëæíîñòè ïî îñíîâíîìó ìåñòó ðàáîòû, íåëüçÿ îäíîâðåìåííî ðàç-
ðåøàòü äîñòóï ê öåííîé èíôîðìàöèè è çàïóñê íåäîâåðåííûõ ïðîöåññîâ, íåëüçÿ â ôèíàíñîâûõ ïðîöåäóðàõ
ñîâìåùàòü ðîëè êîíòðîëåðà-àóäèòîðà è êàññèðà-îïåðàòîðà è ò. ä. Äëÿ äàëüíåéøåãî àíàëèçà îòíîøåíèÿ
âçàèìîèñêëþ÷åíèÿ ðàññìîòðèì íåñêîëüêî ïðèìåðîâ.
Ïðèìåð 1. Ïóñòü ìåæäó ðîëÿìè r1 , r2 è r3 ïîëíîìî÷èÿ ðàñïðåäåëåíû ñëåäóþùèì îáðàçîì: r1 .p = {p1 , p2 },
r2 .p = {p3 , p4 } è r3 .p = {p1 , p3 , p4 }. È ïóñòü íàáîð ïîëíîìî÷èé {p1 , p2 , p3 , p4 } ñ÷èòàåòñÿ íåäîïóñòèìûì ñ
ïîçèöèé áåçîïàñíîñòè ñèñòåìû. Ðàññìîòðèì ïîëüçîâàòåëÿ u, êîòîðûé ìîæåò áûòü àâòîðèçîâàí íà ðîëè
èç íàáîðà u.r = {r1 , r2 , r3 }. Òîãäà â îäíîì ñåàíñå ðàáîòû ñ ñèñòåìîé ïîëüçîâàòåëÿ u íåëüçÿ îäíîâðåìåííî
àâòîðèçîâàòü íà ðîëè r1 è r2 , à òàêæå íà ðîëè r1 è r3 , íî èìååòñÿ âîçìîæíîñòü îäíîâðåìåííîé àâòîðèçàöèè
íà ðîëè r2 è r3 . Âûïèøåì âñå ïàðû ðîëåé, ñâÿçàííûõ îòíîøåíèåì âçàèìîèñêëþ÷åíèÿ ¾=¿, ó÷èòûâàÿ åãî
ñèììåòðè÷íîñòü è àíòèðåôëåêñèâíîñòü: {(r1 , r2 ), (r2 , r1 ), (r1 , r3 ), (r3 , r1 )}. Î÷åâèäíî, ÷òî ýòî îòíîøåíèå íå
ÿâëÿåòñÿ òðàíçèòèâíûì, òàê êàê â ïðåäñòàâëåííîì ìíîæåñòâå ïðèñóòñòâóþò, íàïðèìåð, ïàðû (r3 , r1 ) è
(r1 , r2 ), íî íåò ïàðû (r3 , r2 ).
Ïðèìåð 2. Íà ðèñóíêå 1 ïðåäñòàâëåíû ñòàíäàðòíûå ðîëè ñëóæáû Reporting Services òåõíîëîãèè
SQL Server äëÿ ïðåäîñòàâëåíèÿ äîñòóïà ê îïåðàöèÿì ñåðâåðà îò÷åòîâ [6]. Ñ êàæäîé ñòàíäàðòíîé ðîëüþ
ñâÿçàí íàáîð çàäà÷ (ïîëíîìî÷èé). Äëÿ îáåñïå÷åíèÿ âñåõ ñîñòàâëÿþùèõ èíôîðìàöèîííîé áåçîïàñíîñòè
ïîëüçîâàòåëü íå ìîæåò áûòü îäíîâðåìåííî àâòîðèçîâàí íà ðîëè èç ìíîæåñòâà {r1 , r2 , r3 , r4 , r5 } è ðîëè èç
ìíîæåñòâà {r6 , r7 }. Òîãäà îòíîøåíèå âçàèìîèñêëþ÷åíèÿ ¾=¿ çàäàåòñÿ ìàòðèöåé M= :
0 0 0 0 0 1 1
0 0 0 0 0 1 1
0 0 0 0 0 1 1
(3)
=
M = 0 0 0 0 0 1 1
0 0 0 0 0 1 1
1 1 1 1 1 0 0
1 1 1 1 1 0 0
 ñèëó òîãî, ÷òî [M= ◦ M= ]11 = 1 > 0 = [M= ]11 , ïîñòðîåííîå îòíîøåíèå âçàèìîèñêëþ÷åíèÿ íå ÿâëÿåòñÿ
òðàíçèòèâíûì.
Ðèñ. 1: Ñòàíäàðòíûå ðîëè è ïîëíîìî÷èÿ ñëóæáû Reporting Services; r1 äèñïåò÷åð ñîäåðæèìîãî, r2
èçäàòåëü, r3 áðàóçåð, r4 ïîñòðîèòåëü îò÷åòîâ, r5 ìîè îò÷åòû, r6 ñèñòåìíûé àäìèíèñòðàòîð, r7
ïîëüçîâàòåëü ñèñòåìû.
Èñõîäÿ èç âûøåñêàçàííîãî ñëåäóåò îòêàçàòüñÿ îò îáÿçàòåëüíîé òðàíçèòèâíîñòè îòíîøåíèÿ âçàèìîèñ-
êëþ÷åíèÿ.  ýòîì ñëó÷àå èçìåíÿòñÿ è ñâîéñòâà ãðàôà G= : èñ÷åçíåò òðåáîâàíèå ïîëíîòû êîìïîíåíò ñâÿç-
íîñòè. Òðóäîåìêîñòü, îáîçíà÷åííàÿ â óòâåðæäåíèè 1, îïðåäåëÿåòñÿ àëãîðèòìîì ïðîèçâåäåíèÿ äâóõ ìàò-
ðèö. Åñëè ïðîâåðêà òðàíçèòèâíîñòè íå òðåáóåòñÿ, òî òðóäîåìêîñòü àíàëèçà ãðàôà ñòàíîâèòñÿ ëèíåéíîé.
Àíòèðåôëåêñèâíîñòü îòíîøåíèÿ âçàèìîèñêëþ÷åíèÿ îáåñïå÷èâàåòñÿ îòñóòñòâèåì ïåòåëü â ãðàôå. Ïîýòîìó
ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå.
Óòâåðæäåíèå 2. Ëþáîé ïðîñòîé íåîðèåíòèðîâàííûé ãðàô ïîðîæäàåò â îáùåì ñëó÷àå íåòðàíçèòèâíîå
îòíîøåíèå âçàèìîèñêëþ÷åíèÿ.
3 Ïðåäñòàâëåíèå ãðàôà îòíîøåíèÿ âçàèìîèñêëþ÷åíèÿ
Ïðè ïðîãðàììíî-òåõíè÷åñêîé ðåàëèçàöèè îãðàíè÷åíèé ìîäåëè RBAC2 âîçíèêàåò ïîäçàäà÷à ôîðìàëüíîãî
îïèñàíèÿ îòíîøåíèÿ âçàèìîèñêëþ÷åíèÿ. Êàê îòìå÷àëîñü ðàíåå, ìàòðèöà îòíîøåíèÿ âçàèìîèñêëþ÷åíèÿ
ïðåäñòàâëÿåò ñîáîé ìàòðèöó ñìåæíîñòè íåêîòîðîãî ïðîñòîãî íåîðèåíòèðîâàííîãî ãðàôà. Ïîýòîìó âîç-
ìîæíî ìàòðè÷íîå ïðåäñòàâëåíèå îãðàíè÷åíèÿ ¾âçàèìîèñêëþ÷àþùèå ðîëè¿. Ñ äðóãîé ñòîðîíû, èñõîäÿ èç
îáúåêòèâíûõ ôàêòîðîâ, ãðàô îòíîøåíèÿ G= áóäåò äîñòàòî÷íî ðàçðåæåííûì (ñì. ïðèìåð 2).  ýòîì ñëó÷àå
ïðåäïî÷òèòåëüíåé ïðåäñòàâëåíèå ãðàôà ñïèñêàìè ñìåæíîñòè èëè ñïèñêàìè ðåáåð.
Ïðåäëàãàåòñÿ äëÿ çàäàíèÿ ãðàôà G= íå ðàçðàáàòûâàòü ñîáñòâåííûé ÿçûê ïðåäñòàâëåíèÿ ãðàôîâ, à âû-
áðàòü îäèí èç îáùåïðèçíàííûõ ñòàíäàðòîâ äëÿ ïðåäñòàâëåíèÿ òåîðåòèêî-ãðàôîâûõ ìîäåëåé. Ýòî ïðèâåäåò
êàê ê ñîêðàùåíèþ âðåìåíè ðàçðàáîòêè, òàê è ê ñîâìåñòèìîñòè ñî ìíîãèìè áèáëèîòåêàìè è ïðèêëàäíûìè
ïðîãðàììàìè äëÿ ðàáîòû ñ ãðàôàìè.
Íàèáîëåå ðàñïðîñòðàíåíû ñëåäóþùèå ìåõàíèçìû îïèñàíèÿ ãðàôîâ: DOT (èñïîëüçóåòñÿ â ïðîãðàììíîì
ñðåäñòâå âèçóàëèçàöèè ãðàôîâ Graphviz), GraphML (ÿçûê îïèñàíèÿ ãðàôîâ íà îñíîâå XML), äðóãèå äèà-
ëåêòû XML äëÿ îïèñàíèÿ ãðàôîâ (GML, GXL, XGMML), DGML (ÿçûê ðàçìåòêè îðèåíòèðîâàííûõ ãðàôîâ,
èñïîëüçóåìûé â ãðàôàõ àðõèòåêòóðû Visual Studio). Âñå îíè, ïî ñóòè, ïðåäñòàâëÿþò ñîáîé ñïèñêè âåðøèí
è ðåáåð ãðàôà.
Äëÿ îïèñàíèÿ ãðàôà îòíîøåíèÿ âçàèìîèñêëþ÷åíèÿ ïðåäëàãàåòñÿ èñïîëüçîâàòü ñòàíäàðò GraphML [7].
ßçûê GraphML èìååò XML-ñèíòàêñèñ, ÷òî îáåñïå÷èâàåò åãî ñîâìåñòèìîñòü ñ äðóãèìè ôîðìàòàìè, îñíîâàí-
íûìè íà XML. Êðîìå òîãî, GraphML îáëàäàåò ñîáñòâåííûì ìåõàíèçìîì ðàñøèðåíèÿ, ÷òî ïîçâîëÿåò õðà-
íèòü äîïîëíèòåëüíóþ èíôîðìàöèþ î âåðøèíàõ èëè ðåáðàõ ãðàôà. Äëÿ èìïîðòà/ýêñïîðòà GraphML èìå-
þòñÿ ñïåöèàëüíûå ïðîãðàììíûå èíñòðóìåíòû è áèáëèîòåêè. ×òîáû ðåàëèçîâàòü ñîáñòâåííûé GraphML-
ðèäåð, ìîæíî èñïîëüçîâàòü êàêîé-ëèáî äîñòóïíûé XML-ïàðñåð, àäàïòèðîâàâ åãî ïîä ñâîè çàäà÷è.
Ïðèìåð 3. Ãðàô G îòíîøåíèÿ âçàèìîèñêëþ÷åíèÿ îïðåäåëÿåìîãî ìàòðèöåé (3) îïèñûâàåòñÿ ñëåäóþùèì
ôðàãìåíòîì GraphML-äîêóìåíòà:
Çàêëþ÷åíèå
Ïðåäñòàâëåíèå îãðàíè÷åíèÿ ¾âçàèìîèñêëþ÷àþùèå ðîëè¿ ìîäåëè RBAC2 íå â âèäå îòîáðàæåíèÿ, à â ôîðìå
áèíàðíîãî îòíîøåíèÿ âçàèìîèñêëþ÷åíèÿ íà ìíîæåñòâå ðîëåé ïîçâîëÿåò çàäàòü ýòî îãðàíè÷åíèå ïðîñòûì
íåîðèåíòèðîâàííûì ãðàôîì.  êà÷åñòâå ÿçûêà îïèñàíèÿ òàêîãî ãðàôà ïðåäëàãàåòñÿ èñïîëüçîâàòü XML-
ïîäîáíûé ÿçûê GraphML.
Èññëåäîâàíèå ñâîéñòâ îòíîøåíèÿ âçàèìîèñêëþ÷åíèÿ ïîçâîëèëî îòêàçàòüñÿ îò òðàíçèòèâíîñòè, îñòàâèâ
â êà÷åñòâå îáÿçàòåëüíûõ òðåáîâàíèé ñèììåòðè÷íîñòü è àíòèðåôëåêñèâíîñòü.
Áëàãîäàðíîñòè
Àâòîð âûðàæàþò áëàãîäàðíîñòü Ñ.Â. Áåëèìó çà ïîëåçíûå çàìå÷àíèÿ è ïðåäëîæåíèÿ â ïðîöåññå îáñóæäåíèÿ
òåìàòèêè ñòàòüè.
Ñïèñîê ëèòåðàòóðû
[1] D. Ferraiolo, J. Cugini, R. Kuhn. Role-based access control: Features and motivations. In Proceedings of
Annual Computer Security Applications Conference, IEEE Computer Society Press, 1995, pp. 249255.
[2] D.F. Ferraiolo, D.R. Kuhn. Role-Based Access Controls. In Proceedings of 15th National Computer Security
Conference, Baltimore MD, 1992, pp. 554563.
[3] M. Nyanchama, S.L. Osborn. Access Rights Administration inRole-Based Security Systems. In Proceedings
of the IFIP WG11.3 Working Conference on Database Security VII, North-Holland, 1994, pp. 3756.
[4] R. Sandhu, E. Coyne, H. Feinstein, C. Youman. Role Based Access Control: A multidimensional view. In
Proceedings of 10th Annual Computer Security Applications Conference, Orlando, 1994, pp. 5462.
[5] R.S. Sandhu, E.J. Coyne, H.L. Feinstein, C.E. Youman. Role-Based Access Control Models. IEEE Computer,
1996, N. 29(2), pp. 3847.
[6] URL: https://msdn.microsoft.com/ru-ru/library/ms157363.aspx.
[7] URL: http://graphml.graphdrawing.org/primer/graphml-primer.html.
The Mutual Exclusion Relation on a Set of Roles in Access Control Models
Nadezda F. Bogachenko
The most widespread restriction of the RBAC2 model is the "mutually exclusive roles". This restriction
is interpreted in terms of the binary relations. Properties of the constructed relation are studied. In particular,
transitive and intransitive relations are considered. The XML-like GraphML language is oered to use as language
of the description of restriction "mutually exclusive roles".