Бакалаврская работа посвящена алгоритмам поиска путей в направленном автоматическом случайном тестировании — Concolic Testing. Рассмотрены современные исследования в этой области. По формальному описанию в научной статье реализован алгоритм поиска путей. Прототип алгоритма был описан в рамках фаззера белого ящика для Java байткода — KEX. Проведена сравнительная оценка эффективности реализованного алгоритма по сравнению с известными аналогами.

This work is devoted to path finding algorithms in directed automatic random testing — Concolic Testing. An overview of recent research in this area is given. According to the formal description in the scientific paper, a path finding algorithm is implemented. The prototype of the algorithm was described in the framework of the white-box fuzzer for Java bytecode — KEX. A comparative assessment of the efficiency of the implemented algorithm in comparison with the known analogs is carried out.

• СПИСОК ОБОЗНАЧЕНИЙ И СОКРАЩЕНИЙ
• ВВЕДЕНИЕ
• 1. Анализ использования методов анализа ПО для автоматического тестирования программ
  • 1.1. Использование методов анализа ПО при автоматическом тестировании
  • 1.2. Статический и динамический анализ
  • 1.3. Concolic Testing
  • 1.4. Резюме
• 2. Постановка задачи анализа эффективности алгоритмов поиска пути
  • 2.1. Задачи анализа алгоритмов
  • 2.2. Задача реализации алгоритма поиска путей в KEX
  • 2.3. Резюме
• 3. Реализация прототипа алгоритма поиска путей в рамках KEX
  • 3.1. Control-Flow Graph Directed Search
  • 3.2. Обзор деталей реализации KEX, необходимых для разработки прототипа
    • 3.2.1. Представление статических структур программ
    • 3.2.2. Трассы
    • 3.2.3. Модель представления программы в KEX
  • 3.3. Реализация прототипа алгоритма CFGDS в KEX
    • 3.3.1. Граф CFCG и требования к его реализации
    • 3.3.2. Класс StaticGraph
    • 3.3.3. Изменения в ConcolicChecker
    • 3.3.4. Процедура searchAlongPath
  • 3.4. Резюме
• 4. Апробация прототипа и анализ полученных результатов
  • 4.1. Отбор критериев
    • 4.1.1. Временные критерии
    • 4.1.2. Количественные критерии
    • 4.1.3. Критерии, основанные на покрытии
  • 4.2. Сбор статистики
  • 4.3. Описание плана экспериментов
  • 4.4. Результаты экспериментов и их анализ
    • 4.4.1. Проект AuthzForce
    • 4.4.2. Проект Apache Commons Codec
    • 4.4.3. Проект Exp4j
    • 4.4.4. Проект Fescar
    • 4.4.5. Проект Gareth
    • 4.4.6. Проект Karg
    • 4.4.7. Проект Koin
    • 4.4.8. Подведение итогов экспериментального исследования
  • 4.5. Резюме
• ЗАКЛЮЧЕНИЕ
• СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
• ПРИЛОЖЕНИЕ 1. ГРАФИКИ
• ПРИЛОЖЕНИЕ 2. ЛИСТИНГИ