ТЕСТИРОВАНИЕ, ВЕРИФИКАЦИЯ И ВАЛИДАЦИЯ ПРОГРАММ
УДК 681.3.06
ИСПОЛЬЗОВАНИЕ СВОЙСТВ МУТАЦИОННЫХ АВТОМАТОВ ДЛЯ МИНИМИЗАЦИИ ПРОВЕРЯЮЩИХ ТЕСТОВ
© 2012 г. К. Эль-Факи1, Н. Евтушенко2, М. Дорофеева2 1 Американский Университет Шарджа
Sharjah, UAE PO Box 26666 2 Томский государственный университет, 634050 Томск, пр. Ленина 36 E-mail: kelfakih@aus.ac.ae, ninayevtushenko@yahoo.com, mgrace@sibmail.com
Поступила в редакцию 15.01.2012 г.
В статье предлагается усовершенствование метода построения полных проверяющих тестов для конечных автоматов относительно класса неисправностей, представленного множеством всех полностью определенных детерминированных подавтоматов специального мутационного автомата, число состояний которого может быть больше числа состояний в эталонном автомате. Идея метода заключается в использовании информации об известной части мутационного автомата, за счет чего в ряде случаев исчезает экспоненциальная зависимость длины проверяющего теста от разности числа состояний проверяемого и эталонного автоматов. Экспериментально показано, что для случайно сгенерированных автоматов длина теста, построенного предложенным методом, пропорциональна произведению числа состояний мутационного автомата на число переходов, подлежащих проверке.
1. ВВЕДЕНИЕ
Конечные автоматы широко используется в качестве математической модели для описания поведения дискретных систем управления, в том числе, для тестирования протокольных реализаций и программного обеспечения. Тестирование имеет своей целью контроль правильности функционирования системы и заключается в подаче на вход проверяемой системы определенных входных воздействий -тестовых последовательностей, и наблюдении соответствующих выходных реакций. Для построения качественных проверяющих тестов необходима формальная модель неисправности, которая обычно включает описание эталонного поведения, конечное множество возможных неисправностей и критерий исправности системы, так называемое отношение конформности. При использовании автоматного подхода обычно предполагается, что поведение любой системы с интересующими нас неисправностями описывается автоматом
из области неисправности. Если множество входных последовательностей (проверяющий тест) может обнаружить каждую систему, не эквивалентную эталонной, то такое множество входных воздействий называется полным проверяющим тестом (относительно заданной области неисправности).
Большинство известных работ по построению проверяющих тестов посвящено синтезу тестов относительно модели "черного ящика". Известными методами построения тестов относительно данной модели являются W-ме-тод'[2], HSI-метод [3], Wp-метод [4], UIOv-метод [5], H-метод [6], SPY-метод [7]. Методы построения тестов для детерминированных автоматов относительно модели "черного ящика", доставляют качественные, но, к сожалению, очень длинные тесты.
С практической точки зрения модель "черного ящика" является достаточно абстрактной, поскольку часто известна некоторая информация о структуре переходов или других
свойствах проверяемого автомата. В этом случае проверяющий тест можно строить относительно так называемой модели "серого ящика". При использовании модели "серого ящика" [8-11] область неисправности представляется как множество всех детерминированных полностью определенных подавтоматов заданного недетерминированного автомата, называемого мутационным автоматом. Мутационный автомат определяется на основе эталонного автомата, и соответственно эталонный автомат эквивалентен некоторому подавтомату мутационного автомата. С помощью мутационного автомата могут быть описаны области неисправности, традиционно рассматриваемые в технической диагностике [12, 13], а также неисправности расширенных автоматов, которые используются при описании телекоммуникационных протоколов [8]. Более того, мутационные автоматы специального вида позволяют представить области неисправности, рассматриваемые в теории экспериментов с автоматами: множество всевозможных детерминированных автоматов не более чем с т состояниями и множество автоматов со всевозможными выходными неисправностями. Специальные виды мутационного автомата представляют неисправности на переходах, неисправности типа перепутывания или блокирования входных сигналов в автомате и т.п. [14]. Кроме описанных ситуаций, мутационный автомат может с успехом применяться в задаче тестирования автоматной сети в предположении, что не более чем одна компонента сети может быть неисправной. В этом случае все неисправные сетевые автоматы могут быть представлены как подавтоматы специально построенного мутационного автомата [15, 16]. Также мутационные автоматы интересны при так называемом регрессивном тестировании, когда эталонная система модифицируется в процессе жизненного цикла, и при каждой модификации тест генерируется только для проверки внесенных изменений.
Очевидно, что во всех перечисленных случаях область неисправности может быть задана путем ограничения числа состояний в проверяемых автоматах, однако применение мутационного автомата позволяет избежать
рассмотрения "лишних" проверяемых автоматов и, как следствие, позволяет строить более короткие тесты, полнота которых известна и удовлетворяет разработчиков. Таким образом, модель неисправности на основе мутационного автомата является достаточно компактной, и в то же время позволяет описывать реальные неисправности.
В настоящее время существует большое количество работ, посвященных методам построения тестов относительно модели "серого ящика". В работе [17] тест строится для случая, когда эталонный и мутационный автоматы имеют одно и то же число состояний, и для сокращения длины теста используется информация об уже проверенных переходах тестируемого автомата. Однако авторам не удалось распространить предложенный метод на общий случай, когда мутационный автомат имеет больше состояний, чем эталонный автомат. Методы построения тестов относительно мутационного автомата, предложенные в работах [8, 9], кроме недетерминизма переходов в мутационном автомате, учитывают дополнительные свойства преемников состояний в мутационном автомате и дают дополнительные возможности сокращения проверяющего теста. Однако эти методы также разработаны только для случая, когда мутационный и эталонный автоматы имеют одинаковое число состояний. Для случая, когда мутационный автомат имеет больше состояний, чем эталонный автомат, метод синтеза проверяющего теста предложен в работе [18]. Однако этот метод является эффективным, если число возможных, в том числе неисправных, переходов из каждого состояния по каждому входному символу в мутационном автомате не слишком большое.
В данной работе мы предлагаем метод построения проверяющих тестов относительно мутационного автомата, в котором имеются переходы только двух типов: детерминированные и полностью неопределенные (хаосные). В отличие от других методов предлагаемый метод построения теста может быть использован в случае, когда число состояний проверяемого автомата может превышать число состояний эталонного
автомата, а эталонный автомат может быть частичным.
2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ОБОЗНАЧЕНИЯ
Под конечным автоматом или просто автоматом в данной работе понимается инициальный, полностью определенный, возможно, недетерминированный автомат, т.е. шестерка объектов S = (Б, X, У, ,81) [1], где 5 - конечное непустое множество состояний с выделенным начальным состоянием 81, X и У - конечные входной и выходной алфавиты соответственно, а С Б х X х Б х У -отношение переходов, в котором для каждой пары (8, ж) € Б х X существует хотя бы одна пара у) € Б х У, такая что (8, ж, у) € . Говорят, что переход из состояния в под воздействием входного символа х является детерминированным, если существует только одна пара (8', у) € Б х У, такая что (8, ж, в', у) € . Иначе переход из состояния 8 под действием входного символа ж является недетерминированным. Переход из состояния 8 называется хаосным, если из данного перехода под действием входного символа ж возможны переходы в любые состояния с любыми выходными символами.
Автомат называется детерминированным, если для каждой пары (8, ж) € Б х X существует только одна пара (8', у) € Б х У такая, что (8, ж, 8', у) € . В детерминированном полностью определенном автомате вместо отношения поведения обычно используют две функции: функцию переходов : Б х X ^ Б и функцию выходов А^ : Б х X ^ У. Автомат Т = (Т, X, У, Лт, ¿1) называется подавтоматом автомата S, если Т С Б, ¿1 = и Лт С . Через БиЬ(5) мы обозначаем множество всех детерминированных подавтоматов автомата 5.
Обозначим через X * множество всех последовательностей конечной длины в алфавите X, включая пустую последовательность е (длины 0, по определению). Под действием любой входной последовательности а = ж1... € X* в состоянии 8 в автомате 5 реализуется последовательность переходов
8 = 81 - (ж1/у1) ^ 82-----> - (жй/у£) ^
где для всех г = 1,...,к, ж, 8^+1, у*) € или = (8г,жг) и у» = А^ ^ж») в
детерминированном автомате. Говорят, что последовательность а переводит автомат из состояния s в состояние sk+i. При этом состояние s называется начальным состоянием перехода (под действием последовательности а), а состояние s^+i -конечным. Последовательность yi... yk £ Y* называется реакцией автомата S на входную последовательность а = xi...ж к в состоянии s, множество всех возможных выходных реакций на входную последовательность а в состоянии s обозначается outs(s, а). Если S -детерминированный автомат (S, X, Y, ¿s, As, si), то для простоты вместо outs(s, а) будем писать As (s, а).
Кроме того, через Xm мы обозначаем множество всех последовательностей из X* длины m, и для любого подмножества U С X* через Pre/(U) обозначается множество всех начальных отрезков последовательностей из U.
Как обычно, автомат называется связным, если для каждого состояния s £ S существует последовательность, переводящая автомат из начального состояния в состояние s. Множество входных последовательностей, переводящих связный автомат из начального состояния в каждое из состояний, называется множеством достижимости Q автома
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.