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

1. Введение

Формальные методы и тестирование программного обеспечения

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

Однако, чем большее значение отводится компьютерным системам, тем выше становится цена их ошибок. Как показывает практика, наиболее уязвимым местом компьютерных систем с этой точки зрения является программное обеспечение. Так, ошибка в одном программном модуле многомиллионного межпланетного корабля Mars Climate Orbiter привела к его гибели в атмосфере Марса после более чем девятимесячного полета [1, 2].

Более того, некорректное поведение современных программных систем влечет не только огромные убытки, но и приводит к гибели людей. Например, ошибки в программном обеспечении медицинского оборудования Therac-25 привели к получению повышенной дозы радиации и последующей смерти 7 пациентов [3, 4]. А арифметическая ошибка в программном обеспечении комплекса противовоздушной обороны Patriot не позволила вовремя обнаружить иракскую ракету, что привело к гибели 28 солдат во время ирако-американской войны 1991 года [5]. И это только малая часть уже имевших место прецедентов.

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

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

Одним из основных направлений в области формальных методов являются методы доказательства корректности программ, такие как методы аналитической верификации и проверки моделей [7, 8, 9, 10]. В этих методах доказательство корректности программ строится по следующей схеме. Для данной программной системы создаются математическая модель требований к системе и математическая модель реализации этой системы. После чего доказывается наличие отношения "удовлетворяет" между этими двумя моделями, что и рассматривается как доказательство корректности программы (рисунок 1). Существует также целый набор вариаций подхода. Например, в качестве модели требований может выступать модель программной системы более высокого уровня абстракции, или доказательство корректности может сводиться к доказательству непротиворечивости одной из математических моделей.

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

Многочисленные исследования в области формальных методов нашли свое отражение и в развитии новых технологий тестирования. Одно из наиболее активно развивающихся направлений - тестирование на основе моделей, уже успело показать свои преимущества в целом ряде крупных индустриальных проектов [11, 12, 13, 14, 15, 16, 17].

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

Технология UniTesK

Комплексный подход, позволяющий автоматизировать целый спектр задач тестирования на основе математических моделей, представляет собой технология тестирования UniTesK [18, 19, 20], разработанная в Институте Системного Программирования РАН. Данная технология использует широко известный подход программных контрактов [21] для формального описания требований к программному обеспечению и уникальные методы генерации сложных последовательностей тестовых воздействий на основе неявного описания конечного автомата. Эффективность такого подхода была подтверждена в многочисленных проектах [22], и, в частности, при разработке тестового набора для ядра операционной системы канадского телекоммуникационного гиганта Nortel Networks [23].

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

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

Первое достоинство решения, предлагаемого технологией UniTesK, заключается в значительном сглаживании перехода между областью неформальных объектов и областью их математических моделей. Этот переход является одним из наиболее критикуемых мест формальных методов [24]. Применительно к методам доказательства корректности программ проблема данного перехода заключается в том, что доказательство корректности математической модели реализации программной системы не гарантирует корректность самой реализации. И единственным средством для проверки соответствия между реализацией системы и ее моделью является их сопоставление, выполняемое человеком. Для реальных программных систем такое сопоставление является большой проблемой в виду размеров модели и сложности связей между ее составляющими. Модель поведения системы на конкретных данных, используемая в технологии UniTesK, является значительно более простой, чем модель реализации, а значит сопоставление модели поведения с реальным поведением системы является значительно более простым, чем сопоставление модели реализации с самой реализацией.

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

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

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

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

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

Системы с асинхронным интерфейсом

Изначально технология UniTesK использовала для формального описания требований к программному обеспечению подход классических программных контрактов [21]. Этот подход показал себя с лучшей стороны при разработке тестового набора для ядра операционной системы канадского телекоммуникационного гиганта Nortel Networks [23]. В то же время, проявился и ряд ограничений, связанных с ограниченной областью применимости классических программных контрактов.

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

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

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

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

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

Разработка метода тестирования систем с асинхронным интерфейсом являлась составной частью исследований, проводимых группой UniTesK Lab Института Системного Программирования РАН в рамках развития технологии тестирования UniTesK. Исследование методов спецификации и тестирования систем с асинхронным интерфейсом было выполнено автором совместно с И.Б. Бурдоновым, А.С. Косачевым и В.В. Куляминым. Также автор выражает свою признательность руководителю группы UniTesK Lab А.К. Петренко и коллегам, участвовавшим в реализации системы тестирования CTesK и апробации рассматриваемого метода: В. Омельченко, А. Коптелову, Е. Рогову, Н. Пакулину и Г. Ключникову.

2. Архитектура UniTesK для систем с синхронным интерфейсом

Настоящая глава состоит из четырех разделов. Первые три раздела посвящены рассмотрению математических моделей и принципов решения основных задач тестирования:

• задачи оценки корректности поведения тестируемой системы;
• задачи генерации тестовых данных;
• задачи оценки качества тестирования.

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

Математические модели, описанные в данной главе, несколько отличаются от традиционных описаний технологии UniTesK [18, 19, 25], что обусловлено попыткой взглянуть на технологию UniTesK с точки зрения ее практического использования.

Основные понятия

Перед началом рассмотрения технологии UniTesK введем несколько базовых терминов.

Целевой системой будем называть программную систему, которую необходимо протестировать. В качестве синонима целевой системы также будем использовать словосочетание тестируемая система. В англоязычной литературе этим терминам соответствуют сокращения SUT (System Under Test) и IUT (Implementation Under Test).

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

Оценка корректности поведения тестируемой системы

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

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

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

Например, пользователь библиотеки математических функций ожидает, что вызвав функцию sqrt с параметром x, он получит квадратный корень x, вычисленный с заданной точностью.

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

Формализация задачи

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

Поведение целевой системы в процессе тестирования представляется формальным образом в виде модели поведения, которая состоит из набора взаимодействий целевой системы со своим окружением. Требования, предъявляемые к функциональности целевой системы, описываются формально в виде модели требований. На декартовом произведении всех возможных моделей поведения и всех возможных моделей требований определяется формальное отношение "удовлетворяет", которое соответствует неформальному пониманию отношения "удовлетворяет" между поведением целевой системы и функциональными требованиями. В результате, на уровне математической модели, задача оценки корректности поведения целевой системы эквивалентна проверке наличия отношения "удовлетворяет" между моделью поведения целевой системы и моделью требований. Рассмотренный подход проиллюстрирован на рисунке 2.

Рассмотрим формальные определения моделей поведения и требований.

Модель поведения

Интерфейсом целевой системы будем называть тройку ( X, Y, V ), где

• X - множество стимулов,
• Y - множество реакций,
• V - множество состояний.

Каждое из этих множеств может быть бесконечным ¹. Взаимодействием с целевой системой, обладающей интерфейсом ( X, Y, V ), будем называть четверку ( v, x, y, v' ) V x X x Y x V. Первый элемент взаимодействия v мы будем называть пресостоянием, второй x - стимулом, y - реакцией, v' - постсостоянием.

Понятие взаимодействия можно интерпретировать следующим образом. В состоянии v вызывается интерфейсная операция с некоторыми значениями параметров x, на что целевая система возвращает выходные параметры y и переходит в состояние, соответствующее состоянию v'.

Например, для функции вычисления квадратного корня возможны следующие взаимодействия: ( ε, sqrt( 0.0 ), 0.0, ε ), ( ε, sqrt( 4.0 ), 2.0, ε ) или ( ε, sqrt( 10.0 ), 1.0, ε ). В этом примере множество состояний V состоит из единственного элемента ε, множество стимулов X и реакций Y совпадают с множеством всех неотрицательных действительных чисел.

Определение 1.

Моделью поведения целевой системы с интерфейсом ( X, Y, V ) будем называть конечное или бесконечное мультимножество взаимодействий { ( v_i, x_i, y_i, v'_i ) }.

Модель поведения соответствует набору взаимодействий с целевой системой, имевших место в процессе тестирования. Например, предположим, что в процессе тестирования функция вычисления квадратного корня была вызвана трижды с параметрами 0.0, 4.0 и 10.0 и вернула значения 0.0, 2.0 и 1.0 соответственно. Тогда моделью поведения целевой системы будет мультимножество взаимодействий, произошедших в процессе тестирования { ( ε, sqrt( 0.0 ), 0.0, ε ), ( ε, sqrt( 4.0 ), 2.0, ε ), ( ε, sqrt( 10.0 ), 1.0, ε ) }.

Модель требований

Абстрактным автоматом будем называть четверку ( V, X, Y, E ), где

• V - множество состояний,
• X - множество стимулов,
• Y - множество реакций,
• E V x X x Y x V - множество переходов.

Переходы автомата ( v, x, y, v' ) состоят из пресостояния v, стимула x, реакции y и постсостояния v'. Множества V, X, Y и E могут быть бесконечными.

Определение 2.

Моделью требований к целевой системе с интерфейсом ( X, Y, V ) будем называть абстрактный автомат, множества состояний, стимулов и реакций которого совпадают с V, X и Y соответственно.

Будем говорить, что взаимодействие ( v, x, y, v' ) является корректным относительно модели требований A = ( V, X, Y, E ), если оно принадлежит множеству переходов E.

Будем говорить, что модель поведения целевой системы { ( v_i, x_i, y_i, v'_i ) } удовлетворяет модели требований A = ( V, X, Y, E ), если i ( v_i, x_i, y_i, v'_i ) E.

Рассмотрим пример с функцией вычисления квадратного корня. Что является моделью требований к этой функции? Интерфейс этой системы ( X, Y, V ) был определен в предыдущем разделе. Множество переходов E определим как все переходы ( ε, x, y, ε ) V x X x Y x V, для которых выполнено следующее ограничение: | x - y² | < ε_погр , где ε_погр - некоторое положительное действительное число, меньшее единицы. Тогда взаимодействия ( ε, sqrt( 0.0 ), 0.0, ε ) и ( ε, sqrt( 4.0 ), 2.0, ε ) будут корректными относительно данной модели функциональных требований, а взаимодействие ( ε, sqrt( 10.0 ), 1.0, ε ) - нет.

Программные контракты

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

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

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

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

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

Описание модели требований

Рассмотрим подход программных контрактов более детально и определим способ описания модели требований, применяемый в технологии UniTesK. Сигнатурой интерфейсной операции I называется тройка ( In, Out, Var ), где

• In = { x_i | i = 1, …, in(I) ; in(I) ≥ 0 } - упорядоченный набор входных параметров операции,
• Out = { y_i | i = 1, …, out(I) ; out(I) ≥ 0 } - упорядоченный набор выходных параметров операции,
• Var = { v_i | i = 1, …, var(I) ; var(I) ≥ 0 } - набор переменных состояния, к которым обращается данная операция.

Каждый входной параметр x_i может принимать значения из непустого множества допустимых значений X_i, каждый выходной параметр y_i может принимать значения из непустого множества допустимых значений Y_i, а каждая переменная состояния v_i может принимать значения из непустого множества допустимых значений V_i. Эти непустые множества допустимых значений далее будут называться типами параметров и переменных.

Рассмотрим пример операции вычисления квадратного корня. Сигнатурой этой операции является тройка ( { x₁ }, { y₁ }, {} ). Множеством допустимых значений единственного входного параметра x₁ и единственного выходного параметра y₁ является множество действительных чисел R. Пустое множество переменных состояния означает, что данная операция никак не зависит ни от одной переменной состояния.

Введем следующие обозначения:

X_I = X₁ x … x X_in(I), если in(I) > 0, и X_I = { ε }, в противном случае;

Y_I = Y₁ x … x Y_out(I), если out(I) > 0, и Y_I = { ε }, в противном случае;

V_I = V₁ x … x V_var(I), если var(I) > 0, и V_I = { ε }, в противном случае.

Спецификацией интерфейсной операции I с сигнатурой ( In, Out, Var ) называется пара предикатов ( pre_I, post_I ), в которой

• pre_I - предикат на множестве V_I x X_I, называемый предусловием,
• post_I - предикат на множестве V_I x X_I x Y_I x V_I, называемый постусловием.

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

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

pre_sqrt ( v, x₁ ) ≡ (x₁ ≥ 0)

post_sqrt ( v, x₁, y₁, v' ) ≡ | x₁ - y₁² | < ε_погр

Здесь, как и ранее, ε_погр обозначает некоторое положительное действительное число.

Спецификацией целевой системы называется непустой набор спецификаций ее интерфейсных операций { Spec_Ii | i = 1, …, k; k > 0 }.

В технологии UniTesK для описания требований к функциональности целевой системы (модели требований) также используется подход программных контрактов. Описание модели требований задается в виде спецификации Spec { Spec_Ii | i = 1, …, k }, а соответствующая ей модель требований MR[Spec] ( V, X, Y, E ) определяется согласно следующим правилам:

1. Если в спецификации присутствует хотя бы одна переменная состояния, то множество состояний V является декартовым произведением множеств допустимых значений всех переменных состояния

   V=,
   где Var_Spec является объединением переменных состояния всех интерфейсных операций, принадлежащих спецификации

   Var_Spec = .

2. Если в спецификации не участвует ни одной переменной состояния, то множество состояний состоит из единственного элемента ε:
         V { ε }.

3. Множество стимулов X является дизъюнктивным объединением декартовых произведений множеств допустимых значений входных параметров всех интерфейсных операций спецификации

   X = .

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

4. Множество реакций Y является дизъюнктивным объединением декартовых произведений множеств допустимых значений выходных параметров всех интерфейсных операций спецификации

   Y = .

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

5. Множество переходов E состоит из всех переходов, удовлетворяющих обобщенным предусловию и постусловию спецификации

   E = { ( v, x, y, v' ) V x X x Y x V | pre( v, x ) post( v, x, y, v' ) },
   где предикат pre = , а предикат post =

Описание модели поведения

Требования к функциональности целевой системы являются исходными данными для процесса тестирования². Соответственно, модель требований к целевой системе описывается во время разработки теста и в процессе тестирования не изменяется.

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

Так как модель поведения используется для сравнения с моделью требований, то эти модели должны быть согласованы между собой. Это означает, что обе модели должны быть построены на основе единого интерфейса целевой системы ( X, Y, V ).

Если модель требований задана спецификацией Spec, то таким образом интерфейс целевой системы ( X, Y, V ) фиксирован согласно определению MR[Spec]. Состояние системы определяется значениями переменных состояния, описанных в спецификации, стимул задается интерфейсной операцией и набором значений входных параметров этой операции, а реакция идентифицируется интерфейсной операцией и набором значений выходных параметров этой операции.

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

• набором значений переменных до вызова интерфейсной функции;
• идентификатором интерфейсной операции и набором значений входных параметров этой операции;
• идентификатором интерфейсной операции и набором значений выходных параметров этой операции;
• набором значений переменных после вызова интерфейсной функции.

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

Моделирование требований и поведения

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

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

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

Тогда для каждой функции прикладного интерфейса можно определить соответствующую ей интерфейсную операцию. Сигнатура интерфейсной операции определяется по следующим правилам³:

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

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

Определив сигнатуры интерфейсных операций, участвующих в спецификации, мы тем самым определили интерфейс целевой системы ( X, Y, V ). Согласно MR[Spec] этот интерфейс определяется следующим образом:

• множество стимулов X состоит из вызовов функций прикладного интерфейса со всеми допустимыми наборами входных параметров,
• множество реакций Y состоит из всех возможных возвращаемых значений интерфейсных функций, где под возвращаемым значением подразумевается кортеж значений выходных параметров данной функции,
• множество состояний V состоит из значений, соответствующих различным значениям внутреннего состояния целевой системы и/или ее окружения. При этом учитываются только те значения, от которых зависит ожидаемое поведение хотя бы одной функции прикладного интерфейса.

Взаимодействием с целевой системой в этом случае является четверка ( v, x, y, v' ), в которой:

• пресостояние v соответствует состоянию целевой системы и/или ее окружения до вызова функции прикладного интерфейса,
• стимул x соответствует вызову функции прикладного интерфейса с определенным набором значений входных параметров,
• реакция y соответствует набору значений выходных параметров, который вернула вызванная функция,
• постсостояние v' соответствует состоянию целевой системы и/или ее окружения, в котором она оказалась после данного вызова.

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

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

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

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

Для каждой функции прикладного программного интерфейса определим соответствующую ей интерфейсную операцию.

Сигнатуру операции помещения числа в стек определим как ( { x }, {}, { v_stack } ), где тип входного параметра x - Int, а переменной состояния v_stack - Int-list. Спецификацию этой операции ( pre_push, post_push ) зададим следующими предикатами:

pre_push ( v_stack, x ) ≡ true

post_push ( v_stack, x, vstack' ) ≡ ( vstack' = x ° v_stack )

Сигнатуру операции выборки элемента с вершины стека определим как ( {}, { y }, { v_stack } ), где тип выходного параметра y - Int, а переменной состояния v_stack - Int-list. Спецификацию этой операции ( pre_pop, post_pop ) зададим следующими предикатами:

pre_pop ( v_stack, y ) ≡ size( v_stack ) > 0

post_pop ( v_stack, y, vstack' ) ≡ ( y = head( v_stack ) ) ( vstack' = tail( v_stack ) )

Сигнатуру операции получения размера стека определим как ( {}, { y }, { v_stack } ), где тип выходного параметра y - Int, а переменной состояния v_stack - Int-list. Спецификацию этой операции ( pre_size, post_size ) зададим следующими предикатами:

pre_size ( v_stack, y ) ≡ true

post_size ( v_stack, y, v_stack' ) ≡ ( y = size( v_stack ) ) ( vstack' = v_stack )

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

В данном случае интерфейс целевой системы есть ( X_stack, Y_stack, V_stack ), где⁴:

• X_stack = Int { pop } { size } - множество стимулов состоит из
• целых чисел, соответствующих вызову функции помещения числа в стек с данным числом в качестве параметра,
• элемента pop , соответствующего вызову функции выборки элемента с вершины стека,
• элемента size , соответствующего вызову функции получения размера стека,
• Y_stack = { push } Int Int - множество реакций состоит из
• элемента push , соответствующего отсутствующим выходным параметрам функции помещения числа в стек,
• целых чисел, соответствующих значению единственного выходного параметра функции выборки элемента с вершины стека,
• целых чисел, соответствующих значению единственного выходного параметра функции получения размера стека,
• V_stack = Int-list - множество состояний состоит из списков целых чисел, соответствующих текущему состоянию стека (первый элемент списка соответствует вершине стека).

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

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

Модель поведения для данного теста будет состоять из четырех взаимодействий:

{
( , 0, push, 0 ),
( 0 , size, 1, 0 ),
( 0 , pop, 0, 0 ),
( 0 , size, 1, 0 )
}

Если описать эту модель в терминах спецификации целевой системы, то мы получим следующее:

{
( v_stack , push (0 ), push (), v_stack = 0 ),
( v_stack 0 , size (), size (1 ), v_stack = 0 ),
( v_stack 0 , pop (), pop (0 ), v_stack = 0 ),
( v_stack 0 , size (), size (1 ), v_stack = 0 )
}

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

Модели требований и поведения в унифицированной архитектуре теста

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

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

За оценку корректности взаимодействий отвечает специальный компонент тестовой системы - оракул. Этот компонент генерируется автоматически на основе описания модели требований в виде спецификации целевой системы. Модель поведения целевой системы строится динамически и за это отвечает другой компонент тестовой системы - медиатор. Оракул и медиатор являются одними из основных элементов унифицированной архитектуры теста. Рассмотрим их подробнее.

Медиаторы отвечают в тестовой системе за всю работу с целевой системой. Основными задачами медиатора являются оказание тестового воздействия на целевую систему и построение модели поведения целевой системы. Эти задачи тесно связаны, так как в синхронном случае любое взаимодействие начинается с оказания тестового воздействия или стимула. Ответная реакция целевой системы является другой составляющей взаимодействия. Кроме этого, взаимодействие характеризуется пресостоянием и постсостоянием.

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

Исходя из этого, работа медиатора строится по следующему алгоритму. Получив указание подать стимул x X, медиатор преобразует его в вызов интерфейсной функции целевой системы со значениями входных параметров, соответствующих данному стимулу. Затем медиатор получает ответную реакцию целевой системы, преобразуют ее в модельное представление y Y и возвращает ее обратно. Кроме этого, медиатор синхронизирует модельное состояние с внутренним состоянием тестируемой системы после оказания тестового воздействия.

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

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

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

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

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

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

Технически работа оракулов организована следующим образом. Оракул запоминает все необходимые части текущего модельного состояния v и передает стимул x медиатору. Медиатор оказывает тестовое воздействие, моделируемое посредством стимула x, получает реакцию целевой системы, преобразует ее в модельное представление y и синхронизирует текущее модельное состояние с внутренним состоянием реализации. Оракул, зная сохраненное состояние v, стимул x, реакцию y и текущее состояние v', выносит вердикт о корректности данного взаимодействия.

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

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

На рисунках 4 и 5 представлены диаграммы взаимодействия UML, иллюстрирующие основные варианты работы этой части тестовой системы при тестировании с открытым и со скрытым состоянием соответственно. Работа оракула начинается с получения указания осуществить тестовое воздействие, моделируемое посредством стимула x. От кого именно поступает данное указание, в настоящий момент не рассматривается. Дальнейшая последовательность взаимодействий оракула, медиатора и целевой системы происходит так, как рассматривалось ранее.

Рисунок 4. Основной вариант работы оракула и медиатора при тестировании с открытым состоянием

Рисунок 5. Основной вариант работы оракула и медиатора при тестировании со скрытым состоянием

Генерация тестовых данных

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

Описывать их вручную - очень утомительно и накладно. Автоматически генерировать последовательности тестовых воздействий - возможно, но качество, как правило, оказывается весьма невысоким. Технология UniTesK предлагает следующее компромиссное решение.

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

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

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

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

Формальные определения модели построения тестового сценария будут рассмотрены в последующих разделах.

Управляющие автоматы

Первым шагом в формализации понятия тестового сценария является определение управляющих автоматов.

Определение 3.

Управляющим автоматом будем называть пятерку ( V, X, Y, E, Q ), где

• S - множество состояний,
• X - множество стимулов,
• Y - множество реакций,
• E V x X x Y x V - множество переходов,
• Q V - множество заключительных состояний.

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

Стимул s X называется допустимым в состоянии u V абстрактного автомата A = ( V, X, Y, E ) (или управляющего автомата ( V, X, Y, E, Q ) ), если существует переход ( v, x, y, v' ) E, такой что v = u и x = s.

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

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

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

Последовательность переходов ( e₁, e₂, …, e_n ) абстрактного автомата A = ( V, X, Y, E ) (или управляющего автомата ( V, X, Y, E, Q ) ) называется путем, если для каждого i = 1, …, n-1 постсостояние перехода e_i совпадает с пресостоянием перехода e_i+1. При этом мы будем говорить, что путь ведет из пресостояния перехода e₁ в постсостояние перехода e_n.

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

Функционированием управляющего автомата ( V, X, Y, E, Q ) с начальным состоянием v₀ V называется конечный или бесконечный путь { e_i = ( v_i, x_i, y_i, v'_i ) }, удовлетворяющий следующим условиям:

• если начальное состояние является заключительным (v₀ Q), то путь является пустой последовательностью,
• если начальное состояние не является заключительным (v₀ Q), то пресостояние первого перехода v₁ совпадает с начальным состоянием v₀, (v₁ = v₀),
• если путь является конечным и его длина больше нуля, то постсостояние последнего перехода является заключительным (v_n Q),
• если заключительное состояние присутствует в пути, то путь является конечным и это состояние есть постсостояние последнего перехода.

Управляющие автоматы будут использоваться далее для определения понятия тестового сценария.

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

Тестом целевой системы с интерфейсом ( X, Y, V ) называется конечная или бесконечная последовательность взаимодействий { ( v_i, x_i, y_i, v'_i ) }. Множество всех тестов целевой системы с интерфейсом ( X, Y, V ) будем обозначать символом ℵ( X, Y, V ).

Моделью поведения целевой системы в ходе теста { ( v_i, x_i, y_i, v'_i ) } будем называть мультимножество взаимодействий { ( v_i, x_i, y_i, v'_i ) }.

Тест { ( v_i, x_i, y_i, v'_i ) } целевой системы с интерфейсом ( X, Y, V ) будем называть успешным относительно модели требований A = ( V, X, Y, E ), если модель поведения в ходе теста удовлетворяет модели требований A. В противном случае, тест будет называться неуспешным.

Определение 4.

Тестовым сценарием для целевой системы с интерфейсом ( X, Y, V ) называется пара ( C, s₀ ), где

• C - управляющий автомат ( S, A, B, E, Q ), в котором
• множество стимулов A = X V,
• множество реакций B = (Y x V) { ε },
• множество переходов включает в себя только переходы ( s, a, b, s' ), в которых либо a X и b (Y x V), либо a V и b = ε;
• s₀ : V S - функция инициализации.

Тестовый сценарий управляет процессом тестирования, выполняя одно из двух возможных действий: либо подавая стимул x X, либо устанавливая новое состояние v V. Реакцией на первое действие является реакция целевой системы y и ее постсостояние v', а на второе - пустая реакция ε. Функция инициализации определяет начальное состояние управляющего автомата в зависимости от начального состояния целевой системы.

Множество всех тестовых сценариев для целевой системы с интерфейсом ( X, Y, V ) будем обозначать символом ( X, Y, V ). Множество тестовых сценариев для целевой системы с интерфейсом ( X, Y, V ) и с заданным множеством состояний управляющего автомата S будет обозначаться ( X, Y, V, S ).

Пусть { e_j = ( s_j, a_j, b_j, s'_j ) } является функционированием тестового сценария σ для целевой системы с интерфейсом ( X, Y, V ). Тогда { e_k(i) = ( s_k(i), a_k(i), b_k(i), s'_k(i) ) } будем обозначать подпоследовательность последовательности { e_j } составленную из переходов, действия которых связаны с подачей стимула ( a_k(i) X ).

Результатом применения тестового сценария σ = ( C = ( S, A, B, E, Q ), s₀ ) к целевой системе, находящейся в начальном состоянии v₀ V, является тест { ( v_i, x_i, y_i, v'_i ) }, для которого существует такое функционирование управляющего автомата C с начальным состоянием s₀(v₀) { e_j = ( s_j, a_j, b_j, s'_j ) }, что длина теста совпадает с длиной подпоследовательности { e_k(i) } и для каждого взаимодействия ( v_i, x_i, y_i, v'_i ) выполнены следующие условия:

• пресостояние v_i совпадает с
• начальным состоянием целевой системы v₀, если k(i) = 1;
• ранее установленным состоянием a_k(i)-1, если k(i) > 1 и a_{k (i)-1} V;
• постсостоянием после предыдущей подачи стимула v_i-1, если k(i) > 1 и a_k(i)-1 X;
• стимул x_i совпадает с a_k(i);
• реакция y_i совпадает с первым элементом реакции b_k(i) = ( y_k(i), v_k(i) );
• постсостояние v'_i совпадает со вторым элементом реакции b_k(i) = ( y_k(i), v_k(i) ).

Такой тест мы будем обозначать T( σ, v₀ ).

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

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

Тестовым сценарием с внутренними переходами для целевой системы с интерфейсом ( X, Y, V ) называется пара ( C, s₀ ), где

• C - управляющий автомат ( S, A, B, E, Q ), в котором
• множество стимулов A X V { ε },
• множество реакций B (Y x V) { ε },
• множество переходов включает в себя только переходы ( s, a, b, s' ), в которых либо a X и b (Y x V), либо a V { ε } и b = ε;
• s₀ : V S - функция инициализации.

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

Каждому тестовому сценарию с внутренними переходами σ_ε = ( ( S, A, B, E, Q ), s₀ ) соответствует тестовый сценарий σ( σ_ε ) = ( ( S, A', B, E', Q' ), s₀ ), в котором

• множество стимулов A' = X V,
• множество переходов E' состоит из переходов ( s, a, b, s' ) S x A' x B x S, для которых существует путь s₁ s2 … s_n в управляющем автомате ( S, A, B, E, Q ), удовлетворяющий следующим условиям:
• начальное состояние пути s₁ = s,
• конечное состояние пути s_n = s',
• i { 1, …, n-1 }: (a_i = a) (b_i = b)
                    j { 1, …, n-1 } (i ≠ j) (a_j = ε) (b_j = ε);
• множество заключительных состояний Q' состоит из состояний множества Q, а также из состояний s S, из которых не выходит ни одного перехода во множестве E', но существует путь s₁ s2 … s_n в управляющем автомате ( S, A, B, E, Q ), в котором:
• начальное состояние s₁ = s,
• конечное состояние s_n Q,
• i { 1, …, n } (a_i = ε) (b_i = ε).

Определение 5.

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

Механизмы построения тестового сценария применяются для создания тестовых сценариев на основе каких-либо данных. Примером такого механизма может быть последовательная композиция набора тестовых сценариев.

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

Автоматный механизм построения тестового сценария

Ориентированным графом будем называть тройку G = ( VG, XG, EG ), в которой:

• VG - множество вершин графа;
• XG - множество стимулов графа;
• EG VG x XG x VG - множество дуг графа, каждая из которых состоит из начальной вершины, стимула и конечной вершины.

Ориентированный граф G = ( VG, XG, EG )называется конечным, если множества VG, XG, и EG являются конечными.

Стимул s XG называется допустимым в вершине u VG ориентированного графа G = ( VG, XG, EG ), если существует дуга ( v, x, v' ) EG, такая что v = u и x = s.

Ориентированный граф G = ( VG, XG, EG ) называется детерминированным, если для каждой вершины u VG и стимула s XG существует не более одной дуги ( v, x, v' ) EG, такой что v = u и x = s.

Последовательность дуг ( e₁, e₂, …, e_n ) ориентированного графа G = ( VG, XG, EG ) называется маршрутом, если для каждого i = 1, …, n-1 конечная вершина перехода e_i совпадает с начальной вершиной перехода e_i+1. При этом мы будем говорить, что маршрут ведет из начальной вершины перехода e₁ в конечную вершину перехода e_n.

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

Ориентированный граф G = ( VG, XG, EG ) называется сильно-связным, если для любых двух его вершин v и v' существует маршрут ( e₁, e₂, …, e_n ), ведущий из вершины v в вершину v'.

Обходом конечного ориентированного графа G = ( VG, XG, EG ) называется маршрут v₁ v₂ … v_n, в котором для каждой дуги ( v, x, v' ) EG существует i { 1, … , n-1 }, такое что v = v_i, x = x_i и v' = v_i+1.

Определение 6.

Алгоритмом движения на ориентированных графах называется функция α, которая по ориентированному графу G = ( VG, XG, EG ), текущей вершине v VG и пройденному маршруту ( e₁, e₂, …, e_n ) определяет следующее действие a XG { τ }. Следующее действие может быть либо стимулом x, допустимым в текущей вершине, либо специальным значением τ, символизирующим пустое действие.

Функционированием алгоритма движения α на ориентированном графе G = ( VG, XG, EG ) с начальной вершины v₀ V называется конечный или бесконечный маршрут ( e₁, e₂, …, e_n, … ) в графе G, удовлетворяющий следующим условиям:

• начальная вершина v₁ первой дуги маршрута e₁ = ( v₁, x₁, v'₁ ) совпадает с начальной вершиной v₀;
• в каждой дуге маршрута e_i = ( v_i, x_i, v'_i ) стимул x_i равен α( A, v_i, ( e₁, …, e_i-1 ) ) - значению алгоритма движения α на автомате A, начальной вершине v_i и пройденном маршруте ( e₁, …, e_i-1 );
• если дуга e_i = ( v_i, x_i, v'_i ) является последней в последовательности, то α( A, v'_i, ( e₁, …, e_i ) ) = τ.

Алгоритм движения α называется алгоритмом обхода на классе конечных ориентированных графов Æ, если на любом графе G из класса Æ любое функционирование алгоритма движения α является конечным обходом графа G.

Алгоритм движения α называется неизбыточным, если для любых двух конечных ориентированных графов G₁ = ( VG₁, XG₁, EG₁ ) и G₂ = ( VG₂, XG₂, EG₂ ), для любой вершины v VG₁ ∩ VG₂ и для любого пройденного маршрута ( e₁, …, e_n ), из равенства множеств допустимых стимулов в текущей вершине и в каждой вершине из пройденного маршрута следует равенство α( A₁, v, ( e₁, …, e_n ) ) = α( A₂, v, ( e₁, …, e_n ) ). Другими словами, алгоритм движения является неизбыточным, если он зависит только от текущей вершины, пройденного маршрута и множества допустимых стимулов в текущей вершине и в каждой вершине из пройденного маршрута.

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

В работах [25, 26, 27] представлено исследование неизбыточных алгоритмов обхода различных классов графов. В частности, в [26] рассмотрен неизбыточный алгоритм обхода α_dfsm⁵ на классе детерминированных сильно-связных конечных ориентированных графах. Этот алгоритм используется в технологии UniTesK в качестве основного алгоритма для построения последовательностей тестовых воздействий.

Неизбыточным описанием ориентированного графа называется тройка ( VG, XG, π ), где

• VG - множество вершин графа,
• XG - множество стимулов графа,
• π : VG (XG) - функция, определяющая множество допустимых стимулов в данной вершине графа.

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

Автоматным тестовым сценарием для целевой системы с интерфейсом ( X, Y, V ) называется семерка ( IG, vg₀, α, S, ρ, γ, η ), где

• IG = ( VG, XG, π ) - неизбыточное описание ориентированного графа, называемого графом сценария,
• vg₀ : V VG - функция инициализации графа сценария,
• α - неизбыточный алгоритм движения по графу сценария,
• S - множество состояний сценария,
• ρ : S S - функция рестарта сценария,
• γ : VG x XG ( X, Y, V, S ) - отображение, ставящее в соответствие каждым вершине графа сценария и стимулу, допустимому в этой вершине, тестовый сценарий, который мы будем называть сценарным воздействием,
• η : VG x XG x V x S VG - отображение, ставящее в соответствие конечную вершину дуги графа сценария для данных начальной вершины и стимула графа сценария и состояний сценария и целевой системы после выполнения сценарного воздействия.

Автоматным механизмом построения тестового сценария называется функция, преобразующая автоматный тестовый сценарий ( IG, vg₀, α, S, ρ, γ, η ) в тестовый сценарий, посредством вспомогательного определения тестового сценария с внутренними переходами σ_ε = ( ( S', A, B, E, Q ), s₀ ) по следующим правилам:

• S' = VG x S { ε } x V x EG^* - состояние тестового сценария состоит из:
  • текущей вершины графа сценария vg,
  • текущего состояния сценария s, которое может принимать дополнительное значение ε, которое означает неинициализированное состояние,
  • текущего состояния целевой системы v,
  • пройденного маршрута в графе сценария path. Здесь множество EG^* обозначает множество всех конечных списков элементов из множества дуг EG = VG x XG x VG.
• множество стимулов A = X V { ε }, согласно определению тестового сценария с внутренними переходами;
• множество реакций B = (Y x V) { ε }, согласно определению тестового сценария с внутренними переходами;
• E = { ( ( vg, s, v, path ), a, b, ( vg', s', v', path' ) ) S' x A x B x S' | (α( IG, vg, path ) ≠ τ)
  (v' = state( a, b, v ))
  (s γ_Q( vg, xg ) (vg' = vg) (path' = path) ( s, a, b, s' ) γ_E( vg, xg ))
  (s γ_Q( vg, xg ) (vg' = η( vg, xg, v, s )) (path' = path ^ ( vg, xg, vg' ))
  (a = ε) (b = ε) (s' = ρ( s ))
  )
  }, где использовались следующие сокращения
• xg ≡ α( IG, vg, path );
• state( a, b, v ) = a, если a V;
• state( a, b, v ) = v_b, если b = ( y_b, v_b ) Y x V;
• state( a, b, v ) = v, иначе;
• Q = { ( vg, s, v₀, path ) S' | α( IG, vg, path ) = τ } - заключительными состояния сценария являются состояния, в которых алгоритм движения возвращает пустое действие τ;
• s₀(v₀) = ( vg₀(v₀), γ_S0( vg, α( IG, vg₀(v₀), ) )(v₀), v₀, ), если α( IG, vg₀(v₀), ) ≠ τ,
• s₀(v₀) = ( vg₀(v₀), ε, v₀, ), если α( IG, vs₀(v₀), ) = τ,
  - инициализирующая функция, которая устанавливает следующие начальные значения:
• текущая вершина графа сценария определяется при помощи функции инициализации графа сценария;
• текущее состояние сценария s принимает
• значение, вычисленное посредством инициализирующей функции первого сценарного воздействия, если таковое найдено при помощи алгоритм движения α,
• неинициализированное значение, в противном случае;
• текущее состояние целевой системы инициализируется параметром функции,
• пройденный маршрут инициализируется пустым списком.

Далее для построения тестового сценария автоматный механизм использует определенное ранее преобразование тестового сценария с внутренними переходами в тестовый сценарий без внутренних переходов.

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

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

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

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

Сценарные функции

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

Сценарной функцией для целевой системы с интерфейсом ( X, Y, V ) называется шестерка ( GS, PS, IS, C, is₀, π ), где:

• GS - множество внешних состояний;
• PS - множество параметризующих состояний;
• IS - множество внутренних состояний;
• C = ( CS, A, B, E, Q ) - управляющий автомат, в котором:
• CS = GS x PS x IS - состояние автомата состоит из декартова произведения всех видов состояний сценарной функции,
• A = X V,
• B = (Y x V) { ε },
• E CS x A x B x CS,
• Q CS;
• is₀ : V x GS IS - функция инициализации сценарной функции;
• π : V x GS (PS) - функция, определяющая множество параметризующих состояний для данных внешнего состояния и состояния целевой системы. Это множество мы будем называть множеством параметров.

Множество всех сценарных функций для целевой системы с интерфейсом ( X, Y, V ) и имеющее множество внешних состояний GS мы будем обозначать Σ( X, Y, V, GS ).

Автоматным тестовым сценарием со сценарными функциями для целевой системы с интерфейсом ( X, Y, V ) называется шестерка ( GS, gs₀, VG, vg, α, ), где:

• GS - множество глобальных состояний сценария;
• gs₀ : V GS - функция инициализации глобального состояния;
• VG - множество вершин графа автомата;
• vg : V x GS VG - функция вычисления вершины графа сценария;
• α - неизбыточный алгоритм движения по графу сценария,
• - конечный набор сценарных функций Σ_i Σ( X, Y, V, GS ).

Множества параметров всех сценарных функций должны быть согласованы с вершинами графа сценария:
i { 1, …, k } v₁,v₂ V gs₁,gs₂ GS

vg( v₁, gs₁ ) = vg( v₂, gs₂ ) π_Σi( v1, gs1 ) = π_Σi( v2, gs2 ).

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

Исходя из этого ограничения, можно определить множество параметров сценарной функции Σ_i в данной вершине графа vg как:

• πΣ_i( v, gs ), если v V gs GS : vg( v, gs ) = vg;
• {}, иначе.

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

Автоматным механизмом сценарных функций называется функция, преобразующая автоматный тестовый сценарий со сценарными функциями ( GS, gs₀, VG, vg, α, ) в тестовый сценарий, посредством применения автоматного механизма построения тестового сценария к автоматному тестовому сценарию ( IG', vg₀', α', S', ρ', γ', η' ), определенному по следующим правилам:

• неизбыточное описание ориентированного графа IG' = ( VG', XG', π' ) состоит из:
  • множества вершин, совпадающего с множеством вершин графа автомата VG (VG' = VG),
  • множества стимулов, являющегося дизъюнктивным объединением параметризующих состояний всех сценарных функций (XG' = ),
  • функции, определяющей множество допустимых стимулов π' = ;
• функция инициализации графа сценария vg0': vg0'(v) ≡ vg( v, gs0(v) );
• неизбыточный алгоритм α' = α;
• множество состояний сценария S' = GS x V x State,
  где State = {ε};
• функция рестарта сценария ρ': ρ'( (gs,v,state) ) ≡ ( gs, v, ε );
• сценарное воздействие γ'( vg, ps_i ) = ( ( S', A', B', E', Q' ), s'0 ) ( X, Y, V, S' ) определяется для каждой пары ( vg, ps_i ) следующим образом:
  • A' = X V,
  • B' = (Y x V) { ε },
  • E' = { ( ( gs, v, state ), a, b, ( gs', ( ps'_i, v', is'_i) ) ) :
    ( ( state = ε )
    ( ( gs, ps_i, is_i,0( v, gs ) ), a, b, ( gs', ps'_i, is'_i ) ) E_i
    )
    ( ( is_i IS_i state = ( ps_i, is_i) )
    ( ( gs, ps_i, is_i ), a, b, ( gs', ps'_i, is'_i ) ) E_i
    )
    ( a V ) v' = a
    ( b = ( y_b, v_b ) Y x V ) v' = v_b },
    
  • Q' = { ( gs, v, state ) S' :
    ( ( state = ε )
    ( gs, ps_i, is_i,0( v, gs ) ) Q_i
    )
    ( ( is_i IS_i state = ( ps_i, is_i) ) ( gs, ps_i, is_i ) Q_i
    )
    },
  • s'₀(v₀) = ( gs₀(v₀), v₀, ε );
• отображение η'( vg1, ps_i, v, ( gs, v2, state ) ) = vg( v, gs ).

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

Граф автоматного тестового сценария

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

Предположим, что σ_aut = ( IG, vg₀, α, S, ρ, γ, η ) - автоматный тестовый сценарий для целевой системы с интерфейсом ( X, Y, V ). Предположим, что σ = ( С, s₀ ) - тестовый сценарий, полученный посредством применения автоматного механизма построения тестового сценария к σ_aut. Тогда функционированиями автоматного тестового сценария σ_aut на целевой системе с начальным состоянием v₀ V будем называть все функционирования { e_j = ( s_j, a_j, b_j, s'_j ) } управляющего автомата C с начальным состоянием s₀( v₀ ).

Заметим, что согласно определению автоматного механизма построения тестового сценария состояниями управляющего автомата s_j являются четверки ( vg_j, s_j, v_j, path_j ) VG x S { ε } x V x EG^*.

Графом автоматного тестового сценария σ_aut = ( IG = ( VG, XG, π ), vg₀, α, S, ρ, γ, η ) при функционировании σ_aut { e_j = ( s_j, a_j, b_j, s'_j ) } называется ориентированный граф G' = ( VG', XG', EG' ), в котором:

• множество вершин VG' = VG;
• множество стимулов XG' = XG;
• множество дуг EG' = { eg VG x XG x VG : eg }, где под elems( path_j ) понимается множество всех элементов списка path_j.

Лемма.

Граф автоматного тестового сценария ( IG, vg₀, α, S, ρ, γ, η ) при любом функционировании { e_j = ( s_j, a_j, b_j, s'_j ) } удовлетворяет неизбыточному описанию IG.

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

Механизм построения тестового сценария dfsm

Основным механизмом построения тестовых сценариев в технологии UniTesK является механизм построения тестового сценария dfsm. Этот механизм основан на неизбыточном алгоритме обхода на классе детерминированных сильно-связных конечных ориентированных графов α_dfsm, представленном в работе [26].

Тестовым сценарием dfsm для целевой системы с интерфейсом ( X, Y, V ) называется автоматный тестовый сценарий со сценарными функциями, в котором в качестве алгоритма движения по графу сценария используется алгоритм обхода α_dfsm.

Механизмом построения тестового сценария dfsm называется функция, преобразующая тестовый сценарий dfsm в тестовый сценарий посредством применения автоматного механизма сценарных функций.

Как показано в [26], любое конечное функционирование тестового сценария dfsm приводит

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

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

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

• граф сценария при любом корректном функционировании целевой системы является детерминированным и сильно-связным;
• всякая сценарная функция при любом корректном функционировании целевой системы завершается за конечное число шагов;

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

Тестовый сценарий в унифицированной архитектуре теста

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

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

Первый вид взаимодействия соответствует подаче стимула x X и получению реакции y Y и постсостояния целевой системы v' V. Для осуществления такого взаимодействия тестовый сценарий обращается к оракулу, передавая ему стимул x X. Далее работа происходит по описанной ранее схеме. Оракул запоминает все необходимые части текущего модельного состояния v и передает стимул x медиатору. Медиатор оказывает тестовое воздействие, моделируемое посредством стимула x, получает реакцию целевой системы, преобразует ее в модельное представление y и синхронизирует текущее модельное состояние с внутренним состоянием реализации. Оракул, зная сохраненное состояние v, стимул x, реакцию y и текущее состояние v', выносит вердикт о корректности данного взаимодействия.

В качестве результата взаимодействия тестовый сценарий получает реакцию y Y и постсостояния целевой системы v' V. Последнее передается неявным образом через модельное состояние. Тестовый сценарий, получив эти данные, обновляет свое состояние и принимает решение о следующем взаимодействии.

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

Второй вид взаимодействия соответствует подаче стимула v V и "пустой" реакции целевой системы ε. В этом случае, тестовый сценарий обращается непосредственно к медиатору с указанием перевести целевую систему в состояние, соответствующее модельному состоянию v V. Медиатор выполняет данное указание и соответствующим образом обновляет модельное состояние.

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

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

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

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

Работа автоматного тестового сценария в случае тестирования со скрытым состоянием представлена на рисунке 7.

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

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

---

Далее