X-Machine Тестирование - X-Machine Testing

В (Stream) Методология тестирования X-Machine это полный функциональное тестирование подход к программного обеспечения- и аппаратное тестирование^[1] который использует масштабируемость Stream X-Machine модель вычисления.^[2] Используя эту методологию, можно определить конечный набор тестов, который исчерпывающе определяет, соответствует ли реализация тестируемой системы ее спецификации. Эта цель достигается с помощью подхода «разделяй и властвуй», при котором дизайн разбивается на части.^[3] в коллекцию Stream X-Machines, которые реализованы в виде отдельных модулей, а затем протестированы снизу вверх. На каждом этапе интеграции метод тестирования гарантирует правильную интеграцию тестируемых компонентов.^[4]

Методология превосходит формальные неразрешимость ограничения, требуя, чтобы определенные дизайн для теста принципы соблюдаются во время спецификации и реализации. В результате масштабируемость означает, что практическое программное обеспечение^[5] и оборудование^[6] системы, состоящие из сотен тысяч состояний и миллионов переходов, были успешно протестированы.

Мотивация

Много тестирование программного обеспечения просто обнадеживает, пытаясь испытать систему программного обеспечения различными способами, чтобы увидеть, могут ли быть обнаружены какие-либо ошибки. Тестирование действительно может выявить некоторые ошибки, но никогда не может гарантировать, что система работает правильно, когда тестирование закончено. Функциональное тестирование методы стремятся улучшить эту ситуацию, развивая формальная спецификация описание предполагаемого поведения системы, против которого реализация впоследствии проверяется (своего рода проверка на соответствие ). Спецификация может быть проверена на соответствие требованиям пользователя и позже. доказано быть последовательный и полный математическими рассуждениями (исключая любые логические недостатки конструкции). Полный функциональное тестирование методы систематически используют спецификацию, генерируя наборы тестов, которые проверяют реализованную программную систему исчерпывающе, чтобы определить, соответствует ли он спецификации. Особенно:

Полное положительное тестирование: подтверждает, что все желаемое поведение присутствует в системе;
Полное отрицательное тестирование: подтверждает, что в системе нет нежелательного поведения.

Достичь такого уровня тестирования может быть сложно, поскольку программные системы чрезвычайно сложны, с сотнями тысяч состояний и миллионами переходов. Что необходимо, так это способ разбить спецификацию и задачу тестирования на части, которые можно решить отдельно.

Масштабируемые абстрактные спецификации

Майк Холкомб впервые предложил использовать Сэмюэл Эйленберг теоретический X-машина модель как основа для спецификации программного обеспечения в конце 1980-х.^[7]Это потому, что модель четко разделяет поток управления системы из обработка осуществляется системой. На данном уровне абстракции систему можно рассматривать как простую конечный автомат состоящий из нескольких состояний и переходов. Более сложная обработка делегируется функции обработки на переходах, которые изменяют базовый фундаментальный тип данных Икс. Позже каждая функция обработки может быть раскрыта отдельно и охарактеризована другим X-машина, моделируя поведение этой системы.

Это поддерживает подход «разделяй и властвуй», при котором сначала указывается общая архитектура системы, затем указываются все основные системные операции, затем подпрограммы и т. Д. На каждом этапе уровень сложности управляемый благодаря независимости каждого уровня. В частности, программистам легко проверить простой конечные автоматы против требований пользователей.

Инкрементально тестируемые спецификации

Гилберт Лэйкок первым предложил особый вид X-машина, то Stream X-Machine, в качестве основы для метода тестирования.^[2] Преимуществом этого варианта было то, как можно было контролировать тестирование. В Stream X-Machine, основной тип данных имеет определенную форму: Икс = Из* × Mem × В*, куда В* - входной поток, Из* - выходной поток, а Mem это внутренняя память. Переходы Stream X-Machine помечены функциями обработки вида φ: Mem × В → Из × Mem, то есть они потребляют один вход из входного потока, возможно, изменяют память и производят один выход в выходном потоке (см. связанная статья Больше подробностей).

Преимущества тестирования заключаются в том, что программные системы, разработанные таким образом, наблюдаемый на каждом шагу. Для каждого ввода машина делает один шаг, создавая вывод, так что пары ввода / вывода могут быть точно согласованы. Это контрастирует с другими подходами, в которых система работает до завершения (делая несколько шагов) до того, как будет сделано какое-либо наблюдение. Кроме того, слоистые Stream X-Machines предлагают удобную абстракцию. На каждом уровне тестировщик может забывать о деталях функций обработки и рассматривайте (подсистему) просто как простую конечный автомат. Существуют мощные методы тестирования систем, которые соответствуют спецификациям конечного состояния, такие как W-метод Чоу.^[8]

Спецификация Метод

Следуя методологии (Stream) X-Machine, первым этапом является определение различных типов данных, которые необходимо обработать. Например, текстовый редактор будет использовать базовые типы Характер (ввод с клавиатуры), Позиция (положение курсора мыши) и Команда (мышь или команда меню). Могут быть и другие сконструированные типы, например Текст ::= Характер* (последовательность символов), Выбор ::= Позиция × Позиция (начало и конец выделения) и Документ ::= Текст × Выбор × Булево (текст, возможный выбор и флаг, сигнализирующий, что документ был изменен).

Спецификация высокого уровня

Спецификация верхнего уровня - это Stream X-Machine описание основного взаимодействия пользователя с системой. Например, текстовый процессор будет существовать в нескольких состояниях, в которых нажатия клавиш и команды будут иметь разные эффекты. Предположим, что этот текстовый процессор существует в состояниях {Письмо, Выбор, Подача, Редактирование}. Мы ожидаем, что текстовый процессор запустится в начальной Письмо состояние, но перейти к Выбор состояние, если мышь тащил, или клавиша Shift удерживается. Как только выбор будет сделан, он должен вернуться к Письмо государственный. Аналогично, если выбран параметр меню, он должен войти в Редактирование или же Подача государственный. В этих состояниях определенные нажатия клавиш могут иметь разное значение. Текстовый процессор в конечном итоге возвращается к Письмо состояние, когда любая команда меню завершена. Этот конечный автомат разработан и неформально помечен различными действиями, которые вызывают его изменение состояния.

Типы ввода, памяти и вывода для машины верхнего уровня теперь формализованы. Предположим, что типом памяти простого текстового процессора является тип Документ определено выше. При этом документ рассматривается как текстовая строка с двумя позициями, обозначающими возможный выбор, и флагом, указывающим на изменение с момента последнего спасти-команда. Более сложный текстовый процессор может поддерживать редактирование с возможностью отмены с последовательностью состояний документа: Документ ::= (Текст × Выбор) *, которые сворачиваются в один документ каждый раз, когда спасти-команда выполняется.

Предположим, что тип ввода для машины: В ::= Команда × Характер × Позиция. Это означает, что каждое взаимодействие может быть простой вставкой символа, командой меню или размещением курсора. Любое данное взаимодействие состоит из трех элементов, но некоторые места могут быть пустыми. Например, (Вставлять, 'a', ε) будет представлять ввод символа 'a'; пока (Позиция, ε, 32) будет означать размещение курсора между символами 32 и 33; и (Выбирать, ε, 32) будет означать выбор текста между текущей позицией курсора и местом между символами 32 и 33.

Тип вывода для машины разработан таким образом, чтобы можно было определить по выводам который функция обработки была выполнена в ответ на заданный ввод. Это относится к собственности различимость выхода, описано ниже.

Спецификация низкого уровня

Если система сложная, то она, скорее всего, будет разбита на несколько Stream X-Machines. Наиболее распространенный вид уточнения - взять каждую из основных функций обработки (которыми были ярлыки на машине высокого уровня) и рассматривать их как отдельные Stream X-Machines.^[3] В этом случае типы ввода, памяти и вывода для низкоуровневых машин будут отличаться от тех, которые определены для высокоуровневой машины. Либо это рассматривается как расширение наборов данных, используемых на высоком уровне, либо есть перевод из более абстрактных наборов данных на высоком уровне в более подробные наборы данных на более низком уровне. Например, команда Выбирать на высоком уровне можно разложить на три события: MouseDown, MouseMove, MouseUp на нижнем уровне.

Ипате и Холкомб упоминают несколько видов уточнения, включая функциональная доработка, в котором поведение функций обработки подробно описано, и уточнение состояния, в котором простое пространство состояний разделено на более сложное пространство состояний.^[1] Ипате доказывает, что эти два вида усовершенствования в конечном итоге эквивалентны^[9]

В остальном системы определяются до уровня, на котором разработчик готов доверять примитивным операциям, поддерживаемым средой реализации. Также возможно исчерпывающее тестирование небольших устройств другими методами тестирования.

Условия проектирования для испытаний

Методология (Stream) X-Machine требует от дизайнера соблюдения определенных дизайн для теста условия. Их, как правило, не так уж сложно удовлетворить. Для каждого Stream X-Machine в спецификации мы должны получить:

Минимальная спецификация: Спецификация должна быть минимальный конечный автомат. Это означает, что конечный автомат не должен содержать избыточных состояний, то есть состояний, в которых наблюдаемое поведение перехода идентично поведению в каком-либо другом состоянии.
Детерминированная спецификация: Для каждого состояния машины не более одной из функций обработки φ должна быть включено для текущей памяти и следующего входного значения. Это гарантирует предсказуемость требуемого поведения для тестирования.
Полнота теста: Каждая функция обработки φ должна выполняться по крайней мере для одного входа по отношению ко всем состояниям памяти. Это гарантирует отсутствие взаимоблокировок, когда машина блокируется текущим состоянием памяти. Чтобы гарантировать полноту теста, область функции φ может быть расширен специальными тестовые входы которые используются только во время тестирования.
Различимость выхода: Должна быть возможность отличить, какая функция обработки была вызвана, только по ее выходному значению для всех пар память-ввод. Это гарантирует, что конечный автомат может быть отделен от функций обработки. Для обеспечения различимости вывода codomain функции φ можно продолжить с помощью специальных тестовые выходы которые актуальны только во время тестирования.

Минимальная машина - это машина с наименьшим количеством состояний и переходов для некоторого заданного поведения. Сохранение минимальной спецификации просто гарантирует, что наборы тестов будут как можно меньше. Для предсказуемых систем требуется детерминированная машина. В противном случае реализация могла бы сделать произвольный выбор относительно того, какой переход был сделан. Некоторые недавние работы ослабили это предположение, чтобы позволить тестирование недетерминированных машин.^[10]

Полнота тестирования необходима, чтобы гарантировать, что реализация может быть протестирована в кратчайшие сроки. Например, если в системе есть удаленные или труднодоступные состояния, которые вводятся только после того, как память достигла определенного предельного значения, тогда следует добавить специальные тестовые входы, чтобы позволить обходить память, заставляя конечный автомат переместиться в дальний угол. государственный. Это позволяет быстро охватить все (абстрактные) состояния во время тестирования. Различимость выходных данных - ключевое свойство, поддерживающее масштабируемый метод тестирования. Это позволяет тестировщику рассматривать функции обработки φ как простые метки, подробное поведение которых можно безопасно игнорировать при тестировании конечного автомата следующего уровня интеграции. Уникальные выходы - это значения свидетелей, которые гарантируют, что конкретная функция была вызвана.

Метод тестирования

Метод тестирования (Stream) X-Machine предполагает, что и дизайн, и реализация могут рассматриваться как (набор) Stream X-Machines. Для каждой пары соответствующих машин (Спецификация, Бес), цель тестирования - определить, работает ли поведение Бес, машина реализации, точно соответствует поведению Спецификация, машина спецификации. Обратите внимание, что Бес не обязательно должна быть минимальной машиной - у нее может быть больше состояний и переходов, чем Спецификация и при этом вести себя точно так же.

Чтобы проверить все варианты поведения, должна быть возможность привести машину во все ее состояния, а затем попытаться выполнить все возможные переходы (те, которые должны быть успешными, и те, которые должны быть заблокированы) для достижения полного положительный и отрицательный тестирование (см. выше). Для успешных переходов необходимо также проверить состояние назначения. Обратите внимание, что если Спецификация и Бес имеют одинаковое количество состояний, выше описывается наименьший набор тестов, который достигает цели. Если Бес имеет больше состояний и переходов, чем Спецификация, необходимы более длинные тестовые последовательности, чтобы гарантировать, что избыточный государства в Бес также вести себя так, как ожидалось.

Тестирование всех состояний

В основе стратегии генерации тестов лежит W-метод Цуна С. Чоу для тестирования конечных автоматов,^[8] выбран потому, что он поддерживает тестирование избыточных реализаций. Метод Чоу предполагает простое конечные автоматы с наблюдаемыми входами и выходами, но без непосредственно наблюдаемых состояний. Для отображения на формализм Чоу функции φ_я на переходах Stream X-Machines рассматриваются просто как метки (входы в терминах Чоу), а отличительные выходы используются напрямую. (Позже отображение реальных входов и памяти (мем, в) выбирается для запуска каждой функции φ в соответствии с ее областью определения).

Для определения конкретных состояний в Бес, Чоу выбирает набор характеристик, Вт, наименьший набор тестовых последовательностей, который однозначно характеризует каждое состояние в Спецификация. То есть при запуске в заданном состоянии выполнение последовательностей в W должен дать хотя бы одно наблюдаемое отличие по сравнению с запуском в любом другом состоянии.

Чтобы достичь каждого состояния, ожидаемого в Спецификация, тестер строит государственное покрытие, C, наименьший набор тестовых последовательностей, который достигает каждого состояния. Это можно построить путем автоматического исследования вширь. Спецификация. Набор тестов, который проверяет все состояния минимального Бес затем: ${ displaystyle C otimes W}$ , куда ${ displaystyle otimes}$ обозначает составной продукт из двух наборов. Например, если C = {⟨а⟩, ⟨б⟩} и W = {⟨c⟩, ⟨d⟩}, тогда ${ displaystyle C otimes W = { langle ac rangle, langle ad rangle, langle bc rangle, langle bd rangle }}$ .

Тестирование всех переходов

Вышеупомянутый тестовый набор определяет, Бес имеет те же состояния, что и Спецификация. Чтобы определить, является ли минимальный Бес также имеет такое же поведение перехода, что и Спецификация, тестер строит переходная крышка, К. Это наименьший набор тестовых последовательностей, который достигает каждого состояния, а затем пытается один раз выполнить каждый возможный переход из этого состояния. Теперь входной алфавит состоит из (меток) каждой функции φ из Φ. Построим набор тестовых последовательностей длины 1, состоящий из отдельных функций, выбранных из Φ, и назовем его Φ₁. Переходное покрытие определяется как ${ displaystyle K: = C чашка C otimes Phi _ {1}}$ .

Это будет пытаться все возможные переходы из каждого состояния. Для тех, кто добился успеха, мы должны проверить состояния назначения. Итак, самый маленький тест-набор Т₁ что полностью подтверждает поведение минимального Бес дан кем-то: ${ displaystyle T_ {1} :: = C otimes W cup C otimes Phi _ {1} otimes W}$ . Эту формулу можно переформулировать как:

{ Displaystyle T_ {1} :: = C otimes left ( Phi _ {0} cup Phi _ {1} right) otimes W}

,

где Φ₀ - множество, содержащее пустую последовательность {⟨⟩}.

Если Бес имеет больше состояний, чем Спецификация, приведенного выше набора тестов может быть недостаточно, чтобы гарантировать соответствующее поведение реплицированных состояний в Бес. Итак, выбираются наборы более длинных тестовых последовательностей, состоящие из всех пар функций Φ₂, все тройки функций Φ₃ с точностью до некоторого предела Φ_k, когда тестер убедится, что Бес не может содержать цепочки повторяющихся состояний длиннее, чем k-1. Окончательная формула теста определяется следующим образом:

{ displaystyle T _ { mathrm {k}} :: = C otimes left ( Phi _ {0} cup Phi _ {1} ldots cup Phi _ { mathrm {k}} right ) время W}

.

Этот набор тестов полностью проверяет поведение неминимального Бес в которых предполагается, что цепочки дублированных состояний будут не длиннее, чем k-1. Для большинства практических целей тестирование до k= 2 или k= 3 является довольно исчерпывающим, выявляя все связанные с состоянием ошибки в действительно плохих реализациях.