Îòíîøåíèå âçàèìîèñêëþ÷åíèÿ íà ìíîæåñòâå ðîëåé â ìîäåëÿõ óïðàâëåíèÿ äîñòóïîì Í.Ô. Áîãà÷åíêî 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".