Оценка объёма трудозатрат на отладку по структуре программного обеспечения

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

Введение

Неотъемлемым этапом разработки программного обеспечения является отладка программы, где обнаруживают, локализуют и устраняют ошибки.

В зависимости от доступа разработчика тестов к исходному коду тестируемой программы различают «тестирование (по стратегии) белого ящика» и «тестирование (по стратегии) чёрного ящика».

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

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

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

Оценка характеристик структуры программного обеспечения

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

В любом дереве число ребер на единицу меньше числа вершин. Эта особенность – однозначная связь между числом узлов и числом ребер отличает деревья от других графов.

Часть программных модулей не имеет выходных связей с другими модулями. Им соответствуют узлы графа, которые мы назвали «висячими». Число путей исполнения при отладке ПО должно быть равно числу висячих узлов. Иными словами, для деревьев искомое число вариантов исполнения ПО равно числу висячих узлов.

Рассмотрим дерево, в котором всего узлов Р, а висячих узлов В, m_i – число ребер, входящих и выходящих из i-го узла.

Для «регулярного» дерева, для которого m=const (кроме корневого и висячих узлов)

.

Для больших деревьев, В достаточно велико для того, чтобы было можно положить .

Формулы получены для «регулярного» дерева, где для каждого узла (кроме корневого и висячих) m = const.

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

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

Экспериментальная часть

Построим случайный граф ПО, для которого число выходящих из вершины ребер определяется датчиком случайных чисел. Определим значение структурного параметра всех узлов /число висячих узлов и приведем гистограмму для полученных при построении графа значений (m-1).

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

Примем m=6, количество вершин будем брать не менее 200, и произведем построение 100 реализаций такого дерева.

Этим же алгоритмом построим детерминированный граф ПО при фиксированном значении числа выходящих из узлов ребер (m-1).

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

Получаем следующий результат:

Среднее количество вершин: 326

Дисперсия вершин: 19

СКО вершин: 4.36

Среднее количество листьев: 218

Дисперсия листьев: 13

СКО листьев: 3.61

Средняя высота: 6

Дисперсия высоты: 0.12

СКО высоты: 0.35

Среднее альфа: 1.50

Дисперсия альфы: 0.00105

СКО альфы: 0.03

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

Рисунок 1. Исследование сходимости значения структурного параметра

Как видно из рисунка выше, с ростом числа узлов значение α устанавливается в районе значения 1,5.

Заключение

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

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

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

Стоит отметить, что рассматриваемая нами модель случайного графа-дерева, может описывать не только структуру ПО. Распространение эпидемии, лесного пожара, финансовые пирамиды вполне могут быть описаны данной моделью.