УДК 004.052

Методы машинного обучения для обнаружения дефектов программного обеспечения

Климов Илья Сергеевич – студент Московского государственного технического университета

Аннотация: В данной статье рассмотрены и проанализированы основные методы машинного обучения с целью обнаружения дефектов программного обеспечения (далее – ПО), описаны метрики и проведено сравнение методов машинного обучения для обнаружения дефектов ПО. Также проведена формализация задачи обнаружения дефектов ПО в виде диаграммы в нотации IDEF0. В результате к наиболее эффективным методам машинного обучения отнесены алгоритм случайного леса и бустинг, как его модификация. Однако, в определенных условиях целесообразно применение таких методов машинного обучения, как наивный баиесовский классификатор и метод опорных векторов.

Ключевые слова: дефект, искусственный интеллект, машинное обучение, обнаружение, методы.

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

Прогнозирование дефектов ПО является важной частью цикла разработки программного продукта. Ведь наличие дефектов сильно влияет на надежность, качество и стоимость обслуживания. Прогнозирование модулей с ошибками до развертывания повышает общую производительность [1]. Знание о компонентах, содержащих наибольшее число дефектов, позволяет распределить ресурсы тестирования так, чтобы в первую очередь проверялись компоненты с высокой вероятностью наличия дефектов. Сложно составить правила при поиске дефектов, так как могут встретиться совершенно разные ошибки, поэтому довольно известными являются методы машинного обучения, которые решают данную проблему, обучаясь на примерах. Исследователи применяли различные алгоритмы для решения данной задачи. На рисунке 1 представлена общая схема процесса обучения модели обнаружения дефектов ПО.

Рисунок 1. Процесс обучения модели обнаружения дефектов ПО.

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

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

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

Наивный байесовский классификатор

Наивный байесовский классификатор – простой классификатор, основанный на применении теоремы Байеса с наивным предположением о независимости. Для каждого класса рассчитывается вероятность по теореме Байеса – формула (1), и объект  считается принадлежащим классу ( ), если при этом классе достигается наибольшая апостериорная вероятность: . Для рассматриваемой задачи имеются два класса в зависимости от того, есть дефект в программе или нет.

где  – вероятность того, что объект принадлежит классу ;

и – априорные вероятности класса и объекта  (последняя не влияет на выбор класса и может быть опущена).

Если же сделать «наивное» предположение, что все признаки, описывающие классифицируемые объекты, не связаны друг с другом, то можно вычислить как произведение вероятностей встретить признак среди объектов класса :

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

Несмотря на простоту, наивные байесовские классификаторы могут иметь достаточно высокую точность и производительность по сравнению с другими алгоритмами. К достоинствам также можно отнести малое количество данных, необходимых для обучения [8].

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

В случае решения задачи методом опорных векторов рассматривается задача классификации на два непересекающихся класса, в котором объекты описываются мерными вещественными векторами. Необходимо найти и построить гиперплоскость вида: , разделяющую объекты на два подмножества с максимальной граничной областью. В случае линейной разделимости – построение сводится к решению задачи условной оптимизации, которая с помощью методов Лагранжа может быть сведена к задаче квадратичного программирования. Однако в реальных задачах такое встречаются крайне редко. Для решения линейно неразделимых задач обычно применяют два подхода:

1. Ослабить жесткие ограничения, что приводит к так называемой «мягкой» граничной области – позволяет некоторым точкам нарушать ограничения стандартного метода. В частности, вводятся дополнительные переменные для учета количества ошибок классификации.
2. Применить ядерные функции для линеаризации нелинейных задач – идея заключается в определении ядерной функции, основанной на скалярном произведении данных как нелинейного перехода от пространства входных данных к пространству с большим количеством измерений с целью сделать задачу линейно разделимой. В результате использование ядерных функций делает алгоритм нечувствительным к размерности пространства [9].

Дерево решений

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

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

Преимущества:

• интерпретируемость – позволяют строить правила в форме, понятной эксперту;
• автоматический отбор признаков – признаки в вершины дерева выбираются автоматически из набора признаков;
• управляемость – если некоторые примеры классифицируются неправильно, можно заново обучить только те вершины дерева, из-за которых это происходит. Кроме того, при тренировке разных поддеревьев могут оказаться более эффективными разные алгоритмы обучения.

Недостатки:

• зависимость от сбалансированности обучающих примеров – при неправильных пропорциях классов в обучающей выборке дерево обучится некорректно;
• требуются методы предотвращения переобучения – явление переобучения возникает из-за излишней сложности модели, когда обучающих данных недостаточно. При их нехватке высока вероятность выбрать закономерность, которая выполняется только на этих данных, но не будет верна для других объектов;
• экспоненциальное уменьшение обучающий выборки – так как после обучения каждой вершины дерева происходит разделение на два подмножества, то на каждом следующем уровне дерева обучающее множество вершины содержит все меньше и меньше примеров [10].

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

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

Пусть имеется множество деревьев решений, каждое из которых относит объект к одному из классов . Считаем, что если , то дерево относит объект к одному из классов . При использовании алгоритма простого голосования для каждого класса подсчитывается число деревьев, относящих объект к данному классу – формула (4).

Ответом леса является тот класс, за который подано наибольшее число голосов:

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

Бустинг

Бустинг – модификация алгоритма случайного леса, обучение происходит путем последовательного обучении нескольких моделей для повышения точности всей системы. Выходным данным отдельных деревьев присваиваются веса. Затем неправильным классификациям из первого дерева решений присваивается больший вес, после чего данные передаются в следующее дерево. После многочисленных циклов бустинг объединяет «слабые» классификаторы в один алгоритм [11].

Существуют две основные разновидности бустинга: адаптивный и градиентный.

Адаптивный бустинг (англ. AdaBoost)

одна из самых ранних реализаций бустинга, которая адаптируется и самостоятельно корректирует классификаторы в каждой итерации бустинга. Тренировочным примерам назначаются веса . Так как они имеют вероятностную природу, для них выполняется условие: . Начальное распределение весов является равномерным. Происходит обучение первого дерева, с помощью которого производится классификация тренировочных примеров. Веса правильно классифицированных примеров снижаются, неправильно – повышаются. Следующее дерево строится с учетом обновленных весов, и так далее до достижения заданного количества деревьев или требуемой ошибки классификации [10].

Градиентный бустинг (англ. Gradient Boosting)

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

Как правило, результаты классификации помечаются как положительные (имеются дефекты) и отрицательные (дефекты отсутствуют). Для оценки качества работы полученных моделей используются различные метрики. Так, в статьях [3-7] при сравнении результатов рассматриваются такие метрики, как accuracy, точность (precision), полнота (recall) и F-мера. Для их определения используется матрица матрица ошибок, которая содержит 4 ячейки:

• верно-положительные объекты (TP) – объекты, которые были верно классифицированы как положительные;
• верно-отрицательные объекты (TN) – объекты, которые были верно классифицированы как отрицательные;
• ложно-положительные объекты (FP) – объекты, которые были ложно классифицированы как положительные;
• ложно-отрицательные объекты (FN) – объекты, которые были ложно классифицированы как отрицательные.

1. Accuracy (точность) – широко используемая метрика, представляет собой отношение всех правильных прогнозов к общему числу предсказанных образцов (формула (6)). В ряде задач (с неравными классами) метрика может являться неинформативной. 
2. Precision (точность) – это доля прогнозируемых положительных результатов, которые действительно относятся к этому классу, от всех положительно предсказанных объектов – формула (7). 
3. Recall (полнота) – пропорция всех верно-положительных предсказанных объектов к общему количеству действительно положительных (формула (8)). Чем выше значение полноты, тем меньше положительных примеров пропущено в классификации.
4. F-measure (F-мера) – взвешенное гармоническое среднее полноты и точности (формула (9)). Этот показатель демонстрирует, как много объектов классифицируется моделью правильно, и сколько истинных экземпляров она не пропустит [12].

Для сравнения рассмотренных методов использованы результаты, описанные в статьях [2-7]. Модели обучались на данных, представленных в репозитории NASA [13]. Язык программирования, преобладающий в данных, – C++. В таблице 1 отображены средние арифметические значения для каждой из метрик по всем наборам данных.

Таблица 1. Сравнительная таблица результатов работы алгоритмов.

Метрики Алгоритмы	Accuracy (точность)	Precision (точность)	Recall (полнота)	F-measure (F-мера)
Наивный байесовский классификатор	0.795	0.845	0.803	0.849
Метод опорных векторов	0.841	0.901	0.879	0.902
Дерево решений	0.823	0.845	0.878	0.889
Алгоритм случайного леса	0.847	0.903	0.883	0.903
Градиентный бустинг	0.845	0.859	0.863	0.890
Адаптивный бустинг	0.835	0.858	0.861	0.889

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

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

5. Sharma, T. A Survey on Machine Learning Techniques for Source Code Analysis [Текст] / T. Sharma, M. Kechagia, S. Georgiou, R. Tiwari, I. Vats, H. Moazen, F. Sarro. – 2022. – С. 11-13.
6. Assim, A. Software Defects Prediction using Machine Learning Algorithms [Текст] / A. Assim, Q. Obeidat, M. Hammad // 2020 International Conference on Data Analytics for Business and Industry: Way Towards a Sustainable Economy (ICDABI) – 2020. – С. 1-6.
7. Shah, M. Software Defects Prediction Using Machine Learning [Текст] / M. Shah, N. Pujara – 2020. – С. 1-5.
8. Iqbal, A. Performance Analysis of Machine Learning Techniques on Software Defect Prediction using NASA Datasets [Текст] / A. Iqbal, S. Aftab, U. Ali, A. Husen // International Journal of Advanced Computer Science and Applications – 2019. – С. 1-6.
9. Aleem, S. Comparative performance analysis of machine learning techniques for software bug detection / S.Aleem, L.F. Capretz, F. Ahmed – 2015. – С. 1-9.
10. Cetiner, M. A Comparative Analysis for Machine Learning based Software Defect Prediction Systems [Текст] / M. Cetiner, O.K. Sahingoz // 11th International Conference on Computing, Communication and Networking Technologies – – С. 1-7.
11. Bhandari, G.P. Machine learning based software fault prediction utilizing source code metrics [Текст] / G.P. Bhandari, R. Gupta // IEEE 3rd International Conference on Computing, Communication and Security (ICCCS), Kathmandu (Nepal) – 2018 – С. 1-6.
12. Шитиков, В.К. Классификация, регрессия, алгоритмы Data Mining с использованием R [Текст] / В.К. Шитиков, С.Э. Мастицкий // Тольятти, 2017.
13. Федотов, Д.В. О решении задачи классификации методом опорных векторов [Текст] / Д.В. Федотов // Математические методы моделирования, управления и анализа данных – 2013 – С. 1-3.
14. Кафтанников, И.Л. Особенности применения деревьев решений в задачах классификации [Текст] / И.Л. Кафтанников, А.В. Парасич // Вестник ЮУрГУ. Серия «Компьютерные технологии, управление, радиоэлектроника» – 2015. – С. 26-32.
15. Amazon Web Services. Что такое бустинг? [Электронный ресурс]: Режим доступа URL: https://aws.amazon.com/ru/what-is/boosting/ (Дата обращения 23.11.2022).
16. Дудченко, П.В. Метрики оценки классификаторов в задачах медицинской диагностики [Текст] / П.В. Дудченко // Молодежь и современные информационные технологии: сборник трудов XVI Международной научно-практической конференции студентов, аспирантов и молодых ученых – – С. 164-165.
17. NASA. Promise software engineering repository [Электронный ресурс]: Режим доступа URL: http://promise.site.uottawa.ca/SERepository/datasets-page.html (Дата обращения: 29.11.2022).