wanted tool: point_in_trace --> call_graf / stack_trace

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

Спасибо!

 

mrCyber
бектрейс. Алго тут лежит. Описание его масмом тоже.

 

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

Во-вторых, я это слово знал и ранее. Поиск по форуму по 'backtrace' что-то и дал, но я не знаю, что именно в итоге вы имели в виду. Если же такой вопрос задать гуглу - тот и вовсе завалит вариантами ответов..... Легче написать парсер трассы, чем разгребать эти кучи.

Не могли бы вы чуточку дополнить/прояснить свой ответ. Что вы имели в виду? Плагин? Скрипт? Инструмен? Алгоритм? Подход? Утилиту?

Спасибо еще раз!

 

mrCyber
По поводу алгоритма
Формируем из трассы исполнения блоки(группа инструкций в средину которых нет переходов) инструкций, они будут узлами графа.
А дальше из этого создаем ребра графу и свободно используя стандартные алгоритмы работы с графами находим "последовательность вызовов, которые привели в эту точку".

 

XshStasX
За сегодня я уже нашел в сети неск. дост. подробных трудов о том, как анализируют и разбирают код.

К примеру
http://www.site.uottawa.ca/~tcl/gradtheses/ahamou/AbdelwahabHamouLhadjPhDThesis.pdf
http://static.usenix.org/events/vee06/full_papers/p154-bhansali.pdf

Тема, безусловно, очень интересная. Я бы может был бы и рад погрузиться во все это и написать даже какой-то тул, но увы, не могу себе этого позволить. У меня сейчас задача реверса и разбора кода, а точнее понимание, как работает одна утилита - стоит как стопер на пути к решению другой задачи. И я все дальше ухожу от основной цели в сторону и зарываюсь в попутные проблемы. Мне нужно что-то предельно простое и/или готовое. О чем и вопрошал.

Если я в ближайшие сутки ничего не найду, то я просто напишу выкидывалку из трассы всех инструкций, кроме 'call ...' и 'retn ...' и дальше глядя на эту простыню уже смогу сообразить и представить цепочку вызовов. То есть в пределе меня устроит даже такой быстрый и грязный способ. Но все же решил сперва спросить у Знающих- вдруг есть что-то куда более толковое.

В любом случае Спасибо!

 

stack-backtrace walker есть в любом отладчике, но работает он не с трассами, а со стеком. В общем, бракнуться на интересующем месте и просмотреть этот самый backtrace. Он покажет вам адреса возврата из функций - для функций в которых есть stack-frame, то есть у которых есть в начале

Код (Text):

1. push    ebp
2. mov     ebp, esp

Если принципиально работать с трассами, то только писать свои скрипты для разбора. Тоже ничего сложного и не так как написал XshStasX. От интересующего места вверх ищете пары ret/retn, call - это будут вызовы/возвраты функций внутри текущей функции, если первой встречается call - это и есть вызов текущей функции. Если 2 раза подряд встречается call без ret между ними - значит это функция тоже относится к вашей последовательности вызовов.

Как-то так.

 

http://www.wasm.ru/forum/viewtopic.php?pid=458955#p458955

 

samuraishowdown
Объясни на примере алгоритм

Это трасса исполнения

Нужно вывести цепочку вызовов которая приводит к call memcpy .

 

XshStasX
Я ответил и вам и тс, что есчо нужно ?

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

 

Интересно как без графа используя только трассу исполнения и "пары ret/retn, call " найти цепочку ?
В примере выше(#8) нету ни одного ret/retn.

 

XshStasX

Никак. Код не линейный.

 

Да, мне тоже этот код не кажется реальным. Да, такое все же наверно может быть в реальности, но обычно трассы так не выглядят.

Ну а если трасса именно такая, то:
call entrypoint --> call NtApi --> call sub_routine --> call my block.
А какие еще вар-ты возможны для этого случая?

Вообще, мне кажется, что если за неск. суток на мой вопрос не появилось ни одного ответа отличного, от обсуждения, _как_решить_ такую задачу - то, пожалуй, вопрос закрывается. Мне нужен был готовый инструмент, что в топике предельно ясно и обозначено. Типа тех, что упоминаются в трудах, ссылки на кот. я привел в #5.

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

Спасибо еще раз всем откликнувшимся!

 

mrCyber
Вас не устраивает алго по ссылке, нужен готовый юзабельный код ?

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

 

Malfoy
В том то и дело, что писать код - в данном случае я не оч. хотел бы. У меня дохрена работы и помимо написания кода для таких задач, встречающихся по ходу решения основных. Нужен готовый тул. Говорите есть и надо врубиться, как работает? Ну скажите, что это за зверь - попробуем Если понимание как им пользоваться не превысит времени написания своего кода - то наверно уж раскурю как-нибудь

 

mrCyber
А ведь забавно, у вас времени нет и поэтому я должен за вас код запилить, причём псевдокод вам дан. Такие вопросы в комерсе задают товарищ.

 

Malfoy
Сорри, у меня такого и в мыслях не было. Значит я просто не правильно понял ваши слова. Нет, спасибо. Я писать и сам умею - но это время, которого у меня нет. Цена времени мне хорошо известна, так что от других подобных жертв я тоже не жду.
И конечно же тут никто никому ничего не должен Даже думать забудьте.

 

Если вам нужно получить лог выполнения всех функций, в том числе и тех из которых произошёл возврат, то это не stack-backtrace (call entrypoint --> call NtApi --> call sub_routine --> call my block - а вот это именно он и есть).

Если бы трасса была такой:

Код (Text):

1. call entrypoint
2.  
3. @entypoint:
4.   mov eax,ecx
5.   xor eax,eax
6.  
7. ;--------------------------------------------
8. call func
9. @func:
10. xor eax, eax
11. ret
12. ;--------------------------------------------
13.  
14.   je L1
15.    // здесь код не был выполнен - сработал переход на L1
16. L1:
17.   call NtApi
18.   push eax
19.   call sub_routine
20.   add esp,4
21.   test eax,eax
22.   jz @entypoint
23.   push esi
24.   push edi
25.   push ecx
26.  call my block
27.  
28.   cmp [esp+4],0
29.  jz L3
30.   call memcpy

Stack-backtrace был бы всё равно таким-же call entrypoint --> call NtApi --> call sub_routine --> call my block. Потому что в функу func был заход, но был и выход. То есть эту пару call/ret мы пропускаем.

В общем вы определитесь - вам нужен stack-backtrace или control flow трассировка.
Если второе: нужно из трассы выкинуть лишнее (всё кроме call/ret, можно ещё jxx) или написать скрипт для трассировщика который сохраняет в лог только control flow инструкции. Зачем тут графы - мне не понятно. Вы же не бинарный код дизассемблируете.

Ещё вспомнил. Если осилите сохранять лог трассировки в формате утиля Kcachegrind - он вам покажет вызовы функций визуально, найдет циклы, может ещё чего полезного даст.

Чёта у меня ещё сомнение закралось - так у вас трассировка полная или без захода в некоторые функи, api-шки?

Malfoy

Базару нет. Только у ТСа не код, а трасса

 

samuraishowdown
Такая траса это тоже граф, так как там тоже есть разделение по уровням вложенности(NL), тоесть понятие процедуры не меняется. Участок графа будет иметь некоторый NL(после поднятия NL, раскрытием ветвления любой дальнейший код соответствует уровню вложенности, а просто по коду это определить нельзя), после раскрытия процедурного ветвления. Проход по графу выполняется с его учётом. А это значит что нужно каким то образом пропустить ветвления в пределах некоторого NL. В любом случае получается проход обратный по графу. Далее из за механизма колбеков из ядра(APC, XCPT, apfn). Траса будет весьма замудрёной, попробуйте потрейсить какой нибудь сервис шадова, к примеру создание окна - будет множество рекурсивных вызовов, причём только по вхождению в проекцию это не отфильтровать - KiCallbackReturn дёргается например из User32.

 

Malfoy
Если трейсит в юзермоде, через прерывание int 1, а все отладчики так и делают. Никаких калбеков из ядра вы в этой трассе не увидите. Скорее всего - если калбек, который не вернёт управление на след. инструкция после например sysenter где-то встретится, то программа "выпрыгнет" из под трассировки, и никакой трассы вы вообще не получите. А трасса у ТСа есть - это факт.

И трасса эта линейна. Граф нам не нужен. Если хочем получить stack-backtrace из трассы (хотя проще это сделать из стека, брякнувшись в отладчике в нужном месте), то от интересующего места ищем вверх первый попавшийся call или ret. Если это call - то это уровень вложенности с NL-1 - это нам нужно и это мы запоминаем. Если это ret, то ищем следующие ret или call, пока количество call < количества ret - NL+... больше чем нам нужно, всё это пропускаем. Когда количество ret-ов, call-ов сравнялось и снова встретился call - значит мы снова поднялись на 1 уровень NL - снова запоминаем адрес этой функи - она относится к stack-backtrace. И так по кругу до самого начала трассы.

Трасса линейна. Граф не нужен.

 

samuraishowdown
Граф позволяет пройти обратно по ссылкам. В графе будет к примеру [Line1][Call][Line_Sub]...[Ret][Line2]. Имея описатель [Ret] мы можем раскрыть две обратные ссылки и получить [Line1]. В вашей этой трасе как это сделать, сканить её назад ?