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

грани. Например, добавим к построенному дереву вершину L, соединив с ней все концевые вершины. Положим i=l,...,n, L<X_j. Для остальных вершин порядок определяется как раньше. Построенная структура является решеткой.

Упражнение Доказать

этот факт.

Приведенный пример не исчерпывает множество решеток, представимых в виде графов, однако поясняет как связаны графы и решетки.

Упражнение. Покажите, что следующие графы определяют решетки.

Не всякий граф определяет решетку. Например,

Упражнение. Доказать, что это так.

РЕШЕТКА ПОДМНОЖЕСТВ X.

Для "A, ВÎХ. Определим А<ВÞАÍВ. Все условия частичного порядка 1), 2), 3) выполняются. Кроме того, AÅB - это АÈВ, АÄВ=АÇВ. Следовательно, это решетка.

Пример 4. Х={1, 2, 3}.

( 1 2 3 )

1 2 2 3    1 3

1         2           3

Æ

Пусть программа имеет Х={Х₁,...,Х_m} - входные,Y₁...Y_n - выходные элементы. Каждый выходной элемент зависит от некоторых входных элементов. Отношение вход-выход описывается решеткой рассматриваемого типа. Решетка подмножеств строится по подмножествам X следующим образом. Для каждой Х_iX_i={Х_i}. Для каждой Y_jY_j={X_i|X_jàY_j}.

Пример 5. X₁, Х₂, X₃, Y₁, Y₂. Y₁ зависит только от X₁,Х₂; Y₂ зависит от X₁ и Х₃.

Y₁={X₁,X₂}   Y₂={X₁,X₃}

H

Y₁       Y₂

X₁

X₂                 X₃

L

MLS РЕШЕТКА

Название происходит от аббревиатуры Multilevel Security и лежит в основе государственных стандартов оценки информации. Решетка строится какпрямое произведение линейной решетки L и решетки SC подмножеств множества X, т.е. (a,b), (a’,b’) -элементы произведения, b,b’ÎL - линейная решетка,  a,a’ÎSC - решетка подмножеств некоторого множества X. Тогда

(a,b)<(a’,b’)ÛaÍa’,b<b’

Верхняя и нижняя границы определяются следующим образом:

    (a,b)Å(a¢,b¢)Û(aÈa¢,max{b,b’}),

    (a,b)Ä(a¢,b¢)Û(aÇa¢,min{b,b’}).

Вся информация {объекты системы} отображается в точки решетки {(а,b)}. Линейный порядок, как правило, указывает гриф секретности. Точки множества X обычно называются категориями.

Свойства решетки в оценке информации существенно используются при классификации новых объектов, полученных в результате вычислений. Пусть дана решетка ценностей SC, множество текущих объектов О, отображение С: 0àS, программа использует информацию объектов 0₁,..,0_n , которые классифицированы точками решетки С(0₁),...,С(0_n). В результате работы программы появился объект О, который необходимо классифицировать.