Сейчас на форуме: -Sanchez- (+8 невидимых)

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


Ранг: 331.1 (мудрец), 561thx
Активность: 0.19↘0.06
Статус: Участник

 Создано: 27 марта 2017 11:06 · Поправил: Vamit
· Личное сообщение · #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


-----
Everything is relative...

Ранг: 590.4 (!), 408thx
Активность: 0.36↘0.18
Статус: Модератор

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

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

-----
старый пень

Ранг: 431.7 (мудрец), 389thx
Активность: 0.73↘0.32
Статус: Участник

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

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

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

Ранг: 9.0 (гость), 6thx
Активность: 0.03↘0.02
Статус: Участник

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

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



Ранг: 431.7 (мудрец), 389thx
Активность: 0.73↘0.32
Статус: Участник

 Создано: 27 марта 2017 11:58
· Личное сообщение · #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. }


Ранг: 331.1 (мудрец), 561thx
Активность: 0.19↘0.06
Статус: Участник

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

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

-----
Everything is relative...

Ранг: 431.7 (мудрец), 389thx
Активность: 0.73↘0.32
Статус: Участник

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

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



Ранг: 590.4 (!), 408thx
Активность: 0.36↘0.18
Статус: Модератор

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

Vamit пишет:
Если вы ими пользовались, то должны знать, что им ещё далеко до такого.
Вообще-то они это умеют. Но не во всех случаях, да.

-----
старый пень

Ранг: 431.7 (мудрец), 389thx
Активность: 0.73↘0.32
Статус: Участник

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

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

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


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

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



Ранг: 590.4 (!), 408thx
Активность: 0.36↘0.18
Статус: Модератор

 Создано: 27 марта 2017 13:19
· Личное сообщение · #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 )


-----
старый пень


Ранг: 331.1 (мудрец), 561thx
Активность: 0.19↘0.06
Статус: Участник

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

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

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

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

-----
Everything is relative...

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

Ранг: 9.0 (гость), 6thx
Активность: 0.03↘0.02
Статус: Участник

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

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

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

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


Ранг: 1053.6 (!!!!), 1078thx
Активность: 1.06↘0.81
Статус: Участник

 Создано: 27 марта 2017 14:41 · Поправил: reversecode
· Личное сообщение · #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


Ранг: 337.5 (мудрец), 348thx
Активность: 2.11↗2.42
Статус: Участник

 Создано: 28 марта 2017 02:33
· Личное сообщение · #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


-----
vx

Ранг: 488.1 (мудрец), 272thx
Активность: 0.35↘0
Статус: Участник

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

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

-----
Наша работа во тьме, Мы делаем, что умеем. Мы отдаем, что имеем, Наша работа во тьме....

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


Ранг: 331.1 (мудрец), 561thx
Активность: 0.19↘0.06
Статус: Участник

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

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

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

-----
Everything is relative...

Ранг: 50.0 (постоянный), 31thx
Активность: 0.09↗0.1
Статус: Участник

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

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

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

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

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




Ранг: 331.1 (мудрец), 561thx
Активность: 0.19↘0.06
Статус: Участник

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

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

-----
Everything is relative...


Ранг: 337.6 (мудрец), 224thx
Активность: 0.21↘0.1
Статус: Участник
born to be evil

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

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

-----
От многой мудрости много скорби, и умножающий знание умножает печаль


Ранг: 1053.6 (!!!!), 1078thx
Активность: 1.06↘0.81
Статус: Участник

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

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




Ранг: 337.6 (мудрец), 224thx
Активность: 0.21↘0.1
Статус: Участник
born to be evil

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

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

-----
От многой мудрости много скорби, и умножающий знание умножает печаль


Ранг: 337.5 (мудрец), 348thx
Активность: 2.11↗2.42
Статус: Участник

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

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

-----
vx
 eXeL@B —› Основной форум —› Восстановление деления при реверсе кода
:: Ваш ответ
Жирный  Курсив  Подчеркнутый  Перечеркнутый  {mpf5}  Код  Вставить ссылку 
:s1: :s2: :s3: :s4: :s5: :s6: :s7: :s8: :s9: :s10: :s11: :s12: :s13: :s14: :s15: :s16:


Максимальный размер аттача: 500KB.
Ваш логин: german1505 » Выход » ЛС
   Для печати Для печати