Î ìíîæåñòâàõ íàáîðîâ ïðàâ â ñèñòåìàõ áåçîïàñíîñòè
                   ñ ìàòðèöåé äîñòóïà
                                                           Ñ.Â. Óñîâ

                                                      raintower@mail.ru


                    Îìñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò èì. Ô.Ì. Äîñòîåâñêîãî, Îìñê, Ðîññèÿ




                                                         Àííîòàöèÿ
                          Ñòàòüÿ ïîñâÿùåíà èçó÷åíèþ ñâîéñòâ íàáîðîâ ïðàâ äîñòóïà â ñè-
                          ñòåìàõ ñ äèñêðåöèîííûì ðàçãðàíè÷åíèåì äîñòóïà. Ðàññìàòðèâà-
                          åòñÿ ìîäåëü Õàððèñîíà-Ðóççî-Óëüìàíà. Ïîêàçàíî, ÷òî ìíîæåñòâà
                          íàáîðîâ ïðàâ ôîðìèðóþò ñèñòåìó íåçàâèñèìîñòè. Ïðèâåäåí ïðè-
                          ìåð ñòðîåíèÿ ïîäñèñòåìû áåçîïàñíîñòè, êîãäà óïîìÿíóòàÿ ñèñòåìà
                          íåçàâèñèìîñòè ÿâëÿåòñÿ ìàòðîèäîì.




   Äàííàÿ ðàáîòà ïîñâÿùåíà èçó÷åíèþ íåêîòîðûõ ñâîéñòâ ìíîæåñòâ íàáîðîâ ïðàâ äîñòóïà â äèñêðåöèîí-
íûõ ìîäåëÿõ ñèñòåì áåçîïàñíîñòè.
   Ðàññìîòðèì êîìïüþòåðíóþ ñèñòåìó ñ äèñêðåöèîííîé ïîëèòèêîé áåçîïàñíîñòè Õàððèñîíà-Ðóççî-
Óëüìàíà[1].
   Â ðàìêàõ ìîäåëè HRU ðàññìàòðèâàþòñÿ ñëåäóþùèå ìíîæåñòâà:
   - ìíîæåñòâî îáúåêòîâ äîñòóïà O;
   - ìíîæåñòâî ñóáúåêòîâ äîñòóïà S, ïðè÷åì S ⊆ O;
   - ìíîæåñòâî ïðàâ äîñòóïîâ R;
   Âîçìîæíîñòü ïîëó÷åíèÿ äîñòóïà ñóáúåêòà ê îáúåêòó îïðåäåëÿåòñÿ ìàòðèöåé äîñòóïîâ  òàáëèöåé M ,
ñòðîêè êîòîðîé ïîäïèñàíû ñóáúåêòàìè, à ñòîëáöû  îáúåêòàìè. Êàæäàÿ ÿ÷åéêà ñîäåðæèò íåêîòîðûé íàáîð
ïðàâ α ∈ R, êîòîðûìè îáëàäàåò ñóáúåêò ñòðîêè ïî îòíîøåíèþ ê îáúåêòó ñòîëáöà ìàòðèöû äîñòóïîâ.
Ñîäåðæàíèå ÿ÷åéêè ìàòðèöû äîñòóïîâ, íàõîäÿùåéñÿ íà ïåðåñå÷åíèè ñòðîêè s ∈ S è ñòîëáöà o ∈ S, áóäåì
îáîçíà÷àòü M [s, o].
   Äëÿ âíåñåíèÿ èçìåíåíèé â ìàòðèöó äîñòóïîâ èñïîëüçóþòñÿ òàê íàçûâàåìûå ýëåìåíòàðíûå îïåðàòîðû 
ýòî ñèñòåìíûå êîìàíäû îïðåäåëåííîãî âèäà, âñåãî èõ 6:

 1. CreateSubject(s)  ñîçäàåò ñóáúåêò s ∈ S;

 2. CreateObject(o)  ñîçäàåò îáúåêò o ∈ O;

 3. DestroySubject(s)  óíè÷òîæàåò ñóáúåêò s;

 4. DestroyObject(o)  óíè÷òîæàåò îáúåêò o;

 5. Enter(r, s, o)  âíîñèò ïðàâî äîñòóïà r ∈ R â M [s, o], ïðè ýòîì ìàòðèöà äîñòóïîâ èçìåíÿåòñÿ ïî ïðàâèëó:
    M [s, o] := M [s, o] ∪ {r};

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
 6. Delete(r, s, o)  óäàëÿåò ïðàâî äîñòóïà r ∈ R èç M [s, o], ïðè ýòîì ìàòðèöà äîñòóïîâ èçìåíÿåòñÿ ïî
    ïðàâèëó: M [s, o] := M [s, o] \ {r}.

   Ýëåìåíòàðíûå îïåðàòîðû HRU ãðóïïèðóþòñÿ â êîìàíäû, êîòîðûå ìîæíî ðàññìàòðèâàòü êàê çàïðîñû
íà èçìåíåíèå ìàòðèöû äîñòóïîâ. Êàæäàÿ êîìàíäà ñîñòîèò èç äâóõ ÷àñòåé: óñëîâèÿ âûïîëíåíèÿ êîìàíäû
è ïîñëåäîâàòåëüíîñòè ýëåìåíòàðíûõ îïåðàòîðîâ. Êîìàíäà HRU èìååò ñëåäóþùèé âèä:
   Commandγ(x1 , x2 , . . . , xk )
   if r1 ∈ M [s1 , o1 ] and
   r2 ∈ M [s2 , o2 ] and
   .
   .
   .
   rl ∈ M [sl , ol ]
   < óñëîâèÿ âûïîëíåíèÿ êîìàíäû >
   then
   op1 , op2 , . . . , opn
   < îïåðàòîðû, ñîñòàâëÿþùèå êîìàíäó >.
   Çäåñü êàæäûé èç àðãóìåíòîâ êîìàíäû x1 . . . xk ïðåäñòàâëÿåò ñîáîé ëèáî îáúåêò èç, ëèáî ñóáúåêò, ó÷àñò-
âóþùèé â óñëîâíîé ÷àñòè ëèáî â ýëåìåíòàðíûõ îïåðàòîðàõ; o1 . . . ol ∈ O, s1 . . . sl ∈ S, r1 . . . rl ∈ R.
   Ïðè âûïîëíåíèè êàæäîé êîìàíäû ñèñòåìà ïåðåõîäèò èç îäíîãî ñîñòîÿíèÿ â äðóãîå. Ïóñòü ñèñòåìà â
ìîìåíò âðåìåíè t íàõîäèòñÿ â ñîñòîÿíèè Q(t), òîãäà ïîñëå ïðèìåíåíèÿ íåêîòîðîé êîìàíäû γ ñèñòåìà
ïåðåéäåò â íîâîå ñîñòîÿíèå Q(t + 1) â ñëåäóþùèé ìîìåíò âðåìåíè t + 1.
   Îòìåòèì, ÷òî â óñëîâíîé ÷àñòè êîìàíäû ïðîâåðÿåòñÿ òîëüêî íàëè÷èå ïðàâà â îïðåäåëåííîé ÿ÷åéêå
ìàòðèöû äîñòóïîâ, íî íå åãî îòñóòñòâèå.

  Èòàê, ïóñòü  îáùàÿ ìàòðèöà äîñòóïà, è M (t)  ñîñòîÿíèå ìàòðèöû äîñòóïà â ìîìåíò âðåìåíè t. Òîãäà
äëÿ M (t) ìîæíî ðàññìîòðåòü ìíîæåñòâî A(t) êàê íåñòðóêòóðèðîâàííûé íàáîð ïðàâ:

                            A(t) = {a ∈ S × O × R|a = (s, o, r), r ∈ M (t)[s, o]}.

Çäåñü â ñëó÷àå îáúåêòíî-ñóáúåêòíîé ìîäåëè S  ìíîæåñòâî âñåõ ñóáúåêòîâ, äîïóñêàþùèõ àêòèâàöèþ â
äàííîé ñèñòåìå, O  ìíîæåñòâî âñåõ îáúåêòîâ, êîòîðûå ìîãóò áûòü ñîçäàíû â ñèñòåìå, R  ìíîæåñòâî
âñåâîçìîæíûõ ïðàâ, êîòîðûìè ìîæåò îáëàäàòü ñóáúåêò íà îáúåêò.  ñëó÷àå îáúåêòíî-îðèåíòèðîâàííîé
ìîäåëè S  ìíîæåñòâî îáúåêòîâ, êîòîðûå ìîãóò áûòü ñîçäàíû â ñèñòåìå, O  ìíîæåñòâî ïîëåé è ìåòîäîâ
îáúåêòîâ ñèñòåìû, R  ìíîæåñòâî âñåâîçìîæíûõ ïðàâ, êîòîðûìè ìîæåò îáëàäàòü îáúåêò íà ïîëå èëè
ìåòîä.
   Ðàññìîòðèì ñåìåéñòâî A âñåâîçìîæíûõ ïîäìíîæåñòâ äåêàðòîâà ïðîèçâåäåíèÿ S × O × R. Ïîíÿòíî,
÷òî A(t) ∈ A. Ñåìåéñòâî A êîíå÷íî, åñëè ìíîæåñòâà S è O êîíå÷íû. Òàêèå êîìïüþòåðíûå ñèñòåìû áó-
äåì íàçûâàòü êîíå÷íûìè. Äàëåå, åñëè íå îãîâîðåíî ïðîòèâíîãî, áóäåì ðàññìàòðèâàòü èìåííî êîíå÷íûå
êîìïüþòåðíûå ñèñòåìû.
   Áåçîïàñíîñòü ñèñòåìû áóäåò îïðåäåëåíà â ñîîòâåòñòâèè ñ ðàáîòîé [2]:

Îïðåäåëåíèå 1. Áóäåì ãîâîðèòü, ÷òî ñîñòîÿíèå ñèñòåìû äîïóñêàåò óòå÷êó ïðàâà äîñòóïà r ∈ R, åñëè
ñóùåñòâóþò òàêèå êîìàíäà γ , îáúåêò o è ñóáúåêò s, ÷òî r ∈   / o.M [s, o] â òåêóùåì ñîñòîÿíèè ñèñòåìû, íî
r ∈ o.M [s, o] â ñîñòîÿíèè, â êîòîðîå ñèñòåìà ïåðåéäåò èç òåêóùåãî ïî âûïîëíåíèè êîìàíäû γ .

Îïðåäåëåíèå 2.   Áóäåì ãîâîðèòü, ÷òî ñèñòåìà r-áåçîïàñíà, åñëè íå ñóùåñòâóåò ïîñëåäîâàòåëüíîñòè êî-
ìàíä, ïåðåâîäÿùèõ ñèñòåìó èç íà÷àëüíîãî ñîñòîÿíèÿ â ñîñòîÿíèå, äîïóñêàþùåå óòå÷êó ïðàâà äîñòóïà r.

Îïðåäåëåíèå 3. Áóäåì ãîâîðèòü, ÷òî íàáîð ïðàâ äîñòóïà A(t) ∈ A äîïóñêàåò óòå÷êó ïðàâà äîñòóïà r ∈ R,
åñëè ñîñòîÿíèå ñèñòåìû Q(t) ñ ñîîòâåòñòâóþùåé íàáîðó ïðàâ A(t) ìàòðèöåé äîñòóïà M (t) äîïóñêàåò óòå÷êó
ïðàâà r.

Îïðåäåëåíèå 4.  Áóäåì ãîâîðèòü, ÷òî íàáîð A r-áåçîïàñåí, åñëè ñèñòåìà ñ ñîîòâåòñòâóþùåé íàáîðó ïðàâ
A íà÷àëüíîé ìàòðèöåé äîñòóïà M (0) r-áåçîïàñíà.
   Êðîìå òîãî, íàïîìíèì, ÷òî ñèñòåìîé íåçàâèñèìîñòè íà êîíå÷íîì ìíîæåñòâå X íàçûâàåòñÿ ïàðà (X, I),
I ⊆ 2X , òàêàÿ, ÷òî I ñîäåðæèò ïóñòîå ìíîæåñòâî è ëþáîå ïîäìíîæåñòâî ëþáîãî ýëåìåíòà èç I ñàìî ëåæèò â
I. Ìíîæåñòâà, ÿâëÿþùèåñÿ ýëåìåíòàìè I, íàçûâàþòñÿ íåçàâèñèìûìè, à ìíîæåñòâà, ïðèíàäëåæàùèå 2X \ I
 çàâèñèìûìè. Ìàêñèìàëüíûå ïî âêëþ÷åíèå íåçàâèñèìûå ìíîæåñòâà íàçûâàþòñÿ áàçàìè, ìèíèìàëüíûå
ïî âêëþ÷åíèþ çàâèñèìûå ìíîæåñòâà  öèêëàìè. Íàêîíåö, ñèñòåìà íåçàâèñèìîñòè íàçûâàåòñÿ ìàòðîèäîì,
åñëè âñå åå áàçû ðàâíîìîùíû [3].

Òåîðåìà 1. Ñåìåéñòâî I ⊆ A âñåõ r -áåçîïàñíûõ íàáîðîâ ïðàâ äîñòóïà îáðàçóåò ñèñòåìó íåçàâèñèìîñòè.


Äîêàçàòåëüñòâî. Çàìåòèì, ÷òî óñëîâèåì äëÿ âûïîëíåíèÿ êàêîé-ëèáî êîìàíäû ñëóæèò íàëè÷èå íåêîòîðûõ
ïðàâ, â òî âðåìÿ êàê îòñóòñòâèå ïðàâ â óñëîâíîé ÷àñòè êîìàíäû íèêîãäà íå ïðîâåðÿåòñÿ.
    Ïóñòü äëÿ íà÷àëüíîãî ñîñòîÿíèÿ ñèñòåìû Q(0) ñ îáùèì íàáîðîì ïðàâ A(0) ñóùåñòâóåò öåïî÷êà êîìàíä
γ1 , γ2 , . . . , γT , ïåðåâîäÿùàÿ ñèñòåìà â ñîñòîÿíèå Q(T ), äîïóñêàþùåå óòå÷êó ïðàâà äîñòóïà r. Áåç îãðàíè÷å-
íèÿ äîñòóïà ñ÷èòàåì öåïî÷êó γ1 , γ2 , . . . , γT íåñîêðàòèìîé, â ÷àñòíîñòè, ïðè ïîñëåäîâàòåëüíîì âûïîëíåíèè
êîìàíä ýòîé öåïî÷êè óñëîâèÿ êàæäîé êîìàíäû îêàçûâàþòñÿ âûïîëíåíû (â ïðîòèâíîì ñëó÷àå, åñëè óñëîâèÿ
íå âûïîëíåíû è êîìàíäû íå âûïîëíÿåòñÿ, åå ìîæíî âûêèíóòü èç öåïî÷êè). Ïóñòü A(0) ⊆ A0 (0), è Q0 (0) 
ñîñòîÿíèå òîé æå ñèñòåìû, ñîîòâåòñòâóþùåå íàáîðó A0 (0). Ïðèìåíèì ê ýòîìó ñîñòîÿíèþ ñèñòåìû öåïî÷êó
êîìàíä γ1 , γ2 , . . . , γT : ïî-ïðåæíåìó óñëîâèÿ âûïîëíåíèÿ âñåõ êîìàíä áóäóò âûïîëíåíû. Èòàê, íàäìíîæå-
ñòâî íàáîðà ïðàâ äîñòóïà, íå ÿâëÿþùåãîñÿ r-áåçîïàñíûì, ñàìî íå r-áåçîïàñíî. Íàîáîðîò, ïîäìíîæåñòâî
r-áåçîïàñíîãî íàáîðà áóäåò r-áåçîïàñíûì.                                                                     

   Ðàññìîòðèì íà ìíîæåñòâå íàáîðîâ âñåâîçìîæíûõ ïðàâ A àääèòèâíóþ ôóíêöèþ φ : A → R. Äëÿ ýòîãî
äîñòàòî÷íî çàäàòü çíà÷åíèå ôóíêöèè íà ýëåìåíòàõ ìíîæåñòâà S × O × R. Ñìûñëîì ýòîé ôóíêöèè ìîæåò
áûòü, íàïðèìåð, îöåíêà ýôôåêòèâíîñòè ïðàâà äîñòóïà. Ïî òåîðåìå Ðàäî-Ýäìîíäñà [3] æàäíûé àëãîðèòì
òî÷íî ðåøàåò çàäà÷ó íàõîæäåíèÿ ìàêñèìàëüíîãî çíà÷åíèÿ àääèòèâíîé ôóíêöèè íà r-áåçîïàñíîì íàáîðå,
åñëè ñåìåéñòâî I âñåõ r-áåçîïàñíûõ íàáîðîâ ïðàâ äîñòóïà ÿâëÿåòñÿ ìàòðîèäîì.

Òåîðåìà 2. Ñóùåñòâóåò äèñêðåöèîííàÿ ìîäåëü áåçîïàñíîñòè êîìïüþòåðíîé ñèñòåìû, ñåìåéñòâî âñåõ
r-áåçîïàñíûõ íàáîðîâ ïðàâ äîñòóïà êîòîðîé ÿâëÿåòñÿ ìàòðîèäîì.

    êà÷åñòâå äîêàçàòåëüñòâà ïðèâåäåì ïðèìåð òàêîé êîìïüþòåðíîé ñèñòåìû äëÿ îáúåêòíî-
îðèåíòèðîâàííîé ìîäåëè HRU [4]. Íàïîìíèì îñíîâíûå îòëè÷èÿ îáúåêòíî-îðèåíòèðîâàííîé ìîäåëè HRU
îò êëàññè÷åñêîãî ñóáúåêòíî-îáúåêòíîãî àíàëîãà.
   Ñèñòåìà ðàññìàòðèâàåòñÿ â âèäå ìíîæåñòâà îáúåêòîâ O, èìåþùèõ îòêðûòûå ïîëÿ è ñêðûòûå ïîëÿ,
à òàêæå ìåòîäû îáðàáîòêè ïîëåé. Êàæäûé èç îáúåêòîâ ïðèíàäëåæèò êàêîìó-òî êëàññó k èç ìíîæåñòâà
âñåõ êëàññîâ ñèñòåìû K. Êëàññ çàäàåò ñòðóêòóðó îáúåêòà: îïðåäåëÿåò, êàêèìè îáùèìè ñâîéñòâàìè áóäóò
îáëàäàòü ïîëÿ è ìåòîäû âñåõ îáúåêòîâ ýòîãî êëàññà. Îáúåêòû îäíîãî êëàññà îòëè÷àþòñÿ äðóã îò äðóãà
òîëüêî ñîäåðæàíèåì ñâîèõ ïîëåé.
   Ïîëåì f íàçûâàåòñÿ íåêîòîðàÿ îáëàñòü ïàìÿòè ôèêñèðîâàííîé äëèíû, êîòîðàÿ ìîæåò ñîäåðæàòü ïðî-
èçâîëüíûå äàííûå è èçìåíÿòüñÿ â ïðîöåññå ôóíêöèîíèðîâàíèÿ ñèñòåìû. Ìåòîäîì s íàçûâàåòñÿ íåêîòîðîå
îòîáðàæåíèå, èñïîëüçóþùåå â êà÷åñòâå àðãóìåíòîâ ïîëÿ, è íå èçìåíÿþùååñÿ â ïðîöåññå ôóíêöèîíèðîâàíèÿ
êîìïüþòåðíîé ñèñòåìû.
   Êëàññîì îáúåêòîâ íàçûâàåòñÿ ïðîèçâîëüíûé ñïèñîê ïîëåé è ìåòîäîâ, êàæäîìó èç êîòîðûõ ïðèñâîåíî
îäíî çíà÷åíèå èç ìíîæåñòâà {private, public}. Ïîëÿ è ìåòîäû, êîòîðûì ïðèñâîåíî çíà÷åíèå private, íàçû-
âàþòñÿ ñêðûòûìè. Ïîëÿ è ìåòîäû, êîòîðûì ïðèñâîåíî çíà÷åíèå public, íàçûâàþòñÿ îòêðûòûìè.
   Ñîâîêóïíîñòü ïîëåé è ìåòîäîâ ïîñòðîåííûõ ïî ñïèñêó, çàäàâàåìîìó êëàññîì, íàçûâàåòñÿ îáúåêòîì êëàñ-
ñà. Îáúåêò êëàññà, äëÿ êîòîðîãî íå ñóùåñòâåííà ëèáî î÷åâèäíà â äàííîé çàäà÷å ïðèíàäëåæíîñòü ê êîí-
êðåòíîìó êëàññó, áóäåì íàçûâàòü îáúåêòîì. Äëÿ êàæäîãî îáúåêòà o ∈ O îïðåäåÿþòñÿ ìíîæåñòâî ñêðûòûõ
ïîëåé o.P , ìíîæåñòâî îòêðûòûõ ïîëåé o.F è ìíîæåñòâî ìåòîäîâ o.S .
   Äîñòóïîì ìåòîäà s ê ïîëþ f íàçûâàåòñÿ àêòèâèçàöèÿ ìåòîäà s òàêèì îáðàçîì, ÷òî îáúåêò o ÿâëÿåòñÿ
àðãóìåíòîì ñîîòâåòñòâóþùåãî îòîáðàæåíèÿ. Äîñòóï ê ñêðûòûì ïîëÿì îáúåêòà èìåþò òîëüêî ìåòîäû ýòîãî
îáúåêòà. Êðîìå òîãî, ìåòîäû ìîãóò îáðàùàòüñÿ ê îòêðûòûì ïîëÿì äðóãèõ îáúåêòîâ. Âîçìîæíîñòü äîñòóïà
ê ñêðûòûì ïîëÿì îáúåêòà òîëüêî ìåòîäàìè ýòîãî æå îáúåêòà íàçûâàåòñÿ èíêàïñóëÿöèåé. Äëÿ îòêðûòûõ
ïîëåé (public) áóäåì ñ÷èòàòü âåðíûì ñëåäóþùåå ïðåäïîëîæåíèå: îòêðûòûå ïîëÿ âñåõ îáúåêòîâ èìåþò îäíî
è òî æå ìíîæåñòâî âîçìîæíûõ òèïîâ äîñòóïà. Ìíîæåñòâî äîñòóïîâ ê îòêðûòûì ïîëÿì îáîçíà÷èì ÷åðåç
R.
   Äëÿ ïîñòðîåíèÿ ñèñòåìû äèñêðåöèîííîãî ðàçäåëåíèÿ äîñòóïà äëÿ êàæäîãî îáúåêòà o ∈ O ââîäèòñÿ
äîïîëíèòåëüíîå private ïîëå M , ñîäåðæàùåå ëîêàëüíóþ ìàòðèöó äîñòóïîâ: o.M : O × (o.F ∪ o.S) → 2R ∪
{0, 1}, ïðè÷åì o0 .M [o, f ] → 2R , ãäå f ∈ o0 .F ; o, o0 ∈ O, òî åñòü äëÿ îòêðûòûõ ïîëåé â ÿâíîì âèäå çàäàåòñÿ
ìíîæåñòâî ðàçðåøåííûõ äîñòóïîâ, è o0 .M [o, s] → {0, 1}(o, o0 ?O), ãäå s ∈ o0 .S ; o, o0 ∈ O òî åñòü äëÿ ìåòîäîâ
îïðåäåëÿåì ðàçðåøåíèå (1) èëè çàïðåò (0) âûçîâà.
   Ïî àíàëîãèè ñ ñóáúåêòíî-îáúåêòíîé ìîäåëüþ HRU, äëÿ îáúåêòíî-îðèåíòèðîâàííûõ ìîäåëåé ââîäÿòñÿ
ñëåäóþùèå ýëåìåíòàðíûå îïåðàòîðû:

 1. Create(o, k)  ñîçäàåò îáúåêò o êëàññà k ∈ K, åñëè o ∈ O.

 2. Destroy(o)  óíè÷òîæàåò îáúåêò o, åñëè o ∈ O.

 3. Enter(r, o, o0 .f )  âíîñèò ïðàâî äîñòóïà r â o0 .M [o, f ], åñëè o, o0 ∈ O.

 4. Delete(r, o, o0 .f )  óäàëÿåò ïðàâî r äîñòóïà èç o0 .M [o, f ], åñëè o, o0 ∈ O.

 5. Grant(o, o0 .s)  ðàçðåøàåò âûçîâ îáúåêòó o ìåòîäà o0 .s, åñëè o, o0 ∈ O.

 6. Deprive(o, o0 .s)  çàïðåùàåò âûçîâ îáúåêòó o ìåòîäà o0 .s, åñëè o, o0 ∈ O.

   Ïîä ñîñòîÿíèåì êîìïüþòåðíîé ñèñòåìû â êàæäûé ìîìåíò âðåìåíè ïîíèìàåòñÿ ñîâîêóïíîñòü ìíîæåñòâà
âñåõ îáúåêòîâ ñèñòåìû â ýòîò ìîìåíò âðåìåíè è ñîñòîÿíèÿ âñåõ ìàòðèö äîñòóïîâ o.M îáúåêòîâ ñèñòåìû
â ýòîò ìîìåíò âðåìåíè. Ñîñòîÿíèÿ êîìïüþòåðíîé ñèñòåìû â ìîäåëè HRU èçìåíÿþòñÿ ïîä âîçäåéñòâèåì
çàïðîñîâ íà ìîäèôèêàöèþ ìàòðèöû äîñòóïà â âèäå êîìàíä ñëåäóþùåãî ôîðìàòà:
   Commandγ(x1 , ..., xg ) :
   if <êîíúþíêöèÿ ëîãè÷åñêèõ âûðàæåíèé âèäà r ∈ o0 .M [o, f ] èëè o0 .M [o, s] = 1>
   then <ïîñëåäîâàòåëüíîñòü ýëåìåíòàðíûõ îïåðàòîðîâ>.
   Çäåñü àðãóìåíòû xi ïðåäñòàâëÿþò ñîáîé îáúåêòû, ó÷àñòâóþùèå â êà÷åñòâå àðãóìåíòîâ â óñëîâíîé ÷àñòè
ëèáî â ýëåìåíòàðíûõ îïåðàòîðàõ.

Äîêàçàòåëüñòâî. Ïóñòü ìíîæåñòâî êëàññîâ ñèñòåìû K = {k1 , k2 , . . . , km }. Äëÿ ïðîñòîòû ïðèìåì, ÷òî âñå
îáúåêòû êàæäîãî êëàññà óñòðîåíû äîâîëüíî ïðîñòî: îíè îáëàäàþò îäíèì ìåòîäîì s è îäíèì îòêðûòûì
ïîëåì f , ê êîòîðîìó ñóùåñòâóåò äâà âèäà äîñòóïà: r (áåçîïàñíûé) è w (îïàñíûé). Áóäåì ðàññìàòðèâàòü
ìíîæåñòâî íåçàâèñèìîñòè, ñîâïàäàþùåå ñî ìíîæåñòâîì âñåõ w-áåçîïàñíûõ íàáîðîâ ïðàâ äîñòóïà. Äëÿ
ýòîãî íåîáõîäèìî îïðåäåëèòü, êàêèå êîìàíäû ïðèñóòñòâóþò â ñèñòåìå.
   Ðàññìîòðèì êîìïüþòåðíóþ ñèñòåìó êàê äâóäîëüíûé ãðàô G, â êîòîðîì êàæäîìó îáúåêòó o ñîîòâåò-
ñòâóåò äâå âåðøèíû: o.s è o.f , î÷åâèäíî, ïðåäñòàâëÿþùèå ìåòîä è ïîëå ýòîãî îáúåêòà. Âåðøèíû o.s è o0 .f
ñîåäèíåíû ðåáðîì â ìîìåíò âðåìåíè t, åñëè a = (o, o0 .f, r) ∈ A(t), ãäå A(t)  òåêóùèé íàáîð ïðàâ äîñòóïà
ñèñòåìû. Ïðè ýòîì, âîçìîæíî, o = o0 . Ìû áóäåì îòîæäåñòâëÿòü ïðàâî a = (o, o0 .f, r) ñ ðåáðîì ãðàôà G.
Òàêèì îáðàçîì, G(t) = G(O, A(t)). Ïîñòðîèì òàêóþ ñèñòåìó êîìàíä, êîòîðàÿ äîïóñêàåò äîáàâëåíèå ðåáðà
â ýòîì ãðàôå (òî åñòü ïðàâà r íåêîòîðîãî îáúåêòà íà ïîëå f ýòîãî èëè äðóãîãî îáúåêòà), òîëüêî åñëè îíî íå
ïðèâîäèò ê îáðàçîâàíèþ öèêëà. Åñëè æå öèêë â ãðàôå óæå ñóùåñòâóåò, òî ñîîòâåòñòâóþùåå ñîñòîÿíèå ñè-
ñòåìû äîïóñêàåò óòå÷êó ïðàâà w. Äëÿ ðåàëèçàöèè òðåáóåìûõ êîìàíä ââåäåì äîïîëíèòåëüíîå (ôèêòèâíîå)
ïðàâî äîñòóïà r0 , îáîçíà÷àþùåå îòñóòñòâèå ïðàâà r.
   Âîò êîìàíäà, äîáàâëÿþùåå ðåáðî, íå ïðèâîäÿùåå ê îáðàçîâàíèþ öèêëà:
   Command1(o1 : k1 , o2 : k2 , . . . , om : km )
   if < êîíúþíêöèÿ óñëîâèé âèäà r0 ∈ o∗ .M [o∗∗ , f ] òàêèõ, ÷òî â ãðàôå G îòñóòñòâèå ðåáåð (o∗∗ , o∗ .f, r),
ñîîòâåòñòâóþùèõ ïðîâåðÿåìûì ïðàâàì, äîñòàòî÷íî äëÿ åãî àöèêëè÷íîñòè, òî åñòü G áåç óêàçàííûõ ðåáåð
ÿâëÿåòñÿ ëåñîì >
   then
   Enter(r, o, o0 .f ) (âàæíî, ÷òî óñëîâíîé ÷àñòè íå ïðîâåðÿëîñü îòñóòñòâèå ðåáðà a = (o, o0 .f, r)),
   Delete(r0 , o, o0 .f ).
   Êîìàíä òàêîãî âèäà ìîæåò áûòü äîâîëüíî ìíîãî, òàê êàê êîëè÷åñòâî ëåñîâ èç óñëîâèÿ êîìàíäû, ðàâíî
êàê è ìíîæåñòâî âàðèàíòîâ äîáàâëÿåìîãî ðåáðà èç òåëà êîìàíäû, äîâîëüíî âåëèêî. Âïðî÷åì, òàêèõ êîìàíä
ìîæåò è íå áûòü âîîáùå.
   Êîìàíäû, ïðèâîäÿùàÿ ê óòå÷êå ïðàâà w â ñëó÷àå íàëè÷èÿ â ãðàôå ñèñòåìû öèêëà, âûãëÿäÿò ãîðàçäî
ïðîùå:
  Command2(o1 : k1 , o2 : k2 , , om : km )
  if < êîíúþíêöèÿ óñëîâèé âèäà r ∈ o∗ .M [o∗∗ , f ] òàêèõ, ÷òî â ãðàôå G ðåáðà (o∗∗ , o∗ .f, r), ñîîòâåòñòâóþùèõ
ïðîâåðÿåìûì ïðàâàì, îáðàçóþò öèêë, íàïðèìåð:
  r ∈ o∗ .M [o∗∗ , f ]&r ∈ o∗ .M [o∗ , f ]&r ∈ o∗∗ .M [o∗∗ , f ]&r ∈ o∗∗ .M [o∗ , f ] >
  then
  Enter(w, o, o0 .f ).
  Êîìàíäà, ñîçäàþùàÿ îáúåêò, ìîæåò âíåñòè ëèáî ïðàâî äîñòóïà r ýòîãî îáúåêòà ê ïîëÿì äðóãèõ îáúåêòîâ,
ëèáî ïðàâî äîñòóïà r äðóãèõ îáúåêòîâ ê ïîëþ ñîçäàííîãî îáúåêòà, íî íå òî è äðóãîå îäíîâðåìåííî. Òàêèå
äåéñòâèÿ íå íàðóøàò àöèêëè÷íîñòü ãðàôà ñèñòåìû. Òàêæå â äàííîé ñèñòåìå äîïóñòèìû ïðîèçâîëüíûå
êîìàíäû, íå ñîäåðæàùèå îïåðàöèè Enter.
  Ïîíÿòíî, ÷òî ñèñòåìà íåçàâèñèìîñòè, îáðàçîâàííàÿ w-áåçîïàñíûìè ìíîæåñòâàìè ïðàâ äîñòóïà ïîñòðî-
åííîé êîìïüþòåðíîé ñèñòåìû, áóäåò ÿâëÿåòñÿ äâóäîëüíûì ìàòðîèäîì, à èìåííî  öèêëè÷åñêèì ìàòðîèäîì
ãðàôà ñèñòåìû G.                                                                                               
Çàìå÷àíèå 1. Ïðèìåð, ïîñòðîåííûé â òåîðåìå, ðàáîòàåò òîëüêî â ñëó÷àå îäíîðîäíîé ñèñòåìû áåçîïàñíî-
ñòè. Åãî ìîæíî ðàñïðîñòðàíèòü íà ïðîèçâîëüíóþ êîíå÷íóþ ñèñòåìó, åñëè ââåñòè îòäåëüíûé ïîäêëàññ äëÿ
êàæäîãî îáúåêòà (èç êîíå÷íîãî ìíîæåñòâà).

Çàìå÷àíèå 2. Ñóùåñòâóåò è áîëåå ïðîñòîé ïðèìåð ìàòðîèäà: êîãäà äëÿ óòå÷êè ïðàâà w äîñòàòî÷íî
íàáðàòü îïðåäåëåííîå (ñêàæåì, l) êîëè÷åñòâî ïðàâ r. Ïðè ýòîì åñëè |A| < l, òî ìîæíî äîáàâèòü åùå îäíî
ïðàâî l. Îäíàêî è â ýòîì ñëó÷àå òðåáóåòñÿ îäíîðîäíîñòü ñèñòåìû è íåâîçìîæíîñòü ïîäñòàâèòü â êîìàíäó
îäèí è òîò æå îáúåêò íåñêîëüêî ðàç.

Çàìå÷àíèå 3. Ñèñòåìà, ïîñòðîåííàÿ â òåîðåìå, äîïóñêàåò ïðîâåðêó r -áåçîïàñíîñòè, ïðè÷åì äîâîëüíî ïðî-
ñòóþ: åñëè â íà÷àëüíîì ñîñòîÿíèè ñèñòåìû ýëåìåíòû ìíîæåñòâà A(0) îáðàçóþò öèêë, òî ñèñòåìà äîïóñêàåò
óòå÷êó ïðàâà w, â ïðîòèâíîì ñëó÷àå îíà w-áåçîïàñíà.

Ñïèñîê ëèòåðàòóðû
[1] M. A. Harrison, W. L. Ruzzo, J. D. Ulman. Protection in Operating Systems. Communications of the ACM,
    1425, 1975.

[2] M. V. Tripunitara, N. Li. The Foundational work of Harrison-Ruzzo-Ullman Revisited. Center for Education
    and Research in Information Assurance and Security, Purdue University, West Lafayette, IN 47907-2086,
    2006.

[3] J. Edmonds. Matroids and the Greedy Algorithms. Math Programming, 127136, 1971.

[4] S. V. Belim, S. Yu. Belim, S. V. Usov. Ob"ektno-orientirovannaya modikatsiya modeli bezopasnosti HRU.
    Problemy informatsionnoy bezopasnosti. Komp'yuternye sistemy, 39(1):614, 2010 (in russian).




 Some Properties of Sets of Rights in Access Matrix Models of Security Systems
                                                Sergey V. Usov

   The article is devoted to studying the properties of sets of access rights in the models of security systems
with discretionary access control. The Harrison-Ruzzo-Ulman model of access control is considered. It is shown
that the sets of rights create an independence system. An example of the security system with the sets of rights
forming matroid is shown.