Заметки о структурном программировании, структурных и минимальных тестах

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

Предпосылки

К написанию этой заметки побудили результаты проверки студенческих решений следующей задачи:

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

Это наблюдение может быть интересно скорее начинающим программистам, чем более опытным, так как вопросы сложности кода, при наличии должного опыта, могут быть решены на уровне интуиции.

Изначально задача для студентов была сформулирована мной некорректно, а именно говорилось, что можно использовать только “стандартные возможности языка программирования”, без расшифровки что это обозначает. Действительно, не ясно что является стандартной возможностью, а что — нет, однако интуитивно может быть ясно, что требовалось использовать только:

последовательность подпрограмм,
цикл и
ветвление.

Как следует из теоремы Бёма — Якопини (теорема о структурном программировании), с помощью этих управляющих структур возможно реализовать любую программу, которая представима в виде блок схемы (исполняемого алгоритма). И здесь, определенно, алгоритм поиска медианы не является исключением.

В структурном программировании выделяют семь принципов:

следует отказаться от использования оператора безусловного перехода goto;
любая программа строится из трёх базовых управляющих конструкций: последовательность, ветвление, цикл;
в программе базовые управляющие конструкции могут быть вложены друг в друга произвольным образом;
повторяющиеся фрагменты программы можно оформить в виде подпрограмм (процедур и функций);
каждую логически законченную группу инструкций следует оформить как блок;
все перечисленные конструкции должны иметь один вход и один выход;
разработка программы ведётся пошагово, методом “сверху вниз”.

Конечно, в решениях студентов я не нашел использование goto, все прислали свои решения на Python, в котором эта управляющая конструкция просто отсутствует, однако большинство решений нарушали шестой принцип, а именно — содержали проблему раннего выхода (early exit). Ну и что дальше? — может спросить читатель.

В текущее десятилетие развитие экосистемы вокруг Python-совместимых сред разработки привело к тому, что большая часть этапа прототипирования, в особенности в области анализа данных и машинного обучения, производится в так называемых тетрадках (notebooks) — написание и исполнение кода в которых существенно далеко от принципов структурного программирования. Все это в комплексе, особенно часто — у неопытных и неаккуратных разработчиков, приводит к затруднениям:

невозможности повторить предыдущий результат исполнения программы, так как непонятно в каком порядке исполнялись блоки программы ранее - в процессе разработки и отладки;
большому количеству ошибок, связанных со злоупотреблением глобальными переменными, которые могут определяться и переопределяться в любом блоке “тетрадки”;
необходимости отладки блоков программы средствами функции print;
“я запутался” потому что не выделил блоки/функции/процедуры и не написал unit-тесты до или сразу после реализации.

Кажется, что notebooks парадигма привнесла больше плохого чем хорошего, с одной стороны — время прототипирования существенно уменьшается за счет:

снижения порога входа,
отсутствия необходимости настраивать окружение исполняемого кода,
самодокументируемости программного кода и др,

с другой стороны — программисту дается возможность разрабатывать и исполнять код, нарушая седьмой принцип структурного программирования — “сверху вниз”. И в коммерческой разработке это создает существенные сложности, особенно при совместной разработке и поддержке больших объемов довольного сложного и насыщенного зависимостями кода, который часто разрабатывается в тетрадках и без дополнительных изменений может переноситься в продакшн. Но, вернемся к нашей задаче.

Медиана трех чисел

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

Формула 1 — Очевидное свойство медианы трех чисел.

Здесь сразу напрашивается очевидное решение вида

Формула 2 — Численное решение решение задачи о медиане трех чисел.

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

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

Формула 3 — Если неравенство верно, то число b является медианой трех чисел a,b,c. — Формула 3 — Если неравенство верно, то число b является медианой трех чисел **a,b,c**.

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

Рассмотри тривиальную реализацию нужной нам функции, используя только сравнения в конструкции if/else. Такому алгоритму присвоим условный код “10” и его реализация представлена ниже, а также - здесь.

Рисунок 1 — Реализация алгоритма поиска медианы из трех чисел с использованием оператора if/else. Скопировать код можно тут — https://pastebin.com/Xa5uJtui.

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

Рисунок 2 — Расчет цикломатической сложности алгоритма “10” как количество линейно независимых циклов на графе программы. Красными путями показано шесть таких циклов. — Рисунок 2 — Расчет цикломатической сложности алгоритма “10” как количество линейно независимых циклов на графе программы. Красными путями показано **шесть** таких циклов.

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

Формула 4— Цикломатическое число графа, где E — количество ребер, N — количество вершин, а P — количество компонент связности графа. — Формула 4— Цикломатическое число графа, где **E — количество ребер**, **N — количество вершин**, а **P — количество компонент связности графа**.

Для нашей реализации алгоритма “10” получаем что

Что совпадает с количеством линейно независимых циклов и количеством точек ветвлений (у нас 5 использований условного оператора) + 1. А это означает, что для тестирования корректности работы данной функции нам потребуется не менее 6 тестов, здесь очевидно, что каждый из таких тестов будет являться перестановкой чисел a,b,c. Очевидно, что таких перестановок 3! = 6.

Рассмотрим другую реализацию, идея которой основана на применении нескольких шагов алгоритма сортировки пузырьком, и может быть реализована при наличии заранее определенной функции swap. Дадим этому алгоритму условный код “20”.

Рисунок 3 — Реализация алгоритма поиска медианы трех чисел с использованием условного оператора и подпрограммы swap. Скопировать код можно тут — https://pastebin.com/NaGM7TTj.

Рисунок 4— Расчет цикломатической сложности алгоритма “20” как количество линейно независимых циклов на графе программы. Красными путями показано четыре таких цикла. — Рисунок 4— Расчет цикломатической сложности алгоритма “20” как количество линейно независимых циклов на графе программы. Красными путями показано **четыре** таких цикла.

И для нашей реализации получаем, что

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

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

в реализации “10” у нас всего один метод и его длина 17 строк,
а в реализации “20” у нас два метода, с длинами 1 и 8 строк соответсвенно, и средняя длина равна 4.5 строки.

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

Утилита RADON

Утилита Radon позволяет вам проанализировать ваш python-код и автоматически вычислить большое количество метрик качества кода, такие как:

цикломатическая сложность,
метрики Хальстеда,
метрику поддерживаемости,
и др.

Установить утилиту Radon так же просто

Рисунок 5 — Команда для установки утилиты Radon в Python окружении.

как и пользоваться результатами ее работы. Я собрал все предложенные студентами реализации решения задачи поиска медианы трех чисел и воспользовался автоматическим расчетом метрик утилиты Radon. В первую очередь нас интересует цикломатическая сложность, вычислить которую для каждой функции из любой тетрадки (в данном случае тетрадка называется median_list.ipynb) можно выполнив следующую команду:

Рисунок 6 — Команда для запуска утилиты Radon для подсчета сложности каждой функции из тетрадки median_list.ipynb. — Рисунок 6 — Команда для запуска утилиты Radon для подсчета сложности каждой функции из тетрадки *median_list.ipynb*.

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

Рисунок 7 — Результат применения утилиты radon к тетрадке median_list.ipynb. Каждой функции из тетрадки присвоен свой ранг и рассчитана цикломатическая сложность, которая указана в скобках

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

Таблица 1 — Ранжирование сложности в зависимости от цикломатической сложности. От уровня А — очень простая подпрограмма, до уровня F — крайне высокая сложность, подпрограмма подвержена ошибкам. Источник https://radon.readthedocs.io/en/latest/intro.html.

Тестирование

Вопросы количества тестов достаточных для надежного тестирования программного обеспечения безусловно связаны не только с количество ветвлений и вычисления контурного ранга графа. Часто мы имеем дело со сложными логическими функциями в точках ветвления, гораздо сложнее чем можно себе представить для рассматриваемой в статье задачи. И здесь будет интересен пример из книги [3] в котором для анализа необходимого количества тестов и непосредственного их конструирования приводится реальный пример метода добавляющего объект в структуру типа дерево. Далее продемонстрирована часть кода этого метода.

Рисунок 8— Первые 10 строк кода из Figure 2–18 Code for structure-based exercise [3]

Мы видим ранний выход из метода по сложному логическому условию, которое, скорее всего, здесь оправдано из соображений удобочитаемости кода. И, в целом, здесь же мы имеем ветвление по логическому условию определяемому пятью состояниями. Не сложно подсчитать что это требует от нас 2⁵=32 наивных тестов. Боюсь, что полное покрытие в этом случае будет избыточно и очень трудозатратно, или нет? Ответьте на этот вопрос сейчас и дальнейшее изложение вас может удивить.

Для удобства дальнейшего изложения обозначим эти пять состояний, определяемых функциями isReq(), isBeq(), isNort(), isFlat(), isFreq() атомами x, y, z, w, t, соответсвенно, которые принимают булево значение - 0 или 1. Безусловно, не имея информации о работе этих функций мы не можем понять о достижимости всех 2⁵ состояний, и это еще больше усложняет нашу задачу. Тогда наше ветвление будет осуществляться по значениям следующей булевой функции

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

Формула 5— Булева функция для дальнейшего рассмотрения

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

На этом этапе неподготовленный читатель рискует сильно зависнуть — возьмите большой лист в клеточку и повторяйте шаги по мере чтения.

Пример из общей теории построения тестов

Здесь представленная последовательность действий приводится по примеру из книги [2]. Для нашей функции f соответствующая контактная схема представлена на рисунке 10: каждому контакту сопоставлена своя переменная x, y, z, w, t, а структура контактов определяется двумя полюсами и наличием параллельной связи, обусловленной наличием логической операцией “или”: z или (w и t).

Рисунок 9 — Контактная схема вверху и она же с пронумерованными контактами для булевой функции определяемой формулой 5.

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

Далее мы рассмотрим все такие наборы x, y, z, w, t на которых функция f принимает истинные значения и представим их в виде следующей таблицы-заготовки.

Таблица 2 — Заготовка для таблицы при поиске минимального теста на наличие ровно одного разрыва в контактной схеме

В таблице наверху мы не можем не обратить внимание что появились дополнительные функции f с индексами 0,1,2,3,4,5. Будем считать, что функция с индексом ноль обозначает исправную реализацию контактной схемы, а реализации с номерами 1,2,3,4,5 — с неисправным контактом с соответствующим номером.

Следующий шаг нашего алгоритма состоит в том, что мы должны определить все значения функций 1,2,3,4,5 на указанном наборе значений x, y, z, w, t. Отключите немного мозг, и просто повторите то что написано здесь — потому что заполнять Таблицу 2 мы будем по строкам.

Заполнять таблицу в дидактических целях начнем снизу, так должно быть понятнее. Последний набор (x, y, z, w, t)=(1,1,1,1,1). Соответствующая реализация контактной схемы для него выглядит так же как и на Рисунке 9 — все контакты соединены, разрывы отсутсвуют. Теперь ответим на вопрос — разрыв каких контактов в этом случае разорвет путь от одного полюса до другого? Очевидно, что разывая ровно один из контактов 1 или 2 (см. Рисунок 9) путь между полюсами разорвется. Это означает в соответствующих клетках таблицы в колонках значений функций 1, 2 мы поставим цифру 0, а в остальных клетках для нашего набора — единицы.

Таблица 3— Заполнение значений функций для последнего набора

Продолжим в этом же духе. Возьмем предпоследний набор аргументов (x, y, z, w, t)=(1,1,1,1,0). Нарисуем для него реализацию соответсвующей контактной схемы.

Рисунок 10 — Контактная схема для набора аргументов (x, y, z, w, t)=(1,1,1,1,0). — Рисунок 10 — Контактная схема для набора аргументов *(x, y, z, w, t)=(1,1,1,1,0).*

Ответим на тот же вопрос, что и на прошлом шаге — разрыв каких контактов в этом случае разорвет путь от одного полюса до другого? Теперь так же очевидно, что разрывая один из контактов 1,2 или 3 мы разорвем путь между полюсами. Аналогично в этих колонках поставим нули.

Таблица 4 — Заполнение значений функций для предпоследнего набора

Постройте для наборов аргументов (x, y, z, w, t)=(1,1,1,0,1) и (x, y, z, w, t)=(1,1,1,0,0) соответсвующие контактные схемы и обратите внимание, что ваш вывод будет таким же: разрыв контактов 1,2,3 приведет к разрыву всего пути между полюсами. Что отобразится в таблице следующим образом.

Таблица 5 — Продолжение заполнения для таблицы для аргументов (x, y, z, w, t)=(1,1,1,0,1) и (x, y, z, w, t)=(1,1,1,0,0) — Таблица 5 — Продолжение заполнения для таблицы для аргументов *(x, y, z, w, t)=(1,1,1,0,1)* и *(x, y, z, w, t)=(1,1,1,0,0)*

Нам осталось заполнить значения для первого набора (x, y, z, w, t)=(1,1,0,1,1). Составим соответсвующую контактную схему.

Рисунок 11 — Контактная схема для набора аргументов (x, y, z, w, t)=(1,1,0,1,1). — Рисунок 11 — Контактная схема для набора аргументов *(x, y, z, w, t)=(1,1,0,1,1).*

Мы видим, что разрывая один из контактов 1,2,4 или 5 путь между полюсами так же разорвется. В этих колонках поставим ноль. В итоге наша таблица-заготовка полностью заполнена. Полученная таблица называется “таблицей неисправностей”.

Таблица 6 — Заполненная таблица неисправностей для неисправности вида размыкание ровного одного контакта

Далее, если есть такие наборы (x, y, z, w, t) на которых мы имеем одинаковые значения функций 0,1,2,3,4,5 то оставим только один такой набор. Видим, что на на наборах аргументов (1,1,1,0,0), (1,1,1,0,1), (1,1,1,1,0) в таблице у нас одинаковые строки вида (1,0,0,0,1,1). Оставим в таблице только один такой набор, пусть это будет (1,1,1,0,0,1). Тогда таблица сократится на две строки, а оставшимся наборам присвоем номера.

Таблица 7 — Сокращенная таблица неисправностей. Цветами выделены одинаковые значения функций на оставшихся наборах.

В этой таблице мы видим, что некоторые столбцы совпадают (они выделены цветом), что означает, что неисправности типа размыкания одного контакта неотличимы в случае разомкнутости 1-ого или 2-ого контактов или в случае разомкнутости 4-ого или 5-ого контактов.

Это еще далеко не конец! Теперь мы должны объединить неотличимые неисправности в так называемые классы неисправностей. Для нашего случая мы имеем 4 класса неисправностей, обозначим их следующим образом

Рисунок 12 — Определение четырех классов неисправностей.

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

Таблица 8 — Таблица классов неисправностей

Мы уже заканчиваем. В результате выполнения этих хитрых манипуляций мы получили три набора аргументов (x, y, z, w, t) для нашего теста на неисправность вида разрыва одного контакта. Но можно ли сделать еще чуть меньше?

Выпишем всевозможные! сочетания классов g и заготовим для этого специальную таблицу.

Таблица 9 — Все паросочетания классов неисправностей

Далее, для каждого сочетания мы указываем номера наборов аргументов на которых значения в классах отличаются. Например, для первого паросочетания в таблице 9 все значения отличаются на всех трех наборах, что эквивалентно символической дизъюнкции этих наборов: 1 или 2 или 3. А для второго паросочетания отличается значение только на втором наборе. Продолжая так рассуждать мы заполняем таблицу 10 окончательно.

Таблица 10 — Все паросочетания классов неисправностей и соответсвующие им символические дизъюнкции составленные из наборов на которых значения в классах отличаются.

Заканчивая наше исследование по поиску минимального теста мы должны составить символическую конъюктивно нормальную форму из наших дизъюнкций из Таблицы 10.

И здесь следует вспомнить законы поглощения, использовав которые все становится существенно проще, а именно мы получим вырожденную дизъюнктивно нормальную форму для этого выражения

Рисунок 14— Синволическая ДНФ после минимизации средствами применения закона поглощения

можем взять любую символическую конъюнкцию из этой дизъюнктивной нормальной формы — а она у нас всего одна. Поэтому и минимальный тест в нашем случае будет состоять только из первого и второго набора аргументов. А именно для переменных (x, y, z, w, t) возьмем следующие наборы: 11011 и 11100. Контактные схемы для которых мы изобразим далее.

Рисунок 15— Контактные схемы для элементов построенного минимального множества тестов

Закончить столь длинное рассуждение можно формулой нашего минимального теста, включающего первый и второй набор аргументов

Рисунок 16 — Результат построения минимального теста для тестирования контактной схемы на разрыв ровно одного контакта.

Обратите внимание, последний этап нам снизил количество тестов с трех (наборы 11011, 11100, 11111) до двух, убрав из теста набор 11111.

Кажется, что результат получился абсолютно логичным, мы получили пару критических путей на которых, если наше логическое выражение выдает истину — то можно не беспокоится. И действительно, достаточно получить положительные тесты на наборах 11011 и 11100 чтобы утверждать что на наборе 11111 тест также будет пройден.

Но что если в схеме произошло не размыкание на которое мы тестировали, а, наборот — замыкание?

И здесь мы оставим этот классический подход и отошлем любопытного читателя к фундаментальной работе о логических способах контроля электрических схем, а так же общей теории построении тестов [1] — И. А. Чегис, С. В. Яблонский, “Логические способы контроля работы электрических схем”, Сборник статей по математической логике и ее приложениям к некоторым вопросам кибернетики, Тр. МИАН СССР, 51, Изд-во АН СССР, М., 1958, 270–360.
Обратите внимание, что никаких электрических схем ни в предпосылках к расчетам, ни в их процессе не появлялось. У читателя точно возникнет много вопросов при попытке повторить эти действия для какого-то другого логического условия: начиная от построения самой контактной схемы, нумерации контактов, составления таблиц и заканчивая символическими КНФ/ДНФ, которые были использованы без дополнительных пояснений. Для прояснения данных моментов лучше обратиться к списку использованных источников.

Далее я покажу существенно более простой метод построения подобных тестов как на размыкание так и на замыкание. Этот метод обозначим под кодовым названием “neutral-value design technique”.

Neutral-value design technique

Здесь мы рассмотрим пример из книги [3] в рамках которого предлагается рассмотреть тот же самый кусочек кода на Рисунке 8. Название этого метода можно перевести как “Метод нейтрального значения”.

Для фиксированного набора аргументов (x*,y*,z*,w*,t*) булевой функции f нейтральным элементом будем называть такой элемент этого фиксированного набора при изменении которого на противоположенное значение — значение функции изменяется на это противоположенное значение. Например, для нашей функции (выпишите ее на листочек — будет полезно обращаться к ней дальше)

рассмотрим набор аргументов 11001. Для этого набора нейтральным элементом является w, и действительно, — на наборе 11011 функция принимает значение истина. Следующая таблица демонстрирует это.

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

Каждая из таблиц заполняется построчно и заключается поиске такого набора (x*,y*,z*,w*,t*) для которого элемент на диагонали таблицы является нейтральным: в случае первой таблицы (слева) изменение значения на диагонали в ноль должно приводить к изменению значения функции в ноль, а в случае второй таблицы — изменение значения на диагонали в единицу должно приводить к изменению значения функции в единицу.

Например, заполним третью строку в первой таблице и первую строку — во второй.

И, действительно:

Для набора 11100 нейтральным является z. И значения функции f(11100)=1 но, f(11000)=0.
Для набора 01111 нейтральным является x. И значения функции f(01111)=0 но, f(11111)=1.

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

И, действительно:

Для набора 11101 нейтральным является z. И значения функции f(11101)=1 но, f(11001)=0.
Для набора 01100 нейтральным является x. И значения функции f(01100)=0 но, f(11100)=1.

Использование данного метода не предполагает наличие алгоритма, это как раз то, что называют “способом”, на каждом шаге вы можете выбрать “не совсем тот” набор для нейтрального элемента и в конечном счете не получить минимальный набор тестов. Однако используя эту технику несколько раз, приобретя опыт ее использования — у вас все будет получаться.

Продолжая рассуждать подобным образом, мы получим следующие таблицы

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

Больше интересных техник, а так же о том как к этому подходят в NASA вы можете узнать из книги [4].

Материалы и рекомендуемые источники

И. А. Чегис, С. В. Яблонский, “Логические способы контроля работы электрических схем”, Сборник статей по математической логике и ее приложениям к некоторым вопросам кибернетики, Тр. МИАН СССР, 51, Изд-во АН СССР, М., 1958, 270–360
Тишин, В. В. Дискретная математика в примерах и задачах [Электронный ресурс] : электрон. учеб. пособие / В. В. Тишин ; Минобрнауки России, Самар. гос. аэрокосм. ун-т им. С. П. Королева (нац. исслед. ун-т). — Самара, 2007. — on-line
Mitchell, Jamie L., and Rex Black. Advanced software testing-vol. 3: Guide to the istqb advanced certification as an advanced technical test analyst. Rocky Nook, Inc., 2015.
Hayhurst, Kelly J. A practical tutorial on modified condition/decision coverage. DIANE Publishing, 2001.

О количестве минимальных тестов