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

       

Алгоритм поиска


В данном разделе описан алгоритм поиска различных порядков вызовов методов. Информацию о тестируемой системе алгоритм получает через управляющего (Controller) . В начале каждого удаленного вызова метода выполнение этого вызова блокируется, и управление передается управляющему, который получает информацию о вызываемом методе в виде возможного перехода (Transition) . Будем говорить, что система находится в глобальном состоянии, если в тестируемой системе не остается активных потоков, т.е. все потоки ожидают команды управляющего. Алгоритму поиска информация предоставляется через интерфейс управляющего (рис. 11). Для обнаружения достижения глобального состояния алгоритм вызывает метод управляющего waitForGlobalState. В глобальном состоянии управляющий выдает информацию о глобальном состоянии (метод getStateInfo), включающую в себя список возможных переходов (метод getTransitionList) и сигнал о завершении взаимодействий с тестируемой системой (метод isEndState). Алгоритм поиска может выполнить один из переходов, вызвав метод applyTransition. public interface Controller { public static interface StateInfo { public List<Transition> getTransitionList(); public boolean isEndState(); } public void applyTransition(Transition t); public StateInfo getStateInfo(); public void waitForGlobalState(); }

Рис. 11.Интерфейс управляющего

Как уже упоминалось ранее, в предлагаемом методе тестирования тестовая последовательность строится на основе обхода графа автомата. Переходы автомата представляют собой тестовые воздействия на тестируемую систему. Состояния - обобщенные состояния. Для построения тестовой последовательности от графа автомата требуется сильная связность, т.е. из любого состояния существует путь в любое другое.

Алгоритм поиска различных порядков выполняется для некоторого перехода в автомате в некотором обобщенном состоянии. Каждый раз при выполнении алгоритма система находится в некотором состоянии, соответствующем данному обобщенному состоянию. Для перехода в автомате и состояния системы определим понятие дерева перебора.
Вершинами дерева перебора являются глобальные состояния, а дуги в дереве - это возможные переходы из соответствующих глобальных состояний. Пусть заданы обобщенное состояние S, которому принадлежат состояния системы s1,…, sn, и переход автомата a. Каждому состоянию si и переходу a соответствует дерево перебора ti. Будем говорить, что дерево t1 является поддеревом дерева t2, если для любого пути p1 из t1 существует путь p2 в t2, такой что p1 является префиксом p2. Задача алгоритма поиска - перебрать все пути дерева t, содержащего все пути p, такие что для каждого дерева ti найдется такой путь pi, что p является префиксом pi, то есть t = { p | для всех ti существует pi в ti: p префикс pi }. Отметим, что t является поддеревом любого дерева ti. Такое поддерево будем называть максимальным поддеревом деревьев t1,..., tn. После каждого отката алгоритм сохраняет дерево перебранных путей выполнения. На выходе у алгоритма максимальное поддерево деревьев t1,..., tn, соответствующих состояниям s1,…, sn обобщенного состояния S. Алгоритм управляющего выполняется в несколько этапов. На первом этапе вход алгоритма пуст, и алгоритм начинает выполняться в некотором состоянии. На каждом последующем этапе алгоритм получает на входе пройденное дерево переходов, включающее информацию о последнем пройденном пути. Выполнение на каждом последующем этапе может начинаться в другом состоянии, но принадлежащем тому же обобщенному состоянию. На каждом этапе алгоритм пытается пройти новый путь, принадлежащий деревьям предыдущих этапов. Если же все пути уже пройдены, алгоритм проходит произвольный путь и сообщает о завершении поиска. В конце каждого этапа алгоритм выдает обновленное дерево путей, а также информацию о завершении поиска. Отметим, что алгоритм определяет окончание пути по информации от управляющего. В конце каждого перехода алгоритму известно, завершился ли путь. В тестовых наборах, разработанных по технологии UniTESK, завершение пути соответствует завершению выполнения сценарного метода.

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