Введение 5
1 Постановка задачи 9
1.1 Проблемы поиска состояний гонки 9
1.2 Задача 11
1.3 Требования 11
2 Обзор литературы 12
2.1 Алгоритмы 12
2.2 Современные проекты 13
2.3 Семантика операционных систем 14
3 Разработка программного продукта 15
3.1 Технические аспекты 15
3.1.1 Выбор языка программирования 15
3.1.2 Выбор среды разработки 16
3.1.3 Выбор системы контроля версий 16
3.2 Препроцессинг исходного кода 17
3.2.1 Оператор #if 18
3.3 Парсинг кода и составление синтаксического дерева 19
3.3.1 Выбор парсера 19
3.3.2 Совместимость C и C# 20
3.3.3 Архитектура Roslyn 22
3.4 Связь препроцессора и парсера 22
3.4.1 Простые макросы 23
3.4.2 Макросы — вариативные функции 24
3.4.3 Операторы Stringification и Token-Pasting 24
3.4.4 Общие корректировки 25
3.4.5 Платформо-зависимые корректировки 25
3.5 Семантический анализ 26
3.5.1 Основные семантические понятия 26
3.5.2 Алгебра диапазонов значений 28
3.5.3 Обходчик дерева 30
3.5.4 Ресурсный обходчик 31
3.5.5 Механизм “обещаний” 32
3.6 Анализ кода на состояния гонки 33
3.6.1 Семантика системных вызовов 33
3.6.2 Контексты пользовательских функций 36
3.6.3 Блокировки 37
3.6.4 Пересечение Lockset 39
3.6.5 Фрагментация исходного кода 41
3.6.6 Цепочки фрагментов 45
3.6.7 “Накачка” цепочек фрагментов 46
3.6.8 Анализ псевдонимов 47
3.6.9 Анализ на состояния гонки 50
3.7 Пользовательский интерфейс 51
3.7.1 Выбор SDK 51
3.7.2 Архитектура решения 52
3.8 Облачный сервис Azure 53
3.8.1 Архитектура WorkerRole 54
3.8.2 Архитектура WebRole 54
3.8.3 Настройка Azure 55
3.8.4 Производительность 55
3.8.5 Ограничения и перспективы проекта 55
3.9 Тестирование 56
3.9.1 Препроцессор 56
3.9.2 Парсинг 57
3.9.3 Различные виды анализа 57
3.9.4 Реальное тестирование 57
3.9.5 Сравнение с другими проектами 58
4 Выводы 59
4.1 Возможные улучшения 60
5 Заключение 61
Список литературы 62
Приложение 67
1 Stringification Operator 67
2 Вставка пустых строк 68
3 SyntaxRunner 69
4 Пересечение Lockset 72
5 Внешний вид пользовательского интерфейса 74
6 Отправка задачи в WorkerRole 74
Купить

Компьютерные технологии определяют вектор развития науки и техники. Программы для компьютеров — неотъемлемая их часть. В то время, когда сложность разработки прикладного ПО всё время падает вследствие повышения уровня абстракции и применения специализированных языков программирования, сложность же системного ПО для поддержки всего “парка” техники неминуемо возрастает. Это происходит из-за увеличения числа поддерживаемого аппаратного обеспечения, аппаратных архитектур и постоянно изменяющихся потребностей разработчиков.
Описываемые проблемы выражаются в нескольких аспектах: рост фактической сложности кода (измеряемой, например, методом Т.Дж.Маккейба [1]), разветвление кода для поддержки “необычного” железа, увеличение числа пользователей отдельных функций. Соответственно, происходит ухудшение качества программного продукта и снижение надежности системы.
Одним из важных достижений компьютерных технологий является параллелизм — возможность решать несколько задач одновременно — причем как в рамках одной программы, так и в пределах ОС и компьютера в целом. Такое логичное и правильное изобретение, однако, вносит свою лепту в описанный выше процесс.
Если открыть официальный сайт Linux, а именно журнал изменений за последние года, можно убедиться, что каждый год решаются тысячи проблем параллелизма [2]. В частности, следует упомянуть состояния гонки (race conditions).
Определение. Состояние гонки — это ошибка проектирования программы, при существовании которой корректность кода зависит от порядка выполнения его участков.
Сложность в том, что эта проблема является плавающей, т.е. она может возникать в абсолютно случайные моменты времени, не проявляясь во время тестирования или проявляясь незаметно для тестировщика. Более того, зачастую ошибка накапливается, и заказчики сталкиваются с тем, что сертифицированная и много раз проверенная программа становится нестабильной.
Задача выявления состояний гонки выглядит ещё более непростой на фоне того разнообразия средств межпроцессного и межпотокового взаимодействия, которые предоставляют современные операционные системы. К примеру, в Linux для одной лишь блокировки использования переменных в разных потоках служит более трех базовых примитивов (spinlock, rwlock, semaphore). Часто в системном ПО выключают обработку прерываний, что на некоторых системах полностью блокирует системный планировщик задач. Также существуют различные варианты атомарных функций, которые по определению обеспечивают атомарность, но в сочетании с другими инструкциями вполне могут вызывать тяжело диагностируемые логические ошибки. На вопрос, как всё это многообразие будет между собой взаимодействовать, зачастую не может ответить даже опытный человек.
Всё, что способен определить “на глаз” человек, вполне реализуемо в рамках программного продукта. Однако это не так просто. Достаточно проблематично систематизировать все возможные ошибки, приводящие к состояниям гонки. Более того, семантика используемых функций серьезно зависит от операционной системы и может отличаться даже в сравнении с достаточно близкими версиями одного ядра.
Перед реализацией любой подобной системы необходимо чётко определить требуемый баланс между качеством и скоростью. Нахождение ошибок параллельности является NP-сложной задачей [3] и потому эффективный алгоритм определить достаточно сложно. Можно проверить весь код до малейших деталей, но при этом обнаружить, что на полную проверку программы уйдёт время, сравнимое с временем жизни Вселенной. А можно запустить пере оптимизированный код и понять, что не самый тривиальный ошибочный случай просто останется необнаруженным, и тогда встанет вопрос, есть ли вообще смысл от такого анализа.
Иногда в среде начинающих программистов можно заметить пренебрежение в отношении подобных проблем. Казалось бы, проблема возникает настолько редко, что замечается в одном случае на миллион. И одним из аргументов подобных авторов является производительность, которая при отсутствии блокировок будет действительно выше, чем в ином случае [4]. С этим сложно поспорить, но если, например, незначительная ошибка при выведении графического объекта в одном кадре в час будет едва ли заметна, то вряд ли гипотетический пациент обрадуется малозаметной ошибке в работе медицинского прибора, которая, в каких-то случаях, может стоить ему жизни [5].
На эти доводы можно возразить: ведь не только состояния гонки приносят проблемы. И это верно. Но гонки особенно коварны — их незаметность и зависимость от внешних факторов заставляют быть особенно внимательными при проектировании систем. Изменения “железной” части программно-аппаратного продукта могут привести к задержкам при обработке, и проблема в некорректно написанном коде встанет в полный рост. Увеличит пользователь нагрузку на дисковую подсистему — и все принятые в программе предположения (assumptions) о времени обработки IO-операции окажутся неверными. Примеры можно приводить бесконечно.
В случае с гонками язык программирования как таковой роли не играет: они могут присутствовать во всех программах, язык которых не предполагает строгости формализации параллельного выполнения. Чистый C, рассматриваемый в данной работе, далеко не в первых рядах по популярности [6], но всё же стоит отметить, что большинство инфраструктурных open-source проектов написаны на C. Под термином “инфраструктурные проекты” здесь скрывается системное и, зачастую, свободное программное обеспечение, которое обеспечивает функционирование различных подсистем: маршрутизация, DNS, NTP, VPN, криптография, и т.д. Подобное ПО активно используется на серверах, во встраиваемых устройствах, на смартфонах, планшетах, иногда в автомобилях, уж не говоря о клиентских компьютерах, внедрение непроприетарного ПО в которые является одной из важных задач образовательного и государственного секторов многих стран мира.
Часто в новостных сводках можно услышать про “очередную найденную уязвимость в проекте Х”. И, между тем, весомый процент уязвимостей в системах безопасности — в тех самых базовых программах. К примеру, весьма простая ошибка обработки Heartbeat-запросов в OpenSSL привела к возможности раскрытия пользовательской информации на более чем 17% веб-серверов в мире (уязвимость Heartbleed). И хотя подобные ошибки не являются предметом рассмотрения, упомянутое “коварство” гонок позволяет предположить наличие сотен не менее значительных проблем в компьютерах на базе свободного ПО.
Существует множество программных продуктов, реализующих поиск ошибок в исходных кодах других программ. Они различаются по принципам работы: обычно за основу берутся методы статического или динамического анализа.
Динамический анализ основывается на внедрении сбора статистики в программу на этапе её компиляции. Естественными требованиями является необходимость модификации компиляторов (или установки “ловушек” в существующие), а также в целом возможность компиляции исходного кода. Если первый процесс является достаточно трудозатратным, то второе требование не всегда допустимо. Например, если возникает необходимость проверки лишь небольшого участка кода, то потребуется скомпилировать весь проект. Более того, помимо временных затрат на сборку, результат может оказаться не вполне ожидаемым. Ведь добавленные процедуры сбора статистики увеличивают время выполнения программы, тем самым уменьшая вероятность обнаружения гонки. Ну и наиболее важным недостатком является отсутствие полноценных проверок редко вызываемых частей программ.
Статический анализ лишен подобных проблем, но имеет свои собственные. В то время как динамический анализатор встраивается в уже рабочую программу, и его инструкции выполняются напрямую процессором, статический вариант анализатора вынужден сам быть некоторого рода интерпретатором. Это даёт большую гибкость, но значительно увеличивает сложность разработки. К примеру, банальное определение справедливости условий перехода по инструкции if уже не представляется такой тривиальной задачей [8].
Подводя итог вышеизложенному, можно сделать вывод, что работа в направлении статического анализа на состояния гонки в программах на языке C является перспективной задачей. Теоретически, такой проект способен выполнять точную, полную и достаточно быструю проверку на подобный тип ошибок. И что особенно ценно, исправление найденных таким проектом ошибок позволит улучшить стабильность и надежность практически любого компьютера на основе Linux.
В рамках данной квалификационной работы будет разработан подобный статический анализатор кода на С.

Купить