FLIRT - Fast Library Identification and Recognition Technology

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

Цель

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

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

	библиотечных функций	-	58
	функция main()		- 	1

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

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

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

  	  	push	bp
  		mov	bp, sp
  		xor	ax, ax
  		pop	bp
  		ret
  

  т.к. вероятность неправильного распознавания слишком велика (любопытно, что в современных С++ библиотеках встречается немало таких функций, абсолютно одинаковых байт-в-байт, но с разными именами).
• мы распознаем и даем имена только функциям (кодовый сегмент), игнорируя при этом данные (сегмент данных).
• если функция успешно распознана, то мы присваиваем ей имя и/или комментарий. Получение информации о типах входных/выходных аргументов, о поведении функции и о том, что эта функция делает, не ставится как цель.
• процент неправильно распознанных функций должен быть сведен к минимуму, т.к. неправильно распознанная функция хуже нераспознанной. В идеале неправильно распознанных функций не должно быть.
• распознавание функций должно требовать минимума ресурсов процессора и по памяти.
• алгоритм должен быть платформенно-независимым, т.е. должна работать с программами, скомпилированными для любого процессора.
• при возможности определить функцию main(), т.к. startup-code, взятый из библиотеки, не представляет интереса.

Трудности

Следующая трудность заключается в наличии изменяемых при загрузке программы в память байтов. В основном изменяемые байты происходят из-за наличия ссылок на внешние имена. В таком случае при компиляции программы компилятор еще не знает адреса вызываемой функции и оставляет эти байты равными нулю, записывая в выходной файл так называемую 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

Вообще, все короткие функции (состоящие из 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
      56
        1E
          B8....8ED8
                    33C050FF7608FF7606..........83C406
                                                      8BF083FEFF
	            0. _chmod	(20 5F33)
	            1. _access	(18 9A62)

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

... (начало пути в дереве не показано)
  	05B8FFFFEB278A4606B4008BD8B8....8EC0
    	  0. _tolower (03 41CB) (000C:00)
    	  1. _toupper (03 41CB) (000C:FF)

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

... (начало пути в дереве не показано)
                0D8A049850E8....83C402880446803C0075EE8BC7:
                  0. _strupr (04 D19F) (REF 0011: _toupper)
                  1. _strlwr (04 D19F) (REF 0011: _tolower)

Недостаток такого метода заключается в том, что для опознания функций _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)

Реализация

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

Для автоматического определения компилятора, использованного при написании программы и соответственно нужного сигнатурного файла сделаны специальные сигнатурные файлы, применяемые к точке входа в программу. Эти сигнатурные файлы называются 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...), поэтому он записывается в сигнатурный файл виде текстовой строки. К сожалению составление этого алгоритма неавтоматизировано и трудоемко.

Результаты

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

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

	jmp	off_1234

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

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

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