eXeLab
eXeL@B DVD 2017 !

Курс видеоуроков КРЭКЕРСТВО + ПРОГРАММИРОВАНИЕ 2017
(актуальность: апрель 2017)
Свежие инструменты, новые видеоуроки!

  • 400+ видеоуроков
  • 800 инструментов
  • 100 свежих книг и статей

УЗНАТЬ БОЛЬШЕ >>
Домой | Статьи | RAR-cтатьи | FAQ | Форум | Скачать | Видеокурс
Новичку | Ссылки | Программирование | Интервью | Архив | Связь

Нанимаем реверс-инженеров на постоянной основе
Русский / Russian English / Английский

Сейчас на форуме: (+3 невидимых)
 · Начало · Статистика · Регистрация · Поиск · ПРАВИЛА ФОРУМА · Язык · RSS · SVN ·

 eXeL@B —› Основной форум —› Восстановление деления при реверсе кода
Посл.ответ Сообщение
Vamit


Ранг: 222.7 (наставник)
Статус: Участник

Создано: 27 марта 2017 11:06 · Поправил: Vamit New!
· Личное сообщение · #1

При реверсе кода часто встречаются операции деления замененные компилятором на умножение. Имеется ли какой универсальный алгоритм восстановления деления? В математике я не силен, а искать результат методом подбора утомительно, да и неправильно, всё таки декомпилятор должен иметь алгоритм восстановления деления.
Пара примеров:
Code:
  1. mov    eax, 77777777h
  2. imul   value
  3. sub    edx, value
  4. sar    edx, 6
  5. mov    eax, edx
  6. shr    eax, 1Fh
  7. add    eax, edx
  8. mov    result, eax
  9.  
  10. mov    eax, 51EB851Fh
  11. imul   value
  12. sar    edx, 5
  13. mov    eax, edx
  14. shr    eax, 1Fh
  15. add    eax, edx
  16. mov    result, eax
r_e

Ранг: 502.0 (!)
Статус: Участник

Создано: 27 марта 2017 11:27 New!
· Личное сообщение · #2

Лучи не берут этот участок?
dosprog

Ранг: 271.4 (наставник)
Статус: Участник

Создано: 27 марта 2017 11:28 · Поправил: dosprog New!
· Личное сообщение · #3

Алгоритм существует, есть такая программа - { Атач доступен только для участников форума } - MagicDiv (c)TheSvin.
Только там в обратном направлении - div->mul.
Подозреваю, что можно было бы все часто встречающиеся подобные конструкции
пооформлять в виде шаблонов, и "примерять" их все последовательно на предмет совпадения,
встретив инстркцию mul/imul.
Другое тут вряд ли что-то придумаешь.
Сложно это..

| Сообщение посчитали полезным: Vamit, v00doo

dsrabot1

Ранг: 3.6 (гость)
Статус: Участник

Создано: 27 марта 2017 11:35 New!
· Личное сообщение · #4

r_e пишет:
Лучи не берут этот участок?

А при чем здесь лучи ? Конечно должны брать (кстати х64 некоторые подобные блоки не декомпильнулись, беда, но сейчас не о том), я так понимаю Вамит хочет именно сам восстанавливать данный блок в менее быстрый, но более понятен вариант с делением.
dosprog

Ранг: 271.4 (наставник)
Статус: Участник

Создано: 27 марта 2017 11:58 New!
· Личное сообщение · #5

r_e пишет:
Лучи не берут этот участок?


Да, в принципе, и не должны..

Пример:
Code:
  1. ttt proc
  2. mov eax,nnn
  3. mov edx, mmm
  4. inc eax
  5. mul edx
  6. SHR edx, 20
  7. mov rrr,eax
  8. ret
  9. ttt endp

Результат:
Code:
  1. int __cdecl sub_401000()
  2. {
  3.   int result; // eax@1
  4.   result = dword_403004 * (dword_403000 + 1);
  5.   dword_403008 = dword_403004 * (dword_403000 + 1);
  6.   return result;
  7. }
Vamit


Ранг: 222.7 (наставник)
Статус: Участник

Создано: 27 марта 2017 12:04 · Поправил: Vamit New!
· Личное сообщение · #6

r_e пишет:
Лучи не берут этот участок?

Если вы ими пользовались, то должны знать, что им ещё далеко до такого. А вот непонятную хрень сделать из этого могут
dosprog
За программку спасибо, посмотрю... Алгоритм замены деления на умножение есть, он же используется во многих компиляторах, но он не подходит для обращения, тут нужно что-то другое.
dsrabot1 пишет:
восстанавливать данный блок в менее быстрый

При реверсе быстрота не нужна, а нужен исходный код, программист не станет писать такой код для деления, а просто напишет,
как во втором примере value / 100, а результат первого расшифруйте сами...
dosprog

Ранг: 271.4 (наставник)
Статус: Участник

Создано: 27 марта 2017 12:11 · Поправил: dosprog New!
· Личное сообщение · #7

.. что-то на эту тему было у ManHunter'а (но тоже div->mul, а не наоборот), щас не могу поискать.
r_e

Ранг: 502.0 (!)
Статус: Участник

Создано: 27 марта 2017 12:11 New!
· Личное сообщение · #8

Vamit пишет:
Если вы ими пользовались, то должны знать, что им ещё далеко до такого.

Вообще-то они это умеют. Но не во всех случаях, да.
dosprog

Ранг: 271.4 (наставник)
Статус: Участник

Создано: 27 марта 2017 12:24 · Поправил: dosprog New!
· Личное сообщение · #9

r_e пишет:
Вообще-то они это умеют. Но не во всех случаях, да.


Попробовал в примере .ASM, который в прошлом посте, (процедура <ttt>) заменить переменные <nnn> и <mmm> константами - после этого декомпилятор вообще отказывается такое декомпилить, с сообщением об ошибке.
Значит, наверное, таки что-то они там мудрят в этом направлении, но ничего путного не получается..


dsrabot1 пишет:
После нормального компиля у меня всегда выдавало норм выхлоп


Какой такой "нормальный конпиль"?
- Не было там вообше никакого конпиля. Транслировалось MASM'ом.
r_e

Ранг: 502.0 (!)
Статус: Участник

Создано: 27 марта 2017 13:19 New!
· Личное сообщение · #10

Вот прям свежак
Code:
  1. .text:0069A5CB                 mov     edi, [esp+180h+arg_0]
  2. .text:0069A5D2                 mov     eax, 92492493h
  3. .text:0069A5D7                 mov     ebx, [esp+180h+arg_4]
  4. .text:0069A5DE                 mov     ecx, [edi+8]
  5. .text:0069A5E1                 sub     ecx, [edi]
  6. .text:0069A5E3                 imul    ecx
  7. .text:0069A5E5                 add     edx, ecx
  8. .text:0069A5E7                 sar     edx, 4
  9. .text:0069A5EA                 mov     eax, edx
  10. .text:0069A5EC                 shr     eax, 1Fh
  11. .text:0069A5EF                 add     eax, edx
  12. .text:0069A5F1                 cmp     eax, 20h
  13. .text:0069A5F4                 jnb     short loc_69A5FF

выдает
Code:
  1.   if ( (unsigned int)((a1[2] - *a1) / 28) < 0x20 )
Vamit


Ранг: 222.7 (наставник)
Статус: Участник

Создано: 27 марта 2017 14:07 · Поправил: Vamit New!
· Личное сообщение · #11

Я не отрицаю, иногда рей может что-то и полезное выдать, но к сожалению, только иногда...

Вот нашел интересную табличку по теме --> Link <--, помочь может, но вопрос не решает.

А здесь --> Link <-- более полная инфа

| Сообщение посчитали полезным: v00doo

dsrabot1

Ранг: 3.6 (гость)
Статус: Участник

Создано: 27 марта 2017 14:15 New!
· Личное сообщение · #12

dosprog
Не то ты декомпилишь )
После нормального компиля у меня всегда выдавало норм выхлоп, сколько помню таких моментов.

Vamit
Вот по теме:
https://habrahabr.ru/post/256827/

| Сообщение посчитали полезным: Vamit

reversecode


Ранг: 917.2 (! ! !)
Статус: Участник

Создано: 27 марта 2017 14:41 · Поправил: reversecode New!
· Личное сообщение · #13

у юрчева в его книге ре для начинающих есть одна страница посвящена магическому делению
--> Link <--
еще здесь чуток --> Link <--
в целом алгоритм расширенный алго евклида

вот у менхантера там ссылки чуть чуть мертвые можно погуглить
--> Link <--

Добавлено спустя 5 минут
--> Link <--

Добавлено спустя 2 часа 52 минуты
вот вам пример когда рейс декомпилит
а когда стопорится
вот и думайте что там нужно поменять в двух почти идентичных версиях кода, что бы второй тоже декомпильнулся

может кто скрипт на питоне или идс забабахает для таких случаев))

Code:
  1. mov     eax, [ecx+4]  
  2. mov     ecx, 0E10h    
  3. cdq                   
  4. idiv    ecx           
  5. mov     eax, 88888889h
  6. mov     ecx, edx      
  7. imul    ecx           
  8. mov     eax, edx      
  9. add     eax, ecx      
  10. sar     eax, 5        
  11. mov     edx, eax      
  12. shr     edx, 1Fh      
  13. add     eax, edx      
  14. retn                  


Code:
  1. return *(_DWORD *)(this + 4) % 3600 / 60;


Code:
  1. mov     eax, [ecx+4]  
  2. cdq                   
  3. mov     ecx, 36EE80h  
  4. idiv    ecx           
  5. mov     eax, 45E7B273h
  6. imul    edx           
  7. mov     eax, edx      
  8. sar     eax, 0Eh      
  9. mov     edx, eax      
  10. shr     edx, 1Fh      
  11. add     eax, edx      
  12. retn                  


Code:
  1.   signed int v1; // eax@1
  2.  
  3.   v1 = (signed int)((unsigned __int64)(1172812403i64 * (*(_DWORD *)(this + 4) % 3600000)) >> 32) >> 14;
  4.   return ((unsigned int)v1 >> 31) + v1;
  5.  

| Сообщение посчитали полезным: Vamit

difexacaw

Ранг: 96.5 (постоянный)
Статус: Участник

Создано: 28 марта 2017 02:33 New!
· Личное сообщение · #14

Посмотрите это --> Link <--

Это хорошая обучалка по мат алгосам.

В целом же деление сводится к сдвигу и сложению, псевдокод целочисленного деления:

Code:
  1. ; Q = N/D
  2.  
  3.          !Q
  4.          !T
  5.          Do
  6.                  N <<   ; CF
  7.                  T << + CF
  8.                  T - D  ; CF
  9.                  if CF
  10.                         T + D
  11.                  fi
  12.                  Q <<
  13.          Loop 32
  14.          NOT Q
VodoleY

Ранг: 471.2 (мудрец)
Статус: Участник

Создано: 28 марта 2017 08:03 · Поправил: VodoleY New!
· Личное сообщение · #15

difexacaw пишет:
Посмотрите это --> Link <--

ЖЕСТЬ ) это 1ая книга которую я читал)) правда немного в другом виде, и в переводе. (знакомые сделали на заводе копию, матречный принтер.. куплено было за безумные деньги.. распечатка на овсетной бумаге.. ) гдето 90ый год был.. я попутно.. по этой распечатке.. еще и ассемблер спектрума учил.. ибо книжки по асму то не было)))
ЗЫ.. кстати.. буквально в прошлом году выкинул, ибо чернила выцвели, до состояния не читабельности..

| Сообщение посчитали полезным: difexacaw

Vamit


Ранг: 222.7 (наставник)
Статус: Участник

Создано: 28 марта 2017 09:55 · Поправил: Vamit New!
· Личное сообщение · #16

Вот простые формулы по которым возможно получить делитель, зная магическое число (множитель), кол-во сдвигов и юстировку (+- к старшему дворду после умножения):
без юстировки
divirer = 2 ^ (32 + shift) / magic + 1;
с юстировкой
divirer = 2 ^ (32 + shift) / (magic + 2 ^ (32 + adjust)) + 1;
где: ^ - обозначение степени числа,
shift - кол-во сдвигов после умножения и юстировки
magic - магический множитель
adjust - знаковое юстировочное значение (= 1, если присутствует)
Справедливы для знакового и беззнакового деления.

PS: Для + юстировки формула не верна, правильный результат получается в этом случае по формуле 1 при игнорировании юстировки, но тогда возникает вопрос, а зачем нужно прибавлять множимое к старшему дворду после умножения?
spinz

Ранг: 41.6 (посетитель)
Статус: Участник

Создано: 28 марта 2017 11:03 New!
· Личное сообщение · #17

Разве, зная делимое и частное, нельзя вычислить делитель?

Пусть, например, у нас есть делимое 100 и в результате умножения, заменяющего деление, мы получаем

частное 2. Тогда делитель лежит в диапазоне от 34 до 50. Подавая на вход функции умножения делители из

этого дипазона, двоичным поиском находим нужный делитель.
Vamit


Ранг: 222.7 (наставник)
Статус: Участник

Создано: 28 марта 2017 12:35 · Поправил: Vamit New!
· Личное сообщение · #18

spinz
Частное мы не знаем и делимое тоже, посмотрите примеры в начале темы, известен только магический множитель, дальнейшие сдвиги и юстировка. Но с двумя неизвестными задача не решаема, поэтому предполагаем, что частное = 1, следовательно делимое будет = делителю. Ничего поиском искать не нужно.
Формула 1 работает правильно, формула 2 для отрицательной юстировки так же работает. Причем отрицательную юстировку можно убрать изменив магический множитель magic = 2 ^ 32 - magic; и использовать формулу 1, но тогда мы будем получать только положительный делитель (например, вместо -110, будет 110).
Остается вопрос для чего нужна положительная юстировка или я что-то упустил.
ajax


Ранг: 267.4 (наставник)
Статус: Участник
born to be evil

Создано: 28 марта 2017 14:17 New!
· Личное сообщение · #19

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


Ранг: 917.2 (! ! !)
Статус: Участник

Создано: 20 апреля 2017 15:06 New!
· Личное сообщение · #20

в копилку --> Link <--
ajax


Ранг: 267.4 (наставник)
Статус: Участник
born to be evil

Создано: 20 апреля 2017 15:36 New!
· Личное сообщение · #21

забавное мат задротство. так же, что 16 знаков по Pi в дотнете. типа долететь по марса, поправка/ошибка 4 см может быть
difexacaw

Ранг: 96.5 (постоянный)
Статус: Участник

Создано: 22 апреля 2017 15:14 · Поправил: difexacaw New!
· Личное сообщение · #22

При попытке портировать ряды чебышева(алгосы со спекки) на контроллеры оказалось что коэффициенты не паблик. Приведены они для всего малого числа итераций, посему эти вычисления можно считать приват. Вероятно современные процессоры используют эти же алгоритмы, это обьясняет отсутствие по ним инфы, так как она закрыта.
 eXeL@B —› Основной форум —› Восстановление деления при реверсе кода

Оригинальный DVD-ROM: eXeL@B DVD !

Вы находитесь на форуме сайта EXELAB.RU
Проект ReactOS