Автоматический поиск ошибок в компьютерных программах с применением динамического анализа тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Исходжанов, Тимур Равилевич

• Исходжанов, Тимур Равилевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Исходжанов, Тимур Равилевич

Содержание

1 Обзор систем поиска ошибок

1.1 Сценарии тестирования с применением детекторов

1.2 Ошибки первого и второго рода

1.3 Инструментирование программ

1.3.1 Динамическая инструментация

1.3.2 Статическая инструментация

1.3.3 Компиляторная инструментация

1.4 Библиотеки времени исполнения

1.5 Обработка и хранение состояния памяти

1.6 Поиск переполнений переменных целых типов

1.7 Поиск ошибок работы с памятью

1.7.1 МетсЬеск

1.7.2 Подавление ошибок первого рода

1.7.3 АсИгеэзЗапШгег

1.7.4 Функции работы со строками и массивами байт

1.8 Поиск состояний гонок

1.8.1 Алгоритм Ьоск^

1.8.2 Алгоритмы, основанные на отношении предшествования

1.8.3 Гибридные алгоритмы

2 Детектор состояний гонок ТЬгеас18апШгег

2.1 Методология разработки

2.2 Алгоритм ТЬгеас^апШгег

2.2.1 Вспомогательные определения

2.2.2 Описание базового алгоритма

2.3 Информация об ошибках

2.3.1 Точность стеков предыдущих доступов к памяти

2.3.2 Пример сообщения об ошибке

2.4 Особенности программной реализации алгоритма

2.5 Модификации алгоритма

2.5.1 Режим Happens-before

2.5.2 Оптимизация fast mode

2.6 Сравнение с классическими алгоритмами

2.7 Динамические аннотации

2.8 Обработка событий синхронизации

2.9 Рекомендации по применению

2.10 Производительность детектора ThreadSanitizer

2.11 Переход к компиляторному инструментированию

2.12 Пример найденной критической ошибки

2.13 Заключение

3 Комбинированное инструментирование

3.1 Применение комбинированного инструментирования

3.2 Производительность систем инструментирования

3.3 Ускорение модуля инструментирования DynamoRIO

3.3.1 Быстрая трансляция уже инструментированного кода

3.3.2 Расходы на оптимизацию цепочек базовых блоков

3.3.3 Файловый кэш инструментированного кода

3.3.4 Исполнение отдельных модулей без трансляции

3.4 Направления дальнейших исследований

4 Практическое применение

4.1 Обзор инфраструктуры тестирования Chromium

4.2 Применение детекторов в системе тестирования

4.3 Доработка динамических детекторов ошибок

4.4 Заключение

5 Заключение

А Приложение

А.1 Примеры работы алгоритма ThreadSanitizer

А. 1.1 Простейшее состояние гонки

А. 1.2 Записи в память с синхронизацией посредством мьютекса

А. 1.3 Пропуск состояния гонки в режиме happens-before

А. 1.4 Синхронизация, требующая аннотирования

А.2 Примеры распространенных состояний гонок

А.2.1 Состояние гонки на составных типах данных

А.2.2 Передача данных через переменную простого типа

А.2.3 Создание объекта без синхронизации

А.2.4 Инициализация с двойной проверкой условия

А.2.5 Использование блокировки на чтение при записи

А.2.6 Битовые поля

А.2.7 Состояние гонки на указателе виртуальной таблицы

А.З Ошибки первого рода гибридного алгоритма

А.3.1 Условная переменная РОБ1Х

А.3.2 Очереди сообщений

А.3.3 Подсчет ссылок

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

Введение

Актуальность работы

Компьютерные программы часто содержат ошибки. Ошибки в программном обеспечении могут приводить к разнообразным последствиям, в том числе к таким серьезным, как большие экономические потери и гибель людей [3]; к неправильному или непредсказуемому поведению программ, замедлению их работы, аварийным завершениям исполнения, порче данных и т.п. Ошибки бывают детерминированные (воспроизводятся при одних и тех же начальных данных) и недетерминированные (приводят к различным последствиям от запуска к запуску).

Особый интерес представляют ошибки типа «неопределенное поведение» (англ. undefined behavior), которые происходят при нарушении программистом стандарта языка либо спецификаций используемых программных функций или библиотек. Примером такой ошибки является доступ к памяти за границами массива в программах на языках C/C++. Часто неопределенное поведение указывается в спецификации языка или интерфейса в целях ее упрощения и оптимизации, так как допускает большое количество различных корректных реализаций, из которых можно для каждого конкретного случая выбрать наиболее подходящую (например, наиболее эффективную). В случае нарушения спецификации, приводящего к возникновению неопределенного поведения, компилятор или библиотека вправе выполнять некорректные и неожиданные действия.

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

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

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

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

К очевидным недостаткам динамического анализа относится то, что ошибки возможно находить только в том коде, который исполняется на наборе тестов («покрыт» тестами). Впрочем, если код крупного программного проекта недостаточное покрыт тестами, то это само по себе является проблемой. К недостаткам статического анализа относится его значительная вычислительная сложность (нередко — более чем линейно зависящая от размера кода) и обычно низкая точность. Часто поиск нетривиальных ошибок статическим анализом с достаточной точностью возможен только для отдельных изолированных модулей программы и требует особой организации ее исходного кода.

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

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

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

Для достижения цели работы были поставлены следующие задачи:

1. Изучение и развитие существующих средств поиска ошибок работы с памятью и «состояний гонок» (data race).

2. Разработка нового алгоритма поиска ошибок типа «состояние гонки» и динамического детектора таких ошибок, применимого для тестирования кода с нестандартными средствами синхронизации. Сравнение эффективности и точности полученного детектора с аналогами.

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

(Инструментирование — модификация или внедрение кода в программу, например с целью отслеживания происходящих в ней событий.)

4. Создание автоматической системы тестирования крупного программного проекта с применением модернизированных и новых разработанных детекторов ошибок.

Научная новизна. Благодаря применению динамических аннотаций удалось упростить задачу нахождения ошибок типа «состояние гонки» (которая является NP-трудной), что позволило применить уточненную модель одновременности событий в многопоточных программах. Используя эту модель, был разработан новый алгоритм поиска таких ошибок, обладающий большей точностью, чем аналоги.

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

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

Разработан и реализован ThreadSanitizer, новый детектор ошибок типа «состояние гонки». Благодаря использованию ThreadSanitizer для тестирования браузера Chromium, а также серверного программного обеспечения компании Google было обнаружено более тысячи ранее неизвестных ошибок, в том числе десятки критических.

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

Рассматриваются вопросы практического применения детекторов для тестирования крупных программных проектов. Были доработаны известные детекторы ошибок работы с памятью (в частности, Valgrind/Memcheck).

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

На защиту выносятся следующие положения:

• Разработан новый алгоритм поиска ошибок типа «состояние гонки» (data race) с применением уточненной модели одновременности событий в многопоточных программах. Алгоритм был реализован в новом детекторе состояний гонок для программ на языках C/C++, позволяющем достичь большей точности нахождения ошибок, чем у аналогов.

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

• Создана система регулярного автоматического тестирования программного обеспечения, использующая различные динамические детекторы ошибок, доработанные на основании их анализа. Система внедрена для тестирования веб-браузера Chromium.

Программные реализации, описываемые в данной работе, доступны в виде открытых исходных кодов.

Апробация работы. На разных этапах работы основные результаты по теме диссертации были представлены на следующих конференциях и семинарах:

1. Workshop on Binary Instrumentation and Applications, WBIA'09 (Нью-Йорк, 2009).

2. 52-ая научная конференция МФТИ (Долгопрудный, 2009).

3. Runtime Verification, RV 2011 (Сан-Франциско, 2011).

4. Семинар Института системного программирования РАН (Москва, 2013).

5. Научные семинары кафедры информатики МФТИ (Москва, Долгопрудный, 2010-2013).

По теме диссертации автором опубликовано 5 работ (из них 3 в изданиях из перечня ВАК).

Разработанные детекторы и подходы были успешно использованы для тестирования браузера с открытым исходным кодом Chromium, а также серверного программного обеспечения Google.

1 Обзор систем поиска ошибок

1.1 Сценарии тестирования с применением детекторов

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

Хорошо подходят для анализа автоматические модульные тесты (англ. unit test) — небольшие программы или специальные функции программы-теста, которые обычно выполняют небольшое количество простых действий с программной компонентой, после чего сравнивают полученный результат с ожидаемым. Такие тесты в большинстве своем небольшие и многие из них проверяют «особые» условия, при которых чаще всего и происходят ошибки (например, граничные случаи). Эти особенности как раз хорошо подходят для автоматического поиска ошибок детекторами. Также модульные тесты хороши тем, что их можно многократно перезапустить в случае возникновения недетерминированных ложных срабатываний или пропусков ошибок (см. раздел 1.2). К сожалению, такой подход наследует от модульного тестирования основной недостаток — невозможность нахождения ошибок в коде, не исполняемом тестами.

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

и

ные данные (например, по аналогии с бисекцией) и получить удобный для ручного исследования пример некорректной работы программы [5]. Если же программа отработала корректно, то можно сгенерировать новые входные данные и повторить процесс.

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

1.2 Ошибки первого и второго рода

Не все виды программных ошибок можно находить с абсолютной точностью. Например, точного алгоритма нахождения ошибок типа «использование неинициализированной памяти» не существует, так как он бы позволил решить проблему останова [7].

Введем классификацию погрешностей алгоритмов поиска ошибок, аналогичную принятой в математической статистике:

Определение. Ошибкой первого рода или ложным срабатыванием

(англ. false positive) называется такая ситуация, когда в результате работы детектора пользователь получает сообщение об ошибке, которой на самом деле нет в программе. Ошибкой второго рода или пропуском ошибки (англ. false negative) называется такая ситуация, когда в результате работы детектора пользователь не получает сообщения об ошибке, которая есть в программе.

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

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

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

1.3 Инструментирование программ

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

ей.

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

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

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

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

1.3.1 Динамическая инструментация

При динамической инструментации двоичного кода (англ. dynamic binary instrumentation, DBI) дополнительный код вносится в код исследуемой программы во время ее исполнения.

Для этого код программы разбивается на базовые блоки1. Перед первым исполнением очередного базового блока его инструкции преобразуются в некоторое промежуточное представление (например, дерево выражения или список инструкций). Далее анализатор, используя интерфейс программирования приложений (API) системы инструментирования, считывает и модифицирует код программы в этом представлении. Затем система инструментирования преобразует инструментированную версию базового блока обратно в машинные инструкции, которые помещаются в кэш инструментированного кода (англ. code cache), что позволяет избежать необходимости повторной обработки фрагментов кода. Вместо инструкции перехода (англ. jump), в конце инструментированного базового блока записывается вызов диспетчера переходов, реализуемого инструментатором.

Для такого инструментирования обычно не требуется исходный код, а некоторые промежуточные представления оптимизированы для удобства выполнения необходимых преобразований кода. Поэтому динамическая инстру-ментация широко используется для написания профиляторов, отладчиков, моделирования кэшей процессоров, утилит для поиска ошибок и т.п. Широко применяются системы динамической инструментации Valgrind, PIN и Dynamo-RIO [8, 9, 10].

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

1. Перевод больших объемов кода в промежуточное представление и преобразование обратно в машинное представление занимает много времени в процессе работы (порядка 1000 инструкций системы инструментации на одну инструкцию исходной программы [11]);

2. Переходы между базовыми блоками и вызовы функций должны осуществляться через диспетчер, который проверяет наличие цели перехода в кэше инструментированного кода и выполняет инструментацию в случае промахов кэша (англ. cache miss). При этом требуется выполнить дорогостоящие операции переключения контекста процессора между исполняемым кодом и диспетчером, а затем обратно;

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

3. Дополнительному коду инструментации чаще всего требуются регистры процессора для обработки происходящих в программе событий. Так как в этих регистрах программа может хранить нужные ей данные, в начале внедренного кода нужно сохранить старые значения этих регистров (например, поместив на стек), а в конце — восстановить. Чаще всего это требует выполнения операций доступа к памяти, что ощутимо медленнее работы с регистрами. Решение задачи перераспределения регистров между оригинальным и дополнительным кодом требует компромисса между скоростью инструментирования кода и эффективностью порожденного инструментированного кода;

4. При внесении дополнительных инструкций в код, он сдвигается в памяти, что требует пересчета относительных смещений (трансляции) во всём коде программы;

5. Система должна выполнять проверки, что ни один переход (вызов функции) не приводит к исполнению неинструментированной (нетранслиро-ванной) версии кода.

Некоторые из этих накладных расходов оказывают влияние в основном при старте программы (в начале ее работы), другие влияют и на скорость обработки данных при продолжительной работе, то есть при многократном выполнении одного и того же кода.

Например, система инструментирования Valgrind, использующая неэффективное платформенно-независимое промежуточное представление кода, замедляет работу однопоточных программ приблизительно в 5 раз [7], даже если не требуется вносить никакого дополнительного кода. При этом по историческим причинам Valgrind исполняет потоки в многопоточных программах поочередно (т.е. не одновременно), что оказывает существенное влияние на производительность при использовании современных многоядерных систем. Более новая система DynamoRIO замедляет работу программ на десятки процентов, при этом позволяя потокам исполняться параллельно. PIN также позволяет потокам исполняться одновременно, но работает в 2-3 раза медленнее DynamoRIO.

Некоторые системы динамической инструментации в процессе работы выполняют оптимизацию инструментированного кода. Например, если блок-на-

значение прямого перехода в конце базового блока уже инструментирован, то можно обойтись без вызова диспетчера базовых блоков, просто заменив его на соответствующую инструкцию перехода. Используя счетчики количества исполнений базовых блоков, можно выделить часто исполняемые подряд последовательности фрагментов кода, а также наиболее частые адреса назначений косвенных переходов и вызовов (англ. indirect jump, indirect call). Далее такие цепочки можно заново инструментировать, на этот раз располагая инструментированные блоки кода подряд в памяти. Это существенно снижает нагрузку на кэш процессора и издержки на косвенные переходы и вызовы. В некоторых случаях такого рода оптимизации даже позволяют инструментированной программе превзойти производительность неинструментированной версии [10]. Однако лишние накладные расходы на подсчет числа испонений базовых блоков могут нивелировать эффект от этой оптимизации.

Динамическая инструментация обладает уникальными функциональными возможностями. Во-первых, это один из немногих подходов, которому не требуется доступа ни к исходному коду программы, ни к отладочной информации (англ. debug information). Во-вторых, так как системы инструментации работают с двоичным кодом, исполняемым программой, существует возможность инструментирования динамически сгенерированного (англ. J IT) и самомодифицирующегося (англ. self-modifying code), что является в некоторых случаях необходимым для корректной работы анализаторов.

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

Некоторые алгоритмы динамического анализа программ накладывают ограничения на оптимизации кода, которые можно применять при его компиляции, что зачастую требует перекомпилирования программ для тестирования, тем самым нивелируя одно из достоинств данного подхода. Например, многие алгоритмы анализа несовместимы с оптимизацией кода посредством подстановки функций (англ. function inlining), так как она удаляет инструкции вызова и возврата, что существенно меняет стеки вызовов в программе. Другие примеры более подробно разобраны в разделах 1.7.1 и 1.7.4.

1.3.2 Статическая инструментация

Статическая инструментация двоичного кода (англ. static binary instrumentation) стремится минимизировать затраты на инструментацию во время исполнения, выполняя ее до запуска (например, во время компоновки программы или как отдельное действие перед запуском).

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

Список литературы диссертационного исследования кандидат наук Исходжанов, Тимур Равилевич, 2013 год

Список использованных источников

1. Кудрин М., Прокопенко А., Тормаеов А. Метод нахождения состояний гонки в потоках, работающих на разделяемой памяти // Труды МФТИ — 2009 - Т. 1, № 4 - С. 182-201.

2. Заборовский Н.В. Расчетная модель для нахождения состояний гонок в многопоточных алгоритмах: дис. ... канд. физ.-мат. наук /

Н.В. Заборовский - МФТИ - 2011.

3. Leveson Nancy G, Turner Clark S. An investigation of the Therac-25 accidents // Computer - 1993 - V. 26, no. 7 - P. 18-41.

4. Ernst Michael D. Static and dynamic analysis: Synergy and duality

// WODA 2003: ICSE Workshop on Dynamic Analysis / Citeseer - 2003 -P. 24-27.

5. Test-case reduction for С compiler bugs / John Regehr, Yang Chen,

Pascal Cuoq et al. // Proceedings of the 33rd ACM SIGPLAN conference on Programming Language Design and Implementation — PLDI '12 — New York, NY, USA: ACM, 2012 - P. 335-346.

6. Arya Abhishek, Neckar Cris. Fuzzing for Security // The Chromium Blog — URL: http://blog.chromium.org/2012/04/fuzzing-for-security.html

(дата обращения: 1.08.2013).

7. Seward Julian, Nethercote Nicholas. Using Valgrind to detect undefined value errors with bit-precision // USENIX Annual Technical Conference — 2005 — P. 17-30.

8. Nethercote Nicholas, Seward Julian. Valgrind: A framework for heavyweight dynamic binary instrumentation // Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation —

PLDI '07 - New York, NY, USA: ACM, 2007 - P. 89-100.

9. Pin: building customized program analysis tools with dynamic instrumentation / Chi-Keung Luk, Robert Cohn, Robert Muth et al.

// Proceedings of the 2005 ACM SIGPLAN conference on Programming

language design and implementation — PLDI '05 — New York, NY, USA: ACM, 2005 - P. 190-200.

10. Bruening Derek. Efficient, Transparent, and Comprehensive Runtime Code Manipulation: Ph. D. thesis / Derek Bruening — M.I.T — 2004.

11. Hu Shiliang, Smith James E. Reducing startup time in co-designed virtual machines // ACM SIGARCH Computer Architecture News - 2006 - V. 34, no. 2 — P. 277-288.

12. Edwards Andrew, Vo Hoi, Srivastava Amitabh. Vulcan binary transformation in a distributed environment // Microsoft Research Technical Report — 2001.

13. BIRD: Binary Interpretation using Runtime Disassembly / Susanta Nanda, Wei Li, Lap-Chung Lam, Tzi-cker Chiueh // Proceedings of the International Symposium on Code Generation and Optimization — CGO '06 — Washington, DC, USA: IEEE Computer Society, 2006 - P. 358-370.

14. Syzygy — profile guided, post-link executable reordering — URL: http://c0de.g00gle.c0m/p/sawbuck/wiki/SyzygyDesign (дата обращения: 1.08.2013).

15. GCC, the GNU Compiler Collection - URL: http://gcc.gnu.org/ (дата обращения: 1.08.2013).

16. gcov — a Test Coverage Program // GCC online documentation — URL: http://gcc.gnu.org/onlinedocs/gcc/Gcov.html

(дата обращения: 1.08.2013).

17. Eigler Frank Ch. Mudflap: pointer use checking for C/C++ // GCC Developers Summit / Red Hat Inc - 2003.

18. Necula George C., McPeak Scott, Weimer Westley. CCured: Type-safe retrofitting of legacy code // Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages — POPL '02 - 2002 - P. 128-139.

19. Hasabnis Niranjan, Misra Ashish, Sekar R. Light-weight bounds checking // Proceedings of the International Symposium on Code Generation and Optimization - CGO '12 - 2012 - P. 135-144.

20. CRT Debug Heap Details // Microsoft Developer Network —

URL: http://msdn.microsoft.com/en-us/library/974tc9tl(v=vs. 110).aspx (дата обращения: 1.08.2013).

21. Perens Bruce. Electric Fence malloc() Debugger — URL: http://perens.com/FreeSoftware/ElectricFence/ (дата обращения: 1.08.2013).

22. Berger Emery D., Zorn Benjamin G. DieHard: probabilistic memory safety for unsafe languages // Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation — PLDI '06 — New York, NY, USA, 2006 - P. 158-168.

23. AddressSanitizer: a fast address sanity checker / Konstantin Serebryany, Derek Bruening, Alexander Potapenko, Dmitry Vyukov // Proceedings of the 2012 USENIX conference on Annual Technical Conference - USENIX ATC'12 - Berkeley, CA, USA, 2012 - P. 28-28.

24. MemorySanitizer — URL: https://code.google.eom/p/memory-sanitizer (дата обращения: 1.08.2013).

25. Zhao Qin, Bruening Derek, Amarasinghe Saman. Umbra: Efficient and scalable memory shadowing // Proceedings of the International Symposium on Code generation and Optimization - CGO '10 - 2010 - P. 22-31.

26. Intel® Memory Protection Extensions (Intel® MPX) // Intel® Architecture Instruction Set Extensions Programming Reference — 319433-015. Intel, 2013.

27. 2011 С WE/SANS Top 25 Most Dangerous Software Errors // The MITRE Corporation — URL: http://cwe.mitre.org/top25/

(дата обращения: 1.08.2013).

28. Understanding integer overflow in C/C++ / Will Dietz, Peng Li, John Regehr, Vikram Adve // Proceedings of the 2012 International Conference on Software Engineering - ICSE 2012 - Piscataway, NJ, USA: IEEE Press, 2012 -

P. 760-770.

29. clang: а С language family frontend for LLVM // The LLVM Compiler Infrastructure — URL: http://clang.llvm.org/ (дата обращения: 1.08.2013).

30. Hastings Reed, Joyce Bob. Purify: Fast detection of memory leaks and access errors // Proceedings of the Winter 1992 USENIX Conference — 1991 —

P. 125-138.

31. Intel® Inspector XE 2013 -

URL: http://software.intel.com/en-us/intel-inspector-xe (дата обращения: 1.08.2013).

32. Herb Sutter. The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software —

URL: http://herbsutter.com/welcome-to-the-jungle/ (дата обращения: 1.08.2013).

33. Boehm Hans-J., Adve Sarita V. Foundations of the С++ concurrency memory model // SIGPLAN Notices - 2008 - V. 43, no. 6 — P. 68-78.

34. Java Language Specification, The 3rd Edition / James Gosling, Bill Joy, Guy Steele, Gilad Bracha — Addison-Wesley Professional, 2005.

35. A theory of data race detection / Utpal Banerjee, Brian Bliss, Zhiqiang Ma, Paul Petersen // PADTAD '06: Proceedings of the 2006 workshop on Parallel and distributed systems: testing and debugging — New York, NY, USA, 2006 - P. 69-78.

36. Boehm Hans-J. How to miscompile programs with "benign" data races

// Proceedings of the 3rd USENIX conference on Hot topic in parallelism / USENIX Association - 2011 - P. 3-3.

37. Netzer Robert H. B. Race condition detection for debugging shared-memory parallel programs: Ph. D. thesis / Robert H. B. Netzer — University of Wisconsin — 1991.

38. Engler Dawson, Ashcraft Ken. RacerX: effective, static detection of race conditions and deadlocks // SIGOPS Operating System Review — 2003 — V. 37, no. 5 - P. 237-252.

39. Automatically classifying benign and harmful data races using replay analysis / Satish Narayanasamy, Zhenghao Wang, Jordan Tigani et al.

// Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation — PLDI '07 — New York, NY, USA: ACM, 2007 - P. 22-31.

40. Eraser: a dynamic data race detector for multithreaded programs /

Stefan Savage, Michael Burrows, Greg Nelson et al. // ACM Transactions on Computer Systems — 1997 - V. 15, no. 4 - P. 391-411.

41. Lamport Leslie. Time, clocks, and the ordering of events in a distributed system // Communications of the ACM - 1978 - V. 21, no. 7 - P. 558-565.

42. Flanagan Cormac, Freund Stephen N. Fast Track: efficient and precise dynamic race detection // SIGPLAN Notices - 2009 - V. 44, no. 6 - P. 121-133.

43. Unraveling Data Race Detection in the Intel® Thread Checker / U. Banerjee, B. Bliss, Z. Ma, P. Petersen // First Workshop on Software Tools for Multi-core Systems (STMCS), in conjunction with IEEE/ACM International Symposium on Code Generation and Optimization (CGO), March — V. 26 — 2006.

44. O'Callahan Robert, Choi Jong-Deok. Hybrid dynamic data race detection // PPoPP '03: Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming — New York, NY, USA: ACM, 2003 - P. 167-178.

45. Sun Thread Analyzer // Sun Studio —

URL: http://developers.sun.com/sunstudio (дата обращения: 1.09.2010).

46. Pozniansky Eli, Schuster Assaf. Efficient on-the-fly data race detection in multithreaded С++ programs // PPoPP '03: Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming — New York, NY, USA: ACM, 2003 - P. 179-190.

47. Helgrind: a thread error detector // Valgrind Documentation — URL: http://valgrind.org/docs/manual/hg-manual.html (дата обращения: 1.08.2013).

48. Beck Kent. Test-Driven Development by Example — Addison-Wesley Professional, 2002.

49. DRD: a thread error detector // Valgrind Documentation — URL: http://www.valgrind.org/docs/manual/drd-manual.html (дата обращения: 1.08.2013).

50. Garcia Felix, Fernandez Javier. POSIX thread libraries // Linux Journal — 2000 - no. 70 - P. 36.

51. data-race-test — Race detection tools and more —

URL: http://c0de.g00gle.c0m/p/data-race-test (дата обращения: 1.08.2013).

52. Chromium // The Chromium Projects —

URL: http://dev.chromium.org/Home (дата обращения: 1.08.2013).

53. Zalewski Michal. cross_fuzz — URL: http://lcamtuf.coredump.cx/cross_fuzz/ (дата обращения: 1.08.2013).

54. Hipp D. R., et al. SQLite — URL: http://www.sqlite.org/ (дата обращения: 1.08.2013).

55. TCMalloc: Thread-Caching Malloc // Google Performance Tools —

URL: http://google-perftools.googlecode.com/svn/trunk/doc/tcmalloc.html (дата обращения: 1.08.2013).

56. Bernât Andrew R., Miller Barton P. Anywhere, any-time binary instrumentation // Proceedings of the 10th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools — PASTE '11 — New York, NY, USA: ACM, 2011 - P. 9-16.

57. Bruening Derek, Kiriansky Vladimir. Process-shared and persistent code caches // Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments — VEE '08 — New York, NY, USA: ACM, 2008 - P. 61-70.

58. SPEC CPU2006 benchmark suite // Standard Performance Evaluation Corporation — http://www.spec.org/cpu2006/.

59. Iskhodzhanov Timur, Kleckner Reid, Stepanov Evgeny. Combining compile-time and run-time instrumentation for testing tools // Programmnye produkty i sistemy - 2013 - no. 3 (103) - P. 224-231.

60. bzip2 and libbzip2 — URL: http://bzip.org/ (дата обращения: 1.08.2013).

61. WebKit, an open source web browser engine // The WebKit Open Source Project — URL: http://www.webkit.org/ (дата обращения: 1.08.2013).

62. BuildBot - URL: http://buildbot.net/ (дата обращения: 1.08.2013).

63. Tree Sheriffs // The Chromium Projects —

URL: http://dev.chromium.org/developers/tree-sheriffs (дата обращения: 1.08.2013).

64. Bruening Derek, Zhao Qin. Practical memory checking with Dr. Memory

// Proceedings of the 9th Annual IEEE/ACM International Symposium on Code Generation and Optimization — CGO '11 — Washington, DC, USA, 2011 - P. 213-223.

65. Google Heap Leak Checker // Google Performance Tools — URL: http://google-

perftools.googlecode.com / svn / trunk/doc/heap_checker.html (дата обращения: 1.08.2013).

66. Chandler Carruth. A path forward for an LLVM toolchain on Windows // LLVM Project Blog -

URL: http://blog.llvm.org/2013/09/a-path-forward-for-llvm-toolchain-on.html (дата обращения: 6.09.2013).

67. Meyers S., Alexandrescu A. С++ and the Perils of Double-Checked Locking // Doctor Dobbs Journal — 2004.