Современные информационные
технологии/ 4. Информационная безопасность
к.т.н.,
доцент Сизоненко А.Б.
Краснодарский
университет МВД России
РЕАЛИЗАЦИЯ МАТРИЦЫ ДОСТУПА ПУТЕМ ПРЕДСТАВЛЕНИЯ
ЛОГИЧЕСКИХ ФУНКЦИЙ АРИФМЕТИЧЕСКИМИ ПОЛИНОМАМИ
Введение
Матрицы доступа содержат набор прав доступа субъектов
к объектам и являются основным элементом дискреционной модели разграничения
доступа. Руководящие документы требуют осуществлять контроль доступа субъектов
к защищаемым ресурсам в соответствии с матрицей доступа в автоматизированных
системах с классами защиты 1А, 1Б, 1В, 1Г [5], а для средств вычислительной
техники дискреционная модель разграничения доступа применяется с шестого по
первый класс защищенности [6]. Матрицу доступа можно свести к таблице
истинности и представить системой логических функций. В научной литературе
описаны способы реализации логических функций арифметическими полиномами (АП) [2,
4]. Такое представление, при программной реализации, отличается от традиционной
большей гибкостью, производительностью, достоверностью и, в некоторых случаях,
более компактным представлением [2, 4]. Целью данной работы является достижение
более компактного представления матрицы доступа, по сравнению с традиционным
табличным представлением, путем ее реализации арифметическими полиномами.
1. Описание дискреционной модели разграничения доступа
Рассмотрение проведем на примере модели безопасности
Харрисона-Руззо-Ульмана [1], являющейся классической дискреционной моделью, которая
реализует произвольное управление доступом субъектов к объектам и контроль за
распространением прав доступа.
Формальное описание модели состоит из следующих элементов
[1]:
1. Конечное множество прав доступа 
.
2. Конечные множества исходных субъектов 
и объектов 
. Для того, чтобы включить в область действия модели и отношения
между субъектами, принято считать, что все субъекты одновременно являются и объектами
— 
.
3. Исходная матрица доступа 
, каждая ячейка которой содержит права доступа субъектов к
объектам, принадлежащих множеству прав доступа R.
4. Конечный набор команд 
, каждая из которых состоит из условий выполнения и
интерпретации в терминах перечисленных элементарных операций.
Операция enter вводит право r в существующую ячейку матрицы доступа. Содержимое каждой ячейки
рассматривается как множество, т.е. если это право уже имеется, то ячейка не
изменяется.
Действие операции delete
противоположно действию операции enter.
Она удаляет право из ячейки матрицы доступа, если оно там присутствует. Поскольку
содержимое каждой ячейки рассматривается как множество, delete не делает ничего, если удаляемое право отсутствует в
указанной ячейке.
Операции create
subject и destroy subject соответственно
создают или удаляют субъект, а операции create
object и destroy object
соответственно создают или удаляют объект.
Поведение системы моделируется с помощью понятия
состояния. Пространство состояний системы образуется декартовым произведением
множеств составляющих ее объектов, субъектов и прав – 
. Текущее состояние системы Q в этом пространстве определяется тройкой, состоящей из множества
субъектов, множества объектов и матрицы прав доступа М, описывающей текущие права доступа субъектов к объектам, – 
.
2. Представление систем булевых функций
арифметическими полиномами
Произвольный кортеж булевых функций 
может быть единственным
образом представлен АП [2]:
где 
— целочисленный вектор коэффициентов АП;
, 
— разряды двоичной системы счисления.
АП, описывающий систему логических функций, можно
получить алгебраическим и матричным способами [2, 4]. Алгебраический способ
заключается в реализации следующего алгоритма:
Шаг 1. Получение арифметических полиномов 
для каждой булевой функции 
, 
, по формулам замены логических операций на арифметические: 
; 
; 
; 
.
Шаг 2. Получение арифметических полиномов,
взвешенных весами 
.
Шаг 3. Получение искомого арифметического
полинома 
путем суммирования
арифметических полиномов, полученных в шаге 2 и приведения подобных слагаемых.
Матричное преобразование выполняется следующим образом:
, (1)
где
— вектор истинности БФ; 
— матрица прямого арифметического преобразования
размерности 
; Матрица 
называется n-й
кронекеровской степенью 
базовой матрицы 
.
Матричные преобразования хорошо алгоритмизируются и
удобны для практического применения.
Если 
, где 
— максимальное значение, принимаемое 
, то произвольный кортеж логических функций может быть
представлен модулярным арифметическим полиномом [4]: 
, где 
. Коэффициенты модулярного АП 
лежат в области целых
неотрицательных чисел, а их числовой диапазон равен значению модуля 
[2, 3].
3. Реализация
матрицы доступа арифметическими полиномами
Разобьем матрицу доступа на столбцы, соответствующие отдельным объектам,
и представим его в виде таблицы истинности (табл. 1). Количество переменных
возьмем равным:
, (2)
где 
обозначает округление
до ближайшего большего целого числа.
Таблица 1
|
|
Номер набора |
Переменные ( |
Права доступа ( |
|
||||||
|
|
|
|
|
|
|
|
||||
|
|
0 |
0 |
|
0 |
0 |
|
|
|
|
|
|
|
1 |
0 |
|
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k-1 |
х |
|
х |
х |
|
|
|
|
|
|
|
k |
х |
|
х |
х |
– |
|
– |
– |
– |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
1 |
0 |
– |
|
– |
– |
– |
|
|
|
1 |
|
1 |
1 |
– |
|
– |
– |
– |
)
В таблице истинности первые 
значений будут
определены, а на последних 
наборах функция будет
не определена. Количество функций будет соответствовать количеству возможных
прав доступа субъекта к объекту. Логическая «1» обозначает наличие права,
логический «0» – отсутствие. Вектор Y является целочисленным, значения которого вычисляются
следующим образом: 
.
Для получения вектора коэффициентов применим прямое матричное преобразование
(1). Используя алгоритм, изложенный в [3], можно оптимизировать количество
членов арифметического полинома путем доопределения частично заданной системы
булевых функций не тех наборах, на которых значение функции не задано.
Разберем пример. Пусть дано множество субъектов 
, таким образом, 
. Множество прав доступа включает право на чтение (rd), запись
(wr), выполнение (ex), следовательно 
. Права доступа субъектов к объекту заданы.
Построим таблицу истинности. Вычислим количество переменных по формуле
(2): 
. Система булевых функций будет задана на 10 наборах и на 6
будет не определена (табл. 2).
Таблица 2
|
|
Номер набора |
Переменные ( |
Права доступа ( |
|
|||||
|
|
|
|
|
|
|
|
|||
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
3 |
|
|
2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
3 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
5 |
|
|
4 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
5 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
7 |
|
|
6 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
3 |
|
|
7 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
5 |
|
|
8 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
9 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
7 |
|
|
10 |
1 |
0 |
1 |
0 |
– |
– |
– |
– |
|
|
11 |
1 |
0 |
1 |
1 |
– |
– |
– |
– |
|
|
12 |
1 |
1 |
0 |
0 |
– |
– |
– |
– |
|
|
13 |
1 |
1 |
0 |
1 |
– |
– |
– |
– |
|
|
14 |
1 |
1 |
1 |
0 |
– |
– |
– |
– |
|
|
15 |
1 |
1 |
1 |
1 |
– |
– |
– |
– |
)
Доопределив функцию по алгоритму, изложенному в [3], на тех наборах, на
которых она не задана, получим вектор истинности:
Выполнив матричные преобразования (1) по модулю 8 получим вектор
коэффициентов АП: 
. АП будет иметь вид: 
.
Если к объекту обращается субъект 
, то вычислив значение полинома на третьем наборе переменных 
, получим 
, что соответствует матрице доступа.
ЛИТЕРАТУРА
1.
Девянин П.Н. Модели безопасности компьютерных систем: Учеб. пособие для
студ. высш. учеб. заведений / П.Н. Девянин. – М.: Издательский центр
«Академия», 2005. – 144 с.
3.
Сизоненко А.Б. Алгоритм построения модулярного арифметического полинома
по частично заданной системе булевых функций / Сборник научных трудов по
материалам международной научно-практической конференции «Современные
направления теоретических и прикладных исследований ‘2011». 15-28.03.2011.
Том 2. Технические науки. – Одесса: Черноморье, 2011. С. 72-75.
4.
Финько О.А. Модулярная арифметика параллельных логических вычислений: Монография/
под ред. В.Д. Малюгина. — М.: Институт проблем управления им. В.А.
Трапезникова РАН; Краснодар: КВИ, 2003. — 224с.
5.
Руководящий документ «Автоматизированные системы. Защита от несанкционированного
доступа к информации. Классификация автоматизированных систем и требования по
защите информации». Утвержден решением председателя ГТК при Президенте РФ от 30
марта 1992 г.
6.
Руководящий документ «Средства вычислительной техники. Защита от несанкционированного
доступа к информации. Показатели защищенности от несанкционированного доступа к
информации». Утвержден решением председателя ГТК при Президенте РФ от 30 марта
1992 г.