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

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

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

Статья выполнена в контексте тестирования на основе моделей (MBT, model based testing)², более точно, в контексте технологии тестирования UniTESK [3-5], хотя рассматриваемые в ней вопросы актуальны не только для этой технологии. Модель представляет собой некоторое достаточно абстрактное отображение структуры и поведения целевой системы, созданное на базе требований [6]. В процессе тестирования состояние модели можно интерпретировать, как располагаемую информация о состоянии целевой системы, сформулированную в терминах требований.

В работе предлагается подход к разработке функциональных спецификаций и генерации функциональных тестов, позволяющий работать с неполными требованиями к целевой системе и неполной информацией о ее состоянии. Подход основан на использовании неопределенных значений для моделирования состояния целевой системы, а также трехзначной логики Клини (Kleene) [7] для работы с требованиями и описания свойств системы. Результаты работы получены в ходе выполнения проекта по разработке открытого тестового набора OLVER для операционной системы Linux [8].

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

Технология тестирования UniTESK [3-5] была разработана в Институте системного программирования РАН [10] на основе опыта, полученного при разработке и применении технологии KVEST (kernel verification and specification technology) [11]. Общими чертами этих технологий являются использование формальных спецификаций в форме пред- и постусловий интерфейсных операций и инвариантов типов данных для автоматической генерации оракулов (компонентов тестовой системы, осуществляющих проверку правильности поведения целевой системы), а также применение конечно-автоматных моделей для построения последовательностей тестовых воздействий (тестовых последовательностей). В отличие от технологии KVEST, в которой для спецификации требований использовался язык RSL (RAISE specification language) [12], технология UniTESK использует расширения широко известных языков программирования.

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

• Построение последовательности тестовых воздействий (тестовой последовательности), нацеленной на достижение нужного покрытия.
• Создание единичного тестового воздействия в рамках тестовой последовательности.
• Установление связи между тестовой системой и реализацией целевой системы.
• Проверка правильности поведения целевой системы в ответ на единичное тестовое воздействие.

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

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

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

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

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

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

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

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

Понятно, что из-за различия в роде деятельности, полнота требований по-разному воспринимается разными группами лиц, связанных с программной системой. Например, для пользователя системы полнота требований, в первую очередь, означает возможность на их основе осуществить любой вариант использования системы (use case)⁵; для разработчика системы - правильно ее реализовать; для разработчика тестов - разработать полный набор тестов. Поскольку статья посвящена тестированию, полнота требований в ней рассматривается только с точки зрения разработчика тестов.

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

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

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

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

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

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

Пример. Целевая система является стеком. Интерфейс целевой системы состоит из следующих функций:

• Stack* create(void);
• void push(Stack *stack, Object *obj);
• Object* pop(Stack *stack).

Пусть требования к целевой системе формулируются следующим образом:

Функция create создает пустой стек и возвращает указатель на него. В случае, если стек не полностью заполнен, вызов функции push добавляет в него элемент, противном случае, вызов функции push не меняет состояние стека. Вызов функции pop для непустого стека возвращает последний добавленный в него элемент, для пустого стека - NULL.

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

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

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

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

Проиллюстрируем понятие контрактной полноты требований на следующем примере.

Пример. Рассмотрим целевую систему из предыдущего примера. Пусть требования к функции pop() формулируются следующим образом:

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

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

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

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

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

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

Поскольку в процессе тестирования возможна ситуация, когда состояние целевой системы не полностью определено, для моделирования состояния системы удобно использовать типы, поддерживающие неопределенные значения. Будем считать, что на множестве значений типов заданы отношения уточнения, являющиеся отношениями частичного порядка. Отношения уточнения позволяют сравнивать информативность значений: чем «больше» значение в отношении уточнения, тем больше информации оно несет (см. Рисунок 3). Введем несколько понятий.

Определение. Тип T с заданным на на нем отношением уточнения называется уточняемым типом. Отношение уточнения, заданное на типе T, будем обозначать _T или просто , если из контекста ясно, о каком типе идет речь.

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

Определение. Максимальные значения уточняемого типа T по отношению _T называются (полностью) определенными значениями типа T. Значения уточняемого типа T, не являющиеся полностью определенными, называются неопределенными или не полностью определенными значениями типа T.

Определение. Пусть T - уточняемый тип, тогда через T_c будем обозначать (полностью) определенный подтип типа T, то есть подтип, состоящий из всех полностью определенных значений типа T.

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

Пример. Рассмотрим пример уточняемого типа S_T, представляющего нечеткое множество значений типа T. Нечеткое множество s определяется трехзначной функцией принадлежности f_s: T → {true, false, }. f_s(x) интерпретируется следующим образом: если f_s(x) = true, то x принадлежит множеству s, если f_s(x) = false, то x не принадлежит множеству s, если f_s(x) = , то неизвестно, принадлежит x множеству s или нет. Отношение уточнения естественно определить таким образом: s₁ s_T s₂ тогда и только тогда, когда из того что f_s1(x) = true, вытекает, что f_s2(x) = true, а и из того, что f_s1(x) = false, вытекает, что f_s2(x) = false.

Определение. Пусть T₁, …, T_n - уточняемые типы. Определим на декартовом произведении T₁× … ×T_n отношение уточнения: (x₁, …, x_n) _{T1× ... ×Tn} (y₁, …, y_n) тогда и только тогда, когда x_{1 T1} y₁, …, x_{n Tn} y_n.

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

Определение. Функция f: T₁ → T₂ называется регулярной, если из того, что x _T1 y следует, что f(x) _T2 f(y).

Определение. Функция f: T₁ → T₂ называется полной, если f(T_1с) T_2с, то есть из того, что x T_1c следует, что f(x) T_2c.

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

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

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

Для не полностью определенных состояний целевой системы, не исключены ситуации, когда из-за недостатка информации некоторые логические условия нельзя отнести ни к истинным, ни к ложным. В таких случаях использование двузначной логики для описания свойств целевой системы представляется не совсем адекватным. Для того чтобы описать логическое условие P, которое может быть неопределенным, с помощью двух значений истинности нужно использовать специальные модальные функции возможности и необходимости: ◊P и □P⁶ и описать условие парой (◊P, □P)⁷. Тогда истинное условие описывается парой (true, true) (необходимо), ложное - парой (false, false) (невозможно), неопределенное - парой (true, false) (возможно, но не необходимо).

Описывать логические условия парой модальностей не очень удобно. Естественней положить, что функция истинности может принимать три значения: true (истина), false (ложь) и (неопределенность), а модальные функции возможности и необходимости рассматривать как функции {true, false, } → {true, false}, определяемые следующими таблицами истинности:

Впервые модальные функции возможности и необходимости подобным образом определил Лукасевич (Łukasiewicz), в трехзначной логике Ł₃ [15]. В логике Ł₃ неопределенное значение интерпретируется как промежуточное между ложью и истиной. В нашем случае неопределенное значение следует интерпретировать иначе - как неизвестное значение, которое может быть как истиной, так ложью, но какое оно именно - неизвестно.

Подобным образом неопределенное значение интерпретируется в трехзначной логике Клини (Kleene), называемой K₃. При получении дополнительной информации значение логического условия может измениться с неопределенного значения на false или true, но невозможно, чтобы значение изменилось с true на false или наоборот. Последнее требование называется требованием регулярности [7]. Если определить на множестве {true, false, } отношение уточнения, как показано на следующем рисунке, то регулярность условия означает его монотонность по отношению уточнения.

Рассмотрим логические связки ¬, и . Семантику связок можно определять по-разному, основным ограничением для нас является требование регулярности. Существуют два основных способа определения семантики связок: сильный (сильная логика K₃, сильные связки K₃) и слабый (слабая логика K₃, слабые связки K₃)⁸.

В дальнейшем мы будем использовать сильный вариант логики K₃.

Пример. Рассмотрим пример уточняемого типа S_T - нечеткое множество значений типа T. Нечеткое множество s определяется трехзначной функцией принадлежности f_s: T → {true, false, }. f_s(x) интерпретируется следующим образом: если f_s(x) = true, то x принадлежит множеству s, если f_s(x) = false, то x не принадлежит множеству s, если f_s(x) = , то неизвестно, принадлежит x множеству s или нет. Отношение уточнения естественно определить следующим образом: s₁ s_T s₂ тогда и только тогда, когда из того что f_s1(x) = true, вытекает, что f_s2(x) = true, а и из того, что f_s1(x) = false, вытекает, что f_s2(x) = false.

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

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

Пусть M - уточняемый тип, представляющий состояния модели, S - уточняемый тип, представляющий обобщенные состояния, а f: M → S - функция обобщения модели - функция, ставящая в соответствие каждому состоянию модели обобщенное состояние. Будем считать, что функция f является регулярной и полной. В этом случае она задает факторизацию на множестве полностью определенных значений типа M⁹. Для удобства будем считать, что f( _M) = _S.

Теперь рассмотрим естественное обобщение технологии тестирования UniTESK для генерации тестовых последовательностей на основе неопределенных обобщенных моделей.

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

1. тестовые воздействия, которые допустимы для этого состояния;
2. тестовые воздействия, которые недопустимы для этого состояния;
3. тестовые воздействия, для которых не известно, допустимы они или нет для этого состояния.

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

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

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

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

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

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

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

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

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

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

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

Определение. Ориентированным графом или просто графом G называется совокупность трех объектов (GV, GX, GE): GV - множество вершин, GX - множество раскрасок, GE GV×GX×GV - множество дуг.

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

Определение. Граф G называется конечным, если множества GV и GE конечны.

Определение. Граф G называется детерминированным, если для любых двух дуг (u₁, x₁, v₁) GE и (u₂, x₂, v₂) GE из того, что u₁ = u₂ и x₁ = x₂ следует, что v₁ = v₂.

Определение. Для графа G говорят, что стимул x GX допустим в вершине u GV, если в графе G существует дуга вида (u, x, v).

Определение. Маршрутом в графе G называется любая (возможно пустая) последовательность смежных дуг {(v_i, x_i, v_i+1)}_i=0,n-1, где n ≥ 0. При этом вершина v₀ называется началом маршрута, а вершина v_n - его концом.

Определение. Обходом графа G называется маршрут в графе G, содержащий все его дуги.

Определение. Граф G называется сильно-связным, если для любых двух вершин u, v GV существует маршрут в графе G с началом в вершине u и концом в вершине v.

Определение. Если на множестве GV вершин графа G задано отношение уточнения, будем говорить, что граф G является графом с уточняемыми вершинами.

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

Определение. Подграф G' = (GV', GX', GE') графа с уточняемыми вершинами G = (GV, GX, GE) называется полностью определенным, если все его вершины полностью определены, то есть GV' GV_c.

Определение. Подграф G' = (GV', GX', GE') графа с уточняемыми вершинами G = (GV, GX, GE) называется его информационной проекцией, если:

• вершины из GV' попарно несравнимы в отношении ;
• добаление в GV' любой вершины из GV\GV' нарушает первое свойство;
• множество дуг GE' содержит все дуги графа G, соединяющие вершины из GV'.

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

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

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

Определение. Граф с уточняемыми вершинами G называется открытым, если для любой его информационной проекции G' за исключением главной, существует дуга (u, x, v) GE\GE', раскрашенная стимулом, который отличается от стимулов дуг GE', выходящих из u.

Определение. Граф с уточняемыми вершинами G называется сильно-связным, если для любых двух вершин u, v GV либо существует маршрут, начинающийся в u и заканчивающийся в v, либо v u.

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

Определение. Дуга (u, x, v) в графе с уточняемыми вершинами называется уточняющей, если u v. Уточняющая дуга называется строго уточняющей, если u ≠ v.

Определение. Маршрут {(v_i, x_i, v_i+1)}_i=0,n-1 в графе с уточняемыми вершинами G называется уточняющим маршрутом, если для любых i и j, таких что 0 ≤ i < j ≤ n, либо v_i и v_j не сравнимы в отношении , либо v_i v_j. Уточняющий маршрут называется строго уточняющим, если i, j такие, что 0 ≤ i < j ≤ n и v_i v_j, v_i ≠ v.

Определение. Граф с уточняемыми вершинами называется монотонным, если в нем любой маршрут является уточняющим.

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

Определение. Строго уточняющий маршрут {(v_i, x_i, v_i+1)}_i=0,n-1 в графе с уточняемыми вершинами G называется простым, если никакой его префикс {(v_i, x_i, v_i+1)}_i=0,m-1, где m < n, не является строго уточняющим маршрутом.

Рассмотрим уточняющий маршрут P = {(v_i, x_i, v_i+1)}_i=0,n-1 в графе с уточняемыми вершинами G, начинающийся с неопределенной вершины: v₀ = . Его можно представить в виде конкатенации: P = P₀ … P_N-1 P_N (P_j={(v_i, x_i, v_i+1)}_i=kj,kj+1-1, 0 = k₀ < … < k_N+1 = n), в которой маршруты P_j для 0 ≤ j < N являются строго уточняющими, а маршрут P_N является уточняющим, но не является строго уточняющим маршрутом, то есть различные вершины маршрута P_N несравнимы в отношении уточнения.

Определение. Пусть GV_j={v_kj,…,v_kj+1-1}, где 0 ≤ j < N, - все вершины маршрута P_j кроме последней, GV_N={s_kN,…,s_kN+1} - все вершины маршрута P_N. Множество вершин GV_j, где 0 ≤ j ≤ N, будем называть уровнем неопределенности j уточняющего маршрута P. При этом для j < N будем говорить, что маршрут P_j уточняет вершины с уровня неопределенности j до уровеня неопределенности j+1.

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

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

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

Пример. Рассмотрим граф с множеством вершин {true, false, }× {true, false, }, каждая пара из которых соединена дугой. Маршрут P={( , ), (false, ), (true, ), (false, false), (true, )}¹⁰, очевидно, является уточняющим. Ему соответствуют три уровня неопределенности:

• GV₀ = {( , )};
• GV₁ = {(false, ), (true, )};
• GV₂ = {(false, false), (true, )}.

Видно, что уровни неопределенности GV₁ и GV₂ уточняющего маршрута P имеют общую вершину (true, ).

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

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

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

Как и в работе [16], будем считать, что алгоритму предоставляются две специальные внешние операции status(), возвращающая идентификатор текущей вершины, и call(x), которая осуществляет переход из текущей вершины по дуге, помеченной стимулом x. Для детерминированного графа такая дуга, если существует, то единственная. Предусловием операции call(x) является допустимость стимула x в текущей вершине. Маршрут строится алгоритмом как последовательность дуг, проходимых последовательными вызовами операции call().

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

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

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

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

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

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

Рассмотрим общую схему неизбыточных алгоритмов обхода графов.

// пока есть незавершенные вершины
while (!сompleted())
{
  // если текущая вершина незавершена
  if (next(status()) !=  )
  {
    // подать очередной стимул
    call(next(status()));
  }
  else
  {
    // попасть в пройденную незавершенную вершину
    rollback();
  }
}

Операция completed() возврашает true тогда и только тогда, когда в графе все вершины завершены, то есть не существует вершин графа, из которых ведут не пройденные дуги.

Операция rollback() строит маршрут из текущей вершины в вершину, в которой есть еще не пройденные дуги. Подходы к реализации этой операции могут быть различными. Алгоритмы, основанные на обходе остова графа, выбирают самую дальнюю от корня (поиск в глубину) или самую ближнюю к корню (поиск в ширину) незавершенную вершину, достижимую из текущей [16]. Другим подходом (жадный алгоритм) является выбор ближайшей достижимой незавершенной вершины, но это требует больших затрат памяти¹¹.

Утверждение. Для графов с уточняемыми вершинами, являющихся:

• конечными,
• монотонными,
• детерминированными,
• открытыми,
• сильно-связными

существует неизбыточный алгоритм уточняющего обхода.

Доказательство. Рассмотрим следующий алгоритм, точнее его идею, в рамках определенной ранее схемы. Поскольку граф является монотонным, любой маршрут в нем является уточняющим, следовательно, для него определены уровни неопределенности. Алгоритм хранит в памяти некоторую структуру данных, связанных с текущим уровнем неопределенности, например, подобную описанной в работе [16].

Операция complete() возвращает true тогда и только тогда, когда все пройденные вершины на текущем уровне неопределенности завершены, то есть операция next() для них возвратила ε .

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

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

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

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

Инструмент CTesK является реализацией концепции UniTESK для языка программирования C. Для разработки компонентов тестовой системы в нем используется язык SeC (specification extension of C), являющийся расширением ANSI C. Инструмент CTesK включает в себя транслятор из языка SeC в C, библиотеку поддержки тестовой системы, библиотеку спецификационных типов и генераторы отчетов. Для пользователей Windows имеется модуль интеграции в среду разработки Microsoft Visual Studio 6.0.

Компоненты тестовой системы UniTESK реализуются в инструменте CTesK с помощью специальных функций языка SeC, к которым относятся:

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

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

typedef enum
{
  True_Bool3    =  1, // истина
  False_Bool3   =  0, // ложь
  Unknown_Bool3 = -1  // неопределенное значение
} Bool3;

// отрицание
Bool3 not_Bool3(Bool3 arg);
// дизъюнкция
Bool3  or_Bool3(Bool3 lhs, Bool3 rhs);
// конъюнкция
Bool3 and_Bool3(Bool3 lhs, Bool3 rhs);

Для удобства работы со значениями типа Bool3 также в библиотеку CTesK можно добавить модальные функции возможности и необходимости:

// модальная функция возможности
bool   may_Bool3(Bool3 arg);
// модальная функция необходимости
bool shall_Bool3(Bool3 arg);

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

bool refines(Object *lhs, Object *rhs);

Функция возвращает значение true тогда и только тогда, когда спецификационный объект rhs уточняет спецификационный объект lhs.

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

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

{ "Описание ветви функциональности", Unknown };

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

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

7. Заключение

В работе были рассмотрены вопросы функционального тестирования программных систем в условиях неполной информации. На базе технологии тестирования UniTESK предложен подход к разработке функциональных спецификаций и генерации функциональных тестов, основанный на использовании неопределенных значений для моделирования состояния целевой системы, а также трехзначной логики Клини для работы с неполными требованиями и описания свойств системы. Идеи предложенного подхода нашли свое применение в проекте по разработке открытого тестого набора OLVER для операционной системы Linux.

Литература

1.обратно	D. Dibois, H. Prade. Théorie des possibilités. Applications à la representation des connaissances en informatique. MASSON, Paris, Milan, Barselone, Mexico, 1988 (Дюбуа Д., Прад А. Теория возможностей. Приложения к представлению знаний в информатике: Пер. с фр. - М.: Радио и связь, 1990.)
2.обратно	Ю. П. Пытьев. Возможность. Элементы теории и применения. М.: Эдиториал УРСС, 2000.
3.обратно	сайт, посвященный технологии тестирования UniTESK и реализующим ее инструментам.
4.обратно	А. В. Баранцев, И. Б. Бурдонов, А. В. Демаков, С. В. Зеленов, А. С. Косачев, В. В. Кулямин, В. А. Омельченко, Н. В. Пакулин, А. К. Петренко, А. В. Хорошилов. Подход UniTesK к разработке тестов: достижения и перспективы. (Опубликовано здесь.)
5.обратно	В. В. Кулямин, А. К. Петренко, А. С. Косачев, И. Б. Бурдонов. Подход UniTESK к разработке тестов. Программирование, 29(6): 25-43, 2003.
6.обратно	А. Петренко, Е. Бритвина, С. Грошев, А. Монахов, О. Петренко. Тестирование на основе моделей. Открытые системы, №09/2003. (Опубликовано здесь.)
7.обратно	M. Fitting. Kleene's three-valued logics and their children. Fundamenta Informaticae, 20, 113-131, 1994.
8.обратно	сайт Центра верификации операционной системы Linux.
9.обратно	страница инструмента разработки тестов CTesK.
10.обратно	сайт Института системного программирования РАН.
11.обратно	I. Bourdonov, A. Kossatchev, A. Petrenko, and D. Galter. KVEST: Automated Generation of Test Suites from Formal Specifications. FM'99: Formal Methods. LNCS 1708, Springer-Verlag, 1999, pp. 608-621.
12.обратно	The RAISE Language Group. The RAISE Specification Language. Prentice-Hall BCS Practitioner Series. Prentice-Hall, Inc., 1993.
13.обратно	А. В. Хорошилов. Спецификация и тестирование систем с асинхронным интерфейсом. Институт системного программирования РАН, Препринт 12, 2006.
14.обратно	A. Tarski. Introduction to Logic and to the Methodology of Deductive Sciences. New York, 1941. (А. Тарский. Введение в логику и методологию дедуктивных наук. М.: ГИИЛ, 1948.)
15.обратно	Я. А. Слинин. Современная модальная логика. Развитие теории алетических модальностей (1920 - 1960 гг.). Издательство Ленинградского университета, 1976.
16.обратно	И. Б. Бурдонов, А. С. Косачев, В. В. Кулямин. Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай. Программирование. т. 29, № 5, стр. 245-258, 2003.