АННОТАЦИЯ 4
ВВЕДЕНИЕ 4
1 Основные определения 6
1.1 Конечный автомат 6
1.2 Модель неисправности 9
1.3 Метод Василевского 10
2 Обзор существующих инструментов 12
2.1 Формат файла .fsm 12
2.2 FSMTest-1.0 13
2.3 FSMTestOnline 13
3 Программная реализация 15
3.1 Инструменты разработки 15
3.2 Получение таблицы из файла формата .fsm 15
3.3 Множество достижимости 16
3.3.1 Описание 16
3.3.2 Реализация 17
3.4 Множество различимости 23
3.4.1 Описание 23
3.4.2 Реализация 23
3.5 Метод Василевского 29
3.5.1 Описание 29
3.5.2 Реализация 29
3.6 Диагностическая последовательность 34
3.6.1 Описание 34
3.6.2 Реализация 35
4 Экспериментальные результаты 41
4.1 Сравнение последовательной и параллельной реализации построения
множества различимости 41
4.2 Сравнение последовательной и параллельной реализации оптимизации
теста 42
4.3 Сравнение последовательной и параллельной полной реализации метода Василевского 44
4.4 Сравнение последовательной и параллельной реализации построения
диагностической последовательности 45
ЗАКЛЮЧЕНИЕ 47
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ 48
Тестирование программного обеспечения является одним из ключевых этапов в разработке качественного и надежного программного продукта. Одним из подходов к автоматизации тестирования является использование конечно-автоматных методов синтеза тестов. Однако существующие инструменты синтеза тестов обладают рядом недостатков, и целью данной работы является их доработка и оптимизация.
Тестирование на основе конечных автоматов имеет ряд преимуществ:
1. Автомат является простой моделью [1, 2, 3] для описания различных дискретных систем, например телекоммуникационных.
2. При автоматном тестировании гарантируется полнота покрытия неисправностей [4, 5].
Известные инструменты синтеза тестов [6, 7] реализованы
последовательно, что затрудняет работу с конечно-автоматными моделями сложных систем. При последовательной реализации конечно-автоматных методов синтеза тестов, программа задействует лишь один поток исполнения. Данный подход имеет ряд преимуществ, таких как понимание и простота реализации. Но при таком подходе есть и существенные недостатки, такие как длительное время исполнения для автоматов, имеющих большое число состояний.
Для решения проблемы длительного времени исполнения можно использовать параллельные вычисления [8, 9]. Параллельные вычисления - это способ организации компьютерных вычислений, позволяющий распределить задачу на несколько процессоров или ядер, что может привести к ускорению работы программ.
Параллельная реализация позволяет генерировать тестовые последовательности одновременно на всех имеющихся ядрах (процессах), что в свою очередь может значительно уменьшить время не только
нахождения тестовых последовательностей, но и процесса тестирования в целом.
В данной работе проверяется эффективность применения многопоточного программирования [8] для оптимизации синтеза тестов методом Василевского, а также выявляется и устраняется ряд недостатков существующих реализаций.
В результате проведенной работы был разработан пакет программ, включающий в себя последовательные и параллельные алгоритмы. К последовательным алгоритмам относятся реализации синтеза множеств достижимости и различимости, диагностической последовательности и теста по методу Василевского. К параллельным алгоритмам относятся реализации синтеза множества различимости, диагностической последовательности и теста по методу Василевского. Было проведено сравнение корректности результатов с уже имеющимися реализациями. Были проведены замеры времени выполнения последовательных и параллельных реализаций, по результатам которых были сделаны выводы о приросте производительности параллельных реализаций.
На основании выполненных экспериментов можно сделать вывод, что при использовании параллельных реализаций, которые задействуют 8 потоков, скорость выполнения увеличивается на 30%. Следует учесть тот факт, что прирост скорости возрастает при увеличении числа состояний автомата, от которого зависит объем вычислений программы, то есть, чем больше вычислений необходимо для выполнения программы, тем больше будет прирост.
Необходимо также отметить, что наибольший вклад во время построения теста вносит процедура оптимизации теста. Последующие работы в данном направлении могут быть сосредоточены на оптимизации этого алгоритма, в частности, в процессе формирования теста. Разработанное программное обеспечение размещено в открытом доступе [11] для дальнейших исследований и прикладного использования.
