Статья 'Алгоритмы автоматизированного выявления связей между элементами проекта разработки программного обеспечения' - журнал 'Кибернетика и программирование' - NotaBene.ru
по
Меню журнала
> Архив номеров > Рубрики > О журнале > Авторы > О журнале > Требования к статьям > Редакция и редакционный совет > Порядок рецензирования статей > Политика издания > Ретракция статей > Этические принципы > Политика открытого доступа > Оплата за публикации в открытом доступе > Online First Pre-Publication > Политика авторских прав и лицензий > Политика цифрового хранения публикации > Политика идентификации статей > Политика проверки на плагиат
Журналы индексируются
Реквизиты журнала

ГЛАВНАЯ > Вернуться к содержанию
Кибернетика и программирование
Правильная ссылка на статью:

Алгоритмы автоматизированного выявления связей между элементами проекта разработки программного обеспечения

Голосовский Михаил Сергеевич

научный сотрудник, Государственный научно-исследовательский испытательный институт военной медицины Министерства обороны Российской Федерации

195043, Россия, г. Санкт-Петербург, ул. Лесопарковая, 4

Golosovskii Mikhail Sergeevich

Researcher, Military Medicine Research Institute of S.M.Kirov Military Medical Academy

123103, Russia, Moscow, Novikova-Priboya St., 12 building 2, apt. 67

planetnaya3@gmail.com
Другие публикации этого автора
 

 

DOI:

10.25136/2644-5522.2017.6.19616

Дата направления статьи в редакцию:

02-07-2016


Дата публикации:

11-01-2018


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


Ключевые слова:

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

Работа выполнена при финансовой поддержке РФФИ (грант 16-06-00486).

Abstract: The subject of the study is to determine the links between elements of software development projects implemented with the help of tracing requirements on the basis of data from the monitoring systems of versions of the source code. Many well-known tracing techniques are dependent on the programming language, which limits their use in projects developed using multiple programming languages. Therefore, the research goal was to form a set of algorithms to build relationships between the entities the software development process (artifacts) on the basis of the source code and analyze these connections (the code should be independent of the programming language and easy to implement). The research methodology combines methods of system analysis, software engineering, software development, reliability theory, computer science and mathematical qualimetry. The main conclusions of the study are the algorithms for the automated determination of relations between the elements of a software development project, allowing to solve tasks perform impact analysis. High computational complexity of the algorithms developed can be reduced by the gradual formation of a global connectivity matrix as the project progresses. The accuracy of the developed algorithms can be improved, if the coupling element does not take the file, and the function or class method.


Keywords:

program engineering, software development, program requirements, tracing requirements, version control system, program code, version the program code, software application architecture, integrity control architecture, communication project elements

Введение

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

1. Получение актуального статуса системы по требованиям;

2. Анализ влияния изменения;

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

1. Использование статического анализа программ основанного на структуре программы и отношении между элементами программы;

2. Использование динамического анализа программ основанного на сборе данных во время выполнения программы;

3. Использование анализа на основе обработки исторических данных, получаемых из систем контроля версий программного кода;

Большая часть рассмотренных методов является зависимой от языка программирования, что ограничивает их использование в проектах, разрабатываемых с использованием нескольких языков программирования [3-6]. Цель этой статьи заключается в формировании набора алгоритмов, позволяющих выстраивать связи между сущностями процесса разработки программного обеспечения (артефактами) на основе исходного кода, и анализировать эти связи. При этом он должен быть независимым от языка программирования и простым в реализации.

Исходные данные для выполнения трассировки

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

_1_09

Рисунок 1 – Схема модели взаимосвязи артефактов процесса разработки

Основу модели составляют требования, которые могут выстраиваться в иерархическую структуру с декомпозицией более общих требований более детальными требованиями. При этом ассоциативная связь может возникать между разными требованиями, не находящимися в иерархических отношениях друга другом. В работе под понятием требование будет использоваться общее определение требования, данное в своде знаний по программной инженерии третьей версии [7] как свойство, представленное чем-либо, для решения некоторой проблемы реального мира. Более детально, в зависимости от методологии проектирования и обработки требований в организации, возможно деление требований на различные типы (как пример [2]: функциональные требования, не функциональные требования, атрибуты качества, ограничения, бизнес требования и бизнес правила), но в общем случае допускается, что зависимости могут возникать между требованиями разных типов. Задачи так же могут выстраивать иерархию посредством декомпозиции более крупных задач на более мелкие [8-14]. При этом каждое требование должно быть ассоциировано как минимум с одной задачей, реализующей это требование. В процессе работы, каждому артефакту процесса разработки присваивается уникальный идентификатор. При написании кода в рамках задачи каждому блоку кода, добавляемому в репозиторий, разработчик проставляет комментарий с явным указанием номера задачи или дефекта, в рамках которого было проведено изменение. Дефекты заводятся по итогам выполнения тестовых сценариев, проверяющих полноту реализации требования. Одно требование может быть проверено несколькими тестовыми сценариями, так и один сценарий может проверять несколько требований (сквозные сценарии). Уровни трассировки и роли участников проекта за ведение связей представлены в табл. 1.

Таблица 1 - Распределение ответственности за уровни трассировки по ролям участников проекта

Уровень трассировки

Роль участника проекта, ответственного за ведение трассировки

Требование - Требование

Аналитик, Архитектор

Требование-Компонента

Архитектор

Требование - Задача

Ведущий разработчик

Задача-Задача

Ведущий разработчик

Задача - Код

Разработчик

Требование – Тестовый сценарий

Ведущий тестировщик

Тестовый сценарий- Дефект

Тестировщик

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

1. Задача, задача – один файл

2. Задача, дефект – один файл

3. Дефект, дефект – один файл

В связи с тем, что с одной задачей или дефектом может быть ассоциировано большое количество файлов, тестовые сценарии могут быть сквозными и покрывать несколько и с учетом иерархической структуры требований и задач, необходимо разработать алгоритм вычисления силы связей между требованиями. В качестве основы для вычисления возьмём силу связи файл-задача или файл-дефект Sf, которая будет измеряться в отношении строк кода k ассоциированных с задачей или дефектом к общему числу строк кода N (формула 1). В расчёте принимают участие только строки, содержащие операторы языка программирования.

Sf = k / N. (1)

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

St = min(sf1, sf2) (2)

Значение силы связи может принимать значения от 0 до 1. В случае значения 0 – связь отсутствует, в случае 1 – связь максимальная. Так как между одними и теми же артефактами может осуществляться связь через несколько файлов, определим требования к функции F, вычисляющей результирующее значение силы связи:

В предельном случае, число аргументов функции равно двум и область определения входных аргументов принадлежит интервалу [0…1];

F(x1,x2) = F(x2,x1) - коммутативность, порядок следования аргументов в операции не имеет значения.

F(x,0) = x; - в случае, если связь между артефактами через некоторый файл отсутствует, то существующая связь недолжна измениться;

F(x,1) = 1 – если уже достигнута максимальная связь между артефактами, она не должна быть уменьшена;

F(x1,F(x2,x3)) = F(F(x1,x2), x3) - ассоциативность, при выполнении алгоритма, должна быть возможность вычислять силу связи попарно, при этом не имеет значения порядок вычисления;

F(x1,x2) ≥ max(x1,x2) – в идеале, значение силы связи должно быть больше значения максимального элемента, при двух аргументах отличных от нуля. В этом случае, при наличии связей через большое число файлов, результирующая сила связи будет стремиться к максимальному значению.

Указанным условиям удовлетворяет следующая функция (3):

F(x1,x2) = x1 + x2 - x1 x2 . (3)

Алгоритм определения силы связей между артефактами системы

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

  1. Отбираются вершины, не имеющие родителей.
  2. Для каждой вершины не имеющий родителя осуществляется поиск в глубину вершин, имеющих 2 и более родителя.
  3. Если такая вершина находится, исследуются дочерние вершины на предмет наличия вершин, имеющих несколько родителей.
  4. Если среди дочерних вершин, вершин имеющих более одного родителя не найдено, выполняется копирование вершины, и её поддерева для каждого родителя (рис. 2), при этом связи у скопированной вершины и её родителя проставляется значение мощности s, вычисляемое по формуле 4.

s = 1/m (4)

_2_01

Рисунок 2 – Графическая иллюстрация преобразования связей между артефактами

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

  1. Находится высота самого высокого дерева hmax.
  2. Если эта высота равна 1, то приведение к максимальной высоте не требуется.
  3. В случае, если hmax>2, для каждого дерева с минимальной высотой h≥2 фиксируется первый уровень, уровень дерева h переносится на hmax, на уровнях c h-1 по hmax формируются виртуальные вершины, копирующие уровень h-1 (рисунок 3). Приведение к уровню hmax производится для каждого поддерева, не достигающего уровня hmax.
  4. В случае, если h=1, то выполняется создание виртуальных вершин, копирующих вершину 1 до уровня hmax.

_3

Рисунок 3 – Приведение деревьев к максимальной высоте

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

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

Алгоритм вычисления связей между требованиями для текущей ревизии (версии) и ветки репозитория:

1. Отбирается список файлов в проекте

2. В текущей ревизии для каждого файла отбираются задачи/дефекты ассоциированные с выбранным файлом средствами системы контроля версий, (как пример, команда hg annotate для CVS Mercurial) и вычисляется сила связи по формуле 1 для каждой пары дефект-файл или задача-файл.

3. Формируется матрица связи между задачами/дефектами, непосредственно ассоциированными с исходным кодом. Для этого, если артефакты связаны через несколько файлов, сначала применяется формула 2, определяющая связь через каждый файл в отдельности, после чего применяется формула 3, последовательно к каждой паре значений, проводя свёртку и вычисление единого значения силы связи.

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

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

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

- Если для элемента верхнего уровня иерархии связь осуществляется через несколько элементов нижнего уровня, то для свёртки применяется формула 3, последовательно к каждой паре значений. При операции на матрице, алгоритм выглядит следующим образом. Фиксируются строки для двух элементов, для которых произойдёт свёртка на верхнем уровне. Создаётся матрица, в которой две свёртываемые строки и два свёртываемых соответственно столбца, заменены одной строкой и столбцом. Для столбцов, номера которых не равны выбранным строкам по исходной матрице, производится операция свёртки по формуле 3 результат копируется в новую матрицу. Операция производится попарно до тех пор, пока все дочерние элементы не будут свёрнуты.

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

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

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

Определение требований, которые необходимо повторно протестировать при изменении кода в выбранном файле осуществляется следующим образом:

  1. Отбираются требования нижнего уровня, ассоциированные с выбранными файлами (файлами).
  2. Для выбранных требований, отбираются требований с силой связи, превышающей пороговое.
  3. Шаг 2 повторяется до тех пор, пока новые требования перестанут добавляться. Возможно явно ограничить уровень отбора.
  4. Требования сортируются по силе связи с непосредственно отобранным файлом. И отбираются связанные с ними тестовые сценарии.

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

R = Na/N, (5)

где Na – число строк кода, связанных с выбранными требованиями. N – общее число строк кода в проекте.

Пример выполнения алгоритма

Выполнение алгоритма рассмотрим на структуре артефактов, представленной на рис. 4, где R – требование, Тс – тестовый сценарий, Т – задача, D – дефект. Исходные данные в виде числа строк в файлах и их ассоциация с артефактами приведена в таблице 2.

Таблица 2 – Число строк, ассоциированных с каждым артефактом

Названия файлов

Всего строк

Число ассоциированных строк с задачей или дефектом, полученных на основе системы контроля версий

T1

T2

T3

T5

T6

T7

T8

D1

D2

D3

F1

169

79

0

82

0

0

0

0

8

0

0

F2

138

55

83

0

0

0

0

0

0

0

0

F3

107

0

107

0

0

0

0

0

0

0

0

F4

146

0

0

121

0

0

0

0

0

25

0

F5

158

0

0

0

67

91

0

0

0

0

0

F6

161

0

0

0

95

54

0

0

0

0

12

F7

92

0

0

0

0

0

85

0

0

0

7

F8

193

0

0

0

0

0

0

193

0

0

0

_4

Рисунок 4 – Исходная структура артефактов

Для исходной структуры проведем предварительные преобразования. В результате этих преобразований тестовый сценарий Тс2 и его дочерние элементы разбиваются на две подветви с силой связи с родительскими элементами R7 и R5 по 0,5. Итоговое дерево артефактов (рис. 5) имеет высоту 9 уровней, из них 1 уровень файлов и один уровень тестовых сценариев. Тестовые сценарии непосредственно при формировании матриц связности принимать участие не будут. Нумерацию уровней будем вести от корней дерева – требования R1 и R9.

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

_5

Рисунок 5 – Структура артефактов после подготовительных преобразований

Таблица 3 – Сила связи между артефактами седьмого уровня

Артефакт

T1

T2

T3

T5

T6

T7

T8

D1

D2

D3

T1

0

0,4

0,47

0

0

0

0

0,05

0

0

T2

0,4

0

0

0

0

0

0

0

0

0

T3

0,47

0

0

0

0

0

0

0,05

0,21

0

T5

0

0

0

0

0,62

0

0

0

0

0,07

T6

0

0

0

0,62

0

0

0

0

0

0,07

T7

0

0

0

0

0

0

0

0

0

0,08

T8

0

0

0

0

0

0

0

0

0

0

D1

0,05

0

0,05

0

0

0

0

0

0

0

D2

0

0

0,21

0

0

0

0

0

0

0

D3

0

0

0

0,07

0,07

0,08

0

0

0

0

Таблица 4 – Сила связи между артефактами шестого уровня

Артефакт

T1

T2

T3

T4

T7

T8

D1

D2

D3

T1

0

0,4

0,47

0

0

0

0,05

0

0

T2

0,4

0

0

0

0

0

0

0

0

T3

0,47

0

0

0

0

0

0,05

0,21

0

T5

0

0

0

0

0

0

0

0

0,07

T7

0

0

0

0

0

0

0

0

0,08

T8

0

0

0

0

0

0

0

0

0

D1

0,05

0

0,05

0

0

0

0

0

0

D2

0

0

0,21

0

0

0

0

0

0

D3

0

0

0

0,07

0,08

0

0

0

0

Таблица 5 – Сила связи между артефактами четвёртого уровня

Артефакт

R4

R6

R7

R3

R9

R10

R4

0

0,4

0,49

0

0

0

R6

0,4

0

0

0

0

0

R7

0,49

0

0

0,1

0

0

R3

0

0

0,1

0

0,07

0

R9

0

0

0

0,07

0

0

R10

0

0

0

0

0

0

Таблица 6 – Сила связи между артефактами третьего уровня

Артефакт

R4

R5

R3

R9

R10

R4

0

0,69

0

0

0

R5

0,69

0

0,1

0

0

R3

0

0,1

0

0,07

0

R9

0

0

0,07

0

0

R10

0

0

0

0

0

Таблица 7 – Сила связи между артефактами второго уровня

Артефакт

R2

R3

R9

R10

R2

0

0,1

0

0

R3

0,1

0

0,07

0

R9

0

0,07

0

0

R10

0

0

0

0

Таблица 8 – Сила связи между артефактами первого уровня

Артефакт

R1

R8

R1

0

0,07

R8

0,07

0

На четвёртом уровне, табл. 5, представлена связь между требованиями самого нижнего уровня. Она уже может использоваться для проведения анализа влияний при изменении кода в определённом файле.

Пример: в рамках исправления нового дефекта D4 внесены изменения в файл F1, в этом случае нужно в первую очередь повторно протестировать требования R4 и R7, как иерархически ассоциированные с файлом F1, и требование R6, которое иерархически с кодом не связано, но имеет отличную от нуля связь с требованием R4.

Итоговая таблица 8, представляет связь между требованиями первого уровня. В случае, если требования R1 и К8 связаны с компонентами, которые не должны иметь логической связи друг с другом, то наличие связи через общий код должно послужить сигналом к расследованию корректности реализации спроектированной архитектуры.

Заключение

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

Библиография
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
References
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
Ссылка на эту статью

Просто выделите и скопируйте ссылку на эту статью в буфер обмена. Вы можете также попробовать найти похожие статьи


Другие сайты издательства:
Официальный сайт издательства NotaBene / Aurora Group s.r.o.