CARE: A Platform for Reliable Comparison and Analysis of Reverse-Engineering Techniques

Sylvain Lamprier, Nicolas Baskiotis, Tewfik Ziadi, and Lom Messan Hillah. 2013. CARE: A Platform for Reliable Comparison and Analysis of Reverse-Engineering Techniques. In Proceedings of the 2013 18th International Conference on Engineering of Complex Computer Systems (ICECCS '13). IEEE Computer Society, Washington, DC, USA, 252-255. DOI=http://dx.doi.org/10.1109/ICECCS.2013.44

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

Большинство последних исследований сфокусировано на частных контекстах(тестирование, верификация и т.д), что затрудняет оценку качества алгоритма. Тем не менее сравнение алгоритмов вывода конечного автомата возможно, так как различные цели алгоритмов можно выразить специальными метриками качества, адаптированными к контексту. Как указано в [1], для ранее опубликованных алгоритмов вывода не хватает эталонных тестов(benchmark) для их оценки. Обычно оценка производится на стандартных тестовых случаях, что позволяет говорить только об осуществимости алгоритма, но не об эффективности работы в более широком контексте.

Структура программы задается с помощью формальной грамматики G = (N, Σ, P, S), где N и Σ — множества нетерминальных и терминальных символов соответственно, S — стартовый символ (Block), P — множество правил:

1. Block → BlockList | Alt | Opt | Loop| Call
2. BlockList → Block+
3. Alt → Block Block+
4. Opt → Block
5. Loop → Block
6. Call → MethodLabel Block? MethodLabel

Данная спецификация обладает двумя преимуществами:

1. Последовательность команд, исполненных программой(трассировка), можно извлечь из структуры (через симулирование исполнения программы)
2. Также может быть извлечен соответствующий конечный автомат, который в дальнейшем может служить в качестве эталона при подсчете метрик

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

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

Данные распределения создают различные по сложности программы для алгоритмов вывода конечного автомата из трассировки выполнения программы. Конфигурация A приводит к строго линейным программам, C — ациклическим структурам с условиями, E — циклическим структурам без условий, G — наиболее сложным структурам, содержащим как циклы, так и условия. Конфигурации B, D, E приводит к примерно одинаковым конечным автоматам, но повторяющиеся блоки усложняют задачу вывода.

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

• Равномерная

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

• Объективная(Unbiased)

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

• Необъективная(Biased)

Для каждой точки ветвления задано свое распрделение вероятностей

• Вектор состояния (StateVector)

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

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

Центральная идея алгоритма - рассмотрение состояния конечного автомата согласно последующим действиям, наблюдаемых из него и слитие всех состояний, следующие k действий которых совпадают. Параметр k позволяет контролировать уровень специализации/обобщения алгоритма: при меньших значениях k процесс слияния менее ограничен, в то время как при больших значениях итоговый автомат получается более общим.

В платформе CARE алгоритмы оцениваются по полноте и корректности конечного автомата, выдаваемого ими. Авторы используют метрики точности(precision) и полноты(recall). Полнота оценивает долю программных путей эталонной автомата, которые принимаются оцениваемым, точность — долю путей, полученного из оцениваемого автомата, принадлежащих эталонному. Так как путей может быть бесконечно много, данные метрики не могут быть посчитаны точно, но их можно аппроксимировать, подсчитывая их на подмножествах, равновероятно выбираемых из всего множества путей. Авторы использовали подмножества размером 1000 для подсчета обеих метрик.

В качестве иллюстрации работы платформы авторы провели оценку KTail для различных значений k с помощью 1000 сгенерированных программ для каждой из 7 конфигураций, представленных в таблице 1. Результаты экспериментов показали, что, как и ожидалось, большие значения k приводят к более высоким показателям точности, малые - к более высоким показателям полноты. В результате экспериментов были выделены два лучших значения: k = 5 позволяет ограничивать ошибки обобщения, k = 3 позволяет достичь хорошего качества, строя конечный автомат разумного размера.

Рисунок 1. Значения метрики F1 для k = 3, 5 и 1000. Буквы соответствуют конфигурациям из таблицы 1, цифры — стратегии извлечения трассировки, упорядоченных по возрастанию покрытия поведения:

• 1 = StateVector_0;
• 2 = StateVector_0.2;
• 3 = Biased; 4 = StateVector_0.5;
• 5 = StateVector_1; 6 = Unbiased , 7 = Uniform.

Разница между значениями непостоянна для каждого типа конфигурации. По графику можно заметить, что когда в программе нет повторяющихся блоков, преимущество k = 3 намного больше при ограниченном видении поведения.

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

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

1. генерации различных классов программ(линейные, условные, циклические и т.д)
2. использования различных стратегий симуляции исполнения, приводящих к разным уровням покрытия поведения программы

• [1] N. Walkinshaw, K. Bogdanov, C. Damas, B. Lambeau, and P. Dupont, “A framework for the competitive evaluation of model inference techniques,” in MIIT ’10. New York, NY, USA: ACM, 2010, pp. 1–9.
• [2] A. W. Biermann and J. Feldman, “On the synthesis of finite-state machines from samples of their behavior,” IEEE Transactions Computers, vol. 21, pp. 592–597, 1972.