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

ГГ6 оя

1 9 СЕН Ковела Сергій Іванович

УДК 681.3:681.327.8

МЕТОДИ ЗАХИСТУ ТА ПІДТРИМКИ ЦІЛІСНОСТІ ІНФОРМАЦІЙНОГО ЗАБЕЗПЕЧЕННЯ САПР

05.13.12 - Системи автоматизації проектувальних робіт

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня кандидата технічних наук

Львів - 2000

Дисертацією є рукопис.

Робота виконана у Державному університеті “Львівська Політехі Міністерства освіти і науки України.

Науковий керівник: кандидат технічних наук, доцент

Лобур Михайло Васильович, декан факультету комп’ютерної техніки інформаційних технологій Державного універск “Львівська Політехніка”

Офіційні опоненти: доктор технічних наук, професор,

Хорошко Володимир Олексійович,

професор кафедри “Інформаційно-діагност системи” Київського міжнародного універси цивільної авіації

доктор технічних наук, доцент,

Овсяк Володимир Казимирович,

професор кафедри “Автоматизація і комп’кл технології” Української академії друкарства (м. Лі

Провідна установа: Національний технічний університет Укр

“Київський політехнічний інститут” (м. К

кафедра “Автоматизовані системи управління”

засіданні спеціалізованої вченої ради Д35.052.05 у Державному універск “Львівська Політехніка” (79013, Львів-13, вул. С.Бандери, 12).

З дисертацією можна ознайомитися у бібліотеці Держав) університету “Львівська Політехніка” (Львів, вул. Професорська,!).

Захист відбудеться “ЗО ” _________ 2000 р. о год

Вчений секретар спегралізовапої вченої ради, кандидат технічних наук, доцент

С.П.Ткаченко

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

■дуальність теми. Автоматизація проектувальних робіт с однією з кливіших проблем сучасної науки й техніки. Створення систем автоматизації ування є складною науково-технічною проблемою і вимагає відповідного ґгичного, програмного та інформаційного забезпечення. Основою даційного забезпечення САПР є автоматизовані банки даних, до складу яких л. бази даних (БД) та системи управління ними (СУБД). Для забезпечення їх івного функціонування й використання в САПР вони повинні відповідати ом, часто суперечливим вимогам.

собливістю САПР є те, що в процесі проектування можуть динамічно ватися такі умови користування інформаційним забезпеченням, як правила іу та коректності його використання. Саме тому надзвичайно важливим є ечеїшя можливості швидкої зміни на логічному рівні специфікації умов і користування (специфікація захисту та правила доступу до ресурсу, що асться). Це вимагає наявності інтегрованих механізмів, які дозволяли б ювати контроль за коректністю використання даних, а також контролювати і до них на основі прийнятої політики безпеки і забезпечували б при цьому івість швидкої зміни правил здійснення таких операцій в процесі гування. У зв’язку з необхідністю захисту інформації в БД від апаратних чи імних збоїв, а також від некоректного чи зловмисного її використання гься поняття захисту та цілісності даних. У роботі проаналізовано специфіку розв’язок цих понять і показано, що забезпечення належного рівня захисту мації та її цілісності є найважливішими умовами ефективного ;іопування автоматизованих банків даних.

к відомо, процес проектування автоматизованих банків даних з ованими механізмами захисту та підтримки цілісності пов’язаний зі іми труднощами. Це пояснюється, зокрема, тим, що відома методологія гування нодібних об’єктів у своїй основі є неформальною. Внаслідок цього має багато недоліків, а отже, потребує подальшого розвитку та значення. Разом з тим, більш докладний аналіз показав, що задачі, пов’язані з 5кою механізмів контекстно-орієнтованого та атомарного захисту, а також імки цілісності автоматизованих банків даних, можуть бути формалізовані й овалі за допомогою автоматизованих процедур. Таким чином, наведені вище зання свідчать про акіушіьність досліджуваної в роботі проблематики.

[стою робот» є розробка удосконалених методів захисту та підтримки ості інформаційного забезпечення САПР шляхом створення методик і ітмів для автоматизованого проектування інтегрованих механізмів захисту та імки цілісності автоматизованих банків даних.

ідповідно до поставленої мети у дисертаційній роботі розв’язуються задачі 5ки та удосконалення алгоритмів і програмного забезпечення для

автоматизованого проектування:

- механізму контекстно-орієнтованого захисту;

- механізму захисту, що ґрунтується на атомарній концепції безпеї-включаючи багаторівневий захист;

- процесів управління паралельною обробкою даних із застосувать розкладів транзакцій.

Наукова новизна одержаних результатів.

1. Розроблено алгоритм автоматизованого проектування механізі контекстно-орієнтованого захисту інформації у базах даних, який л можливість здійснювати модифікацію запитів на доступ до даних в залежно< від передісторії звертань і оптимізувати експлуатаційні характеристики систеї “користувач - БД”. Відмінностями запропонованого алгоритму є можливіс контролю коректності початкового формулювання специфікації захисту, також новий підхід до здійснення ізоморфних перетворень граф-моделей Б/, метою забезпечення дотримання заданих вимог захисту та покращан експлуатаційних характеристик автоматизованих банків даних, і захищаються.

2. Удосконалено алгоритм кластеризації елементів даних БД у групи з однаковиї атрибутами захисту (атоми та молекули), особливостями якого є автоматизова реорганізація БД у відповідності з вимогами захисту, перевірка коректної вимог захисту, а також можливість реалізації атомарного захисту не лише процесі логічного проектування БД, але й в умовах експлуатації п; необхідності оперативної зміни системної специфікації захисту та каної доступу.

3. Створено узагальнену методику зведення довільних розкладів транзакцій , еквівалентної послідовної форми. Дана методика відзначається тим, і забезпечує не лише виявлення, але й ліквідацію тупикових ситуацій аналізованих розкладах для різних ступенів деталізації моделей транзакцій.

4. На основі запропонованої узагальненої методики розроблено алгори: автоматизованого проектування процесів управління паралельною обробке даних у централізованих БД на основі розкладів транзакцій з різними типа? блокувань, що забезпечує підтримку цілісності даних при їх колективної використанні. Особливостями цього алгоритму є новий метод аналі орієнтованих графів на наявність контурів, що може бути застосований багатьох задачах автоматизованого проектування, та спосіб ліквідації тупикові ситуацій при паралельному виконанні транзакцій, який дозволяє усува виникаючі конфлікти з мінімальними втратами паралелізму.

Практичне значення одержаних результатів:

- розроблено алгоритми та прикладне програмне забезпечення д автоматизованого проектування механізму захисту контекстно-залежн інформації у базах даних, а також механізму захисту, що ґрунтується ;

з

атомарній концепції безпеки, які забезпечують можливість практичної реалізації захисту даних при заданих конкретних вимогах (які можуть часто змінюватися) з усіма перевагами, що випливають з автоматизації проектувальних робіт;

- розроблено методику, алгоритми та прикладне програмне забезпечення управління процесами паралельної обробки даних, які забезпечують підтримку цілісності баз даних при колективному режимі користування, високий ступінь паралелізму виконання операцій і, таким чином, високу продуктивність системи обробки інформації у цілому;

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

Розроблені в дисертаційній роботі методи та алгоритми впроваджені у жавному підприємстві "ЛРГЕНТУМ" (м. Львів, Україна) при розробці зматизованої системи обліку дорогоцінних металів, а також в навчальному цесі при читанні спецкурсів для студентів спеціалізації “Захист інформації в гп’ютеризованих системах управління” на кафедрі “Автоматика і телемеханіка” жавного університету “Львівська Політехніка”, що підтверджено відповідними зми.

Особистий внесок здобувача. Основний зміст роботи, усі теоретичні та ктичііі розробки, висновки і рекомеїщації виконані автором особисто. У кованих працях, опублікованих в співавторстві, здобувачу належать:

5, 8] - участь в постановці задач і розробці механізмів управління безпечною обкою даних в інформаційно-обчислювальній системі; [2,4, 9, 10]-розробка [елей аналізу та проектування процедур захисту ресурсів обчислювальної геми із розподіленою обробкою даних.

Апробація результатів дисертації. Основні положення і результати ертаційної роботи доповідалися і обговорювалися на міжнародній ково-технічній конференції “Досвід розробки та застосування ладо-технологічних САПР мікроелектроніки” (Львів, 1997), міжнародній ково-технічній конференції “Сучасні проблеми засобів телекомунікації!, п’ютерної інженерії та підготовки спеціалістів” (Львів - Славсько, 1998), VI аїнсько-польській конференції “САПР в машинобудуванні - проблеми чанпя та впровадження” (Львів, 1998), міжнародній науково-технічній ференції Бгосікоеигс^зка Копісгепсіа Каико\уо-Тес1тісгпа МеЬсІу і БуБІету при1еш\уе \у Аиіотаїусе і Еіекігогесітісс Ш М8КАЕ’99 (Ченстохова - Порай, публіка Польща), міжгалузевому, міжрегіональному семінарі Наукової Ради Н України “Технічні засоби захисту інформації” (Львів, 1998), міжгалузевому, регіональному семінарі Наукової Ради НАН України “Технічні засоби захисту зрмації” (Львів, 1999).

Публікації. За результатами виконаних досліджень опубліковано 11 робіт, яких 4 - одноосібні, у т.ч. 6 наукових статей (з яких 6-у фахових виданнях

4 - матеріали і тези доповідей на конференціях.

Структура та обсяг роботи. Дисертаційна робота (загальним обсягом 2( сторінок) складається з вступу, чотирьох розділів, висновків, списку літературні джерел з 123 найменувань і додатків на 110 сторінках. Зміст роботі викладено і 158 сторінках, включаючи 43 рисунки та 7 таблиць. У додатках наведено тексі вихідних кодів розробленого програмного забезпечення та результати його роботі

ЗМІСТ РОБОТИ

У вступі наведено загальну характеристику роботи, обгрунтовано актуальність, сформульовано її мету та основні задачі досліджень, визначеі методи вирішення поставлених задач, сформульовано наукову новизну роботи ■ практичну цінність одержаних результатів, викладено короткий зміст роботи.

У першому розділі роботи наведений аналіз основних проблем проектувані автоматизованих банків даних з інтегрованими механізмами захисту інформації підтримки її цілісності, а також існуючих підходів та методів розв’язання ці проблем. В результаті проведеного аналізу обґрунтовані актуальність та виЄ основних напрямків досліджень, що є мстою дисертаційної роботи. Основ результати досліджень викладені у 2-му - 4-му розділах роботи.

Другий розділ роботи присвячений дослідженню проблем захис контекстно-залежної інформації у базах даних із застосуванням автоматизован процедур. Контекстно-залежною називають інформацію, доступ до якої залежи від передісторії звертань до бази даних. Контекстна залежність являє собою умої яка містить декілька атрибутів і / або деякий взаємозв’язок між атрибута елементів (наприклад, 3 - “запис”, Ч - “читання”, В - ’’виконання”).

Реальний механізм контекстно-орієнтованого захисту даних визначається деяким перетворенням, же змінює або видаляє певні атрибути доступу до тексту в залежності від контекстного відношення, що вказує яким способом атрибути доступу до елемента-тексту (Di) зв’язані з атрибутами Рис.1. Контекстна залежність мі доступу до елемента-контсксту (D2) (рис. 1). елементами даних БД.

Аналіз показав, що початково сформульовані контекстні залежності між елементами бази даних можуть бу представлені у вигляді орієнтованих графів з мережевою структурою. При цьо вершинами графа є елементи даних з відповідними атрибутами, а д) відображають задані контекстні залежності між елементами (рис. 2). На показано, що характерними особливостями таких орграфів є відсутність петель паралельних дуг, і це має важливе значення для їх дослідження. Однак, графи ти

іережі непридатні для розв’язання проблем контекстно-орієнтованого захисту, [ цього їх доцільно представити у вигляді ієрархічних структур.

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

Рис.2. Приклади орграфів структури баз даних з врахуванням вимог захисту.

У практичних випадках, коли БД містить десятки, сотні, або й більше :ментів, виникають проблеми як із самим процесом побудови граф-моделі БД, іховуючи його трудомісткість, так і з перевіркою її на коректність. Складність іробки механізму захисту контекстно-залежної інформації обумовлена ще й тим, він вимагає модифікації запитів у залежності від послідовності та змісту тередніх звертань.

Таким чином, основними задачами проектування механізму контекстно-єнтованого захисту є наступні:

автоматизована побудова граф-моделі БД на основі заданих контекстних залежностей між елементами даних;

автоматичне виявлення контурів у граф-моделі БД з метою корекції контекстних залежностей, сформульованих на початковому етапі проектування; автоматизація процесу декоіггуризації граф-моделі за обірунтованим критерієм з метою ліквідації можливих порушень вимог захисту;

автоматизоване визначення оптимальної послідовності та змісту запитів, а також їх модифікація в залежності від передісторії звертань з врахуванням вимог захисту.

Вказані задачі розв’язані у роботі за допомогою ізоморфних перетворень іф-моделей БД із застосуванням автоматизованих процедур. Для ізоморфних )етворень орграфів використано метод, який ґрунтується на визначенні ссимальних відстаней між орзв’язаними вершинами ірафа та розподілі їх по

рівнях ієрархічних структур. В результаті цього можуть бути побудов; лісоподібні структури двох видів: з закріпленими коренями та з закріплеп листям (рис. 3). Якщо у початковому графі контекстних залежностей конту відсутні, то побудова лісоподібних структур відбувається без ускладнень одержані структури є єдино можливими. Коли ж в орграфі с контури, то перш все необхідно виявити множину вершин, що їх утворює, а потім здійсни деконтуризацію графа шляхом видалення однієї або декількох дуг. В залежної від того, скільки і яких дуг видаляється у процесі деконтуризації, можна одержа лісоподібні структури з різним числом рівнів розподілу, які хоч і є інваріанта; початкової ормережі, але не є рівноцінними в плані реалізації вимог захис інформації.

ЗАПИТИ МНОЖИНИ ЗАПИТИ множини

Рис.З. Лісоподібні структури граф-моделі бази даних із врахуванням вимог захис 1) з закріпленими коренями; 2) з закріпленим листям.

Необхідно відзначити, що процес побудови лісоподібних структур та дослідження є досить складним і трудомістким, особливо, коли число елемент; які потребують контекстного захисту, є значним. Тому вихід з цієї ситуації поляг у формалізації та автоматизації цих процесів.

Нами розроблено алгоритм (рис.4) та відповідне програмне забезпечення, допомогою яких розв’язуються сформульовані вище зада контекстно-орієнтованого захисту.

Розподіл елементів даних но рівнях ієрархії дає можливість визначи-оптимальну послідовність та зміст запитів з метою доступу до елементів даних,

врахуванням вимог захисту, так і без них. При цьому, у випадку врахування [мог захисту послідовність та зміст запитів користувача на доступ до елементів іних повинні бути впорядкованими в тому сенсі, що запити на доступ до еменгів даних, розташованих на зовнішніх рівнях ієрархії (“корені” та ’’листя” цповідно), повинні передувати запитам на доступ до елементів даних, >зтаиюваних на внутрішніх рівнях. Перелік усіх можливих запитів та їх ймовірної >слідовності для отримання певної конкретної інформації з БД окремими іристувачами може бути оформлений у вигляді самостійного документа, який ачно полегшить їх роботу.

Рис.4. Структура алгоритму автоматизованого проектування механізму контекстно-орієнтованого захисту даних БД.

Аналіз показав, що більш доцільним можна вважати використання оподібних структур із закріпленим листям (рис. 3), оскільки листя відображає :менти даних, які не потребують захисту, і тому доступ до них повинен бути ссимальио спрощеним. У той же час, число запитів, які необхідно зробити з гою доступу' до елементів даних, визначається числом рівнів ієрархії, тому в ¡робленому алгоритмі передбачена можливість деконтуризації ормережі за шципом одночасної мінімізації числа видалених дуг та числа рівнів ієрархії ультугочої лісоподібної структури.

Мінімізація числа рівнів структури БД, а також чітка визначеність порядку та сту запитів дає можливість підвищити продуктивність СУБД, забезпечити

максимальну повноту відповіді і спростити процес фізичної реалізації БД. ГІ[ цьому полегшується також контроль за санкціонованістю використання ба: даних.

Таким чином, результати, одержані у другому розділі роботи, підтверджую! що основні проблеми, пов’язані з проектуванням механізму захисту контексти залежної інформації, можуть бути успішно розв’язані за допомого автоматизованих процедур.

У третьому розділі роботи досліджуються проблеми захисту баз даних, які ґрунтується на атомарній концепції безпеки, у тому числі й багаторівнево: захисту.

Один із найпростіших способів перешкодити користувачеві БД у здійснен несанкціонованого доступу до деяких даних — приховати сам факт існування таю даних у БД тобто будь-який користувач повинен знати про існування лише ті частини інформації, яка необхідна для виконання тільки його безпосередн завдань.

Як відомо, завершальним етапом логічного проектування БД є розробка структурної схеми. На додаток до схеми розробляються описи підмножин БД, я називаються підехемами. Підсхеми відображають представлення окремі користувачів про БД і можуть бути використані ж засоби обмеження достуї користувачів лише до тієї її частини, що відповідає його профілю достуг Найпростішою формою фіксації прав доступу є таблиця або матриця доступу.

З огляду на проблеми захисту даних, продуктивність СУБД визначаєть ефективністю запобігання неавторизованому доступу до інформації, у тому числі несанкціонованому перегляду. Тому в процесі проектування сисп автоматизованої обробки даних потрібно брати до уваги необхідність забезпечені прямого чи опосередкованого доступу тільки до даних, цільової обробки які вимагає конкретніш запит (рис. 5).

Для розв’язання вказаної проблеми була запропонована так звана атомар, концепція безпеки. Відповідно до цієї концепції передбачається логічний розподі компонентів БД і виділення мінімальної одиниці специфікації, яку запропоноваї називати атомом захисту (рис. 6). Атом захисту об’єднує елементи, жі маю деяку спільну властивість, виражену через їх атрибути у вигляді певної логічн умови - канону. При цьому на основі профілю доступу користувача СУБД мо> забезпечити йому доступ до дозволеної частини інформації без попередньо аналізу на санкціонованість груп елементів БД, що знаходяться в інших атомах.

Нехай, наприклад, БД містить набір елементів даних [Б^АьАз), В2(АЬА Оз(А(), В4(Аі,Аз), 05(Аі,Аз,А4), Об(А4), В7(А2), В8(Л1,А3,А1), Ог/Ад), Ою(Аі,А Оц(Аі,Аз), Б^АьАг), О^А^), Ві4(Лі,Л3), Оі5(Аі,А3,А4), Оіб(А(), Оп(А

Оі8(Аі,Аз,А4), ІЗі^АД В2о(Аі,А2), 02і(А|,А3), О^АьАг), 023(А4), В^А^А 025(Аі,Аз,А4), ОгбСАД 027(А2), В28(Аі,А3,А4), Ог^Аі), 03о(Аі,А2)],

"ИД - сукупність атрибутів, що характеризують означені елементи даних шриклад, “дозвіл на читання”, “дозвіл на запис”, тощо), а профіль доступу для ного користувача описується наступним логічним виразом:

0 = А2 л ((Д л Д,) V (А3 л Д,)).

(1)

де А, - вимога наявності, а А, - відповідно, відсутності певного атрибуту в исі елемента даних, що перевіряється на доступність у даному профілі доступу.

А- Аз «і Аі Аі 01 Аі 04 Аі А: 05 Аі А: Аі 0« А. Аі Аг А- Аз А, 69 А« ОК Аі А-

Аі Аз 012 А, Аз аіз Аі 01* Аі Аз 01» Аі Аз А. Рів А. »17 Аі Аі 013 Аі Аі А, 019 А« 02£ А- Аі

А- Аз Аі Аї »а А, ... »29 Аі А:- Аі ом А« 021 Аі Аг 03 А- Аз А« 0Э А. »3 А\ А:

1)

с. 5. Структура відношень між елементами бази даних, що ілюструють проблему несанкціонованого перегляду:

1) модель бази даних; 2) граф-модель БД.

Нехай, також, в системі необхідно виділити атоми (1 - 4) захисту, що іактеризуються наступними канонами (К,):

К, А^ л А2 а А^ л ^4,

К2 • А1 Л ^2 ^ ^3 ^ ^4 *

К3 *. /\1 д А2 а А3 л А4

/^4 • А.| А /^2 ^ ^3 ^ ^4

Рис. 6. Структура бази даних з розподілом елементів даних по атомах захисту. Тоді в результаті аналізу запиту користувача

(У = Л2л((А1лД,МД,лА4)). (3)

буде визначено, що атомі містить елементи [Di,D4,Dii,Di4, D2i,D24 атом 2 - елементи [D2, D7, D10, D12, Di7, D20, D22, D27, D30], атом 3 - елемент [D3, Dé, Dg, D13, Dj6, D]9, D23, D26, D29], атом 4 - елементи [D5, Dg, D15, D^, D25, D2g прігчому атоми 1,2 і 4 підпадають під специфікацію запиту' користувача (3). Одна] внаслідок того, що канон атому 2 (2) не відповідає заданому профілю доступу (1 користувачеві буде повідомлено лише про існування елементі [D], D4, D|i,Di4, D2i, D24] та [D5, Ds, Di5, Dig, D25, D2s].

Проте, у відомих джерелах атомарний механізм захисту описаний лише її

щептуальному рівні, іцо унеможливлює його практичну реалізацію. Крім того, е при кількох десятках елементів БД, що характеризуються певними наборами іибутів, здійснити процес реорганізації БД з метою виділення атомів захисту с фактично неможливо у зв’язку з його складністю та трудомісткістю. Додаткові 'днощі виникають також при необхідності зміни системної специфікації захисту ' або канонів.

З метою забезпечення можливості практичної реалізації механізму атомарного исту нами розроблено алгоритм, що дозволяє автоматизувати процес його )екгувашш при різних початкових вимогах (рис. 7).

:с. 7. Структура алгоритму автоматизованого проектування механізму захисту даних БД на основі атомарної концепції безпеки.

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

У багатьох випадках необхідна диференціація засобів захисту в залежності від ы секретності окремих елементів даних. Іншими словами, для організації рігання інформації з різними грифами секретності актуальною є проблема аторівневого захисту. Оскільки елементи, що належать до одного атома, іагають однакових засобів захисту, їх необхідно віднести до одного рівня

класифікації, тобто самі рівні класифікації можуть розглядатися як атрибут захисту. Якщо сегменти иідфаіілів, які містять елементи з різними рівням класифікації, попарно не перетинаються, тобто не мають спільних елементів, т доступ до елементів одного рівня класифікації не буде пов’язаний з доступом у. елементів, що належать до інших рівнів. Об’єднуючи атоми захисту, можі отримати молекулу захисту. Очевидно, що цей процес також потреб) алгоритмізації і реалізований нами як складова частина загального алгоритм (рис. 7). Відповідний приклад наведений в роботі.

Слід відзначити, що розроблений алгоритм дає можливість здійснюваї реструктуризацію БД не лише у процесі проектування її логічної та фізичні структури, але й у процесі експлуатації, коли виникає потреба оперативної зміг логічних виразів системної специфікації захисту або канонів.

Розподіл елементів БД на атоми та молекули захисту приводить до ієрарх моделей БД, що створює ряд переваг, основною з яких є можливість розділеного і фізичному рівні зберігання груп елементів (атомів чи молекул) у зовнішн пристроях пам’яті. При цьому не лише блокуються обхідні шляхи доступу, але підвшцується продуктивність систем обробки інформації у цілому.

Четиертий розділ роботи присвячений автоматизації проектування процес управління паралельною обробкою з метою підтримки цілісності БД. Зада1 управління процесами паралельної обробки є складовою загальної пробле\: підтримки цілісності БД і с актуальною при проектуванні СУБД спеціальної призначення. Основна мета при цьому полягає у забезпеченні цілісності БД • досягненні високого ступеня паралелізму виконання операцій з даними при малі затратах на організацію процесів паралельної обробки.

Як відомо, найбільш поширений і надійний метод управління паралельно обробкою пов’язаний з поняттями транзакція та розклад транзащій (або граф запуску). Управління цілісністю БД повинне забезпечувати підтримку її узгодженому стані при колективному режимі роботи з паралельнії маніпулюванням даними і є важливим навіть у випадку роботи системи з одни користувачем. У багатокористувацьких системах виконання транзакцій мох починатися, перериватися та поновлюватися у довільні моменти часу. З поіши користувача це виглядає так, ніби множина транзакцій виконується паралельно, а: істинний паралелізм можливий дише тоді, коли обчислювальна система об’єдн; декілька центральних процесорів. Однак, у будь-якому випадку неприпустимим порушення роботи однієї транзакції іншою.

Парачельне виконання декількох транзакцій є коректним, якщо і тільки якп їх спільний результат буде таким самим, як і при їх виконанні послідовно деякому порядку. Тобто узгоджені стани бази даних можна забезпечити допомогою послідовних, або такт, що можуть бути зведеними до послідовні, розкладів.

Монопольне використання поля запису в процесі роботи СУБД забезпечуєть

допомогою блокувань. Для цього БД розбивається на частини, тобто елементи, можна блокувати в процесі обробки даних. Суттєвим при цьому є вибір виду та ¡міру цих елементів з метою досягнення певного компромісу між степенем залелізму та затратами ресурсів системи на реалізацію блокувань.

Серйозною проблемою при )алельній обробці є також так звані пики, тобто взаслюблокування, коли іа із пари транзакцій, що перебувають стадії виконання, блокує елементи піх, що їх потребує інша для ершення своєї роботи, і навпаки [с. 8).

Як правило, множина усіх транзакцій, які можуть коли-небудь викопуватися )алельно, наперед невідома, отже вимушена вимога полягає у тому, щоб усі інзакції відповідали двофазному протоколу.

Процеси паралельної обробки, що стосуються операцій над об'єктами бази мх, можуть відрізнятися типом застосовуваних блокувань і відповідно різною іадністю проектування розкладів транзакцій.

Розробка розкладів транзакцій, що можуть бути зведені до послідовних, є :ить складною проблемою проектування СУБД. Звідси випливає необхідність рмалізації задач паралельної обробки, розробки відповідних алгоритмів і эгрампого забезпечення та розв’язання цих задач за допомогою ЕОМ.

З цією метою нами запропоновано нову узагальнену методику зведення і'иіьннх розкладів транзакцій до еквівалентної послідовної форми, і па її основі роблено алгоритм автоматизованого проектування еквівалентних послідовних ; клад і в з блокуваннями типу “блокування-розблокупання” та “блокування для :ання та запису” (рис. 9).

Основною логічною умовою забезпечення коректності паралельної обробки іих у централізованих БД є динамічне формування та підтримка еквівалентного шідовного розкладу операцій у рамках змінного набору операцій активних язакцій {фрейму активних транзащій), вміст якого змінюється під час роботи теми. Дотримання цієї умови можна забезпечити виконанням наступних дій: відтворення поточної структури фрейму на орієнтованому графі (граф очікувань);

детектування в побудованому графі очікувань всіх контурів, наявність яких означає присутність конфліктів в аналізованому фреймі;

визначення набору вершин, що призводять до появи контурів в графі очікувань та вибір з цього набору вершини-кандидата для видалення з графа з метою його повної декоіпуризації (ця вершина відповідає так званій, транзакгіії-жертві, скасування якої призведе до усунення всіх конфліктних ситуацій і вимагатиме найменших вілрат ресурсів системи); зауважимо, що таких вершин може бути

Користувач

Очікує Використовується Очікує Запис БД

Рис. 8. Взаемоблокування транзакцій.

декілька в залежності від структури графа очікувань;

Рис. 9. Структура алгоритму автоматизованого проектування еквівалентних послідовних розкладів транзакцій.

- видалення вершшш-кандидата з графа очікувань (тобто, скасувані транзакції-жертви, що призведе до зміни вмісту аналізованого фрейму);

- реструктуризація вмісту аналізованого фрейму за результатами топологічно сортування графа очікувань з мстою отримання еквівалентного послідовно розкладу.

Запропонована методика є узагальненою в тому розумінні, що спосої формування еквівалентного послідовного розкладу операцій для розкладів з різні ступенем деталізації моделей транзакцій є аналогічними і відрізняються лш

юцедурого побудови графу очікувань для аналізованого фрейму.

У алгоритмі, який реалізує ідо методику, передбачено автоматизовані юцедури побудови орієнтованих графів очікування, аналізу цих графів на явність контурів і, у випадку їх відсутності, здійснення топологічного сортування афа, в результаті чого отримується еквівалентний послідовний розклад анзакцій. Поява контурів у ірафі очікувань є ознакою виникнення тупикових туацій. Тому в алгоритмі передбачена не тільки можливість виявлення тупиків, е й ліквідація конфліктів. Це здійснюється за допомогою оригінальних процедур,

і дозволяють проаналізувати граф очікувань на наявність контурів і ліквідувати нфлікти з мінімальними втратами паралелізму

ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ ТА ВИСНОВКИ

Розроблено алгоритм та програмне забезпечення для автоматизованого проектування механізму захисту контекстно-залежної інформації у базах даних. Даний алгоритм ґрунтується на ізоморфних перетвореннях граф-моделей БД, і відрізняється тим, що забезпечує формалізацію вимог захисту, перевірку їх на коректність, оптимізацію структурних перетворень та визначення необхідної послідовності й змісту запитів до даних, в залежності від передісторії звертань. Коректність і ефективність алгоритму підтверджена прикладами та результатами розв’язання практичних задач.

Розроблено алгоритм та програмне забезпечення для автоматизованого проектування механізму захисту інформації у базах даних на основі атомарної концепції безпеки, що відзначається можливістю здійснення реорганізації БД у відповідності з заданими логічними умовами захисту як при проектуванні БД, так і під час її експлуатації. При цьому розв'язується також проблема багаторівневого захисту даних з різними категоріями секретності. Реалізація атомарної концепції захисту та її переваги ілюструються тестовими задачами. Створено узагальнену методику зведення довільних розкладів транзакцій до еквівалентної послідовної форми, а також алгоритм та програмне забезпеченім, відмінностями яких є те, що вони дають змогу підтримувати цілісність централізованих БД завдяки управлінню процесами паралельної обробки з різними типами блокувань транзакцій. При цьому забезпечується не лише виявлення тупикових ситуацій, але й ліквідація конфліктів з мінімальними втратами паралелізму. Даний алгоритм може бути покладений в основу роботи планувальника транзакцій при проектуванні СУБД спеціального призначення. Практичне застосування розроблених алгоритмів та відповідного програмного забезпечення крім розв’язання основних задач - захисту та підтримки цілісності інформації у базах даних - забезпечує також підвищення ефективності інформаційного забезпечення САПР; одночасно при ньому реалізуються усі перевалі, що випливають з автоматизації процесів проектування.

СПИСОК ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Лобур М.В., КовелаС.1. Електронний зв’язок: проблема конфіденціиност інформації. Вісник Державного університету “Львівська Політехніка’ Комп’ютерна інженерія та інформаційні технології, -1998, №327, - с.279 - 285.

2. ЛобурМ.В., КовелаС.1. Деякі особливості автоматизації проектне конструкторських робіт в контексті розподіленого використання проектної базі Вісник Державного університету “Львівська Політехніка”. Комп’ютери інженерія та інформаційні технології, -1998, №349, - с.141 -144.

3. Лобур М.В., КовелаС.І. До питання про захист інформаційних ресурсі обчислювальної системи від несанкціонованого доступу. Вісник Державног університету “Львівська Політехніка”. Комп’ютерна інженерія та інформаціш технології, - 1999, №370, - с.90 - 93.

4. ЛобурМ.В., КовелаС.І. Дослідження проблеми організації доступу д інформації баз даних на основі атомарної концепції безпеки. Вісник Державног університету “Львівська Політехніка”. Комп’ютерна інженерія та інформанті технології, №380, - 1999, - с.87 - 93.

5. Ковсла С.І. Досліджеіпія проблем контекстно-орієнтованого захисту інформац в базах даних. Вісник Державного університету “Львівська Політехніка Комп’ютерна інженерія та інформаційні технології, №386, - 1999, - с.79 - 84.

6. Ковела С.І., “Підтримка цілісності інформації автоматизованих банків даних умовах паралельної обробки”. Збірник наукових праць Української Академ друкарства “Комп’ютерні технології друкарства”, - 1999, №3, - с.114 -123.

7. КовелаС.І. Системи шифрування даних в інформаційних мережах: загалы

принципи функціонування: Альманах бсзопасност:

Информационно-аналитический сборник. Львовское агентство экономическс безопасности “Галактика”, 1997, с.32..

8. Лобур М.В., Ковсла С.І. Інформаційні мережі: сучасні методи криптографія» обробки даних. Тез. доп. Міжнародна науково-технічна конференція “Досв розробки та застосування приладо-технологічних САПР мікроелектроніки Львів, 1997, с.106.

9. Лобур М.В., Ковела С.І. Стратегія побудови захищеної обчислювальної систе.\ з розподіленою обробкою даних. Тези доп. на міжнародній науково-технічн конференції “Сучасні проблеми засобів телекомунікацій, комп’ютери інженерії та підготовки спеціалістів”, (Львів, 1998), с.92.

10. ЛобурМ.В., КовелаС.І. Деякі особливості автоматизації проекти конструкторських робіт в контексті розподіленого використання проектної баз Тези доп. на VI українсько-польській конференції “САПР в машинобудуванн проблеми навчання та впровадження”, (Львів, 1998), с.119.

11. Kovela S. Referring the technical aspect of information system resource protectio Rep. Srodkoeuropejska Konferencja Naukowo-Techniczna Metody і Systen Komputerowe w Automatyce і Elcktrotechnice III MSKAE’99, Czestochowa - Pori 1999, p.90.

АНОТАЦІЯ

Ковела С.І. Методи захисту та підтримки цілісності інформаційного іезиечеиіш САПР. - Рукопис.

Дисертація на здобугтя наукового ступеня кандидата технічних наук за щіальністю 05.13.12 - Автоматизація проектувальних робіт. - Державний верситет “Львівська Політехніка”, Львів, 2000.

Розроблено оригінальні алгоритми для автоматизованого проектування нанізму коитекстно-орієнтованого захисту та механізму захисту інформації на юві атомарної концепції безпеки, що дають можливість змінювати логічну іуктуру баз даних у відповідності з заданими логічними умовами захисту ж в зцесі проектування автоматизованих банків даних, так і під час їх експлуатації, а ;ож спрощують процес контролю санкціонованості їх використання. Створено ігальнепу методику і алгоритм управління паралельною обробкою даних, що іезпечують підтримку цілісності централізованих баз даних при колективному мімі їх використання з мінімальними втратами паралелізму виконання операцій яхом зведення довільних розкладів транзакцій з різними типами блокувань до »валентної послідовної форми.

На основі запропонованої методики та алгоритмів розроблено пакет окладного програмного забезпечення, подано результати розв'язку тестових (ач з його застосуванням. Алгоритми впроваджено у спеціалізованому зграйному комплексі та у навчальному процесі.

Ключові слова: контекстна залежність, граф-модель, лісоподібна струкгура, морфне перетворення, атом захисту, молекула захисту, цілісність, транзакція, ?івалентний послідовний розклад.

АННОТАЦИЯ

Ковсла С.И. Методы защиты и поддержки целостности

формационного обеспечения САПР. - Рукопись.

Диссертация на соискание учёной степени кандидата технических наук по щиальности 05.13.12 - Автоматизация проектных работ. - Государственный иверситст “Львівська Політехніка”, Львов, 2000.

Разработаны оригинальные алгоритмы для автоматизированного

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

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

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

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

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

ABSTRACT

Kovela S.I. Protection and integrity support techniques for CAD informatio facilities. - Manuscript.

Thesis for the Degree of Candidate of Technical Science in speciality 05.13.12 Automation of design operations. - State university “Lviv Polytechnic”, Lviv, 2000.

The thesis deals with engineering of algorithms for automated design of protcctic and integrity support mechanisms for CAD information facilities. The methods of da protection and integrity support in automated data banks (ADB) are considered. It shown that ensuring appropriate level of information security and integrity is of vit importance for efficient operation of automated data bank. This requires creation < integrated mechanisms, which would monitor data for correct utilization and contr acccss to them basing on given security specification. These mechanisms would als allow for fast alteration of data monitoring and access control modes during the desi£ process. Another topic closely related to database (DB) information protection is ensurir its integrity.

There arc two kinds of security mechanisms considered in the thesis. These arc tl context-oriented protection mechanism and the mechanism of protection, which is base on atomic security concept.

Main objectives of the context-oriented protection mechanism are formulated wi the solution provided through application of isomorphic conversions to DB graph-mode in a framework of automated procedures. At that it is demonstrated that given conte dependencies can be represented in a form of oriented graphs with network structu featuring loop and parallel edge absence. The isomorphic conversions of DB grap; models with formation of tree-like structures are used in order to achieve the specific objectives. It is proposed to cany out the isomorphic conversions according to criterion i simultaneous minimization of the removed edge count and the hierarchy level count' the resultant tree-like structures. This allows for correction of given context dependenci if needed and for definition of optimal sequence and contents of user queries adjusts according to data protection considerations. This also boosts overall DBMS performam and simplifies implementation of DB logical structure.

The algorithm which implements main context-oriented protection functions in

nework of automated procedures is designed in the thesis.

The previously proposed atomic security concept, which stipulates logical itioning of DB components and isolation of atoms of protection featuring some imon attributes represented in a form of certain logical condition (canon), has gained her advancement in the thesis. An algorithm, which allows for development jmation of atomic security mechanism with various starting security requirements, is eloped to provide practical basis for implementation of the above mechanism. It :ifically provides for automatic checkup of protection canons for conformity with :n system security specification and allows for DB restructuring in accordance with irity requirements both during DB design and operation whenever rapid alteration of cal conditions of protection is needed. An automated procedure of isolating atoms molecules of protection, which allows for securing data with different levels of ccy, is also developed (multilevel protection).

Generalized technique for automated design of control processes of parallel data :essing is proposed in the thesis. The primaty objective of the technique proposed is iring integrity in centralized DB basing on transaction schedule control realized for ous types of blocking. At that the integrity of DB data is guaranteed and high level of illelism is attained at low blocking arrangement expense. The technique stipulates Ability of reducing arbitrary transaction schedules to equivalent serial ones and ides not only deadlock detection but also conflict resolution.

Basing on the above technique the correspondent algorithm is developed. The >osed algorithm allows for automated design of equivalent serial transaction schedules tinimal loss of parallelism of operation and can be used as a backbone in design of cated DBMS schedulers.

Correctness of the algorithms developed is justified with the results of test and tical task solutions.

Key words: context-sensitive dependence, graph-model, tree-like structure, lorphic conversion, atom of protection, molecule of protection, integrity, transaction, valent serializable schedule.