Тестирование программ с использованием х-машин
жүктеу/скачать 97 Kb.
|
- Бұл бет үшін навигация:
- 2Пример спецификации с использованием X-машинам
- 3Метод тестирования
- 3.2Учет будущего тестирования при написании программ
- 3.3Детали метода
- 4У совершенствование спецификации
- 4.1Замена функции перехода между состояниями Х-машиной
- 4.2Основная-вспомогательная Х-машина
- 5Практическое применене
| Тестирование программ с использованием Х-машин.
Богданов К. Е., Холкомб М. Данная работа была финансирована Daimler-Chrysler AG. Аннотация: В данной статье рассматривается метод тестирования программ на основании теории X-машин. В отличие от многих других методов тестирования, данный метод позволяет доказать, что реализация программы точно соответствует ее спецификации, при выполнении некоторых условий. Обеспечение выполнения этих условий относительно нетрудно осуществить на практике; нужно только осуществлять проэктирование программы с учетом последующего применение метода. В силу этого, описываемый метод может быть полезен как при тестировании обычных программ, так и тех, от успешного функционирования которых может зависеть жизнь человека, например, программ, обеспечивающих безопастность самолетов. 1ВведениеВ последнее время интегрированные среды разработки программ а также системы ускоренной разработки значительно сократили время затрачиваемое программистами на написание программ, тогда как тестирование по-прежнему занимает значительное время. Логическое доказательство правильной работы не может заменить тестирование посколько оно работает с моделью программы, в то время как тестирование имеет возможность получать результаты от реальной системы в реальной операционной среде. X-машины похожи на конечные автоматы, но содержат память и могут производить более сложные операции, чем просто ввод/вывод одного символа. В силу этого, им не присуща проблема конечных автоматов, где сколь-нибудь содержательная спецификация содержит слишком большое количество состояний для какого-бы то ни было анализа. Кроме этого, Х-машины допускают постепенное расширение системы. В начале спецификация может содержать всего несколько состояний, и в процессе развития в нее вносятся новые состояния и переходы. Если на такое развитие наложить некоторые незначительные ограничения, это позволяет существенно сократить объем тестирования. Описываемый метод [3, 4] основан на методе тестирования конечных автоматов [2] и расширяет область применения последнего в сфере Х-машин. 2Пример спецификации с использованием X-машинамРассмотрим простой магнитофон, выполняющий стандартные операции “воспроизведение”, “перемотка”, “стоп “и “запись”, а также умеющий перевернуть кассету при нажатии кнопки воспр при воспроизведении. Х-машина, управляющая этим магнитофоном, приведена ниже.
ПЕРЕМОТКА воспр 
сторона  
воспр 
кнопка_стоп 
вперед_назад стоп запись ЗАПИСЬ
СТОП
Функции на переходах между состояниями дают команды лентопротяжному механизму. Эта машина получает как нажатия кнопок пользователя воспр, запись, стоп, вперед, назад, так и информацию пленка_кончилась от лентопротяжного механизма. Набор входных символов таким образом получается ={воспр, запись, стоп, вперед, назад, пленка_кончилась}. Входная последовательность, состоящая из приведенных символов, вызывает переходы, которые изменяют память и производят выходные символы. Эти символы, которые представляют из себя команды лентопротяжному механизму приведены ниже: ={стоп, движение, воспр, зап, }{вперед, назад} где означает “без изменений”. Память представляет из себя тип пленки, счетчик и направление движения пленки, M={Fe, Cr, Metal}{вперед, назад} Функции записываются в форме (,m)=(m',), где -входной символ, -выходной и m, m’ – память до и после выполнения функции. С учетом вышесказанного, функцию стоп можно записать в виде, где переменные выделены, входные и выходные символы подчеркнуты,
при условии, что {стоп, пленка_кончилась}. Функция стоп определена только для указанных значений переменных. Аналогично, получаем
Функцию запись можно определить так, чтобы магнитофон не записывал на Metal-пленку,
при условии, что пленка{Fe, Cr}. В силу того, что не для каждого входного символа определен какой-либо переход из всех состояний, мы доопределяем рассматриваемую Х-машину переходами, которые не меняют состояние и памятью выдают . 3Метод тестирования3.1ВВедениеОписываемый метод основан на теории тестирования для конечных автоматов [2] и дополняет ее. Основные условия, на которых основан метод, это ограниченное количество состояний в реализации спецификации и правильная реализация функций. В соответствии с этим методом, мы пытаемся посетить каждое состояние и попытаться вызвать все возможные переходы. Если переход вызвать удалось, то необходимо определить, является ли итоговое состояние ожидаемым. Например, при тестировании перехода воспр из состояния ПЕРЕМОТКА в ВОСПРОИЗВЕДЕНИЕ, необходимо
3.2Учет будущего тестирования при написании программПри тестировании, мы предполагаем, что все фукции были протестированы заранее и поэтому их реализация правильна. Кроме этого, необходимо иметь возможность вызвать любой желаемый переход и определить по состоянию выхода, какой произошел. Например, мы не всегда можем вызвать запись т.к. этот переход зависит от состояния пленка. Для того, чтобы иметь возможноть применить описываемый метод, мы добавляем дополнительный входной символ зап так, что он может всегда вызватъ переход запись. После тестирования, мы можем либо “забыть”, что какие-либо символы были добавлены, либо убрать их из программы (к примеру, используя #ifdef). Переопределенный запись выглядет следующим образом:
при условии, что =запись пленка{Fe, Cr} =зап. Разные функции могут быть вызваны одним и тем же входным символом, например стоп и кнопка_стоп вызваны нажатием стоп. И та и другая функция делает одно и то же, в силу этого мы ме можем определить, какая из них произошла. Поэтому необходимо добавить новый выходной символ который мы назовем к_стоп, означающий, что произошел переход с функцией кнопка_стоп на нем. Для того, чтобы соблюсти эти условия, их нужно принимать во внимание при разработке програмы, а не тогда, когда она уже написана и менять что-либо уже поздно. Тестирование в течение всей жизни программы, от спецификации до готового кода, необходимо для создания качественного программного обеспечения. 3.3Детали методаОписываемый метод тестирования основан на трех множествах,
={стоп, вперед_назад, воспр, запись, кнопка_стоп, сторона}
C={ 1, вперед_назад, воспр, запись }, где 1, пустая последовательность, означает, что мы остаемся в состоянии СТОП.
W={ воспр, стоп} так как, к примеру, СТОП и ВОСПРОИЗВЕДЕНИЕ разделяются функцией воспр, которая существует из СТОП, но не из ВОСПРОИЗВЕДЕНИЕ (где кнопка воспр вызовет функцию сторона, но ее мы отличить от воспр сможем легко). И г При этом a::b означает конкатенацию последовательностей a и b. На практике реализация может содержать больше состояний, чем спецификация; это может объясняеться удобством реализации. Такие состояния должны быть эквивалентны каким-либо другим состояниям, так что общее количество состояний остается без изменений. Значительное отличие в количестве состояний возможно если реализация была написана исходя из иных представлений о решаемой задаче, чем спецификация. В таких случаях тестирование с использованием спецификации особого смысла не имеет. Обычно имеет смысл предполагать, что эта разница равна 0 или 1. Р
ПЕРЕМОТКА
сторона
воспр 
кнопка_стоп
вперед_назад стоп ЗАПИСЬ
запись СТОП
стоп СТОП2
Рис. 2 Лишние состояния Приведенная Х-машина имеет дополнительное состояние СТОП2, которое даже не похоже на СТОП и попасть в него можно только через ЗАПИСЬ. Для того, чтобы отловить все подобные ошибки в реализации, нужно пытаться вызвать все пары функций, из каждого состояния. Тогда запись, стоп позволит нам попасть в СТОП2. Если разница в числе состояний 3, нам нужно работать с тройками функций и т.п. Таким образом, множество последовательностей функций, необходимых для тестирования получается  Е К Количество последовательностей, необходимых для тестирования, можно подсчитать следующим образом: В нашем случае, получаем для m=n,
4У
|
