Введение
1. Обзор работ 10
1.1. Типы клонов кода и методы их поиска 10
1.1.1. Типы клонов кода 10
1.1.2. Текстовый подход 11
1.1.3. Лексический подход 13
1.1.4. Синтаксический подход 15
1.1.5. Семантический подход 17
1.1.6. Метрический подход 19
1.1.7. Комбинированные подходы 21
1.1.8. Сравнения подходов 22
1.2. Методы поиска семантических ошибок 22
2. Методы поиска клонов кода 28
2.1. Разделение ГЗП на подграфы 28
2.1.1. Алгоритм разделения ГЗП на ЕС 29
2.2. Алгоритмы линейной сложности для отсева пар ЕС 31
2.3. Поиск схожих подграфов на основе слайсинга 32
2.4. Поиск схожих подграфов на основе изоморфизма деревьев
2.4.1. Преобразование ГЗП в дерево 35
2.4.2. Алгоритм изоморфизма деревьев 37
2.5. Поиск схожих подграфов на основе метрик 40
2.5.1. Битовый вектор 40
2.6. Сравнение реализованных алгоритмов 46
2.7. Сравнение с существующими методами 47
2.8. Результаты тестирования 49
2.8.1. Генерация ГЗП 50
2.8.2. Разделение ГЗП 52
2.8.3. Количество найденных клонов 53
2.8.4. Результаты работы алгоритма на основе слайсинга 54
2.8.5. Результаты работы алгоритма на основе изоморфизма деревьев 55
2.8.6. Результаты работы алгоритма на основе метрик 57
2.8.7. Сравнение результатов реализованных алгоритмов 58
3. Архитектура инструмента поиска клонов кода 60
3.1. Схема поиска клонов кода 61
3.1.1. Схема генерации ГЗП 62
3.1.2. Разделение ГЗП на подграфы 64
3.1.3. Схема поиска клонов кода 65
3.1.4. Фильтрация ложных срабатываний 65
3.2. Интегрированная система тестирования 66
3.2.1. Влияние преобразования вызовов функций на ГЗП 67
3.2.2. Влияние преобразования «диспетчер» на ГЗП 67
3.2.3. Влияние преобразования строковых констант на ГЗП 67
3.2.4. Влияние преобразования графа потока управления на ГЗП 68
3.2.5. Влияние переплетения циклов на ГЗП 68
3.2.6. Влияние переплетения функций на ГЗП 69
3.2.7. Влияние усложнения анализа потока данных на ГЗП 69
3.2.8. Влияние разбиения целочисленных констант на ГЗП 69
3.2.9. Влияние размножения тел функции на ГЗП 3.2.10. Влияние вставки ложных циклов на ГЗП 70
3.2.11. Влияние формирования непрозрачных предикатов на ГЗП 70
3.2.12. Объединение ГЗП 71
3.2.13. Оценка точности реализованных алгоритмов 72
3.3. Запуск в многоядерных системах 72
4. Поиск клонов кода для языка JavaScript 75
4.1. Архитектура динамического компилятора V8 76
4.2. Построение графа зависимостей программы по представлению Hydrogen
4.2.1. Промежуточное представление Hydrogen 77
4.2.2. Граф зависимостей программы 77
4.2.3. Построение графа зависимостей программы по представлению Hydrogen 78
4.3. Результаты тестирования 80
4.4. Сравнение разработанного инструмента с инструментом CloneDR 83
5. Методы поиска семантических ошибок 84
5.1. Схема работы инструмента 84
5.2. Поиск клонов кода на основе лексического анализа 86
5.3. Поиск семантических ошибок 87
5.4. Изоморфизм пары графов 88
5.5. Результаты тестирования 90
Заключение 92
Литература
