Модуль генерации форматирующих сред в распределенных реляционных СУБД

Молодченко Ж.А., Сотов Л.С., Харин В.Н. МОДУЛЬ ГЕНЕРАЦИИ ФОРМАТИРУЮЩИХ СРЕД В РАСПРЕДЕЛЕННЫХ РЕЛЯЦИОННЫХ СУБД

Обеспечение информационной безопасности (ИБ) является одной из основных задач при построении систем управления базами данных (СУБД). Современный этап развития отечественных информационных систем характеризуется широким использованием коммерческих высокопроизводительных ПЭВМ и серверных конфигураций на их основе.

Использование высокоинтегрированных аппаратных средств зарубежного производства, необходимых для обеспечения функциональных возможностей системы, предъявляет специфические требования к концепции построения системы информационной безопасности СУБД.

Типичные угрозы СИБ СУБД, связанные с использованием высокоинтегрированных аппаратных средств коммерческой ЭВМ, могут проявляться в виде спорадических инициализаций недекларированных функций аппаратной или/и программной частей системы, в результате чего может происходить:

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

разрушение хранимой информации в базах данных.

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

В работах [1], [2], [3] рассматривается подход к созданию форматирующих множеств на основе бито-

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

Рассмотрим строку длиной п бит из N битной последовательности, подлежащей хранению или обработке. Под форматом представления будем понимать матрицу инциденций для отображений бинарных отношений транспозиции каждого бита исходной строки в соответствующий бит строки-приемника. Главная диагональ этой матрицы, представленная единичными элементами, соответствует отображению п-6итовой строки самой на себя. Существует п! преобразований формата для отображения представлений п-6итной строки. Очевидно, что если выбирать определенным образом соответствующее отображение п-6итной строки в виде формата представления при оперативной обработке, то содержательная интерпретация представления становится возможной только в том случае, если известно преобразование, переводящее рассматриваемую п-битную строку в формат оперативного отображения, т.е. в ОФ-формат.

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

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

Рис.1 Дуальное преобразование битовой транспозиции

Если принять по умолчанию в качестве формата оперативной обработки один из элементов форматирующего множества, то для перевода n-битной строки в любой другой формат и обратного преобразования требуется знание всего одного элемента форматирующего множества.

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

Для формирования перестановочной матрицы элементов R необходимо осуществить генерацию n k = log2(n)-битовых уникальных последовательностей. Для этого можно использовать генератор псевдослучайной последовательности (ПСП) [4]. Наиболее простым является генератор Галуа на регистрах сдвига (Linear Feedback Shift Register - LFSR) разрядностью к бит, который в общем случае описывается уравнением

Прямое преобразование битовой транспозиции

Результирующее представление бита -формат оперативной обработки

Обратное преобразование битовой транспозиции

Представление бита в формате ОФ

ґ а1 а . . ак-1 ак "

1 0 . .. 0 0

т = 0 і . .. 0 0

V 0 0. . 1 0 ,

к -степень образующего многочлена к

ф( х) - ^ аіх*, а= і, ає {0,1}, ] = і,...к - і.

1=\

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

сдвига LFSR получается матрица, строки которой являются псевдослучайными адресами

Г Ап А12 ... А1к-1 Лк ^

А21 А22 ... А2к-1 А2к

А = А31 А32 ... А3к-1 Азк

V Ап1 Ап2 ... Апк-1 Апк )

ательности

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

Пусть У = К хX - результат форматирующего преобразования У = (у ...у ) битовой последова X = (хг...хп) . Множество У -представляет множество данных в формате оперативной обработки, множество

X -представляет собой множество данных в формате хранения. Последовательность Т можно получить с использованием п одноразрядных мультиплексоров, на адресные входы которых подаются данные соответствующей строки матрицы псевдослучайных адресов. X = ^...х ) подается на соответствующие входы данных. Преобразование описывается выражением у = X (А\,..., Ак ),*' = 1, п.

Матрица А при данном алгоритме формирования достаточно просто устроена: каждая новая строка получается сдвигом предыдущей на 1 бит и добавлением 1 бита в начало строки. Для генерации строк матрицы А предпочтительным является более сложное преобразование с использованием стохастического генератора ПСП (RFSR) [10], одна из возможных схем которого представлена на рисунке 2.

начальное значение

Ап,-, Ак, і = 1,п

Параметр преобразования (число тактов работы генератора) У I

Рисунок 2. Блок-схема стохастического генератора ПСП на базе LFSR.

Каждая строка генерируется после у. тактов генератора ПСП, где У^У .

В этом случае матрица А более сложна для анализа.

Условием, накладываемым на строки матрицы А , является рассеяние -достаточная удаленность векторов А\ ,, Ак для соседних строк. В качестве параметра удаленности удобно использовать сумму результатов операций побитового XOR соседних строк матрицы Б. = А\  А-11 ^ ^ Ак  А-\к . При полном совпадении строк Б-=0 , максимальное рассеяние Б.=п . На практике задается критическое значение Бк . Блоки данных ПСП у которых Б. < Бк отбрасываются. Такой алгоритм эффективно реализуется аппаратно и обладает высоким быстродействием.

Недостатком рассмотренных схем является то, что матрица адресов А , а соответственно перестановочная матрица элементов Я являются псевдослучайными. Для осуществления преобразования обратного форматирующему достаточно определить случайную последовательность у . Далее все определяется алгоритмом формирования ПСП, который считается известным. Кроме того, для работы генераторов ПСП необ-

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

Таким образом, в основу построения модуля генерации форматирующих сред (МГФС) необходимо положить естественный случайный процесс. Известны решения проблемы генерации случайных чисел с использованием явления радиоактивного распада [11,12], нестабильности генератора колебаний [13,14], теплового шума полупроводникового прибора [15], цифровой генератор случайных битов [16]. Последний генератор можно интегрировать в СБИС.

При использовании того или иного метода следует принимать во внимание скорость генерации, статистические свойства генерируемой последовательности, специальные требования, определяемые алгоритмом модуля

В данной работе в качестве базового элемента МГФС предлагается использовать генератор динамического шума. Такие генераторы имеют достаточно высокую выходную мощность и случайный сигнал от них легко преобразовать в случайную последовательность бит. Известно большое количество генераторов, демонстрирующих случайное поведение: генератор на диоде Ганна [6], генератор с запаздыванием в цепи обратной связи [7], генератор с инерционной нелинейностью [8] и т.п. При выборе конструкции динамического генератора шума следует учитывать статистические свойства генерируемых сигналов, ширину и

равномерность распределения спектральной плотности мощности шума, простоту и возможности интеграции в электронную микросхему.

На рисунке 3 изображена ячейка МГФС. Она состоит из двух хаотических генераторов Г1, Г2, выполненных на сферических или тонкопленочных YIG резонаторах [9].

Г1

Триггер Шмидта

>

Г 2

Рисунок 3. Базовая ячейка МГФС.

Сигналы этих генераторов поступают на триггер Шмидта, который в зависимости от соотношения амплитуд входных сигналов вырабатывает состояние 0 или 1. На выходе триггера формируется случайная последовательность бит во времени. При необходимости получить случайную последовательность нескольких бит объединяется соответствующее количество базовых ячеек МГФС.

Преимуществами данной схемы является простота (ячейка состоит из двух повторителей и триггера Шмидта), возможность реализации в виде микросхемы (МИС) с большим числом одновременно генерируемых бит, что обеспечивает большую производительность МГФС.

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

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

Для формирования на базе А перестановочной матрицы необходимо обеспечить уникальность строк А , в противном случае различные элементы Х формата хранения данных отобразятся в один элемент У

формата оперативного представления данных. Уникальность строк матрицы А обеспечивается формированием уникального подмножества Б{ е А . Это подмножество можно генерировать с использованием LFSR. Другим решением проблемы является программная проверка последовательностей А\ ,•••, Ак ,*= 1,п на уникальность, при которой дубликаты строк отбрасываются.

Исследуем модель базовой ячейки МГФС. Одним из механизмов возникновения хаотических колебаний в генераторах на YIG резонаторе является нелинейное взаимодействие с субгармоническими составляющими [8]. Модель двухмодового YIG генератора с сигналами на основной у частоте и частоте субгармоники

П

у ~ — описывается уравнениями: йх

— = кх + (85 + - р (х2 + у2)) - у - СО$(6) - к - 2у -у- х - (х2 + у2),

сО;

— = ку -

сО;

= -2г- (1 + х).

ад

где х = -« 008(^),у = « 2 = «2 ; £ -безразмерное время; « -нормированная амплитуда колебаний на

основной частоте; « -нормированная амплитуда колебаний на субгармонической частоте; к - нормированный инкремент нарастания амплитуды колебаний основной частоты; у - нормированный коэффициент нелинейной диссипации, определяющий ограничение амплитуды колебаний на основной частоте за счет нелинейности вольтамперной характеристики транзистора (у < 0) ; р^,р2,0 - нормированные коэффициенты, отражающие связь колебаний на основной и субгармонической частотах ^ = ^+8-1 — 2д>2 + ав(^2) -обобщенная фаза, - фаза огибающей на основной частоте, - фаза огибающей субгармоники,

8 = у- 2 - у2 - параметр рассинхронизма колебаний, равный разности частоты настройки основного и

удвоеной частоты субгармонического резонатора.

Второй генератор на рисунке 1 описывается аналогичными уравнениями. Триггер переключается в со-

„2 , ,.2 /_2 , , ,2

стояние 1 при условии glСt) = гцф -0^(0 + А = 0 , где «1 (/) = + у2, = ^х22 + у22 , амплитуды колебаний

первого и второго генераторов на основной частоте, А -параметр, определяющий гистерезис триггера Шмидта. Переключение в состояние 0 происходит при условии g2 0) = «(0 -«(/) +А = 0 .

Исследовались выборки случайной бит последовательности считываемой с базовой ячейки МГФС через постоянные интервалы времени. Параметры системы (1) представлены в таблице 1.

Таблица 1.

к 8, Р1 Р2 0 У

0,20 1,00 0,00 0,14 3,14 0,009

При данных значениях параметров YIG генераторы генерируют хаотический сигнал. Распределение спектральной плотности мощности сигнала генератора представлено на рисунке 4.

-10 -СПИ -20 :.

0

0.2 б.4 0.6

0,

.8

1.

F

Рисунок 4 Распределение плотности мощности сигнала YIG генератора в режиме хаотических колебаний Результаты работы модуля МГФС тестировались по методикам оценки качества генераторов ПСП [4]. Исследование гистограммы распределения элементов последовательности показало, что закон распределения символов ПСП близк к равномерному.

Распределение на плоскости и проверка серий не показали наличия каких либо закономерностей. Проверка на монотонность и исследование автокорреляционной функции свидетельствуют о случайном характере последовательностей, генерируемых МГФС.

Таким образом, в работе рассмотрены варианты структурной и функциональной частей модуля генерации форматирующих сред. Одним из вариантов построения является МГФС с использованием генератора случайной битовой последовательности на базе естественного случайного процесса, которая является

начальным состоянием генератора ПСП на LFSR или RFSR. Другим вариантом построения МГФС является

генерация перестановочной матрицы с использованием случайной битовой последовательности на базе

естественного случайного процесса. В качестве такого процесса используются хаотические колебания

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

1. В.Н. Харин, И.А. Бойченко, В.Г. Сарайкин Проектирование компонентов защиты данных в реляционных СУБД на основе CASE-технологий: Монография. - М. МГУЛ, 2002, 137 с.

2. Ж.А. Молодченко, В.Н. Харин Множественная транспозиция элементов форматирующих множеств.

Сборник материалов межвузовской научно-практической конференции «Проблемы и перспективы лесного коплекса» том 2, с.15 - 19. Воронеж. Гос. Лесотехн. Акад.. -Воронеж, 2005. - 264 с.

3. Ж.А. Молодченко, В.Н. Харин Синтез уникальных форматирующих множеств заданной мощности. Сбор-

ник материалов международной научно-практической конференции «Наука и образование на службе лесного комплекса» (к 75-летию ВГЛТА), том 2, с. 220 -223, Воронеж. Гос. Лесотехн.Акад. - Воронеж, 2005. -362 с.

4. Иванов М.А., Чугунков И. В Теория, применение и оценка качества генераторов псевдослучайных последовательностей.-M.:КУДИЦ-ОБРАЗ, 2003, 238 с.

5. Л.С.Сотов, М.Л.Коваленко. Исследование двухдоменной модели сферического микрорезонатора на основе железо-иттриевого граната в ненасыщенном режиме. Изд-во Саратовского госуниверситета, 2005, С.

6. Коростелев Г.Н., Сотов Л.С. Сложная динамика генераторов на диоде Ганна с низкочастотным контуром. Изв. вузов. Радиотехника иэлектроника.-1989.-N9.-T.34.-С.1925-1929.

7. Кияшко С.В., Пиковский А.С., Рабинович М.И. Автогенератор радиодиапазона со стохастическим поведением.//Радиотехника и электроника.- 1980.- Т.25.- 2.- С.336-343.

8. Анищенко В.С. Стохастические колебания в радиофизических системах.- Саратов: Из-во Саратовского университета,198 6.- 200 с.

9. А.А. Игнатьев, Л.С. Сотов Моделирование режимов генерации субгармонических составляющих генераторов с гетеромагнитным взаимодействием.

10. Осмоловский С.А. Стохастические методы передачи данных. М.:Радио и связь, 1991.

11. M.Guide, «Concept for a High-Performance Random Number Generator Based on Physical Random Phenomena», Frequenz, v.39, 1985, pp. 187-190.

12. M.Gude, «Ein quasi-idealer Gleichverteil-ungsgenerator basierend auf physikalischen Zufallsphinomenen», Ph.D. dissertation, Aachen University of Tecnology, 1987.

13. R.C. Fairfield, R.L. Mortenson, and K.B. Koulthart, «An LSI Random Number Denerator (RNG)»,Advances in Cryptology: Proceedings of CRYPTO 84, Springer Verlag, 1985, pp.203-230.

14. AT&T, «T7001 Random Number Generator», Data Sheet, Aug 1986.

15. M.Richter, «Fin Rauschgenerator zur Gewinning won qasi-idealen Zufallszahlen fur die stochastische Simulation,» Ph.D. dissertation, Aachen University of Technology,19 92.

16. G.B. Agnew, «Random Sources for Cryptographic Systems,» Advances in Cryptology EUROCRYPT '8 7 Proceedings, Springer-Verlag, 1988, pp.77-81.

ЛИТЕРАТУРА