Математическое и алгоритмическое обеспечение интеллектуального статического анализа программных систем для специализированных гетерогенных вычислительных платформ тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Горчаков Артем Владимирович

• Горчаков Артем Владимирович
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Горчаков Артем Владимирович

Введение

Глава 1. Современные методы и алгоритмы интеллектуального статического анализа программных систем для выявления реализованных алгоритмов

1.1. Программные системы для гетерогенных вычислительных платформ

1.2. Поиск реализаций алгоритмов при разработке программных систем

1.3. Задача классификации текстов программ для определения реализованного алгоритма

1.4. Методы и алгоритмы преобразования текстов программ в векторные представления

1.4.1. Метод на основе word2vec

1.4.2. Метод на основе code2vec

1.4.3. Метод на основе гистограмм кодов операций

1.4.4. Метод на основе гистограмм типов вершин деревьев абстрактного синтаксиса

1.5. Оценка качества классификаторов

1.6. Методы и алгоритмы классификации векторных представлений текстов программ

1.6.1. Метод к ближайших соседей

1.6.2. Метод опорных векторов

1.6.3. Алгоритм случайного леса

1.6.4. Искусственные нейронные сети

1.6.5. Машины экстремального обучения

1.7. Методы и алгоритмы кластеризации векторных представлений текстов программ

1.8. Оценка качества разбиения набора объектов на кластеры

1.9. Алгоритмы поиска наилучших значений параметров методов и алгоритмов

1.9.1. Генетические алгоритмы

1.9.2. Роевые алгоритмы

1.10. Выводы по главе

Глава 2. Методы и алгоритмы повышения качества анализа текстов программ

2.1. Методы и алгоритмы преобразования текстов программ в векторные представления

на основе цепей Маркова

2.2. Определение решаемой задачи по тексту программы

2.2.1. Многоклассовая классификация для определения решаемой программой задачи

2.2.2. Оценка качества классификаторов программ

2.2.3. Чувствительность векторных представлений программ к классификатору

2.3. Бинарная классификация для обнаружения семантического сходства программ

2.4. Выявление подходов к решению задач в наборе текстов программ

2.4.1. Разбиение набора программ на кластеры на основе реализованных алгоритмов

2

2.4.2. Оценка качества разбиений набора текстов программ на кластеры

2.5. Алгоритм непрерывной оптимизации параметров методов и алгоритмов

2.5.1. Модифицированный алгоритм оптимизации на основе поиска косяком рыб

2.5.2. Оценка качества алгоритмов непрерывной оптимизации

2.6. Выводы по главе

Глава 3. Методы и алгоритмы вынесения рекомендаций по ускорению программ

3.1. Методика вынесения рекомендаций по повышению скорости выполнения программ

3.2. Методы и алгоритмы поиска фрагментов текстов программ по программе-примеру

3.2.1. Алгоритм сравнения текстов программ на основе вычисления расстояния между их векторными представлениями на основе цепей Маркова для деревьев абстрактного синтаксиса и графов «определение-использование» и оценки их цикломати-ческой сложности

3.2.2. Оценка качества векторных представлений текстов программ на основе цепей Маркова для деревьев абстрактного синтаксиса и графов «определение-использование»

3.2.3. Алгоритм поиска фрагментов текстов программ по программе-примеру

3.2.4. Оценка качества алгоритма поиска фрагментов текстов программ

3.3. Результаты применения методики вынесения рекомендаций по ускорению программ

3.4. Выводы по главе

Глава 4. Методы и алгоритмы учёта учебных достижений в курсах по программированию

4.1. Методика учёта учебных достижений в массовых курсах по программированию

4.2. Методы и алгоритмы выявления и определения способов решения учебных задач

4.2.1. Выявление способов решения задач на основе кластеризации программ

4.2.2. Определение способов решения задач на основе классификации программ

4.2.3. Автоматический учёт учебных достижений

4.3. Выводы по главе

Заключение

Список сокращений и условных обозначений

Список литературы

Список рисунков

Список таблиц

Приложение А. Типы задач, генерируемых Цифровым ассистентом преподавателя

Приложение Б. Параметры классификаторов и результаты оценки их качества

Приложение В. Свидетельства о государственной регистрации программ для ЭВМ

Приложение Г. Акты о внедрении результатов диссертации

3

Введение диссертации (часть автореферата) на тему «Математическое и алгоритмическое обеспечение интеллектуального статического анализа программных систем для специализированных гетерогенных вычислительных платформ»

Введение

Актуальность темы. Компьютеризация и цифровизация приводит к расширению круга задач, стоящих перед разработчиками программных систем (ПС). Для ускорения и упрощения разработки ПС были предложены методы интеллектуального статического анализа текстов программ для задач поиска ошибок, уязвимостей, нарушений стандартов программирования, а также для задач восстановления названий идентификаторов при обратной разработке ПС, определения функциональных возможностей и авторства ПС. Методы интеллектуального статического анализа основаны на преобразовании текстов программ в векторные представления с последующим применением методов и алгоритмов кластеризации и классификации, при этом существует потребность в повышении качества анализа текстов программ. Инновации в архитектуре серверов позволяют создавать гетерогенные вычислительные платформы. В гетерогенных вычислительных платформах центральный процессор дополняется специализированными ускорителями, такими как: графические процессоры, интегральные схемы специального назначения, программируемые логические интегральные схемы. Задача аппаратно-программного разбиения в настоящее время решается на основе вручную выявляемых разработчиком фрагментов текстов программ, обладающих потенциалом ускорения на заданной гетерогенной вычислительной платформе, и вследствие этого существует потребность в ускорении ПС на основе возможностей, предоставляемых гетерогенной вычислительной платформой с заданным набором аппаратных ускорителей, на которой планируется развёртывание ПС, для достижения наилучшей скорости работы ПС. В этой связи актуальна разработка математического и алгоритмического обеспечения интеллектуального статического анализа текстов программ ПС с целью их преобразования для повышения скорости выполнения программ на заданной гетерогенной вычислительной платформе.

Степень разработанности темы. Первые алгоритмы статического анализа и преобразования программ были описаны в 1950-х годах в работах А.П. Ершова, Л.В. Канторовича, Г. Хоппер (G. Hopper), Т.Дж. МакКейба (T.J. McCabe) и др. Так, Г. Хоппер и А.П. Ершовым были разработаны первые компиляторы, а Л.В. Канторовичем было впервые описано представление программ в виде деревьев, содержащих информацию о синтаксической структуре. Теории алгоритмов посвящены работы А.А. Маркова, Д.Э. Кнута (D.E. Knuth), М.В. Ульянова, В.А. Головешкина.

Задачу проектирования ПС для специализированных вычислительных платформ рассматривали Р.С. Митра (R.S. Mitra), А. Басу (A. Basu), П. Арато (P. Arato), С. Джухач (S. Juhasz), З.А. Манн (Z.A. Mann), А. Орбан (A. Orban), Д. Папп (D. Papp), Д. Саа (D. Saha), предложившие в 1990—2000-х годах подходы к аппаратно-программному разбиению ПС на основе популяционных алгоритмов

дискретной оптимизации. Позднее Х. Чжоу (X. Zhou) и Р. Канади (R. Canady), С. Бао (S. Bao) и А. Гокхейл (A. Gokhale) предложили способ минимизации издержек при размещении ПС на облачных платформах. П. Мокри (P. Mokri), М. Хэмпстед (M. Hempstead), Г. Захаропулу (G. Zacharopoulos), Л. Феретти (L. Feretti), Г. Ансалоне (G. Ansaloni), Г.Д. Гульельмо (G.D. Guglielmo), Л. Карлони (L. Car-loni), Л. Поцци (L. Pozzi) в 2020-х годах разработали подходы к статическому анализу текстов программ для идентификации фрагментов, обладающих потенциалом аппаратного ускорения, поскольку это необходимо для постановки и решения вышеупомянутых задач дискретной оптимизации. Современные исследования в области статического анализа текстов программ посвящены разработке и применению методов и алгоритмов интеллектуального анализа данных для задачи предсказания имён идентификаторов, которая рассматривалась в работах В. Коваленко, Е. Богомолова, Т. Брык-сина, У Алона (U. Alon), М. Зильберштейна (M. Zilberstein), О. Леви (O. Levy), И. Яхав (E. Yahav), для задачи поиска дефектов и уязвимостей в ПС, решению которой посвящены работы С. Ли (X. Li), Л. Вана (L. Wang), У. Яна (Y. Yang), У. Чена (Y. Chen), К. Ши (K. Shi), У. Лу (Y. Lu), Ж. Чана (J. Chang), Ж. Вэя (Zh. Wei). Эти задачи сводятся к задаче определения алгоритма, реализованного в тексте программы, решению которой посвящены работы А.Ф. да Сильвы (A.F. da Silva), Е. Борина (E. Borin), Ф.М.К. Перейры (F.M.Q. Pereira), А. Тахерхани (A. Taherkhani), Л. Малми (L. Malmi), А. Корхонен (A. Korhonen).

Методы и алгоритмы интеллектуального анализа данных и машинного обучения включают метод ^-ближайших соседей, разработанный Э. Фикс (E. Fix) и Дж. Ходжесом (J. Hodges), метод опорных векторов, разработанный К. Кортес (C. Cortes) и В. Вапником (V. Vapnik), алгоритм случайного леса, разработанный Т.К. Хо (T.K. Ho) и Л. Брейманом (L. Breiman). Существенный вклад в развитие искусственных нейронных сетей внесли А.И. Галушкин, П.Дж. Вербос (P.J. Werbos), Ф. Розенблатт (F. Rosenblatt), А. Крижевский, И. Суцкевер, Дж.Э. Хинтон (G.E. Hinton), Я. Лекун (Y. LeCun), Д.П. Кингма (D.P. Kingma), Дж. Ба (J. Ba), Т. Миколов, К. Чен (K. Chen), Г. Коррадо (G. Corrado), Х. Гуан-Бин (H. Guang-Bin). К.О. Стэнли (K.O. Stanley) и Р. Миикулайненом (R. Miikkulainen) был предложен подход на основе генетических алгоритмов Дж.Г. Холланда (J.H. Holland) для настройки параметров искусственных нейронных сетей. В Российской Федерации исследованиями в области биоинспири-рованной оптимизации занимаются А.П. Карпенко, Е.С. Семёнкин, В.В. Становов, Ш.А. Ахмедова, Л.А. Демидова, Е.А. Сопов, С.И. Родзин, В.В. Курейчик, В.М. Курейчик и др. Вопросами интеллектуального статического анализа и преобразования текстов программ занимаются А.А. Белеванцев, А.Е. Бородин, П.Н. Советов, Т.А. Брыксин и др.

Объектом исследования являются программные системы для специализированных гетерогенных вычислительных платформ.

Предмет исследования определён паспортом специальности 2.3.5, направлением исследований п.1, в части моделей, методов и алгоритмов анализа, трансформации и тестирования программ и программных систем, направлением исследований п.4, в части интеллектуальных систем машинного обучения, управления базами данных и знаний, инструментальных средств разработки цифровых продуктов.

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

Для достижения цели диссертационной работы решались следующие задачи:

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

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

3. Разработка и проведение экспериментальных исследований подхода к классификации текстов программ для определения алгоритма, реализованного в тексте программы.

4. Разработка и проведение экспериментальных исследований подхода к разбиению набора текстов программ на кластеры в зависимости от реализованных в текстах программ алгоритмов.

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

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

Научная новизна:

1. Впервые разработан метод преобразования текстов программ в векторные представления, основанный на построении цепей Маркова заданного порядка для деревьев абстрактного синтаксиса.

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

3. Разработан метод иерархической кластеризации текстов программ, отличающийся использованием расстояния Йенсена-Шеннона и векторных представлений текстов программ на основе цепей Маркова, построение которых производится для деревьев абстрактного синтаксиса.

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

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

Теоретическая значимость работы заключается в том, что: впервые описан и исследован подход к преобразованию текстов программ в векторные представления на основе цепей Маркова, построение которых производится для деревьев абстрактного синтаксиса и графов «определение—использование»; впервые предложена метрика для оценки чувствительности векторных представлений текстов программ к классификатору; впервые описан и исследован подход к кластеризации векторных представлений текстов программ на основе цепей Маркова и расстояния Йенсена-Шеннона; впервые модифицирован и исследован алгоритм поиска косяком рыб, в котором используется хаотический генератор псевдослучайных чисел и экспоненциальное убывание шага.

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

Результаты диссертационной работы использованы в составе технологического инструментария, применяемого для создания специализированного встроенного программного обеспечения телекоммуникационного оборудования, выпускаемого ООО «ЭН-ЭС-ДЖИ» (NSG Ltd.). Предложенные в диссертационной работе алгоритм преобразования текстов программ в векторные представления, основанный на построении цепей Маркова для деревьев абстрактного синтаксиса, а также алгоритм поиска фрагментов кода по тексту программы-примера были применены для идентификации фрагментов кода, обладающих перспективами ускорения, по разработанной методике вынесения рекомендаций по повышению скорости выполнения программ. Преобразование найденных фрагментов позволило повысить производительность средства построения программно-определяемой глобальной сети. Результаты диссертационной работы внедрены в практическую деятельность ООО «МИРЦ-Тех». Применение предложенных в диссертационной работе алгоритмов и методики вынесения рекомендаций по повышению скорости выполнения программ позволило выполнить переработку ПС клиентов ООО «МИРЦ-Тех» для ускорения ПС и избавления от дублирующейся функциональности.

Результаты диссертационного исследования используются в учебном процессе РТУ МИРЭА в ряде дисциплин, включая такие дисциплины как: «Программирование на языке Python», «Разработка кроссплатформенных программных систем», «Документирование и управление версиями программного обеспечения». Применение разработанной методики учёта учебных достижений в массовом курсе «Программирование на языке Python» в весеннем семестре 2022-2023 учебного года позволило автоматизировать выявление способов решения задач по программированию для повышения вовлеченности студентов в образовательный процесс, что выражается в увеличении числа решённых разными способами задач на 35%.

Основные результаты и научные положения, выносимые на защиту:

1. Метод преобразования текстов программ в векторные представления на основе цепей Маркова, построение которых производится для деревьев абстрактного синтаксиса, позволяющий обеспечить снижение чувствительности к классификатору до 4 раз и повышение точности, полноты и F1-меры используемых совместно с ним классификаторов до 12%.

2. Метод иерархической кластеризации векторных представлений текстов программ на основе цепей Маркова, построение которых производится для деревьев абстрактного синтаксиса, с использованием расстояния Йенсена-Шеннона, позволяющий обеспечить повышение значений показателя чистоты кластеризации и индекса Рэнда в среднем на 40% по сравнению с рассмотренными аналогами.

3. Модификация алгоритма поиска косяком рыб для задач непрерывной оптимизации, позволяющая обеспечить повышение точности находимых решений в среднем в 38 раз на тестовых оптимизационных задачах по сравнению с рассмотренными аналогами.

4. Алгоритм поиска фрагментов текстов программ в деревьях абстрактного синтаксиса по тексту программы-примера, основанный на оценке цикломатической сложности фрагментов текстов программ, а также на вычислении расстояния Йенсена-Шеннона между векторными представлениями текстов программ на основе цепей Маркова, построение которых производится для деревьев абстрактного синтаксиса и для графов «определение—использование», позволяющая обеспечить повышение точности, полноты и Fi-меры в среднем на 27% по сравнению с рассмотренными аналогами.

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

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

Личный вклад. Все научные результаты и основные положения, выносимые на защиту, получены автором лично.

Апробация результатов работы. Основные положения и результаты диссертационной работы докладывались в период 2019-2023 гг. на 11 конференциях, среди которых: всероссийская научно-техническая конференция «Интеллектуальные и информационные системы» (Интеллект2019, г. Тула, 2019); 8th International Workshop on Mathematical Models and their Applications (IWMMA, Krasnoyarsk, Russian Federation, 2019); 14th International Symposium «Intelligent Systems» (INTELS'20, Moscow, Russian Federation, 2020); 3rd International Conference on Control Systems, Mathematical Modeling, Automation and Energy Efficiency (SUMMA, Lipetsk, Russian Federation, 2021); всероссийская научно-техническая конференция «Интеллектуальные и информационные системы» (Интеллект-2021, г. Тула, 2021); 10th International Workshop on Mathematical Models and their Applications (IWMMA, Krasnoyarsk, Russian Federation, 2021); 2nd International Conference on Technology Enhanced

Learning in Higher Education (TELE, Lipetsk, Russian Federation, 2022); всероссийская научно-практическая конференция с международным участием «Информационный обмен в междисциплинарных исследованиях» (ИОМИ, г. Рязань, 2022); всероссийская школа-семинар «Системный анализ и обработка данных в психологии и образовании» (г. Москва, 2023); 21-я открытая всероссийская конференция «Преподавание информационных технологий в Российской Федерации» (г. Нижний Новгород, 2023); XXVIII всероссийская научно-техническая конференция студентов, молодых учёных и специалистов «Новые информационные технологии в научных исследованиях» (НИТ-2023, г. Рязань, 2023). Диссертация обсуждалась на кафедре корпоративных информационных систем института информационных технологий РТУ МИРЭА.

Диссертационная работа была выполнена при поддержке Министерства науки и высшего образования Российской Федерации, тема № FSFZ-2024-0023 «Методы выявления и обработки инцидентов в программном обеспечении на основе интеллектуального анализа мультимодальных векторных представлений текстов программ с применением технологий машинного и глубокого обучения».

Основные публикации по теме работы. По теме диссертации опубликовано 22 работы, в том числе 6 работ в изданиях, включенных в перечень рецензируемых журналов, рекомендованных ВАК по специальности 2.3.5; 11 работ в рецензируемых научных изданиях, индексируемых в международных реферативных базах и системах цитирования Scopus и Web of Science, из которых 2 статьи квартиля Q1 и 4 статьи квартиля Q2; 5 работ в иных изданиях.

Объем и структура работы. Диссертация состоит из введения, 4 глав, заключения и 4 приложений. Полный объем диссертации составляет 176 страниц, включая 49 рисунков и 33 таблицы. Список литературы содержит 228 наименований.

Глава 1. Современные методы и алгоритмы интеллектуального статического анализа программных систем для выявления реализованных алгоритмов

1.1. Программные системы для гетерогенных вычислительных платформ

Инновации в архитектуре вычислительных машин обеспечили возможность создания гетерогенных вычислительных платформ для решения специализированных задач [1]. В гетерогенных платформах центральный процессор общего назначения (англ. Central Processing Unit, CPU) дополняется специализированными ускорителями, такими как графические процессоры (англ. Graphics Processing Unit, GPU) [2], интегральные схемы специального назначения (англ. Application-Specific Integrated Circuit, ASIC), программируемые логические интегральные схемы (англ. Field-Programmable Gate Array, FPGA) [3]. Современные тенденции в области проектирования ПС направлены на перенос программных реализаций вычислительно интенсивных алгоритмов [4—6] на аппаратные ускорители, доступные на гетерогенной вычислительной платформе, для повышения скорости выполнения программ за счёт балансировки нагрузки, предотвращения простоя процессоров [7].

Выбор специализированного процессора для аппаратного ускорения фрагмента текста программы зависит от алгоритма, реализуемого фрагментом. Так, в [8] приведены оценки производительности специализированных процессоров и процессора общего назначения Intel в задаче машинного обучения, согласно которым GPU TitanXp позволяет ускорить обучение свёрточной искусственной нейронной сети (ИНС) LeNet-5 [9] в 8.8 раз по сравнению с CPU E-1620. При этом, как показано в [8], аппаратная реализация обученной ИНС на FPGA Arria-10 позволяет ускорить выполнение предсказаний в 44.4 раза по сравнению с CPU E-1620. Согласно оценкам, приведённым в [10], FPGA Xilinx PYNQ-Z1 позволяет ускорить классификацию изображений при помощи свёрточной ИНС AlexNet [11] в 64 раза по сравнению с двухъядерным CPU ARM Cortex-A9, в 1.6 раза по сравнению с четырёхъядерным CPU Intel i5-6400. В [8, 10] показано, что гетерогенные вычисления, включающие применение CPU для подготовки данных, GPU для обучения ИНС, FPGA для выполнения предсказаний ИНС, позволяют достичь наилучшей производительности ПС, решающей задачи интеллектуального анализа данных при помощи нейросетевых алгоритмов.

В [1] приведены оценки скорости решения систем линейных алгебраических уравнений (СЛАУ) и факторизации матриц на CPU i7-3820 и GPU GeForce Titan в задаче электрического каротажа нефтегазовых скважин. Показано, что нахождение решений СЛАУ на GPU может выполняться в несколько раз медленнее, чем на CPU, при этом факторизация матрицы выполняется быстрее на GPU. Применение гетерогенных вычислений, задействование и CPU, и GPU, позволяет достичь лучшей скорости выполнения программ в рассмотренных в [1] задачах численного моделирования.

Для максимизации производительности программно-аппаратных комплексов с учётом заданных ограничений, таких как, например, ограничения на энергопотребление, широкое распространение получил подход codesign [12, 13], согласно которому проектирование программных и аппаратных средств выполняется совместно с целью задействования специализированных ускорителей при решении вычислительных задач в процессе функционирования ПС.

При разработке ПС, как правило, используется один или несколько языков программирования общего назначения, таких как Python, Java, C#, C, JavaScript, в то время как для программирования аппаратных ускорителей применяют специализированные языки. Например, Open Computing Language (OpenCL) [14] и Compute Unified Device Architecture (CUDA) [15] используются для программирования графических процессоров, а для конфигурирования FPGA традиционным способом применяются языки описания аппаратуры (англ. Hardware Description Language, HDL), Verilog [16] или VHDL (англ. Very high-speed integrated circuits Hardware Description Language) [17]. Для упрощения переноса алгоритмов на FPGA были разработаны инструменты высокоуровневого синтеза (англ. High Level Synthesis, HLS) инструкций уровня регистровых передач (англ. Register Transfer Level, RTL) [18, 19]. Такие инструменты позволяют транслировать алгоритмы, описанные на языках высокого уровня, таких как C, C++, OpenCL, в RTL-код для последующего конфигурирования FPGA.

Известно также о предметно-ориентированных языках программирования (англ. Domain-Specific Language, DSL), позволяющих синтезировать высокопроизводительный HLS код [20—22]. Так, в [20] описан инструмент, позволяющий транслировать DSL на основе языка Python в Vivado HLS (C++) или OpenCL. В процессе трансляции осуществляется построение статического графа потока данных, переписывание графа для применения оптимизаций, а также синтез кода для целевой платформы. В [21] описан DSL, также основанный на подмножестве синтаксиса языка Python, поддерживающий трансляцию DSL в C для последующей обработки результата трансляции HLS-ком-пилятором. В [22] предложены методы и алгоритмы синтеза правил машинно-зависимой оптимизации для применения в компиляторах DSL для специализированных процессоров. Перечисленные инструменты могут использоваться для трансляции подмножества языка программирования высокого уровня, например, Python [20—22], в высокопроизводительный код, пригодный для запуска на GPU, для конфигурирования FPGA или для проектирования ASIC.

В [23, 24] рассматривалась оптимизационная задача аппаратно-программного разбиения при разработке ПС для вычислительных платформ, было предложено применение дискретных популя-ционных алгоритмов глобальной оптимизации для решения данной задачи. Позднее в [25] был предложен способ минимизации издержек при размещении ПС на облачной вычислительной платформе.

Для постановки и решения задачи аппаратно-программного разбиения необходимо предварительно выделить фрагменты текстов программ ПС, обладающие потенциалом аппаратного ускорения, а также получить версии выделенных фрагментов, пригодные для запуска на аппаратных ускорителях. В этой связи современные исследования в области статического анализа посвящены идентификации фрагментов ПС с целью их последующей переработки [20—22] для переноса на специализированные аппаратные ускорители [26—29].

1.2. Поиск реализаций алгоритмов при разработке программных систем

Для повышения производительности ПС, функционирующей на гетерогенной вычислительной платформе, реализованной с использованием языков программирования общего назначения, необходимо идентифицировать фрагменты текстов программ, пригодные для ускорения, а также выбрать подходящий способ их ускорения. Способы ускорения фрагментов текстов программ ПС могут включать как задействование специализированных процессоров для предотвращения их простоя, так и использование параллелизма по данным в многоядерном процессоре общего назначения [22, 23]. И в том, и в другом случае для упрощения и ускорения разработки может быть использован встраиваемый DSL, основанный на синтаксисе языка программирования общего назначения, поддерживающий трансляцию в пригодное для запуска на специализированном процессоре представление. При наличии доступа к текстам программ ПС задача идентификации фрагментов текстов программ ПС для вынесения рекомендаций по их ускорению может быть решена методами статического анализа.

Первые методы статического анализа и преобразования программ были описаны в [30—33]. А.П. Ершовым [30] и Г.М. Хоппер [31] были разработаны первые компиляторы, а Л.В. Канторовичем [32] было впервые описано представление программ в виде деревьев, содержащих информацию о синтаксической структуре. Такие деревья известны в литературе как деревья абстрактного синтаксиса (англ. Abstract Syntax Tree, AST). В настоящее время инструменты статического анализа широко используются при разработке программного обеспечения для его упрощения посредством автоматической переработки текстов программ [33, 34], для обнаружения некорректного кода [35], а также для поиска и устранения кода, нарушающего корпоративные стандарты программирования [36]. Современные исследования в области анализа и преобразования программ сосредоточены на задействовании алгоритмов интеллектуального анализа данных при статическом анализе текстов программ. Известные применения интеллектуальных статических анализаторов включают автоматическое дополнение программ [37], поиск дефектов и уязвимостей в ПС [38, 39], рекомендацию назва-

Список литературы диссертационного исследования кандидат наук Горчаков Артем Владимирович, 2024 год

// / г

0.6

0.4

0.2

0.0

----- word2vec

Цепь Маркова 1-го порядка для AST

---Цепь Маркова 2-го порядка для AST

--- code2vec

Гистограммы кодов операций ■ — Гистограммы типов вершин AST

100 200 300 400 500 600 700 800 900 1000 100 200 300 400 500 600 700 800 900 1000 Число программ Число программ

Рисунок 2.8 — Графическая зависимость качества (1.15), (1.16), (1.17), (1.18) KNN-классификатора от размера набора данных и подхода к преобразованию программ в векторные представления

Согласно рис. 2.8, векторные представления программ на основе AST и гистограмм кодов операций превосходят векторные представления программ на основе токенов на наборах, содержащих менее 500 программ. Ситуация меняется для наборов данных среднего размера, содержащих около 1000 программ, где word2vec показывает такие же результаты, что code2vec или цепи Маркова 2-го порядка для AST. Использование гистограмм на основе AST, цепей Маркова 1-го порядка и гистограмм на основе кодов операций позволяет достичь наилучшего качества классификатора KNN, несмотря на простоту этих подходов, не требующих обучения ИНС или настройки параметров.

60

Полученные результаты согласуются с работами [51] и [61], где показано, что простые алгоритмы преобразования программ в векторные представления могут превосходить подходы, основанные на обучении глубоких ИНС, в задаче определения реализованного алгоритма.

На рис. 2.9 показано влияние размера набора данных и способов преобразования программ в векторы на качество результатов, полученных с помощью SVM-классификатора.

1.0

0.8

0.6-

0.4

ё О

0.2

0.0

...... word2vec

Цепь Маркова 1-го порядка для AST

---Цепь Маркова 2-го порядка для AST

--- code2vec

- Гистограммы кодов операций --Гистограммы типов вершин AST

1.0

0.8 -

0.6-

* 0.4 №

0.2

100 200 300 400 500 600 700 800 900 1000 Число программ

0.0

...... word2vec

Цепь Маркова 1-го порядка для AST

---Цепь Маркова 2-го порядка для AST

--- code2vec

- Гистограммы кодов операций --Гистограммы типов вершин AST

100 200

300 400 500 600 700 Число программ

800 900 1000

1.0

0.8 -

0.6-

0.4-

0.2-

0.0

...... woid2vec

Цепь Маркова 1-го порядка для AST

---Цепь Маркова 2-го порядка для AST

---code2vec

- Гистограммы кодов операций --Гистограммы типов вершин AST

100 200 300 400 500 600 700 800 900 1000 Число программ

1.0

0.8 - У

0.6-

0.4-

0.2-

0.0

...... woid2vec

Цепь Маркова 1-го порядка для AST

---Цепь Маркова 2-го порядка для AST

---code2vec

- Гистограммы кодов операций --Гистограммы типов вершин AST

100 200

300 400 500 600 700 Число программ

800 900 1000

Рисунок 2.9 — Графическая зависимость качества (1.15), (1.16), (1.17), (1.18) SVM-классификатора от размера набора данных и подхода к преобразованию программ в векторные представления

Как показано на рис. 2.9, векторные представления программ на основе AST и кодов операций в случае SVM также превосходят векторы на основе токенов на наборах данных малого и среднего размера. Векторные представления программ, полученные с использованием цепей Маркова 1-го порядка для AST и гистограмм кодов операций, лучше всего работают на небольших наборах данных при использовании с SVM. Увеличение размера набора данных приводит к повышению качества векторных представлений на основе токенов word2vec.

На рис. 2.10 приведено сравнение разных подходов к преобразованию программ в векторные представления перед применением классификатора на основе RF-алгоритма (см. Алгоритм 4). Согласно рис. 2.10, цепи Маркова 1-го и 2-го порядка, гистограммы типов вершин AST, гистограммы кодов операций превосходят word2vec и code2vec на наборах малого и среднего размера в случае RF.

1.0

0.8

0.6

§ 0.4В ю О

0.2-1

0.0

^ ...».....

..... word2vec

Цепь Маркова 1-го порядка для AST

---Цепь Маркова 2-го порядка для AST

--- code2vec

Гистограммы кодов операций ■ — Гистограммы типов вершин AST

1.0

0.2-

0.0

0.8- У у

£ 0.6-

Он

S

Е 0.4-

П- - ---.-.,—

..... word2vec

Цепь Маркова 1-го порядка для AST

---Цепь Маркова 2-го порядка для AST

--- code2vec

- Гистограммы кодов операций --Гистограммы типов вершин AST

100 200 300 400 500 600 700 800 900 1000 100 200 300~

Число программ

400 500 600 700 800 900 1000 Число программ

1.0

г / /

/

< .

0.6

0.4

0.2-

0.0

^ 1 ^_LI_

■ г' .............

..... word2vec

Цепь Маркова 1-го порядка для AST

---Цепь Маркова 2-го порядка для AST

--- code2vec

Гистограммы кодов операций ■ — Гистограммы типов вершин AST

1.0 0.8

ё 0.6

6 g

С 0.4 0.2-1

0.0

..... word2vec

Цепь Маркова 1-го порядка для AST

---Цепь Маркова 2-го порядка для AST

---code2vec

- Гистограммы кодов операций --Гистограммы типов вершин AST

100 200 300 400 500 600 700 800 900 1000 100 200 300~

400 500 600 700 Число программ

800 900 1000

Число программ

Рисунок 2.10 — Графическая зависимость качества (1.15), (1.16), (1.17), (1.18) RF-классификатора от размера набора данных и подхода к преобразованию программ в векторные представления

Как видно из рис. 2.10, при использовании гистограмм типов вершин AST и цепей Маркова для AST RF требуется меньше примеров для достижения высокого качества классификации по сравнению с гистограммами кодов операций. Это может указывать на то, что признаки, извлечённые из AST программ, более информативны в рассматриваемой задаче.

На рис. 2.11 приведено сравнение подходов к преобразованию программ в векторные представления, используемых совместно с ИНС. Согласно рис. 2.11, цепи Маркова на основе AST показывают лучшие результаты среди рассмотренных подходов преобразования программ в векторы, используемых совместно с классификатором на основе ИНС. В отличие от RF (см. рис. 2.10) и KNN (см. рис. 2.8), гистограммы на основе AST и кодов операций работают значительно хуже с ИНС. Это может указывать на то, что при использовании ИНС с подходами к преобразованию программ в векторы на основе гистограмм требуется дополнительная настройка гиперпараметров ИНС.

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

1.0

0.8

0.6

I

8

ё О

1 ■ / /

0.4

0.2

0.0

га*»"'

----- woid2vec

Цепь Маркова 1-го порядка для AST

---Цепь Маркова 2-го порядка для AST

--- code2vec

Гистограммы кодов операций ■ — Гистограммы типов вершин AST

0.2-

0.0-

word2vec Цепь Маркова 1-го порядка для AST

---Цепь Маркова 2-го порядка для AST

--- code2vec

Гистограммы кодов операций ■ — Гистограммы типов вершин AST

100 200 300 400 500 600 700 800 900 1000 100 200 300 400 500 600 700 800 900 1000 Число программ Число программ 10 -—-¡-..._______¡_____ 1.0 -

- ■ ~ ^

----- word2vec

Цепь Маркова 1-го порядка для AST

---Цепь Маркова 2-го порядка для AST

--- code2vec

Гистограммы кодов операций ■ — Гистограммы типов вершин AST

0.8

0.6-

0.4

0.2

0.0

word2vec Цепь Маркова 1-го порядка для AST

---Цепь Маркова 2-го порядка для AST

--- code2vec

Гистограммы кодов операций ■ — Гистограммы типов вершин AST

100 200 300 400 500 600 700 800 900 1000 100 200 300 400 500 600 700 800 900 1000 Число программ Число программ

Рисунок 2.11 — Графическая зависимость качества (1.15), (1.16), (1.17), (1.18) ИНС от размера набора данных и подхода к преобразованию программ в векторные представления

abcdefghijklmnopqrstuvwx

¡ 0.8-1

I Е-

^0.6-

•ЯДУ Ин1

1 \ I ** } } ,

i sí

* i t TI1 T

\ } {

5*

abcdefghijklmnopqrstuvwx

(a) word2vec + KNN

(b) word2vec + SVM

(c) word2vec + RF

(d) ward2vec + MLP

(e) Цепь Маркова 1-го порядка для AST + KNN

(f) Цепь Маркова 1-го порядка для AST + SVM

(g) Цепь Маркова 1-го порядка для AST + RF

(h) Цепь Маркова 1-го порядка для AST + MLP

(i) Цепь Маркова 2-го порядка для AST + KNN (j) Цепь Маркова 2-го порядка для AST + SVM (к) Цепь Маркова 2-го порядка для AST + RF (1) Цепь Маркова 2-го порядка для AST + MLP (m) code2vec + KNN

(n) code2vec + SVM (o) code2vec + RF (p) code2vec + MLP

(q) Гистограммы кодов операций + KNN (г) Гистограммы кодов операций + SVM (s) Гистограммы кодов операций + RF (t) Гистограммы кодов операций + MLP (и) Гистограммы типов вершин AST + KNN (v) Гистограммы типов вершин AST + SVM (w) Гистограммы типов вершин AST + RF (х) Гистограммы типов вершин AST + MLP

abcdefghijklmnopqrstuvwx

аЬс(1еГеЬ1]к1т]1ор4[Ни¥¥х

Рисунок 2.12 — Оценки качества классификации для пар из подхода к преобразованию программ в векторные представления и классификатора для набора, содержащего 100 программ из [152]

Отрезки, показанные на рис. 2.12, обозначают интервалы, ограниченные д + а и д — а, где д обозначает среднее значение (2.4), а а обозначает стандартное отклонение (2.5), вычисленное на основе наблюдений, полученных в результате перекрестной проверки качества классификатора по k блокам при k = 5 (см. рис. 2.6 и рис. 2.7). Данные, представленные на рис. 2.12, также приведены в числовом виде в таблице 2.3.

Таблица 2.3 — Оценки качества классификации для пар из подхода к преобразованию текстов программ в векторы и классификатора, для набора, содержащего 100 текстов программ из [152]

Вложение программ Алг. Общая точ. (1.15) Точность (1.16) Полнота (1.17) F1 мера (1.18)

word2vec (см. раздел 1.4.1) KNN 39.0 ± 10.7 30.3 ± 8.3 37.2 ± 7.9 31.8 ± 7.5

SVM 25.0 ± 3.2 11.7 ± 6.2 21.9 ± 4.1 13.4 ± 5.8

RF 65.0 ± 6.3 59.0 ± 5.0 61.4 ± 5.4 57.8 ± 5.4

ИНС 19.0 ± 7.3 5.1 ± 3.7 14.8 ± 5.3 6.8 ± 4.5

Цепь Маркова 1 -го порядка для AST (см. раздел 2.1) KNN 81.0 ± 5.5 78.8 ± 5.3 78.2 ± 3.5 75.4 ± 5.1

SVM 84.0 ± 7.3 78.6 ± 8.9 80.0 ± 8.0 77.0 ± 9.6

RF 92.0 ± 4.0 88.2 ± 5.9 89.4 ± 5.3 87.8 ± 6.1

ИНС 86.0 ± 7.3 79.6 ± 10.5 82.0 ± 9.1 79.5 ± 10.0

Цепь Маркова 2-го порядка для AST (см. раздел 2.1) KNN 70.0 ± 10.5 63.3 ± 12.7 66.1 ± 9.1 62.1 ± 11.3

SVM 83.0 ± 6.8 75.4 ± 8.2 77.6 ± 6.5 75.0 ± 7.7

RF 91.0 ± 5.8 88.2 ± 9.4 88.8 ± 8.1 87.1 ± 9.4

ИНС 88.0 ± 8.1 81.6 ± 10.8 83.9 ± 10.4 81.2 ± 11.4

code2vec (см. раздел 1.4.2) KNN 76.0 ± 9.7 70.2 ± 12.6 71.5 ± 10.8 68.6 ± 12.2

SVM 81.0 ± 9.7 77.7 ± 7.8 79.3 ± 8.9 76.4 ± 9.3

RF 74.0 ± 5.8 67.6 ± 7.3 71.2 ± 7.1 67.9 ± 8.2

ИНС 76.0 ± 5.8 69.9 ± 6.7 71.8 ± 5.9 68.4 ± 6.4

Гистограммы кодов операций (см. раздел 1.4.3) KNN 84.0 ± 10.7 78.7 ± 12.5 80.3 ± 12.1 78.3 ± 12.7

SVM 87.0 ± 9.3 83.6 ± 11.6 84.8 ± 10.3 83.6 ± 11.3

RF 86.0 ± 7.3 81.6 ± 10.2 82.4 ± 9.3 80.6 ± 10.3

ИНС 60.0 ± 7.1 44.7 ± 8.1 53.3 ± 5.6 45.9 ± 7.3

Гистограммы типов вершин AST (см. раздел 1.4.4) KNN 84.0 ± 6.6 82.2 ± 5.8 81.9 ± 6.5 79.8 ± 6.5

SVM 86.0 ± 5.8 83.1 ± 6.6 83.5 ± 6.6 81.4 ± 6.7

RF 92.0 ± 3.0 88.2 ± 4.9 89.4 ± 4.3 87.8 ± 5.1

ИНС 52.0 ± 6.8 34.3 ± 5.5 43.1 ± 4.1 35.6 ± 5.1

Для каждой меры качества в таблице 2.3 жирным выделены 3 наилучших значения. Для небольшого набора, содержащего 100 текстов программ, классификаторы на основе RF и SVM лучше всего работают с вложениями, учитывающими иерархические связи между элементами синтаксиса программ, включая цепи Маркова для AST, гистограммы вершин AST, гистограммы кодов операций, code2vec, как видно из рис. 2.12 и таблицы 2.3. Простой классификатор KNN (см. Алгоритм 3) показывает хорошие результаты при использовании вместе с цепями Маркова 1-го порядка для AST или с вложениями программ на основе гистограмм.

Цепи Маркова 1-го и 2-го порядка на основе AST, а также гистограммы типов узлов AST, используемые совместно с RF, показывают лучшее качество классификации по сравнению с другими рассмотренными подходами к преобразованию программ в векторные представления для малого набора данных, содержащего 100 программ. Низкое качество классификаторов на основе ИНС, используемых вместе с вложениями на основе гистограмм, может указывать на необходимость дополнительной настройки гиперпараметров классификаторов на основе ИНС.

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

• (a) word2vec + KNN А (Ь) word2vec + SVM

■ (с) word2vec + RF

• (d) word2vec + MLP

• (e) Цепь Маркова 1 -го порядка для AST + KNN (f) Цепь Маркова 1-го порядка для AST + SVM

■ (g) Цепь Маркова 1-го порядка для AST + RF

• (h) Цепь Маркова 1-го порядка для AST + MLP

• (i) Цепь Маркова 2-го порядка для AST + KNN A (j) Цепь Маркова 2-го порядка для AST + SVM

■ (к) Цепь Маркова 2-го порядка для AST + RF

• (1) Цепь Маркова 2-го порядка для AST + MLP

• (m) code2vec + KNN A (n) code2vec + SVM

■ (o) code2vec + RF

• (p) code2vec + MLP

• (q) Гистограммы кодов операций -I- KNN А (г) Гистограммы кодов операций -I- SVM

■ (s) Гистограммы кодов операций + RF

• (t) Гистограммы кодов операций + MLP

• (и) Гистограммы типов вершин AST + KNN A (v) Гистограммы типов вершин AST + SVM

■ (w) Гистограммы типов вершин AST + RF

• (х) Гистограммы типов вершин AST + MLP

ibcdefgh i j klmnopqr s tnvwx

bcdefghi j klmnopqr s tuvwx

Рисунок 2.13 — Оценки качества классификации для пар из подхода к преобразованию программ в векторные представления и классификатора для набора, содержащего 1000 программ из [152]

Данные, показанные на рис. 2.13, также представлены в числовом виде в таблице 2.4. Для каждой меры качества в таблице 2.4 жирным выделены 3 наилучших значения. Результаты, полученные

65

для 1000 программ, в целом аналогичны результатам, полученным для 100 программ (см. рис. 2.12). Однако, согласно рис. 2.13 и таблице 2.4, цепи Маркова 2-го порядка на основе AST работают значительно хуже при использовании с KNN по сравнению с цепями Маркова 1 -го порядка. Цепи Маркова как 1 -го, так и 2-го порядка достигают наилучших показателей общей точности (1.18), точности (1.15), полноты (1.16) и F1 меры (1.17) при использовании с RF и ИНС.

Таблица 2.4 — Оценки качества классификации для пар из подхода к преобразованию текстов программ в векторы и классификатора, для набора, содержащего 1000 текстов программ из [152]

Вложение программ Алг. Общая точ. (1.15) Точность (1.16) Полнота (1.17) F1 мера (1.18)

word2vec (см. раздел 1.4.1) KNN 92.3 ± 3.1 92.6 ± 2.8 92.1 ± 3.1 92.2 ± 3.0

SVM 92.5 ± 2.3 92.7 ± 2.3 92.3 ± 2.3 92.3 ± 2.3

RF 93.6 ± 1.6 93.8 ± 1.5 93.5 ± 1.6 93.5 ± 1.6

ИНС 91.0 ± 1.8 91.3 ± 2.1 90.7 ± 1.8 90.8 ± 1.8

Цепь Маркова 1 -го порядка для AST (см. раздел 2.1) KNN 95.7 ± 1.9 96.2 ± 1.7 95.7 ± 1.9 95.7 ± 1.9

SVM 96.7 ± 0.7 97.0 ± 0.7 96.7 ± 0.6 96.7 ± 0.6

RF 97.8 ± 0.9 98.0 ± 0.8 97.8 ± 0.9 97.8 ± 0.9

ИНС 97.9 ± 1.2 98.0 ± 1.2 97.9 ± 1.2 97.9 ± 1.2

Цепь Маркова 2-го порядка для AST (см. раздел 2.1) KNN 92.5 ± 2.3 94.0 ± 1.4 92.4 ± 2.4 92.3 ± 2.4

SVM 97.0 ± 1.7 97.3 ± 1.5 96.9 ± 1.8 97.0 ± 1.7

RF 98.2 ± 1.3 98.3 ± 1.2 98.2 ± 1.3 98.2 ± 1.3

ИНС 97.5 ± 0.8 97.7 ± 0.8 97.5 ± 0.7 97.5 ± 0.7

code2vec (см. раздел 1.4.2) KNN 92.1 ± 1.3 92.5 ± 1.4 92.0 ± 1.3 92.0 ± 1.4

SVM 94.3 ± 1.9 94.5 ± 1.9 94.3 ± 1.8 94.2 ± 1.9

RF 90.9 ± 2.5 91.4 ± 2.3 90.3 ± 2.7 90.4 ± 2.6

ИНС 94.5 ± 1.2 94.6 ± 1.3 94.3 ± 1.3 94.2 ± 1.3

Гистограммы кодов операций (см. раздел 1.4.3) KNN 96.1 ± 0.9 96.3 ± 0.9 96.1 ± 0.9 96.1 ± 0.9

SVM 97.2 ± 1.2 97.4 ± 1.1 97.1 ± 1.3 97.2 ± 1.2

RF 97.0 ± 1.0 97.2 ± 0.8 97.0 ± 1.1 97.0 ± 1.0

ИНС 91.8 ± 1.6 92.4 ± 1.1 91.6 ± 1.7 91.6 ± 1.5

Гистограммы типов вершин AST (см. раздел 1.4.4) KNN 95.5 ± 0.9 95.7 ± 0.8 95.4 ± 1.1 95.4 ± 1.0

SVM 96.6 ± 1.4 96.7 ± 1.3 96.5 ± 1.4 96.5 ± 1.4

RF 97.2 ± 0.7 97.4 ± 0.7 97.2 ± 0.8 97.2 ± 0.8

ИНС 88.4 ± 1.4 89.0 ± 1.3 87.8 ± 1.4 87.9 ± 1.4

Как показано на рис. 2.13 и в таблице 2.4, увеличение порядка цепи Маркова на основе AST не дает заметных преимуществ, поскольку цепи Маркова 1 -го и 2-го порядка демонстрируют похожие характеристики при использовании совместно с RF. В случае KNN увеличение порядка цепи Маркова может снизить качество классификации. Согласно рис. 2.13 и таблице 2.4, вложения программ в векторное пространство на основе токенов word2vec работают значительно лучше с увеличением размера набора данных, показывая лучший результат по сравнению с векторами code2vec, используемыми совместно с RF, и по сравнению с вложениями на основе гистограмм, используемыми с ИНС.

Вложения на основе цепей Маркова 1 -го порядка, как правило, наименее чувствительны к используемому классификатору, показывая хорошие результаты в смысле (1.15), (1.16), (1.17) и (1.18) по сравнению со всеми рассмотренными классификаторами, согласно рис. 2.12 и рис. 2.13. С целью подтверждения или опровержения этого наблюдения была выполнена численная оценка чувствительности подходов к преобразованию программ в векторы, на основе анализа собранных данных, представленных в табл. 4 и табл. 5. Результаты оценки чувствительности приведены в разделе 2.3.

С целью статистической проверки наблюдаемого улучшения качества классификаторов при использовании векторных представлений программ на основе цепей Маркова 1 -го порядка, построение которых производится для AST, был применен критерий Уилкоксона (англ. Wilcoxon signed-rank test) [160] к оценкам качества различных пар, состоящих из вложения программ и алгоритма классификации. Для получения статистически репрезентативных результатов оценка качества каждой пары повторялась 10 раз, каждый раз наборы данных, содержащие 100 и 1000 программ, разбивались на 5 блоков, для оценки качества использовалась перекрёстная проверка по к блокам при к = 5 (см. рис. 2.6 и 2.7). Таким образом, каждое из полученных распределений оценок качества классификатора содержало в общей сложности 50 значений. Распределения, полученные для векторов программ на основе цепей Маркова 1 -го порядка, сравнивались с распределениями для других вложений, для каждого алгоритма классификации. Согласно нулевой гипотезе, два сравниваемых распределения не имеют статистически значимых различий [160]. Значениеp (англ. p-value) было установлено в 0.05.

В таблице 2.5 представлены результаты для набора данных, содержащего 100 программ (см. также рис. 2.12). В таблице 2.6 приведены результаты для набора данных, содержащего 1000 программ (см. также рис. 2.13). Знак «=» в таблицах 2.5 и 2.6 означает, что между сравниваемыми распределениями нет статистически значимых различий, знак «+» означает, что вложение программ на основе цепей Маркова 1 -го порядка превосходит вложение, с которым сравнивается, знак «-» означает, что вложение на основе цепей Маркова 1-го порядка приводит к ухудшению качества классификатора по сравнению с другим вложением.

Таблица 2.5 — Результаты статистического теста Уилкоксона, применяемого к распределению Fl-меры (1.17), полученному для вложений программ на основе цепей Маркова 1-го порядка, и распределениям Fl-меры, полученным для других вложений, используемых совместно с классификаторами на основе ККК, SVM, RF, ИНС, для набора, содержащего 100 программ из [152]

Классификатор KNN SVM RF ИНС

Вложение программ Знак ^-value Знак ^-value Знак ^-value Знак ^-value

word2vec + 0.004 + 0.004 + 0.004 + 0.004

Цепь Маркова 2-го порядка для AST + 0.011 = 0.250 = 0.916 = 0.652

code2vec = 0.820 = 0.359 + 0.004 + 0.008

Гистограммы кодов операций - 0.019 = 0.359 = 0.207 + 0.004

Гистограммы типов вершин AST - 0.004 = 0.164 = 0.498 + 0.004

Таблица 2.6 — Результаты статистического теста Уилкоксона, применяемого к распределению Fl-меры (1.17), полученному для вложений программ на основе цепей Маркова 1-го порядка, и распределениям Fl-меры, полученным для других вложений, используемых совместно с классификаторами на основе ККК, SVM, RF, ИНС, для набора, содержащего 1000 программ из [152]

Классификатор KNN SVM RF ИНС

Вложение программ Знак ^-value Знак ^-value Знак ^-value Знак ^-value

word2vec + 0.004 + 0.004 + 0.004 + 0.004

2-nd order AST-based Markov chain + 0.004 = 0.652 = 0.150 + 0.027

code2vec + 0.004 + 0.004 + 0.004 + 0.004

Histograms for Bytecode = 0.570 = 0.359 + 0.027 + 0.004

Histograms for AST = 0.426 = 0.074 + 0.042 + 0.004

Согласно таблицам 2.5 и 2.6, векторные представления программ на основе цепей Маркова 1-го порядка для AST превосходят вложения на основе цепей Маркова 2-го порядка на наборах данных, содержащих как 100, так и 1000 программ. В случае использования цепей Маркова совместно с SVM и RF отсутствуют статистически значимые различия в качестве классификации, достигаемом при использовании цепей 1 -го или 2-го порядка. В случае KNN и ИНС, напротив, между распределениями, полученными для цепей Маркова 1 -го и 2-го порядка, были выявлены статистически значимые различия (см. таблицу 2.5 и таблицу 2.6). Отсюда следует, что повышение порядка цепи Маркова выше 1 не даёт улучшения качества в смысле (1.17), и даже приводит к ухудшению качества, что делает цепи Маркова 1-го порядка для AST наиболее подходящими для практических применений.

Цепи Маркова 1-го порядка для AST превосходят гистограммы типов вершин AST и гистограммы кодов операций, когда такие векторные представления используются совместно с классификаторами на основе RF и ИНС. Как видно из таблиц 2.5 и 2.6, векторные представления на основе цепей Маркова также превосходят word2vec и code2vec. Векторные представления на основе гистограмм превосходят цепи Маркова на малом наборе данных при использовании совместно с KNN.

Как видно из таблиц 2.4 и 2.5, векторные представления программ на основе цепей Маркова 1-го порядка, используемые совместно с RF-классификатором, позволяют достичь наилучшего в рассматриваемой задаче качества классификации в смысле (1.15), (1.16), (1.17) и (1.18), что подтверждается результатами статистического тестирования (см. таблицу 2.5 и рис. 2.12, а также таблицу 2.6 и рис. 2.13). Алгоритм классификации векторных представлений текстов программ на основе цепей Маркова, построение которых производится для AST, повышает общую точность (1.18), точность (1.16), полноту (1.17) и Fl-меру (1.17) в среднем на 12% по сравнению с аналогами (см. таблицу 2.5 и таблицу 2.6).

2.2.3. Чувствительность векторных представлений программ к классификатору

Метод или алгоритм преобразования текстов программ в векторные представления, позволяющий получать классификаторы высокого качества при использовании совместно с различными алгоритмами классификации, потенциально имеет больше возможных применений. Так, например, алгоритм классификации KNN (см. Алгоритм 3) используется, когда большое количество размеченных данных для обучения трудно или невозможно получить, а алгоритмы RF, SVM, ИНС могут применяться в случае, если прецедентов в наборе для обучения достаточно много и требуется разработать классификатор наилучшего качества (см. таблицу 2.4). Таким образом, конкретный алгоритм классификации выбирается в зависимости от предметной области и решаемой задачи.

Оценка чувствительности к классификатору методов и алгоритмов преобразования текстов программ в векторные представления может выполняться для выявления векторного представления, позволяющего достигать высокого качества классификации вне зависимости от выбранного алгоритма классификации [76, 161]. Метод или алгоритм преобразования текстов программ в векторные представления может быть представлен как отображение Мт, где X — множество текстов

программ, т — число компонент в векторах. Для оценки качества классификаторов, как правило, используется перекрёстная проверка качества по к блокам (см. рис. 2.6) и метрика качества классификации, например, (1.15), (1.16), (1.17) или (1.18). Результатом оценки качества i-го классификатора проверкой по к блокам является множество Qt = [q1, q2,..., содержащее к оценок качества.

Для оценки качества отображения g: X ^ Мт, используемого совместно с n алгоритмами классификации, например, с KNN, SVM, RF и ИНС, основываясь на выбранной мере качества классификации, например, (1.15), (1.16), (1.17) или (1.18), и на результатах перекрёстной проверки качества каждого i-го классификатора по k блокам (см. рис. 2.6) предлагается метрика

= (2.6)

где Qt = {q1 qf,..., q^} — множество, содержащее k оценок качества i-го классификатора из n классификаторов, участвующих в оценке g: X ^ Rm, Q = Q2, Qt, — , Qn} — множество, содержащее множества оценок качества n классификаторов, ^(Qt) — среднее качество i-го классификатора, <(Qt) — среднеквадратическое отклонение для Qt, t = 1, n, i = 1, п.

Для оценки чувствительности к классификатору способа преобразования программ в векторы g: X ^ Rm предлагается метрика

<(Q) = Jzn=i(^(Qt)- ОТЭ)2^-^, (27)

где Qt = q2, , — множество, содержащее k оценок качества i-го классификатора, Q = { Q2, "■, Qt, "■, Qn} — множество, содержащее множества оценок качества n классификаторов, — среднее качество i-го классификатора, Д(^) вычисляется по формуле (2.6), <(Qt) — среднеквадратическое отклонение для Qt, t = 1, n, i = 1, п.

В формулах метрик качества (2.6) и чувствительности к классификатору (2.7) метода или алгоритма преобразования программ в векторные представления оценки качества классификаторов, имеющие меньшее стандартное отклонение <( Qt) (2.5), оказывают большее влияние на результат.

Так, например, при оценке чувствительности к классификатору векторных представлений программ на основе цепей Маркова 1-го порядка для AST на малом наборе данных, содержащем 100 программ, в результате перекрёстной проверки общей точности (1.18) KNN-классификатора по k блокам при k = 5 (см. рис. 2.6) было получено распределение значений (1.18) Q1, для SVM — распределение Q2, для RF — Q3, для ИНС — Q4. Как указано в таблице 2.3, Q1) = 81.0 и <( Q1) = 5.5, p(Q2) = 84.0 и <(Q2) = 7.3, p(Q3) = 92.0 и <(Q3) = 4.0, = 86.0 и <(Q4) = 7.3. Поскольку

Q1 = { Q1, Q2, Q3, Q4}, по формуле 2.7 легко рассчитать чувствительность векторных представлений программ на основе цепей Маркова 1-го порядка для AST к классификатору <r(Q1) « 4.45.

Аналогичным образом, при оценке чувствительности к классификатору векторных представлений на основе цепей Маркова 2-го порядка для AST на наборе данных, содержащем 100 программ, было получено распределение значений общей точности (1.18) для KNN, Q2 для SVM, Q3 для RF

и Q4 для ИНС. Как указано в таблице 2.3, Q1) = 70.0 и <( Q1) = 10.5, Q2) = 83.0 и <( Q2) = 6.8,

70

V-(Q3) = 91.0 и a(Q3) = 5.8, = 88.0 и a(Q4) = 8.1. Таким образом при Q2 = [QVQ2,Q3,Q4)

чувствительность к классификатору векторных представлений текстов программ на основе цепей Маркова 2-го порядка <r(Q2) « 7.36. Поскольку <r(Qi) < <r(Q2) (4.45 < 7.36), метод преобразования программ в векторные представления на основе цепей Маркова 1-го порядка для AST менее чувствителен к используемому классификатору, чем векторы на основе цепей Маркова 2-го порядка.

Результаты сравнения чувствительности к классификатору рассматриваемых методов и алгоритмов преобразования программ в векторные представления на наборе данных, содержащем 100 программ, с использованием метрик общей точности (1.18), точности (1.15), полноты (1.16) и F1 меры (1.17), рассчитанной по формуле (2.7), показаны на рис. 2.14.

Рисунок 2.14 — Результаты сравнения чувствительности к используемому классификатору методов и алгоритмов преобразования программ в векторные представления на наборе данных из 100 программ из исходного набора [152] на основе данных таблицы 2.3 (чем меньше, тем лучше)

Согласно рис. 2.14, code2vec и цепи Маркова 1-го порядка наименее чувствительны в смысле метрики (2.7) к используемому классификатору на наборе данных, содержащем 100 программ, а word2vec и гистограммы типов вершин AST — наиболее чувствительны.

Результаты сравнения чувствительности к классификатору рассматриваемых методов и алгоритмов преобразования программ в векторные представления на наборе данных, содержащем 1000 программ из исходного набора [152], с использованием метрик (1.18), (1.15), (1.16) и (1.17), рассчитанной по формуле (2.7), показаны на рис. 2.15.

0.030

е 0.025

•Г 0.020

0.015

О 0.010

0.005

0.000

0.035 -

i 0.030

о

t 0.025 -

0.020

8 0.015

0.010 -

0.005

0.000

Рисунок 2.15 — Результаты сравнения чувствительности к используемому классификатору методов и алгоритмов преобразования программ в векторные представления на наборе данных из 1000 программ из исходного набора [152] на основе данных таблицы 2.4 (чем меньше, тем лучше)

Как показано на рис. 2.15, цепи Маркова 1-го порядка и word2vec являются наименее чувствительными в смысле метрики (2.7) к алгоритму классификации на наборе из 1000 программ, решающих задачи 11 типов. Это соответствует наблюдениям, описанным в разделе 2.2.2: качество векторных представлений программ на основе токенов улучшается с увеличением размера набора данных.

Согласно рис. 2.14 и рис. 2.15, цепь Маркова 1-го порядка для AST — это наименее чувствительное к используемому алгоритму классификации векторное представление, независимо от размера набора данных. Использование цепей Маркова 1-го порядка позволяет понизить в 1.43—4 раза чувствительность к алгоритму классификации. Увеличение порядка цепи увеличивает чувствительность к классификатору, при этом согласно таблицам 2.3 и 2.4 KNN-классификатор показывает худшее качество классификации с увеличением порядка цепи. Это делает цепи Маркова 1-го порядка для AST наиболее подходящими для практических применений.

2.3. Бинарная классификация для обнаружения семантического сходства программ

В работе [162], опубликованной вскоре после выхода работ [147, 148], в которых был впервые предложен и исследован подход к преобразованию программ в векторные представления на основе цепей Маркова 1-го порядка, построение которых выполняется для AST (см. раздел 2.2), описывается

средство обнаружения семантического сходства программ Amain (англ. AST-based Markov chain). В отличие от работ [147, 148], где рассматривается задача кластеризации и многоклассовой классификации, работа [162] посвящена задаче бинарной классификации, решением которой является классифицирующее отображение а:ХхХ^ Y, позволяющее определять, являются ли две поданные на вход программы семантически схожими, причём Y = {0,1}, а X — множество текстов программ.

Для решения задачи бинарной классификации в [162] предлагается преобразовать AST двух программ на языке Java из множества программ X в цепи Маркова 1 -го порядка по алгоритму, схожему с Алгоритмом 8 — вершинами графа переходов цепей Маркова, построенных для AST, являются типы вершин AST. После этого две матрицы смежности полученных графов переходов цепей Маркова 1-го порядка предлагается сравнить с использованием евклидова расстояния (1.20), манхэт-тенского расстояния (1.22), расстояния Чебышёва (1.23), косинусного расстояния (1.41). Извлечённый таким образом вектор признаков пары программ принадлежит векторному пространству М4. После этого предлагается выполнить обучение классификатора на основе RF (см. Алгоритм 4) для аппроксимации отображения а*: М4 ^ Y, Y = {0,1}, позволяющего по вектору признаков пары программ определить, являются ли они семантически схожими.

Для оценки качества разных способов обнаружения семантического сходства программ в [162] использовались такие меры качества бинарной классификации, как точность (1.11), полнота (1.12), Fl-мера (1.13), рассматривался набор Google Code Jam, содержащий 275 570 семантически схожих программ и 270 000 семантически различающихся программ на языке Java. Результаты, полученные при помощи описанного в [162] метода бинарной классификации на основе цепей Маркова для AST Amain, сравнивались с результатами, полученными при помощи таких методов и алгоритмов бинарной классификации программ, как RtvNN [163], DeepSim [164], FCCA [165], Deckard [166], ASTNN [167], TBCNN [168]. Результаты, описанные в [162], представлены в таблице 2.7.

Таблица 2.7 — Оценки качества методов определения семантического сходства программ

Группа методов Метод Точность (1.11) Полнота (1.12) F1-Mepa (1.13)

На основе токенов RtvNN [163] 0.90 0.20 0.33

На основе графов программ DeepSim [164] 0.82 0.71 0.76

FCCA [165] 0.90 0.95 0.92

На основе AST программ Deckard [166] 0.44 0.45 0.44

ASTNN [167] 0.87 0.95 0.91

TBCNN [168] 0.89 0.91 0.90

Цепи Маркова Amain [162] 0.91 0.93 0.92

Из результатов, представленных в таблице 2.7, можно сделать вывод, что метод Amain [162], основанный на построении цепей Маркова 1-го порядка для AST, и метод FCCA [165] позволяют достичь наилучшей полноты (1.12) и Fi-меры (1.13) в задаче бинарной классификации пар программ на языке Java из набора Google Code Jam для обнаружения их семантического сходства. При этом метод Amain [162] позволяет достичь наилучшей точности (1.11). Результаты, опубликованные в работе [162], согласуются с результатами, полученными автором данной диссертационной работы [76, 147, 148], и подтверждают преимущество использования представлений программ на основе цепей Маркова 1-го порядка, построение которых выполняется для AST, в задачах обнаружения алгоритма или определения сходства реализованных в программах алгоритмов.

2.4. Выявление подходов к решению задач в наборе текстов программ

2.4.1. Разбиение набора программ на кластеры на основе реализованных алгоритмов

Предложенный подход к преобразованию текстов программ в векторные представления на основе цепей Маркова для AST, позволяющий достичь высокого качества классификации как при определении типа задачи, решаемой программой [76], так и при выявлении семантического сходства программ [162], может быть использован для повышения качества разбиений наборов программ на кластеры в зависимости от реализованных в программах алгоритмов [147].

Рассматриваемая в данном разделе задача разбиения конечного множества программ X с X на к непересекающихся подмножеств (кластеров) в случае, если число к известно заранее, сводится к построению отображения а: X ^ F, ставящего в соответствие каждой программе х £ X метку кластера у £ F, где Y = {1,2,..., fc). Метка кластераy здесь обозначает номер алгоритма, причём считается, что в каждой программе х из набора программ X реализован один из к известных алгоритмов.

Для оценки качества векторных представлений текстов программ на основе цепей Маркова для AST в задаче кластеризации был сформирован малый набор X из 30 программ, входящих в [152]. Выбранные 30 программ содержали решения уникальных задач типа 4 (см. Приложение А), реализующих разные рекуррентные формулы тремя разными способами. Предварительная разметка 30 текстов программ, включенных в набор, проводилась вручную — каждой программе х £ X была поставлена в соответствие метка у £ Y при Y = {1, 2, 3). Это обеспечило возможность оценки качества автоматического разбиения набора X на 3 кластера сравнением результатов разбиения с метками классов yj, поставленными в соответствие каждой программе Xj вручную. Программы, реализующие рекуррентные формулы тремя разными способами, представлены в наборе X в равных долях.

Примеры различающихся способов решения уникальных задач на реализацию рекуррентной формулы из анализируемого набора данных X, основанного на [152], представлены на рис. 2.16.

def main(n): def main(n): def main(n):

if n == 0: mas = [-0.3] res1 = -0.31

return -0.68 for i in range(1, n + 1): res2 = -0.44

if n == 1: m = mas[i-1] ** 3 / 23 for i in range(1, n):

return 0.56 x = m + mas[i-1] + mas[i-1] ** 2 temp = res1 - res2 ** 3 / 38

if n >= 2: mas.append(x) res1 = res2

c = math.ceil(main(n - 2)) ** 2 return mas[n] res2 = temp

return main(n - 1) + 47 * c return temp

(а) (б) (в)

Рисунок 2.16 — Примеры программ на языке Python из анализируемого набора данных X, программы реализуют уникальные рекуррентные формулы при помощи разных алгоритмов: а) рекурсивная функция; б) цикл и список с вычисленными значениями; в) цикл и переменные

Для оценки качества результатов автоматического разбиения набора текстов программ на 3 кластера использовались такие меры качества, как показатель чистоты кластеризации [169] и индекс Рэнда [170]. Данные меры позволяют численно оценить, насколько полученное алгоритмом кластеризации разбиение на кластеры С похоже на разбиение М, произведённое экспертом вручную. Показатель чистоты кластеризации (англ. Purity) [169] вычислялся как:

1 I I

Purity(C,М) =-Ic.ecmax|CinMy|, (2.8)

п 1 м;-ем' J1

где n — число объектов в X, С = { С^, С2,..., Cfc} — полученное от алгоритма кластеризации разбиение X на k непересекающихся подмножеств Сх, С2,..., Cfc, М = {Мх, М2,..., Mfc} — разбиение множества X на k кластеров Mx, М2,..., Mfc, причём X = Uf=x С, а X = Uf=x Mj. Индекс Рэнда (англ. Rand Index) [170] вычислялся как:

Rand(C,M)=M, (2.9)

А = {(Oj, Oy) | Oj е Сг л Oy е Сг л Oj е л оу е Mft), (2.10)

в = {(Oj, Oy) | Oj е Ch Л Oy е Сг2 Л Oj е Mfti л Oy е M^}, (2.11)

где n — число объектов в X, Сг, С^, С^ е С, С = {С-^ С2, ..., Cfc} — полученное в результате кластеризации разбиение X на k кластеров, Mft, Mfti, Mftz е М, М = {Ml, M2, ..., Mfc} — эталонное разбиение X на k кластеров, i ф _/, 1 < i ,_/ < п, ф /2, 1 < Z, /2 < fc, ф h2, 1 < h, h2 < fc.

Разбиение набора программ X на кластеры осуществлялось по схеме, показанной на рис. 2.17.

Рисунок 2.17 — Схема процесса разбиения набора текстов программ X на к кластеров

Как показано на рис. 2.17, сначала на основе набора текстов программ X производилось построение матрицы попарных расстояний D, принадлежащей пространству Мпхп, где п = |Х|. Полученная матрица попарных расстояний D подавалась на вход алгоритму агломеративной иерархической кластеризации [171, 172], использовалась реализация алгоритма из библиотеки sklearn [101] и метод средней связи как компромиссный вариант между методами одиночной и полной связи [172].

Агломеративный алгоритм иерархической кластеризации начинает работу с создания кластеров, каждый из которых содержит единственный объект из X. Затем наиболее похожие кластеры объединяются до тех пор, пока число кластеров не равно fc. При выполнении агломеративной иерархической кластеризации по методу средней связи расстояние между двумя кластерами Са и считается равным среднему расстоянию между принадлежащими данным кластерам объектами:

(2.12)

где Ca и Сь — сравниваемые кластеры, |Са| — число объектов, принадлежащих кластеру Са, |СЬ| — число объектов, принадлежащих кластеру Сь, Oj — объект, принадлежащий кластеру Ca, — объект, принадлежащий кластеру , d(Oj, oft) — расстояние между объектами Oj и , вычисляемое на этапе построения матрицы попарных расстояний D (см. рис. 2.17).

Матрица попарных расстояний D между объектами из набора программ X для кластеризации (см. рис. 17) может быть построена разными способами. В процессе экспериментальных исследований сравнивались 3 метода построения матрицы D.