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

48454ЦВ

Леошкевич Илья Олегович

СИСТЕМА ВЫЯВЛЕНИЯ НЕДЕКЛАРИРОВАННЫХ ВОЗМОЖНОСТЕЙ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ, ВЛЕКУЩИХ НАРУШЕНИЕ КОНФИДЕНЦИАЛЬНОСТИ ИНФОРМАЦИИ

Специальность: 05.13.19 - методы и системы защиты информации, информационная безопасность

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Автор:

1 2 МАЙ 2011

Москва - 2011

4845408

Работа выполпепа в Национальном исследовательском ядерном университете «МИФИ».

кандидат физико-математических наук, доцент

Велигура Александр Николаевич

доктор технических наук Конявский Валерий Аркадьевич

кандидат технических наук Тульский Сергей Александрович

Факультет вычислительной математики и кибернетики Московского государственного универсистета имени М.В.Ломоносова

Защита состоится 1 июня 2011 г. в 16 часов 00 минут на заседании диссертационного совета ДМ 212.130.08 при Национальном исследовательском ядерном университете «МИФИ», расположенном по адресу: 115409, г. Москва, Каширское шоссе, д. 31. Тел. для справок: +7 (495) 323-95-26, 324-84-98.

С диссертацией можно ознакомиться в библиотеке Национального исследовательского ядерного университета «МИФИ».,

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

Автореферат разослан * %_<х*урз|У)-А— 2011 г.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

Ученый секретарь диссертационного совета

Горбатов В.'С.

Общая характеристика работы

Актуальность работы. Обеспечение конфиденциальности информации является одной из важнейших задач в сфере информационной безопасности. Действующий стандарт ГОСТ Р ИСО/МЭК 17799-2005 определяет конфиденциальность как "обеспечение доступа к информации только авторизованным пользователям" . Серьёзным источником угрозы конфиденциальности информации является наличие в обрабатывающем её программном обеспечении недекларированных возможностей (НДВ), которые определяются руководящим документом Гостехкомиссии от 4 июня 1999 года как "функциональные возможности программного обеспечения, не описанные или не соответствующие описанным в документации, при использовании которых возможно нарушение конфиденциальности, доступности или целостности обрабатываемой информации".

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

Необходимость выявления НДВ-К обусловлена тем, что во многих современных операционных системах предполагается корректность программ, обрабатывающих конфиденциальную информацию от имени пользователя. Это допущение отсутствует в системах, работающих по модели Белла-Лапа-дула, где выполняется свойство "звезды" - процессы с более высоким уровнем конфиденциальности не могут писать в области с более низким уровнем конфиденциальности. Хотя реализации модели Белла-Лападула для современных операционных систем существуют, зачастую они не используются, в том числе из соображений удобства.

Актуальность разработки новых способов выявления НДВ-К обуславливается тем, что задача выявления НДВ-К, как и любые другие задачи исчерпывающего анализа поведения программного кода, алгоритмически неразрешима. Это следует из результата, полученного Аланом Тьюрингом в 1936 году.

Проблемой выявления НДВ-К в последнее десятилетие занималось множество исследователей, из которых особо можно выделить Nicholas Nethercote

\

(автораутилиты Valgrind), Dawn Song (университет Беркли), Jim Chow (Стэн-фордский университет), и Вартана Падаряна (Институт системного программирования РАН). Ими спроектированы и разработаны средства динамического анализа, позволяющие отслеживать зависимости между обрабатываемыми работающей программой данными, и таким образом позволяющие обнаруживать в ней НДВ-К. Однако, они не позволяют доказать отсутствие НДВ-К, так как с их помощью невозможно исследовать поведение программы при всех возможных входных данных.

Автором данной работы предлагается новая система статического анализа, предназначенная для выявления НДВ-К и работающая на уровне исполняемого кода. Статический анализ предоставляет больше возможностей по рассмотрению всех путей выполнения программы, нежели динамический, а работа на уровне исполняемого кода повышает точность за счёт того, что он является конечным результатом процесса сборки и не подлежит изменениям перед выполнением на ЭВМ конечного пользователя. Применение такой системы позволит существенно ускорить и уменьшить затраты на выявление НДВ-К.

Объектом исследования диссертационной работы является исполняемый код программного обеспечения.

Предметом исследования диссертационной работы являются НДВ, влекущие нарушение конфиденциальности информации.

Целью диссертационной работы является синтез методики выявления НДВ, влекущих нарушение конфиденциальности информации.

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

• анализ существующих методов выявления НДВ, влекущих нарушение конфиденциальности информации;

• анализ существующих методов верификации исполняемого кода;

• синтез архитектуры системы выявления НДВ, влекущих нарушение конфиденциальности информации;

• синтез алгоритма построения формальной модели программного обеспечения по его исполняемому коду;

• реализация системы выявления НДВ, влекущих нарушение конфиденциальности информации.

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

Научная новизна проведенных исследований и полученных в работе результатов заключается в следующем: '

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

• построены два абстрактных домена для представления адресов, позволяющие анализировать низкоуровневые идиомы работы с указателями, основывающиеся на побитовых операциях;

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

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

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

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

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

• построенные численные абстрактные домены: домен выровненных адресов, позволяющий точно учитывать результаты операции выравнивания указателей, и домен битовых полей, позволяющий описывать работу с адресами, в неиспользуемые биты которых помещена дополнительная информация;

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

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

Внедрение результатов работы. Результаты работы используются в.ООО ИБМ Восточная Европа/Азия при разработке программного обеспечения, а также в учебном процессе кафедры №42 "Криптология и дискретная математика" Национального исследовательского ядерного университета «МИФИ».

Публикации и апробация работы. Основные положения диссертации изложены в 8' публикациях, 4 из которых в изданиях, включенных в Перечень ведущих рецензируемых изданий. Результаты работы докладывались и получили одобрения на следующих конференциях:

• XV Всероссийская научная конференция. Проблемы информационной безопасности в системе высшей школы. 2008;

• XVII Всероссийская научная конференция. Проблемы информационной безопасности в системе высшей школы. 2010;

• 12-й Национальный форум информационной безопасности. Информационная безопасность России в условиях глобального информационного общества. 2010;

• VII межрегиональная научно-техническая конференция студентов и аспирантов. Применение кибернетических методов в решении проблем общества XXI века. 2010;

• Научная сессия МИФИ. 2010.

Структура и объем диссертации. Диссертация состоит из введения, обзора литературы, 4 глав, заключения и библиографии из 101 позиции. Общий объем диссертации составляет 154 страницы, включая 19 рисунков и 8 таблиц.

Содержание работы

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

В первой главе определяется рассматриваемый в данной работе тип НДВ - НДВ-К, проводится анализ существующих методов выявления НДВ и анализа исполняемого кода.

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

Задача выявления НДВ-К может быть формализована в терминах абстрактной вычислительной машины, построенной в соответствии с принципами архитектуры фон Неймана.

Зададим машину А как тройку (Мд, 1а, состоящую из множества со^ стояний оперативной памяти, набора инструкций и функции декодирования. Каждый такт работы машины заключается в выполнении одной инструкции из множества Та С (Ма МА)- Функция декодирования dA 6 (МА -¥ 1А) служит для однозначного определения следующуей выполняемой инструкции по содержимому оперативной памяти. Функционирование машины описывается формулой mn+iia = <1а(тпП1а)(гпП1а), где то,л - некоторое начальное состояние. В целях настоящей работы то,л задаётся как 1а{ш*,а), где 1а € (Ма —> МА) - функция загрузки проверяемого программного обеспечения в оперативную память, а т,,л - входные данные.

Назовём политикой обработки информации для машины А четвёрку ра = {CpA,tpA,kpA, M.jpA). СрА - это множество, описывающее конфиденциальность хранящейся в оперативной памяти информации. Теневая память МрА = (МдХ СрА) описывает содержимое оперативной памяти и его конфиденциальность. tpA - это преобразование, дополняющее семантику набора инструкций правилами продвижения меток конфиденциальности: tpA € (Ia 1рл), где 1рА = (МрА МрА). Наконец, крА е (МрА -> Boolean) - функция проверки допустимости состояний теневой памяти, а М»,рд £ МрА - множество начальных состояний. Политика обработки информации ра может быть использована для преобразования машины А в машину Арл, функционирующую по формуле тп+1,рл = £рд(^л(тп,л))(пгп,рА)- С учётом проверяемого программного обеспечения 1а, то,рл = с»,л).

Программа 1а удовлетворяет политике обработки информации Ра, если при выполнении 1д на любых допустимых входных данных не возникнет состояния теневой памяти, отвергаемого функцией допустимости крА: Ут*,РА € М„,Рд,г € N : kpA(m.ifj). Задача выявления НДВ-К состоит в проверке этого условия.

С такой постановкой задачи связаны два ограничения. Во-первых, определённые детали процесса обработки конфиденциальной информации, например, соответствие реализаций криптографических преобразований стандар-

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

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

Автоматизированные средства можно разделить на статические и динамические. Известными динамическими методами выявления НДВ-К являются анализ меток (taint analysis), анализ содержимого оперативной памяти, а также отслеживание системной активности, в частности, работы с диском и сетью.

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

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

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

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

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

Существует ряд систем, реализующих разновидности приведённых выше методов. К динамическим системам анализа исполняемого кода относятся Valgrind, BitBlaze TEMU, TaintBochs, TrEx, EMU и НКВД 2.5. В них имеется функционал для решения поставленной задачи, однако, им присуще принципиальное ограничение динамических средств - отсутствие гарантий полноты; поэтому видится актуальным разработка дополняющего их статического средства. К статическим системам анализа исполняемого кода относятся IDA/HexRays, CodeSurfer/x86, BitBlaze Vine, Jakstab и BoundT. В них отсутствует функционал для решения поставленной задачи, поэтому было принято решение разработать собственную систему анализа, опирающуюся на существующие наработки.

Во второй главе перечисляются связанные с НДВ-К угрозы конфиден-

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

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

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

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

4. Работа с системой может проводиться в несколько итераций - на основании результатов работы аналитик может произвести уточнение политики и повторить проверку.

5. Система должна поддерживать множество архитектур процессоров; добавление поддержки новых архитектур не должно быть связано с принципиальными затруднениями.

6. Система должна работать непосредственно с семантикой машинных команд, а не ориентироваться на их типовые последовательности. Использование знаний о типовых последовательностях допустимо лишь для повышения производительности.

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

Для удовлетворения этих требований была разработана архитектура системы выявления НДВ-К, состоящая из следующих компонентов (рисунок 1):

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

2. Интерфейс к системам компьютерной алгебры. Некоторые фазы анализа оперируют символьными выражениями, точно описывающими работу фрагментов кода. Для поддержания компактности и выявления свойств таких описаний используются сторонние системы компьютерной алгебры. Предусмотрена возможность подключения произвольных систем, имеющих требуемый системой функционал. В реализованном прототипе используются Wolfram Research Mathematica и Parma Polyhedra Library.

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

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

5. Модуль выявления НДВ-К является расширением статического анализатора. Он дополняет создаваемую статическим анализатором формальную модель программы исходя из политики обработки информации, анализирует дополненную модель, и выдаёт заключение о её соответствии политике обработки информации. Используемые при этом абстрактные домены гарантируют отсутствие ошибок второго рода.

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

информации

Рис. 1. Архитектура системы выявления НДВ-К

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

Описания составляются с использованием символьных выражений, включающих в себя около 20 типов операций. Выражения могут содержать обращения к памяти, задаваемые с помощью четырёх значений: адресного пространства, смещения, типа и атрибутов доступа. В качестве примера можно привести выражение UL(32) [$memory : esp * 8 : rpl -> ss_rpl] + 42, обозначающее значение вершины стека архитектуры х86, увеличенное на 42.

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

На рисунке 2 приведён фрагмент описания одной разновидности инструкции not архитектуры х86. Первый элемент - 0xF6 == 8, обозначает, что первые 8 бит инструкции имеют значение 0xF6. Второй элемент отвечает за разбор байта ModR/M с помощью одноимённого правила, у которого есть несколько параметров - имена правил, с помощью которых следует разбирать поля R/0 и R/M, а также имена переменных, в которые следует поместить

результат, op 1 := OxFF - op 1 отвечает за генерацию микроинструкции присваивания, mnemonic = "not" - за помещение в переменную времени разбора с именем mnemonic имени распознанной инструкции, и, наконец, вызов правила Next О - за генерацию микрокоманды увеличения счётчика инструкций. Все именованные сущности: ModRM, С3_2, Byte и т.д., являются частью описания и не встроены в язык.

/* not r/m8: "F6 /2" */ 0xF6 == {8}; ModRM(

HegOpcode -> "C3_2", RegMemory -> "Reg8", type -> Byte, resultl -> temp, result2 -> opl); opl := OxFF - opl; mnemonic = "not"; NextO;

/* Комментарий. */ /* Код операции. */ /* Байт ModR/M. */ /* R/0 = 2. */

/* R/M - либо 8-битный регистр, */ /* либо значение типа "Byte" в памяти. */ /* R/0 сохранять не нужно. */ /* R/M следует занести в переменную opl. */ /* Результат работы: инверсия битов. */ /* Название. */

/* Переход к следующей инструкции.*/

Рис. 2. Инструкция not

Правила представляют собой набор вариантов, а каждый вариант состоит из последовательности элементов: Rule = Var*,Var = Elem*. Перед использованием правила компилируются в графы разбора, для чего проводится объединение всех вариантов внутри каждого правила с помощью модификации алгоритма построения префиксных деревьев. Пример объединения вариантов показан на рисунке 3.

Во время дизассемблирования происходит спуск по дереву разбора. Если с вершиной связана операция проверки соответствия константе размера JV, то из входного потока запрашивается значение размера N и происходит переход по ребру, помеченному полученным значением. Для других видов вершин соответствующее связанному с ними оператору действие - присваивание переменной времени разбора, вызов другого правила или генерация микрокода, а затем осуществляется переход по единственному исходящему ребру. Микропрограмма для инструкции not al, полученная с помощью приведённого выше описания, выглядит следующим образом:

1: al := OxFF - al; 2: eip := eip + 2;

Граф потока управления. Анализируемая программа с помощью дизассемблера преобразуется во внутреннее представление, а затем в граф потока управления, над которым проводится дальнейший анализ. Каждой команде целевого процессора в графе соответствует так называемая большая

Рис. 3. Объединение вариантов

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

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

Рис. 4. Граф потока управления

яний, передаваемых анализатору. В работе используются два вида доменов состояний - основанные на регионах (домен простых состояний) и на алгебре массивов (домен символьных состояний).

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

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

ния. Абстрактной суммой называется пара Ь+х, где Ъ - база, а х - абстрактное целое. Мультисуммой называется множество абстрактных сумм с различными базами. Региональной суммой называется абстрактная сумма, в которой 6 представляет собой регион. Выровненным смещением называется абстрактная сумма, в которой Ь представляет собой тройку —((b + x) mod 2м), де М -целое число, называемое показателем выравнивания. Набором битовых полей называется сумма вида гДе хг~ абстрактные целые, а гц - неотрица-

г

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

' Символьные состояния представляют собой последовательности символьных присваиваний, с которыми связаны два символьных условия: предположение и условие пути. Использование анализатора потоков данных с доменом символьных состояний позволяет получать передаточные функции ациклических участков кода. Для анализа циклов в работе используется алгоритм, основанный на разбиении выполнения цикла на фазы. Для каждой фазы составляются описывающие её рекурсивные уравнения, которые решаются с помощью внешней системы компьютерной алгебры. Результаты последовательного выполнения фаз объединяются, что позволяет получить символьное состояние, описывающее весь цикл.

Политика обработки информации позволяет задавать их источники, структуру и метки конфиденциальности. Структура входных данных задаётся в виде порождающей всевозможные корректные входные данные недетерминированной "входной" микропрограммы. За установку меток конфиденциальности на входные данные отвечают размещаемые во входной микропрограмме операторы taint, принимающие адрес, длину и метку конфиденциальности. Выходные данные обрабатываются детерминированной "выходной" микропрограммой, целью которой является снятие меток конфиденциальности, например, с шифртекста, с помощью оператора untaint. Считается, что программа удовлетворяет политике, если после её завершения или любого вызова выходной микропрограммы меток конфиденциальности не остаётся.

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

стве основных источников имён можно перечислить жёстко закодированные строки, параметры командной строки, конфигурационные файлы (в случае Windows ещё и-реестр) и графический интерфейс; имена одних источников могут получаться из других. Например, в политике могут содержаться утверждения вида "для файла, чьё имя получено из параметра командной строки --key, следует использовать входную микропрограмму с именем Key".

Алгоритм анализа исполняемого кода выполняется в несколько проходов, каждый из которых состоит их фаз.

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

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

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

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

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

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

Модуль обнаружения НДВ-К модифицирует ход выполнения алгоритма анализа в соответствии с переданной ему политикой обработки информации. В частности, он добавляет к фазе дополнения графа потока управления функциональность по подстановке входных и выходных микропрограмм. Кроме того, после завершения построения формальной модели он проводит проверку её соответствия политике, для чего используется продвижение меток. Продвижение меток представляет собой анализ потоков данных с абстрактным доменом, реализованном на основе домена простых состояний и связывающим с каждым диапазоном адресов метки конфиденциальности. Операции в этом домене отражают правила продвижения меток, в частности, taiiit и untaint добавляют или удаляют метку с заданных диапазонов адресов, а при присваивании выражения ехрг ячейке памяти тет метки конфиденциальности, наложенные на mem, заменяются объединением меток конфиденциальности, наложенных на все ячейки памяти, присутствующие в ехрг. Для отслеживания зависимостей по управлению с каждой точкой программы связывается информация о переходах, которыми обусловлено попадание в неё; они могут быть вычислены как её итерированный обратный фронтир доминирования.

В четвёртой главе приводятся примеры применения разработанной системы.

IBM. Система была использована в ООО ИБМ Восточная Европа/Азия для верификации диагностических компонентов базовой контрольной программы операционной системы z/OS, в частности, подсистемы трассировки системных событий. Ошибки в ней могут привести не только к аварийному останову системы, но и выдаче неавторизованному пользователю конфиденциальной информации или предоставлению ему полного контроля над системой.

На основе рекомендаций IBM по созданию безопасного программного обеспечения для z/Architecture был сформирован перечень ошибок, подлежащих автоматизированному поиску. В него входят хранение конфиденциальной информации в "пользовательской" памяти и запись в "пользовательскую" память без понижения текущего уровня привилегий.

Было проанализировано 15 модулей общим объёмом 130 тыс. строк. Были обнаружено 2 ошибки (отражённые в таблице 1), заключающиеся в записи в "пользовательскую" память без понижения уровня привилегий.

Кафедра №42. Система была использована в учебном процессе кафедры №42 "Криптология и дискретная математика" Национального исследовательского ядерного университета «МИФИ» в рамках курсов "Информатика"

Фрагмент GTF Размер (тыс. строк) НДВ найдено (шт.)

LINKLIB 20 0

LPALIB- 95 2

Макросы 15 0

Всего 130 2

Таблица 1. Результаты верификации подсистемы трассировки событий

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

В рамках курса "Информатика" студенты выполняют практические работы, заключающиеся в написании программ на языках Си и Ассемблер (х86). Чтобы помочь студентам лучше подготовиться к сдаче, была реализована Web-система предварительной сдачи на основе пакета ORZ Online Judge. Студент посылает код через Web-интерфейс, а система выполняет предопределённые тесты и вызывает разработанную систему для обнаружения потенциальных ошибок работы с памятью. Функционал по продвижению меток конфиденциальности в данном случае не используется. Собранная статистика работы отражена в таблице 2.

Задание Средний размер (строк) Среднее время (сек.) Число образцов Ошибок найдено

3.5 100 54 113 0

4.2 150 72 97 5

5.3 500 251 171 3

6.2 150 31 53 7

6.3 200 107 92 4

Таблица 2. Результаты автоматических проверок практических заданий

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

В заключении обобщаются результаты проделанной работы

Основные выводы и результаты работы

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

2. Разработаны требования к системе выявления НДВ, влекущих нарушение конфиденциальности информации. Для их удовлетворения предложена архитектура системы выявления НДВ, влекущих нарушение конфиденциальности информации; спроектированы её основные компоненты - дизассемблер, интерфейс к системам компьютерной алгебры, анализатор потоков данных, статический анализатор и модуль выявления НДВ, влекущих нарушение конфиденциальности информации, а также связи между ними.

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

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

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

6. Разработанное программное обеспечение успешно применено для анализа диагностических компонентов базовой контрольной программы операционной системы z/OS, а также в учебном процессе в рамках курсов "Информатика" и "Защита программного обеспечения'1.

Основные публикации по теме диссертации

Лёошкевич, И.О. Поиск уязвимостей в программном обеспечении с помощью анализа исполняемого кода / И.О. Леошкевич // XV Всероссийская научная конференция. Проблемы информационной безопасности в системе высшей школы — 2008. — С. 93-94

Леошкевич, И.О. Анализ методов идентификации структур данных в исполняемом коде / И.О. Леошкевич, А.Ю. Тихонов // Безопасность информационных технологий — 2009. — №2. — С. 94-97

Леошкевич, И.О. Получение архитектурно-независимой семантики исполняемого кода / И.О. Леошкевич // Безопасность информационных технологий - 2009. - №4. - С. 120-124

Леошкевич, И.О. Разработка системы автоматического анализа исполняемого кода / И.О. Леошкевич // XVII Всероссийская научная конференция. Проблемы информационной безопасности в системе высшей школы — 2010. — с. 158

Леошкевич, И.О. Анализ зависимостей в исполняемом коде / И.О. Леошкевич // Труды научной сессии МИФИ — 2010. — С. 208-211

Леошкевич, И.О. Поиск утечек информации в программном обеспечении с помощью анализа исполняемого кода / И.О. Леошкевич // Безопасность информационных технологий — 2010. — №1. — С. 89-91

Леошкевич, И.О. Система для семантического анализа исполняемого кода / И.О. Леошкевич // VIII межрегиональная научно-техническая конференция студентов и аспирантов. Применение кибернетических методов в решении проблем общества XXI века. Тезисы докладов. — 2010. - С. 9-11

Леошкевич, И.О. Низкоуровневая политика обработки данных / И.О. Леошкевич, А.Н. Велигура // Безопасность информационных технологий — 2010. — №3. — С. 53-55

Тир.ЮО экз .зак. № У5 1,2 у.п.л. отпечатано в тип. НИИ «НПО «ЛУЧ» г.Подольск Моск.обл.

Введение

Глава 1. Задача выявления НДВ.

1.1. Методы статического анализа.

1.1.1. Поиск потенциально онасных конструкций

1.1.2. Проверка формальных ¡моделей.

1.1.3. Абстрактная интерпретация.

1.1.4. Анализ потоков данных.

1.2. Методы динамического анализа.

1.2.1. Контроль поведения.

1.2.2. Инструментальное оснащение.

1.3. Гибридные методы

1.4. Методы анализа исполняемого кода.

1.4.1. Дизассемблирование.

1.4.2. Существующие внутренние представления.

1.4.3. Особенности некоторых архитектур.

1.5. Инструментарий.

1.6. Системы анализа исполняемого кода.

1.6.1. Интерактивный дизассемблер ГОА.

1.6.2. Статический анализатор Сос1е8иг!ег/х86.

1.6.3. Платформа динамического анализа Уа^ппс!.

1.6.4. Платформа для комплексного анализа ВйВ1аге.

1.6.5. Анализатор времени выполнения Вошк1Т.

1.6.6. Прочие системы анализа исполняемого кода.

1.7. Выводы.

Глава 2. Система выявления НДВ.

2.1. Модель нарушителя.

2.2. Требования к системе.

2.3. Компоненты системы.

2.3.1. Дизассемблер.

2.3.2. Анализатор потоков данных.

2.3.3. Интерфейс к системам компьютерной алгебры.

2.3.4. Статический анализатор.

2.3.5. Модуль выявления НДВ-К.

2.4. Выводы.

Глава 3. Элементы системы выявления НДВ.

3.1. Язык описания архитектур процессоров

3.1.1. Внутреннее представление.

3.1.2. Структура описания.

3.1.3. Адресные пространства

3.1.4. Выражения.

3.1.5. Правила.

3.1.6. Типы.

3.1.7. Прочее.

3.1.8. Компиляция.

3.1.9. Применение правил.

3.2. Граф потока управления.

3.3. Моделирование ввода-вывода.

3.3.1. Компоненты модели ввода-вывода.

3.3.2. Язык описания модели ввода-вывода.

3.3.3. Анализ модели ввода-вывода.

3.4. Численные домены

3.4.1. Абстрактные значения.

3.4.2. Абстрактные суммы

3.4.3. Мультисуммы.

3.4.4. Выровненные адреса.

3.4.5. Битовые поля.

3.5. Анализатор потоков данных.

3.6. Домен простых состояний

3.6.1. Состояния участков памяти.

3.6.2. Состояния программы.

3.7. Домен символьных состояний.

3.8. Символьный анализ циклов

3.9. Проверка политики обработки информации.

3.10. Выводы.

Глава 4. Применение системы выявления НДВ.

4.1. Работа с системой выявления НДВ.

4.2. Тестовые испытания.

4.3. Внедрение - ООО ИБМ Восточная Европа/Азия

4.4. Внедрение - Кафедра №42 НИЯУ МИФИ

Актуальность работы. Недекларпрованные возможности программного обеспечения (НДВ) определяются руководящим документом Гостехкомиссии от 4 июня 1999 года как "функциональные возможности программного обеспечения, не описанные или не соответствующие описанным в документации, при использовании которых возможно нарушение конфиденциальности, доступности или целостности обрабатываемой информации"[1]. Конфиденциальная информация определяется руководящим документом Гостехкомиссии от 30 марта 1992 года как "информация, требующая защиты"[2].

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

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

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

Необходимость выявления НДВ-К обусловлена тем, что во многих современных операционных системах предполагается корректность программ, обрабатывающих конфиденциальную информацию от имени пользователя. Это допущение отсутствует в системах, работающих по модели Белла-Лапа-дула^], где выполняется свойство "звезды" - процессы с более высоким уровнем конфиденциальности не могут писать в области с более низким уровнем конфиденциальности. Хотя реализации модели Белла-Ланадула для современных операционных систем существуют, зачастую они не используются, в том числе из соображений удобства.

Задачи исчерпывающего анализа поведения программного кода в общем случае алгоритмически неразрешимы, что следует из результата, полученного Аланом Тьюрингом в 1936 году[5]; задача выявления НДВ-К не является исключением. Кроме того, даже для частных случаев, важных на практике, её решение связано с рядом сложностей. Во-первых, зависимость какой-либо информации от конфиденциальной не очевидна, и во многих случаях может быть отслежена лишь по длинной цепочке присваиваний и преобразований, вытекающей из применения нетривиальных структур данных и алгоритмов. Во-вторых, факт сохранения такой информации может быть скрыг на уровне исходного кода - например, даже если разработчик принял меры по её перезаписи, компилятор на фазе оптимизации может удалить код очистки как неиспользуемый. В-третьих, НДВ-К может активироваться только при определённых и явно не выраженных в коде условиях.

Проблемой выявления НДВ-К в последнее десятилетие занималось множество исследователей, из которых особо можно выделить Nicholas Nethercote (автора утилиты Valgrind)[6], Dawn Song (университет Беркли) [7], Jim Chow (Стэнфордский университет) [8], и Вартана Падаряна (Институт системного программирования РАН) [9]. Ими спроектированы и разработаны средства динамического анализа, позволяющие отслеживать зависимости между обрабатываемыми работающей программой данными, и таким образом позволяющие обнаруживать в ней НДВ-К. Однако, они не позволяют доказать отсутствие НДВ-К, так как с их помощью невозможно исследовать поведение программы при всех возможных входных данных.

Автором данной работы предлагается новая система статического анализа, предназначенная для выявления НДВ-К и работающая на уровне исполняемого кода. Статический анализ предоставляет больше возможностей по рассмотрению всех путей выполнения программы, нежели динамический, а работа на уровне исполняемого кода повышает точность за счёт того, что он является конечным результатом процесса сборки и не подлежит изменениям перед выполнением на ЭВМ конечного пользователя. Применение такой системы позволит существенно ускорить и уменьшить затраты на выявление НДВ-К.

Объектом исследования диссертационной работы является исполняемый код программного обеспечения.

Предметом исследования диссертационной работы являются НДВ, влекущие нарушение конфиденциальности информации.

Целью диссертационной работы является выявление НДВ, влекущих нарушение конфиденциальности информации.

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

• анализ существующих методов выявления НДВ, влекущих нарушение конфиденциальности информации;

• анализ существующих методов верификации исполняемого кода;

• синтез архитектуры системы выявления НДВ, влекущих нарушение конфиденциальности информации;

• синтез алгоритма построения формальной модели программного обеспечения по его исполняемому коду;

• реализация системы выявления НДВ, влекущих нарушение конфиденциальности информации.

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

Научная новизна проведенных исследований и полученных в работе результатов заключается в следующем:

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

• построены два абстрактных домена для представления адресов, позволяющие анализировать низкоуровневые идиомы работы с указателями, основывающиеся па побитовых операциях;

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

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

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

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

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

• построенные численные абстрактные домены: домен выровненных адресов, позволяющий точно учитывать результаты операции выравнивания указателей, и домен битовых нолей, позволяющий описывать работу с адресами, в неиспользуемые биты которых помещена дополнительная информация;

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

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

Внедрение результатов работы. Результаты работы используются в ООО ИБМ Восточная Европа/Азия при разработке программного обеспечения, а также в учебном процессе кафедры №42 "Криптология и дискретная математика" Национального исследовательского ядерного университета «МИФИ».

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

• XV Всероссийская научная конференция. Проблемы информационной безопасности в системе высшей школы. 2008;

• XVII Всероссийская научная конференция. Проблемы информационной безопасности в системе высшей школы. 2010;

• 12-й Национальный форум информационной безопасности. Информационная безопасность России в условиях глобального информационного общества. 2010;

• VII межрегиональная научно-техническая конференция студентов и аспирантов. Применение кибернетических методов в решении проблем общества XXI века. 2010;

• Научная сессия МИФИ. 2010.

Структура и объем диссертации. Диссертация состоит из введения, обзора литературы, 4 глав, заключения и библиографии из 101 позиции. Общий объем диссертации составляет 155 страниц, включая 11 рисунков и 8 таблиц.

3.10. Выводы

В данной главе подробно рассмотрены принципы функционирования разработанной системы выявления НДВ-К.

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

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

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

Глава 4

Применение системы выявления НДВ 4.1. Работа с системой выявления НДВ

С точки зрения пользователя система состоит из двух основных компонентов - анализатора и программы для просмотра результатов. Вызов анализатора имеет следующий вид: fa --module <имя-файла> [--ext <расширения>] [--arg <аргументы загрузчика>]

Опции имеют следующее значение:

• -module - имя модуля. Поддерживаются модули в форматах raw (без заголовка), РЕ и zmod.

• -ext - набор расширений для дизассемблера. Политика обработки информации должна быть реализована как расширение.

• -arg - аргументы для загрузчика модуля. Для загрузчика формата zmod это базовый адрес каждого сегмента и содержимое некоторых полей PSW.

Поверхностный отчёт о ходе работы системы, включающий в себя наименование проводимой в данный момент фазы анализа и её результаты, печатается на стандартный вывод. Более подробная информация - граф потока управления и отчёт о возможности наличия НДВ-К, помещается в директорию, имя которой совпадает с именем модуля. Граф потока управления можно просмотреть с помощью графической утилиты vis, реализованной на языке С# с использованием библиотеки Microsoft Automatic Graph Layout, реализующей алгоритм визуализации графов Сугиямы [96]. Отчёт представляет собой текстовый файл, содержащий адреса инструкций, предположительно реализующих НДВ-К.

4.2. Тестовые испытания

Были подвергнуты анализу 64 тестовые программы, из которых:

• Группа А, 47 программ: имеют небольшой размер и служат для проверки корректности анализа распространённых конструкций;

• Группа Б, 17 программ: реализуют различные вариации НДВ-К.

Для группы А целью являлось получение полной формальной модели безотносительно наличия или отсутствия в них НДВ-К. Результат использования разработанной систему представлен в таблице 4.1.

Для группы Б целью являлось успешное выявление НДВ-К. Программы в группе Б также имеют небольшой размер и реализуют следующие виды НДВ-К:

• Наличие остаточной информации, напрямую зависящей от конфиденциальной, в локальной переменной;

• Остаточная информация, зависящая от конфиденциальной по управлению;

• Остаточная информация, зависящая от конфиденциальной по адресу;

• Сохранение конфиденциальной информации через двойное разымено-вывание;

• Неполная или отсутствующая очистка динамической копии конфиденциального массива;

• Остаточная информация в полях классов.

Система успешно выявила все НДВ-К, реализованные в программах группы Б.

Наименование Кол-во Время анализа инструкций (сек.) addesp 27 8 alias 1 25 8 and esp 23 7 ascendingloop 26 8 bad loop 1 26 8 bsf obx eax 27 8 bubble 28 8 cmp addjmp 26 8 dead flags 23 7 defl 28 7 demand 1 22 8 dcscend i ng loop post ,jnz 25 8 descend ing loop pre j 1 24 7 fmode 2820 309 fuzz 371 58 gen 2041 236 if-1 995 128 infeasible 23 7 keyfileO 578 88 linear 25 7 livel 658 75 loops 5962 835 malloc 150 22 mallocl 967 121 maychangel 184 30 memory counter 25 7 misc 896 96 ofn 158 28 overwrite static 23 8 proc 589 73 rdtsc 27 8 repstosd 23 7 sample4 3872 483 sample5 2354 247 sample6 4260 488 selfmodifyingl 28 9 selfmodifying2 23 7 simpleloop 26 8 smloop 24 8 strlen 25 8 two counters 24 8 uncertain fill 150 26 unreachable loop 23 8 unsigned ascending loop 30 9 unsigned descending loop 23 7 xorl 24 7 zero tricks 27 7

Заключение

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

Проанализировано более 20 существующих средств выявления НДВ и анализа исполняемого кода; на основании анализа сделаны следующие выводы:

1. Существующие средства динамического анализа обладают функционалом для выявления НДВ-К, однако, они не могут предоставить • гарантий отсутствия НДВ-К, поэтому актуальна разработка дополняющего их статического средства;

2. Выявление НДВ-К необходимо проводить на уровне исполняемого кода программного обеспечения;

3. Существующие средства статического анализа исполняемого кода не обладают функционалом по выявлению НДВ-К;

4. Существующие средства статического анализа исполняемого кода не могут быть использованы в качестве основы системы выявления НДВ-К.

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

НДВ-К относительно политики обработки информации. К системе предъявлен ряд требований, из которых можно выделить универсальность - поддержку различных целевых процессоров и операционных систем, и возможность анализа всех путей выполнения программного обеспечения. Основным принципом работы системы является продвижение меток конфиденциальности: информация, зависящая от конфиденциальной также является конфиденциальной, если только политика обработки информации не утверждает обратного; все возможные источники конфиденциальная информация и допустимые приёмники конфиденциальной информации описываются политикой её обработки; любое отклонение является признаком наличия НДВ-К.

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

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

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

Таким образом, в работе полностью решены поставленные задачи: проведён анализ существующих систем выявления НДВ-К и анализа исполняемого кода, показавший необходимость разработки системы выявления НДВ-К, разработаны архитектура и алгоритмы работы системы выявления НДВ-К, а также реализована сама система выявления НДВ-К.

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

Практичекую значимость результатов работы определяет успешный опыт использования системы в ООО ИБМ Восточная Европа/Азия для проверки фрагментов кода диагностических компонентов базовой контрольной программы операционной системы z/OS, а также в учебном процессе кафедры №42 "Криптология и дискретная математика" Национального исследовательского ядерного университета «МИФИ» в рамках курсов "Информатика" и "Защита программного обеспечения".

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

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

• построенные численные абстрактные домены: домен выровненных адресов, позволяющий точно учитывать результаты операции выравнивания указателей, и домен битовых полей, позволяющий описывать работу с адресами, в неиспользуемые биты которых помещена дополнительная информация;

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

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

1. Гостехкомиссия. Руководящий документ. Защита от несанкционированного доступа к информации. Часть 1. Программное обеспечение средств защиты информации. Классификация по уровню контроля отсутствия иедекларированных возможностей / 1999.

2. Гостехкомиссия. Руководящий документ. Защита от несанкционированного доступа к информации. Термины и определения / 1992.

3. Halderman, J. Alex. Lest We Remember: Cold Boot Attacks on Encryption Keys / J. Alex Halderman // Proceedings of the USENIX Security Symposium — 2008. — pp. 45-60.

4. Bell, D. Eliott. Secure Computer Systems: Mathematical Foundations. Tech. rep. №2547. 1973.

5. Turing, Alan. On computable numbers, with an application to the Entscheidungsproblem / Alan Turing // Proceedings of the London Mathematical Society — 1936. — №42. — pp. 230-265.

6. Nethercote, Nicholas. Dynamic Binary Analysis and Instrumentation. PhD thesis. University of Cambridge, 2004.

7. Song, Dawn. BitBlaze: A New Approach to Computer Security via Binary Analysis / Dawn Song // ICISS — 2008.

8. Chow, Jim. Understanding Data Lifetime via Whole System Simulation / Jim Chow — 2004.

9. Падарян, В.А. Программная среда для динамического анализа бинарного кода / В.А. Падарян, А.И. Гетьман, М.А. Соловьев // Труды Института системного программирования РАН — 2009.

10. Evans, David. Improving Security Using Extensible Lightweight Static Analysis / David Evans, David Larochelle // IEEE Software — 2002.

11. Hovemeyer, David. Finding bugs is easy / David Hovemeyer, William Pugh // Object-Oriented Programming, Systems, Languages and Applications — 2004. — pp. 92-106.

12. JetBrains. Nullable How-To URL: http : / /www . jetbrains . com/ idea/documentation/howto.html.

13. Clarke, Edmund. Predicate Abstraction of ANSI-C Programs using SAT / Edmund Clarke // Formal Methods in System Design — 2004.pp. 105-127.

14. Cytron, R. An Efficient Method of Computing Static Single Assignment Form / R. Cytron // POPL — 1989. — pp. 25-35.

15. Rushby, John. SMT Solvers: A Disruptive Technology. http://fm. cs.uiuc.edu/talks/060406/slides.pdf. 2006.

16. Cousot, Patrick. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints / Patrick Cousot, Radhia Cousot // POPL — 1977. — pp. 238-252.

17. Cousot, Patrick. Refining Model Checking by Abstract Interpretation / Patrick Cousot, Radhia Cousot // Automated Software Engineering1999. — №1. — pp. 69-95.

18. Ope, О. Теория графов (второе издание). Москва: Наука, 1980.

19. Cousot, Patrick. Comparing the Galois connection and widening/narrowing approaches to abstract interpretation / Patrick Cousot, Radhia Cousot // Programming Language Implementation and Logic Programming — 1992. — pp. 269-295.

20. Schmidt, David A. Data flow analysis is model checking of abstract interpretations / David A. Schmidt — 1998. -— p. 11.

21. Mit, Michael Ernst. Static and Dynamic Analysis: Synergy and Duality / Michael Ernst Mit, Michael D. Ernst — 2003. — pp. 2427.

22. Clarke, Edmund. Counterexample-Guided Abstraction Refinement / Edmund Clarke // CAV — 2000. — pp. 154-169.

23. Sen, Koushik. CUTE and jCUTE: Concolic unit testing and explicit path mo del-checking tools / Koushik Sen, Gul Agha — 2006. — pp. 419423.

24. Ball, Thomas. The SLAM project: debugging system software via static analysis / Thomas Ball, Sriram K. Rajamani // Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages — 2002.

25. Beyer, Dirk. The Software Model Checker Blast: Applications to Software Engineering / Dirk Beyer // STTT — 2007. — pp. 505-525.

26. Ball, T. SLAM2: Static Driver Verification with Under 4% False Alarms / T. Ball // Formal Methods in Computer Aided Design — 2010.

27. Gulwani, Sumit. Bound Analysis using Backward Symbolic Execution. Tech. rep. 2009.

28. Moura, Leonardo. Z3: An Efficient SMT Solver / Leonardo Moura, Nikolaj Bj0rner // Conference on Tools and Algorithms for the Construction and Analysis of Systems — 2008.

29. Beckman, Nels. Proofs, from Tests / Nels Beckman // MSR-TR — 2008.

30. Lai, Akash. MCDASH: Refinement-Based Property Verification for Machine Code / Akash Lai, Junghee Lim, Thomas Reps — 2009.

31. Intel. Intel 64 and IA-32 Architectures Software Developer's Manual Volume 2A: Instruction Set Reference, A-M.

32. Guilfanov, Ilfak. Decompilers and beyond / Ilfak Guilfanov — 2008.

33. Valgrind Source Code URL: http://valgrind.org/downloads/ current.html.

34. Dullien, Thomas. REIL: A platform-independent intermediate representation of disassembled code for static code analysis. Tech. rep. Zynamics, 2009.

35. Lim, Junghee. A system for generating static analyzers for machine instructions / Junghee Lim, Thomas Reps // CC —■ 2008.

36. Ramsey, Norman. Specifying Instructions' Semantics Using Lambda-RTL / Norman Ramsey, Jack Davidson — 1999.

37. Cai, Hongxu. Certified Self-Modifying Code / Hongxu Cai, Zhong Shao, Alexander Vaynberg // YALEU/DCS/TR — 2010.

38. Appel, Andrew W. A semantic model of types and machine instructions for proof-carrying code / Andrew W. Appel, Amy P. Felty // POPL — 2000.

39. Neophytos, Michael G. Machine Instruction Syntax and Semantics in Higher Order Logic / Michael G. Neophytos, Andrew W. Appel // TR — 2000.

40. Ray, Sandip. Towards a Formalization of the X86 Instruction Set Architecture / Sandip Ray — 2008.

41. Rogers, Ian. Static Single Assignment / Ian Rogers.

42. Tu, Peng. Gated SSA-based demand-driven symbolic analysis for parallelizing compilers / Peng Tu, David Pradua // ICS — 1995. — pp. 414-423.

43. Dijkstra, Edsger. Guarded commands, nondeterminacy and formal derivation of programs / Edsger Dijkstra // Communications of the ACM — 1975. — №8. — pp. 453-457.

44. Holzmann, Gerard J. The SPIN MODEL CHECKER: Primer and Reference Manual. Addison-Wesley.

45. ЦБИ. Анализатор исходных текстов "АИСТ-С" URL: http: //www. cb i-inf о.ru/group s/page-343.htm.

46. ЦБИ. Программа исследования программного обеспечения "EMU" -URL: http://www.cbi-info.ru/groups/page-342.htm.

47. Газинформсервис. IRIDA контроль и защита потоков управления в исполняемых кодах программ - URL: http://bit-info.com/GAZ-IS/irida.

48. БНТИ. Анализатор механизма очистки оперативной памяти "НКВД 2.5" URL: http://www.bnti.ru/des.asp?itm=2244.

49. Balakrishnan, Gogul. WYSINWYX: What You See Is Not What You eXecute. PhD thesis. University of Wisconsin-Madison, 2007.

50. Nethercote, Nicholas. How to Shadow Every Byte of Memory Used by a Program / Nicholas Nethercote, Julian Seward // VEE — 2007. — pp. 65-74.

51. Holsti, Niklas. Computing Time as a Program Variable: A Way Around Infeasible Paths / Niklas Holsti // WCET — 2008.

52. Holsti, Niklas. Analysing Switch-Case Tables by Partial Evaluation / Niklas Holsti // WCET — 2007.

53. Pugh, William. Counting Solutions to Presburger Formulas: How and Why. Tech. rep. University of Maryland, 1993.54. lpsolve — URL: http://lpsolve.sourceforge.net/.

54. Kinder, Johannes. Jakstab: A Static Analysis Platform for Binaries / Johannes Kinder, Helmut Veith // CAV — 2008. — pp. 423-427.

55. Kinder, Johannes. An Abstract Interpretation-Based Framework for Control Flow Reconstruction from Binaries / Johannes Kinder, Helmut Veith, Florian Zuleger // VMCAI — 2009. — pp. 214-228.

56. Kinder, Johannes. Static Analysis of x86 Executables. PhD thesis. 2010.

57. Wang, Tielei. IntScope: Automatically Detecting Integer Overflow Vulnerability in X86 Binary Using Symbolic Execution / Tielei Wang — 2008.

58. GiNaC is Not a CAS URL: http: //www. ginac. de/.

59. Dullien, Thomas. Platform-independent static binary code analysis using a meta-assembly language / Thomas Dullien, Sebastian Porst // CSW — 2009.

60. Sharif, Monirul. Eureka: A Framework for Enabling Static Malware Analysis / Monirul Sharif // ESORICS — 2008. — pp. 481-500.

61. Vanegue, Julien. Next Generation Debuggers for Reverse Engineering / Julien Vanegue // BHEU — 2007.

62. Durden, Tyler. Automated vulnerability auditing in machine code / Tyler Durden // Phrack — 2007.

63. Visser, W. Model Checking Programs / W. Visser // ASE — 2003.№2.

64. Allen, Matthew. Slicing Multi-threaded Java Programs: A Case Study / Matthew Allen, Susan Horwitz // PPoPP — 2003. — pp. 44-54.

65. Shumow, Daniel. Side Channel Leakage Profiling in Software / Daniel Shumow, Peter L. Montgomery — 2010.

66. Common Weaknesses Enumeration url: http: //ewe.mitre. org/.

67. Eset. Tlireat Encyclopaedia Win32/Induc.A - URL: http://www. eset. eu/ encyclopaedia/win32-induc-a-virus.

68. Меньшов, B.C. Применение низкоуровневого исследования программного обеспечения на наличие недекл.арируемых возможностей / B.C. Меньшов, В.Н. Липовенко // Информационное противодействие угрозам терроризма — 2008. — С. 187-195.

69. Nicholson, Andy. 64-bit programming in a 32-bit world: writing-portable code for 16-, 32-, and 64-bit architectures / Andy Nicholson // Dr. Dobb's Journal — 1993.

70. Ахо, А. Компиляторы, принципы, технологии и инструментарий, 2-е изд. Москва: Вильяме, 2008.

71. Laviron, Vincent. Refining Abstract Interpretation-Based Static Analyses with Hints / Vincent Laviron, Francesco Logozzo // LNCS — 2009. — pp. 343-358.

72. Cooper, Keith D. A Simple, Fast Dominance Algorithm / Keith D. Cooper, Timothy J. Harvey, Ken Kennedy — 2001.

73. Schwartzbach, Michael. Lecture Notes on Static Analysis / Michael Schwartzbach — 2008.

74. Cousot, Patrick. Static Determination of Dynamic Properties of Programs / Patrick Cousot, Radhia Cousot // Proceedings of the Second International Symposium on Programming — 1976. — pp. 106-130.

75. Cousot, Patrick. Automatic discovery of linear restraints among variables of a program / Patrick Cousot, Nicolas Halbwachs — 1978. — pp. 84-97.

76. Mine, A. The Octagon Abstract Domain / A. Mine // Higher-Order and Symbolic Computation — 2006. — pp. 31-100.

77. Logozzo, Francesco. Pentagons: a weakly relational abstract domain for the efficient validation of array accesses / Francesco Logozzo, Manuel Fahndrich // SAC — 2008. — pp. 184-188.

78. Sotin, Pascal. Quantifying the Precision of Numerical Abstract Domains / Pascal Sotin — 2010.

79. Balakrishnan, Gogul. Analyzing Memory Accesses in x86 Executables / Gogul Balakrishnan, Thomas Reps // CC — 2004. — pp. 5-23.

80. Reps, Thomas. Static Program Analysis via 3-Valued Logic / Thomas Reps // LNCS — 2002.

81. Warren, Henry S. Hacker's Delight. Addison-Wesley Professional, 2003, p. 320.

82. Tarjan, Robert. Depth-first search and linear graph algorithms / Robert Tarjan // Switching and Automata Theory — 1971. — pp. 114121.

83. Muchnick, Steven S. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997.

84. Yorsh, Greta. Generating precise and concise procedure summaries / Greta Yorsh, Eran Yahav, Satish Chandra // POPL — 2008. — pp. 221-234.

85. Fahringer, Thomas. Advanced Symbolic Analysis for Compilers / Thomas Fahringer, Bernhard Scholz // LNCS — 2003.

86. Sinha, Nishant. Symbolic program analysis using term rewriting and generalization / Nishant Sinha // FMCAD — 2008.

87. Wies, Thomas. Verifying Complex Properties using Symbolic Shape Analysis / Thomas Wies // Workshop on Heap Abstraction and Verification — 2006.

88. Kovacs, Laura. Finding Loop Invariants for Programs over Arrays Using a Theorem Prover / Laura Kovacs, Andrei Voronkov // FASE — 2009.

89. Dijkstra, Edsger W. A Discipline of Programming. Upper Saddle River, NJ, USA: Prentice Hall PTR, 1997, p. 240.

90. Carette, Jacques. Program Verification by Calculating Relations / Jacques Carette, Ryszard Janicki, Yun Zhai // Applied Simulation and Modeling — 2006.

91. Balakrishnan, Gogul. Refining the control structure of loops using static analysis / Gogul Balakrishnan — 2009. — pp. 49-58.

92. GNU Linear Programming Kit URL: http: //www. gnu. org/software/ glpk/.

93. Parametric Integer Programming URL: http://piplib.org/.

94. Scholz, Bernhard. User-input dependence analysis via graph reachability / Bernhard Scholz, Chenyi Zhang, Cristina Cifuentes — 2008.

95. Sugiyama, Kozo. Methods for Visual Understanding of Hierarchical System Structures / Kozo Sugiyama, Shojiro Tagawa, Mitsuliiko Toda // IEEE Transactions on Systems, Man, and Cybernetics — 1981. — pp. 109-125.

96. IBM. z/Architecture Principles of Operation, 8th Edition / 2009.

97. Anckaert, Bertrand. A model for self-modifying code / Bertrand Anckaert, Matias Madou, Koen De Bosschere // Proceedings of the 8th international conference on Information hiding — 2006.

98. Schmitz, Karl. z/OS System Integrity: Authorized Software without Security Holes / Karl Schmitz // SHARE — 2003.

99. Беззубцев, И.О. Материалы курса "Информатика" / И.О. Беззубцев, И.О. Леошкевич, О.С. Варламов.101. orz online judge URL: https://code.google.eom/p/orzoj/.