ПРОГРАММИРОВАНИЕ, 2013, No 1, с. 73-81
ТЕСТИРОВАНИЕ, ВЕРИФИКАЦИЯ И ВАЛИДАЦИЯ ПРОГРАММ
У л :
МЕТОДЫ БЫСТРОГО АНАЛИЗА ИСХОДНОГО КОДА НА
ЯЗЫКАХ C/C++
© 2013 г. В.О. Савицкий, Д.В. Сидоров
Институт Системного Программирования РАН 109004 Москва, ул. А. Солженицына, 25 E-mail: ssavitsky@ispras.ru, sidorov@ispras.ru Поступила в редакцию 10.09.2012
Статический анализ — популярный инструмент обнаружения уязвимостей, не выявляемых обычным тестированием. Основной проблемой при разработке статических анализаторов является быстродействие. В статье описаны методы ускорения работы такого анализатора: инкрементальный анализ, ленивый анализ и кэширование заголовочных файлов. Эти методы позволяют существенно ускорить поиск дефектов и делают возможным интеграцию статического анализа в среду разработки. Результатом является обнаружение дефектов на файле, редактируемом в Visual Studio, за время не более 0.5с, то есть практически на каждое нажатие клавиши. Это позволяет обнаруживать и исправлять критические уязвимости еще на стадии написания исходного кода.
1. ВВЕДЕНИЕ
Одной из наиболее распространенных проблем, возникающих в процессе разработки программного обеспечения, является проблема недостаточной надежности. На завершающих стадиях разработки - отладке и тестировании -ПО проверяется на соответствие спецификации. Однако существующие методы тестирования не позволяют выявить все имеющиеся дефекты. Поэтому для проектов, для которых отсутствие уязвимостей является критически важным фактором, применяются дополнительные методы обнаружения дефектов. Одним из таких средств является статический анализ.
Статический анализ - метод поиска определенных классов ситуаций или шаблонов, которые могут означать наличие уязвимости, в исходном коде программы [1]. Эти классы включают утечки памяти, разыменование нулевого указателя, переполнение буфера и ошибки кроссплатформенности. Простейшим примером такой ситуации является предупреждение компилятора о неинициализированной переменной. Однако, поиск таких сложных дефектов как разыменование нулевого указателя, не может
осуществляться компилятором из-за накладываемых требований быстродействия. Поэтому статический анализ обычно реализуется как отдельный инструмент.
Результатом работы первого компонента статического анализатора является дерево абстрактного синтаксиса с атрибутами. Поиск простейших дефектов можно осуществлять уже на этой стадии. Для удобного описания шаблонов, которые должны быть помечены как дефекты, можно воспользоваться языком К AST [2]. Этот язык используется в компонентах статического анализатора Klocwork Insight [3]. Более сложные дефекты ищутся по графу потока выполнения после преобразования дерева. Так как вариантов путей потока управления много, то эта стадия анализа занимает больше времени, а полное время анализа проектов объемом миллионы строк кода достигает нескольких часов. Поэтому статический анализ обычно выполняется на мощной серверной машине для всего проекта раз в сутки. Это приводит к тому, что на обнаружение и, что более важно, исправление даже простых программных дефектов будет потрачено неоправданно много времени.
Если программист заметит предупреждение о реальной ошибке при компиляции программы, то исправить ее не составит труда. Сложнее предоставить решение, если ошибку обнаружил пользователь, который приобретает готовый продукт. Еще труднее диагностировать и исправить ошибку, если программа установлена во встраиваемой системе. Таким образом, «цена» программного дефекта растёт очень быстро в зависимости от времени, прошедшего от внесения до обнаружения ошибки. То есть, чем раньше обнаружен дефект, тем проще его исправить.
В результате исключительное значение приобретает оптимизация статического анализа по времени работы. Обычно при анализе проекта время разбора исходного кода - стадий препроцессора, парсера и семантического анализа -сравнимо со временем непосредственного поиска дефектов. Для проектов на С и С++ это время можно существенно сократить за счет сохранения результатов анализа заголовочных файлов для последующего использования.
Обычно структура каждого исходного файла такова: в начале записаны директивы препроцессора для подключения заголовочных файлов, затем следуют определения, относящиеся непосредственно к этому файлу. Ниже показан пример такого файла.
#include <windows.h> #include <iostream> #include <user_types.h>
typedef unsigned int boxes;
В подключаемые файлы обычно выносятся декларации и определения, которые могут использоваться во многих файлах. Каждый файл может использовать лишь небольшое количество определений из заголовочного файла, но вынужден подключать его целиком. Кроме того, одни и те же заголовки анализируются много раз. В результате время компиляции файла и всего проекта неоправданно увеличивается. Если сохранить результаты работы препроцессора, парсера и семантического анализа, и использовать их в дальнейшей работе анализатора, то общее время обработки одного исходного файла можно сократить. Рассмотрим далее три метода, основанные
на данном наблюдении. Метод инкрементального анализа предполагает сохранение контекста для многократного анализа разных версий одного и того же файла. Это позволяет ускорить повторный анализ файла при его редактировании, предоставляя результаты анализа за время менее секунды, то есть по мере ввода текста пользователем. Метод ленивого анализа основан на откладывании анализа неиспользуемых объектов из заголовочных файлов. Наконец, метод кэширования заголовочных файлов предполагает сохранение трасс построенных семантических элементов для воспроизведения их при анализе исходных файлов. Опишем эти методы подробнее.
2. ИНКРЕМЕНТАЛЬНЫЙ АНАЛИЗ
Как правило, программист просматривает результаты статического анализа через какой-либо интерфейс, затем вносит исправления и на следующий день снова проверяет результаты. В таком режиме дефекты могут попасть, например, в ночную сборку, которая будет использоваться тестировщиками. Кроме того, на следующий день программист может уже переключиться на другую задачу, и ему придется потратить время на то, чтобы вернуться ко вчерашней задаче. Очевидно, большой интерес представляет возможность сокращения времени этого цикла. Так, если дефекты будут отображаться по мере ввода и редактирования текста программы, то время, затраченное на исправление, будет минимально. Инкрементальный анализ делает это возможным.
Когда программист изменяет исходный код, необходимо заново построить синтаксическое дерево, выполнить на нем анализ и сравнить новый список дефектов со старым. Для того, чтобы быстро построить новое дерево разбора, можно строить его инкрементально, то есть используя результаты предыдущих запусков анализа. Анализ нескольких проектов с открытым кодом показывает, что более 90% символов, обрабатываемых компилятором, приходят из заголовочных файлов.
Естественное решение в таком случае обрабатывать общие заголовочные файлы лишь однажды. Такая технология получила название
Рис. 1.
Соотношение количества лексем в заголовочных и исходных файлах.
„предварительно откомпилированные заголовки". Например, в варианте, реализованном в компиляторе MS Visual Studio [4], для ßcei'o проекта или ei'o части создается один общий заголовочный файл, в который подключаются все заголовочные файлы, которые мемут использоваться в разных исходных файлах проекта. Затем директивы подключения зах'оловков в каждом файле заменяются одной директивой подключения этхих) общмх) зах'оловочнохх) файла.
Компилятору сначала передается команда создания предварительно откомпилировавших) заголовка. В результате компилятор создает файл, в который записывает таблицу макросов препроцессора, таблицу найденных идентификаторов, и другие данные, необходимые для поеледующмх) разбора файлов. При дальнейшей сборке проекта, компилятор тратит время только на загрузку сохраненной информации. Это существенно сокращает время анализа каждохх) отдельжих) файла. Несколько иной подход используется в компиляторе gee [5]. gee позволяет скомпилировать заголовочный файл как обычный файл проекта, при этом будет создан файл с расширением .geh в директории, в которой находится заголовок. Затем во время обработки директив подключения зах'оловков компилятор сначала ищет соответствующий .geh файл и использует сх'о, если это возможно. Возможен и другой способ часто используемые зах'оловки собираются в один. Этот зах'оловок компилируется и подключается к файлам проекта при помощи оп-
ции include. Если в заголовочных файлах присутствует защита подключения (include guard), то зах'оловки из общмх) файла не будут обрабатываться повторно. Метод компилятора gee предпочтительнее метода, иснользуемохх) компилятором MS Visual Studio, поскольку не требует вносить изменения в исходный код проекта.
3. АНАЛИЗ НА „ЛЕТУ "
Технику предварительно откомпилированных зах'оловков можно обобщить на случай оджих) файла, анализируемохх) mhoixj раз. Для каждого открываемся^ в среде разработки файла анализатор будет создавать кэш следующих) вида. Анализатор обрабатывает входную последовательность символов, отслеживая момент появления первой лексемы непосредственно из текста файла. В следующем фрагменте это место отмечено пунктирной линией.
#include <stdio.h> #include <stdlib.h>
typedef char number; #include <inlined.h>
Заметим, что в данном примере последний за!х).ловок не попадет в кэш, так как директива eix) подключения находится после первой лексемы из исходного файла, но это редко встречающаяся ситуация. В момент обнаружения такой лексемы в памяти сохраняется "
Рис. 2.
Структура использования предварительно откомпилированных заголовков.
моменту. В него включены таблица символов препроцессора, таблица символов пареера, необходимые семантические элементы, а также состояние области видимости идентификаторов. Также сохраняется состояние работы компонентов анализатора, которым для обнаружения дефекта нужна информация о файле целиком. Затем анализируется оставшаяся часть файла. После того как пользователь изменяет исходный файл, с некоторой зад
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.