Анализ тестового покрытия компиляторов Выполнила: Байцерова Ю.С., 545 Гр. Научный руководитель: ст. преп. Вояковская Н. Н. Рецензент: ст. преп. Луцив Д.В.
Контекст работы RulesLanguage Codegen Tester
Постановка задачи Цель Разработка инструмента для анализа тестового покрытия компиляторов и автоматической генерации тестов на основе этого анализа Задачи Изучение существующих метрик и методов анализа тестового покрытия, их сравнение Разработка инструмента для построения графа потока управления с заданной глубиной раскрытия функций Разработка генератора тестов и анализатора тестового покрытия
Граф потока управления Пример программы на языке С Граф потока управления
Постдоминаторное и доминаторное деревья Доминаторное дерево Постдоминаторное дерево
Предлагаемое решение (1) тестируемая функция вызываемые функции графы потока управления Understand DOT-файлы экспорт Подготовительная стадия
Предлагаемое решение (2) DOT-файлы матрицы смежности Parser списки узлов итоговый граф потока управления замещение узлов с вызовом на CFG вызываемой функции Инструмент для построения пополняемого графа потока управления
Предлагаемое решение (3) итоговый граф потока управления дерево доминаторовдерево постдоминаторов граф доминаторов слияние граф компонент сильной связности объединение узлов в компоненты сильной связности множество маршрутов поиск маршрутов множество тестов на языке RulesLanguage Генератор тестов
Подготовительная стадия (1) тестируемая функция вызываемые функции графы потока управления Understand DOT-файлы экспорт Подготовительная стадия
Подготовительная стадия (2). Взаимодействие с Understand digraph "" { __N1 [color="darkgreen", label="start", shape="Msquare"]; __N2 [label="MARK (RULEnode) = RULE;"]; __N3 [label="(ClauseLexClass != RULE_LC)", shape="diamond"]; __N4 [label="fetchFromClauseList (RULE_LC, RULEnode);"]; __N5 [label="return RULEnode;"]; __N6 [color="brown", label="end", shape="Msquare"]; __N1 -> __N2; __N2 -> __N3; __N3 -> __N4 [color="green", label="yes"]; __N3 -> __N5 [color="red", label="no"]; __N4 -> __N5; __N5 -> __N6; } экспорт
Инструмент для построения пополняемого графа потока управления (1) DOT-файлы матрицы смежности Parser списки узлов итоговый граф потока управления замещение узлов с вызовом на CFG вызываемой функции Инструмент для построения пополняемого графа потока управления
Инструмент для построения пополняемого графа потока управления (2)
Генератор тестов (1) итоговый граф потока управления дерево доминаторовдерево постдоминаторов граф доминаторов слияние граф компонент сильной связности объединение узлов в компоненты сильной связности множество маршрутов поиск маршрутов множество тестов на языке RulesLanguage Генератор тестов
Генератор тестов (2). Граф доминаторов Доминаторное дерево Постдоминаторное дерево Граф доминаторов
Генератор тестов (3). Построение графа компонент сильной связности итоговый граф потока управления дерево доминаторовдерево постдоминаторов граф доминаторов соединение граф компонент сильной связности объединение узлов в компоненты сильной связности множество маршрутов поиск маршрутов множество тестов на языке RulesLanguage Генератор тестов
Генератор тестов (4). Построение графа компонент сильной связности Граф доминаторов Граф с выделенными компонентами сильной связности
Генератор тестов (5). Построение графа компонент сильной связности Удаление лишних дуг Итоговый граф
Генератор тестов (6). Множество маршрутов итоговый граф потока управления дерево доминаторовдерево постдоминаторов граф доминаторов соединение граф компонент сильной связности объединение узлов в компоненты сильной связности множество маршрутов поиск маршрутов множество тестов на языке RulesLanguage Генератор тестов
Генератор тестов (7). Множество маршрутов Итоговый граф Множество путей
Генератор тестов (8). Множество тестов на языке RoulesLanguage итоговый граф потока управления дерево доминаторовдерево постдоминаторов граф доминаторов слияние граф компонент сильной связности объединение узлов в компоненты сильной связности множество маршрутов поиск маршрутов множество тестов на языке RulesLanguage Генератор тестов
Генератор тестов (9). Множество тестов на языке RoulesLanguage start А В С stop start MARK (LOOPnode) = DO; return LOOPnode; MARK (MAPnode) = MAP; stop DO MAP do from 1 to 5 index i while ij enddo map 1 to a
Генератор тестов (10). Графический интерфейс
Заключение o Изучены и проанализированы метрики и методы анализа тестового покрытия o Разработан и реализован на языке С# инструмент построения пополняемого графа потока управления o Разработан и реализован на языке С# генератор тестов и анализатор тестового покрытия