====== Предсказание дефектов в программном обеспечении с помощью Байесовских сетей. ======
//(Дмитрий Персиянов, МФТИ ФИВТ 394, декабрь 2016. На основе [[http://link.springer.com/article/10.1007/s10664-012-9218-8|этой статьи]])//

===== 1 Введение =====

Разработка программного обеспечения без дефектов -- очень сложный процесс. Почти всегда будут присутствовать ошибки, которые очень трудно заметить, даже если методологии разработки ПО были корректно применены. Из-за дефективных модулей в системе этап ее поддержки оказывается проблемным для пользователей и стоит денег заказчику системы. Таким образом, очень важно уметь предсказывать дефекты в компонентах системы перед ее деплоем. Это ведет к уменьшению общей стоимости проекта и повышает общий шанс его успеха.

В ранних публикациях о предсказании дефектов в ПО преимущественно использовались признаки из статического анализа кода. Потом стало понятно, что пользуясь только этими признаками, построить модель предсказания дефектов, которая будет обладать большой предиктивной силой, очень трудно. Соответственно, необходимо исследовать другие признаки. В поддержку этой идеи, авторы утверждают, что если ПО имеет дефекты, то это может быть вызвано одной из следующих причин:
  * Спецификация проекта неверна из-за противоречивых требований или упущенной функциональности. Возможно, она очень сложна для понимания, либо плохо документирована.
  * Плохой дизайн системы, не учитывающий все требования или учитывающий неверным образом.
  * Разработчики недостаточно квалифицированы для реализации данного проекта.
  * Проблема в project management’е, плохое следование методологиям разработки ПО.
  * Система плохо тестируется.

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


===== 2 Байесовские сети =====

Байесовская сеть -- это направленный граф <latex> G </latex> без циклов, состоящий из множества <latex> E </latex> ребер и множества <latex> V </latex> вершин, который отображает совместное распределение множества переменных. Вершинами являются переменные, а ребро отражает влияние одной переменной на другую. Переменными будут являться наши метрики впоследствии.

Пусть <latex> X = \{X_1, X_2, \dots, X_n\} </latex> это множество непрерывных или дискретных переменных. Распределение переменной <latex> X_i </latex> записывается как <latex> P(X_i|a_{x_i}) </latex>, где <latex> a_{x_i} </latex> -- родители вершины <latex> X_i </latex> в графе. Если у <latex> X_i </latex> нет родителей, то априорное мы считаем, что имеем априорное распределение <latex> P(X_i) </latex>.

Совместное распределение переменных с помощью формулы Байеса может быть записано в следующем виде:
<latex> P(X) = \prod_{i=1}^n P(X_i|a_{x_i}) </latex>

С другой стороны, используя формулу Байеса и значения переменных-родителей, мы можем посчитать апостериорную вероятность переменной. В Байесовских сетях есть два типа вывода: вывод следствий из причин (causal inference) и вывод причин из следствий (diagnostic inference). То есть, имея значения переменных, можно вычислять вероятность переменных-родителей.

Проиллюстрируем это примером:
{{ :mdd:1_.png?600 |}}

Слева изображена Байесовская сеть. Объясним значения переменных:
  * ED (experienced developers) -- бинарная переменная, означающая, опытные ли разработчики в проекте
  * UT (unit testing) -- бинарная переменная, означающая, применяется ли юнит тестирование при разработке проекта
  * FP (fault prone, defectiveness) -- бинарная переменная, говорящая нам о том, есть ли дефекты дефекты в нашем ПО.

Таким образом, вероятность переменной FP означает вероятность возникновения ошибок в ПО. А это как раз то, что мы хотим предсказывать.

Например, мы можем посчитать вероятность отсутствия дефектов при условии опытных разработчиков:
<latex> P(FP|ED) = P(FP|ED,UT)P(UT|ED) + P(FP|ED, not UT)P(not UT|ED) </latex>.
Далее, т.к. переменные ED и UT независимы, то <latex> P(UT|ED) = P(UT) </latex> и
<latex> P(FP|ED) = P(FP|ED,UT)P(UT) + P(FP|ED, not UT)P(not UT) </latex>.

Используя значения из таблицы, получаем <latex> P(FP|ED) = 0.34 </latex>. Это пример causal inference.

Мы также можем записать:
<latex> P(ED|FP) = \frac{P(FP|ED)P(ED)}{P(FP} </latex>.

Найти <latex> P(FP) </latex> мы можем, пользуясь всеми значениями таблицы и формулой полной вероятности. Следовательно, мы можем найти <latex> P(ED|FP) </latex>. Это пример diagnostic inference.

===== 2.1 Алгоритм K2 =====

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

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

Алгоритм K2, предложенный Cooper и Herskovits в 1992 году, ищет наиболее оптимальную структуру сети используя следующую эвристику. Ему на вход подается порядок на переменных. Он не обязательно точен и должен задавать структуру сети, это грубые интуитивные предположения о зависимости переменных друг от друга. Базируясь на нем, алгоритм ищет для каждой переменной родителей таким образом, что их добавление увеличит функционал для Байесовской сети.

Если добавление любой переменной <latex> X_j </latex> к множеству родителей переменной <latex> X_i </latex> не приводит к увеличению функционала, то алгоритм прекращает поиск родителей для <latex> X_i </latex>.

Псевдокод алгоритма выглядит так:
{{ :mdd:2bayes.png?600 |}}

Подробнее про алгоритм можно почитать [[http://web.cs.wpi.edu/~cs539/f12/Projects/k2_algorithm.pdf|здесь]].

===== 3 Предлагаемый подход =====

Стоит отметить, что количество метрик очень большое и не все из них имеют высокую предиктивную способность. Перечислим некоторые из них:

  * SLOC -- количество строк кода
  * CBO -- среднее количество классов, с которыми связан какой-то конкретный класс
  * WMC -- взвешенная сложность методов / класс, сложность определяется по-разному, в простейшем случае она равна 1 и WMC равно числу методов.
  * NOC -- количетсво детей класса
  * Подробнее про различные метрики можно прочитать [[https://habrahabr.ru/company/intel/blog/106082/|здесь]].

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

Как уже было сказано, ранние исследования использовали в основном метрики из статического анализа кода. Такие метрики могут не учитывать критически важные признаки наличия дефектов, например плохой анализ требований или дизайн архитектуры, неопытных разработчиков, плохую документацию, финансовые проблемы в проекте. К сожалению, эти факторы не всегда можно формализовать и сформировать на их основе новые метрики. Авторы добавляют две новые метрики,  LOCQ -- качество кода, и NOD -- количество разработчиков в проекте. Вторая метрика ясна, первая же считается с помощью плагина PMD для Netbeans. Плагин анализирует код и ищет возможные проблемы, например баги, “мертвый” код (недостижимые точки в коде), не оптимально написанные участки кода, усложненных выражений, а также дублирование кода. В качестве метрики берется число обнаруженных плагином проблем во всех классах и модулях системы.

Обучение сети проводилось на кодах проектов Apache (см. таблицу ниже).
{{ :mdd:3bayes.png?600 |}}

Для некоторых из них метрика NOD была известна (для каждого класса в проекте). Для других (Ant, Lucene и Synapse) данных по количеству разработчиков нет, и поэтому авторы сделали два эксперимента: сеть с метрикой NOD и сеть без нее. 

С целью получить более стабильные результаты, авторы проводили 10-холдаут валидацию с размером обучающей выборки 67%.

В итоге, авторы предложили следующую архитектуру сети (это ее общий вид, конкретные сети для каждого датасета будут отличаться):
{{ :mdd:4bayes.png?600 |}}

Здесь ребро из вершины <latex> x </latex> в вершину <latex> y </latex> означает, что переменная <latex> y </latex> влияет на значение <latex> x </latex>. Стоит заметить, что Metric5, Metric6, Metric7 наиболее важные, так как напрямую влияют на устойчивость системы к дефектам. Остальные метрики влияют на устойчивость косвенным образом.

Для того чтобы обучить Байесовскую сеть с помощью K2 алгоритма, необходимо задать порядок на вершинах сети.  Приведем сразу порядок, предложенный авторами, а затем поясним интуицию за ним.
{{ :mdd:bayes5.png?600 |}}

Метрики были расположены в три группы, причем метрики из Group1 сильнее влияют на целевую переменную, чем Group2, а метрики из Group2 сильнее, чем из Group3.

Интуитивно, чем больше общий размер кодовой базы, тем больше вероятность того, что в нем есть ошибка. Лучшим образом размер проекта отображает LOC. Также, хорошо отображает его и CBO -- количество взаимодействий между классами. Третей метрикой в первой группе была взята LOCQ, получаемая с помощью статического анализатора PMD и отображающая общее качество кода.

===== 4 Эксперименты и результаты =====
Как уже было сказано, авторы измеряли качество на исходных кодах проектов Apache. Были выбраны проекты достаточно большие для того, чтобы можно было проводить кросс-валидацию.
Из-за смещенности классов (количество дефективных модулей сильно меньше количества модулей без дефектов) авторы выбрали метрику AUC-ROC.
{{ :mdd:bayes6.png?600 |}}

Далее приведем структуры Байесовских сетей для разных датасетов, которые получились после оптимизации алгоритмом K2. Это дает понимание метрик, которые сильнее всего кореллируют с целевой переменной.
{{ :mdd:bayes7.png?400 |}}

Наиболее сильными метриками на коде проекта Ant оказались LOC и LOCQ. Справа показаны таблицы условных распределений. Верхняя таблица <latex> P(bug|loc) </latex>, а нижняя <latex> P(loc|cbo) </latex>. Сразу заметны сильные корреляции между переменными, что означает высокую предиктивную способность.
Также видно, что метрики DIT и NOC алгоритм K2 решил не включать в сеть, что служит признаком их низкой важности. Что, впрочем сходится с реальностью. DIT -- depth of inheritance tree, NOC -- number of childs. Почти во всех больших проектах есть интерфейсы, абстрактные классы и наследование. Это скорее упрощает разработку, чем усложняет ее (при условии правильного дизайна наследования).

Взглянем на датасет Tomcat:
{{ :mdd:bayes8.png?400 |}}

Здесь LOCQ коррелирует с целевой переменной меньше, чем CBO. Также приводится таблица условной вероятности <latex> P(loc, bug|cbo) </latex>. CBO очень сильно коррелирует с человеческой интуицией и целевой переменной.

Наконец, Apache Poi:

{{ :mdd:bayes9.png?400 |}}


----


Отдельно проводились эксперименты с метрикой NOD, чтобы изучить ее влияние на результат. Приведем полученные сети на датасетах Ant, Tomcat и Poi.

Для всех датасетов наблюдается положительная корреляция между NOD и BUG. Чем больше разработчиков, тем больше вероятность дефекта в системе.

{{ :mdd:bayes10.png?600 |}}

ополнительно, авторы исследуют зависимость отсутствия ошибок в системе при условии, что NOD = 1 и NOD > 1 (для одного класса в коде, а не всего проекта). Авторы, с помощью теста Стьюдента показывают статистическую значимость своих результатов. То есть один разработчик на класс -- лучше, чем несколько. Таким образом, авторы подтверждают гипотезу о том, что поговорка “у семи нянек дитя без глазу” работает и в разработке программного обеспечения.

{{ :mdd:bayes11.png?600 |}}

===== 5 Выводы =====

В статье авторы, предлагая новый метод, основанный на Байесовских сетях, проводят исследование влияния различных метрик качества ПО на вероятность наличия ошибок в коде. Этот же метод используется и для предсказания вероятности наличия ошибки. Авторы показывают, что метрики LOC и LOCQ сильнее всего влияют на вероятность наличия ошибки. С другой стороны, влияние метрик NOC и DIT ограничено и им не следует доверять.

Основной вклад статьи заключается в следующих пунктах:
  * Проведено исследование на 9 различных датасетах. Показано, что одни метрики могут хорошо влиять на целевую переменную на одних данных и в то же время слабо коррелировать с ней на других.
  * Предложена новая метрика LOCQ, основанная на статическом анализаторе кода. Показана ее важность (она встала наряду с общеизвестными метриками CBO и WMC) для предсказания наличия ошибок в коде.
  * Исследовано влияние метрики NOD и показано, что следует ограничивать число разработчиков, работающих над одним и тем же куском кода.
  * Показано, что метрики NIC и DIT почти всегда не имеют никакого влияния на целевую переменную.
  * Так как LOC показал очень хорошую предиктивную способность, авторы верят, что можно использовать лишь эту метрику для быстрого предсказания (пусть и с меньшей точностью) наличия дефекта, так как эту метрику очень просто измерить.