Тестирование софта - статьи

       

Краткое описание обходчиков UniTESK


В настоящий момент CTesK [], один из инструментов, поддерживающих разработку тестов по технологии UniTESK, включает два обходчика, реализующих различные алгоритмы построения обхода графов и имеющих различные ограничения на вид графов, с которыми они могут работать.

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

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

Задача построения алгоритмов, строящих обход недетерминированных графов, заданных неизбыточным образом, была успешно решена []. Но предложенный в работе [] алгоритм является полновесным средством работы с существенно недетерминированными графами. В то же время, в большинстве случаев можно обойтись более простым решением, обладающим более узкой областью применимости, которое реализовано во втором обходчике CTesK, ndfsm [].

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

Содержание раздела