Лекция 4. Основные техники построения тестов (1186163), страница 2
Текст из файла (страница 2)
Соответственно, принимающий автомат часть своих стимулов получает извне, ачасть — из каналов, для которых он является приемником. Каждый канал устроен какочередь — посылающий автомат вставляет свою реакцию как последнее сообщение,принимающий автомат выбирает всегда первое находящееся в канале сообщение.Иногда используются взаимодействующие расширенные автоматы, получаемые израсширенные в точности так же, как взаимодействующие получаются из обычных.Иерархические автоматы — могут иметь структурированные состояния, одни из ихсостояний являются под-состояниями других.
Это полезно для возможности определитьпереход по одному и тому же стимулу из целого множества состояний в одно.Иерархический автомат может быть преобразован в конечный при помощи процедурыуплощения — состояниями конечного автомата объявляются цепочки состоянийиерархического, в которых каждое следующее состояние является под-состояниемпредыдущего, а у последнего состояния нет под-состояний.Иерархические расширенные автоматы с дополнительной возможностью определенияпараллельных под-состояний — это диаграммы переходов (Statecharts) в рамках UML.Помимо переменных, в автомат можно добавить таймеры — это специальныепеременные, которые автономно изменяют свое значение в соответствии с ходом времени.Расширенные автоматы с таймерами называются временными (Timed Automata).Поведение автомата можно определить не только для конечных, но и для бесконечныхвходных последовательностей.
В этом случае получаются так называемые ω-автоматы.В теоретической информатике используются исполнимые модели программ в виденекоторых машин — машины Тьюринга, машины Поста или другие машины,формализующие понятие универсальной или ограниченной вычислимости. Они удобны длядоказательства результатов об алгоритмической сложности решения или о неразрешимостикаких-либо задач, но в качестве способа моделирования сложных программных систем неиспользуются.Логико-алгебраические моделиЛогико-алгебраические модели описывают преимущественно свойства моделируемыхсистем.
По виду используемых формализмов их можно (несколько условно) разделить налогические и алгебраические.Логические модели используют различные виды логических исчислений, отличающиесяоперациями, которые можно применять к высказываниям для построения новыхвысказываний, и описывают свойства систем как набор высказываний в определеннойлогике.Алгебраические модели используют алгебраические исчисления, в которых операциивыполняются не над высказываниями, а над термами. Система описывается в рамках такогоисчисления как множество термов (соответствующих возможным состояниям системы), накоторых специальными аксиомами определяется отношение эквивалентности (какиесостояния считаются одинаковыми).
Часто определяются термы нескольких типов, тогдаодин из этих типов соответствует состояниям системы, а остальные — типам другихобъектов, которые можно получать с помощью операций системы.Основные виды используемых при описании ПО алгебраических моделей следующие.•Реляционные алгебры (см.
в курсах по базам данных).•Абстрактные типы данных (пример приведен в Лекции 3 — там описан абстрактныйтип индексированного списка)•Разнообразные алгебры процессов.•Машины с абстрактным состоянием (Abstract State Machines, ASM, см. ниже).Основные виды логических моделей такие.•Исчисления высказываний и предикатов, первого и высших порядков.•λ-исчисление первого и высших порядков.•Временные логики, использующие операторы «раньше», «позже», «когда-нибудь вбудущем» и пр.•µ-исчисление, являющееся расширением временных логик.•Логики явного времени, где вместо соотношений между порядком событий типа«позже»-«раньше»-«между» явно указывается время или временные интервалы,когда они имели место.Промежуточные моделиПромежуточные модели либо определяются как исполнимые, но могут быть легкоинтерпретированы как логико-алгебраические или наоборот, либо сочетают в себе чертыобоих основных классов моделей.Например, алгебры процессов представляют собой алгебраические исчисления, в которыхпроцессы представлены термами, строящимися по определенным правилам.
В то же времяестественная интерпретация алгебр процессов дается системами размеченных переходов, ичасто между системами переходов и представляемыми ими процессами не делаетсяразличий.Пример второго рода — машины с абстрактным состоянием (ASM). В качествесостояний такой машины рассматриваются различные универсальные алгебры с одной и тойже сигнатурой (называемой сигнатурой машины), включающей константы true, false, undef.Переходы составляются из конечного набора элементарных действий нескольких типов.•Смена значения операции из сигнатуры символа на некотором наборе аргументовf(a1, …, an) := <выражение, составленное из операций сигнатуры>•Условное выполнение определенных действийif(<условие>) <действия>•Параллельное выполнение некоторых действий для всех объектов, обладающихнекоторым свойствомforall x : P(x) do <действия, зависящие от x>Приведем простой пример описания стека с помощью ASM.•Сигнатура.o size : int — размер стека;o elements(int) : object — содержимое стека;o top : object — элемент в вершине стека;o input : {pop, push}×object — выполняемая операция.•Начальное состояние.size = 0; ∀i elements(i) = undef; top = undef;•Описание.if(π1(input) = push){ size := size + 1; elements(size+1) := π2(input); top := π2(input); }if(π1(input) = pop){ size := size - 1; elements(size) := undef; top := elements(size-1); }Еще один вид промежуточных моделей, использующий элементы исполнимых моделей илогических — программные контракты (software contracts).Программный контракт описывает некоторый компонент с определенным интерфейсом.Интерфейс представляет собой конечное множество операций.
Каждая операция имеет имя инабор параметров определенных типов.Программный контракт компонента состоит из следующих элементов.•Описание структуры данных внутреннего состояния компонента.Это описание включает определение элементов данных и их типов, а такжеинварианты.Каждый инвариант — это предикат, зависящий от описанных элементов данных.Если такой предикат выполнен, данные состояния компонента корректны. Иначе —нарушены их ограничения целостности и пользоваться таким компонентом нельзя.•Описание структур данных всех используемых типов.Для каждого типа также определяются элементы данных, их типы и инвариантыданного типа.Описание контракта для каждой операции.o Предусловие.Предусловие определяет ситуации, в которых операцию можно вызывать.Оно представляет собой предикат, зависящий от внутреннего состояниякомпонента и аргументов операции.o Постусловие.Постусловие описывает требования к корректным результатам работыоперации. Оно представляет собой предикат, зависящий от внутреннегосостояния в момент вызова операции, аргументов, с которыми она былавызвана, возвращаемого ею результата и состояния компонента сразу послевызова.В рамках программного контракта соединяется описание состояний компонента,характерное для исполнимых моделей, с декларативным описанием поведения операций,которые, вообще говоря, нельзя выполнить на какой-то машине.•Основные методы построения тестовОсновные методы построения тестов можно разделить на следующие группы.•Вероятностные методы.Эти методы основаны на вероятностной генерации тестовых воздействий всоответствии с определенными распределениями.Вероятностные методы хорошо автоматизируются и являются наименеетрудоемкими.
Однако обеспечиваемая ими полнота тестирования варьируетсяслучайным и плохо предсказуемым заранее образом — в одних случаях оказываетсядостаточно хорошей, в других очень плохой. С помощью вероятностных методовхорошо находятся случайные ошибки и опечатки, все другие виды ошибок — неочень хорошо. Используются они, когда о тестируемой системе почти ничегонеизвестно, а получение дополнительной информации и построение тестов другимиметодами не может быть осуществлено в рамках проекта.•Методы, нацеленные на полное покрытие.В рамках этих методов тесты строятся целенаправленно таким образом, чтобыобеспечить покрытие выделенных критерием покрытия классов ситуаций.Эти методы автоматизируются плохо, в основном используются при ручнойразработке тестов и достаточно трудоемки.
Обеспечиваемая ими полнота приадекватном выборе критерия полноты тестирования очень высока. Позволяютнаходить любые виды ошибок. Используются при наличии практически полнойинформации о системе, достаточных ресурсов и необходимости провестисистематическое и аккуратное тестирование.•Комбинаторные методы.Эти методы основаны на разбиении тестовых воздействий на некоторые элементы исоставлении различных комбинаций из этих элементов по определенным правилам сцелью получить достаточно систематический перебор тестовых воздействий.Они хорошо автоматизируются, более трудоемки, чем вероятностные, нозначительно проще, чем нацеленные на покрытие методы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
