Исследование и разработка методов автоматического поиска ошибок в компиляторах языков программирования тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Степанов Даниил Сергеевич

  • Степанов Даниил Сергеевич
  • кандидат науккандидат наук
  • 2024, ФГАОУ ВО «Санкт-Петербургский политехнический университет Петра Великого»
  • Специальность ВАК РФ00.00.00
  • Количество страниц 116
Степанов Даниил Сергеевич. Исследование и разработка методов автоматического поиска ошибок в компиляторах языков программирования: дис. кандидат наук: 00.00.00 - Другие cпециальности. ФГАОУ ВО «Санкт-Петербургский политехнический университет Петра Великого». 2024. 116 с.

Оглавление диссертации кандидат наук Степанов Даниил Сергеевич

Введение

Глава 1. Анализ методов автоматического поиска ошибок в компиляторах и их постобработки

1.1. Качество компиляторов и проблемы его обеспечения

1.2. Методы автоматического поиска ошибок в компиляторах языков программирования

1.2.1. Конструирование тестовых программ

1.2.2. Исследование тестовых оракулов

1.2.3. Исследование методов постобработки результатов

1.3. Выводы

Глава 2. Платформа для автоматического обнаружения ошибок в компиляторах языков программирования

2.1. Общая схема платформы

2.1. Модуль генерации тестов

2.1.1. Языко-независимые мутации

2.1.2. Языко-зависимые мутации

2.2. Модуль взаимодействия с компилятором

2.3. Постобработка найденных ошибок

2.4. Выводы

Глава 3. Описание новых алгоритмов генерации тестовых программ, редукции и дедупликации найденных ошибок

3.1. Типо-ориентированная генерация по шаблону

3.2. Редукция тестовых программ, приводящих к ошибке

3.3. Алгоритм автоматического обнаружения одинаковых ошибок

Глава 4. Реализация инструмента для автоматического поиска ошибок в компиляторе языка КоШп на основе платформы BBF

4.1. Модульная архитектура программного комплекса

4.2. Работа с компилятором языка программирования КоШп

4.3. Реализация модуля генерации тестов

4.3.1. Обфускатор выражений

4.3.2. Добавление циклов

4.3.3. Добавление методов в класс

4.4. Реализация модуля взаимодействия с компилятором

4.5. Реализация модуля постобработки найденных ошибок

4.5.1. Реализация алгоритмов редукции программ на языке КоШп

4.5.2. Реализация модуля автоматического обнаружения одинаковых ошибок

4.6. Выводы

Глава 5. Апробация инструмента для автоматического поиска ошибок в компиляторе языка КоШп и новых алгоритмов генерации, редукции и дедупликации

5.1. Оценка общего вклада разработанного инструмента в качество компилятора КоШп

5.2. Апробация алгоритма типо-ориентированной генерации по шаблону

5.3. Апробация алгоритма редукции тестовых программ, содержащих ошибку

5.4. Апробация алгоритма автоматического обнаружения одинаковых ошибок

5.5. Выводы

Заключение

Список сокращений и условных обозначений

Список литературы

Список иллюстративного материала

Приложение А. Акт о внедрении результатов диссертационного исследования

Рекомендованный список диссертаций по специальности «Другие cпециальности», 00.00.00 шифр ВАК

Введение диссертации (часть автореферата) на тему «Исследование и разработка методов автоматического поиска ошибок в компиляторах языков программирования»

Введение

Актуальность темы исследования и степень ее разработанности.

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

Наиболее часто используемым методом проверки качества компиляторов является ручное тестирование. Главным недостатком ручного тестирования является человеческий фактор: помимо больших трудовых и временных затрат ручное тестирование обладает низкой полнотой: фактически удается протестировать лишь ограниченное число сценариев использования конструкций целевого языка программирования. Указанные недостатки привели к созданию научной области, занимающейся вопросами качества компиляторов.

Область автоматической проверки качества компиляторов существует уже более 50 лет и, несмотря на это, в настоящее время активно развивается. Одним из самых эффективных и практически полезных методов в этой области является фаззинг. Фаззинг впервые был предложен профессором Бартоном Миллером из университета Висконзина в 1988 году. Фаззером называется программа, которая генерирует случайные последовательности данных и направляет их на вход тестируемой программе. Несмотря на простоту заложенной в его основу идеи, за прошедшие годы фаззинг показал свою эффективность и стал одним из

основных методов автоматического поиска ошибок в программах общего назначения. Опыт применения фаззинга в задачах повышения качества компиляторов также показал свою эффективность и включение фаззинга в процессы жизненного цикла компиляторов постепенно становится обычной практикой. Целью любого фаззера компиляторов является генерация множества случайных, нетривиальных, корректных программ и проверка на нем различных характеристик качества целевого компилятора. Все подходы к генерации случайных программ для тестирования компиляторов делят на две группы: генеративные и мутационные. Генеративные подходы основаны на генерации новых тестовых программ с учетом грамматики целевого языка, а мутационные подходы основаны на модификации уже существующих программ.

В области генеративных подходов выделяются работы следующих авторов: Purdom, Kenneth V., A.G. Duncan, J.S. Hutchinson, A. van Wijngaarden, Kreutzer P., Yang X., Bastani O., Cummins C., Nagai E. и др. В области мутационных подходов наиболее значимыми являются работы авторов Le V., Afshari M., Chen Y., C. Holler, K. Herzig, A. Zeller, C. Libdury, F. Donaldson, E. Nagai, A. Groce и др.

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

работы следующих авторов: A. Zeller, Y. Chen, Holmes J., Myers E., A. Zakari, J. Chen, Abreu R., M. Weiser, G. Mishergi и др.

Все подходы для генерации кода и постобработки результатов предназначены для компиляторов конкретных языков программирования или даже конкретных компиляторов и их версий, их адаптация к компиляторам других языков программирования - чрезвычайно трудоемкая задача. Поэтому создание универсальной платформы для фаззинга компиляторов, в которой были бы систематизированы и применены существующие методы, является актуальной задачей. Кроме того, генерация кода и постобработка результатов - по-прежнему актуальные проблемы, которые решены только частично. Цели и задачи диссертационной работы. Целью диссертационной работы является исследование и разработка методов генерации программ для задач автоматического тестирования компиляторов, а также методов обнаружения ошибок компиляторов и их постобработки. Для достижения поставленной цели в работе ставились и решались следующие задачи:

1. Исследование и разработка методов генерации тестовых программ для фаззинга компиляторов языков программирования.

2. Исследование и разработка метода автоматической редукции тестовых программ, приводящих к ошибкам.

3. Исследование и разработка метода обнаружения тестовых программ, приводящих к одинаковым ошибкам.

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

Постановка цели и задач исследования соответствует следующим пунктам паспорта специальности 2.3.5 Математическое и программное обеспечение вычислительных систем, комплексов и компьютерных сетей:

п. 1: модели, методы и алгоритмы проектирования, анализа, трансформации, верификации и тестирования программ и программных систем, п. 2: языки программирования и системы программирования, семантика программ, п. 10: оценка качества, стандартизация и сопровождение программных систем.

Предметом исследования являются методы автоматического обнаружения ошибок в компиляторах языков программирования и их постобработки. Теоретическая и практическая значимость работы.

Теоретическая значимость диссертационного исследования заключается в разработке нового метода генерации программ для задачи автоматического тестирования компиляторов и создании новых методов редукции найденных и обнаружения дублирующихся ошибок.

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

Методология и методы исследования. Для решения поставленных задач использовались различные методы из теории вероятности, теории графов, теории компиляции, вычислительной математики, формальных языков. Для оценки экспериментов применялись методы измерения и обработки результатов. Программная реализация платформы и инструмента выполнена на языке программирования КоШп. Положения, выносимые на защиту.

1. Метод генерации программ для задач тестирования компиляторов, учитывающий, в отличие от аналогов, не только синтаксис

программы, но и информацию из типовой системы компилятора, позволяющий расширить класс обнаруживаемых ошибок, а также повысить эффективность их обнаружения в 1,5 раза.

2. Метод редукции тестовых программ, реализующий комбинацию из существующих и разработанных алгоритмов, позволяющий увеличить эффективность редукции в среднем на 44%.

3. Метод обнаружения дублирующихся ошибок, расширяющий класс обнаруживаемых дубликатов.

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

Научная новизна результатов.

1. Впервые представлен метод генерации программ для задач тестирования компиляторов, использующий не только синтаксис исходной программы, но и информацию из типовой системы целевого языка программирования.

2. Впервые для редукции программ было применено каскадное объединение существующих и разработанных алгоритмов.

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

Степень достоверности и апробация работы. Достоверность полученных результатов подтверждается корректным использованием математического аппарата, обеспечивается положительными итогами применения разработанных методов на практике и сравнения с аналогами. Основные положения и результаты диссертационной работы опубликованы в ведущих научных изданиях и обсуждались на международных научных конференциях и семинарах: конференция ASE (ноябрь 2019 г., Сан-Диего,

США), конференция ICST (апрель 2021 г., Рио-де-Жанейро, Бразилия), семинар Modern Compilers and Languages Technologies (декабрь 2021 г., Санкт-Петербург), семинар Effective Development Technologies In Business Scenario (декабрь 2022 г., Санкт-Петербург), семинар по фундаментальным вопросам программной инженерии, теории и экспериментальному программированию STEP-2023 (апрель 2023 г., Новосибирск, Россия), семинар высшей школы интеллектуальных систем и суперкомпьютерных технологий Санкт-Петербургского политехнического университета Петра Великого (апрель 2023 г., Санкт-Петербург, Россия), семинары группы лабораторий "JetBrains Research" (ежегодно с 2018 г., Санкт-Петербург, Россия), семинары лаборатории "Верификации и анализа программ" (еженедельно с 2018 г., Санкт-Петербург, Россия). Публикации. Основные положения диссертации изложены в 4 печатных работах, из них 2 работы проиндексированы в базе Scopus, 2 работы опубликованы в журналах из перечня периодических изданий, рекомендуемых ВАК, один из которых также проиндексирован в Scopus. Внедрение. Разработанный в рамках диссертационного исследования инструмент внедрен в процесс сопровождения компилятора языка Kotlin, что подтверждено соотвествующим актом от компании АНО ДПО «Научно-исследовательский и образовательный центр «ДжетБрейнс»». Акт представлен в Приложении А.

Структура и объем работы. Диссертация состоит из введения, 5 глав и заключения. Общий объем диссертации 116 страниц; диссертация содержит 41 рисунок, 10 таблиц и одно приложение, список литературы включает 111 наименований.

Глава 1. Анализ методов автоматического поиска ошибок в компиляторах и их постобработки

В данной главе подробно описана проблема обеспечения качества компиляторов, а также выявляются причины, из-за которых все современные компиляторы содержат большое количество ошибок; с исторической перспективы рассматриваются методы для их автоматического поиска. Для более детального анализа методов автоматического поиска неисправностей в компиляторах процесс их поиска разбивается на этапы, каждый из которых подробно описан и исследован.

1.1. Качество компиляторов и проблемы его обеспечения

Ввиду повсеместности использования, к компиляторам предъявляются повышенные требованиям к таким характеристикам качества программного обеспечения [1] как функциональная пригодность, надежность, уровень производительности, безопасность и т.д. Для обеспечения качества командами разработки и поддержки компилятора применяются всевозможные средства: ручное тестирование [2], пользовательское тестирование [3], регрессионное тестирование [4], автоматические средства для поиска ошибок [5] и т.д. Но, несмотря на прилагаемые усилия, проблемы с качеством компиляторов очень серьезные: даже в продуктовых версиях самых популярных компиляторов число ошибок довольно велико. В этом легко убедиться, проанализировав информацию из системы отслеживания ошибок любого современного компилятора [6, 7]. Там можно найти десятки тысяч отчетов о найденных ошибках. Так как существенная часть ошибок обнаруживается пользователями компиляторов во время разработки программного обеспечения, то это негативно влияет на репутацию компилятора и может

понизить лояльность его пользователей [8]. Такое большое число ошибок вызвано тем, что количество возможных программ на любом языке программирования бесконечно, а чем больше язык содержит различных языковых конструкций, тем сложнее создавать сценарии их комбинирования. Кроме того, современные компиляторы содержат большое количество оптимизаций [9], призванных улучшить эффективность результирующей программы, которые также могут содержать ошибки.

Рассмотрим виды ошибок компилятора. Первый, самый очевидный, это аварийное завершение работы (падение). При этом результирующий код не создается, а пользователь получает сообщение об ошибке. Второй вид ошибок проявляется, когда результирующий бинарный код или байт-код создается, но не соответствует исходной семантике программы, то есть работает некорректно. Такие ситуации называются мискомпиляциями (от англ. miscompilation). Данный вид ошибок является намного более опасным, так как может быть не замечен или проигнорирован программистом, кроме того, такие ошибки могут возникать в определенных случаях при достаточно редких условиях. Третий вид ошибок - проблемы с производительностью, когда результат работы компилятора семантически корректен, но либо компиляция производится слишком долго, либо работа программы требует слишком большого количества времени. К четвертому виду дефектов относятся ошибки, которые напрямую не влияют на работу результирующей программы, но влияют на качество проекта в целом: ошибки плагинов, работы с системами сборки и т.п.

Имеющееся разнообразие ошибок и необходимость их эффективного обнаружения привело к созданию научной области, которая занимается автоматическим поиском дефектов в компиляторах. Данная область существует уже более 50 лет и в настоящее время активно развивается.

Одним из самых эффекивных и практически полезных методов в данной области является фаззинг [10]. Термин фаззинг был предложен в 1988 году профессором Бартоном Миллером в работе [11]. Фаззером называется программа, которая генерирует случайные последовательности данных и направляет их на вход тестируемой программе, проверяя, как эта программа будет на них работать. Сам процесс тестирования программы с применением фаззера называется фаззингом. В настоящее время существует большое количество фаззеров общего назначения [12-16], но все они плохо применимы к компиляторам ввиду сложности и структурированности входных данных.

1.2. Методы автоматического поиска ошибок в компиляторах языков программирования

Фаззинг компилятора с точки зрения организации достаточно прост и эффективен [17]: производится генерация случайной тестовой программы на целевом языке программирования, далее запускаются процессы ее компиляции и выполнения, в ходе которых проверяются необходимые свойства. Однако, несмотря на кажущуюся простоту, для полноценного тестирования необходимо решить большое число проблем. Во-первых, конструирование синтаксически и семантически корректной нетривиальной случайной программы - непростая задача. Во-вторых, необходимо решить проблему тестовых оракулов - компонентов, которые проверяют, выполняется ли проверяемое свойство качества. В третьих, необходимо обработать найденные ошибки, так как они могут дублироваться или тестовые программы, которые к ним приводят, могут содержать большое количество нерелевантной дефекту информации. На рис. 1 приведена общая универсальная схема работы большинства средств автоматического тестирования компиляторов. Далее каждый этап будет рассмотрен более подробно.

Рис 1. Общая схема работы большинства средств автоматического

тестирования компиляторов

1.2.1. Конструирование тестовых программ

Цель любого модуля конструирования тестовых программ - генерация случайной, нетривиальной и корректной программы. Рассмотрим два последних свойства генерируемых программ более подробно. Генерируемые программы должны быть нетривиальными, потому что ошибки, содержащиеся в тривиальных программах обычно обнаруживаются более простыми методами обеспечения качества и в промышленных версиях компиляторов они, обычно, уже исправлены. По

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

Все подходы к генерации кода для тестирования компилятора можно разделить на две группы: генеративные и мутационные. Генеративные подходы пытаются полностью генерировать тестовые программы, в то время как мутационные подходы модифицируют уже существующие.

Область генеративного фаззинга компиляторов начала свое развитие относительно давно - в 1972 году Пурдом П. в работе [18] представил самый очевидный и простой подход для генерации случайных программ на целевом языке программирования: итерацию по случайным правилам продукций грамматики целевого языка. В результате получается синтаксически корректная программа. К сожалению, данный подход хорошо подходит только для тестирования парсеров, так как без модификаций в подавляющем большинстве случаев генерируется семантически некорректный код. Для исправления этого ограничения исследователи предлагали различные расширения грамматик, позволяющие добавить в процесс генерации семантические правила (аффиксные грамматики [19, 20], атрибутные грамматики [21-24] и W-грамматики [25, 26]). Одной из наиболее современных работ в этой области является работа Крейцера и коллег, которые представили [27] язык описания атрибутных грамматик, содержащих в декларативной форме как синтаксические, так и семантические правила целевого языка программирования. Недостатком этого подхода является огромный объем ручной работы, необходимой для создания грамматики для любого

современного языка программирования с большим количеством конструкций.

Для преодоления приведенных выше недостатков появились методы, которые опираются на грамматику, но добавляют различные механизмы для внесения семантической информации. Исследователи Сирер и др. предложили [28] такой подход для тестирования виртуальной машины Java с помощью вероятностной итерации по правилам продукций грамматики с целью дополнительно генерации частей шаблона. Важно отметить, что входная грамматика была расширена различными правилами, например ограничениями на использование определенных правил продукций или условиями, описывающими допустимый контекст применимости правил продукции.

Еще одним примером генеративного подхода с использованием грамматики являются работы ученых Янг и др., которые представили инструмент CSmith и являющийся на момент написания работы самым востребованным и эффективным средством автоматического поиска ошибок в компиляторах языков C/C++ [29]. Отличием этого подхода от остальных является то, что правила генерации программ были описаны вручную в исходном коде инструмента. Процесс генерации состоит в следующем: сначала создаются структуры данных, далее генерируется функция main, в которой содержатся различные сценарии использования созданных структур данных. На каждом этапе генерации используется грамматика, чтобы определить, какое правило продукции может быть применено, а также выполняется набор проверок, чтобы убедиться, что результирующая программа корректна и не содержит ситуаций с неопределенным поведением (англ. undefined behavior). За годы работы инструмент обнаружил большое количество ошибок в компиляторах Clang [30] и GCC [31], что сильно помогло в улучшении их качества.

Помимо упомянутых, существует большое количество генеративных подходов, реализующих другие идеи, например: вывод правил генерации из существующего кода [32], машинное обучение [33], тестирование определенных частей компилятора путем написания генераторов необходимых выражений [34] и т.д. [35-37].

Главными недостатками генеративной группы подходов являются сложность реализации и адаптации к другим языкам программирования. Даже CSmith - самый популярный инструмент, реализующий генеративный подход, генерирует код лишь на подмножестве языков C/C++, концентрируясь на арифметических операциях и работе с памятью. Достоинствами являются в большинстве подходов гарантируемая семантическая и синтаксическая корректность результирующих программ, а также управляемый процесс генерации.

Вторая группа подходов - мутационные подходы к генерации тестовых программ на целевом языке программирования. Они отличаются от генеративных тем, что вместо полной генерации тестовых программ по грамматике используют существующие программы в качестве исходных точек для последующих их модификаций с целью получения новых программ.

Мутационные подходы делятся на 2 группы: сохраняющие и не сохраняющие исходную семантику. Все мутации могут производиться над различными представлениями программ: абстрактным синтаксическим деревом (АСД), графом потока управления (ГПУ), текстом программы и т.д.

Сохраняющие семантику мутационные подходы основываются на принципе equivalence modulo inputs (EMI) [38]. Основная идея EMI заключается в том, что две программы считаются эквивалентны друг другу относительно какого-либо набора входных данных если для каждого элемента набора поведение этих программ одинаково. Это означает, что

мутации по построению должны производить тестову. программу, семантически эквивалентную исходной. Далее производится проверка того, что мутированная и исходная программы работают одинаково. Большинство случаев несоответствия поведений являются следствием неисправностей компилятора. Тривиальными примерами сохраняющих семантику мутаций могут служить модификация или добавление "мертвого кода" (кода, не затронутого в процессе выполнения) или замены различных выражений в программе на эквивалентные. В рамках подхода можно выделить работы [39-42]. Главным недостатком EMI является его ограничение в плане того, что генерируемые программы обязательно должны быть эквивалентными, что ограничивает полноту тестирования.

Не сохраняющие семантику мутационные подходы, как понятно из названия, изменяют семантику модифицированной программы. Примерами таких модификаций могут быть: изменение знаков арифметических выражений, переименование переменных, изменения выражений, изменение иерархии классов и т.д. Такие мутации, в общем случае, не гарантируют семантическую корректность полученной после применения мутации новой программы (мутанта), поэтому после каждой мутации необходимо ее проверять и, в случае обнаружения некорректности, производить откат в предыдущее корректное состояние. Чен и др. в своей работе [43] реализовали 129 не сохраняющих семантику мутаций для тестирования различных реализации виртуальной машины Java и обнаружили таким образзом более 50 ошибок. Холлер и др. представили работу [44] по поиску ошибок в интерпретаторе JavaScript из браузера Mozilla Firefox. Основная идея работы заключалась в том, чтобы изменять узлы в абстрактном синтаксическом дереве, представляющем исходную тестовую программу, на узлы того же типа, взятые из других программ. Для повышения вероятности корректности результирующего кода авторами также было предложено несколько корректирующих

эвристик, например переименование переменных в соответствии с исходной программой. Помимо перечисленных, в рамках не сохраняющих семантику мутационных подходов можно выделить работы [45-47].

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

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

1.2.2. Исследование тестовых оракулов

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

Аварийное завершение компилятора - самый распространенный и легко детектируемый вид ошибок. Для обнаружения подобного типа неисправности необходимо проанализировать сообщение об ошибке, с которой завершился компилятор. Пример подобного сообщения об ошибке для компилятора языка КоШп представлен на рис. 2.

Похожие диссертационные работы по специальности «Другие cпециальности», 00.00.00 шифр ВАК

Список литературы диссертационного исследования кандидат наук Степанов Даниил Сергеевич, 2024 год

Список литературы

1. ГОСТ Р ИСО/МЭК 25010-2015 Информационные технологии (ИТ). Системная и программная инженерия. Требования и оценка качества систем и программного обеспечения (SQuaRE). Модели

качества систем и программных продуктов. (2018). In Росстандарт. Официальное издание. М.: Стандартинформ.

2. Itkonen J., Mantyla M. V., Lassenius C. How do testers do it? An exploratory study on manual testing practices //2009 3rd International Symposium on Empirical Software Engineering and Measurement. -IEEE, 2009.-С. 494-497.

3. Myers G. J., Sandler C., Badgett T. The art of software testing. - John Wiley & Sons, 2011.

4. Wong W. E. et al. A study of effective regression testing in practice //PROCEEDINGS The Eighth International Symposium On Software Reliability Engineering. - IEEE, 1997. - С. 264-274.

5. Rafi D. M. et al. Benefits and limitations of automated software testing: Systematic literature review and practitioner survey //2012 7th International Workshop on Automation of Software Test (AST). -IEEE, 2012.-С. 36-42.

6. Historical archive of all LLVM issues [Электронный ресурс]. -Режим доступа: http s : / /bugs. llvm. org/

7. Java bug database [Электронный ресурс]. - Режим доступа: https://bugs .j ava.com/bugdatabase/

8. Sun C, Le V, Su Z. Finding and analyzing compiler warning defects. In: Proceedings of the 38th IEEE/ACM International Conference on Software Engineering. 2016, 203-213

9. Lattner C. A. LLVM: An infrastructure for multi-stage optimization : дис. - University of Illinois at Urbana-Champaign, 2002.

10. Zeller A. et al. The fuzzing book. - 2019.

11. Barton P. Miller, Lars Fredriksen, and Bryan So. 1990. An empirical study of the reliability of UNIX utilities. Commun. ACM 33, 12 (Dec. 1990), 32-44. https://doi.org/10.1145/96267.96279

12. M. Zalewski, American Fuzzy Loop [Электронный ресурс]. - Режим до ступа: http ://lcamtuf.coredump. cx/afl/

13. M. Bohme, V.-T. Pham, M.-D. Nguyen, and A. Roychoudhury, "Directed greybox fuzzing," in Proc. ACM Conf. Comput. Commun. Security, 2017, pp. 2329-2344.

14. M. Bohme, V.-T. Pham, and A. Roychoudhury, "Coverage-based greybox fuzzing as markov chain," in Proc. ACM Conf. Comput. Commun. Security, 2016, pp. 1032-1043

15. C. Aschermann, P. Jauernig, T. Frassetto, A.-R. Sadeghi, T. Holz, and D. Teuchert, "NAUTILUS: Fishing for deep bugs with grammars," in Proc. Netw. Distrib. Syst. Security Symp., 2019.

16. J. Caballero, P. Poosankam, S. McCamant, D. Babic, and D. Song, "Input generation via decomposition and re-stitching: Finding bugs in malware," in Proc. ACM Conf. Comput. Commun. Security, 2010, pp. 413-425.

17. Marcozzi M. et al. Compiler fuzzing: How much does it matter? //Proceedings of the ACM on Programming Languages. - 2019. - T. 3. -№. OOPSLA.-C. 1-29.

18. Purdom P. A sentence generator for testing parsers. BIT Numerical Mathematics. - 1972, pp. 366-375.

19. Kenneth V. Hanford. 1970. Automatic generation of test cases. IBM Syst. J., 1970, pp. 242-257.

20. Bernard Houssais. 1977. Verification of an Algol 68 Implementation. In Proceedings of the Strathclyde ALGOL 68 Conference. 117-128.

21. A. G. Duncan and J. S. Hutchison. 1981. Using Attributed Grammars to Test Designs and Implementations. In Proceedings of the 5th International Conference on Software Engineering. 170-178.

22. Burgess CJ. 1986. Towards the automatic generation of executable programs to test a Pascal compiler. (1986).

23. Colin J Burgess and M Saidi. 1996. The automatic generation of test cases for optimizing Fortran compilers. Information and Software Technology 38, 2 (1996), 111-119.

24. M. Amodio, S. Chaudhuri, and T. Reps. 2017. Neural Attribute Machines for Program Generation. ArXiv e-prints (May 2017). arXiv:cs.AI/1705.09231

25. A. van Wijngaarden. 1965. Orthogonal design and description of a formal language. Stichting Mathematisch Centrum

26. F. Bazzichi and I. Spadafora. 1982. An Automatic Generator for Compiler Testing. IEEE Transactions on Software Engineering SE-8, 4 (1982), 343-353.

27. Kreutzer P., Kraus S., Philippsen M. Language-agnostic generation of compilable test programs. 2020 IEEE 13th International Conference on Software Testing, Validation and Verification (ICST), 2020, pp. 39-50. doi:10.1109/ICST46399.2020.00015

28. Sirer E. G., Bershad B. N. Using production grammars in software testing //ACM SIGPLAN Notices. - 1999. - T. 35. - №. 1. - C. 1-13.

29. Yang X. et al. Finding and understanding bugs in C compilers //Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation. - 2011. - C. 283-294.

30. Lattner C. LLVM and Clang: Next generation compiler technology //The BSD conference. - 2008. - T. 5. - C. 1-20.

31. Von Hagen W. The definitive guide to GCC. - Apress, 2011.

32. Bastani O. et al. Synthesizing program input grammars //ACM SIGPLAN Notices. - 2017. - T. 52. - №. 6. - C. 95-110.

33. Cummins C. et al. Compiler fuzzing through deep learning //Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis. - 2018. - C. 95-105.

34. Nagai E. et al. Random testing of C compilers targeting arithmetic optimization //Workshop on Synthesis And System Integration of Mixed Information Technologies (SASIMI 2012). - 2012. - C. 48-53.

35. Daniel M. Berry. 1983. A New Methodology for Generating Test Cases for a Programming Language Compiler. ACM Sigplan Notices 18, 2 (1983), 46-56.

36. Robert Mandl. 1985. Orthogonal Latin Squares: An Application of Experiment Design to Compiler Testing. Commun. ACM 28, 10 (1985), 1054-1058.

37. Takahide Yoshikawa, Kouya Shimura, and Toshihiro Ozawa. 2003. Random Program Generator for Java JIT Compiler Test System. In Proceedings of the Third International Conference on Quality Software. 20-23.

38. Le V., Afshari M., Su Z. Compiler validation via equivalence modulo inputs //ACM Sigplan Notices. - 2014. - T. 49. - №. 6. - C. 216-226.

39. Vu Le, Chengnian Sun, and Zhendong Su. 2015. Finding Deep Compiler Bugs via Guided Stochastic Program Mutation. In Proceedings of the 2015 International Conference on Object-Oriented Programming, Systems, Languages, and Applications. 386-399.

40. Lidbury C. et al. Many-core compiler fuzzing //ACM SIGPLAN Notices. - 2015. - T. 50. - №. 6. - C. 65-76.

41. Chengnian Sun, Vu Le, and Zhendong Su. 2016. Finding compiler bugs via live code mutation. In Proceedings of International Conference on

Object-Oriented Programming, Systems, Languages, and Applications. 849-863.

42. Alastair F. Donaldson, Hugues Evrard, Andrei Lascu, and Paul Thomson. 2017. Automated testing of graphics shader compilers. Proceedings of the ACM on Programming Languages 1, OOPSLA (2017), 93:1-93:29.

43. Chen Y. et al. Coverage-directed differential testing of JVM implementations //proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation. - 2016. - С. 85-99.

44. Christian Holler, Kim Herzig, and Andreas Zeller. 2012. Fuzzing with code fragments. In Proceedings of the 21st USENIX Conference on Security Symposium. 445-458

45. Alex Groce, Mohammad Amin Alipour, Chaoqiang Zhang, Yang Chen, and John Regehr. 2016. Cause reduction: delta debugging, even without bugs. Software Testing, Verification and Reliability 26, 1 (2016), 40-68.

46. Alex Groce, Chaoqiang Zhang, Mohammad Amin Alipour, Eric Eide, Chen Yang, and John Regehr. 2013. Help, help, i'm being suppressed! The significance of suppressors in software testing. In International Symposium on Software

47. Chen Y., Su T., Su Z. Deep differential testing of JVM implementations //2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE). - IEEE, 2019. - С. 1257-1268.

48. Flash Sheridan. 2007. Practical Testing of a C99 Compiler Using Output Comparison. Software: Practice and Experience 37, 14 (2007), 1475-1488

49. Oracle JDK [Электронный ресурс]. - Режим доступа: http://openjdk.java.net

50. IBM JDK [Электронный ресурс]. - Режим доступа: http: //www. ibm .com/developerworks/j ava/j dk

51. Jikes RVM [Электронный ресурс]. - Режим доступа: http://www.jikesrvm.org

52. Azul Systems JDK [Электронный ресурс]. - Режим доступа: http://www.azulsystems.com/products/zulu

53. GNU compiler for the Java programming language [Электронный ресурс]. - Режим доступа: https:// gcc.gnu.org/onlinedocs/ gcc-3.2.3/gcj

54. Sassa M., Sudosa D. Experience in Testing Compiler Optimizers Using Comparison Checking //Software Engineering Research and Practice. -2006.-С. 837-843.

55. Robin Morisset, Pankaj Pawan, and Francesco Zappa Nardelli. 2013. Compiler Testing via a Theory of Sound Optimisations in the C11/C++11 Memory Model. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation. 187-196

56. Chris Hawblitzel, Shuvendu K. Lahiri, Kshama Pawar, Hammad Hashmi, Sedar Gokbulut, Lakshan Fernando, Dave Detlefs, and Scott Wadsworth. 2013. Will You Still Compile Me Tomorrow? Static Cross-version Compiler Validation. In Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering. 191-201

57. Kota Kitaura and Nagisa Ishiura. 2018. Random Testing of Compilers' Performance Based on Mixed Static and Dynamic Code Comparison. In Proceedings of the 9th International Workshop on Automating TEST Case Design, Selection, and Evaluation. 38-44.

58. M. Weiser, "Program slicing," in International Conference on Software Engineering. IEEE Press, 1981, pp. 439-449.

59. Korel B., Laski J. Dynamic slicing of computer programs //Journal of Systems and Software. - 1990. - Т. 13. - №. 3. - С. 187-195.

60. Chen Z. et al. Dynamic slicing of Python programs //2014 IEEE 38th Annual Computer Software and Applications Conference. - IEEE, 2014.-С. 219-228.

61. Zhang X., Gupta N., Gupta R. A study of effectiveness of dynamic slicing in locating real faults //Empirical Software Engineering. - 2007. -Т. 12.-С. 143-160

62. Zeller A. Isolating cause-effect chains from computer programs //ACM SIGSOFT Software Engineering Notes. - 2002. - Т. 27. - №. 6. - С. 1-10.

63. Cyrille Artho. 2011. Iterative delta debugging. International Journal on Software Tools for Technology Transfer 13, 3 (2011), 223-246

64. Misherghi G., Su Z. HDD: hierarchical delta debugging //Proceedings of the 28th international conference on Software engineering. - 2006. -C. 142-151.

65. Sterling C. D., Olsson R. A. Automated bug isolation via program chipping //Proceedings of the sixth international symposium on Automated analysis-driven debugging. - 2005. - C. 23-32.

66. Regehr J. et al. Test-case reduction for C compiler bugs //Proceedings of the 33rd ACM SIGPLAN conference on Programming Language Design and Implementation. - 2012. - C. 335-346.

67. Moritz Pflanzer, Alastair F. Donaldson, and Andrei Lascu. 2016. Automatic Test Case Reduction for OpenCL. In Proceedings of the 4th International Workshop on OpenCL. 1:1-1:12.

68. Stone J. E., Gohara D., Shi G. OpenCL: A parallel programming standard for heterogeneous computing systems //Computing in science & engineering. - 2010. - T. 12. - №. 3. - C. 66.

69. Herfert S., Patra J., Pradel M. Automatically reducing tree-structured test inputs //2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE). - IEEE, 2017. - C. 861-871.

70. Sun C. et al. Perses: Syntax-guided program reduction //Proceedings of the 40th International Conference on Software Engineering. - 2018. -C. 361-371.

71. G. Gharachorlu and N. Sumner, "Pardis: Priority aware test case reduction," in International Conference on Fundamental Approaches to Software Engineering. Springer, 2019, pp. 409-426

72. Chen Y. et al. Taming compiler fuzzers // Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation. New York, NY, USA: ACM, 2013. P. 197-208. doi: 10.1145/2491956.2462173

73. Gonzalez T.F. Clustering to minimize the maximum intercluster distance // Theor Comput Sci. 1985. Vol. 38. P. 293-306. doi:10.1016/0304-3975(85)90224-5

74. Holmes J., Groce A. Causal Distance-Metric-Based Assistance for Debugging after Compiler Fuzzing // 2018 IEEE 29th International Symposium on Software Reliability Engineering (ISSRE). IEEE, 2018. P. 166-177. doi: 10.1109/ISSRE.2018.00027

75. P. Jaccard. Distribution de la flore alpine dans le bassin des dranses et dans quelques r'egions voisines. Bulletin de la Soci'et'e vaudoise des sciences naturelles, 37:241-272, 1901.

76. Myers E.W. AnO(ND) difference algorithm and its variations // Algorithmica. 1986. Vol. 1, № 1-4. P. 251-266. doi: 10.1007/BF01840446

77. Wong W.E. et al. A Survey on Software Fault Localization // IEEE Transactions on Software Engineering. 2016. Vol. 42, № 8. P. 707-740. doi: 10.1109/TSE.2016.2521368

78. Zakari A. et al. Multiple fault localization of software programs: A systematic literature review // Inf Softw Technol. 2020. Vol. 124. P. 106312. doi: 10.1016/j.infsof.2020.106312

79. Soremekun E. et al. Locating faults with program slicing: an empirical analysis // Empir Softw Eng. 2021. Vol. 26, № 3. P. 51. doi: 10.1007/s10664-020-09931-7

80. Chang B.-Y.E. et al. Type-based verification of sssembly language for compiler debugging // Proceedings of the 2005 ACM SIGPLAN international workshop on Types in languages design and implementation. New York, NY, USA: ACM, 2005. P. 91-102. doi: 10.1145/1040294.1040303

81. Hemmert K.S. et al. Source level debugger for the Sea Cucumber synthesizing compiler // 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 2003. FCCM 2003. IEEE Comput. Soc. P. 228-237. doi: 10.1109/FPGA.2003.1227258

82. Krebs N., Schmitz L. Jaccie : A Java-based compiler-compiler for generating, visualizing and debugging compiler components // Sci Comput Program. 2014. Vol. 79. P. 101-115. doi: 10.1016/j.scico.2012.03.001

83. Chen J. et al. A survey of compiler testing //ACM Computing Surveys (CSUR). - 2020. - T. 53. - №. 1.-C. 1-36.

84. Alex Groce, Chaoqiang Zhang, Eric Eide, Yang Chen, and John Regehr. 2012. Swarm Testing. In Proceedings of the 2012 International Symposium on Software Testing and Analysis. 78-88.

85. Jibesh Patra and Michael Pradel. 2016. Learning to Fuzz: Application-Independent Fuzz Testing with Probabilistic, Generative Models of Input Data. Technical Report

86. Osbert Bastani, Rahul Sharma, Alex Aiken, and Percy Liang. 2017. Synthesizing Program Input Grammars. In Proceedings of the 38th Conference on Programming Language Design and Implementation, Vol. 52. 95-110

87. Abdulazeez S Boujarwah, Kassem Saleh, and Jehad Al-Dallal. 1999. Testing syntax and semantic coverage of Java language compilers. Information and Software Technology 41,1 (1999), 15-28.

88. D. Callahan, J. Dongarra, and D. Levine. 1988. Vectorizing Compilers: A Test Suite and Results. In Proceedings of the 1988 ACM/IEEE Conference on Supercomputing. 98-105.

89. Kyle Dewey, Jared Roesch, and Ben Hardekopf. 2015. Fuzzing the Rust Typechecker Using CLP (T). In Proceedings of the 2015 30th International Conference on Automated Software Engineering. 482-493

90. Pierre-Loïc Garoche, Falk Howar, Temesghen Kahsai, and Xavier Thirioux. 2014. Testing-Based Compiler Validation for Synchronous Languages.. In NASA Formal Methods. 246-251.

91. Huang J. C. Program instrumentation and software testing //Computer. - 1978. - T. 11. - №. 4. - C. 25-32.

92. Gascon H. et al. Pulsar: Stateful black-box fuzzing of proprietary network protocols //Security and Privacy in Communication Networks: 11th EAI International Conference, SecureComm 2015, Dallas, TX, USA, October 26-29, 2015, Proceedings 11. - Springer International Publishing, 2015. - C. 330-347.

93. Takanen A. et al. Fuzzing for software security testing and quality assurance. - Artech House, 2018.

94. Cha S. K., Woo M., Brumley D. Program-adaptive mutational fuzzing //2015 IEEE Symposium on Security and Privacy. - IEEE, 2015. - C. 725-74

95. Pham V. T. et al. Smart greybox fuzzing //IEEE Transactions on Software Engineering. - 2019. - T. 47. - №. 9. - C. 1980-1997.

96. Wang J. et al. Superion: Grammar-aware greybox fuzzing //2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE). - IEEE, 2019. - C. 724-735.

97. Lee G., Shim W., Lee B. Constraint-guided Directed Greybox Fuzzing //USENIX Security Symposium. - 2021. - C. 3559-3576.

98. Godefroid P., Levin M. Y., Molnar D. SAGE: whitebox fuzzing for security testing //Communications of the ACM. - 2012. - T. 55. - №. 3. - C. 40-44.

99. Pham V. T., Böhme M., Roychoudhury A. Model-based whitebox fuzzing for program binaries //Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering. - 2016. -C. 543-553.

100. Cadar C. et al. Klee: unassisted and automatic generation of high-coverage tests for complex systems programs //OSDI. - 2008. - T. 8. - C. 209-224.

101. Kuleshov V., Precup D. Algorithms for multi-armed bandit problems //arXiv preprint arXiv:1402.6028. - 2014.

102. Wei Chu; Lihong Li; Lev Reyzin; Robert E. Schapire (2011), "Contextual bandits with linear payoff functions" (PDF), Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS): 208-214

103. Carpentier A. et al. Upper-confidence-bound algorithms for active learning in multi-armed bandits //Algorithmic Learning Theory: 22nd International Conference, ALT 2011, Espoo, Finland, October 5-7, 2011. Proceedings 22. - Springer Berlin Heidelberg, 2011. - C. 189-203.

104. D. Huang, J. Tristan, and G. Morrisett, "Compiling Markov chain Monte Carlo algorithms for probabilistic modeling," in Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2017), 2017, pp. 111-125.

105. C. Andrieu, N. de Freitas, A. Doucet, and M. I. Jordan, "An introduction to MCMC for machine learning," Machine Learning, vol. 50, no. 1-2, pp. 5-43,2003.

106. Q. Zhang, C. Sun, and Z. Su, "Skeletal program enumeration for rigorous compiler testing," in Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2017, pp. 347-361.

107. Stepanov D., Akhin M., Belyaev M. Type-centric Kotlin compiler fuzzing: Preserving test program correctness by preserving types //2021 14th IEEE Conference on Software Testing, Verification and Validation (ICST). - IEEE, 2021.-C. 318-328.

108. Chen J. et al. Compiler bug isolation via effective witness test program generation // Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. New York, NY, USA: ACM, 2019. P. 223-234. doi: 10.1145/3338906.3338957

109. Sohn J., Yoo S. FLUCCS: using code and change metrics to improve fault localization // Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis. New York, NY, USA: ACM, 2017. P. 273-283. doi: 10.1145/3092703.3092717

110. Abreu R., Zoeteweij P., van Gemund A.J.C. On the Accuracy of Spectrum-based Fault Localization // Testing: Academic and Industrial Conference Practice and Research Techniques - MUTATION (TAICPART-MUTATION 2007). IEEE, 2007. P. 89-98. doi: 10.1109/TAIC.PART.2007. 13

111. Arpit Christi, Matthew Lyle Olson, Mohammad Amin Alipour, and Alex Groce. 2018. Reduce Before You Localize: DeltaDebugging and Spectrum-Based Fault Localization. In International Symposium on Software Reliability Engineering Workshops. 184-191.

Список иллюстративного материала

1 Схема работы средств автоматического тестирования компилятора....................................................................................................................................13

2 Сообщение об аварийном завершении работы компилятора

языка Kotlin......................................................................................................................................19

3 Пример тестовой программы, приводящей к ошибке компилятора Kotlin....................................................................................................................23

4 Алгоритм дельта-дебаггинга............................................................................................24

5 Схема работы средств автоматического тестирования компилятора....................................................................................................................................25

6 Общая схема платформы для автоматического поиска ошибок в компиляторах..................................................................................................................................31

7 Пример замены узла в абстрактном синтаксическом дереве на

узел того же типа из другого дерева..........................................................................35

8 Пример программы на языке Kotlin для проведения мутации, использующей семантическую информацию....................................................37

9 Алгоритм генерации объектов произвольных типов..................................38

10 Система голосования для поиска мискомпиляций....................................40

11 Пример тестируемой программы на языке Java..............................................42

12 Тестирование по стратегии черного ящика....................................................42

13 Тестирование по стратегии серого ящика......................................................43

14 Часть символического представления примера для тестирования

по стратегии белого ящика................................................................................................43

15 Схема работы направленного тестирования компилятора....................44

16 Схема приоритезации мутаций......................................................................................45

17 Пример работы подхода SPE............................................................................................50

18 Пример работы алгоритма TCG....................................................................................51

19 Пример работы фазы генерации....................................................................................53

20 Алгоритм генерации вызовов программных конструкций..................54

21 Пример работы мутационной фазы............................................................................56

22 Алгоритм работы мутационной фазы......................................................................57

23 Схема работы модуля редукции....................................................................................59

24 Алгоритм внутрипроцедурного слайсинга..........................................................61

25 Алгоритм слайсинга на уровне функций..............................................................62

26 Пример применения алгоритма слайсинга..........................................................63

27 Алгоритм самой дальней точки для ранжирования тестовых примеров........................................................................................................................................69

28 Схема работы инструмента для автоматического тестирования компилятора языка Kotlin....................................................................................................71

29 Алгоритм обфускации случайного выражения и пример его работы..............................................................................................................................................74

30 Пример работы трансформации, добавляющей циклы............................75

31 Пример работы трансформации, добавляющей методы в класс . 76

32 Пример сообщения об ошибке компилятора Kotlin....................................77

33 Система голосования для тестирования компилятора языка

Kotlin................................................................................................................................................78

34 Пример работы текстовых трансформаций........................................................80

35 Пример работы трансформации, удаляющей унаследованные свойства и функции..................................................................................................................81

36 Пример работы трансформации, упрощающей оператор when ... 82

37 Количество отправленных дефектов за каждый месяц работы инструмента ............................................85

38 Диаграмма суммарного количества найденных ошибок в зависимости от дня эксперимента..............................................................................89

39 Примеры дефектов, найденных с применением TCG..........................89

40 Пример мискомпиляции, найденной при помощи TCG ..........92

41 Пример работы различных алгоритмов редукции........................................95

Список таблиц

1 Статистика распределения по важности найденных

дефектов..............................................................................................................................................86

2 Результаты первого эксперимента..............................................................................88

3 Результаты второго эксперимента........................................................................88

4 Краткое описание тестируемых проектов......................................................93

5 Эффективность алгоритмов редукции..................................................................93

6 Производительность алгоритмов редукции................................................94

7 Результаты попарных сравнений тестовых программ из выборки-1 ..................................................................... 97

8 Результаты попарных сравнений тестовых программ из выборки-2..................................................................... 98

9 Результаты попарных сравнений тестовых программ из выборки-3 ..................................................................... 98

10 Результирующие ранжированные списки для тестовых выборок. 98

Приложение А. Акт о внедрении результатов диссертационного

исследования

о применении результатов диссертационной работы Степанова Д.С. «Исследование и разработка методов автоматического поиска ошибок в компиляторах языков программирования»

Настоящим актом подтверждается, что разработанные в рамках диссертационного исследования Степанова Д.С. методы и основанный на них инструментарий используются в исследовательских и инженерных проектах в системе поддержки качества компилятора языка Щ)Шп.

Внедрение разработанного Степановым Д.С. инструментария в цикл разработки и обеспечения качества компилятора языка КоШп позволило обнаружить существенное число критических ошибок в компиляторе и повысить эффективность процесса поиска ошибок в проекте.

Директор AHO ДПО "Научно-исследовательский и образовательный центр "ДжетБрейнс"

АНО ДПО "Научно - исследовательский и образаватеньный центр "ДжетБрейнс" 194100, Санкт-Петербург, ул. Кантемировская, д. 2, лит. А, офис 201 ИНН 78147L7551, КПП 781401001 ОГРН 1187800000134

АКТ

Иванов A.B.

Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.