Тестирование программ с использованием х-машин



Дата12.06.2016
өлшемі97 Kb.
#130995
Тестирование программ с использованием Х-машин.
Богданов К. Е., Холкомб М.

Данная работа была финансирована Daimler-Chrysler AG.


Аннотация: В данной статье рассматривается метод тестирования программ на основании теории X-машин. В отличие от многих других методов тестирования, данный метод позволяет доказать, что реализация программы точно соответствует ее спецификации, при выполнении некоторых условий. Обеспечение выполнения этих условий относительно нетрудно осуществить на практике; нужно только осуществлять проэктирование программы с учетом последующего применение метода. В силу этого, описываемый метод может быть полезен как при тестировании обычных программ, так и тех, от успешного функционирования которых может зависеть жизнь человека, например, программ, обеспечивающих безопастность самолетов.

1Введение


В последнее время интегрированные среды разработки программ а также системы ускоренной разработки значительно сократили время затрачиваемое программистами на написание программ, тогда как тестирование по-прежнему занимает значительное время. Логическое доказательство правильной работы не может заменить тестирование посколько оно работает с моделью программы, в то время как тестирование имеет возможность получать результаты от реальной системы в реальной операционной среде.
X-машины похожи на конечные автоматы, но содержат память и могут производить более сложные операции, чем просто ввод/вывод одного символа. В силу этого, им не присуща проблема конечных автоматов, где сколь-нибудь содержательная спецификация содержит слишком большое количество состояний для какого-бы то ни было анализа. Кроме этого, Х-машины допускают постепенное расширение системы. В начале спецификация может содержать всего несколько состояний, и в процессе развития в нее вносятся новые состояния и переходы. Если на такое развитие наложить некоторые незначительные ограничения, это позволяет существенно сократить объем тестирования. Описываемый метод [3, 4] основан на методе тестирования конечных автоматов [2] и расширяет область применения последнего в сфере Х-машин.

2Пример спецификации с использованием X-машинам


Рассмотрим простой магнитофон, выполняющий стандартные операции “воспроизведение”, “перемотка”, “стоп “и “запись”, а также умеющий перевернуть кассету при нажатии кнопки воспр при воспроизведении. Х-машина, управляющая этим магнитофоном, приведена ниже.


ВОСПРОИЗВЕДЕНИЕ



ПЕРЕМОТКА

воспр

сторона





воспр

кнопка­_стоп

вперед_назад

стоп


запись

ЗАПИСЬ

СТОП

стоп

Рис. 1 Простой магнитофон

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

Набор входных символов таким образом получается

={воспр, запись, стоп, вперед, назад, пленка_кончилась}.

Входная последовательность, состоящая из приведенных символов, вызывает переходы, которые изменяют память и производят выходные символы. Эти символы, которые представляют из себя команды лентопротяжному механизму приведены ниже:

={стоп, движение, воспр, зап, }{вперед, назад}

где означает “без изменений”.

Память представляет из себя тип пленки, счетчик и направление движения пленки,

M={Fe, Cr, Metal}{вперед, назад}

Функции записываются в форме (,m)=(m',), где -входной символ, -выходной и m, m’ – память до и после выполнения функции. С учетом вышесказанного, функцию стоп можно записать в виде, где переменные выделены, входные и выходные символы подчеркнуты,



стоп(,m)

=

(m,(стоп, вперед))

при условии, что {стоп, пленка_кончилась}. Функция стоп определена только для указанных значений переменных. Аналогично, получаем

кнопка­_стоп(стоп,m)

=

(m, (стоп, вперед))

сторона(воспр, (пленка, счетчик, вперед))

=

((пленка, счетчик, назад), (воспр, назад))

сторона(воспр, (пленка, счетчик, назад))

=

((пленка, счетчик, вперед), (воспр, вперед))

Функцию запись можно определить так, чтобы магнитофон не записывал на Metal-пленку,

запись(запись, (пленка, счетчик, напр))

=

((пленка, счетчик, напр), (запись, напр))

при условии, что пленка{Fe, Cr}.

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


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

3.1ВВедение


Описываемый метод основан на теории тестирования для конечных автоматов [2] и дополняет ее. Основные условия, на которых основан метод, это ограниченное количество состояний в реализации спецификации и правильная реализация функций.

В соответствии с этим методом, мы пытаемся посетить каждое состояние и попытаться вызвать все возможные переходы. Если переход вызвать удалось, то необходимо определить, является ли итоговое состояние ожидаемым. Например, при тестировании перехода воспр из состояния ПЕРЕМОТКА в ВОСПРОИЗВЕДЕНИЕ, необходимо



  • Перейти в состояние ПЕРЕМОТКА из исходного состояния, СТОП, используя переход вперед_назад. Для этого мы нажимаем кнопку вперед и ожидаем, что на выходе будет (движение, вперед).

  • Попытаться вызвать переход воспр, путем нажатия воспр. При этом на выходе должен появиться символ (воспр, вперед). Если появилось что-либо иное, это означает, что данного перехода из состояния ПЕРЕМОТКА нет.

  • Определить состояния после перехода. В данном случае мы можем нажать воспр, чтобы вызвать переход сторона так как он существует только из состояния ВОСПРОИЗВЕДЕНИЕ. На выходе должно при этом должно измениться (воспр, вперед) на (воспр, назад).

  • Перевести автомат в начальное состояние, например, выключением. После этого мы можем, к примеру, перевести его в состояние ПЕРЕМОТКА и убедиться, что перехода запись из него нет. Для этого достаточно нажать запись, что должно вызвать (, XX). ХХ означает, что эта часть вывода для нас значения не имеет.



3.2Учет будущего тестирования при написании программ


При тестировании, мы предполагаем, что все фукции были протестированы заранее и поэтому их реализация правильна. Кроме этого, необходимо иметь возможность вызвать любой желаемый переход и определить по состоянию выхода, какой произошел. Например, мы не всегда можем вызвать запись т.к. этот переход зависит от состояния пленка. Для того, чтобы иметь возможноть применить описываемый метод, мы добавляем дополнительный входной символ зап так, что он может всегда вызватъ переход запись. После тестирования, мы можем либо “забыть”, что какие-либо символы были добавлены, либо убрать их из программы (к примеру, используя #ifdef). Переопределенный запись выглядет следующим образом:

запись(­, (пленка, счетчик, напр))

=

((пленка, счетчик, напр), (запись, напр))

при условии, что =запись  пленка{Fe, Cr}  =зап.
Разные функции могут быть вызваны одним и тем же входным символом, например стоп и кнопка_стоп вызваны нажатием стоп. И та и другая функция делает одно и то же, в силу этого мы ме можем определить, какая из них произошла. Поэтому необходимо добавить новый выходной символ который мы назовем к_стоп, означающий, что произошел переход с функцией кнопка_стоп на нем.
Для того, чтобы соблюсти эти условия, их нужно принимать во внимание при разработке програмы, а не тогда, когда она уже написана и менять что-либо уже поздно. Тестирование в течение всей жизни программы, от спецификации до готового кода, необходимо для создания качественного программного обеспечения.

3.3Детали метода


Описываемый метод тестирования основан на трех множествах,

  • Множество функций X-машины спецификации, . Это множество содержит функции, изпользуемые на каком-либо переходе. В нашем случае

={стоп, вперед_назад, воспр, запись, кнопка_стоп, сторона}

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

C={ 1, вперед_назад, воспр, запись },

где 1, пустая последовательность, означает, что мы остаемся в состоянии СТОП.



  • Разделяющее множество, W. После того, как мы пытаемся вызвать все возможные функции из всех состояний и какой-либо переход происходит, необходимо определить, в каком состоянии мы оказались. Для этого служит множество последовательностей W. Оно составлено так, чтобы для какой бы то ни быко пары состояний, в нем найдется последовательность функций, которая будет существовать из одного, но не из другого состояния. В нашем случае,

W={ воспр, стоп}

так как, к примеру, СТОП и ВОСПРОИЗВЕДЕНИЕ разделяются функцией воспр, которая существует из СТОП, но не из ВОСПРОИЗВЕДЕНИЕ (где кнопка воспр вызовет функцию сторона, но ее мы отличить от воспр сможем легко).

И
спользуя вышеприведенные методы, мы получаем для множества тестовых последовательностей (МТП), описанного выше,

г
де произведение множеств последовательностей определено как

При этом a::b означает конкатенацию последовательностей a и b.

На практике реализация может содержать больше состояний, чем спецификация; это может объясняеться удобством реализации. Такие состояния должны быть эквивалентны каким-либо другим состояниям, так что общее количество состояний остается без изменений. Значительное отличие в количестве состояний возможно если реализация была написана исходя из иных представлений о решаемой задаче, чем спецификация. В таких случаях тестирование с использованием спецификации особого смысла не имеет. Обычно имеет смысл предполагать, что эта разница равна 0 или 1.

Р
воспр
ассмотрим пример реализации со следующим автоматом:


ВОСПРОИЗВЕДЕНИЕ



ПЕРЕМОТКА

сторона





воспр

кнопка­_стоп

вперед_назад

стоп

ЗАПИСЬ


запись

СТОП



стоп

СТОП2



Рис. 2 Лишние состояния

Приведенная Х-машина имеет дополнительное состояние СТОП2, которое даже не похоже на СТОП и попасть в него можно только через ЗАПИСЬ. Для того, чтобы отловить все подобные ошибки в реализации, нужно пытаться вызвать все пары функций, из каждого состояния. Тогда запись, стоп позволит нам попасть в СТОП2. Если разница в числе состояний 3, нам нужно работать с тройками функций и т.п. Таким образом, множество последовательностей функций, необходимых для тестирования получается





Е
сли количество состояний спецификации n, а реализации – m, то МТП получается

К

ак видно, большие значения m-n могут значительно увеличить объем тестирования.
Вышеприведенные формулы позволяют определить последовательности переходов, которые необходимы для тестирования. Последовательности нажатий кнопок могут быть получены заменой имен функций на имена кнопок; здесь мы используем результаты предположения, что для любой последовательности переходов можно найти соответствующию последовательность нажатий (параграф выше).



Количество последовательностей, необходимых для тестирования, можно подсчитать следующим образом:

В нашем случае, получаем для m=n,


совершенствование спецификации


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

включить_мотор


МОТОР ВКЛЮЧЕН



подвести_головку

МОТОР ВКЛЮЧЕН



включить_усилитель


Рис. 3 Замена функции воспр Х-машиной

4.1Замена функции перехода между состояниями Х-машиной


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

4.2Основная-вспомогательная Х-машина


Этот тип усовершенствований позволяет поместить Х-машину внутрь состояния, как показано на Рис. 4. В этом случае вспомогательная машина активна только в состоянии ПЕРЕМОТКА. Если мы можем предположить, что вначале спецификация и реализация исходного магнитофона (Рис. 1) были созданы, а потом изменения описанные здесь внесены, то ошибки реализации, при которых, например, переход воспр переведет магнитофон из перемотки назад, в состояние ЗАПИСЬ, а из перемотки вперед-в правильное состояние ВОСПРОИЗВЕДЕНИЕ будут невозможны. Эта ситуация изображена на Рис. 5.


ПЕРЕМОТКА ВПЕРЕД



назад

ПЕРЕМОТКА НАЗАД

вперед



Рис. 4 Вспомогательная Х-машина в состоянии ПЕРЕМОТКА

Д
авайте сравним объем тестирования при использовании данного типа усовершенствования и без него. Без использования мы имеем Х-машину, состоящую из 5 состояний и 8 переходов (6 исходных и два новых). Таким образом, количество послевовательностей

в
то время как при раздельном тестировании

с разницей прочти вдвое.


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


ПЕРЕМОТКА



ПЕРЕМОТКА ВПЕРЕД

назад


вперед


ПЕРЕМОТКА НАЗАД


ВОСПРОИЗВЕДЕНИЕ



воспр

сторона


кнопка­_стоп




воспр

вперед_назад

стоп

воспр


запись

ЗАПИСЬ

СТОП

стоп

Рис. 5 Пример ошибки реализации, невозможной при описанном усовершенствовании

5Практическое применене


Несмотря на кажущуюся сложность, данный метод был применен в ряде случаев с успехом. К примеру, студенты создавали спецификации и программировали их на языке C. Затем ошибки были внесены в реализацию, дабы посмотреть, сумеет ли данный метод их отловить. Результаты были впечатляющие: не только ошибки в состояниях-переходах, но и в функциях были найдены. Это показывает, что даже если условия его применимости не выполнены, метод тем не менее может быть полезен.
Метод может также быть использован в контексте систем, где особой надежности не требуется, то и в этом случае он может быть полезен. К примеру, часть программы может быть записана в виде автомата и МТП вычислен. В этом случае «необычные» последовательноти функций могут помочь идентифицировать ошибки в программе. При таком применении данный метод похож на методы тестирования, в которых каждая команда или ветвь if-оператора, выполнены по крайней мере один раз. В отличие от такого типа методов, данный имеет доказательства в основе его и поэтому может быть применен для программ в широком диапазоне требуемых надежностей.

6Заключение


Мы рассмотрели метод тестирования программ, основанный на теории Х-машин и возможности уменьшения размера МТП с изпользованием усовершенствований. Он был также успешно применен на практике.
Данный метод был расширен для тестирования реализаций спецификаций, использующих statecharts [1]. Statecharts [5] содержат много больше элементов, чем Х-машины. К примеру, в них используется иерархия состояний (похожая на «основная-вспомогательная Х-машина» усовершенствование) и параллельная работа нескольких машин. Попытки использовать расширенный метод также были успешны; опыт показал, что разработка программ с использованием усовершенствований позволяет значительно сократить объем тестирования.
В будущем, метод тестирования Х-машин будет применен для тестирования объектно-ориентированных программ. Мы надеемся, что и это увенчается успехом.

7Литература


1. K. Bogdanov, M. Holcombe and H. Singh. “Automated Test Set Generation for Statecharts” - In “FM-Trends: International Workshop on Current Trends in Applied Formal Methods, Oct 98”, to appear in Springer LNCS Series in 1999.

2. T.S. Chow. “Testing software design modeled by finite-state machines”. IEEE Transactions on Software Engineering, SE-4(3):178--187, 1978.

3. M. Holcombe and F. Ipate. “Correct Systems: building a business process solution”.

Springer-Verlag Berlin and Heidelberg GmbH&Co. KG, 1998.

4. F.E. Ipate. “Theory of X-machines and Applications in specification and Testing”. Ph.D. thesis, University of Sheffield, 1995.



5. A.Naamad, D.Harel “The Statemate Semantics of Statecharts” Technical Report, Weizmann Institute of Science,1995, а также http://www.wisdom.weizmann.ac.il/Papers/trs/CS95-31/abstract.html

Достарыңызбен бөлісу:




©www.dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет