Apline - Logo

FLIRT - Fast Library Identification and Recognition Technology

  1. Цель
  2. Трудности
  3. Идея
  4. Реализация
  5. Результаты

Цель

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

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

С другой стороны, каждая программа на языке высокого уровня использует достаточно большое количество стандартных библиотечных функций, процент которых в теле программы может достигать до 95%. Например, если взять всем известную программу "Hello, world!":

	библиотечных функций	-	58
	функция main()		- 	1
Конечно, это вырожденный случай тривиальной программы, но обычно где-то половина (50%) кода программы - библиотечные функции. Из-за этого пользователю дизассемблера приходится тратить больше половины времени на разбор библиотечных функций. Именно больше половины, т.к. анализ программы в чем то схож с решением кроссвордов. При решении кроссвордов: чем больше букв известно, тем более высока вероятность, что мы отгадаем следующее слово. При дизассемблировании: чем больше комментариев и осмысленных имен в функции, тем быстрее мы поймем, что функция делает.

Широкое применение готовых библиотек, таких как OWL, MFC и подобные, еще больше увеличивают долю стандартных функций в программе. Средняя программа, например для Win32, написанная на C++ с применением современных технологий (т.е. с использованием AppExpert и иже с ним) использует 1000-2500 библиотечных функций одновременно.

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

  • мы не ставим своей целью распознать 100% всех функций. Это невозможно теоретически и более того, возможность распознать функцию может приводить к нежелательным последствиям. Например, не имеет смысла распознавать функцию
    	  	push	bp
    		mov	bp, sp
    		xor	ax, ax
    		pop	bp
    		ret
    
    т.к. вероятность неправильного распознавания слишком велика (любопытно, что в современных С++ библиотеках встречается немало таких функций, абсолютно одинаковых байт-в-байт, но с разными именами).
  • мы распознаем и даем имена только функциям (кодовый сегмент), игнорируя при этом данные (сегмент данных).
  • если функция успешно распознана, то мы присваиваем ей имя и/или комментарий. Получение информации о типах входных/выходных аргументов, о поведении функции и о том, что эта функция делает, не ставится как цель.
  • процент неправильно распознанных функций должен быть сведен к минимуму, т.к. неправильно распознанная функция хуже нераспознанной. В идеале неправильно распознанных функций не должно быть.
  • распознавание функций должно требовать минимума ресурсов процессора и по памяти.
  • алгоритм должен быть платформенно-независимым, т.е. должна работать с программами, скомпилированными для любого процессора.
  • при возможности определить функцию main(), т.к. startup-code, взятый из библиотеки, не представляет интереса.

Трудности

Основная трудность заключается в количестве функций и об'еме памяти, занимаемой ими. Если подсчитать общий об'ем библиотек всех версий всех моделей всех популярных производителей компиляторов, то мы запросто перевалим за гигабайты. Если же к этому прибавить периодически выходящие исправления, библиотеки типа OWL, MFC, BFC и иже с ними, то об'ем просто нереален. Пока пользователи персональных систем не могут себе позволить выделять такие об'емы под простую утилиту - дизассемблер, необходимо придумать алгоритм сжатия информации, необходимой для распознавания библиотечных функций. Также количество функций заставляет задуматься о времени распознавания. Простой перебор функций и сравнивание не годятся.

Следующая трудность заключается в наличии изменяемых при загрузке программы в память байтов. В основном изменяемые байты происходят из-за наличия ссылок на внешние имена. В таком случае при компиляции программы компилятор еще не знает адреса вызываемой функции и оставляет эти байты равными нулю, записывая в выходной файл так называемую fixup information. (Иногда эту таблицу называют relocation table, relocation information). Например, отрывок из листинга ассемблерной программы

B8 0000s                               mov     ax, seg _OVRGROUP_
9A 00000000se                          call    _farmalloc
26: 3B 1E 0000e                        cmp     bx, word ptr es:__ovrbuffer
содержит изменяемые байты.

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

Также бывают линкеры, которые позволяют себе менять даже те байты об'ектного кода, у которых нет fixup information. Они это делают для ускорения выполнения программы. Например:

	     	0000: 9A........	call	far ptr xxx
превращается в
	        0000: 90		nop
	     	0001: 0E		push	cs
		0002: E8....		call	near ptr xxx

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

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

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

Еще один вид функций, представляющих определенную трудность при распознавании - это функции вида

		call	xxx
		ret
или
		jmp	xxx
На первый взгляд эти функции неинтересны, но вы удивитесь, узнав, сколько таких стандартных функций у вас в библиотеках. Например, BCC OS/2 v1.5 содержит 20 таких функций, среди них такие часто используемые как read(), write() и т.д. Побайтное сравнение таких функций не дает практически ничего, т.к. в любой библиотеке найдется десяток другой таких функций, отличающихся только тем, какую функцию они вызывают.

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

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

Идея

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

Все информация для распознавания функций хранится в сигнатурном файле. Каждая функция представляется шаблоном. Шаблон - это первые 32 байта функции с пометкой всех изменяемых байтов. Например:

558BEC0EFF7604..........59595DC3558BEC0EFF7604..........59595DC3 _registerbgidriver
558BEC1E078A66048A460E8B5E108B4E0AD1E9D1E980E1C0024E0C8A6E0A8A76 _biosdisk
558BEC1EB41AC55604CD211F5DC3.................................... _setdta
558BEC1EB42FCD210653B41A8B5606CD21B44E8B4E088B5604CD219C5993B41A _findfirst
изменяемые байты обозначены как ".."

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

558BEC
      0EFF7604..........59595DC3558BEC0EFF7604..........59595DC3 _registerbgidriver
      1E
        078A66048A460E8B5E108B4E0AD1E9D1E980E1C0024E0C8A6E0A8A76 _biosdisk
      B4
        1AC55604CD211F5DC3                                       _setdta
        2FCD210653B41A8B5606CD21B44E8B4E088B5604CD219C5993B41A   _findfirst
(приведен маленький кусочек реального дерева). В узлах дерева хранятся последовательности байт. В данном примере корень дерева содержит последовательность "558BEC", от него растут 3 ветки, начинающиеся соответственно на 0E, 1E, B4. Ветка B4 в свою очередь содержит ссылки на две ветки. Каждая ветвь заканчивается листьями. В листе хранится информация о функции - на этом рисунке показано только имя функции.

Построение дерева позволяет достичь двух целей одновременно:

  • мы сэкономили память, сохранив совпадающие начала функций в одном экземпляре. При этом чем больше похожих функций, тем больше будет выигрыш.
  • у нас появилась возможность быстрого сопоставления - количество сравнений, необходимых для сопоставления адреса в программе с базой сигнатур, находится в логарифмической зависимости от количества функций.
Принимать решение на основе первых 32 байт было бы по крайней мере безответственным делом, к тому же в реальных библиотеках встречаются функции, начинающиеся одинаково:
558BEC
      56
        1E
          B8....8ED8
                    33C050FF7608FF7606..........83C406
                                                      8BF083FEFF
	            0. _chmod	(20 5F33)
	            1. _access	(18 9A62)
Судя по всему эти функции отличаются после первых 32 байт. Поэтому они попали в один и тот же лист нашего дерева. В таком случае мы сосчитаем CRC16 от 33го байта до первого изменяемого байта и сохраним в сигнатурном файле. Нам также придется сохранить длину участка, по которому вычислялся CRC16, т.к. для разных функций эта длина разная. В вышеприведенном примере для функции _chmod CRC16 вычислялся по 20 байтам: 33..52; тогда как для функции _access CRC16 вычислялся по 18 байтам. Возможен неблагоприятный вариант расположения изменяемых байт в программе сразу же после первых 32 байтов. В вырожденном случае (когда 33й байт является изменяемым) длина участка для вычисления CRC16 может равняться нулю. Однако, как показывает опыт сопоставления, этот алгоритм работает устойчиво и дает очень малый процент ошибок.

К сожалению, иногда встречаются функции, имеющие одинаковые первые 32 байта и дающие одинаковый CRC16. Например:

... (начало пути в дереве не показано)
  	05B8FFFFEB278A4606B4008BD8B8....8EC0
    	  0. _tolower (03 41CB) (000C:00)
    	  1. _toupper (03 41CB) (000C:FF)
Нам не повезло: участок для подсчета CRC16 оказался коротким (всего 3 байта) и CRC16 у обеих функций совпал. В этом случае мы пытаемся найти позицию, в которой эти функции отличаются друг от друга (в нашем примере это позиция 32+3+000C).

Hо и этот метод не всегда позволяет отличить функции друг от друга. Hиже приведен пример:

... (начало пути в дереве не показано)
                0D8A049850E8....83C402880446803C0075EE8BC7:
                  0. _strupr (04 D19F) (REF 0011: _toupper)
                  1. _strlwr (04 D19F) (REF 0011: _tolower)
Эти функции совпадают байт-в-байт по неизменяемым байтам и отличаются только вызываемыми функциями. В этом случае единственный способ отличить эти функции - посмотреть, куда ссылается инструкция, находящаяся по 11у байту.

Недостаток такого метода заключается в том, что для опознания функций _strupr и _strlwr необходимо, чтобы функции _toupper или _tolower уже были распознаны и получили правильные имена. Это означает, что при неудаче сопоставления из-за отсутствия ссылки на _toupper или _tolower мы должны отложить сопоставление на более позднее время и повторить попытку после нахождения этих функций. Это делает алгоритм многопроходным, но к счастью второй и последующие проходы требуется применять для очень малого количества потенциальных библиотечных функций.

И наконец, функции могут совпадать байт-в-байт, ссылаться на одни и те же внешние имена, но называться по разному. Как ни странно, это часто встречается в библиотеках, особенно для С++. Такая ситуация называется коллизией (т.е. коллизия - это когда функции в листе дерева неотличаемы друг от друга применением вышеприведенных методов). Классический пример:

558BEC1EB441C55606CD211F720433C0EB0450E8....5DCB................
   0. _remove (00 0000)
   1. _unlink (00 0000)
или
8BDC36834702FAE9....8BDC36834702F6E9............................
   0. @iostream@		(00 0000)
   1. @iostream_withassign@ (00 0000)
Тут без искусственного интеллекта не обойтись :) Hо т.к. мы поставили себе целью эффективный и быстрый алгоритм, то искусственный интеллект мы оставим для будущего развития алгоритма.

Реализация

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

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

Для автоматического определения компилятора, использованного при написании программы и соответственно нужного сигнатурного файла сделаны специальные сигнатурные файлы, применяемые к точке входа в программу. Эти сигнатурные файлы называются startup-сигнатурами. Вышеприведенный алгоритм успешно различает startup модули всех популярных производителей компиляторов. При этом не требуется различать модели (small,compact,medium,large,huge) библиотек и версии компиляторов, т.к. все функции хранятся в одном сигнатурном файле и достаточно определить правильный сигнатурный файл - остальное берет на себя вышеприведенный алгоритм.

Существуют отдельные startup-сигнатуры для каждого формата дизассемблируемого файла. Для программ под управлением MS DOS используется сигнатура exe.sig, под OS/2 - lx.sig или ne.sig и т.д.

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

Ввиду того, функции из <ctype.h> являются короткими и ссылаются на массив типов символов, было решено обработать ссылки на этот массив как исключительный случай. Для этого в сигнатурном файле хранится CRC16 массива типов символов.

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

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

Создание сигнатурного файла происходит в 2 этапа: обработка библиотек и формирование сигнатурного файла. В первом этапе используется программа parselib - она обрабатывает *.obj и *.lib файлы. При этом формируются pattern-файлы, в которых содержатся шаблоны функций, имена, CRC16 и вся остальная информация, необходимая для построения сигнатурного файла. Hа втором этапе утилита sigmake создает сигнатурный файл из pattern-файлов.

Разделение на 2 этапа сделано для независимости программы sigmake от формата входного файла. В будущем возможно написание программ для обработки файлов, отличающихся от *.obj или *.lib

Было принято решение компрессировать (используя алгоритм InfoZip) получившиеся сигнатурные файлы для уменьшения об'ема необходимого дискового пространства для их хранения.

Для удобства работы пользователя была предпринята попытка распознавания функции main() в программе. Алгоритм нахождения этой функции отличается у разных компиляторов и у разных типов программ (DOS/OS2/WinDows/GUI/Console...), поэтому он записывается в сигнатурный файл виде текстовой строки. К сожалению составление этого алгоритма неавтоматизировано и трудоемко.

Результаты

Как оказалось, сигнатурные файлы очень хорошо ужимаются - более, чем в 2 раза. Причиной этому является то, что они практически на 95% состоят из имен функций. (пример: сигнатура для mfc 2.x до ужатия занимала почти 2.5мб, после - 700кб, при этом там содержится информация для распознавания 33634 функций; в среднем 21 байт на функцию)

Вообще, если сравнить об'ем исходных библиотек с об'емом сигнатурных файлов, то соотношение получается от 100 до 500 раз.

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

	jmp	off_1234
что наиболее радует, неправильно распознанных функций не было замечено вообще. Правда это не означает, что их нет.

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

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

(c) Copyright 1997 by Ilfak Guilfanov and Datarescue.
Reproduction without permission is forbidden

Apline LLC
107140, Москва,
ул. Краснопрудная, д.12/1, стр. 1, пом. 15

Тел: (495) 724-75-82