Дисертації (СП)
Постійне посилання зібрання
У зібранні розміщено дисертації, які захищені працівниками кафедри.
Переглянути
Нові надходження
Документ Відкритий доступ Метод автоматизації рефакторингу програмного коду з використанням бази знань(КПІ ім. Ігоря Сікорського, 2024) Ткачук, Андрій Віталійович; Булах, Б. В.Ткачук. А. В. Методи автоматизації рефакторингу програмного коду з використанням бази знань. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 122 «Комп’ютерні науки». – Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Київ, 2024. Метою дисертаційного дослідження є розробка методу аналізу початкового коду та його подальшого автоматизованого рефакторингу, який спирається на використання бази знань про цей код. Об'єктом дисертаційного дослідження є процеси збору, представлення і обробки інформації про початковий код програмних продуктів. Предметом дисертаційного дослідження виступають методи аналізу, представлення та обробки інформації для рефакторингу початкового коду з урахуванням його семантики, які базуються на використанні формалізованих знань про код. У ході роботи над дисертацією було використано такі методи дослідження: спостереження, порівняння, аналіз, формалізація, абстрагування, моделювання, експеримент. Зазначені методи були обрані зважаючи на мету та завдання дослідження, а також на практичність їх використання при вирішенні проблем автоматизованого аналізу та рефакторингу початкового коду прикладних програм. У дисертації вперше запропоновано метод автоматизації рефакторингу програмного коду, який відрізняється від існуючих тим, що здійснює перетворення коду на рівні сутностей бази знань, створеної на основі запропонованої моделі формалізації знань про синтаксис і семантику коду, для автоматичного виявлення і виправлення розповсюджених антишаблонів програмування. Вперше запропоновано метод модифікації проміжного представлення програмного коду в процесі рефакторингу, що уможливлює виправлення нетривіальних антишаблонів, який відрізняється від існуючих тим, що застосовує механізми логічного виведення до знань про код, сформульованих з використанням описових логік і правил логічного виведення. Удосконалено модель формалізації знань про програмний код для його рефакторингу на основі онтології об’єктно-орієнтованої мови програмування, що відрізняється від існуючих тим, що представляє не лише базові відомості про синтаксис, отримані від синтаксичного аналізатора, а й семантику складних конструкцій, шаблонів та антишаблонів з можливою прив'язкою до функцій програмного продукту. Розроблений метод дозволяє перевикористовувати схему бази знань із накопиченими знаннями про шаблони та антишаблони під час аналізу та рефакторингу початкового коду різними мовами програмування, що дозволяє зменшити час та витрати на розробку систем рефакторингу, розробляючи лише частину системи, що пов'язана із перетворення початкового коду в сутності бази знань і навпаки. Запропонований підхід до формалізації знань про початковий код дозволяє отримувати метадані про зміст початкового коду, порівнювати наповнення репозиторіїв (шукати семантичні дублікати), створювати документацію про програмний продукт з допомогою вже існуючих засобів для роботи із семантичними даними, описувати шаблони і антишаблони для проведення аналізу і рефакторингу без втручання розробника. Запропоновано застосування розробленого методу для побудови програмного прототипу системи аналізу і рефакторингу початкового коду для мови програмування Swift з описом онтології мовою OWL-DL, а правил логічного виводу та запитів до онтології – мовою S(Q)WRL, що дало змогу значно пришвидшити процес здійснення рефакторингу. Таким чином досягається суттєве зменшення витрат на розробку та підтримку програмних продуктів. Дисертація складається із семи розділів. У першому розділі розглянуто автоматизовані системи рефакторингу. Дано визначення системи автоматизованого рефакторингу, порівняно такі системи за побудовою і принципом роботи, розглянуто їх переваги і недоліки. Розглянуто можливість застосування і використання семантичних підходів до вирішення задач рефакторингу. Сформульовано висновок про те, що ефективне функціонування інструментів автоматизованого рефакторингу значною мірою залежить від автоматизованого аналізу початкового коду. Аналіз дає необхідне уявлення про структуру та семантику коду, гарантуючи безпечність і послідовність рефакторингу. Зазначено, що включення семантичного розуміння в статичний аналіз коду та рефакторинг забезпечує глибоке й точне розуміння поведінки коду, що призводить до більш точних і надійних результатів. У другому розділі детально розглянуто поняття онтології та її застосування в якості основи бази знань. Дано визначення описових (дескриптивних) логік та мови OWL на їх основі, а також описано версії та профілі мови, її основні поняття та особливості, концентруючись на можливостях представлення семантики і способах логічного виведення засобами OWL. Дано визначення системи логічного виведення, розглянуто і порівняно алгоритми, що застосовуються такими системами. Розглянуто можливості доповнення виразності OWL у вигляді правил SWRL та запитів SQWRL. Було зроблено висновок, що коли необхідно проаналізувати велику кодову базу або знайти шаблони в ній, онтологія, описана в OWL, та пов'язані з нею можливості логічного виведення можуть бути надзвичайно цінними. Використання системи логічного виведення (англ. reasoner) дозволяє створити логічно узгоджені та максимально інформативні онтології, тим самим максимізуючи їх корисність у таких застосуваннях як відкриття знань, інтеграція даних та семантичний пошук. У третьому розділі досліджено можливості вбудованого рефакторингу у мові Swift. Розглянуто можливості додавання нових дій рефакторингу до мови програмування, а також оцінено можливість масштабування. Проведено оцінку отриманих результатів. У результаті експериментів було встановлено, що для додавання лише одної відносно простої дії рефакторингу необхідно написати близько 300 рядків коду. І немає причин вважати, що в інших випадках потрібно буде написати суттєво меншу кількість рядків коду. Таким чином, існує актуальна потреба в удосконаленні та автоматизації процесу розширеного рефакторингу, що дозволила б розробнику уникнути написання чималої кількості «інфраструктурного» коду, більше зосередившись на кінцевій меті рефакторингу. У четвертому розділі розглянуто застосування формалізованих знань про початковий код для здійснення рефакторингу у мові Swift. Досліджено можливість подолання існуючих перепон при додаванні нових дій рефакторингу із застосуванням формалізованих знань. Запропоновано формальне представлення початкового коду у вигляді окремої бази знань. У результаті проведеного дослідження встановлено, що використання запропонованого методу дозволяє виконувати складні завдання рефакторингу за допомогою простої вербальної формалізованої команди. У п’ятому розділі доведено, що онтології можна використовувати, щоб ефективно зберігати знання зокрема про початковий код. Розглянуто кілька підходів до перетворення кодової бази в базу знань про код як сукупність фактів про код, що спираються на онтологію. У шостому розділі проведено розширення можливостей здійснення аналізу та рефакторингу за допомогою описових правил. До пропонованої моделі додано набір правил, що описують певні дії рефакторингу, і здійснено перевірку їх застосування для доведення ефективності. У сьомому розділі описано ряд проведених експериментів із застосуванням запропонованого методу та моделі для перевірки справедливості їх теоретичних очікуваних властивостей та характеристик. Здійснено аналіз статистичних даних, отриманих шляхом опитування експертів щодо швидкодії та взаємодії і роботи із запропонованими методом і моделлю. Проведено перевірку роботи методу і моделі на різних наборах вихідних даних, а також якісне порівняння із існуючими програмними рішеннями для рефакторингу. Ці розділи разом підкреслюють практичне застосування та ефективність використання онтологій та формалізованих знань у розробці програмного забезпечення, зокрема в контексті рефакторингу та аналізу коду. Дослідження демонструє потенціал цього підходу у підвищенні ефективності процесів розробки програмного забезпечення. У дисертації запропоновано метод аналізу та рефакторингу початкового коду прикладних програм, який через використання бази знань про початковий код на основі онтології, дозволяє абстрагуватись від конкретної мови програмування в проекті і здійснювати складні маніпуляції із початковим кодом шляхом маніпуляції його семантичним представленням. Основна ідея методу полягає у роботі із представленням коду на семантичному рівні, що відрізняється від існуючих способів використанням онтології та засобів OWL/S(Q)WRL для роботи із семантикою. У ході експериментальних досліджень було доведено можливість відносно просто описувати правила рефакторингу в онтології та здійснювати аналіз і рефакторинг різної складності, а також показано зменшення витрат часу на виконання таких завдань на 36% у порівнянні із іншими підходами аналізу і рефакторингу.Документ Відкритий доступ Методи вирівнювання рукописного тексту на основі розпізнавання з використанням машинного навчання та структурного аналізу символів(КПІ ім. Ігоря Сікорського, 2024) Яковчук, Олег Костянтинович; Рогоза, Валерій СтаніславовичЯковчук О.К. Методи вирівнювання рукописного тексту на основі розпізнавання з використанням машинного навчання та структурного аналізу символів. Кваліфікаційна наукова праця на правах рукопису. Дисертаційна робота на здобуття наукового ступеня доктора філософії за спеціальністю 122 «Комп’ютерні науки». – Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», 2024. Метою дисертаційного дослідження є підвищення ефективності вирішення комплексу задач, що виникають при вирівнюванні рукописного тексту. Разом із зростанням популярності рукописного введення постає завдання ефективної обробки рукописної інформації, зокрема рукописного тексту. Однією із задач є забезпечення структурної коректності та зрозумілості тексту, представленого в рукописному вигляді. Зокрема, актуальним завданням є вирішення проблеми вирівнювання рукописного тексту, при цьому зберігаючи формат, структуру рукописних елементів та їх текстовий вміст. Важливим є також збереження ідентичності та унікальності написаного тексту, що визначаються персональними особливостями написання та почерку автора. Водночас створювані рішення повинні мати змогу працювати в умовах обмеження обчислювальних ресурсів, на персональних пристроях, таких як смартфони, розумні годинники, інтерактивні дошки, монітори з рукописним введенням та інші гаджети. У даній дисертаційній роботі акцент робиться на вирішенні задачі вирівнювання рукописного тексту зі збереженням початкового стилю написання, без перетворення рукописного тексту в друковану форму. В дослідженні використовуються передові методи та технології для обробки рукописного тексту, включно з розпізнаванням та сегментацією тексту. Дослідження в напрямках обробки рукописного тексту, разом з візуальним покращенням тексту для підвищення його ясності та чіткості, має важливе значення для подальшого вдосконалення систем рукописного введення та їх використання в різних сферах, від освітнього до професійного використання. Розвиток вирівнювання рукописного тексту відкриває нові перспективи для зручної та ефективної роботи з рукописною інформацією, що стає невід’ємною частиною сучасного цифрового життя. В першому розділі дисертаційної роботи описується постановка задачі вирівнювання рукописного тексту, визначаються основні проблеми, що існують на сьогоднішній день та потребують уваги для ефективного вирішення поставлених задач. Визначається підзадача оцінки рукописного тексту на розбірливість та вирівняність, а також підзадача порівняння двох рукописних текстів для визначення якості результатів вирівнювання. Проводиться грунтовний аналіз існуючих досліджень та передових робіт як в області обробки рукописного введення, так і конкретно для задачі вирівнювання тексту, аналіз підходів до розпізнавання та сегментації рукописного тексту для визначення найбільш релевантних для використання в системі, що розроблюється в цій роботі. Розглядається загальна структура запропонованого рішення. В другому розділі представлено рішення, що пропонується використовувати в системі вирівнювання для проведення розпізнавання та сегментації рукописного введення. Досліджуються принципи роботи рекурентних нейронних мереж для задачі розпізнавання рукописного тексту. Описується ідея довгої короткочасної пам’яті, представляється архітектура мережі з використанням довгої короткочасної пам’яті, що дає змогу вирішувати відразу два завдання: сегментації та класифікації символів. Досліджується принцип нейромережевої часової класифікації. Представляється додаткова мережа для уточнення та покращення результатів сегментації символів. Представлено додаткові алгоритми для приєднання відтермінованих символів, пошуку та виправлення помилок сегментації. В третьому розділі приведено опис основної частини системи вирівнювання рукописного тексту. Представляється запропонований новий метод вирівнювання, що використовує структурний аналіз символів. Цей розділ включає в себе розгляд процесу попередньої обробки вхідних даних, представлення метрик текстового рядка, запропонованого розбиття символів на класи, виконання знаходження класів символів, обрахунку метрик всіх символів та фінальних метрик вирівняного рядка, проведення переміщення символів на знайдені відповідні позиції. Детально розглядається процес виконання кожного кроку, виконується розгляд розроблених алгоритмів та підходів, що застосовуються для структурного аналізу символів. Результатом даного розділу є спроектована та розроблена система для структурного аналізу рукописного тексту, що дозволяє виконувати поставлену задачу вирівнювання. В четвертому розділі представлені основні експерименти для аналізу якості роботи розробленої системи. Описується набір експериментальних даних та його базові характеристики. Проводиться оцінка точності системи розпізнавання. Виконуються обчислювальні експерименти, на основі яких підтверджено загальну спроможність системи успішно вирівнювати рукописний текст. Проводиться аналіз успішних прикладів роботи системи та допущених помилок при вирівнюванні, оцінка продуктивності роботи системи в середовищі з обмеженими ресурсами. Також розроблена система порівнюється з наявними підходами до поліпшення зовнішнього вигляду та вирівнювання рукописного тексту, результат підтвердив визначені переваги розробленої системи та її практичну цінність. Основним результатом цієї роботи є розроблена система вирівнювання рукописного тексту, яка базується на запропонованому методі вирівнювання рукописного тексту на основі розроблених алгоритмів розпізнавання та сегментації тексту, а також з використанням структурного аналізу символів, що враховує індивідуальні особливості почерку, зв’язне написання символів та дозволяє зберегти початковий стиль написання тексту. Розроблена система вирівнювання дає змогу розв’язувати наступні задачі по вирівнюванню текстів українською мовою: вирівнювання одного рядка рукописного тексту, вирівнювання текстів, що складаються з багатьох рядків, вирівнювання документів, що містять різні типи текстових блоків, вирівнювання текстової інформації з можливістю підтримувати різні типи контенту, такі як специфічні символи, математичні формули, адреси електронної пошти, номери телефонів і т.д. Особливістю розробленої системи є можливість до масштабування та розширення для підтримки нових мов, типів контенту, введення окремих правил для особливих задач вирівнювання. Перевагою розробленої системи є здатність вирівнювати текст з врахуванням персональних особливостей написання користувача. Розроблену систему вирівнювання тексту було успішно інтегровано в тестовий мобільний застосунок, який надає змогу користувачу вводити рукописний текст, отримувати результат розпізнавання тексту та результат вирівнювання тексту. Проведено експериментальні дослідження, що підтвердили здатність системи виконувати всі поставлені завдання. Система показала високі характеристики якості роботи та швидкодії в умовах роботи на пристроях з обмеженнями обчислювальних ресурсів. В результаті розроблена система може бути інтегрована до інших мобільних додатків для обробки та вирівнювання рукописного тексту. Підтримка роботи з українським текстом дає потенційні можливості для використання системи в різноманітних галузях нашої країни, таких як освіта, медицина, рекламний бізнес і т.д. На сьогодні існує тенденція цифровізації документообігу в різних сферах діяльності, в тому числі між державою та громадянами, де також може мати велику користь система обробки рукописного тексту для покращення візуального сприйняття, розбірливості написаного тексту, а також для зменшення загального розміру рукописного тексту, що дозволяє підвищити ефективність використання простору в текстових документах. Наукова новизна отриманих результатів. В рамках цього дослідження було: - Вперше запропоновано метод вирівнювання рукописного тексту, наукова новизна якого полягає у використанні розроблених алгоритмів розпізнавання та сегментації тексту, які базуються на теорії машинного навчання, а також у проведенні структурного аналізу символів, що враховує індивідуальні особливості почерку, зв’язне написання символів та дозволяє зберегти початковий стиль написання тексту. - Вдосконалено метод сегментації рукописного тексту, що ґрунтується на використанні легковісної рекурентної нейронної мережі та динамічного програмування, який відрізняється від існуючих застосуванням додаткових алгоритмів, які дають змогу знаходити та виправляти помилки сегментації, визначати відповідні символи для відтермінованих штрихів, що дозволяє підвищити точність маркування кожного символа. - Вперше розроблено метод вирівнювання для тексту, написаного українською мовою, наукова новизна якого полягає у використанні алгоритмів, що базуються на структурному аналізі символів, та визначаються окремо для кожного символа, а також у можливості реалізувати вирівнювання рукописних літер для різних стилів написання. Практичне значення отриманих результатів. Практичне значення результатів, отриманих у ході дисертаційного дослідження, зводиться до наступного переліку: - Розроблені метод та алгоритми впроваджено в інструментальну систему вирівнювання рукописного тексту, що дає змогу розв’язувати задачі вирівнювання одного рядка рукописного тексту та текстів, що складаються з багатьох рядків, на пристроях з обмеженнями обчислювальних ресурсів. - Розроблена система забезпечує високу точність результатів, що дозволяє використовувати її для знаходження правильних позицій всіх символів та їх коректного вирівнювання, що продемонстровано на прикладі її використання в тестовому мобільному додатку для вирівнювання рукописного тексту українською мовою. - Запропоновані та розроблені в цій роботі методи були використані при розробці комерційних проектів, зокрема в мобільному додатку для смартфонів Samsung у вигляді функції вирівнювання рукописного тексту для різних мов.Документ Відкритий доступ Підвищення ефективності алгоритмів нечіткого пошуку з використанням таблиці подібності символів(КПІ ім. Ігоря Сікорського, 2024) Клещ, Кирило Олегович; Петренко, Анатолій ІвановичКлещ К.О. Підвищення ефективності алгоритмів нечіткого пошуку з використанням таблиці подібності символів. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 122 «Комп’ютерні науки». – Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», 2024. Дисертаційне дослідження присвячене підвищенню швидкодії алгоритмів і розробці методу нечіткого пошуку з використанням таблиці подібності символів, для пошуку найбільш релевантних документів до пошукової фрази. В роботі створено метод нечіткого пошуку, який складається з 9 послідовних кроків та потрібен для швидкого пошуку співпадінь на великому наборі текстових даних. За допомогою цього методу була створена система нечіткого пошуку, яка дозволила вирішити задачу пошуку найрелевантніших документів до пошукової фрази з набору таких документів. Розроблений метод нечіткого пошуку комбінує переваги алгоритмів на основі детермінованих скінченних автоматів та алгоритмів на основі динамічного програмування для підрахунку відстані Дамерау-Левенштейна. Така комбінація дозволила впровадити таблицю подібності символів оптимальним чином. В рамках роботи запропоновано підхід та спосіб створення таблиці подібності символів та розроблено приклад такої таблиці для символів з англійського алфавіту, що дозволило знаходити міру подібності поміж двома символами з константною асимптотикою та перетворювати поточний символ в його базовий аналог. Для фільтрування й сортування документів було розроблено метод оцінювання відповідності текстових даних до пошукової фрази на основі метрики, яка одночасно враховує кількість знайдених і незнайдених символів та кількість знайдених і незнайдених слів. Алгоритм Дамерау-Левенштейна дозволяє знаходити відстань редагування поміж двома словами, враховуючи помилки наступних типів: заміна, видалення, додавання та транспозиція символів. В рамках роботи була запропонована модифікація цього алгоритму за допомогою використання таблиці подібності для більш точної оцінки відстані редагування між двома словами. На основі розробленого методу була створена система нечіткого пошуку, яка дозволить знаходити шукані результати швидше та підвищить релевантність отриманих результатів шляхом їхнього сортування відповідно до значень розробленої метрики подібності тестових даних. Також у роботі було досліджено, проаналізовано та надано рекомендації, яким чином можна інтегрувати особливості та потужності таблиці подібності символів з алгоритмом нечіткого пошуку Дамерау-Левенштейна. Дослідження алгоритмів нечіткого пошуку в тексті є важливою темою в галузі обробки тексту та інформаційного пошуку. Це обумовлено зростаючим обсягом текстової інформації і ймовірністю помилок через вплив людського фактору при написанні тексту та створенні текстового контенту. Нечіткий пошук використовує алгоритми для пошуку даних в тексті, які приблизно відповідають шаблону. Це досягається шляхом зіставлення та порівняння рядків або ключових слів, які можуть бути схожими між собою, але не ідентичними. У першому розділі дисертаційної роботи були розглянуті та проаналізовані різні алгоритми нечіткого пошуку. Такі як: алгоритм Дамерау-Левенштейна, алгоритм N-грам, алгоритм Джаро-Вінклера, алгоритм Bitap, звичайний алгоритм Левенштейна, алгоритм SoundE та алгоритми на основі скінченних автоматів. У ролі оптимального алгоритму пошуку відстані редагування між двома словами було обрано алгоритм Дамерау-Левенштейна, бо він дозволяє впровадити таблицю подібності оптимальним чином. Також були розглянуті алгоритми на основі скінченних автоматів, а саме: автомат на основі префіксного дерева, автомат на основі таблиці та автомат на основі хешування. Перші два виявились неефективними через певні недоліки, а останній виявився оптимальним та найбільш універсальним з точки зору швидкодії роботи та часу побудови, а також об’єму витраченої пам’яті. У другому розділі дисертаційної роботи було розроблено та покроково описано метод нечіткого пошуку, який дозволяє знаходити найрелевантніші документи до пошукової фрази. Також були розглянуті переваги та недоліки застосування таблиці подібності символів, підходи та способи її побудови. Було створено приклад таблиці подібності для символів з англійської мови за допомогою групування символів у JSON файлі. Використання таблиці подібності покращує отримані результати, особливо при використанні мов зі спеціальними символами. Це дозволяє знаходити набагато більше релевантних результатів, проте швидкодія алгоритму може зменшитись. За допомогою використання такої таблиці підвищується релевантність відповідних документів навіть при наявності орфографічних помилок, скорочень, слів-синонімів або інших форм неточностей у запиті. Підхід із використанням таблиці подібності символів може бути використаний у системах перевірки орфографії та автоматичної корекції, системах автозавершення та автодоповнення, а також у реалізації функцій з виявлення дублікатів даних та плагіату. У третьому розділі дисертаційної роботи проведено аналіз коректності результатів та ефективності алгоритмів нечіткого пошуку з використанням таблиці і без, а також алгоритму пошуку точного збігу. Було проведено перевірку всіх 4 алгоритмів нечіткого пошуку на основі скінченних автоматів на коректність роботи, а також розроблено та проаналізовано тести продуктивності для різних вхідних даних. Для перевірки коректності було розроблено програму, що використовує словник слів та порівнює редагувальну відстань, обчислену поточним рішенням, із редагувальною відстанню, обчисленою за допомогою готового бібліотечного рішення. Для перевірки продуктивності було проведено тестування, що визначає час побудови автомата та час перевірки слова для кожного з рішень. Також була реалізована система нечіткого пошуку на основі запропонованого методу та впроваджена у веб-додаток для пошуку найбільш релевантних документів. Отримані результати можуть бути корисними та використані в різних галузях, де потрібно ефективно та швидко проводити нечіткий пошук у великих обсягах даних, наприклад, при пошуку подібних документів у пошукових системах або при автокорекції помилок. В рамках роботи було: реалізовано метод нечіткого пошуку, який комбінує переваги алгоритмів на основі детермінованих скінченних автоматів та алгоритмів на основі динамічного програмування для підрахунку відстані Дамерау-Левенштейна; запропоновано технологію створення таблиці подібності символів у розроблений метод та створено приклад такої таблиці для символів з англійського алфавіту, що дозволило знаходити міру подібності двох символів із константною асимптотикою та перетворювати поточний символ в його базовий аналог; модифіковано метод оцінювання відстані редагування між двома словами за допомогою використання таблиці подібності в алгоритмі Дамерау-Левенштейна; запропоновано метод оцінювання відповідності текстових даних до пошукової фрази на основі метрики, яка одночасно враховує кількість знайдених/незнайдених слів та символів. Для реалізації декількох кроків розробленого методу було запропоновано технологію до створення таблиці подібності символів, яка дозволить враховувати можливу семантичну подібність символів в словах. Оцінюючи подібність на основі різних критеріїв, таких як: форма, контекст і фонетика, таблиця подібності символів дозволила модифікувати алгоритм нечіткого пошуку, який може ранжувати відповідні результати навіть за наявності великої кількості неспівпадінь unicode значень схожих символів. Це, в свою чергу, збільшило кількість релевантних результатів на 10 %, в залежності від довжини пошукової фрази. Також було впроваджено реалізований метод у систему для пошуку найбільш релевантних електронних листів, документів або текстів у середовищі для резервного копіювання.Документ Відкритий доступ Аналіз програмного коду з використанням гібридного методу пошуку та класифікації вразливостей(КПІ ім. Ігоря Сікорського, 2024) Куб’юк, Євгеній Юрійович; Кисельов, Геннадій ДмитровичКуб’юк Є.Ю. Аналіз програмного коду з використанням гібридного методу пошуку та класифікації вразливостей. - Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 122 «Комп’ютерні науки». – Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», 2024. Актуальність теми. У контексті стрімкого розвитку інформаційних технологій та цифровізації суспільства, проблематика кібербезпеки набуває особливої гостроти. Згідно зі статистикою, у 2022 році кількість кібератак зросла на 42% порівняно з попереднім роком, а фінансові збитки сягнули $6 трлн. Основною причиною такої ситуації є зростання кількості вразливостей у програмному забезпеченні, які активно використовуються зловмисниками. Зокрема, у Національній базі даних вразливостей США (NVD) за 2022 було зареєстровано понад 25 000 нових вразливостей, що на 20% більше ніж у 2021. Більше 75% успішних кібератак базувалися на експлуатації вже відомих вразливостей. Це свідчить про гостру необхідність розробки ефективних заходів щодо своєчасного виявлення та усунення вразливостей у програмному коді. Одним з найбільш перспективних напрямів вирішення цієї проблеми є створення автоматизованих систем аналізу коду на основі технологій штучного інтелекту. Такі системи здатні ефективно виявляти приховані дефекти безпеки на етапах розробки ПЗ, що дозволяє знизити ризики та підвищити захищеність. Їх інтеграція у процеси розробки поліпшить дотримання практик безпечного програмування та скоротить час на тестування безпеки. Отже, створення інноваційних методів та засобів автоматизації аналізу безпеки програмного коду є вкрай актуальним завданням для підвищення рівня кіберзахисту сучасних програмних систем. Мета і завдання дослідження. Метою дисертаційного дослідження є розробка та удосконалення методів виявлення та класифікації вразливостей в програмному коді з використанням нейронних мереж та методів виявлення подібності коду. Основні завдання дослідження включають: - Дослідити методи виявлення вразливостей в програмному коді. - Дослідити ефективність методів виявлення подібності коду в задачі класифікації вразливостей. - Дослідити моделі представлення програмного коду. - Розробити метод побудови проміжного представлення програмного коду для подальшого аналізу на предмет вразливостей. - Розробити метод виявлення вразливостей на основі нейронних мереж. - Розробити метод класифікації вразливостей на основі методу виявлення подібності коду. - Виконати програмну реалізацію системи аналізу програмного коду, з використанням гібридного методу пошуку та класифікації вразливостей програмного коду. - Провести обчислювальні експерименти та оцінку розробленої системи. - Продемонструвати практичну цінність розробленої системи на прикладі впровадження в процеси життєвого циклу розробки програмного забезпечення. Об’єктом дослідження є процес пошуку та класифікації вразливостей безпеки в програмному коді. Предметом дослідження виступають методи, алгоритми та структури даних для ефективного аналізу програмного коду на предмет вразливостей безпеки. Методи дослідження. В роботі застосовуються наступні методи дослідження: абстрактно-логічний аналіз проблеми, експерименти, моделювання, аналіз даних, порівняння. Зазначені методи були обрані з огляду на поставлені мету та задачі дослідження, а також на практичність їх застосування при вирішенні проблеми автоматичного аналізу програмного коду на предмет вразливостей безпеки. Наукова новизна отриманих результатів. Вперше запропоновано гібридний метод аналізу програмного коду, що поєднує методи глибокого навчання та методи виявлення подібності коду для пошуку та класифікації вразливості в коді, який дозволяє ефективно виконувати пошук вразливостей в коді, а також класифікувати з високою точністю знайдені вразливості. Отримав подальший розвиток метод побудови проміжного представлення програмного коду у вигляді кодового гаджету, який відрізняється від існуючих методів наявністю обмеження по розміру локального контексту відносно ключової точки, що дозволило зменшити результуючий розмір кодових гаджетів та підвищити точність класифікації при подальшому аналізі нейронною мережею. Вперше запропоновано метод класифікації вразливостей в програмному коді з використанням ковзного хешування абстрактного синтаксичного дерева, який відрізняється від існуючих методів тим що використовує метод виявлення подібності коду для ефективної класифікації вразливостей без необхідності використання навчальної вибірки великого об’єму. Практичне значення отриманих результатів. Розроблений метод дозволяє знаходити вразливості в програмному коді, написаному на мові C/C++, а також класифікувати тип знайденої вразливості, що дозволяє спростити процес пріоретизації та виправлення знайдених вразливостей для розробників програмних продуктів. Технологія пошуку та класифікації вразливостей в програмному коді успішно впроваджена в процеси розробки ІТ компанії та використовується для аналізу програмних продуктів на предмет вразливостей у якості сервісу аналізу коду. Також, командний інтерфейс системи дозволяє використовувати її у якості утиліти для аналізу коду, без необхідного розгортання у вигляді сервісу, що дозволяє спеціалістам з кібербезпеки використовувати даний інструмент в якості рекомендаційної системи в рамках процесів оцінки безпеки програмного коду. Розроблений метод було протестовано на реальних проектах з відкритим вихідним кодом. Зокрема, за допомогою розробленої системи вдалося знайти вразливість в проекті з відкритим вихідним кодом - Microsoft Terminal. Публікації. За результатами дисертаційного дослідження опубліковано 5 наукових праць, з яких 4 статті у наукових фахових виданнях України (3 з яких входять до міжнародних наукометричних баз) та 1 публікація в збірнику матеріалів конференції. Результати дослідження. Розроблено програмне забезпечення системи аналізу коду, що реалізує запропонований гібридний метод. Експериментально підтверджено ефективність системи у задачах пошуку та класифікації вразливостей в програмному коді. Структура та обсяг роботи. Дисертація складається зі вступу, 4 розділів, висновків, списку використаних джерел. Повний обсяг дисертації становить 140 сторінок. Робота містить 27 рисунків та 9 таблиць. Список використаних джерел налічує 81 найменувань. Основний зміст роботи. У вступі обґрунтовано актуальність теми, сформульовано мету та завдання дослідження, визначено об'єкт, предмет та методи дослідження, розкрито наукову новизну та практичне значення отриманих результатів. У першому розділі проведено аналіз сучасного стану у сфері кібербезпеки та тенденцій зростання кількості вразливостей у програмному забезпеченні. Розглянуто ключові стандарти та методології забезпечення безпеки ПЗ, зокрема Microsoft SDL, ОWASP та ISO 27034. Проаналізовано сучасні виклики, пов’язані зі зростанням складності систем та появою нових технологій. Розглянуто існуючі стандарти та методології забезпечення безпеки ПЗ. Досліджено можливості методів штучного інтелекту, зокрема машинного навчання, для автоматизації процесів аналізу безпеки коду. Розглянуто різні архітектури нейронних мереж та їх застосування для детекції вразливостей. Проаналізовано переваги та недоліки підходів. У другому розділі сформульовано постановку задачі дослідження та побудовано її математичну модель. Формалізовано функції перетворення даних на вході та виході системи. Розглянуто різні моделі подання програмного коду та обґрунтовано доцільність використання абстрактних синтаксичних дерев. Запропоновано власний гібридний підхід аналізу коду, що поєднує переваги глибокого навчання та алгоритмів пошуку подібності. Наведено детальний опис архітектури та математичних моделей складових компонент системи, зокрема нейромережевої моделі та модуля ковзного хешування AST. У третьому розділі представлено розробку ключових модулів запропонованої системи аналізу програмного коду з використанням гібридного методу пошуку та класифікації вразливостей. Описано удосконалений метод формування проміжних представлень коду на базі кодових гаджетів та їх подальша векторизація. Наведено архітектуру та алгоритми функціонування моделі глибокого навчання на основі BLSTM та модуля ковзного хешування AST. Також деталізовано розроблений метод класифікації вразливостей на основі ковзного хешування вузлів AST та порівняння з базою еталонів. Описано процедуру формування бази знань хешів вразливого коду та метод визначення оптимального вікна хешування AST. Четвертий розділ присвячено експериментальним дослідженням розробленої системи з використанням спеціалізованих наборів даних та кодових баз реальних проектів. Представлено аналіз отриманих результатів та порівняння з існуючими аналогами за критеріями якості та продуктивності. Обґрунтовано практичну цінність системи та можливості інтеграції в процеси безперервної інтеграції та доставки ПЗ. Модель пошуку вразливостей з використанням нейронних мереж продемонструвала 94.1% точності, а модель класифікації вразливостей з використанням ковзного хешування AST для 40 класів вразливостей - 51.1% точності. Обґрунтовано можливі шляхи вдосконалення системи. Висновки. У дисертаційній роботі вирішено актуальне науковоприкладне завдання розробки методів та програмних засобів для автоматизації процесів аналізу програмного коду на предмет вразливостей безпеки: 1. Запропоновано гібридний підхід до аналізу коду на основі поєднання методів глибокого навчання та алгоритмів пошуку подібності коду. Розроблено відповідну систему, що реалізує даний підхід. 2. Розроблено метод побудови проміжного представлення програмного коду у вигляді кодового гаджету, що дозволило підвищити ефективність подальшого аналізу за допомогою нейромереж. 3. Запропоновано метод класифікації вразливостей на основі ковзного хешування AST, що демонструє переваги за швидкодією у порівнянні з існуючими RNN-моделями. 4. Експериментально підтверджено ефективність розробленої системи, зокрема 94.1% точність пошуку вразливостей та 51.1% багатокласової точності їх класифікації.Документ Відкритий доступ Класифікація документів на основі векторних представлень словників при обробці природної мови у малоресурсному середовищі(КПІ ім. Ігоря Сікорського, 2023) Шаптала, Роман Віталійович; Кисельов, Геннадій ДмитровичШаптала Р.В. Класифікація документів на основі векторних представлень словників при обробці природної мови у малоресурсному середовищі. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 122 «Комп’ютерні науки». – Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», 2023. Метою дисертаційного дослідження є розробка та вдосконалення методів класифікації документів, написаних природною мовою, у малоресурсному середовищі за допомогою побудови векторних графових представлень словників природної мови. Проблема обробки природної мови у малоресурсному середовищі є складною через брак даних, які можна використовувати для тренування сучасних алгоритмів машинного навчання. Малоресурсне середовище може бути викликано відсутністю чи дорожнечою ручної розмітки на початкових етапах побудови інформаційних систем, а також низькими популярністю та розвитком природної мови у інформаційному просторі. Типові методи обробки природної мови вимагають наявність розмітки текстів відповідно до задачі, яка розв’язується. Така розмітка часто виконується експертами у прикладній галузі або людьми з високим рівнем лінгвістичної грамотності. Анотатори, які здатні виконувати розмітку, можуть не бути доступними для великого набору проєктів через відсутність фінансування (зазвичай це тимчасова робота, яка може не виправдати операційні кошти) чи мотивації (анотування – рутинна та одноманітна робота). Зважаючи на те, що 63% контенту Інтернету написано англійською мовою, і більшість мов представлена менш ніж 1% веб-сторінок, величезна кількість мов є малоресурсними та, відповідно, менш дослідженими з точки зору підходів до обробки природних мов. Це призводить до того, що інформаційні системи, які вимушені працювати на основі малопредставлених мов, часто потерпають від низької якості, порівняно з їх англомовними аналогами. Тому, покращення вже існуючих та розробка нових методів обробки природної мови у малоресурсному середовищі є актуальною задачею. У першому розділі дисертаційної роботи проведено аналітичний огляд методів та досліджень за темою дисертації. На основі огляду було сформовано класифікацію методів обробки природної мови у малоресурсному середовищі та виділено їх основні припущення, переваги і недоліки. У ході аналізу було з'ясовано, що існуючі методи для обробки природної мови у малоресурсному середовищі вимагають додаткових даних з суміжним до прикладної області змістом, що часто є не виправданим припущенням. Тому дослідження було спрямовано на розробку нових методів з використанням мінімальної кількості сторонніх даних, а саме – лінгвістичних словників, які існують у великій кількості мов як додатковий ресурс. Використання словникової інформації не є чимось новим – їх не рідко використовують системи побудовані на правилах. Проблема таких підходів – вони явно роблять запити до словників чи онтологій (побудованих на їх основі) щодо зв'язків між сутностями у прикладних текстах. Таким чином, поєднання сучасних методів обробки природної мови та словникової інформації ускладнюється, адже перші оперують з векторними представленнями лінгвістичних сутностей, а другі – є дискретними елементами у графових структурах. Тому методи перетворення інформації, що міститься у словниках, у вектори, з якими можуть працювати новітні підходи машинного навчання у контексті обробки природної мови можуть дозволити більш ефективно розширити уявлення прикладних систем про мову, аніж явні правила пошуку у словниках. Через це було сформовано наступне наукове завдання: «Розробка методів обробки природної мови на основі векторних представлень словників у малоресурсному середовищі». У другому розділі представлено загальну методику побудови векторних представлень словників та їх поєднання з методами обробки природної мови. Проведено теоретичні дослідження щодо можливості отримання таких представлень, їх бажаних властивостей та шляхів застосування. Отримано класифікацію методів побудови векторних представлень графів, виділено їх ознаки та обмеження. До таких методів відносяться методи на основі факторизації, такі як HOPE, факторизація графу, Лапласівські проекції, GraRep, LLE; методи на основі випадкових блукань, такі як Node2Vec, DeepWalk та Walklets; методи на основі глибокого навчання, такі як SDNE, DNGR та GCN; та інші. Описано яким чином дані методи можна застосувати для моделювання словників та варіанти модифікацій алгоритмів для роботи зі словниковими даними. Також було проаналізовано та упорядковано методи злиття кількох векторних представлень для отримання фінальних векторів, які можна використовувати для різноманітних задач обробки природної мови, наприклад класифікації документів. При цьому було виділено ті, що практично застосовувати у малоресурсному середовищі з обмеженим розміром розмічених даних, а саме метод конкатенації та зваженої суми векторних представлень. Для використання даних методів у контексті злиття векторних представлень документів на основі слів та словників була запропонована модифікація даних методів через додавання етапу пошуку відповідності слів. У третьому розділі описано результати експериментальних досліджень. Для перевірки впливу різних методів побудови векторних представлень словників, а також злиття векторних представлень словників та методів обробки природної мови у малоресурсному середовищі на результати моделювання у практичному завданні, було обрано вирішення задачі класифікації документів. Експериментальні дослідження проведено у прикладній області містобудування та урбаністики, а саме класифікації петицій до Київської міської ради за напрямами, такими як транспорт, освіта, благоустрій тощо. В якості додаткової словникової інформації, на основі якої будуються векторні представлення для поєднання з типовими методами класифікації документів, було обрано словник синонімів української мови. Для розуміння методів передобробки та формулювання практичних рекомендацій при роботі з подібними даними, у цьому розділі було детально описано та проаналізовано обидва джерела інформації. Малоресурсність середовища забезпечено через два аспекти вирішуваної задачі – петиції написані українською мовою, яка входить до третього десятка найпоширеніших мов світу та має невелику кількість якісних наборів даних для покращення якості роботи моделей, а також малим розміром набору даних при високій змістовній варіативності петицій. Результати проведених досліджень показали, що векторні представлення словників на основі методів кодування вершин графів можна поєднувати з типовими векторними представленнями документів для покращення якості класифікації документів за допомогою підходів машинного навчання. Кожен крок запропонованого методу має набір параметрів та гіперпараметрів, від яких залежить результат та ефективність фінального рішення. Тому додатково наведено аналіз даних опцій, а також порівняння різних підходів до побудови представлень вершин графів у контексті словників. Для досягнення найкращих результатів пропонується використання методу на основі випадкових блукань - Node2Vec, який перетворює елементи словника у вектори за прийнятний час, не вимагає багато ресурсів та отримує вищі оцінки при подальшій класифікації документів. Для наступного кроку, а саме злиття векторних представлень документів та словникової інформації оптимальним виявився метод зваженої суми. Додатково наводяться практичні рекомендації по роботі з подібними даними, а саме особливості отримання, збереження та передобробки документів, побудови словників для кожного з методів класифікації документів, збереження та обробки словника синонімів, а також аналіз статистичної значущості результатів. Наукова новизна одержаних результатів полягає у наступному: 1. Вперше запропоновано метод класифікації документів на основі векторних представлень словників при обробці природної мови у малоресурсному середовищі, який відрізняється від методів доповнення даних, що базуються на словниках, тим що у ньому поєднуються векторні представлення документів з векторними представленнями елементів лінгвістичних словників, що дозволяє збільшити F1-міру якості класифікації документів у малоресурсному середовищі; 2. Запропоновано векторну модель слів зі словника синонімів, яка на відміну від інших будується на основі векторних представлень вузлів графу словника, що надає можливість її повторного використання в різних задачах обробки природної мови через трансферне навчання; 3. Модифіковано методи конкатенації та зваженої суми при злитті векторних представлень слів додаванням етапу пошуку відповідності слів з документу словам з словника синонімів, що дозволяє покрити відсутні у словнику словоформи без побудови моделей визначення частини мови та пошуку словоформ, що суттєво ускладнено у малоресурсних середовищах. Практичне значення одержаних результатів полягає у тому, що: 1. Розроблений метод дозволяє значно підвищити F1-міру якості систем класифікації документів у малоресурсних середовищах. Таким чином розробники даних систем можуть зменшити час та витрати на розробку, адже вища якість системи досягатиметься з меншою кількістю розмітки, розширення якої може бути не доступним, або вимагати додаткових часових чи фінансових інвестицій; 2. Розроблено векторні представлення слів у словнику синонімів української мови, які можна перевикористовувати за допомогою трансферного навчання при створенні програмних систем у інших прикладних областях; 3. Представлено набір даних для класифікації тем петицій, націлений на тестування методів обробки природної мови у малоресурсному середовищі. Документи написані українською мовою та мають вузьку урбаністичну спеціалізацію, що робить набір даних відмінним від корпусів загального призначення; 4. Запропоновано застосування розробленого методу до класифікації петицій до Київської міської ради за темами, яка дозволяє автоматично пропонувати тему петиції при ручній розмітці, що може суттєво скоротити час на їх аналіз.Документ Відкритий доступ Стохастична оптимізація продуктивності пакету симуляції транспорту частинок в фізиці високих енергій(2019) Шадура, Оксана Віталіївна; Петренко, Анатолій ІвановичДокумент Відкритий доступ Стратегії розвитку сервіс-орієнтованих систем у хмарному середовищі(2018) Петренко, Олексій Олексійович; Кисельов, Геннадій Дмитрович