Автоматическая генерация тестовых данных для оптимизаторов графических моделей

       

Генератор тестовых данных для оптимизатора Flowchart


Набор тестов предназначен для генератора кода, осуществляющего трансляцию и оптимизацию графа Flowchart блока Stateflow Chart, описывающего конструкцию if-then-else.

Оптимизатор ищет в графе вершины, соединенные двумя и более дугами. Каждой дуге ставится в соответствие условие, в случае выполнения которого осуществляется переход по этой дуге, а также может быть определено действие, осуществляемое при переходе. Для каждой вершины графа одна из исходящих дуг не должна иметь условия - она соответствует ветви "else" конструкции "if-then-else".

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

В соответствии с методом GraphOTK, на основе описания алгоритма оптимизации строится абстрактная модель тестов.

В случае оптимизации Flowchart в описании алгоритма используются следующие термины: StateflowMachine (часть блока Simulink Stateflow Chart, которая содержит описание flowchart-графа) и вершины графа.

Шаблоном для оптимизатора является блок Stateflow Chart, который содержит не менее двух вершин, соединенных дугами.

В процессе генерации для блока Stateflow Chart строятся различные циклические и ациклические графы, описывающие структуры if-then-else различной разветвленности и глубины вложенности. Гарантируется, что из начальной вершины графа можно достичь любой другой его вершины. Число вершин в графах изменяется от 3 до 10. Число дуг, соединяющих произвольные две вершины, изменяется от 0 до 3.

Каждой (кроме одной) дуге, исходящей из каждой вершины, поставлено в соответствие условие, заключающееся в проверке принадлежности входного сигнала блока заданному интервалу. Гарантируется, что уловия condition-узлов дуг, исходящих из одной вершины, являются взаимоисключающими.

Каждой дуге поставлено в соответствие действие; в результате выполнения действий формируется величина выходного сигнала блока в зависимости от величины входного сигнала.
Для дуг, исходящих из начальной вершины графа, действие заключается в присваивании выходному сигналу величины входного сигнала, умноженной на некоторый коеффициент (различный для различных дуг). Для остальных дуг действие заключается в прибавлении к величине выходного сигнала величины входного сигнала, умноженной на некоторый коеффициент (различный для различных дуг). Каждый тест представляет собой модель, содержащую блок Statflow Chart.

Входной сигнал подается извне (с помощью блока InPort), выходной сигнал подается на выход модели (блок OutPort).

Целью генерации является получение набора тестов, содержащих блок Stateflow Chart и удовлетворяющих следующим требованиям:



  • тесты должны содержать графы с количеством конечных вершин (т.е. вершин, у которых нет исходящих дуг) от 1 до 5 (значение 5 выбрано в целях получения приемлемого количества тестов);
  • между начальной вершиной графа и каждой из конечных вершин должны быть пути (по дугам через другие вершины графа, без учета циклов) длины от 1 до 5 (длина равна числу дуг на пути); должны быть перебраны все возможные сочетания длин пути (т.е. должны быть графы, где все пути имеют длину 1, графы с путями длины 1 и 2 и т.д.);
  • для каждой упомянутой выше комбинации длин пути набор тестов должен содержать как ациклические графы, так и графы с циклами;
  • число дуг между вершинами графа на каждом из путей должно варьироваться от 1 до 3 (что соответствует безусловному переходу, конструкции "if-else" и конструкции "if-elseif-else").


Объем и время генерации сгенерированного множества тестовых данных тестов приведены в Таб. .

В приложении A приведен аннотированный пример сгенерированных тестовых данных для оптимизации Flowchart.

Таб. 2. Характеристики сгенерированных тестов для оптимизации Flowchart.

Количество тестовРазмер тестов, MBВремя генерации
1335603 m. 45 s.

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