ТЕСТИРОВАНИЕ, ВЕРИФИКАЦИЯ И ВАЛИДАЦИЯ ПРОГРАММ
УДК 681.3.06
АВТОМАТИЗАЦИЯ ПОСТРОЕНИЯ МОДЕЛЕЙ НОРМАЛЬНОГО ПОВЕДЕНИЯ
© 2012 г. А.В. Сапожников Лаборотория информационных систем в образовании и научных исследованиях ВМК МГУ 119991, Москва, ГСП-1, Ленинские горы, д.1, стр.52 E-mail: andrey.askold@gmail.com Поступила в редакцию 24.10.2011 г.
Рассматривается задача алгоритмизированного построения описаний нормального поведения сетевых программ. Предложен механизм обнаружения внедрения в программу вредоносного кода во время её выполнения. Приводится алгоритм решения задачи построения множества нормального поведения программы по набору примеров нормального поведения.
1. ВВЕДЕНИЕ
В данной работе рассматривается задача алгоритмизации построения множества нормального поведения программы по заданному набору примеров нормального поведения. Следуя [3] и [5], под поведением программы в данной работе понимается множество историй программы, где каждая история представляет собой последовательность шагов программы. Нормальное поведение программы - это подмножество поведения, состоящее только из таких историй, которые отмечены как допустимые. Понятно, что конечный набор примеров нормального поведения не покрывает множество всех возможных историй нормального поведения. Для решения задачи построения множества нормального поведения по набору примеров нормального поведения в данной работе предложена операция расширения множества примеров нормального поведения и показано, что результирующее множество всегда принадлежит нормальному поведению программы.
Структура работы следующая: во втором разделе приводятся понятия поведения программы и нормального поведения, формализованные в работах [3] и [5]. Показывается, что только информации о взаимодействии программы с другими объектами информационной системы
недостаточно для решения задачи контроля безопасного выполнения программы. В третьем разделе предлагается решение этой проблемы, основанное на расстановке в программу т.н. контрольных точек и их отслеживании. В четвертом разделе ставится задача построения нормального поведения программы по набору примеров нормального поведения, решаемая с помощью операций расширения множества примеров нормального поведения. Указываются условия, при выполнении которых данные операции расширения являются корректными. Алгоритм решения этой задачи приведен в пятом разделе. В шестом разделе кратко рассматриваются похожие работы в области контроля за поведением программ во время их выполнения и указываются ограничения предлагаемых в этих работах способов описания нормального поведения программы и методов построения таких описаний. Заключение и выводы данной работы приводятся в разделе семь.
2. ФОРМАЛЬНАЯ МОДЕЛЬ ОПИСАНИЯ ПОВЕДЕНИЯ СЕТЕВЫХ ОБЪЕКТОВ
Следуя работам [3] и [5], будем представлять поведение распределенной информационной системы (РИС) и отдельных программ в виде описания поведения отдельных про-
цессов. Поведение процесса p это граф bhp = (Vp, Rp, rootp, labelp), где
1. (Vp, Rp) есть ациклический ориентированный граф со множеством вершин Vp и отношением достижимости Rp. Множество Vp при этом называется множеством состояний процесса.
2. rootp это некоторый элемент из Vp, называемый корневой вершиной графа.
3. labelp есть функция разметки множества вершин графа (кроме корневой) т.н. шагами процесса - элементами особого множества S. labelp : Vp \ {rootp} ^ S. Факт разметки вершины v G V элементом s G S будем записывать в виде vs.
Пусть M - множество сообщений, которыми могут обмениваться процессы в ходе своего функционирования, IA - алфавит внутренних действий процесса (некоторые операции, выполняемые процессом и не включающие в себя операции обмена сообщениями между процессами), а P - множество процессов в РИС. Тогда множество шагов процесса это S = M х IA* х M х {P U back}. Элемент этого множества называется шагом процесса и представляет собой четвёрку: sp = (as, qs, @s,ps), где
1. as G M - называется сообщением-воздействием на шаге s.
2. qs - последовательность внутренних действий процесса.
3. es - называется сообщением-реакцией на
шаге s.
4. ps - процесс, которому передается сообщение-реакция.
Шаг s = (a,q,e,ps) можно так же кратко записывать как s = (а ^ fi,ps), для краткости опуская последовательность внутренних действий.
Путь в графе bhp называется историей процесса p.
При этом история процесса имеет свойство замкнутости слева, т.е. если последовательность vi,v2,...,vn является историей процесса, то и
Vk < n vi,v2,... ,vk так же является историей. Все множество путей в bhp образует поведение процесса.
В [3] показывается, что структура bhp - дерево.
Объедение графов поведения нескольких процессов, образующих программу П - даёт нам граф поведения программы: BH = |J bhp.
peP
Программа П представлена своим графом потока управления программы (CFG - control flow graph): П = (Uп, Eп), где вершины G Uп размечены операторами программы, а ребра еП = (иП[, ^П,) отражают передачу управления в программе ([1], [14]). Каждому шагу sp G S соответсвует некоторый путь иП ,иП ,...,иПп в CFG программы - последовательность операторов программы, выполнение которых и реализует обмен сообщениями as и и внутренние действия qs этого шага. Мы будем в дальнейшем говорить, что история trace G BH покрывает некоторый путь в CFG программы (т.е. некоторую последовательность вершин иП, иП,..., иППп, размеченных операторами программы, выполнение которых реализует последовательность шагов этой истории trace).
Отметим, что описание поведения программы в виде последовательности шагов абстрагирует нас от низкоуровневых деталей устройства реальной программы и передачи управления в CFG программы и концентрирует внимание на информационном взаимодействии процессов (обмен сообщениями между процессами разных программ, обращение программы к ресурсам и т.п.).
Теоретически множество BH может быть получено полностью автоматическим образом, на основе статического анализа CFG программы (т.е. еще до момента её непосредственного выполнения). На практике, построение множества BH на основе статического анализа кода программы зачастую является невозможным, например, из-за взаимодействия программы с библиотеками, код которых может быть недоступен для анализа.
Во множестве BH существует подмножество историй, которые мы называем нормальными - эти истории соответствуют желаемому поведению программы. Такое подмножество историй называется нормальным поведением
программы и обозначается BHnorm: BHnorm С BH.
Если множество нормального поведения BHnorm известно, то можно поставить задачу контроля безопасного выполнения программы - т.е. проверки того факта, что история trace выполняемой в данный момент программы принадлежит множеству нормального поведения: trace £ BHnorm. Данная задача ставится и решается в работе [5], где для проверки принадлежности trace £ BHnorm используются конечные автоматы специального вида. Данные автоматы получают на вход последовательность шагов программы и в случае, если наблюдаемая история не принадлежит множеству нормального поведения, сигнализируют об обнаружении аномалии, т.е. отклонения наблюдаемой истории от множества историй, принадлежащих BHnorm.
Построение таких автоматов в работе [5] производится автоматически, по заданному множеству нормального поведения. Однако вопрос о том, как получить множество BHnorm, в работе [5] остается открытым. Алгоритмизация построения множества нормального поведения BHnorm и является целью данной работы.
2.1. Причины возникновения аномалий поведения
Мы будем рассматривать логически корректные программы, т.е. программы, для которых BHnorm = BH. В таких программах, однако, могут существовать уязвимости вида "возможность внедрения вредоносного кода" [11], позволяющие осуществить внедрение исполняемого кода в программу во время ее выполнения. Результатом такого внедрения кода в общем случае будет изменение структуры CFG программы - появление новых вершин или удаление уже существующих, появление или удаление ребер между парами вершин и изменение разметки вершин CFG операторами программы. В свою очередь, изменение CFG программы приводит к изменению поведения программы: П ^ П', BH ^ BH', BH = BH'.
В такой ситуации, наблюдаемые во время выполнения программы истории могут как отличаться от историй, входящих в нормальное
поведение программы, так и совпадать с ними: 3trace\,trace2 : trace\ £ BHnorm ,trace\ £ BH', trace2 £ BHnorm. Это означает, что наличие известного множества BHnorm и наблюдение за текущей историей trace не позволяют в общем случае обнаружить факт модификации кода программы во время ее выполнения. Это происходит потому, что описание нормального поведения BHnorm не содержит информации об устройстве CFG программы.
2.2. Механизм контрольных точек в программе
Для того, чтобы сделать возможным обнаружение факта модификации программы во время ее выполнения, предлагается использовать механизм контрольных точек.
Мы будем говорить, что в программу П расставленно множество контрольных точек Chp - т.е. часть вершин CFG программы размечена элементами из Chp.
В рамках нашей формальной модели мы будем рассматривать особый внешний по отношению к программе процесс логической среды Pcheckp, с которым все остальные процессы могут обмениваться сообщениями из множества Mcheckp. Каждое такое сообщение есть ничто иное, как информирование процесса pcheckp о том, что процесс p прошел контрольную точку - это означает, что в CFG программы П управление было передано на вершину, помеченную элементом из Chp. Тем самым, отдельная история процесса p теперь может включать шаги
checkp
вида Si которые будут сводиться к
отправке процессу pcheckp сообщения о прохождении процессом p очередной контрольной точки. Последовательность прохождения программой контрольных точек отражает последовательность передачи управления между вершинами CFG программы. Нарушение последовательности наблюдения контрольных точек является индикацией того, что CFG программы был изменен в результате модификации кода программы посредством внедрения злоумышленник
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.