Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Cybernetics and programming
Reference:

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

Mironov Sergei Vladimirovich

Deputy Director, Department of Information Technology in the Management of Public and Municipal Finance and Information Support of the Budgetary Process, the Ministry of Finance of the Russian Federation

109097, Russia, Moscow, ul. Il'inka, 9

gniiivm-m@yandex.ru
Other publications by this author
 

 

DOI:

10.7256/2306-4196.2017.1.20351

Received:

10-09-2016


Published:

22-03-2017


Abstract: The subject of research is mathematical software software certification procedures for information security requirements in view of time constraints, regulatory and design requirements. This essential requirement is the availability of the source code on the test software, which is quite critical for developers as a potential channel formed intellectual property leakage. To overcome this drawback, the technique of testing the compilers on the lack of mechanisms for the implementation of undeclared capabilities to stage software compilation. The research methodology combines the methods of software engineering, theory of possibilities of object-oriented programming, systems analysis, the theory of reliability. The main conclusion of the study is that by forming an optimal set of tests using the mathematical apparatus of the theory of games, spending his compiling and analyzing the control flow graphs and data obtained from the compiler output and built according to the original texts of the tests, we can conclude the presence or absence in the test compiler mechanisms introduction of undeclared capabilities in the compiled software.


Keywords:

software, software certification, compilers testing, introduction of undeclared capabilities, software compilation, software engineering, information security, software security, program analysis, certification testing programs


Введение

В настоящее время идет процесс стремительного развития информационных технологий, который влечет за собой увеличение сложности программного обеспечения (ПО), используемого в автоматизированных системах различного назначения [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_06

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

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

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

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

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

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

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

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

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

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

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

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

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

2_02

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

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

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

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

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

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

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

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

3_02

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

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

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

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

Заключение

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

References
1. Butusov I.V., Nashchekin P.A., Romanov A.A. Teoretiko-semanticheskie aspekty organizatsii kompleksnoi sistemy zashchity informatsionnykh sistem // Voprosy kiberbezopasnosti. 2016. № 1 (14). S. 9-16.
2. Fedorov M.V., Kalinin K.M., Bogomolov A.V., Stetsyuk A.N. Matematicheskaya model' avtomatizirovannogo kontrolya vypolneniya meropriyatii v organakh voennogo upravleniya // Informatsionno-izmeritel'nye i upravlyayushchie sistemy. 2011. T. 9. № 5. S. 46-54.
3. Bogomolov A.V., Chuikov D.S., Zaporozhskii Yu.A. Sredstva obespecheniya bezopasnosti informatsii v sovremennykh avtomatizirovannykh sistemakh // Informatsionnye tekhnologii. 2003. № 1. S. 2.
4. Golosovskii M.S. Model' otsenivaniya pogreshnostei prognozirovaniya srokov razrabotki programmnogo obespecheniya // Programmnye sistemy i vychislitel'nye metody. 2015. № 3. S. 311-322.
5. Borodakii Yu.V., Kulikov G.V., Nepomnyashchikh A.V. Metodika otsenivaniya funktsional'nykh vozmozhnostei sistem obnaruzheniya vtorzhenii na osnove ranzhirovaniya stepeni opasnosti atak // Izvestiya YuFU. Tekhnicheskie nauki. 2006. № 7 (62). S. 77-82.
6. Kotenko I.V., Kotukhov M.M., Markov A.S. Zakonodatel'no-pravovoe i organizatsionno-tekhnicheskoe obespechenie informatsionnoi bezopasnosti AS i IVS. SPb: VUS, 2000. 190 s.
7. Rukovodyashchii dokument Gostekhkomissii Rossii «Zashchita ot nesanktsionirovannogo dostupa k informatsii. Chast' 1. Programmnoe obespechenie sredstv zashchity informatsii. Klassifikatsiya po urovnyu kontrolya otsutstviya nedeklarirovannykh vozmozhnostei» 1999.
8. Mironov S.V. Testirovanie kompilyatorov na programmnye zakladki // Informatsionnye tekhnologii. 2008. № 8. S. 61-64.
9. Kukushkin Yu.A., Bogomolov A.V., Ushakov I.B. Matematicheskoe obespechenie otsenivaniya sostoyaniya material'nykh sistem // Informatsionnye tekhnologii, №7, 2004 (prilozhenie). 24 s.
10. Borodakii Yu.V., Dobrodeev A.Yu., Bedarev I.K., Kulikov G.V. Intellektual'nye sistemy obespecheniya informatsionnoi bezopasnosti // Voprosy zashchity informatsii. 2007. № 1. S. 50-52.
11. Markov A.S., Mironov S.V., Tsirlov V.L. Vyyavlenie uyazvimostei programmnogo obespecheniya v protsesse sertifikatsii//Informatsionnoe protivodeistvie ugrozam terrorizma. 2006. № 7. S. 177-186.
12. «Ob utverzhdenii Trebovanii k obespecheniyu zashchity informatsii v avtomatizirovannykh sistemakh upravleniya proizvodstvennymi i tekhnologicheskimi protsessami na kriticheski vazhnykh ob''ektakh, potentsial'no opasnykh ob''ektakh, a takzhe ob''ektakh, predstavlyayushchikh povyshennuyu opasnost' dlya zhizni i zdorov'ya lyudei i dlya okruzhayushchei prirodnoi sredy». Prikaz FSTEK Rossii ot 14 marta 2014 g. № 31.
13. Markov A.C., Mironov S.V, Tsirlov B.JI. Vyyavlenie uyazvimostei programmnogo obespecheniya v protsesse sertifikatsii // Informatsionnoe protivodeistvie ugrozam terrorizma, № 7, 2006. S. 177-186.
14. Mironov S.V., Kulikov G.V. Analiz potentsial'nykh vozmozhnostei metodov testirovaniya programmnogo obespecheniya bez ispol'zovaniya iskhodnykh tekstov // Programmnye sistemy i vychislitel'nye metody. 2015. № 2. S. 150-162.
15. Golosovskii M.S. Informatsionno-logicheskaya model' protsessa razrabotki programmnogo obespecheniya // Programmnye sistemy i vychislitel'nye metody. 2015. № 1. S. 59-68.
16. Zelenov S.V., Zelenova S.A., Kosachev A.S., Petrenko A.K. Generatsiya testov dlya kompilyatorov i drugikh tekstovykh protsessorov // Programmirovanie. 2003. T. 29. № 2. S. 59-69.
17. Kosachev A.S., Posypkin M.A. Obzor metodov testirovaniya kompilyatorov // Programmirovanie. 2005. T. 31. № 1. S. 15-29.
18. Gorlushko D.S. Aspekty primeneniya ob''ektno-orientirovannogo podkhoda v regressionnom testirovanii kompilyatorov // Voprosy radioelektroniki. 2013. T. 4. № 3. S. 96-107.
19. Markov A.S., Mironov S.V., Tsirlov V.L. Vyyavlenie uyazvimostei v programmnom kode // Otkrytye sistemy, №12, 2005. S.64-69.
20. Mironov S.V., Kulikov G.V. Tekhnologii kontrolya bezopasnosti avtomatizirovannykh sistem na osnove strukturnogo i povedencheskogo testirovaniya programmnogo obespecheniya // Kibernetika i programmirovanie. 2015. № 5. S. 158-172.
21. Kotlyarov V.P, Kolikova T.V. Osnovy testirovaniya programmnogo obespecheniya. M.: Internet-Universitet Informatsionnykh tekhnologii, 2006. 285 s