wanted tool: point_in_trace --> call_graf / stack_trace

Тема в разделе "WASM.RESEARCH", создана пользователем mrCyber, 2 мар 2012.

  1. mrCyber

    mrCyber New Member

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

    Спасибо!
     
  2. Malfoy

    Malfoy New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2012
    Сообщения:
    698
    mrCyber
    бектрейс. Алго тут лежит. Описание его масмом тоже.
     
  3. mrCyber

    mrCyber New Member

    Публикаций:
    0
    Регистрация:
    29 дек 2011
    Сообщения:
    42
    Malfoy
    Во-первых, спасибо за ответ. По кол-ву просмотров/ответов я уж начал думать, что хочу чего-то ненормального.

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

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

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

    XshStasX New Member

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

    mrCyber New Member

    Публикаций:
    0
    Регистрация:
    29 дек 2011
    Сообщения:
    42
    XshStasX
    За сегодня я уже нашел в сети неск. дост. подробных трудов о том, как анализируют и разбирают код.

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

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

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

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

    samuraishowdown New Member

    Публикаций:
    0
    Регистрация:
    6 мар 2011
    Сообщения:
    70
    stack-backtrace walker есть в любом отладчике, но работает он не с трассами, а со стеком. В общем, бракнуться на интересующем месте и просмотреть этот самый backtrace. Он покажет вам адреса возврата из функций - для функций в которых есть stack-frame, то есть у которых есть в начале
    Код (Text):
    1. push    ebp
    2. mov     ebp, esp
    Если принципиально работать с трассами, то только писать свои скрипты для разбора. Тоже ничего сложного и не так как написал XshStasX. От интересующего места вверх ищете пары ret/retn, call - это будут вызовы/возвраты функций внутри текущей функции, если первой встречается call - это и есть вызов текущей функции. Если 2 раза подряд встречается call без ret между ними - значит это функция тоже относится к вашей последовательности вызовов.

    Как-то так.
     
  7. Malfoy

    Malfoy New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2012
    Сообщения:
    698
  8. XshStasX

    XshStasX New Member

    Публикаций:
    0
    Регистрация:
    9 авг 2008
    Сообщения:
    991
    samuraishowdown
    Объясни на примере алгоритм

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

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

    Malfoy New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2012
    Сообщения:
    698
    XshStasX
    Я ответил и вам и тс, что есчо нужно ?

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

    XshStasX New Member

    Публикаций:
    0
    Регистрация:
    9 авг 2008
    Сообщения:
    991
    Интересно как без графа используя только трассу исполнения и "пары ret/retn, call " найти цепочку ?
    В примере выше(#8) нету ни одного ret/retn.
     
  11. Malfoy

    Malfoy New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2012
    Сообщения:
    698
    XshStasX
    Никак. Код не линейный.
     
  12. mrCyber

    mrCyber New Member

    Публикаций:
    0
    Регистрация:
    29 дек 2011
    Сообщения:
    42
    Да, мне тоже этот код не кажется реальным. Да, такое все же наверно может быть в реальности, но обычно трассы так не выглядят.

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

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

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

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

    Malfoy New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2012
    Сообщения:
    698
    mrCyber
    Вас не устраивает алго по ссылке, нужен готовый юзабельный код ?

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

    mrCyber New Member

    Публикаций:
    0
    Регистрация:
    29 дек 2011
    Сообщения:
    42
    Malfoy
    В том то и дело, что писать код - в данном случае я не оч. хотел бы. У меня дохрена работы и помимо написания кода для таких задач, встречающихся по ходу решения основных. Нужен готовый тул. Говорите есть и надо врубиться, как работает? Ну скажите, что это за зверь - попробуем :) Если понимание как им пользоваться не превысит времени написания своего кода - то наверно уж раскурю как-нибудь :)
     
  15. Malfoy

    Malfoy New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2012
    Сообщения:
    698
    mrCyber
    А ведь забавно, у вас времени нет и поэтому я должен за вас код запилить, причём псевдокод вам дан. Такие вопросы в комерсе задают товарищ.
     
  16. mrCyber

    mrCyber New Member

    Публикаций:
    0
    Регистрация:
    29 дек 2011
    Сообщения:
    42
    Malfoy
    Сорри, у меня такого и в мыслях не было. Значит я просто не правильно понял ваши слова. Нет, спасибо. Я писать и сам умею - но это время, которого у меня нет. Цена времени мне хорошо известна, так что от других подобных жертв я тоже не жду.
    И конечно же тут никто никому ничего не должен :) Даже думать забудьте.
     
  17. samuraishowdown

    samuraishowdown New Member

    Публикаций:
    0
    Регистрация:
    6 мар 2011
    Сообщения:
    70
    Если вам нужно получить лог выполнения всех функций, в том числе и тех из которых произошёл возврат, то это не 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
    Базару нет. Только у ТСа не код, а трасса
     
  18. Malfoy

    Malfoy New Member

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

    samuraishowdown New Member

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

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

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

    Malfoy New Member

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