Game-theoretic approach to testing compilers for the presence of undeclared capabilities of implementation mechanisms

В настоящее время идет процесс стремительного развития информационных технологий, который влечет за собой увеличение сложности программного обеспечения (ПО), используемого в автоматизированных системах различного назначения ^{[1, 2]}. Увеличение сложности ПО ведет к росту в нем числа ошибок проектирования или разработки и вероятных недекларированных возможностей (НДВ) ^[3-5].

Для потребителя ПО необходимо получить некоторую гарантию в безопасности приобретенных продуктов. К основным мероприятиям по оценке безопасности программного обеспечения относят обязательную сертификацию по требованиям безопасности информации ^[6]. Однако возможности сертификации ограничены как временными рамками, так и нормативно-правовыми и конструкторскими требованиями. Кроме того, сертификация программного обеспечения по требованиям безопасности должна производиться на соответствие Руководящего документа ^[7], в котором используются, как показала практика, неэффективные методы выявления НДВ. Еще одним существенным требованием, накладываемым Руководящим документом, является наличие исходных кодов на исследуемое ПО. Это требование весьма критично для разработчиков, т.к. образуется потенциальный канал утечки интеллектуальной собственности, что объясняет, почему зарубежные производители нечасто проводят сертификацию своих продуктов в РФ ^[8-11].

Использование ПО в сферах деятельности человека, в которых цена ошибки проектирования или разработки играет огромную роль предполагает, что оно должно проходить проверки на информационную безопасность. ПО, не прошедшее проверки в установленном порядке, представляет угрозу как для жизни и здоровья, так и для материальных ценностей. Это особенно актуально в автоматизированных системах, определенных в ^[12] как автоматизированные системы управления производственными и технологическими процессами на критически важных объектах, потенциально опасных объектах, а также объектах, представляющих повышенную опасность для жизни и здоровья людей и для окружающей природной среды.

Принимая во внимание эти факторы, становится очевидным, что любой сбой, вызванный ошибками или НДВ, в работе столь сложных организационно-технических систем может привести к катастрофическим последствиям ^[13-15].

Как уже говорилось, в настоящее время основным регламентированным инструментом подтверждения безопасности ПО, на территории РФ, является процедура сертификации на наличие НДВ ^[7].

Одним из основных органов, контролирующим процедуру сертификации, является Федеральная служба по техническому и экспортному контролю Российской Федерации (ФСТЭК России). Испытания проводятся в аккредитованных ФСТЭК России испытательных лабораториях (ИЛ). ИЛ выполняют всю основную работу по поиску НДВ. После того, как ИЛ закончит испытания ПО, результаты испытаний направляются в орган по сертификации, который проверяет корректность испытаний и выводы. Проверив результаты работы ИЛ, орган по сертификации отправляет отчет во ФСТЭК России, который выдает сертификат соответствия, подтверждающий отсутствие НДВ по определенному классу требований в соответствии с ^[7].

Проанализируем существующие методы анализа программ на наличие/отсутствие НДВ. Применяемые в настоящее время экспертами ИЛ методы проверки соответствия ПО требованиям Руководящего документа ^[7] в целом позволяют решить проблемы выявления НДВ. Однако, подходы к сертификационных испытаний обладают существенным недостатком - высокой трудоемкостью и недостаточной автоматизацией работы экспертов ^[14-19].

В соответствии с ^[7] основными испытаниями, которые проводятся испытательными лабораториями являются статический и динамический анализ исходных текстов программ. В зависимости от уровня секретности информации, обрабатываемой с использованием данного ПО, выделены 4 уровня контроля недекларированных возможностей, каждый из которых характеризуется различными минимальными требованиями к испытаниям, проводимым ИЛ ^[16-19].

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

Существуют две основные стратегии тестирования программного обеспечения ^{[17, 20]}:

структурная стратегия;

поведенческая стратегия.

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

К основным методам структурного тестирования ^[21] относят:

статическое тестирование:

модульное тестирование;

интеграционное тестирование;

сигнатурное тестирование;

системное тестирование

динамическое тестирование:

трассировочное тестирование.

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

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

К основным методам поведенческого тестирования ^[21] относят:

тестирование функционала на соответствие эксплуатационным документам;

стрессовое и нагрузочное тестирование;

тестирование граничных значений входных параметров;

тестирование производительности ПО;

тестирование совместимости с другим ПО;

рандомизированное тестирование;

тестирование работы с окружением;

тестирование подсистем безопасности.

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

Для объединения достоинств описанных ранее стратегий предлагается следующая методика тестирования компиляторов на отсутствие механизмов внедрения НДВ на этапе компиляции ПО (рис. 1).

Рисунок 1. Схема разработанной методики тестирования компиляторов.

Методика тестирования компиляторов состоит из следующих основных этапов:

1. Формирование списка закладок и программных тестов.
2. Формирование модели выявления закладок и оптимального набора тестов.
3. Компиляция исходных текстов тестов.
4. Представление исходного текста и объектного кода теста в виде графа.
5. Сравнение графов и определение факта внедрения программной закладки.

Для формирования списка закладок и программных тестов предлагается следующий подход.

В настоящее время существуют следующие международные стандарты для языков программирования C/C++: ANSI/ISO 9899-1990, ISO/IEC 9899:1999 и ISO/IEC 14882:1998.

Тесты разделяются на типы в зависимости от ожидаемого правильного результата теста:

- тесты, которые должны завершиться успешно, т.е. с нулевым кодом возврата;

- тесты, которые должны завершиться с ненулевым кодом возврата;

- тесты, которые должны давать не фатальную ошибку времени исполнения;

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

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

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

Для решения этого вопроса используется алгоритм проверки соответствия структуры скомпилированных тестов с их исходными текстами. Алгоритм приведен на рисунке 2.

Рисунок 2. Алгоритм сравнения структуры исходных текстов и объектного кода.

Для сравнения структуры можно использовать два метода тестирования «черного ящика» тестирование потока управления и тестирование потока данных ^[14].

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

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

Внедрение НДВ влечет за собой изменение структуры текста как на уровне потока управления, так и на уровне данных, поэтому на этапе сравнения данных необходимо использовать модель тестирования потока управления и данных.

Для этого строятся графы потока управления и данных исходного текста, а также графы потока управления и данных объектного кода после исследуемого компилятора.

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

Пример графа потока управления до и после внедрения программной закладки представлен на рис. 3.

Рисунок 3. Слева - пример графа потока управления до внедрения НДВ, справа - пример графа потока управления, построенный по объектному коду исследуемого компилятора, после внедрения программной закладки (пунктирными линиями показан объект НДВ и его вызовы).

На основании сведений, полученных выше, формируем следующие этапы методики тестирования компилятора:

1. Формируются тестовые данные для тестирования исследуемого компилятора.
2. Эти данные подаются на вход исследуемому компилятору.
3. По полученным данным на выходе компилятора строится граф потока управления и данных.
4. Строится граф потока управления и данных по исходным текстам теста.
5. Сравнение графов потоков управления, полученных в п. 3 и 4.
6. Анализ результатов сравнения.

Формировать наборы тестов для исследования компиляторов предлагается на основе теоретико-игрового подхода, например, при условии конечности множеств закладок и тестов, процесс тестирования компилятора можно классифицировать как конечную игру двух лиц с нулевой суммой ^[8].

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