Получить список процедур.

DelAlt

Что вы имеете ввиду, что за проблема с адресом ?

 

Код (ASM):

1. foo:
2. dd 00C3C033h
3.  
4. start:
5.   call $+5
6.   pop  eax
7.   sub  eax, 9
8.   call eax   ; --> foo

EP на "start:", отсутствие ветвлений извне гарантируется. Как будем строить?

 

DelAlt

Этот адрес будет в карте CFG если собрать с данной опцией.

 

Indy_, карта в условия задачи не входит. Более того -- она здесь не нужна.

 

DelAlt,

Во первых невозможно этот код от данных отличить общим способом(только по дельтасмещению). Во вторых оно и не нужно, норм модуля такое не содержат.

 

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

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

 

DelAlt,

Я что то не вполне вас понимаю. Если все точки входа известны, то ваш вопрос бессмысленный, так как эта задача существует если вход не известен. Причём тут эмуляция тоже не ясно.

> ветвление по вычисленному в рантайме адресу

Часто вычисляется в динамике, через индексацию к примеру. Но что с того ?
У меня изначально суть задачи именно что бы не накапливать входы в динамике, так как это не профайл.

 

Indy_,
> Если все точки входа известны, то ваш вопрос бессмысленный, так как эта задача существует если вход не известен.
Вы говорите глупости, даже не пытаясь разобраться. Переходы в пределах покрываемой области не являются точками входа. Для кода, приведенного выше, точка входа одна: "start". По "foo:" изначально никакой информации не имеется.

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

> У меня изначально суть задачи именно что бы не накапливать входы в динамике.
Вы парсите .map-файл для отделения кода от данных. Это задача на написание текстового парсера, какое это имеет отношение к построению CFG?

 

DelAlt,

> Для кода, приведенного выше, точка входа одна: "start". По "foo:" изначально никакой информации не имеется.

Согласен, я просто про start подумал. Так как не суть важно(нет разницы) что нет ссылки непосредственно на процедуру или она вычисляется(ссылки так же не имеется).

> какое это имеет отношение к построению CFG?

Из за аббревиатуры путаница возникла. В PE есть карта, в которой помечаются начала процедур, которые есть в модуле. Это мс называет механизмом CFG. Есно оно не имеет отношения к построению графов. Я использовал входы, описанные в CFG(там не весь код описывается, тоесть что не вызывается косвенно там не нужно) для покрытия всего кода модуля.

С мап файлами сомнительный способ, во первых формат зависит от версии и в некоторых там не помечался код.

 

DelAlt,

> обеспечивая входные данные для частичной эмуляции контекста вокруг ветвлений.

Что это значит ?
Мне нужно решить следующее. Где то тут я вылаживал доку просто как интересную технику, залил есчо раз. У меня супервизор локальный и активно использует данный механизм. Адреса процедур заменяются через описанный метод. Но есть проблема, ссылка на процедуру может не использоваться непосредственно, к примеру она однократно передаётся к код инициализации(к примеру регистраци оконной процедуры) и далее эта процедура вызывается из вне. Посему до инициализации нужно найти процедуру. Даже если накопить список процедур в динамике, то не получится повторно выполнить инициализацию. Поэтому в статике изначально нужно это сделать. Вероятностный метод не подходит, так как приложение будет иногда крэшить.

 

Indy_,
>> обеспечивая входные данные для частичной эмуляции контекста вокруг ветвлений.
> Что это значит ?
Первоначальная идея заключается в интеграции эмуляции с алгоритмами построения CFG. Начнем с простейшего случая: нужная часть окружения определена непосредственно или доступна для вычисления с получением однозначного результата. Код приведенный выше -- это такой случай:

Код (ASM):

1. foo:
2. dd 00C3C033h
3. start:
4.   call  $+5
5.   pop  eax
6.   sub  eax, 9
7.   call  eax   ; --> foo

Для каждого неопределенного перехода (в данном случае "call eax") происходит рекурсивное построение графа потока данных (DFG, def-use chains) в обратном порядке (построение каждой цепочки начинается с use и завершается либо на def, либо когда упираемся в точку входа), тем самым определяя область для дальнейшей эмуляции. Алгоритм построения def-use примитивен, не будем углубляться, это лучше погуглить. Основное что нужно знать для понимания: def - инструкция модифицирующая переменную таким образом, что следующее значение переменной не зависит от предыдущего, другими словами def -- это начало dataflow-цепочки (для реверсивного обхода, в нашем случае, def прерывает цепочку). use-инструкция -- такая, для которой Vnext=f(Vprev). На нашем примере получаем:

1) call eax -- неопределенный переход обнаружен, адрес в eax;
2) начинаем построение def-use-цепочки в обратном порядке, рекурсивно инициируя новую цепочку для всех переменных, связанных с данной:

• eax:
  Код (ASM):

  1.   def: pop eax     ;  ^
  2.   use: sub eax, 9  ;  |
  3.   use: call eax    ;  |
• доходим до "pop eax" -- это одновременно def-инструкция по eax (завершаем цепочку по eax) и (неявно) use-инструкция для верхушки стека (раскладывается в две переменных -- значение esp и в свою очередь адресуемое через esp значение, для простоты здесь примем за одну переменную: адресуемое значение -- [esp]); инициируем def-use chain для [esp];
  
• [esp]:
  Код (ASM):

  1.   def: call $+5  ;  ^
  2.   use: pop eax   ;  |
  call $+5 является def-инструкцией для переменной, значение которой записано в вершине стека и завершает вторую цепочку.

3) пересечение полученных последовательностей и есть область, необходимая к эмуляции для уточнения интересующего нас перехода ("call eax"): в нашем случае это область в пределах одного базового блока от "call $+5" до "call eax" включительно;

4) т.к. мы еще в рамках самого примитива, то работаем с простым эмулятором (только определенные значения), соответственно для нашего примера начальные значения EIP и ESP заданы эмулятором произвольно, но определены (!). эмулируя в пределах полученной области, очевидно, что на "call eax" в eax мы имеем адрес "foo:", что позволяет покрыть:

Код (ASM):

1. foo:
2. dd 00C3C033h
3.     ; -->
4. foo:
5.   xor eax, eax
6.   ret
7.   db 00
8.  

Алгоритм определения области для частичной эмуляции остается (если не считать возможные оптимизации) неизменным. Но для решения задачи в более общем виде, с возможностью применять данную технику в сложных случаях, понадобится эмуляция на частично определенном контексте. Идея сходная с VRP (value range propagation), работающие варианты реализации можно найти в современных оптимизирующих компиляторах (варианты, реализованные для SSA /LLVM/clang/ не должны смущать, т.к. сам принцип работы остается тем же) и по сути VRP и является, за одним только главным отличием, что здесь используется не для оптимизирующих преобразований, а для частичного определения контекста при построении CFG. Простыми словами, нужен эмулятор, умеющий в диапазоны значений (классический VRP) и поддерживающий сохранение символического компонента переменной. Например:

Код (ASM):

1.  
2.     ; eax = ?
3.     ; esi = ?
4. movzx eax, word ptr [esi]
5.     ; eax = 0..FFFF
6. shr eax, 6
7.     ; eax = 0..3FF
8. cmp eax, ...
9. jX ...
10.  

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

Код (ASM):

1.  
2.     ; ecx = ?x
3. mov eax, ecx
4.     ; ecx = ?x
5.     ; eax = ?x
6. not eax
7. add eax, 8
8.     ; ecx = ?x
9.     ; eax = -?x-1+8
10. ...
11. ...
12. add eax, ecx
13.     ; eax = 7
14.  

Начиная с этого момента можно смотреть в сторону интеграции эмулятора с SMT-солверами, т.к. хотя бы уже примерно видно куда это можно вкручивать, чтобы не переизобретать велосипеды.

 

DelAlt

Вы упускаете одну деталь. В ваших примерах есть непосредственно ссылка на код в виде ветвления, которая однозначно говорит что по ссылке код. Если же будет манипуляция адресом, к примеру он будет передан в апи, то тут такие способы не сработают. Так как не известно является ли значение ссылкой(если нет релока), либо что по ссылке код - для этого нужно его корректность проверить. Для кода малого размера это не сработает. Я приводил уже пример https://exelab.ru/f/index.php?action=vthread&forum=6&topic=24488&page=0#8
Но там проверки основаны на релоках и простой проверке на корреляции в графе(пересечение инструкций). Хотя при таком подходе весьма эффективно получается.

 

DelAlt

> Простыми словами, нужен эмулятор, умеющий в диапазоны значений (классический VRP) и поддерживающий сохранение символического компонента переменной.

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

 

Indy_,
> Если же будет манипуляция адресом, к примеру он будет передан в апи, то тут такие способы не сработают. Так как не известно является ли значение ссылкой...
Стек эмулируется, рекурсивно покрытие кода API, резолв неопределенного вызова callback'а по технике выше.

> Так понимаю эти ллвм етц не нэйтивные, тоесть это нельзя собрать в нэйтивную длл и заюзать когда нужно.
Не понимаю. Какие dll, что юзать? Это компиляторы, из них нам интересно посмотреть вживую какие алгоритмы работают. Вы хотите выдернуть себе кусок LLVM и унести в dll? Это было для примера, чтобы посмотреть как некоторые алгоритмы реализованы и работают, как строится DFG, как диапазоны значений распространяются на графе, например: https://github.com/gcc-mirror/gcc/blob/master/gcc/tree-vrp.c

> Так как это всё очень толстая система и соответственно медленная и главное - анстаб получится.
Здесь интересно бы увидеть аргументацию. Покажите ваши прикидки по размеру и временной сложности.

 

DelAlt

> Стек эмулируется, рекурсивно покрытие кода API, резолв неопределенного вызова callback'а по технике выше.

Покажите на примере, совершенно не понятно о чём вы говорите. Допустим у нас есть код:



Это регистрация класса в гуе в блокноте. Фиксапов в нём не имеется. CFG карты нет тоже. Никакой инфы про данный адрес. Можно только по контексту догадаться что это адрес процедуры. Какой резолв может есчо быть или эмуляция, если этот адрес сохраняется далее в стуктурах ядра и через них, через сложный механизм колбеков гуя будет в дальнейшем вызван. Поменять мы его тоже не можем(если определить в динамике, то это ничего не даст - переопределить его нельзя). Остаётся только аналитически определить что это адрес и по этому адресу находится код.

> Это было для примера, чтобы посмотреть как некоторые алгоритмы реализованы и работают, как строится DFG

DFG построить простой не составляет проблемы. Для этого не нужны какие то алгосы, есчо и от компилятора. И я не пишу компилятор

 

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

> Какой резолв может есчо быть или эмуляция, если этот адрес сохраняется далее в стуктурах ядра и через них, через сложный механизм колбеков гуя будет в дальнейшем вызван.
Вы делаете логические ошибки, результат которых приписываете мне и требуете его объяснить. И мне кажется, что в этом процессе мое участие не требуется. Найдите самостоятельно где говорилось о полной универсальности метода и построении CFG для кода, который недоступен в процессе анализа. После того как найти не получится, есть вероятность что стоит подумать кому на самом деле надо задать уточняющие вопросы и кому надо внимательнее читать, перед тем как критиковать

Если при построении вершина не может быть определена, то варианты: или заменять ее простой
заглушкой, состоящей из вызова калбека, которая укажет анализатору как продолжать строить покрытие, или эвристика, или же оставлять ее неопределенной. Разве это не очевидно?

> DFG построить простой не составляет проблемы. Для этого не нужны какие то алгосы, есчо и от компилятора. И я не пишу компилятор.
Это понятно, вы пишете парсер .map-файлов.

 

DelAlt

> Уверен что вы не могли сделать подобный вывод с потолка

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

> Вы делаете логические ошибки, результат которых приписываете мне и требуете его объяснить.

Нет, просто я говорю об одном, вы же что то не совсем по теме отвечаете. Вот я вам привёл реал пример со скрином даже.

> Это понятно, вы пишете парсер .map-файлов.

Не, я же говорил что это не пригодный способ. Помимо того, что не ясно как там с маркерами кода, получается такой способ не порт на другие компили, к примеру дельф или иной. CFG-карты хороший способ, но это тоже компилер специфическое. С COFF не получится, так как маркеры кода содержатся только в дебаг инфе.

 

Вот нашёл доку по теме. Там тоже корректность кода вероятностным путём проверяется.

 

Indy_,
мне сложно продолжать, вы не держите контекст и делаете выводы, противоречащие логике. Если это сознательно, то кормить троллей желания тем более никакого. Еще раз:

> А учитывая вес кода по вашей ссылке на гх, это вообще не юзабельно.
Повторю: приведенный код из GCC -- реализация для посмотреть, для общего понимания того что подобные вещи уже есть и используются, причем давно. Не надо идти дальше и сравнивать объем кода в модуле оптимизирующего компилятора из абсолютно конских масштабов проекта с тем, что я предложил к использованию для покрытия. Вы понимаете разницу?

> Нет, просто я говорю об одном, вы же что то не совсем по теме отвечаете. Вот я вам привёл реал пример со скрином даже.
Если убрать воду, то вы описываете момент, при котором нет возможности проанализировать часть кода (передается адрес потенциального callback'а, но обнаружить переход по этому адресу или доказать отсутствие такого перехода не представляется возможным). Ответ был и по теме. Ключевые слова для поиска в предыдущем сообщении: "вершина", "не", "определена", "пивная", "еще парочку".

 

DelAlt

> нет возможности проанализировать часть кода

Получается если методы ваши(DFG etc) не работают на элементарной загрузке указателя, то какой практический смысл обрабатывать более сложные конструкции, как например выше вы приводили. Академического интереса ради только. Но проблема у меня практическая.

> для общего понимания того что подобные вещи уже есть и используются

Я это спрашивал на кряклабе по ссылке которую приводил. Там тоже какую то лабуду писали про солверы

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