122 Комп’ютерні науки

Permanent URI for this collection

https://ekmair.ukma.edu.ua/handle/123456789/35525

Освітньо-наукова програма: Комп’ютерні науки

Browse

Now showing 1 - 5 of 5

Методи та засоби побудови автоматизованої освітньої програмної системи для кібербезпеки (кіберполігону) : дисертація на здобуття наукового ступеня доктора філософії
(2026) Бабич, Трохим; Глибовець, Андрій
Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 122 "Комп’ютерні науки" (12 – Інформаційні технології). – Національний університет "Києво-Могилянська академія", Київ, 2026. У дисертаційній роботі розв’язано важливу наукову задачу побудови автоматизованих освітніх програмних систем для практико-орієнтованого навчання у предметних областях з підвищеними вимогами до ізоляції середовищ виконання. Особливим випадком таких систем виступає кіберполігон як автоматизоване освітнє програмне середовище, що забезпечує автоматизоване розгортання ізольованих лабораторних завдань з кібербезпеки і автоматизовану перевірку коректності їх виконання. Актуальність роботи зумовлена кадровим розривом у галузі кібербезпеки, що зафіксований ENISA і ISC2 і перевищує чотири мільйони фахівців у глобальному масштабі і близько трьохсот тисяч позицій тільки у країнах Європейського Союзу. Класична академічна модель підготовки структурно не спроможна забезпечити необхідний приріст кваліфікованих фахівців за прийнятний час; для України ця проблема додатково загострилася у зв’язку з повномасштабним вторгненням Російської Федерації. Дисертаційна робота присвячена розробленню моделей, методів і архітектурних рішень для побудови такого класу програмних систем з гарантованими властивостями цілісності моделі знань, безпеки конкурентного розгортання, поліморфної оркестрації гетерогенних виконавчих середовищ і доведеної автоматизованої перевірки коректності виконання навчальних завдань. Розглянуто архітектурні рішення академічних кіберполігонів (DETER, CRATE, KYPO, CyRIS, SecGen), комерційних платформ (Hack The Box, TryHackMe, RangeForce) і гібридних академічно-комерційних платформ (UWF Cyber Range). Встановлено, що ні академічні, ні комерційні рішення не пропонують інтегрованої архітектури з композиційними інваріантами, яка б одночасно поєднувала формалізовану модель каталога компетентностей з перевірюваними інваріантами, поліморфну агентську оркестрацію і автоматизовану перевірку коректності виконання навчальних завдань. Систематизовано термінологію предметної області з акцентом на чіткому розмежуванні понять верифікації (формальне математичне доведення) і перевірки коректності (експериментальне порівняння), сервісу блокувань через Redis і класичного розподіленого взаємного виключення Lamport-стилю, програмної системи як абстрактного класу і програмної платформи Colo як конкретного артефакту реалізації. Сформовано модель каталога компетентностей як типізований орієнтований граф з трьома інваріантами (повноти покриття, ациклічності передумов і замикання передумов) над таксономіями NICE Workforce Framework і MITRE ATT&CK, з’єднаними через шар лабораторних завдань. Інваріанти формалізовано як предикати першого порядку, що перевіряються на рівні схеми та завантаження каталога. Доведено теорему про властивості цільового профілю за інваріантами каталога (Теорема 3.1), яка стверджує, що цільовий профіль робочої ролі NICE є непорожнім, замкненим за транзитивним замиканням передумов і зберігає порядок покриття за умов виконання усіх трьох інваріантів. Сформульовано задачу мінімального покриття бракуючих компетентностей (MCCP) як варіант задачі покриття множин з обмеженнями типізованого графа. Доведено NP-важкість задачі. Запропоновано жадібний евристичний алгоритм поліноміальної складності 𝑂(|𝑇|⋅|𝑅|⋅𝑑𝑚𝑎𝑥) з доведеною верхньою межею якості наближення 𝐻(|𝑅|), де 𝐻 - гармонійна функція. Розроблено метод стисненого інверсного індексу на основі структури даних RoaringBitmap для масштабованого зіставлення профілів компетентностей. Доведено теорему про складність операцій композиції 𝑂(𝐵+𝐴), де 𝐴 - сумарна кількість верхньорівневих ключів двох бітмапів, 𝐵 - сума розмірів контейнерів під спільними ключами. Розроблено поліморфний агентський протокол для гетерогенних виконавчих середовищ (контейнерних Docker і віртуальних машинних QEMU/KVM) через єдиний REST API і спільний абстрактний інтерфейс драйвера, з адаптивним автоматом станів активності IDLE/ACTIVE/FAST. Розв’язано задачу безпечного конкурентного розгортання ізольованих середовищ через комбінацію сервісу блокувань на основі атомарної операції SET NX у Redis (за паттернами Chubby і ZooKeeper, з індивідуальним ключем блокування) і ACID-транзакції бази даних з блокуванням рядка сесії розгортання LabRun через SELECT FOR UPDATE. Доведено теорему (Теорема 4.1) про збереження інваріанта квоти при паралельному розгортанні, яка гарантує, що для будь-якого користувача у будь-який момент часу кількість активних сесій не перевищує визначену квоту. Розроблено протокол поетапного оновлення зі збереженням стану (англ. stateful canary deployment) для довготривалих ізольованих навчальних сесій зі спільним станом у реляційній і кеш-базах даних. Доведено теорему (Теорема 4.2) про збереження активних сесій під час оновлення програмної системи у нормальному режимі без покладання на маршрутизацію з прив’язкою сесій через клієнтські cookie. Розроблено архітектуру програмної платформи Colo як інтегрованої реалізації запропонованих моделей і методів. Платформа складається приблизно з 70 тисяч рядків програмного коду на мові Python з застосуванням фреймворку Django, 26 тисяч рядків JavaScript і 13 тисяч рядків HTML-шаблонів. Реалізовано 106 шаблонів лабораторних завдань і сімейство протокольно повних файлів remote_solver.py для автоматизованої перевірки коректності виконання. Розроблено формалізовану мову опису лабораторних завдань як предметно-орієнтовану мову (DSL) з валідацією через JSON-схему і детермінованою генерацією ключів на основі SHA-256 із індивідуальним для пари (user,lab) початковим значенням (seed), ключованим серверним секретним ключем через HMAC-SHA256 (що забезпечує криптографічну непередбачуваність ключа без зберігання у БД); той самий механізм підтримує два режими відповіді - CTF-флаг або змістовну відповідь (індикатор компрометації, поле SIEM, класифікаційний вердикт) з анти-чіт-вплетенням лише голого значення. Створено SDK з п’ятьма категоріями генераторів часу виконання (crypto, forensics, stego, binary, network) для рандомізації завдань. Реалізовано повноцінну інтеграцію з системами управління навчанням через стандарт LTI 1.3 з підтримкою Deep Linking, Assignment-Grade Service і Names and Roles Provisioning Service. Експериментально перевірено коректність запропонованих рішень. Метрики продуктивності у контрольованому режимі теплого кешу (образ присутній у локальному кеші, вимірювання на dev-середовищі): медіана часу розгортання контейнерних завдань - 4,2 секунди, віртуальних машинних - 3,0 секунди швидким NBD-шляхом (загальна медіана VM-розгортань 86 секунд через бімодальний розподіл, §5.6.1; завдяки механізму NBD-ін’єкції, що дозволяє ін’єктувати ключі-флаги у файлову систему образу до запуску гостьової операційної системи); у режимі холодного старту (з підтягуванням образу з реєстру) медіана розгортання контейнерних завдань - близько 77 секунд (§5.6.1). Стрес-тест безпеки конкурентного розгортання з 100 паралельних запитів від одного користувача з квотою 1 підтверджує теоретичну гарантію: рівно одна сесія створилася, 99 - відхилено з очікуваною помилкою. У 47 операціях розгортання за період експлуатації лютий-травень 2026 жодна активна сесія не була втрачена через перемикання версій (95-відсоткова довірча межа ймовірності втрати - 7,6 % на одну операцію за інтервалом Уілсона). Перевірка коректності виконання remote_solver.py показала 100 % успішність відтворення сценаріїв розв’язання для завдань з реалізованим remote_solver. Практичне значення одержаних результатів. Платформу Colo впроваджено у навчальний процес бакалаврської програми з кібербезпеки факультету інформатики Національного університету "Києво-Могилянська академія" і у програму перенавчання ветеранів повномасштабного російського вторгнення компанії Sheriff Company; практичну підготовку, підтверджену актами впровадження (Додаток Б), пройшли 66 здобувачів НаУКМА за 2025-2026 навчальний рік і 36 ветеранів Sheriff Company - разом 102 особи, а у версії V2 платформи станом на 2026-05-20 зафіксовано 4 042 розгортання ізольованих середовищ. Формалізована мова опису лабораторних завдань і SDK уможливлюють додавання нових завдань незалежними авторами з автоматизованою перевіркою якості їх виконання. Перспективними напрямами подальших досліджень є: формальне дослідження стійкості моделі компетентностей до оновлень редакцій таксономій NICE і MITRE ATT&CK з автоматичним переносом профілів засвоєних компетентностей здобувачів при зміні структури каталога; адаптація запропонованих моделей і методів до суміжних напрямів кібербезпекової освіти (безпека промислових систем керування ICS/SCADA, безпека Інтернету речей, безпека хмарних інфраструктур, цифрова форензика); розширення каталога лабораторних завдань до промислових масштабів (500-1000 шаблонів) і дослідження поведінки MCCP-розв’язувача у нових режимах розрідженості каталога.
Автоматизований аналіз та візуалізація в доповненій реальності архітектури програмних модулів для виявлення антипатернів : дисертація на здобуття наукового ступеня доктора філософії
(2026) Франків, Олександр; Глибовець, Микола
Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 122 "Комп’ютерні науки" (12 — Інформаційні технології). — Національний університет "Києво-Могилянська академія", Київ, 2026. Дисертаційна робота присвячена розв’язанню актуальної науково-прикладної задачі аналізу архітектури програмного забезпечення на основі автоматизованої побудови графової моделі програмного модуля та її подальшої візуалізації. Основною метою роботи є розроблення підходу, який дозволяє формалізувати структуру програмної системи, виконувати аналіз її архітектури та виявляти потенційні проблеми проєктування виключно на основі вихідного коду без необхідності використання додаткової документації, UML-діаграм або ручного опису архітектури. На сьогодні одним із важливих викликів у галузі розроблення програмного забезпечення є забезпечення належної якості програмних систем та підтримка їх архітектурної цілісності в процесі розвитку проєкту. Незважаючи на значну кількість наявних засобів автоматизованого аналізу програмного коду, більшість із них зосереджені переважно на виявленні локальних синтаксичних або семантичних помилок. Водночас аналіз загальної структури програмної системи, взаємодії її компонентів та оцінювання архітектурних рішень часто залишаються складними задачами, що потребують значних ручних зусиль з боку розробників. Додатковою проблемою є обмежені можливості наявних інструментів щодо представлення результатів аналізу у формі, зручній для сприйняття людиною. У складних програмних системах текстові звіти або набори окремих метрик нерідко є недостатніми для формування цілісного уявлення про структуру архітектури та локалізацію потенційних проблем. У дисертації проведено аналіз сучасних підходів до оцінювання архітектури програмного забезпечення, зокрема методів статичного аналізу коду, використання програмних метрик, засобів виявлення архітектурних вад, а також методів візуального представлення програмних систем. Показано, що існуючі підходи часто розглядають окремі характеристики програмного забезпечення ізольовано та недостатньо враховують глобальну структуру залежностей між компонентами системи. Встановлено, що традиційні метрики зв’язності, згуртованості або складності є корисними для оцінювання окремих фрагментів програмного коду, однак не забезпечують достатнього рівня наочності для аналізу складних архітектурних взаємозв’язків. Запропоновано підхід до представлення архітектури програмного забезпечення у вигляді орієнтованого зваженого графа. У межах запропонованої моделі вершини графа відповідають структурним елементам програмної системи, зокрема типам даних, полям та методам, а ребра — різним видам залежностей між ними. Модель враховує як декларативні зв’язки, такі як належність або наслідування, так і поведінкові взаємодії, зокрема виклики методів, використання типів та доступ до полів. Використання ваг ребер дозволяє відобразити інтенсивність взаємодій між компонентами системи та забезпечує можливість подальшого аналізу структури програмного забезпечення. Показано, що використання графової моделі дозволяє перейти від текстового представлення вихідного коду до формалізованої структури, придатної для алгоритмічної обробки, аналізу та візуалізації. На відміну від спрощених моделей залежностей, запропонований підхід враховує напрям взаємодії між компонентами та дозволяє аналізувати структуру системи на різних рівнях деталізації. Запропонована модель є достатньо універсальною для адаптації до різних мов програмування. У роботі розроблено методи автоматизованого аналізу архітектури програмного забезпечення на основі дослідження структури графа. Зокрема, запропоновано підходи до виявлення потенційних архітектурних вад, пов’язаних із порушенням зв’язності, згуртованості компонентів та наявністю циклічних залежностей. Аналіз виконується без використання додаткової інформації про програмну систему та базується виключно на структурі побудованої графової моделі. У роботі обґрунтовано використання просторового розміщення вузлів графа та особливості локальної структури залежностей для визначення потенційних проблем архітектури програмного забезпечення. Зокрема, надмірна концентрація зв’язків, ізольовані групи компонентів або аномально велика кількість взаємодій між окремими елементами можуть свідчити про порушення принципів проєктування. Запропонований підхід дозволяє локалізувати проблемні області програмного коду та спростити подальший процес аналізу й рефакторингу програмної системи. Окрему увагу приділено задачі візуалізації графової моделі архітектури програмного забезпечення. У дисертації розглянуто використання просторового представлення графа як засобу підвищення наочності та зменшення когнітивного навантаження під час аналізу складних залежностей між компонентами програмної системи. Для побудови візуального представлення використано силовий алгоритм розміщення графа, що моделює вершини як систему взаємодіючих частинок. Такий підхід дозволяє автоматично формувати естетично прийнятні конфігурації графа, придатні для подальшого аналізу користувачем. У роботі ґрунтовно досліджена можливість застосування методів машинного навчання для оптимізації процесу побудови візуального представлення графової моделі. Зокрема, розглянуто використання графових нейронних мереж як допоміжного інструменту покращення початкового розміщення вузлів графа та зменшення обчислювальної складності класичних силових алгоритмів. Запропонований комбінований підхід дозволяє підвищити швидкодію побудови візуалізації без суттєвого погіршення її естетичних характеристик та читабельності. Показано, що використання методів машинного навчання не може повністю замінити класичні алгоритми візуалізації, а виконує роль допоміжного інструменту оптимізації. Поєднання графових нейронних мереж із силовими алгоритмами дозволяє враховувати структурні особливості графа та забезпечує адаптивність підходу до різних типів програмних систем. Практичним результатом дисертаційної роботи є розроблення програмного комплексу A.D.A.R. (Architecture Displayer in Augmented Reality), призначеного для автоматизованої генерації, аналізу та візуалізації архітектури програмного забезпечення. Розроблена система виконує побудову графової моделі програмного модуля, підтримує аналіз архітектурних залежностей та дозволяє відображати структуру програмної системи у тривимірному просторі. Використання просторової візуалізації та засобів доповненої реальності дозволяє спростити сприйняття складних залежностей між компонентами програмного забезпечення на інтуїтивному рівні. Запропонований підхід може бути використаний у задачах аналізу якості програмного забезпечення, виявлення архітектурних проблем, підтримки процесу супроводу програмних систем, рефакторингу та дослідження структури великих програмних проєктів. Окрім практичного застосування у процесі розроблення програмного забезпечення, результати роботи можуть бути використані у навчальному процесі під час вивчення дисциплін, пов’язаних із архітектурою програмного забезпечення, статичним аналізом коду та методами візуалізації даних. У результаті проведеного дослідження отримано комплексний підхід до аналізу архітектури програмного забезпечення, який поєднує графове представлення структури програмної системи, автоматизований аналіз залежностей, методи візуалізації та елементи машинного навчання. Запропонований підхід забезпечує можливість більш наочного та ефективного дослідження структури програмних систем і може бути основою для подальшого розвитку засобів автоматизованого аналізу програмного забезпечення. Дисертаційна робота складається з п'яти розділів. У першому розділі проведено аналітичний огляд підходів до контролю якості та аналізу архітектури програмного забезпечення, методів візуалізації програмних систем та існуючих інструментів. Виявлено, що жоден із наявних засобів не забезпечує одночасно статичного аналізу вихідного коду, зваженого графа залежностей, адаптивного виявлення аномалій та тривимірної просторової візуалізації, що обґрунтовує задачу дослідження. У другому розділі розроблено графову модель архітектури програмного модуля у вигляді орієнтованого зваженого графа з трьома категоріями вузлів і шістьма класами ребер, що охоплюють як декларативні, так і поведінкові залежності між компонентами. Описано метод автоматизованої побудови моделі для мови Swift на основі графа символів SymbolKit та продемонстровано її придатність для виявлення конкретних проблем проєктування. У третьому розділі розроблено підхід до автоматизованого виявлення архітектурних аномалій на основі статистичного аналізу характеристик графа залежностей. Детектор визначає відхилення відносно типових значень конкретної системи, що забезпечує адаптивність без жорстко заданих порогів. Підхід апробовано на реальному Swift-застосунку із підтвердженням виявлених аномалій аналізом вихідного коду. У четвертому розділі досліджено метрики якості візуалізації графів та встановлено їхні обмеження з точки зору когнітивного сприйняття. Запропоновано використання графових нейронних мереж як евристики для формування початкового розміщення вершин у силових алгоритмах. На вибірці з 44 Swift-проєктів підтверджено повну стабілізацію результатів та скорочення часу побудови layout до 58 % для графів середнього розміру. Розглянуто інтеграцію графової моделі у середовище доповненої реальності як засіб просторової візуалізації. У п'ятому розділі описано програмний комплекс A.D.A.R., реалізований як набір модулів Swift Package Manager із рівнем покриття тестами 95 %. Наведено деталі інтеграції в інструментарій розробника через SPM-плагіни та описано застосунок-переглядач з підтримкою багатокористувацьких AR-сесій і механізмами зменшення когнітивного навантаження. Дослідження проводилося в рамках виконання наукових тем кафедри інформатики Національного університету «Києво-Могилянська академія»: «Моделі та методи машинного навчання в прикладних задачах» (УДК: 004.85, 004.49; 004.056.57, № держреєстрації 0123U102430) та «Аналіз великих об'ємів даних в реальному режимі часу» (УДК: 004.4:061.68, 004.67.775, № держреєстрації 0118U000647).
Resource-Aware Embodied Intelligence through the Optimization of Data, Compute, and Trust : dissertation to obtain the degree of Doctor of Philosophy
(2026) Kuzmenko, Dmytro; Shvai, Nadiia
PhD thesis to obtain the degree of Doctor of Philosophy in the Programme Subject Area 122 "Computer Science" (12 – Information Technologies). – National University of Kyiv-Mohyla Academy, Kyiv, 2026. Modern robotic systems must learn and act under hard constraints of wall-clock time, onboard compute and memory, and energy, while remaining safe, reliable, and understandable in interaction with people. State-of-the-art perception, decisionmaking, and vision-language models often assume large training budgets or cloud resources, which limits real-world deployment. This dissertation is aimed specifically at solving these problems. It develops a set of algorithms and system designs that reduce temporal and computational cost without degrading task performance, and extends the notion of efficiency to human-robot interaction in terms of trust, safety, and cooperation. In the dissertation, methods are proposed and experimentally studied for efficient perception from egocentric video, resource-aware object-goal navigation with visionlanguage components, time-efficient model-based reinforcement learning with policy distillation for multi-task deployment, and a manager-level mixture-of-experts for vision-language models that selects among experts at inference time according to memory and latency budgets. The work also introduces an experimental benchmark for Empathic Ethical Disobedience (EED Gym), which formalizes efficiency in humanrobot interaction as maintaining safety and cooperation while minimizing unnecessary risk and interaction overhead. The research applies methods of machine learning and control, including semisupervised learning with pseudo-labels, architectural selection and ablation of visionlanguage stacks, model-based reinforcement learning with trajectory optimization, policy and ensemble distillation, mixture-of-experts routing with budget-aware expert selection, and simulation-based human-robot evaluation with safety-aware reward shaping and trust metrics. The experimental program covers large-scale egocentric perception datasets for walking environments, embodied navigation in scanned 3D scenes, multi-task control domains, and scripted human-agent interaction scenarios. Scientific results obtained in the dissertation: – A methodology for label- and compute-efficient visual perception based on semisupervised learning for egocentric locomotion scenes. – Resource-aware configurations for vision-language object-goal navigation that trade off success and path efficiency against GPU memory and latency. – Algorithms for time-efficient model-based reinforcement learning and a distillation pipeline that compresses multi-task agents into compact deployable policies. – An energy-efficient RL extension with a fuel-consumption penalty that reduces operational energy use with minimal impact on lap-time performance. – A manager-level mixture-of-experts (MoIRA) for vision-language models that provides budget-adaptive routing over heterogeneous experts. – A benchmark and methodology for efficiency in human-robot interaction (EED Gym), formalizing trust, safety, and cooperation under constraints. Conducted experimental research: An experimental study was performed across four strands. For perception, semi-supervised pipelines on egocentric datasets were evaluated with accuracy and label-efficiency metrics and analyzed with confusion matrices and deployment footprints. For object-goal navigation, vision-language stacks were profiled on HM3D-based splits with success, SPL, and module-wise time/VRAM measurements, producing deployable configurations under limited memory. For model-based reinforcement learning, training recipes and distillation procedures were evaluated by wall-clock, reward, and policy size across multiple tasks, including generalization and ablations. For human-robot interaction, EED Gym scenarios were used to measure safety risk, trust dynamics, and cooperative payoff for baseline policies and learned agents, with interventions such as clarification and refusal. Practical significance: The proposed methods form a software and experimental suite for building robotic systems that operate within realistic budgets. Semi- supervised perception reduces annotation and training cost and is suitable for mobile or embedded devices. Resource-aware navigation stacks enable zero- or low-shot object-goal navigation under modest GPU memory. Time-efficient RL with distillation shortens training cycles and allows multi-task deployment on limited hardware. The MoIRA manager permits a single agent to adapt its expert usage to changing latency or memory budgets without retraining. EED Gym provides an evaluation environment for developers and researchers to quantify safety-aware efficiency in interaction with people. The first chapter of the dissertation is dedicated to the analysis of existing research in label-efficient perception, object-centric navigation with vision-language models, time-efficient reinforcement learning and policy distillation, mixture-of-experts for large vision-language models, and efficiency in human-robot interaction. It outlines the main problems and challenges, including the dependence on large annotation budgets, instability under memory limits, and the need to optimize not only compute but also interaction safety and trust. The second chapter is dedicated to the methodology and experiments for efficient perception in robotics. The chapter presents a class of semi-supervised pipelines for egocentric walking environments, describes pseudo-label mining and augmentation strategies, and shows how coarse-to-fine training schedules and compact backbones yield accurate recognition with reduced labeled data and practical deployment footprints. The third chapter is dedicated to vision-language frontier maps for object-goal navigation. The chapter analyzes alternative vision-language backbones and detectors, introduces a resource-aware composition of components, and studies how success and path efficiency change with memory and latency budgets. A set of recommended configurations is provided for machines with limited VRAM. The fourth chapter presents the main algorithms for time-efficient model-based reinforcement learning and policy distillation. Training and planning schedules are introduced to reduce wall-clock time without degrading reward, multi-task distillation is used to compress ensembles and controllers into compact policies, and a joint energyefficient RL study augments the reward with a fuel-consumption term, reducing fuel per lap of the race car with minimal impact on lap time. The chapter includes ablations, generalization studies, and deployment considerations. The fifth chapter introduces MoIRA, a manager-level mixture-of-experts for visionlanguage-action agents. It proposes two zero-shot routing strategies – embeddingbased cosine similarity and prompt-driven language model inference – and three model serving configurations, then validates the framework on GR1 and LIBERO benchmarks, demonstrating that specialist routing matches or outperforms generalist baselines with explicit control over memory and latency trade-offs. The sixth chapter focuses on human-robot interaction and the Empathic Ethical Disobedience Gym. The chapter defines tasks, metrics for trust, safety, and cooperation, and intervention policies, and shows experimental results that quantify efficiency in interaction beyond compute alone, including when a robotic agent should clarify, comply, or refuse. In the general conclusions, the main findings of the dissertation are summarized, including the development of sample-efficient learning and inference methods across perception, navigation, control, and interaction, and the confirmation that efficiency can be optimized jointly with performance and safety for deployment-ready robotic systems.
Індексний доступ на основі суфіксних масивів для підрядкового пошуку в PostgreSQL : дисертація на здобуття наукового ступеня доктора філософії
(2026) Зважій, Дмитро; Глибовець, Андрій
Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 122 "Комп’ютерні науки" (12 — Інформаційні технології). — Національний університет "Києво-Могилянська академія", Київ, 2026. Дисертацію присвячено розробці методу індексного доступу для підрядкового пошуку, безпосередньо вбудованого в реляційну систему керування базами даних (СКБД). Підрядковий пошук, тобто знаходження усіх рядків бази даних, що містять заданий шаблон як префікс, як суфікс або як довільне входження, є фундаментальною операцією інформаційно-пошукових систем, проте у наявних реляційних СКБД він підтримується лише фрагментарно: вбудовані механізми PostgreSQL (Б-дерево з text_pattern_ops, GIN із pg_trgm, повнотекстовий пошук) охоплюють лише часткові випадки задачі, а зовнішні рішення на основі суфіксного індексу (зокрема SAES над Elasticsearch) не дають внутрішньої підтримки в самій реляційній СКБД. Це робить актуальною розробку методу індексного доступу, безпосередньо вбудованого в реляційну СКБД, який єдиною індексною структурою підтримує усі три операції підрядкового пошуку, визначений у термінах інваріантів цієї платформи та апробований у PostgreSQL. Об’єктом дослідження є процес виконання операцій підрядкового пошуку в реляційних системах керування базами даних. Предметом дослідження є моделі, методи та програмні засоби індексного доступу на основі суфіксних структур даних, що підтримують виконання операцій підрядкового пошуку у середовищі реляційної СКБД-платформи. Метою дослідження є побудова теоретичної моделі, розробка та експериментальне обґрунтування методу індексного доступу на основі суфіксного масиву для підтримки операцій підрядкового пошуку в PostgreSQL. Метод має гарантувати логарифмічну складність пошуку O(mlogN), однакову для трьох операцій (за префіксом, суфіксом та входженням), повну інтеграцію з менеджером буферів, журналюванням із записом наперед та програмним інтерфейсом методів доступу PostgreSQL і коректну взаємодію з моделлю багатоверсійного керування паралельністю на шляху читання. Для досягнення мети поставлено такі завдання дослідження: формально визначити операції підрядкового пошуку та їхню ієрархію складності; проаналізувати суфіксні структури даних як теоретичну основу методу; обґрунтувати вибір PostgreSQL як платформи апробації методу; виміряти продуктивність наявних механізмів PostgreSQL та оцінити розрив з теоретичними можливостями; побудувати теоретичну модель сторінкового суфіксного масиву у моделі блочного зовнішнього зберігання та довести межі I/O- і просторової складності методу інваріан- тно щодо конкретної СКБД-платформи; проаналізувати архітектуру PostgreSQL як систему обмежень для проєктування методу; обґрунтувати вибір суфіксного масиву порівняно з суфіксним деревом з урахуванням цих обмежень; розробити структуру сторінок, алгоритми побудови та пошуку методу; розробити програмну реалізацію SAindex безпосередньо в ядрі PostgreSQL; провести порівняльне експериментальне оцінювання на реальних та синтетичних даних. Для вирішення цих завдань застосовано теоретичні методи аналізу алгоритмів у моделі блочного зовнішнього зберігання з параметрами ⟨B, e, ek,N⟩ (побудова теоретичної моделі сторінкового суфіксного масиву та доведення меж I/O-складності методу); методи системної інтеграції через інтерфейс Access Method API PostgreSQL та системного програмування мовою C (розробка програмної реалізації SAindex); непараметричні методи статистичного аналізу, а саме критерій Манна–Вітні з контролем розміру ефекту через дельту Кліффа, якими виконано емпіричну верифікацію переваги на трьох наборах даних (GeoNames, synthetic_uniform, synthetic_zipf) на п’яти масштабах від 100 000 до 5 000 000 рядків, по 30 запусків на шаблон. Наукова новизна одержаних результатів полягає в такому. Уперше розроблено теоретичну модель сторінкового суфіксного масиву, сумісного з інваріантами реляційної СКБД-платформи, у системі параметрів ⟨B, e, ek,N⟩, яка зводить три операції підрядкового пошуку (префіксну, суфіксну та за входженням) до спільного діапазонного примітива з позиційною фільтрацією та обґрунтовує розподіл даних за схемою доступу через лему про розділення. Уперше доведено межі I/O-складності методу: верхню межу пошукової фази ≤ 2⌈log2 P⌉ + O(1) блочних доступів незалежно від типу операції та довжини шаблону, лінійні нижні межі фази збирання результатів для трьох стратегій та повноту покриття множин результатів, інваріантні щодо конкретної реляційної СКБД-платформи. Уперше встановлено просторову складність методу як N(e + 8,125) + B байтів, строго лінійну за обсягом колекції та незалежну від характеру даних, з кількісним обґрунтуванням коефіцієнта просторової надлишковості відносно вихідних даних. Уперше запропоновано метод індексного доступу на основі сторінкового су- фіксного масиву, повний цикл функціонування якого (зберігання, побудова, пошук, збирання результатів) специфіковано не в термінах PostgreSQL, а в термінах загальних інваріантів реляційної СКБД (буферний менеджер, журналювання із записом наперед, модель багатоверсійного керування паралельністю, інтерфейс методів доступу). Така платформо-незалежна специфікація уможливлює перенесення методу на будь-яку реляційну СКБД, що задовольняє ці інваріанти. Дістала подальшого розвитку інтеграція суфіксних структур у систему ти- пів та операторів реляційної СКБД через клас операторів text_sa_ops та два нові оператори: @> для пошуку за входженням (раніше доступний у PostgreSQL лише для контейнерних типів, але не для пари (text, text)) і ~@ для суфіксного пошуку, що є повністю новим оператором у системному каталозі; префіксний пошук інтегровано з вбудованим ^@. На відміну від евристичного розпізнавання планувальником шаблонів LIKE, запропоноване розширення дозволяє виразити тип підрядкового запиту прямо у системному каталозі. Практичне значення одержаних результатів та апробація методу. Запропонований метод апробовано шляхом розробки програмної реалізації SAindex обсягом 2782 рядки коду мовою C, інтегрованої безпосередньо в ядро PostgreSQL 18devel з відкритим вихідним кодом. Реалізація задовольняє вимоги стандартного протоколу побудови індексів та виконує повне WAL-журналювання операцій модифікації індексних сторінок; повноцінна підтримка інкрементальних модифікацій (aminsert, ambulkdelete, amvacuumcleanup) є напрямком подальшої роботи. На основі непараметричного критерію Манна–Вітні з контролем розміру ефекту через дельту Кліффа встановлено перевагу SAindex над триграмним методом GIN_TRGM з прискоренням 6,3× у медіані за шаблонами для запитів за входженням та 46,5× для префіксних запитів, перевагу над спеціалізованими Б-деревами у режимах низької селективності та рівнозначну продуктивність з BTREE_REV у режимі автоматичного вибору плану оптимізатором на масштабі 5M рядків. Достовірність експериментальних результатів підтверджено обов’язковою перевіркою коректності (160 з 160 тестових випадків відповідності множин рядків, повернутих SAindex, результатам послідовного сканування) та статистичною значущістю на основі 2188 тестів попарного порівняння методів. Дисертаційна робота складається з п’яти розділів. У першому розділі проведено аналітичний огляд методів пошуку підрядків та теоретичних основ суфіксних структур даних. Формалізовано три цільові операції підрядкового пошуку (префіксний, суфіксний пошук та пошук за входженням); розглянуто фундаментальні суфіксні структури (суфіксне дерево, суфіксний ма- сив, масив LCP, FM-індекс) та сучасні алгоритми їхньої побудови. Проаналізовано наявні механізми підрядкового пошуку в PostgreSQL та зовнішні рішення на основі суфіксного індексу; виявлено принциповий розрив між теоретичними можливостями суфіксних структур та їхньою реалізацією в реляційних СКБД, що обґрунтувало задачу дослідження. У другому розділі виконано експериментальну оцінку наявних механізмів підрядкового пошуку: міжсистемне порівняння PostgreSQL, Elasticsearch, MySQL та ClickHouse з еталонною реалізацією суфіксного дерева, деталізований бенчмарк механізмів PostgreSQL з виявленням характеру їхніх обмежень. Побудовано спрощену модель вартості пошуку у сторінковому суфіксному масиві в параметрах ⟨B, e,N, L,P⟩ та кількісно оцінено очікувану перевагу. У третьому розділі побудовано теоретичну модель індексного доступу на основі суфіксного масиву у зовнішній пам’яті в параметрах ⟨B, e, ek,N⟩, незалежну від конкретної СКБД-платформи. Доведено зведення трьох операцій підрядкового пошуку до єдиного діапазонного примітива з позиційною фільтрацією, межі I/O-складності пошукової та збиральної фаз, повноту покриття множин результатів і просторову складність N(e + 8,125) + B байтів. У четвертому розділі викладено метод індексного доступу на основі сторінкового суфіксного масиву для PostgreSQL. Архітектуру PostgreSQL подано як систему шести інваріантів C1–C6, що формують простір допустимих рішень; систематично оцінено шість вбудованих методів індексного доступу і обґрунтовано непридатність кожного як носія суфіксної структури. На цій основі запропоновано п’ятисекційну структуру зберігання на диску, формат індексного запису з матеріалізованим префіксом ключа, п’ятифазний конвеєр побудови через tuplesort, клас операторів text_sa_ops з трьома стратегіями пошуку та три стратегії збирання ідентифікаторів кортежів. Доведено коректність методу через систему з п’яти формальних тверджень. У п’ятому розділі наведено опис програмної реалізації SAindex та її експериментальної оцінки. Реалізацію виконано мовою C обсягом 2782 рядки коду й інтегровано в ядро PostgreSQL 18devel. Сформульовано методологію оцінки на трьох наборах даних (GeoNames, synthetic_uniform, synthetic_zipf) на п’яти масштабах від 100 000 до 5 000 000 рядків, по 30 запусків на шаблон. Наведено результати порівняння SAindex з GIN_TRGM, BTREE та BTREE_REV за чотирма парами, проаналізовано їхню статистичну значущість, поведінку за обмеженого I/O та валідність вибору планувальника; обговорено практичні обмеження методу та намічено напрями подальшої роботи.
Методи перевірки та безпечної актуалізації зовнішньої пам'яті RAG за умов модифікації знань та спотворення зворотного зв'язку : дисертація на здобуття наукового ступеня доктора філософії
(2026) Андрощук, Максим; Глибовець, Андрій
Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 122 "Комп’ютерні науки" (12 — Інформаційні технології). — Національний університет "Києво-Могилянська академія", Київ, 2026. Системи RAG дають змогу великим мовним моделям використовувати зовнішні джерела знань без перенавчання їхніх параметрів. У динамічних середовищах — корпоративних, медичних і юридичних — зовнішні джерела знань постійно змінюються, що породжує проблему безпечного оновлення: як приймати легітимні зміни й водночас відхиляти спотворені або помилкові дані. Більшість наявних RAG-систем не забезпечує формально обґрунтованих меж ризику проникнення отруєних даних, не має механізмів розрізнення природного дрейфу знань і координованого спотворення, а також потребує значних обчислювальних витрат для верифікації суперечностей, які за повного попарного порівняння зростають квадратично. Наявні підходи до захисту RAG-систем, зокрема PoisonedRAG, RobustRAG і TrustRAG, розглядають окремі аспекти захисту — фільтрацію отриманих документів, агрегування відповідей із кількох підмножин та оцінювання довіри до джерел, однак не формують єдиної архітектури, яка поєднує верифікацію суперечностей, безпечне переведення нових знань із карантинного стану до основної пам’яті та розрізнення легітимного дрейфу знань і координованого отруєння. Окремою проблемою є обчислювальна вартість верифікації: повне попарне порівняння отриманих документів засобами NLI має квадратичну складність відносно кількості документів у контексті, що обмежує застосування такої верифікації в онлайн-сценаріях. Водночас параметричні підходи до редагування знань моделей, зокрема ROME і MEMIT, передбачають доступ до ваг або внутрішніх представлень базової моделі — це ускладнює їх застосування для закритих моделей, доступних лише через API і поширених у промислових RAG-розгортаннях. Об’єктом дослідження є процеси оброблення, верифікації та оновлення даних у зовнішній пам’яті RAG-систем за умов динамічної зміни знань і спотворення джерел інформації. Предметом дослідження є методи й алгоритми верифікації узгодженості, виявлення суперечностей та безпечної актуалізації зовнішньої пам’яті RAG-систем без модифікації параметрів генеративної моделі. Метою дослідження є розроблення методів верифікованої та захищеної від отруєння актуалізації зовнішньої пам’яті RAG-систем за умов обмеженої обчислювальної вартості верифікації. Для досягнення мети вирішено такі завдання: розроблено якірну схему виявлення суперечностей зі зниженою вартістю NLI-верифікації; запропоновано двофазну схему карантину та затвердження нових знань із модельною верхньою межею ризику проникнення отруєних даних; побудовано шар прийняття рішень для розрізнення легітимного дрейфу знань і координованого отруєння; удосконалено механізми запитно-орієнтованого відбору підграфа, злиття ранжувань і керування повторною генерацією. Методологічну основу дослідження становлять методи математичного моделювання, теорії ймовірностей, статистичного аналізу, оброблення природної мови, зокрема NLI-верифікації, байєсівські методи виявлення зміни режиму, а також порівняльна експериментальна перевірка на контрольованих стендах і зовнішніх еталонних наборах даних. Наукова новизна одержаних результатів полягає у розробленні архітектури непараметричної адаптації зовнішньої пам’яті RAG-систем, яка поєднує верифікацію суперечностей, карантинне оновлення знань і виявлення режиму змін у єдиному замкненому циклі без модифікації параметрів генеративної моделі. Взаємодія функціональних контурів організована таким чином: результати NLI-верифікації суперечностей (A3) одночасно використовуються як вхідні сигнали для байєсівського карантину (A5) і детектора зміни режиму (A6); детектор A6, у свою чергу, змінює пороги прийняття рішень в A5 у разі виявлення координованої схеми змін, а оновлений стан довіри до джерел повертається на етап пошуку через зважування каналів злиття ранжувань. Така замкнена архітектура дає змогу системі поступово накопичувати інформацію про достовірність джерел під час тривалої експлуатації та зменшує потребу в ручному переналаштуванні параметрів у межах досліджених сценаріїв. Запропоновано інтегровану схему безпечної актуалізації зовнішньої пам’яті RAG, у якій контур верифікації суперечностей (A3), контур карантину та затвердження нових знань (A5), а також контур розрізнення легітимного дрейфу знань і координованого отруєння (A6) функціонують як взаємопов’язані підсистеми зі спільним інформаційним обміном через стан довіри до джерел. Інтеграція забезпечує системний ефект, недосяжний для окремих компонентів: рішення про карантин враховують сигнали детектора режиму, а оновлення довіри до джерел синхронізується з результатами верифікації. У контрольованих експериментальних сценаріях це дало змогу скоротити обчислювальні витрати NLI-верифікації на 57 %, заблокувати всі отруєні документи з тестового набору, зберегти 93 % легітимних оновлень і досягти повної класифікації режимів "дрейф знань / координоване отруєння" для досліджених конфігурацій. Удосконалено окремі механізми запропонованої архітектури: якірну схему виявлення суперечностей, яка знижує вартість NLI-верифікації з O(K²) до O(K·a); двофазну схему карантину та затвердження нових знань з аналітичною верхньою межею ризику проникнення отруєних даних; шар прийняття рішень на основі байєсівського детектора зміни режиму з виявленням коаліцій джерел; методи запитно-орієнтованого відбору підграфа, злиття ранжувань із урахуванням довіри й часу та керування повторною генерацією. Дістав подальшого розвитку підхід до непараметричної адаптації RAG-систем за участю людини у контурі керування завдяки введенню механізму довірчого оновлення за вимірами "джерело — тема — користувач — час". Запропоновані алгоритми перевірено на десяти зовнішніх еталонних наборах даних (N = 1250 запитів), а також у змагальних сценаріях із цільовою ін’єкцією отруєних документів. У базовому одномодельному налаштуванні повний конвеєр зберігає статистичний паритет із RAG-конвеєром на основі BM25-ретривера на 9 із 10 еталонних наборів даних; зафіксовано один статистично значущий негативний результат, який інтерпретується як очікувана плата за підвищення безпеки. У контрольованому наборі адверсаріальних експериментів механізм карантину заблокував усі отруєні документи з тестового набору; за цільової атаки з підміною відповідей відновлення якості відповідей становило 99,4 % відносно неатакованого сценарію. Експериментальну перевірку побудовано за принципом множинного підтвердження: контрольовані абляційні експерименти оцінюють внесок кожного компонента архітектури окремо; інтеграційні тести перевіряють властивості системи загалом; змагальні експерименти з цільовою ін’єкцією отруєних документів і симуляцією координованих атак оцінюють стійкість захисних механізмів; зовнішні еталонні набори даних використовуються для перевірки відсутності деградації якості на стандартних задачах. Статистичну значущість ключових результатів перевірено з поправкою на множинні порівняння за методом Беньяміні — Хохберга; для відповідних експериментальних тверджень наведено розміри ефектів і довірчі інтервали. Окремим компонентом експериментальної перевірки є дослідження стійкості: BOCPD-детектор зберіг якість класифікації в усіх 60 досліджених конфігураціях гіперпараметрів, що свідчить про придатність підходу до розгортання без додаткового ручного налаштування у межах перевірених промислово орієнтованих сценаріїв. Обмеження дослідження полягають у наступному. Ефективність запропонованих алгоритмів верифікації залежить від точності зовнішнього NLI-верифікатора, тому помилки такого верифікатора можуть впливати на якість виявлення суперечностей і подальші рішення щодо карантину. Контур перевірки зворотного зв’язку досліджено у межах контрольованого симуляційного сценарію; його перенесення на реальний користувацький зворотний зв’язок потребує окремої експериментальної перевірки. Захист від координованого отруєння обґрунтовано для випадку, коли атакувальна коаліція становить меншість активних джерел; стійкість до масових атак типу Сивілли потребує додаткових механізмів, зокрема доказу виконаної роботи або довірчого шлюзування джерел. Практичне значення одержаних результатів полягає у можливості застосування запропонованих алгоритмів для побудови корпоративних довідкових сервісів, систем підтримки клієнтів, а також медичних і юридичних інформаційних систем, у яких критичними є швидкість оновлення знань і фактологічна достовірність відповідей. Запропонована архітектура не потребує модифікації параметрів базової мовної моделі та є сумісною із закритими моделями, доступними лише через API; це розширює сферу її промислового застосування порівняно з параметричними підходами до редагування знань моделі. Зниження обчислювальної вартості NLI-верифікації на 57 % у досліджених сценаріях підвищує економічну доцільність онлайн-розгортання верифікованих RAG-систем за високого потоку запитів. В умовах широкого промислового розгортання RAG-систем і зростання кількості змагальних атак на пошукові індекси запропоновані методи дають змогу знизити ризик поширення недостовірної інформації без перенавчання великих мовних моделей. Результати дослідження можуть бути використані у навчальних курсах із інформаційного пошуку, оброблення природної мови та безпеки систем штучного інтелекту.

Browse

Recent Submissions