Лекции. Тестирование ПО (all in one) (1186159), страница 19
Текст из файла (страница 19)
В этом случае получаются так называемые ω-автоматы.В теоретической информатике используются исполнимые модели программ в виденекоторых машин — машины Тьюринга, машины Поста или другие машины,формализующие понятие универсальной или ограниченной вычислимости. Они удобны длядоказательства результатов об алгоритмической сложности решения или о неразрешимостикаких-либо задач, но в качестве способа моделирования сложных программных систем неиспользуются.Логико-алгебраические моделиЛогико-алгебраические модели описывают преимущественно свойства моделируемыхсистем. По виду используемых формализмов их можно (несколько условно) разделить налогические и алгебраические.Логические модели используют различные виды логических исчислений, отличающиесяоперациями, которые можно применять к высказываниям для построения новыхвысказываний, и описывают свойства систем как набор высказываний в определеннойлогике.Алгебраические модели используют алгебраические исчисления, в которых операциивыполняются не над высказываниями, а над термами.
Система описывается в рамках такогоисчисления как множество термов (соответствующих возможным состояниям системы), накоторых специальными аксиомами определяется отношение эквивалентности (какиесостояния считаются одинаковыми). Часто определяются термы нескольких типов, тогдаодин из этих типов соответствует состояниям системы, а остальные — типам другихобъектов, которые можно получать с помощью операций системы.Основные виды используемых при описании ПО алгебраических моделей следующие.•Реляционные алгебры (см.
в курсах по базам данных).•Абстрактные типы данных (пример приведен в Лекции 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}
