Теоретические основы защиты информации

Грамотный юрист Новокузнецк окажет юридические услуги.

Теоретические основы защиты информации - стр. 75


      2. S tg-связна с Р.

Доказательство. 1. Достаточность.

Доказательство будем вести индукцией по длине n tg-пути, соединяющего S и Р. При n=l утверждение доказано в теореме 1. Пусть длина tg-пути в G, соединяющего S и Р равна n>1. Пусть также есть вершина Q на этом tg-пути, которая смежна с S. Тогда по теореме 1 можно перейти к графу G', в котором

. Ясно, что проводимые при этом команды не уничтожают tg-пути, ведущего из Р в Q. При этом длина пути из Р в Q равна (n-1), что позволяет применить предположение индукции. Тогда возможен переход от G' к G", в котором есть дуга
. Сквозной переход от G к G’ доказывает достаточность.

2. Необходимость.

Пусть для пары вершин Р и X в графе G нет дуги

, а после выполнения некоторой последовательности команд в графе G' есть дуга
. Если в G нет ни одной вершины S, для которой существует дуга
, то для любой команды с преобразования графа G в графе G’ полученном G|-cG’ при помощи с, также нет ни одной вершины S, из которой выходит дуга
. Это следует из просмотра всех четырех допустимых команд. Тогда для любой последовательности команд в графе G’, полученном из G применением этой последовательности команд, также нет какой-нибудь вершины S с дугой
. Тогда такой вершины нет в графе G', что противоречит условию. Следовательно, в графе G есть S такая, что
.

Пусть G' такой граф, когда впервые появляется дуга

. Пусть G’ такой граф, из которого по некоторой команде получился G'.  Тогда просмотр команд позволяет заключить, что дуга
возникла применением к некоторому
, команды take или grant. Это значит, что в графе G’ от Р к S существует tg-путь длины 1.

Пусть в графе G вершины Р и S не связаны tg-путем. Тогда при любой команде с в графе G’, полученном из G командой с G|-cG’ , также нет tg-пути из Р в S. В самом деле, возьмем take

Если в р не было take или grant, то новая дуга не увеличивает количество дуг с правом take или grant в новом графе, поэтому новый tg-путь возникнуть не может. Если в р есть t или g, то между V и Z существовал tg-путь и новая дуга не увеличила числа tg-связных вершин и поэтому не могла связать Р и S.


Начало  Назад  Вперед



Книжный магазин