ПРОГРАММИРОВАНИЕ, 2009, no 6, с. 3-18
ТЕСТИРОВАНИЕ, ВЕРИФИКАЦИЯ И ВАЛИДАЦИЯ ПРОГРАММ
УДК 004.92+004.94
ПОЛНОЕ ТЕСТИРОВАНИЕ С ОТКРЫТЫМ СОСТОЯНИЕМ ОГРАНИЧЕННО НЕДЕТЕРМИНИРОВАННЫХ СИСТЕМ
© 2009 г. И. Б. Бурдонов, А. С. Косачев
Институт системного программирования РАН 109004 Москва, ул. Солженицына, 25 E-mail: {igor,kos} @ispras.ru Поступила в редакцию 19.03.2009 г.
В статье представлен подход к проблеме полноты тестирования, под которым понимается проверка соответствия реализации требованиям, описываемым спецификацией. Полнота означает, что тесты обнаруживают все возможные ошибки в реализации. На практике тестирование должно заканчиваться за конечное время. Требования полноты и конечности в общем случае противоречат друг другу. Тем не менее, конечные полные тесты удается построить для ограниченных классов реализаций и спецификаций при наличии специальных тестовых возможностей. Предложены алгоритмы тестирования и дана оценка их сложности для конечных спецификаций и конечных реализаций с ограниченным недетерминизмом при тестировании с открытым состоянием.
ВВЕДЕНИЕ
Тестирование - это проверка в процессе эксперимента соответствия (конформности) реализации требованиям, заданным в виде спецификации. Тестирование полное, если оно однозначно отвечает на вопрос: есть в реализации ошибки или нет, где под ошибкой понимается нарушение требований, то есть неконформность. Для практического применения тестирование должно заканчиваться за конечное время. В общем случае тестирование оказывается либо неполным, либо бесконечным. Решение проблемы можно искать, сужая класс рассматриваемых реализаций и используя дополнительные тестовые возможности. В некоторых случаях удается построить тесты, которые конечны и полны, но только для заданных классов реализаций и спецификаций при дополнительных тестовых возможностях.
Основными причинами бесконечности полного тестирования являются объем реализации и/или спецификации и недетерминизм реализации.
Если объем требований бесконечен, нельзя их все проверить за конечное время: конечное тестирование по бесконечной спецификации заведомо неполно. Если хотя бы одно из требований нужно проверять в реализации в бесконечном
числе ситуаций, то за конечное время это также нельзя сделать. Для полноты конечного тестирования реализация также должна быть конечной.
Однако конечности реализации недостаточно, если ее объем неизвестен: ни в какой момент времени мы не можем знать, все ли ситуации, возможные в реализации, проверены, или нет. Нам нужно оценить объем реализации либо заранее, предполагая не только его конечность, но и ограниченность, либо в процессе тестирования. В последнем случае нужны дополнительные тестовые возможности, позволяющие наблюдать в том или ином виде протестированную часть реализации и делать выводы о наличии или отсутствии других частей.
Если поведение реализации недетерминирова-но без всяких ограничений, то ни в какой момент времени мы не можем знать, продемонстрировала ли реализация все варианты своего поведения или нет. Для полноты конечного тестирования на недетерминизм реализации приходится налагать те или иные ограничения.
В статье рассматривается тестирование конечной реализации по конечной спецификации с двумя дополнительными предположениями: 1) тестирование с открытым состоянием - у нас есть возможность наблюдать состояния ре-
А, В, С,...сЪ
а; ш
ШШ1 ^^Вк.
Рис. 1. Машина тестирования.
ализации, в которых она оказывается в процессе тестирования, 2) реализация ограниченно-недетерминирована - если одно и то же тестовое воздействие повторяется в одном и том же состоянии реализации достаточное, известное заранее число раз, то реализация демонстрирует все возможные варианты поведения. Для этого случая мы предлагаем алгоритмы конечного и полного тестирования и даем оценки числа тестовых воздействий и объема вычислений.
Первый раздел статьи содержит основные положения теории конформности, изложенной в [1-3]. Во втором разделе обсуждаются проблемы практического тестирования и пути их решения. В третьем разделе предлагаются алгоритмы обхода, а в четвертом разделе - алгоритмы тестирования реализации, доказывается конечность и полнота тестирования и приводятся оценки сложности.
1. ТЕОРИЯ КОНФОРМНОСТИ
1.1. Семантика взаимодействия и безопасное тестирование
Верификация конформности понимается как проверка соответствия исследуемой системы заданным требованиям. В модельном мире система отображается в реализационную модель (реализацию), требования - в спецификационную модель (спецификацию), а их соответствие - в бинарное отношение конформности. Если требования выражены в терминах взаимодействия системы с окружающим миром, возможно тестирование как проверка конформности в процессе тестовых экспериментов, когда тест подменяет собой окружение системы. Само отношение конформности и его тестирование основаны на той или иной модели взаимодействия.
Мы рассматриваем семантики взаимодействия, которые основаны только на внешнем, наблюдаемом поведении системы и не учитывают ее внутреннее устройство, отображаемое на
уровне модели в понятие состояния. Мы можем наблюдать только такое поведение реализации, которое, во-первых, "спровоцировано" тестом (управление) и, во-вторых, наблюдаемо во внешнем взаимодействии. Такое взаимодействие может моделироваться с помощью так называемой машины тестирования [1-6]. Она представляет собой "черный ящик", внутри которого находится реализация (рис. 1). Управление сводится к тому, что оператор машины, выполняя тест (понимаемый как инструкция оператору), нажимает кнопки на клавиатуре машины, "разрешая" реализации выполнять те или иные действия, которые могут им наблюдаться. Наблюдения (на "дисплее" машины) бывают двух типов: наблюдение некоторого действия, разрешенного оператором и выполняемого реализацией, и наблюдение отказа как отсутствия каких бы то ни было действий из числа тех, что разрешены нажатыми кнопками. Мы будем обозначать действия строчными буквами, а отказы (как множества действий) - прописными.
Подчеркнем, что при управлении оператор разрешает реализации выполнять именно множество действий, а не обязательно одно действие. Каждой кнопке соответствует свое множество разрешаемых действий. После наблюдения (действия или отказа) кнопка отжимается, и все внешние действия запрещаются. Далее оператор
может нажать другую (или ту же самую) кнопку.
Тестовые возможности определяются тем, какие "кнопочные" множества есть в машине, а также тем, для каких кнопок возможно наблюдение отказа. Тем самым, семантика взаимодействия определяется алфавитом внешних (наблюдаемых) действий Ь и двумя наборами кнопок машины тестирования: с наблюдением соответствующих отказов - семейство Ш С V(Ь) и без наблюдения отказа - семейство Д С Р(Ь). Предполагается, что ШПД = 0 и иШииД = Ь. Такую семантику мы называем Ш/Д-семантикой.
В [1,3] показано, что достаточно ограничиться семантиками, в которых все отказы наблюдаемы: Д = 0. Любая Ш/Д-семантика эквивалентна Ш и Д/0-семантике: для любой спецификации в Ш/Д-семантике существует (и может быть построена при некоторых, практически приемлемых, ограничениях) спецификация в
R U Q/0-семантике, определяющая тот же класс конформных реализаций и не меньший класс реализаций, поддающихся тестированию. Поэтому мы будем рассматривать только R-семантики, то есть будем считать, что Q = 0.
Для выполнимости действия необходимо, чтобы оно было определено в реализации и разрешено оператором. Если этого условия также и достаточно, то в системе нет приоритетов. Мы ограничимся только такими системами.
Кроме внешних действий реализация может совершать внутренние (ненаблюдаемые) действия, обозначаемые символом т. Эти действия всегда разрешены. Предполагается, что любая конечная последовательность любых действий совершается за конечное время, а бесконечная -за бесконечное время. Бесконечная последовательность т-действий ("зацикливание") называется дивергенцией и обозначается символом А. Кроме этого, мы вводим специальное, также не регулируемое кнопками, действие, которое называем разрушением и обозначаем символом 7. Оно моделирует любое запрещенное при тестировании поведение реализации. Дивергенция сама по себе не опасна, но при попытке выхода из нее, когда оператор нажимает любую кнопку, он не знает, нужно ли ждать наблюдения или бесконечно долго будут выполняться только внутренние действия. Поэтому оператор не может ни продолжать тестирование, ни закончить его. Тестирование, при котором не возникает разрушения и попыток выхода из дивергенции, называется безопасным.
1.2. LTS-модель и ее трассы
В качестве модели реализации и спецификации мы используем систему помеченных переходов (LTS - Labelled Transition System) - ориентированный граф с выделенной начальной вершиной, дуги которого помечены некоторыми символами. Формально, LTS - это совокупность S = = LTS(Vs, L, Es, so), где Vs - непустое множество состояний (вершин графа), L - алфавит внешних действий, Es Q Vs х (L U {т, 7}) х Vs -множество переходов (помеченных дуг графа), so £ Vs - начальное состояние (начальная вершина графа). Переход из состояния s в состояние
s' по действию z обозначается s
Обозна-
чим s
= ш / = s' s
s' и s
= /s' s
-— s'. Маршрутом LTS называется последовательность смежных переходов: начало каждого перехода, кроме первого, совпадает с концом предыдущего перехода.
Выполнение LTS в машине тестирования сводится к выполнению того или иного перехода, определенного в текущем состоянии и разрешаемого нажатой кнопкой (т- и 7-переходы всегда разрешены).
Состояние стабильно, если из него не выходят т- и 7-переходы, и дивергентно, если в нем начинается бесконечная цепочка т-переходов (в частности, т-цикл). Отказ P £ R порождается стабильным состоянием, из которого нет переходов по действиям из P. Переход s s' разрушающий, если из s' по цепочке (возможно, пустой) т-переходов достижимо начало 7-перехода.
Добавим в каждом стабильном состоянии LTS S виртуальные петли, помеченные порождаемыми отказами, и А-переходы из дивергентных состояний. В полученной LTS рассмотр
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.