ТЕСТИРОВАНИЕ, ВЕРИФИКАЦИЯ И ВАЛИДАЦИЯ ПРОГРАММ
УДК 004.92+004.94
СИСТЕМЫ С ПРИОРИТЕТАМИ: КОНФОРМНОСТЬ, ТЕСТИРОВАНИЕ, КОМПОЗИЦИЯ
© 2009 г. И. Б. Бурдонов, А. С. Косачев
Институт системного программирования РАН 109004 Москва, ул. Солженицына, 25 E-mail: {igor,kos} @ispras.ru Поступила в редакцию 15.07.2008 г.
В статье представлен подход к моделированию компонентов распределенных систем, взаимодействие которых построено на обработке событий с учетом их приоритетов. Несмотря на широкое использование на практике приоритетной обработки запросов или сообщений, математические модели взаимодействия таких программ чаще всего абстрагируются от приоритетов, вводя излишний недетерминизм в описание их поведения. Предложенный подход пытается избежать этого недостатка за счет определения параллельной композиции, моделирующей взаимодействие такого рода. Основное содержание статьи - построение формальной теории тестирования компонентов, использующих приоритеты. В рамках этой теории вводятся понятие безопасного выполнения модели и отношение конформности между моделями, а также рассматриваются вопросы построения наборов тестов, проверяющих конформность.
ВВЕДЕНИЕ
В существующих теориях тестирования конформности (conformance testing) подразумевается отсутствие приоритетов между действиями, которые тестируемая система может выполнять в данной ситуации [1]. Это называется правилом недетерминированного выбора на выполнение одного из таких действий. В то же время для реальных программных и аппаратных систем это правило не всегда адекватно отражает требуемое поведение системы. Рассмотрим несколько примеров.
Выход из дивергенции. Под дивергенцией понимается бесконечная внутренняя активность ("зацикливание") системы. Запрос, поступающий извне, может бесконечно долго игнорироваться системой, если он имеет тот же приоритет, что внутренняя активность. Заметим, что внутренняя активность может быть инициирована предыдущим запросом. Если речь идет о составной системе, собранной из нескольких компонентов, то такая внутренняя активность может быть естественным результатом взаимодействия компонентов между собой. И в этом случае для обработки запроса, поступающего в систе-
му (в один из ее компонентов) извне, он должен иметь больший приоритет, чем внутреннее взаимодействие.
Выход из осцилляции (приоритет приема над выдачей). Под осцилляцией понимается бесконечная цепочка выдачи сообщений системой. Для того, чтобы такую цепочку можно было прервать, заставив систему обрабатывать поступающий извне запрос, последний должен иметь больший приоритет, чем выдача сообщений.
Приоритет выдачи над приемом в неограниченных очередях. Этот обратный пример характерен для неограниченной очереди, используемой в качестве буфера между взаимодействующими системами, в частности, при асинхронном тестировании (тестировании в контексте). Здесь нужно, чтобы выборка из очереди была приоритетней постановки в очередь. В противном случае очередь имеет право только принимать сообщения и никогда их не выдавать. При асинхронном тестировании для входной очереди это означает, что все входные сообщения, посылаемые тестом, не доходят до реализации, бесконечно накапливаясь в очереди. Соответственно, для выходной очереди это означает, что тест мо-
жет не получать никаких ответных сообщений от реализации, хотя она их выдает, поскольку они "оседают" в очереди.
Прерывание цепочки действий. Команда "отменить" (cancel) должна останавливать выполнение последовательности действий, инициированной предыдущим запросом, и вызывать цепочку завершающих действий. При отсутствии приоритетов такая команда, даже если она выдана сразу после выдачи запроса, имеет право быть выполнена только после того, как вся обработка закончится, то есть фактически ничего "не отменяет".
Приоритетная обработка входных воздействий. Если в систему поступает одновременно несколько запросов, то часто требуется их обработка в соответствии с некоторыми приоритетами между ними. Это часто реализуется в виде очереди запросов с приоритетами или в виде нескольких очередей запросов с приоритетами между очередями. К этому типу приоритетов относится и обработка аппаратных прерываний в операционной системе.
Отсутствие приоритетов в моделях hardware и software систем не дает возможности проверять при тестировании выполнение тех требований к системе, которые могут быть выражены только в форме приоритетов. В данной статье предлагается способ введения приоритетов в теорию конформности: в семантику взаимодействия и модель системы, в отношение конформности, в методы генерации тестов и оператор композиции (сборки составной системы из взаимодействующих между собой компонентов). Теория конформности без приоритетов кратко описана в нашей статье [2], подробное изложение с доказательствами утверждений содержится в диссертации одного из авторов данной статьи [3], теория конформности для класса так называемых ^7^-семантик излагается в книге [4]. Здесь мы сначала повторим основные положения этой теории, а затем модифицируем их для случая приоритетов.
1. ТЕОРИЯ КОНФОРМНОСТИ БЕЗ ПРИОРИТЕТОВ
1.1. Семантика взаимодействия и безопасное тестирование
Верификация конформности понимается как проверка соответствия исследуемой системы заданным требованиям. В модельном мире систе-
Машина тестирования
А, В, C,...cL
ШЕШ
ЩШЛ1
Рис. 1.
ма отображается в реализационную модель (реализацию), требования - в спецификационную модель (спецификацию), а их соответствие - в бинарное отношение конформности. Если требования выражены в терминах взаимодействия системы с окружающим миром, возможно тестирование как проверка конформности в процессе тестовых экспериментов, когда тест подменяет собой окружение системы. Само отношение конформности и его тестирование основаны на той или иной модели взаимодействия.
Мы будем рассматривать такие семантики взаимодействия, которые основаны только на внешнем, наблюдаемом поведении системы и не учитывают ее внутреннее устройство, отображаемое на уровне модели в понятии состояния. В этом случае говорят о тестировании методом "черного ящика", или функциональном тестировании. Мы можем наблюдать только такое поведение реализации, которое, во-первых, "спровоцировано" тестом (управление) и, во-вторых, наблюдаемо во внешнем взаимодействии. Такое взаимодействие может моделироваться с помощью так называемой машины тестирования [1-6]. Она представляет собой "черный ящик", внутри которого находится реализация (рис. 1). Управление сводится к тому, что оператор машины, выполняя тест (понимаемый как инструкция оператору), нажимает какие-то кнопки на клавиатуре машины, "приказывая" или "разрешая" реализации выполнять те или иные действия, которые могут им наблюдаться. Наблюдения (на "дисплее" машины) бывают двух типов: наблюдение некоторого действия, разрешенного оператором и выполняемого реализацией, и наблюдение отказа как отсутствия каких бы то ни было действий из числа тех, что разрешены нажатыми кнопками. Мы будем обозначать действия строчными буквами, а отказы (как множества действий) - прописными.
Следует подчеркнуть, что при управлении оператор разрешает реализации выполнять именно множество действий, а не обязательно
одно действие. Например, при тестировании реактивных систем, основанных на обмене стимулами и реакциями, посылка одного стимула из теста в реализацию может интерпретироваться как разрешение реализации выполнять только одно действие - прием этого стимула. Однако прием тестом ответной реакции должен означать разрешение реализации выдавать любую реакцию как раз для того, чтобы проверить, правильна эта реакция или нет. Мы будем считать, что оператор нажимает одну кнопку, но на кнопке "написано", вообще говоря, не одно действие, а множество разрешаемых действий. Когда происходит наблюдение (действие или отказ), кнопка автоматически отжимается, и все внешние действия считаются запрещенными. Далее оператор может нажимать другую (или ту же самую) кнопку.
В то же время "кнопочное" множество - это, вообще говоря, не любое подмножество множества всех действий. В вопросе о том, какие множества действий могут разрешаться тестом, а какие нет, среди исследователей существует большое разнообразие точек зрения. Например, для реактивных систем обычно считается, что нельзя (или бессмысленно) смешивать посылку стимулов с приемом реакций (Ян Тритманс). Но существует и прямо противоположный подход: нельзя "тормозить" выдачу реакций реализацией, поэтому, даже посылая стимул, тест должен быть готов к приему любой реакции (А.Ф. Петренко в [7]).
Также следует подчеркнуть, что наблюдение отказа возможно не при любой кнопке. И здесь разные исследователи опираются на разные предположения. Для тех же реактивных систем долгое время считалось, что тест может наблюдать отсутствие реакций (quiescence, стационарность), например, по тайм-ауту, но не видит, принимает реализация посланный ей стимул или нет (input refusal, блокировка стимула). С другой стороны, в последние годы появляется все больше и больше работ, в которых такие блокировки стимулов допускаются или допускаются частично [2, 4, 8-14]. Также и реакции, если они принимаются тестом по разным "выходным каналам", можно принимать не все, а лишь те, которые относятся к одному или нескольким выбранным каналам [12, 13].
Итак, семантика взаимодействия определяется тем, какие (в принципе) существуют наблюдаемые действия (алфавитом внешних действий Ь), какие множества действий может разрешать тест (набором кнопок машины тестирования), и для каких из этих кнопок наблюдаемы соответствующие отказы (семейством Ж С Р(Ь)), а для каких нет (семейством Д С Р(Ь)). Предполагается, что Ж П О = 0 и иЖ и иД = Ь. Такую семантику мы называем Ж/Д-семантикой.
Кроме внешних, наблюдаемых действий реализация может совершать внутренние, ненаблюдаемые (и, следовательно, неразличимые оператором) действия, которые обозначаются символом т. Выполнение таких действий не регулируется оператором - они всегда разрешены. Предполагается, что любая конечная последовательность любых действий совершается за конечное время,
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.