Русская Википедия:Поиск клонов в исходном коде
Поиск клонов в исходном коде — анализ исходного кода с помощью различных алгоритмов, с целью обнаружения клонированного кода, который может иметь вредоносный характер.
Введение
В настоящее время производителями выпускается огромное количество программных продуктов. К сожалению, известен исходный код не каждого продукта. А в неисследованной программе могут быть скрыты функции, имеющие вредоносный характер. На анализ только одного исполняемого файла у исследователя уйдут многие месяцы, а возможно и годы (в зависимости от размера файла). Такие большие затраты неэффективны и не допустимы. Именно поэтому актуальна задача автоматического анализа исполняемого кода. При наличии инструментов для поиска клонированного кода, исследователю не придётся анализировать участки кода уже исследованные ранее или являющиеся стандартными библиотеками. Данные инструменты смогут находить вредоносные программы в коде, сравнивая их с ранее проанализированными двоичными файлами вредоносных программ.
Способы анализа исходного кода
Существует множество способов поиска клонированного кода, но в основном они подразделяются на синтаксические, структурные и семантические. У каждого подхода есть свои достоинства и недостатки. В научных работах и на практике в настоящее время чаще используется комбинированный подход, который позволяет получить более точный результат. Для упрощения анализа используются, так называемые отпечатки(fingerprint). Отпечатком называется информация, особым образом собранная из исследуемого программного объекта и пригодная для сравнения с другими подобными отпечатками. Данная информация представляет собой уникальное и компактное представление функциональности кода. Алгоритм получения отпечатков - это процедура, которая произвольному элементу данных большого размера ставит в соответствие гораздо более короткую битовую строку. Функции, которые выполняют эквивалентные задачи должны быть представлены похожими отпечатками. Кроме того, результирующие отпечатки должны быть устойчивы к несоответствиям на уровне байтов и терпимы к незначительным изменениям в функции. Также, вероятность возникновения конфликта между отпечатками различных функций должна быть минимальной. То есть не должны возникать ситуации, когда для различных по смыслу функций генерируются идентичные отпечатки. В терминологии отпечатков, перед разработчиком стоят следующие вопросы: каким образом сгенерировать отпечаток, как сравнивать два отпечатка и каким образом оценить результаты.
Структурный подход
Сравнение различных вариантов одного и того же исполняемого файла затрудняется тем, что один и тот же исходный код в зависимости от компилятора преобразуется в различные представления на уровне сборки. Так например, в зависимости от настроек оптимизации компилятора на идентичные инструкции могут назначаться различные регистры. В зависимости от того, как компилятор моделирует конвейер, отдельные инструкции могут быть переупорядочены. Вместо того, чтобы сосредоточиться на конкретных инструкциях уровня сборки структурный подход рассматривает код как граф потока управления, граф потока данных. Одним из основных недостатков данного подхода является то, что структура кода не устойчива к архитектурным изменениям, версионным изменениям, обфускации.
Синтаксический подход
Существуют алгоритмы, опирающиеся исключительно на синтаксическое сходство. Большая часть алгоритмов использует именно синтаксический подход, поскольку определение семантической схожести является намного более сложной задачей. Основной недостаток данного подхода - полное игнорирование структуры программы. Также, синтаксический анализ, как и структурный, не учитывает архитектурные и версионные изменения, обфускацию.
Семантический подход
Синтаксический анализ имеет дело с внешними, текстовыми конструкциями. Семантика же, ориентированная на содержательную интерпретацию, имеет дело с внутренним представлением, то есть смыслом объектов, описанных в программе. При семантическом подходе код рассматривается как последовательность байтов и инструкций.
Алгоритмы анализа исходного кода
Алгоритм Хескела[1]
Один из алгоритмов, использующих синтаксический подход. Две программы представляются в виде строк токенов. Алгоритм ищет наибольшую общую подпоследовательность двух строк, до тех пор, пока она не будет меньше некоторого, наперёд заданного нижнего порога. Далее оценивается процент вхождения одной программы в другую. Основным достоинством этого алгоритма является его линейная сложность. Основной недостаток - полное игнорирование структурных свойств сравниваемых программ. Также возможно совпадение токенизированного представления программ (представление, которое сохраняет существенные признаки программы, и скрывает легко изменяемые), но отсутствие совпадения в исходном коде. Алгоритм также может использоваться для создания зашифрованной версии файла в виде различий между собой и каким-либо заданным файлом, что позволяет восстановить исходный файл из файлов различия и заданного файла.
BinDiff[2]
Один из инструментов, использующих лишь структурное сходство. BinDiff сравнивает двоичные файлы как направленные графы. Эта программа использует в качестве алгоритма сравнения упрощенный способ распознавания изоморфизма графов потока управления, так как, вообще говоря, задача изоморфизма является NP полной.
Общая идея данного подхода заключается в следующем: Даны две исполняемые программы, для каждой из которых строится граф. В каждом графе создается набор узлов, состоящих из двух элементов (по одному от каждой программы), которые могут быть использованы для представления одних и тех же элементов в обоих исполняемых файлах. Эти узлы используются для создания других итеративно, до тех пор пока мы не получим отображение, которое нельзя улучшить. После того, как мы сопоставили максимально возможное количество функций, мы можем начать сопоставлять блоки таким же образом. Поскольку у нас уже есть изоморфизм, который позволяет нам получить две связанные функции, нам достаточно рассматривать соответствия между парами узлов из каждого графа. Дальше данная операция продолжается для все большего числа узлов.
Для построения изоморфизма вводятся такие понятия, как селектор и свойство.
- Селектор - отображение, которое для заданного узла А из одного графа и набора узлов из другого графа возвращает либо один из элементов данного набора, либо пустое множество. Оcновной целью селектора является выбрать из заданного набора наиболее похожий на А узел. В случае если существует несколько узлов, одинаково похожих на А селектор возвращает пустое множество. Интуитивно понятно, что вероятность возврата селектором пустого набора возрастает с увеличением входных наборов.
- Свойство π - отображение, которое переводит два графа в подмножество их узлов: <math>\pi(A, B) \longrightarrow (A^{'n}, B^{'n}), A^{'n} \subset A^n, B^{'n} \subset B^n</math>. Это делается с целью уменьшить размер набора, используемого селектором, что увеличивает вероятность того, что селектор вернет не пустое множество.
Создание узлов.
Если дан селектор s, то изоморфизм <math>p: A^n \longrightarrow B^n</math>, можно построить задав начальный изоморфизм <math>p_1</math>, который затем будет последовательно улучшаться, пока это возможно. Начальный изоморфизм <math>p_1: A^n \longrightarrow B^n</math> строится простым образом с помощью селектора: <math>p_1(x) \longrightarrow s(x, B^n)</math>. Это определение можно улучшить в случае, если нам задан набор свойств. Пусть <math>\Pi = </math>{ <math>\pi_1, ..., \pi_j</math>} - заданный набор свойств. Тогда улучшенный начальный изоморфизм можно построить следующим образом:
for <math>\pi \in \Pi</math>do
(K, L) <math>\longleftarrow</math><math>\pi(A, B)</math>;
for <math>x \in K</math>do
define <math>p_1(x) \longrightarrow s(x, L)</math>
end
end
Добавление узлов.
Если дан начальный изоморфизм <math>p_1</math>, дальнейшие улучшенные изморфизмы можно построить по следующему алгоритму:
Input: <math>p_{n-1}, s, A, B</math>
Result: <math>p_n</math>
<math>S \longleftarrow</math>{ <math>x \in A^n|_{n-1} \neq \oslash</math>};
for <math>x \in S</math>do
P <math>\longleftarrow</math>up<math>(x)</math>
K <math>\longleftarrow</math>up<math>(p_{n-1}(x))</math>;
for <math>y \in P</math>do
if <math>s(y, K) \neq \varnothing</math>then
define <math>p_n(y) \longrightarrow s(y, K)</math>
end
end
end
Приведенный выше алгоритм извлекает узлы, для которых <math>p_{n-1}</math> имеет не пустое отображение, а затем рассматривает только узлы наборов, которые являются прямыми ”родителями” узла, и отображение этих "родителей" с помощью изоморфизма <math>p_{n-1}</math>. Поскольку эти наборы значительно меньше, чем наборы, рассмотренные ранее, шансы на то, что s вернет непустой результат, увеличиваются.
Применение.
Данный изоморфизм может использоваться для переноса восстановленной информации между различными дизассемблированными файлами, восстановления изменений, внесенных обновлениями безопасности и обнаружения кражи кода. Наиболее интересными применениями в области защиты информации является анализ вредоносных программ, поскольку анализ семейства троянов или вирусов может быть сведен к анализу различий между модификациями, и извлечении подробностей о уже установленных уязвимостях, в случаях когда разработчик обновления безопасности отказывается раскрывать детали.
BinSign[3]
Основной целью BinSign является предоставление точного и масштабируемого решения для снятия отпечатков двоичного кода. Данный алгоритм анализирует как структурные, так и семантические свойства. Для генерации отпечатка сначала извлекаются глобальные особенности функции такие как, количество и размер аргументов, константы, возвращаемое значения, строки, ссылки, количество базовых блоков. Далее на основе графа потока управления строятся tracelet’ы. Каждый tracelet состоит из пары связанных блоков, каждый из блоков обладает своими особенностями: количество инструкций, группы инструкций, константы, количество констант. Таким образом, учитываются структурные особенности. Далее генерируется отпечаток, пригодный для сравнения. Данный отпечаток имеет множество применений, таких как идентификация компилятора, идентификация библиотечной функции, анализ авторства, обнаружение клонов, обнаружение уязвимостей, анализ происхождения, обнаружение и классификация вредоносных программ и т.д.
Tracelet[4]
Алгоритм для вычисления сходства между функциями. Основная задача состоит в том, чтобы правильно определить понятие сходства, которое выходит за рамки прямого синтаксического сопоставления и способно находить измененные версии кода, а не только точные совпадения. Алгоритм основан на разложении функции в tracelets - краткий фрагмент трассы исполнения компьютерной программы, используемый в автоматизированных системах, пытающихся понять и оптимизировать исходный код. Для установления сходства применяется простой механизм перезаписи. Этот механизм выравнивает данные, чтобы сопоставить регистры и адреса памяти между tracelet'ами, устраняя различия между tracelet'ами, которые в остальном похожи.
Алгоритм для оценки сходства двух функций.
Рассмотрим общую структуру алгоритма сравнения (принцип работы используемых функций будет рассмотрен далее):
Input: <math>T, R</math>- функции, которые нужно сравнить (target, reference)
<math>NM</math>- метод нормировки
<math>k</math>- длина tracelet
<math>\alpha, \beta</math>- пороговые значения
Output: <math>IsMatch</math>- можно ли считать функции одинаковыми
<math>SimilarityScore</math>- оценка сходства
Alghoritm <math>FunctionsMatchScore( T, R, NM, k, \alpha, \beta)</math>
RefTracelets = ExtractTracelets(R,k)
TargetTracelets = ExtractTracelets(T,k)
MatchCount = 0
foreach <math>r \in RefTargets</math>do
foreach <math>t \in TargetSelects</math>do
AlignedInsts = AlignTracelets(r, t)
t' = RewriteTracelet( AlignedInsts, r, t)
S = CalcScore(r, t')
RIdent = CalcScore(r, r)
TIdent = CalcScore(t', t')
if <math>Norm(S, RIdent, TIdent, NM) > \beta </math>then
MatcCount++
end
end
SimilarityScore = MathCount / |RefTracelets|
IsMath = SimilarityScore <math>> \alpha</math>
Алгоритм начинается с разложения каждой из двух функций в набор из tracelet'ов длины k (функция ExtractTracelets). Мы рассматриваем каждый tracelet как ограниченную последовательность инструкций без промежуточных переходов. После того, как каждая функция была представлена в виде набора tracelet'ов, начинается попарное сравнения tracelet'ов. Сравнение производится следующим образом: сначала пары traceletов сравниваются с помощью функции AlignTracelets, затем t tracelet перезаписывается с учетом r. Сходство tracelet вычисляется с помощью функции CalcScore. Два tracelets считаются одинаковыми если их показатель сходства выше порогового значения <math>\beta</math>. Наконец, две функции считаются похожими, если их оценка сходства превышает пороговое значение <math>\alpha</math>.
Разложение функции на tracelets.
Tracelet извлекаются рекурсивно из узлов графа потока управления. Для того, чтобы извлечь все tracelet от определенного узла в графе потока управления, необходимо вычислить все tracelet от какого-либо дочернего узла, а затем использовать декартово произведение между узлом и вычисленными tracelet.
Input: <math>G = \langle B, E\rangle</math>- граф потока управления
<math>k</math>- длина tracelet
Output: <math>T</math>- список всех tracelet в графе
Alghoritm <math>ExtractTracelets(G, k)</math>
result = <math>\oslash</math>
foreach <math>b \in B</math>do
result <math>\bigcup=</math>Extract(b, k)
end
return result
Function <math>Extract(b, k)</math>
bCode = {stripJumps(b)}
if k = 1 then
return bCode
else
return <math>\bigcup_{\{ b'|(b, b') \in E\}}bCode\times Extract(b', k-1)</math>
end
Данный алгоритм использует вспомогательную функцию StripJumps. Эта функция принимает последовательность инструкций, в которой инструкция перехода может отображаться как последняя инструкция, и возвращает последовательность без инструкции перехода.
Алгоритм для оценки сходства двух tracelets.
В данном алгоритме каждая инструкция сборки рассматривается как буква (например, pop eax; является буквой). Составляется специальная таблица соответствий, которая на самом деле является мерой сходства между инструкциями сборки. При этом очень высокая оценка дается при идеальном совпадении.
Input: <math>T, R</math>- tracelets, которые нужно сравнить (target, reference)
Output: <math>Score</math>- оценка сходства данных tracelets
Alghoritm <math>CalcScore(T, R)</math>
A = InitMAtrix(|T|, |R|)
for <math>i = |T|; i > 0; i-- </math>do
for <math>j = |R|; j > 0; j-- </math>do
A[i, j] = Max(Sim(T[i], R[j]) + A[i+1, j+1],
A[i+1, j],
A[i, j+1])
end
end
Score = A[0, 0]
Сходство между инструкциями вычисляется с помощью следующей формулы: <math>Sim(c, c') =\begin{cases} 2 + |\{i|args(c)[i] = args(c')[i]\}|, & \text{ SameKind(c, c') } \\ -1, & \text{otherwise} \end{cases}</math>, где <math>c, c'</math>- инструкции, которые нужно сравнить. Мы вычисляем оценку, подсчитывая количество совпадающих аргументов, а также даем 2 «балла» за то, что «виды» совпадают. Если инструкции не совпадают, то формула возвращает отрицательный результат.
Перезапись заданного кода с учетом другого кода.
Для дальнейшего улучшения процесса сопоставления используется перераспределение аргументов и метод перезаписи.
Input: <math>AlignedInstr</math>- набор записей с выровненными инструкциями
<math>T, R</math>- tracelets, которые нужно сравнить (target, reference)
Output: <math>T'</math>- измененный код
Alghoritm <math>RewriteTracelet(T, R)</math>
foreach <math>(t, r) \in AlignedInsts </math>do
for <math>i = 1; i < |args(t)|; i++ </math>do
<math>s_t = args(t)[i] </math>
<math>s_r = args(r)[i] </math>
<math>nv = newVarName(s_t) </math>
<math>\varphi = \varphi \land (nv = s_r) </math>
if <math>s_t \in read(t) \ and \ lastWrite (s_t) \neq \perp </math>then
<math>\varphi = \varphi \land (nv = lastWrite(s_t)) </math>
else if <math>s_t \in write(t) </math>then
<math>lastWrite(s_t) = nv </math>
end
end
<math>vmap = solve(\varphi, symbols(R)) </math>
foreach <math>t \in T </math>do
<math>t' = t </math>
foreach <math>s_t \in t </math>do
if <math>(s_t) \in vmap </math>then
<math>t' = t'[s_t \mapsto vmap(s_t)] </math>
end
end
<math>T'.append(t') </math>
end
Сначала мы перебираем выровненные пары команд из T и R. Для каждой пары команд выполнено <math>|args(r)| = |args(t)|</math>(достигается путем применения AlignTracelets). Для каждой пары выровненных аргументов мы абстрагируем аргумент в T tracelet'e. Это делается с помощью newVarName, который генерирует уникальные имена временных переменных в соответствии с типом аргумента. Затем создаётся перекрестное ограничение между новой переменной и значением аргумента из r инструкции, которое добавляется к ограничению <math>\varphi</math>. После с помощью функции read(t) мы узнаем используется ли аргумент <math>s_t</math>для чтения. Затем алгоритм использует вспомогательную структуру данных lastWrite(<math>s_t</math>) для определения имени последней временной переменной, в которую записан аргумент <math>s_t</math>. Создается ограничение данных от последней записи в чтение. В противном случае, алгоритм с помощью функции write(t) проверяет является ли <math>s_t</math>командой записи и обновляет значение lastWrite(<math>s_t</math>). Наконец, после создания всех переменных и ограничений, вызывается функция solve, которая разрешит все конфликты и вернет минимальное решение, необходимое чтобы переписать tracelet.
Источники
