Тестирование потоков данных

Базовые понятия

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

По крайней мере, половина современных исходных кодов состоят из операторов объявления данных. Если мы хотим достичь качественного кода, который можно будет часто повторно применять, то нам обязательно стоит обратиться к данному методу тестирования. Вас это не убедило? В современных ПК в компромиссе «память – процессорное время» в 99% случаев выбор делают в пользу процессора. А алгоритмы, предполагающие работу с большими массивами данных, обязательно нужно тестировать на корректность потоков данных.

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

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

Определение – Переменная определяется в двух случаях:

a) при объявлении, при этом получая значения по умолчанию;

b) при появлении в левой части выражения присваивания.

Использование – Переменная используется в двух случаях:

a) при появлении в правой части выражения присваивания;

b) в случае появления в условиях if, условиях, задающих цикл (while, for), то есть в случаях управления ходом выполнения программы.

Шаги тестирования потоков данных (DU тестирование)

Способ DU тестирования требует охвата всех DU цепочек программы. Разработка тестов проходит на основании потоков данных. Критерием для выбора пути является покрытие максимального количества DU цепочек.

Шаги способа DU тестирования:

Шаг 1.Построение управляющего графа программы (описано в методе тестирования базового пути).

Шаг 2.Построение информационного графа. Граф строится по следующим принципам:

a) в случае определения переменной создаётся направленная связь (пунктирная линия) от вершины к переменной;

b) в случае использования переменной создаётся направленная связь (пунктирная линия) от переменной к вершине (в противоположную сторону).

Шаг 3.Формирование полного набора DU цепочек.

Шаг 3а. Формирование множества определения данных:

Шаг 3б. Формирование множества использования данных:

Шаг 3в. Формирование цепочек определения и использования:

DU представляется в виде , где x – переменная, i – вершина определения x, j – вершина использования x.

Шаг 4.Формирование полного набора отрезков путей в управляющем графе (на основе построенных DU цепочек).

Шаг 5.Построение маршрутов.

Шаг 6. Формирование тестовых вариантов.

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

Тестирование потоков данных можно провести, к примеру, на алгоритме сортировки вставкой (Insertion Sort), который эффективно работает при сортировке небольшого количества элементов. Приведём формулировку задачи:

Вход:последовательность из n чисел < >.

Выход:перестановка (изменение порядка) < > входной последовательности таким образом, что для её членов выполняется соотношение

Ниже приведён псевдокод алгоритма, который мы и будем тестировать:

0 // точка вызова процедуры сортировки – начальная (внешняя) вершина

1 for j 2 to length[A]

2 do key A[j]

3 i j – 1

4 while i > 0 и A[i] > key

5 do A[i + 1] A[i]

6 i i – 1

7 A[i + 1] key

8 end for

Шаг 1.Построение управляющего графа программы (рисунок 2).

Рисунок 2 – Управляющий граф программы

Шаг 2.Построение информационного графа (рисунок 3).

Рисунок 3 – Граф программы с управляющими и информационными связями

Шаг3а.Формирование множества определения данных:

DEF(0)={A}

DEF(1)={j}

DEF(2)={key}

DEF(2)={i}

DEF(5)={A}

DEF(6)={i}

DEF(7)={A}

Шаг 3б.Формирование множества использования данных:

USE(1)={A}

USE(2)={j}

USE(3)={i}

USE(4)={A, key, i}

USE(5)={A,i}

USE(6)={i}

USE(7)={i, key}

Шаг3в.Формирование цепочек определения и исполнения:

DU: {[A,0,1]; [A,0,4]; [A,0,5];

[j,1,2];

[key,2,4]; [key,2,7];

[i,2,3]; [i,2,4]; [i,2,5]; [i,2,6]; [i,6,7];[i,6,3];[i,6,4];[i,6,5]}

Шаг 4.Формирование полного набора отрезков путей в управляющем графе (на основе построенных DU цепочек). Рисуется фрагмент информационного графа (ФИГ), а также соответствующий ему фрагмент управляющего графа (ФУГ). На рисунках 4 - 9 представлено формирование полного набора отрезков путей в управляющем графе.

A

A

Рисунок 4 – [A, 0, 1] и [A, 0, 4]

key

j

A

Рисунок 5 – [A, 0, 5], [j, 1, 2] и [key, 2, 4]

key

i

Рисунок 6 – [key, 2, 7] и [i, 2, 3]

i

i

Рисунок 7 – [i, 2, 4] и [i, 2, 6]

i

i

Рисунок 8 – [i, 6, 7] и [i, 2, 5]

i

i

i

Рисунок 9 – [i, 6, 3], [i, 6, 4] и [i, 6, 4]

Шаг 5.Формирование маршрутов по цепочкам управляющего графа.

Путь 1: 0-1-2-3-4-5-6-7-8 // N > 1, массив не отсортирован

Путь 2: 0-1-2-3-7-8 // N > 1, массив не отсортирован

Путь 3: 0-1-2-3-4-7-8 // N > 1, массив отсортирован

Путь 4: 0-1-2-3-4-5-6-3-4-5-6-7-8 // N > 1, массив не отсортирован

Шаг 6.В соответствии с маршрутами формируем тестовые варианты:

ТВ 1: Исходные данные: N = 6, A = {2, 5, 4, 6, 1, 3} – вставка ключевого элемента на новое место в массиве, но не в начало массива.

Ожидаемый результат: A = {1, 2, 3, 4, 5, 6}.

ТВ 2: Исходные данные: N = 6, A = {2, 4, 5, 6, 1, 3} – вставка ключевого элемента в начало массива.

Ожидаемый результат: A = {1, 2, 3, 4, 5, 6}.

ТВ 3: Исходные данные: N = 6, A = {1, 2, 3, 4, 5, 6} – ключевой элемент остаётся на своём месте.

Ожидаемый результат: A = {1, 2, 3, 4, 5, 6}.

ТВ 4: Исходные данные: N = 6, A = {1, 2, 4, 5, 6, 3} – повторный поиск места ключевого элемента в массиве.

Ожидаемый результат: A = {1, 2, 3, 4, 5, 6}.