Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Грушо А.А., Тимонина Е.Е. Теоретические основы защиты информации - файл GRUSHO.DOC


Грушо А.А., Тимонина Е.Е. Теоретические основы защиты информации
скачать (359.8 kb.)

Доступные файлы (1):

GRUSHO.DOC3280kb.25.12.2003 04:30скачать

содержание

GRUSHO.DOC

  1   2   3   4
Грушо А.А. Тимонина Е.Е.

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

1996 г. Издательство Агентства “Яхтсмен”

В настоящее время и у нас в стране, и за рубежом достаточно много публикаций по современным стандартам защиты, средствам и методам защиты. Однако работы, которая являлась бы творческим обобщением существующих формальных моделей, нормативных документов, зарубежных стандартов в области защиты информации на нашем книжном рынке пока еще не было. Авторам удалось "оживить" разрозненные, порой противоречивые фрагменты, придав им новое качество, в виде целостных теоретических основ защиты информации.

Показаны пути использования формальных математических методов для защиты информации. Изложены основы теории защиты информационных систем. Приведены примеры доказательства защищенности автоматизированных информационных систем.

Для специалистов, работающих в области искусственного интеллекта, программирования для ЭВМ, защиты информационных и банковских систем.

Книга доктора физико-математических наук, член-корреспондента Академии Криптографии Российской Федерации, действительного члена Международной Академии Информации, профессора Александра Александровича Грушо и член-корреспондента Международной Академии Информатизации, кандидата физико-математических наук Елены Евгеньевны Тимониной посвящена введению в формальную теорию защиты информации. Выполненная в академическом стиле, работа наряду со строгими определениями и доказательствами содержит большое количество примеров из практической жизни, доходчиво иллюстрирующих основные теоретические положения.

Особо хотелось бы выделить разделы, посвященные гарантированно защищенным распределенным системам, доказательному подходу к построению систем защиты и определению политики безопасности. Что или кто является гарантом защищенности информации в автоматизированных системах в условиях, когда в общем виде проблема обеспечения безопасности в АИС относится к алгоритмически неразрешимым проблемам? Авторы дают ответ на этот вопрос, сведя его к вопросу о том, поддерживает или нет система защиты сформулированную политику безопасности.

На сегодняшний день и у нас в стране, и за рубежом достаточно много публикаций по современным стандартам защиты, средствам и методам защиты. Однако работы, которая являлась бы по своей сути творческим обобщением существующих формальных моделей, нормативных документов, зарубежных стандартов в области защиты информации на нашем книжном рынке не было. А.А. Грушо и Е.Е. Тимониной удалось "оживить" разрозненные, порой противоречивые фрагменты, придав им новое качество, в виде целостных теоретических основ защиты информации.

Хотелось бы отметить ориентацию данной книги на ведение учебной работы, что позволяет ее рекомендовать в качестве учебника для студентов и специалистов, работающих в области обеспечения безопасности самого широкого плана - от разработки политики безопасности для всей организации, до разработки конкретных систем защиты информации в АИС.

^ Доктор технических наук С. П. Расторгуев
Введение

Предлагаемая работа написана в стиле Lecture Notes и представляет введение в формальную теорию защиты информации в электронных системах обработки данных. В отличие от других руководств и пособий по защите информации здесь не ставилась задача перечислить как можно полнее все угрозы, механизмы защиты и другие детали проблемы защиты информации. Основная цель работы - доступно изложить методы анализа систем защиты информации в электронных системах обработки данных. Как большинство современных методов изучения сложных систем, анализ систем защиты предполагает иерархическую декомпозицию. Верхний уровень иерархии составляет политика безопасности со своими специфическими методами ее анализа. Следующий уровень - основные системы поддержки политики безопасности (мандатный контроль, аудит и т.д.). Затем следует уровень механизмов защиты (криптографические протоколы, криптографические алгоритмы, системы создания защищенной среды, системы обновления ресурсов и т.д.), которые позволяют реализовать системы поддержки политики безопасности. Наконец самый низкий уровень - реализация механизмов защиты (виртуальная память, теговая архитектура, защищенные режимы процессора и т.д.). В работе рассматриваются только верхние уровни этой иерархии, так как механизмы защиты достаточно полно описаны в литературе. Ограничения изложения рамками верхних уровней иерархии позволило с высокой степенью формализации ввести основные понятия и модели защиты информации, определения, что такое "хорошая" или "плохая" системы защиты, описать доказательный подход в построении систем защиты, позволяющий говорить о гарантированно защищенных системах обработки информации. Описанный подход лежит в основе многих стандартов для систем защиты и позволяет проводить анализ и аттестование защищенных систем.

Следует обратить внимание на то, что в большинстве руководств по защите верхние уровни иерархии не отражены, или не объяснено их значение. В результате создается иллюзия, что качественная защита определяется только надежностью и количеством механизмов защиты. Наводят на определенные размышления неточные переводы требований стандартов по защите, которые привозят к нам иностранные специалисты. В связи с этим, базисом для работы явился анализ исходных текстов американских стандартов по защите и статей, в которых излагались результаты анализа моделей, лежащих в основе этих стандартов. Поэтому работу можно рассматривать как изложение определенной "платформы" для разработки систем защиты информации, которая взята за основу в США, Канаде и Западной Европе.

^ Глава 1 ВСПОМОГАТЕЛЬНЫЕ СТРУКТУРЫ (МОДЕЛИ), ИСПОЛЬЗУЕМЫЕ В ЗАЩИТЕ ИНФОРМАЦИИ

Для того, чтобы провести исследование и получить практический результат часто применяют следующий прием. В объект исследования вносят некоторую структуру, которая имеет искусственный характер, но облегчает исследование. Например, для анализа взаимодействия тел физики внесли в описание окружающего мира структуры силовых взаимодействий, электрических взаимодействий. Математики для анализа реальных процессов вносят структуры вероятностного пространства и вероятностей событий. Иногда говорят, что строится модель объекта. Оба названия приемлемы, однако мы предпочитаем первое, так как в ходе анализа потребуется вносить в информацию несколько структур и анализировать их взаимодействие. В терминах моделей такие нагромождения представляются более трудными для объяснения. Далее мы рассмотрим следующие структуры, которые вносятся в неопределяемый объект под названием информация, теории защиты которого будет посвящена вся работа:

  • структура языка, позволяющая говорить об информации как о дискретной системе объектов;

  • иерархическая модель вычислительных систем и модель OSI/ISO, позволяющие аппаратную, программную, прикладную компоненты вычислительных систем и сетей связи представлять в виде объектов некоторых языков, а также представляют примеры неиерархической декомпозиции и анализа сложных систем;

  • структура информационного потока, позволяющая описывать и анализировать угрозы информации;

  • структура ценности информации, позволяющая понять, что надо и что не надо защищать;

  • структуры реляционных баз данных, которые рассматриваются как примеры организации информации в вычислительных системах, и используются для пояснения наиболее трудных проблем защиты.

В заключение главы в качестве примера проблемы согласования различных структур между собой рассматривается задача совмещения одной из структур ценности информации и структуры реляционной базы данных.
^ 1.1. ЯЗЫК, ОБЪЕКТЫ, СУБЪЕКТЫ.

Используем некоторые понятия математической логики. Пусть А конечный алфавит, А - множество слов конечной длины в алфавите А.

Из А при помощи некоторых правил выделено подмножество Я правильных слов, которое называется языком. Если Я1 - язык описания одной информации, Я2 - другой, то можно говорить о языке Я, объединяющем Я1 и Я2 описывающем ту и другую информацию. Тогда Я1 и Я2 подъязыки Я.

Будем считать, что любая информация представлена в виде слова в некотором языке Я. Кроме того, можно полагать, что состояние любого устройства в вычислительной системе достаточно полно описано словом в некотором языке. Тогда можно отождествлять слова и состояния устройств и механизмов вычислительной системы или произвольной электронной системы обработки данных (ЭСОД). Эти предположения позволяют весь анализ вести в терминах некоторого языка.

Определение Объектом относительно языка Я (или просто объектом, когда из контекста однозначно определен язык) называется произвольное конечное множество языка Я.

Пример 1. Произвольный файл в компьютере есть объект. В любой момент в файл может быть записано одно из конечного множества слов языка Я, в некотором алфавите А, которое отражает содержимое информации, хранящейся в файле. Значит, файл можно рассматривать как конечное множество слов, которые в нем могут быть записаны (возможные содержания файла). То, что в данный момент в файле содержится только одно слово, не исключает потенциально существования других записей в данном файле, а в понятие файла как объекта входят все допустимое множество таких записей. Естественно выделяется слово, записанное в файле в данный момент, - это состояние объекта в данный момент.

Пример 2. Пусть текст в файле разбит на параграфы так, что любой параграф также является словом языка Я и, следовательно, тоже является объектом. Таким образом, один объект может являться частью другого.

Пример 3. Принтер компьютера - объект. Существует некоторый (достаточно сложный) язык, описывающий принтер и его состояния в произвольный момент времени. Множество допустимых описаний состояний принтера является конечным подмножеством слов в этом языке. Именно это конечное множество и определяет принтер как объект.

В информации выделим особо описания преобразований данных.

Преобразование информации отображает слово, описывающее исходные данные, в другое слово. Описание преобразования данных также является словом. Примерами объектов, описывающих преобразования данных, являются программы для ЭВМ

Каждое преобразование информации может:

а) храниться;

б) действовать.

В случае а) речь идет о хранении описания преобразования в некотором объекте (файле). В этом случае преобразование ничем не отличается от других данных. В случае б) описание программы взаимодействует с другими ресурсами вычислительной системы - памятью, процессором, коммуникациями и др.

Определение. Ресурсы системы, выделяемые для действия преобразования, называются доменом.

Однако для осуществления преобразования одних данных в другие кроме домена необходимо передать этому преобразованию особый статус в системе, при котором ресурсы системы осуществляют преобразование. Этот статус будем называть "управление".

Определение. Преобразование, которому передано управление, называется процессом.

При этом подразумевается, что преобразование осуществляется в некоторой системе, в которой ясно, что значит передать управление.

Определение. Объект, описывающий преобразование, которому выделен домен и передано управление, называется субъектом.

То есть субъект - это пара (домен, процесс). Субъект для реализации преобразования использует информацию, содержащуюся в объекте О, то есть осуществляет доступ к объекту О.

Рассмотрим некоторые основные примеры доступов.

1. Доступ субъекта S к объекту О на чтение (r) данных в объекте О.

При этом доступе данные считываются в объекте О и используются в качестве параметра в субъекте S.

2. Доступ субъекта S к объекту О на запись (w) данных в объекте О.

При этом доступе некоторые данные процесса S записываются в объект О. Здесь возможно стирание предыдущей информации.

3. Доступ субъекта S к объекту О на активизацию процесса, записанного в О как данные (ехе). При этом доступе формируется некоторый домен для преобразования, описанного в О, и передается управление соответствующей программе.

Существует множество других доступов, некоторые из них будут определены далее. Множество возможных доступов в системе будем обозначать R.

Будем обозначать множество объектов в системе обработки данных через О, а множество субъектов в этой системе S. Ясно, что каждый субъект является объектом относительно некоторого языка (который может в активной фазе сам менять свое состояние). Поэтому S  O. Иногда, чтобы не было различных обозначений, связанных с одним преобразованием, описание преобразования, хранящееся в памяти, тоже называют субъектом, но не активизированным. Тогда активизация такого субъекта означает пару (домен, процесс).

В различных ситуациях мы будем уточнять описание вычислительной системы. Однако мы всегда будем подразумевать нечто общее во всех системах. Это общее состоит в том, что состояние системы характеризуется некоторым множеством объектов, которое будем предполагать конечным.

В любой момент времени на множестве субъектов введем бинарное отношение a активизации. S1aS2, если субъект S1, обладая управлением и ресурсами, может передать S2 часть ресурсов и управление (активизация). Тогда в графах, которые определяются введенным бинарным отношением на множестве объектов, для которых определено понятие активизации, возможны вершины, в которые никогда не входит ни одной дуги. Таких субъектов будем называть пользователями. Субъекты, в которые никогда не входят дуги и из которых никогда не выходят дуги, исключаются.

В рассмотрении вопросов защиты информации мы примем аксиому, которая положена в основу американского стандарта по защите ("Оранжевая книга") и будет обсуждаться далее. Здесь мы сформулируем ее в следующей форме.
Аксиома. Все вопросы безопасности информации описываются доступами субъектов к объектам.
Если включить в рассмотрение гипотетически такие процессы как пожар, наводнение, физическое уничтожение и изъятие, то эта аксиома охватывает практически все известные способы нарушения безопасности в самых различных вариантах понимания безопасности. Тогда для дальнейшего рассмотрения вопросов безопасности и защиты информации достаточно рассматривать множество объектов и последовательности доступов.

Пусть время дискретно, ^ Оt - множество объектов момент t, St - множество субъектов в момент t. На множестве объектов Оt как на вершинах определим ориентированный граф доступов Gt следующим образом: дуга с меткой pR принадлежит Gt тогда и только тогда, когда в момент t субъект S имеет множество доступов р к объекту О.

Согласно аксиоме, с точки зрения защиты информации, в процессе функционирования системы нас интересует только множество графов доступов {Gt}t=1T. Обозначим через ={G} множество возможных графов доступов. Тогда  можно рассматривать как фазовое пространство системы, а траектория в фазовом пространстве  соответствует функционированию вычислительной системы. В этих терминах удобно представлять себе задачу защиты информации в следующем общем виде. В фазовом пространстве  определены возможные траектории Ф, в  выделено некоторое подмножество N неблагоприятных траекторий или участков таких траекторий, которых мы хотели бы избежать. Задача защиты информации состоит в том, чтобы любая реальная траектория вычислительного процесса в фазовом пространстве  не попала во множество N. Как правило, в любой конкретной вычислительной системе можно наделить реальным смыслом компоненты модели , и N. Например, неблагоприятными могут быть траектории, проходящие через данное множество состояний ‘.

Чем может управлять служба защиты информации, чтобы траектории вычислительного процесса не вышли в N? Практически такое управление возможно только ограничением на доступ в каждый момент времени. Разумеется, эти ограничения могут зависеть от всей предыстории процесса. Однако, в любом случае, службе защиты доступно только локальное воздействие. Основная сложность защиты информации состоит в том, что имея возможность использовать набор локальных ограничений на доступ в каждый момент времени, мы должны решить глобальную проблему недопущения выхода любой возможной траектории в неблагоприятное множество N. При этом траектории множества N не обязательно определяются ограничениями на доступы конкретных субъектов к конкретным объектам. Возможно, что если в различные моменты вычислительного процесса субъект S получил доступ к объектам О1 и О2, то запрещенный доступ к объекту О3 реально произошел, так как из знания содержания объектов О1 и O2 можно вывести запрещенную информацию, содержащуюся в объекте O3.

Пример 4. Пусть в системе имеются два пользователя U1, и U2, один процесс S чтения на экран файла и набор файлов O1...Om. В каждый момент работает один пользователь, потом система выключается и другой пользователь включает ее заново. Возможны следующие графы доступов
R r

Uj------->S-------------Oi , i=l ,..., m, j=l , 2. (1)
Множество таких графов - . Траектории - последовательности графов вида (1). Неблагоприятными считаются траектории, содержащие для некоторого i= 1...m состояния
R r

U1------------>S------->Oi

R r

U2------------>S------->Oi
То есть неблагоприятная ситуация, когда оба пользователя могут прочитать один объект. Ясно, что механизм защиты должен строить ограничения на очередной доступ, исходя из множества объектов, с которыми уже ознакомился другой пользователь. В этом случае, очевидно, можно доказать, что обеспечивается безопасность информации в указанном смысле.

Пример 5. В системе, описанной в примере 4, пусть неблагоприятной является любая траектория, содержащая граф вида
R r

U1------------>S------->O1
В этом случае очевидно доказывается, что система будет защищена ограничением доступа на чтение пользователя U1 к объекту О1
^ 1.2. ИЕРАРХИЧЕСКИЕ МОДЕЛИ И МОДЕЛЬ ВЗАИМОДЕЙСТВИЯ ОТКРЫТЫХСИСТЕМ (OSI/ISO).

Ясно, что реализация автоматизированных информационных систем требует большого программно-аппаратного комплекса, который надо спроектировать, создать, поддерживать в работоспособном состоянии. Сложность этих систем такова, что требуется разработка специальной технологии проектирования и создания таких систем. В настоящее время основным инструментом решения задач анализа, проектирования, создания и поддержки в рабочем состоянии сложных систем является иерархический метод.

В основе метода лежит разбиение системы на ряд уровней, которые связаны однонаправленной функциональной зависимостью. В литературе предлагалось несколько вариантов формального и полуформального описания такой зависимости. Например, Парнас (D.L.Parnas, 1974) описывал такую зависимость следующим образом. Уровень А зависит в правильности своего функционирования от уровня В, или уровень А обращается к уровню В, или уровень А использует уровень В, или А требует присутствия правильной версии В. Однако это неформальные описания, а формализация здесь не удается из-за широкой общности понятия "сложная система" и неоднозначности разбиения на уровни. В целях понимания одного и того же в декомпозициях различной природы сложных систем можно договориться об универсальных принципах описания иерархического метода. Предположим, что интересующая нас сложная система А адекватно описана на языке Я. Предположим, что мы провели декомпозицию (разложение) языка Я на семейство языков D1,D2,...,Dn. Если язык Di, i=2,.., n, синтаксически зависит только от словоформ языка Di-1, то будем говорить, что они образуют два соседних уровня. Тогда система А может быть описана наборами слов B1,...,Bn в языках D1,D2,...,Dn причем так, что описание Вi синтаксически может зависеть только от набора Вi-1. В этом случае будем говорить об иерархической декомпозиции системы A и уровнях декомпозиции B1,...,Bn , где уровень Вi непосредственно зависит от Bi-1. Рассмотрим ряд простейших примеров иерархического построения сложных систем.

Пример 1. Пусть вся информация в системе разбита на два класса Secret и Тор Secret, которые в цифровой форме будем обозначать 0 и 1. Пусть все пользователи разбиты в своих возможностях допуска к информации на два класса, которые также будем обозначать 0 и 1. Правило допуска к информации X при запросе пользователя Y определяется условием, если класс х запрашиваемой информации X, а класс у пользователя Y, то допуск к информации разрешен тогда и только тогда, когда x=y. Это условие можно описать формально формулой некоторого языка D2
if x=y then "Допуск Y к X"
Для вычисления этого выражения необходимо осуществить следующие операции, которые описываются в терминах языка D1:
x:=U1(X),

y:=U2(Y),

z=xy

U(X,Y,z),
где U1(X) - оператор определения по имени объекта X номера класса доступа х; U2(Y) - оператор определения по имени пользователя Y номера класса допуска у;  - сложение по mod 2; U(X, Y, z) - оператор, реализующий доступ Y к X, если z=0 , и блокирующий систему, если z=l.

По построению уровень B2 зависит от B1, а вся система представлена иерархической двухуровневой декомпозицией с языками D1 и D2. Причем Я=(D1, D2).

Пример 2. Гораздо чаще используется неформальное иерархическое описание систем. Например, часто используется иерархическая декомпозиция вычислительной системы в виде трех уровней.

Аппаратная часть - Операционная система -Пользовательские программы.
^ МОДЕЛЬ OSI/ISO.
1. Одним из распространенных примеров иерархической структуры языков для описания сложных систем является разработанная организацией международных стандартов (ISO) Эталонная модель взаимодействия открытых систем (OSI), которая принята ISO в 1983 г.

ISO создана, чтобы решить две задачи:

  • своевременно и правильно передать данные через сеть связи (т.е. пользователями должны быть оговорены виды сигналов, правила приема и перезапуска, маршруты и т.д.);

  • доставить данные пользователю в приемлемой для него распознаваемой форме.

2. Модель состоит из семи уровней. Выбор числа уровней и их функций определяется инженерными соображениями. Сначала опишем модель.


Пользователь 1







Пользователь 2




прикладной уровень

7

7

прикладной уровень




представительский уровень

6

6

представительский уровень




сеансовый уровень

5

5

сеансовый уровень




транспортный уровень

4

4

транспортный уровень




сетевой уровень

3

3

сетевой уровень




канальный уровень

2

2

канальный уровень




физический уровень

1

1

физический уровень





Физическая среда
Верхние уровни решают задачу представления данных пользователю в такой форме, которую он может распознать и использовать. Нижние уровни служат для организации передачи данных. Иерархия состоит в следующем. Всю информацию в процессе передачи сообщений от одного пользователя к другому можно разбить на уровни; каждый уровень является выражением некоторого языка, который описывает информацию своего уровня. В терминах языка данного уровня выражается преобразование информации и "услуги", которые на этом уровне предоставляются следующему уровню. При этом сам язык опирается на основные элементы, которые являются "услугами" языка более низкого уровня. В модели OSI язык каждого уровня вместе с порядком его использования называется протоколом этого уровня.

Каково предназначение каждого уровня, что из себя представляет язык каждого уровня?

^ Прикладной уровень (ПУ). ПУ имеет отношение к семантике обмениваемой информации (т.е. смыслу). Язык ПУ обеспечивает взаимопонимание двух прикладных процессов в разных точках, способствующих осуществлению желанной обработки информации. Язык ПУ описывает два вида ситуаций:

  • общие элементы для всех прикладных процессов, взаимодействующих на прикладном уровне;

  • специфические, нестандартизируемые элементы приложений.

Язык ПУ состоит и постоянно расширяется за счет функциональных подъязыков. Например, разработаны протоколы (языки ПУ):

  • виртуальный терминал (предоставление доступа к терминалу процесса пользователя в удаленной системе);

  • файл (дистанционный доступ, управление и передачу информации, накопленной в форме файла);

  • протоколы передачи заданий и манипуляции (распределенная обработка информации);

  • менеджерские протоколы;























  • одним из важных протоколов прикладного уровня является "электронная почта" (протокол Х.400), т.е. транспортировка сообщений между независимыми системами с различными технологиями передачи и доставки сообщений.

^ Уровень представления (УП). УП - решает те проблемы взаимодействия прикладных процессов, которые связаны с разнообразием представлений этих процессов. УП предоставляет услуги для двух пользователей, желающих связаться на прикладном уровне, обеспечивая обмен информацией относительно синтаксиса данных, передаваемых между ними. Это можно сделать либо в форме имен, если обеим связывающимся системам известен синтаксис, который будет использоваться, либо в форме описания синтаксиса, который будет использоваться, если он не известен. Когда синтаксис передаваемой информации отличается от синтаксиса, используемого принимающей системой, то УП должен обеспечить соответствующее преобразование.

Кроме того, УП обеспечивает открытие и закрытие связи, управление состояниями УП и контролем ошибок.

^ Уровень сеанса (УС). УС обеспечивает управление диалогом между обслуживаемыми процессами на уровне представления. Сеансовое соединение сначала должно быть установлено, а параметры соединения оговорены путем обмена управляющей информацией. УС предоставляет услугу синхронизации для преодоления любых обнаруженных ошибок. Это делается следующим образом: метки синхронизации вставляются в поток данных пользователями услуги сеанса. Если обнаружена ошибка, сеансовое соединение должно быть возвращено в определенное состояние, пользователи услуги должны вернуться в установленную точку диалогового потока информации, сбросить часть переданных данных и затем восстановить передачу, начиная с этой точки.

^ Транспортный уровень (ТУ). ТУ представляет сеансовому уровню услугу в виде надежного и прозрачного механизма передачи данных (вне зависимости от вида реальной сети) между вершинами сети.

^ Сетевой уровень (СУ). СУ представляет ТУ услуги связи. СУ определяет маршрут в сети. Организует сетевой обмен (протокол IP). Управляет потоками в сети.

Канальный уровень. Представляет СУ услуги канала. Эта услуга состоит в безошибочности последовательной передачи блоков данных по каналу в сети. На этом уровне реализуется синхронизация, порядок блоков, обнаружение и исправление ошибок, линейное шифрование.

^ Физический уровень. Физический уровень обеспечивает то, что символы, поступающие в физическую среду передачи на одном конце, достигали другого конца.

Каким образом реализуются функции обмена информацией на каждом уровне? Для этого на каждом уровне к исходному блоку данных добавляется информация в виде выражения языка соответствующего уровня (как правило в виде дополнительного заголовка).

Уровни функционально взаимодействуют, во-первых, как одинаковые уровни у различных абонентов, во-вторых, как смежные уровни в одной иерархии.
Блок данных

ПУ Блок прикладных данных ДДДДДДДДД

УП Заголовок услуги представления ППППДДДДДДДДД

УС Заголовок услуги сеанса СССССППППДДДДДДДДД

ТУ Заголовок транспортной услуги ТТТТСССССППППДДДДДДДДД

СУ Заголовок сетевой услуги ссссссссТТТТСССССППППДДДДДДДДД

КУ Заголовок канала передачи ккккккссссссссТТТТСССССППППДДДДДДДДД

ФУ
Связь любых одинаковых уровней у различных абонентов при передаче, использующей соединение, состоит из трех фаз:

а) - установление соединения;

б) - передача данных;

в) - разъединение.

В фазе а) происходит переговор о наборе параметров передачи. В фазе б) - выявление и исправление ошибок, поддержание соединения.

На каждом уровне свои способы выявления и исправления ошибок:

канал - исправление битов;

сеть - разъединение и потеря пакетов; соответственно исправление этих ошибок;

сеанс, транспортирование - исправление адресации.

Важные информационные элементы каждого уровня будем называть объектами, таким образом, связь (N-1)-го, N-го и (N+l)-го уровней выглядит следующим образом; каждый уровень содержит набор объектов, которые взаимодействуют между собой в разных системах на одном уровне. На разных уровнях объекты взаимодействуют через ключи доступа услуг.

В модели OSI стандартизированы виды взаимодействия поставщика услуги на уровне N и потребителя на уровне (N+l). Эти виды называются примитивами услуг. Их четыре:

  • запрос;

  • признак;

  • ответ;

  • подтверждение.

Запрос подается пользователем услуги на (N+l)-м уровне системы А для того, чтобы обратиться к услуге протокола-поставщика услуги на N-уровне. Это приводит к посылке сообщения N-го уровня в систему В. В системе В запрос на уровне N вызывает появление примитива "признак", выпускаемого поставщиком услуги на уровне N в В на (N+l)-ый уровень.

Примитив "ответ" выпускается пользователем услуги на уровне N+l в В в ответ на признак, явившийся в точке доступа к услуге между уровнями N и N+l системы В. Примитив "ответ" является директивой протоколу уровня N завершить процедуру обращения примитива "признак". Протокол на уровне N в системе В генерирует сообщение, которое передается в сети и повторяется на уровне N системы А. Это вызывает посылку примитива "подтверждение", который выпускается поставщиком услуги в системе А на уровне N в точку доступа к услуге между уровнями N и N+l. На этом процедура, начатая запросом в точке доступа к услуге между уровнями N и N+l в системе А завершается.
^ 1.3. ИНФОРМАЦИОННЫЙ ПОТОК.

Структуры информационных потоков являются основой анализа каналов утечки и обеспечения секретности информации. Эти структуры опираются на теорию информации и математическую теорию связи. Рассмотрим простейшие потоки.

1. Пусть субъект S осуществляет доступ на чтение (r) к объекту О. В этом случае говорят об информационном потоке от О к S. Здесь объект О является источником, а S - получателем информации.

2. Пусть субъект S осуществляет доступ на запись (w) к объекту О. В этом случае говорят об информационном потоке от S к О. Здесь объект О является получателем, а S - источником информации.

Из простейших потоков можно построить сложные. Например, информационный поток от субъекта S2 к субъекту S1 по следующей схеме:

r w

S1 ---------- O ---------- S2 (1)
Субъект S2 записывает данные в объект О, а затем S1 считывает их. Здесь S2 - источник, а S1 - получатель информации. Можно говорить о передаче информации, позволяющей реализовать поток. Каналы типа (1), которые используют общие ресурсы памяти, называются каналами по памяти.

С точки зрения защиты информации, каналы и информационные потоки бывают законными или незаконными. Незаконные информационные потоки создают утечку информации и, тем самым, могут нарушать секретность данных.

Рассматривая каналы передачи информационных потоков, можно привлечь теорию информации для вычисления количества информации в потоке и пропускной способности канала. Если незаконный канал нельзя полностью перекрыть, то доля количества информации в объекте, утекающая по этому каналу, служит мерой опасности этого канала. В оценках качества защиты информации американцы используют пороговое значение для допустимой пропускной способности незаконных каналов.

С помощью теоретико-информационных понятий информационные потоки определяются следующим образом.

Будем считать, что всю информацию о вычислительной системе можно описать конечным множеством объектов (каждый объект - это конечное множество слов в некотором языке Я). В каждом объекте выделено состояние, а совокупность состояний объектов назовем состоянием системы. Функция системы - это последовательное преобразование информации в системе под действием команд. В результате, из состояния s мы под действием команды  перейдем в состояние s', обозначается: s|-- s'(). Если  последовательность команд, то композиция преобразований информации обозначается также, т.е. s|---s'() означает переход из состояния s в s' под действием последовательности команд  (автоматная модель вычислительной системы).

В общем виде для объектов X в s и Y в s' определим информационный поток, позволяющий по наблюдению Y узнать содержание X.

Предположим, что состояние X и состояние Y - случайные величины с совместным распределением Р(х, у)=Р(Х=х, Y=y), где под {Х=х} понимается событие, что состояние объекта X равно значению х (аналогично в других случаях). Тогда можно определить: P(x), Р(у/х), Р(х/у), энтропию Н(Х), условную энтропию H(X/Y) и среднюю взаимную информацию

I(Х, Y) = Н(X) - H(X/Y).

Определение. Выполнение команды  в состоянии s, переводящей состояние s в s', вызывает информационный поток от X к Y (обозначение Х-->Y ),если I(Х, Y)>0. Величина I(Х, Y) называется величиной потока информации от X к Y.

Определение. Для объектов X и Y существует информационный поток величины С (бит), если существуют состояния s и s' и последовательность команд  такие, что s|-- s'(), X-->Y.

Оценка максимального информационного потока определяется пропускной способностью канала связиХ---> Y и равна по величине

C(, X, Y)=max I(X, Y).

P(x)

Рассмотрим дальнейшие примеры информационных потоков в вычислительных системах.

1. Рассмотрим операцию присвоения значения переменных

Y:=X.

Пусть X - целочисленная случайная величина со значениями [0,15] и Р(x) - равновероятная мера на значениях X. Тогда Н(Х)=4 бит. После выполнения операции присвоения по полученной в состоянии s‘ величине Y однозначно восстанавливается X, следовательно H(X/Y)=0 I(X, Y)=4C(, X, Y)=4, т.к. рассмотренный канал - симметричный.

2. Y:=X

Z:=Y.

Выполнение этих команд вызывает непрямой (косвенный) поток информации Х-->Z, такой же величины как прямой поток Х-->Y.

3. Z:=X + Y.

Предполагаем, что X, Y [0,15] и равновероятны. Тогда Н(Х)=4, H(Y)=4.
0 < H(X/Z) = Р(х, z) logP(x/z)< 4,

(xz)
следовательно, 0 < I(Х, Z) < 4 бит.

4. Пусть X1, X2,..., Хn - независимые одинаково распределенные равновероятные случайные величины со значениями 0 и 1.

n

Z=Xi , Н(Х1) = 1,

i=1
n-1 n

H(X1/Z)= - Р(Х1=0, Z=k) logP(X=0/Z=k)- Р(Х1=1, Z=k) logP(X=l /Z=k)

k=o k=1
Если n->, то H(X1/Z) = Н(Х1)(1 + O(1)), откуда следует, что I(X1/Z)=O(l).

Отсюда возникает возможность прятать конфиденциальные данные в статистические данные.

5. Z:=XY, X и Y - равновероятные булевы случайные величины, - сложение по mod 2, тогда Z не несет информации о X или Y.

6. If X=l then Y=l. Х{0,1}, где величина X принимает свои значения с вероятностями Р(Х=0)=Р(Х==1)=1/2, начальное значение Y=0, Н(Х)=1.

H(X/Y)=  Р(х, у) logP(x/y)=0.

(x,y)

Следовательно, I(Х, Y) = 1. Поток называется неявным, в отличие от явного при операции присвоения.

7. If(Х=1) и (Y=l) then Z:=l.

H(X)=H(Y)=l, Z=l => X=l=Y
X=0 c P=2/3 }

Z = 0 => } апостериорные вероятности

X=1 c P=1/3 }
Отсюда Hz(X)O,7. Поэтому количество информации о X в Z равно

I(Z, Х)  0,3.

Если X1, Х2,...,Хn - исходные (ценные) переменные системы (программы), а Y=(Y1,...,Ym) - выходные, то I(Xi,Y) - количество информации о Хi, в потоке, который индуцируется системой. Тогда отношение I(Xi,Y)/Н(Х1) - показатель "утечки" информации о X1. Если установить порог > О для "утечки", то из условия при каждом i=l.....n,

I(Xi,Y)/Н(Хi)<,

следуют требования к защите Y.
^ 1.4. ЦЕННОСТЬ ИНФОРМАЦИИ.

Чтобы защитить информацию, надо затратить силы и средства, а для этого надо знать какие потери мы могли бы понести. Ясно, что в денежном выражении затраты на защиту не должны превышать возможные потери. Для решения этих задач в информацию вводятся вспомогательные структуры - ценность информации. Рассмотрим примеры.

1 . ^ Аддитивная модель. Пусть информация представлена в виде конечного множества элементов и необходимо оценить суммарную стоимость в денежных единицах из оценок компонент. Оценка строится на основе экспертных оценок компонент, и, если денежные оценки объективны, то сумма дает искомую величину. Однако, количественная оценка компонент невсегда объективна даже при квалифицированной экспертизе. Это связано с неоднородностью компонентв целом. Поэтому делают единую иерархическую относительную шкалу (линейный порядок, который позволяет сравнивать отдельные компоненты по ценности относительно друг друга). Единая шкала означает равенство цены всех компонент, имеющих одну и туже порядковую оценку.

Пример 1 01,...,0n - объекты, шкала 1<...<5. Эксперты оценили (2, 1, 3,...., 4) - вектор относительных

ценностей объектов. Если есть цена хотя бы одного объекта, например, C1=100 руб., то вычисляется оценка одного балла С1/. = 50 руб.,

где  - число баллов оценки первого объекта, и вычисляется цена каждого следующего объекта: C2=50руб., C3=150 руб. и т.д. Сумма дает стоимость всей информации. Если априорно известна цена информации, то относительные оценки в порядковой шкале позволяют вычислить цены компонент.

2. ^ Анализ риска. Пусть в рамках аддитивной модели проведен учет стоимости информации в системе. Оценка возможных потерь строится на основе полученных стоимостей компонент, исходя из прогноза возможных угроз этим компонентам. Возможности угроз оцениваются вероятностями соответствующих событий, а потери подсчитываются как сумма математических ожиданий потерь для компонент по распределению возможных угроз.

Пример 2. Пусть О1,...,Оn - объекты, ценности которых С1,...,Сn. Предположим, что ущерб одному объекту не снижает цены других, и пусть вероятность нанесения ущерба объекту Оi равна рi, функция потерь ущерба для объекта Оi равна

{ Ci, если объету i нанесен ущерб,

Wi= {

{ 0, в противном случае.

Оценка потерь от реализации угроз объекту i равна EWi = piСi.

Исходя из сделанных предположений, потери в системе равны W=W1+...+Wn . Тогда ожидаемые потери(средний риск) равны:

n

EW=piCi

i=1

Существуют ППП, позволяющие автоматизировать оценку риска, например, RASYS.

3. ^ Порядковая шкала ценностей. Далеко не всегда возможно и нужно давать денежную оценку информации. Например, оценка личной информации, политической информации или военной информации не всегда разумна в денежном исчислении. Однако подход, связанный со сравнением ценности отдельных информационных элементов между собой, по-прежнему имеет смысл.

Пример 3. При оценке информации в государственных структурах используется порядковая шкала ценностей. Все объекты (документы) государственного учреждения разбиваются по грифам секретности. Сами грифы секретности образуют порядковую шкалу: несекретно < для служебного пользования <секретно < совершенно секретно (НС<ДСП<С<СС) или у американцев : unclassified<confidential<secret<top secret (U<Conf<S<TS). Более высокий класс имеет более высокую ценность и поэтому требования по его защите от несанкционированного доступа более высокие.

4. ^ Модель решетки ценностей. Обобщением порядковой шкалы является модель решетки. Пусть дано SC - конечное частично упорядоченное множество относительно бинарного отношения <, т.е. для каждых А, В, С выполняется

1) рефлексивность: А<А,

2) транзитивность: А<В, В<С==>А<С,

3) антисимметричность: А<В, В<А => А=В.

Определение. Для А, BSC элемент C=ABSCназывается наименьшей верхней границей (верхней гранью), если

1) А<С, В<С;

2) A<D, B<DC<D для всех DSC.

Элемент AB, вообще говоря, может не существовать. Если наименьшая верхняя граница существует, то из антисимметричности следует единственность.

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

Определение. Для А, BC элемент E=ABSCназывается наибольшей нижней границей (нижней гранью), если

1) Е<А, Е<В;

2) D<A, D<BD<E.

Эта граница также может не существовать. Если она существует, то из антисимметричности следует единственность.

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

Определение. (SC, <) называется решеткой, если для любых А, BSC существует ABSC и ABSC.

Лемма. Для любого набора S={А1,...,Аn } элементов из решетки SC существуют единственные элементы,:

S=A1...An - наименьшая верхняя граница S;

S=A1...An - наибольшая нижняя граница S.

Доказательство. Докажем ассоциативность операции .

C1=(A1A2) A3=A1(A2A3)=C2.

По определению C1>A3, C1>A1A2. Отсюда следует С1>Аз, С1>A2, С11. Тогда C1>A2A3, С11, cледовательно, С12. Аналогично С21. Из антисимметричности С12.

Отсюда следует существование и единственность S. Такими же рассуждениями доказываем, что существует S и она единственна. Лемма доказана.

Для всех элементов SC в конечных решетках существует верхний элемент High = SC, аналогично существует нижний элемент Low = SC.

Определение. Конечная линейная решетка - это линейно упорядоченное множество, можно всегда считать {0, 1 ,..., n}=SC .

Для большинства встречающихся в теории защиты информации решеток существует представление решетки в виде графа. Рассмотрим корневое дерево на вершинах из конечного множества Х={Х1, Х2...Хn }с корнем в Xi. Пусть на единственном пути, соединяющем вершину X1 с корнем, есть вершина Xj. Положим по определению, что Хij. Очевидно, что таким образом на дереве определен частичный порядок. Кроме того, для любой пары вершин Xi и Xj существует элемент ХiХj, который определяется точкой слияния путей из Xi и Xj в корень. Однако такая структура не является решеткой, т.к. здесь нет нижней грани. Оказывается, что от условия единственности пути в корень можно отказаться, сохраняя при этом свойства частичного порядка и существование верхней грани. Например, добавим к построенному дереву вершину L, соединив с ней все концевые вершины. Положим i=l,...,n, L<Xj. Для остальных вершин порядок определяется как раньше. Построенная структура является решеткой.

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

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

Упражнение. Покажите, что следующие графы определяют решетки.
Не всякий граф определяет решетку. Например,
Упражнение. Доказать, что это так.
^ РЕШЕТКА ПОДМНОЖЕСТВ X.

Для A, ВХ. Определим А<ВАВ. Все условия частичного порядка 1), 2), 3) выполняются. Кроме того, AB - это АВ, АВ=АВ. Следовательно, это решетка.

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

( 1 2 3 )

1 2 2 3 1 3

1 2 3


Пусть программа имеет Х={Х1,...,Хm} - входные,Y1...Yn - выходные элементы. Каждый выходной элемент зависит от некоторых входных элементов. Отношение вход-выход описывается решеткой рассматриваемого типа. Решетка подмножеств строится по подмножествам X следующим образом. Для каждой ХiXi={Хi}. Для каждой YjYj={Xi|XjYj}.

Пример 5. X1, Х2, X3, Y1, Y2. Y1 зависит только от X12; Y2 зависит от X1 и Х3.

Y1={X1,X2} Y2={X1,X3}

H

Y1 Y2

X1

X2 X3

L


^ MLS РЕШЕТКА

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

,)(’,’’,’

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

max{,’}),

min{,’}).

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

Свойства решетки в оценке информации существенно используются при классификации новых объектов, полученных в результате вычислений. Пусть дана решетка ценностей SC, множество текущих объектов О, отображение С: 0S, программа использует информацию объектов 01,..,0n , которые классифицированы точками решетки С(01),...,С(0n). В результате работы программы появился объект О, который необходимо классифицировать. Это можно сделать, положив С(0)= C(01)...C(0n). Такой подход к классификации наиболее распространен в государственных структурах. Например, если в сборник включаются две статьи с грифом секретно и совершенно секретно соответственно, и по тематикам: первая - кадры, вторая - криптография, то сборник приобретает гриф совершенно секретно, а его тематика определяется совокупностью тематик статей (кадры,криптография).
^ 1.5. РЕЛЯЦИОННЫЕ БАЗЫ ДАННЫХ

Предположим, что мы хотим внести решетку ценностей (например, MLS) в конкретную информацию,которая хранится и обрабатывается на ЭВМ. Рассмотрим примеры механизмов такого внесения и проблемы, которые здесь возникают. Для определенности рассмотрим информацию, структурированную и обрабатываемую при помощи реляционной базы данных.Такая модель информации называется реляционноймоделью данных (РМ). Материалы следующих параграфов 1.5 и 1.6 базируются на работах D.Denning, T.Lunt и их коллег.

РМ состоит из отношений, которые представляют собой таблицы со многими входами, и алгебры отношений, которая позволяет строить новые отношения в терминах других отношений (в РМ входят также правила целостности хранимой информации и производной информации).

Каждое отношение R определяется схемой R (А1,...,Аn), которая характеризуется множеством атрибутовА1,..., Аn, т.е. переменных, описывающих входы таблицы.Отношение состоит из множества записей (векторов или строк), которые представляют собой значения данных в области определения атрибутов (то есть элементы таблицы - значения атрибутов).

Реляционная алгебра состоит из операторов для выбора всех или части записей, имеющих определенные значения из отношения (таблицы), и для добавления данных в различные отношения.

Для иллюстрации рассмотрим базу данных "Flight"("Полеты''). Эта база определена следующими схемами. Отношение ITEM с атрибутами: номера мест, имена, веса. Отношение Flight с атрибутами: номер рейса, дата вылета, назначение, общий вес груза. ОтношениеPAYLOAD, дающее количество использованных местна борту во время полета.

ITEM (ITEM #, ITEMNAME, Weight)

Flight (Flight #, Date, Dest, Weight)

PAYLOAD (Flight #, ITEM #, QTY, Weight)

Множество схем, определяющих отношения в базе данных, само представляется как отношение

Relation (Relname, Attmame),

которое содержит атрибуты всех отношений (иногда используется два отношения: одно для названий отношений, другое - для названий атрибутов).Например, в этой таблице запись

< Flight, Weight >

определяет, что отношение Flight содержит атрибутWeight.
^ ФУНКЦИОНАЛЬНАЯ ЗАВИСИМОСТЬ (FD)

Пусть X и Y два множества атрибутов в схеме R.

Определение. X функционально определяет Y(обозначается Х->Y) тогда и только тогда, когда не

существует двух различных строк (векторов) в R с одноименными значениями из X и различными из Y.

Например, в классном журнале с атрибутами имя, присутствие и отметка за данное число. Атрибут имя функционально определяет все остальные атрибуты.

Функциональная зависимость позволяет определить базовое для РМ понятие первичного ключа отношения.

Определение. Множество атрибутов называется кандидатом в ключи для отношения, если оно функционально определяет все другие атрибуты и является минимальным множеством (т.е. ни один атрибут из множества не может быть исключен так, чтобы оно по-прежнему функционально определяло остальные).

Определение. Для любого отношения один из кандидатов в ключи отношения выделяется и называется первичным ключом.

Замечание. Первичный ключ не обновляется. Первичный ключ может быть использован для выбора спецификации строк в отношении и для того,чтобы связать отношение в нечто целое.

Определение. Первичный ключ для R1, помещенныйв R2, называется вторичным ключом в R2.

Одно из основных правил целостности данных связано с первичным ключом. Целостность для элементов информации реляционной базы данных: ни одна строка таблицы не может принимать нулевое значение в каком-либо атрибуте из первичного ключа.Это свойство означает, что любые строки однозначно идентифицируемы.

Понятие функциональной зависимости позволяет определить и исследовать некоторые каналы утечки в базах данных, которые появляются из возможности вывода из одних объектов других (или еще один случай потока информации). Пусть множество F - это класс пар Х-->Y, X, YU=Attr(R) - множество атрибутов R.

Теорема 1. 1. Если YXU, то X->Y.

2. Если X->Y, Y->Z, X,Y,ZU, то X->Z.

3. Если X->Y, X->Z, X,Y ZU, то X->YZ.

4.Если X->Y, X->Z, X,Y,ZU, то X->YZ.

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

1. Пусть есть два набора значений атрибутов Y, что уу'. Y соответствует компонентам вектора X, для которых значения атрибутов в X не совпадают на у и у'.

2. Для строк с различными значениями атрибутовY значения векторов для атрибутов X различны. Для строк с различными значениями Z значения Y различны. Тогда значения X различны. Следовательно,X->Z.

3. Очевидно.

4. аa' из YZ, тогда отличаются значения атрибутов хотя бы Y или Z, например, Z. Тогда есть отличия на X. Теорема доказана.

Определение. Множество пар функциональных зависимостей F+ называется замыканием множества пар функциональных зависимостей F, если F+ -множество всех функциональных зависимостей, которые порождаются множеством F при помощи пп.1, 2, 3, 4 теоремы 1, то есть конструктивно построены, исходя из F, используя правила теоремы.

Определение. Два множества функциональных зависимостей (FD) F и G называются эквивалентными,если F+=G+.

Доказанная ниже теорема позволяет значительно сократить класс множеств FD, которые необходимо изучать для одного и того же F+. B частности, достаточно ограничиться редуцированными FD, эквивалентными F.

Определение. Множество F функциональныхзависимостей называется редуцированным, если:

1) в F нет двух пар Х->Y и X'->Y' таких, чтоX=X' и YY';

2) для всех X->Y в F XY=0.

Теорема 2. Для произвольного F существует редуцированный G такой, что F+=G+.

Доказательство. Для каждого Х->Y из F построим эквивалентные функциональные зависимости в G, удовлетворяющие условиям редуцированного класса. Пусть X->Y, X'->Y' из F такие, чтоХ=Х', YY'.Если YY', то возьмем в G X->YY' по п. 4.

Наоборот: если в G есть X->YY', то в G+ по п.1есть YY'->Y и YY'->Y'.

Тогда по п. 2 теоремы 1 в G+ есть Х->Y, Х->Y'.Пункт 1 доказан.

Пусть Х->Y, XY.

Отсюда по п.1 и п.2 теоремы 1: Y->Y\(YX)=>Y->X->Y\(YX).

Обратно. Если X->Y\(YX) есть в G, то Х->Y есть в G+, т.к. по п.1 теоремы 1: X->XY и Х->(Y\ (YX))(XY)=Y по п.4. Теорема доказана.

Использование функциональной зависимости для компрометации базы данных иллюстрируется следующим простым примером.

Пример 1. Пусть R - отношение в реляционной базе данных некоторой компании, содержащее атрибуты имя - ранг - зарплата. Предположим, что зарплата - совершенно секретные сведения, а имя и ранг - секретные. Предположим также, что в R выполняется следующая функциональная зависимость РАНГ -> зарплата, что означает, что все служащие одного ранга получают одинаковую зарплату. Тогда пользователь, имеющий допуск к данным не выше секретно, может получить допуск к совершенно секретной информацию о конкретном лице, если он знает соответствие ранг-зарплата хотя бы для некоторых лиц.

Для того, чтобы проанализировать возможность возникновения подобных зависимостей, надо изучить все множество F+ для набора исходных зависимостей F. Это удобнее сделать, если F - редуцированное множество, что не ограничивает общности, благодаря доказанной теореме.
^ ЦЕЛОСТНОСТЬ В РМ.

Если описывать условия целостности данных в РМ формально, это можно сделать, определив конъюнкцию одного или нескольких условий, которым должны удовлетворять набор атрибутов, выраженных формулами какого-либо языка.

Пример 2. Ограничения целостности данных могут иметь следующий вид:

I=( R.1A>O)(R1.A=R2.A)(0<R1.B+R2.B<100),где R1.A - атрибут А в отношении R1, R2.A -соответственно в R2, R1.B - атрибут В в R1, R2.В -в R2.

Если даны I1,...Im, то область состояний D базы данных определяется формулой



где под Ik также подразумевается множество значений, которые могут принимать атрибуты базы данных, удовлетворяющие логической формуле Ik. Будем предполагать D
^ РЕЛЯЦИОННЫЕ ОПЕРАТОРЫ (РО).

В реляционной модели выделяют реальные (или базовые) отношения, которые соответствуют хранящимся данным, и производные отношения, которые образуются с помощью реляционных операторов.

РО строит новые отношения из одного или нескольких существующих. Можно определить пять основных операторов.

1 . Select (R, F).

Строит новое отношение, состоящее из всех векторов (строк) R, удовлетворяющих F, где F -формула вида "AiV'' или "АiАj" где  - отношение сравнения (=, < и т.д.) и V - значение из области Di атрибута Аi. (Этот оператор также называют " -выбор" ).

2. Project (R (Ai1,...,Aik)).

Строит новое отношение следующим образом: берутся по очереди все строки R и из каждой из них выбрасываются все элементы в координатах, не являющиеся атрибутами Ai1,...,Aik, затем удаляются дубликаты в множестве получившихся строк нового отношения.

3. Union (R1, R2).

Строит новое отношение, состоящее из строк, которые есть хотя бы в одном отношении R1 или R2.Схемы для R1 и R2 должны быть совместимы, то есть иметь одинаковое число атрибутов, согласование по области определения атрибутов.

4. Diff (R1, R2).

Строит новое отношение, состоящее из тех и только тех строк R1, которые не входят в R2. Схемы R1 и R2 должны быть совместимы.

5. Product (R1, R2).

Образует новое отношение из прямого произведения таблиц R1 и R2, т.е. каждая строка R1 приписывается каждой строке R2.

Кроме перечисленных основных РО полезно определить следующие два производных оператора.

  1. Natural-join (R1, R2, (Ai1,...,Aik)).

Этот оператор выбирает и оставляет в новой таблице вектора из прямого произведения R1 и R2 такие, в которых атрибуты Ai1,...,Aik принимают одинаковое значение и затем выбрасываются лишние атрибуты (встречающиеся дважды).

  1. Outer-join (R1, R2, (Ai1,...,Aik)).

Строит Natural-join из R1 и R2 и к нему добавляет каждую строку в R1, которая не имеет подходящей строки в R2, а также добавляет каждую строку в R2, которая не имеет подходящей строки в R1.
^ 1.6. МНОГОУРОВНЕВЫЕРЕЛЯЦИОННЫЕБАЗЫ ДАННЫХ.

Следующий шаг - внести решетку ценностей в информацию, наделенную структурой реляционной базы данных. Такое внесение возможно не всегда. Функционирование базы данных может привести к противоречию с размещением информации в том или ином классе решетки и затем, к компрометации этой информации.Чтобы этого не случилось надо согласовывать все элементы БД (т.е. отношения и реляционную алгебру) и решетку ценностей. А именно, при внесении решетки в БД (короче, при классификации информации) необходимо решить следующие задачи:

1. Уметь классифицировать отдельные (неделимые) факты и объекты. В реляционных БД требуется поддерживать MLS на уровне элементов потому, что каждая строка отношения может содержать много различных фактов, имеющих разные классификации (например, время вылета - секретно, время прибытия - секретно, назначение - совершенно секретно). Хотя в литературе использовались и другие подходы.

2. Уметь создавать для просмотра пользователями виртуальные отношения. Будем называть их обзорами, в которых не все данные имеют одну классификацию. Поскольку обзоры это производные данные, то создание обзора требует проведения классификации производных данных.

3. Уметь вносить новые данные и обновлять старые, причем элементы вносимых данных могут иметь разную классификацию.

4. Необходима состоятельность классов информации, т.е. для каждого факта не должны при различных видах обработки получаться различные классы ценности. При этом пользователь может не иметь доступа к некоторым классам, но не должен из-за этого терять возможность работать с БД.

5. Уметь определять ограничения целостности на данных, имеющих различную классификацию. В частности, это надо делать автоматически, чтобы не заставлять пользователя запоминать все правила классификации информации.

6. Уметь восстанавливать данные с учетом их классификации.

Основная идея внесения MLS в БД (D. Denning, Т.Lunt и др.) состоит в создании нового отношения, где классы MLS входят как атрибуты отношения. То есть, любая данная схема расширяется включениями классификационного атрибута Сi для каждого атрибута данных Аi. Область значений Сi определяется парой классов (Li, Нi), которые определяют подрешетку отнизшего класса Li до высшего для данного атрибута класса Нi. Класс элемента аi в данном векторе определяется С(аi)=Сi в этой подрешетке (функцияC(a)=class(a) - обозначает отображение элементовРМ в решетку).

Определение. Многоуровневое базовое отношение (MLS R) определяется как произвольное отношение, у которого существуют классификационные атрибуты Сi для всех атрибутов данных Аi. Такое отношениепредставляется схемой:

R(A1, C1, ..., An, Cn)

Пример I. Решетка {S, TS}; A 1 - первичный ключ.

A1

C1

A2

C2

A3

C3

mad

S

17

S

X

S

foo

S

34

S

W

TS

ark

TS

S

TS

y

TS

Схема, в целом, классифицирована как S.

Определение. Атрибут Ai и соответственно атрибут Ci в MLS R называется одноуровневым, если область, определяемая Ci, - одна точка в решетке, иначе Ai называется многоуровневым.

Определение. MLS R называется одноуровневым, если все атрибуты одноуровневые и соответствуют одному классу.

Схема для MLS R также классифицируется. Этот класс обозначается class(R) и этот класс относится к имени отношения, имени всего набора атрибутов R и схеме. Class(R) должен доминироваться нижней гранью L1,...,Ln классификационных атрибутов С1,...,Сn в схеме. Это свойство позволяет доминировать class(R) всеми элементами таблицы.

В стандартной реляционной базе любой отсутствующий элемент представляется каким-нибудь аналогом нулевого значения. Положим, что это выполняется и для многоуровневой реляционной модели. Кроме того, нулевое значение атрибута Аi будет определять наименьшее значение Li атрибута Сi.

Тогда, если новое отношение V, например, обзор, не должен содержать TS данных, то должна осуществляться фильтрация данных, помещаемых в V. Тогда S - отфильтрованный обзор предыдущего примера,примет вид.

Пример 2.

A1

C1

A2

C2

A3

C3

mad

S

17

S

X

S

foo

S

34

S

null

S


^ КЛАССИФИКАЦИОННЫЕ ОГРАНИЧЕНИЯ.

Классификация информации в ходе функционирования системы происходит автоматически на основе классификационных ограничений (КО).

Определение. КО S - это правило, которое определяет значения для одного или более классификационных атрибутов Ci. Формально S - это четверка вида:

С=(R, А, Е, L),

где R - имя отношения; А - набор из одного или нескольких атрибутов в R; Е - опциональное выражение (например, формула логики предикатов); L - класс (точка в решетке ценностей).

Правило S интерпретируется следующим образом:

if Е then class (R.A)=L,

где R.A - означают атрибуты А в отношении R. Без ограничения общности, далее полагаем, что Ai определены на множестве действительных чисел (целые числа - частный случай, а значения не целочисленных атрибутов могут быть перенумерованы).

Замечание. Класс L - это выражение, которое может быть или константой, например, Secret, Тор Secret, или содержать одну или несколько переменных. Например, "Classt(B)" или "Class(B) , Class(C)".

Определение. Два класса L1 и L2 называются равными, если они представлены символьно идентичными записями.

Замечание. Это позволяет конструктивно проверятьсостоятельность.

Выражение Е есть конъюнкция одного или более условий, которым удовлетворяют наборы атрибутов в БД (дизъюнкции сводятся к конъюнкциям).

Пример 3.

E=(R1.A>0)((R1.A)=(R2.A))(0<R1.BR2.B<100).

Существует 4 типа классификационных ограничений.

1. Зависящие от типа. Выражение Е отсутствует и класс L - постоянный, так что все элементы, связанные с атрибутом, имеют один класс. Этот тип ограничений определяет одноуровневый атрибут. Например,

(R, А, , secret)

(R, (А, В), , secret)

2. Зависящие от значения. Здесь или Е присутствует, или L описывается выражением от переменной (или оба случая), так что класс элемента зависит от значения элемента, или от значения или класса других данныхБД. Например,

(R, A, A=1, conf)

(R, A, A=2, secret)

(R, A, , class(R.B))

(R, A, A=1, class(R.B))

3. Зависящие от уровня источника. Класс L есть выражение "класс пользователя". Например,

( R, А, , class (user))

(R, В, В > О, class (user))

4. Зависящие от грифа источника. Класс L есть выражение *, которое означает, что субъект, вводящий элемент, определяет также и класс элемента. Например,

(R.A, , *)

(R, В, В > О, *)
СОСТОЯТЕЛЬНОСТЬ.

Напомним :

Определение. Множество классификационных ограничений называется состоятельным, если для каждой возможной строки реляционной БД из D, никакие два ограничения не определяют конфликтные классы для одного и того же элемента.

Пример 4. Рассмотрим БД Flight и классификационные ограничения на атрибуты Flight #, Dest, Date в отношении Flight.

(Flight, (Flight #, Dest, Date), ( Date < 500), Secret)

(Flight, (Flight #, Dest, Date), (1< Dest< 2), T.S)

(Flight , (Flight #, Dest, Date), (Dest>2)v(Date > 500),class(user)).

Предположим, что ограничения целостности разрешают строку со следующими значениями:

(Flight #=1750, Dest=l, Date=450).

Тогда ограничения несостоятельны, так как строка удовлетворяет обоим первым двум ограничениям, но эти ограничения не определяют одинаковые классы. Однако классификационные ограничения не будут несостоятельными, если выполняются еще следующие ограничения целостности:

(1 <Dest<2)(Date>500),

так как тогда нижние два из классификационных ограничений не выполняются одновременно.

Для того, чтобы определить, является ли множество классификационных ограничений состоятельным при данных ограничениях целостности, достаточно определить, является ли каждая пара ограничений Si иSj состоятельной. (По определению проверить состоятельность требуется для каждой пары. Так как надо каждый элемент покрыть хотя бы одним ограничением, если покрывают 3 и более, и они конфликтны, то, следовательно, существуют два конфликтные.)

Для проверки пары используется следующая теорема.

Теорема. 1. Данная пара Si и Sj классификационных ограничений состоятельная, если выполняется хотя бы одно из следующих условий'.

1. Li=Lj - оба ограничения определяют один класс (напоминаем, равенство символьное);

2. .A(i)A(j)= - Si и Sj накладывают ограничения на непересекающиеся множества атрибутов;

3. EiEj= - оба ограничения не могут выполняться одновременно;



















  1. EiEjD= - оба ограничения не совместимы с условиями целостности.

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

1. Очевидно, так как требуется символьное равенство выражений, откуда следует, что конфликтное присвоение классов невозможно.

2. Происходит присвоение классов разным атрибутам.

3. Невозможно присвоить хоть один класс.

4. Невозможно присвоить хоть один класс. Теорема доказана.

Простые достаточные условия теоремы позволяют реализовать алгоритм, их проверяющий, и эффективно проверить состоятельность классификационных ограничений на практике.
^ ПОЛНОТА КЛАССИФИКАЦИОННЫХ ОГРАНИЧЕНИЙ.

Пусть доказано, что система состоятельна. Теперь надо проверить, что она полна.

Определение. Множество классификационных ограничений называется полным, если для любого набора значений атрибутов из области определения базы данных каждому элементу приписывается класс хотя бы одним классификационным ограничением.

Рассмотрим процедуру проверки полноты.

1. Для каждого атрибута А рассмотрим {Si} ивыберем все ограничения, содержащие А; если это множество пусто, то система неполная.

  1. Если классификационные ограничения не покрывают область возможных значений какого-либо атрибута, то система неполная. В противном случае система ограничений полная.

Пример 5. Пусть есть два атрибута А и В

D(A) = {(АВ), 10<А<20},

D(B) = {(АВ), -10<В<30},

S1= (R, (А, В), А + 2В<30, Sec),

S2= (R, (А, В), 5А - 2В<60, Sec),

S3= (R, (А, В), ЗВ - 2А<30, Sec).



Таким образом, все точки покрыты, отсюда следует полнота. Из того, что классы одинаковы, следует состоятельность.
^ ПРОБЛЕМА ПОЛИИНСТАНТИНАЦИИ.

Суть проблемы поясним на простом примере.

Пример 6. Пусть пользователь получил обзор, как это было сделано в примере 2 и решил дополнить его имеющимся в его распоряжении данными. Это нельзя запрещать, т.к. легко строится канал утечки. Предположим, что он достроил отношение примера 2.

A1

C1

A2

C2

A3

C3

mad

S

17

S

X

S

foo

S

34

S

U

S

ark

S

22

S

Z

S

Тогда в базе данных появились две таблицы с одинаковым набором значений ключевого атрибута, в том виде, как он виден пользователю. Это явление получило название полиинстантинация. Одно из решений проблемы - ввести классификационные атрибуты в состав ключевых атрибутов.
^ ДЕКОМПОЗИЦИЯ MLS R В СТАНДАРТНЫЕ БАЗОВЫЕ ОТНОШЕНИЯ РЕЛЯЦИОННОЙМОДЕЛИ.

Мы построим декомпозицию произвольной MLS R в семейство стандартных базовых отношений БД. Тогда реальные отношения получаются как обзор этих базовых. При этом, стандартные базовые отношения будут одноуровневыми. Отсюда следует, что механизм хранения их идентичен механизму хранения в обычной БД (не MLS), т.е. имеется ввиду отображение при помощи программного обеспечения в файлы, сегменты и т.д. Механизм защиты здесь - внешний и не связан с конкретными элементами информации. Этот механизм определяет защиту и доступ к информации любого заданного класса.Сначала несколько замечаний.

Определение. Пусть множество атрибутов А одинаково классифицируются на всех строках отношения, тогда говорят, что они равномерно классифицированы.

Теорема 3. При выполнении основных ограничений целостности множество атрибутов первичного ключа равномерно классифицировано и этот класс доминируется классами всех остальных элементов строки.

Доказательство. Если первичный ключ не равномерно классифицирован, то возможно существует пользователь, который не имеет права на высший класс, но имеет право на низший. В этом случае, в обзоре этого отношения в атрибуте высшего класса первичного ключа должны стоять null, что противоречит требованиям целостности хранимой информации (в первичном ключе нельзя иметь null). Аналогично, если какой-то элемент имеет класс меньший, чем элементы первичного ключа, то в обзоре эта строка появится, а первичный ключ будет null. Теорема доказана.

Пусть дано R(A11,..., Аnn), где А1 - первичный ключ. Первый шаг декомпозиции - создать базовоеотношение R1,X для каждого значения х атрибута С1 первичного ключа А1, т.е. для каждого x(L1, Н1)создаем R1.X(A1) с классом х. Назовем их "отношениями, связанными с первичным ключом". Если первичный ключ состоит из нескольких атрибутов, то, в силу равномерности классификации, можно считатьего одним атрибутом А1 с одним классификационным атрибутом С1 и для него создать R1.X(A1).

Второй шаг. Для произвольного А.(которое может также быть множеством атрибутов, но равномерно классифицированным с атрибутом Сi) образуем базовые отношения (называемые "отношения, связанные с атрибутом Аi").

Для i = 2,...,n каждой паре х,у, x(L1, Н1), y(Li, Нi), у>х (из теоремы 3) строим Ri,X,Y(A1, Аi) с классом у.

В этих отношениях, очевидно, А1 - первичный ключ. Однако таким отношениям присваивается класс у (поднимая, возможно, уровень значения первичного ключа, что при восстановлении исправляется исходя из информации в R1,X), таким образом, эти отношения одноуровневые по построению. Алгоритм декомпозиции следующий (заменим R на {R1,X(A1), Ri,X,Y(A1, Аi)}): для каждой строки (а11,..., ann) в R поместим а1 в R1,C1 и для i=l,..., n поместим (а1, аn) в Ri.C1.Ci. Любая новая строка при коррекции БД разлагается также.

Пример 7. Рассмотрим отношение из примера 1.





Очевидно, что, если исходное отношение - одноуровневое, то процедура декомпозиции тривиальна.

Рассмотрим процедуру восстановления MLS из базовых одноуровневых отношений. Определим оператор "ml", который преобразует строку стандартных отношений R1,X или Ri,X,Y , в строку MLS отношения.

а) m1(Ri,X) - многоуровневое отношение R' со схемой R'(A1,C1). Для каждой строки а1 в R1,X строка (а1, х) строится в R'.

б) m1(Ri,X,Y) - многоуровневое отношение R' со схемой R'(A1, С1, Аi, Сi). Для каждой строки а1, аi в Ri,X,Y строка (а1, х, аi, у) строится в R'.

Обозначим через УAB оператор Outer-join относительно атрибутов АВ и через U оператор Union. Тогда формула для восстановления R имеет вид:

Recover(R) =  (R’1,XУA1C1R’2,X УA1C1 ... УA1C1R’n,X),

x{L1,H1}

где R'i,X= U R'i,X,Y, i = 2,..., n,

ye{max(Li,x),H,)

R’1,X = m1(R1,X),

R'i,X,Y =m1(R'i,X,Y ).

Можно доказать следующую теорему.

Теорема 4. Recover (Decompose R) = R.

Вместо доказательства восстановим пример 1.

Пример 8. m1(Ri,X) = R’i,X

m1(Ri,X,Y) = R’i,X,Y


Recover(R)=((R'1SУA1C1R’2SSA1C1 (R'3SSUR'3STS))U

U(R'1TSУA1C1R’2TSTSУA1C1R'3TSTS).

Отсюда получаем отношение примера 1.
  1   2   3   4



Скачать файл (359.8 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации