Реверсинг и конечные автоматы

Y_Mur

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

 

Решил я как-то пооптимизировать замену div на mul:

Код (Text):

1. ; --- Деление на константу ---
2. _DIV_ MACRO Delimoe, Delitel
3.    mov EAX, Delimoe
4.    mov EDX, 0FFFFFFFFh / Delitel + 1
5.    imul EDX
6. ENDM
7. ; ВНИМАНИЕ: результат в EDX, (в EAX мусор)
8.  
9. ; --- Остаток от деления на константу ---
10. _ORD_ MACRO Delimoe, Delitel
11.    mov EAX, Delimoe
12.    mov EDX, 0FFFFFFFFh / Delitel + 1
13.    mul EDX
14.    mov EDX, Delitel
15.    imul EDX
16. ENDM
17. ; ВНИМАНИЕ: результат в EDX (в EAX мусор)

В некотором диапазоне чисел сей код даёт корректный результат, но в общем случе не корректный
Вопрос как узнать этот корректный диапазон?
Прямой перебор - оооочень долго
Кажется тебя интересуют грабли такого типа?

 

_Serega_
А если сходящуюся функцию подсунуть, хотя бы вычисление синуса или числа Pi через ряды?

 

_Serega_
Собственно "вредные предназначения" для меня тоже не очевидны

Это и для обычного тестирования сложной математической функции не лишне , но боюсь "в общем виде" сия задача решается только методом перебора , что для серьёзной математики нереально

 

Y_Mur
Прямой проход это то, что я для _DIV_ MACRO скажу:
4 Состояния:
-#GP
-#PF
-#AC
-EDX=[n1..n2,n3..n4] EAX=[m1..m2] EIP=[EIP+z1]
т.е. Я скажу все возможные результаты выполнения твоего кода, для всего множества входных значений. Эта задача кажется простой, но возможно я чего-то не замечаю, типа косвенной адресации или чего-то в этом роде.
То что нужно тебе это как раз есть обратный проход.

 

Y_Mur

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

 

Pavia

К сожалению, ФПУ не поддерживается и не планируется, хотя если можешь представить итерационную на обычных командах, то обязательно нужно проверить. Хотя я тут траблов не вижу, ИМХО должно работать.

 

_Serega_
Результатом тестирования моих _DIV_, _ORD_ должен быть ответ "да" если результат макроса совпадает с результатом обычного div, или "нет" если не совпадает Где тут обратный прход?
Соответственно общим результатом тестирования будет диапазон i...k, где макрос работает и диапазон k+1...n где он нагло врёт
Но если я тебя правильно понял, то результатом работы твоего "конечного автомата" будет ответ: "приведённый здесь вопрос имеет 2 варианта ответа "Да" и "Нет""
Как вероятность встретить динозавра на улице 50% "встречу" или "не встречу" )
Если я угадал, то объясни наконец зачем оно такое надо?

 

Y_Mur
Ты совсем меня не понял.
Все, я больше не могу, завтра на свежую голову попробую объяснить.
На сегодня всем спокойной ночи.

 

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

 

_Serega_
Понятие "конечный автомат" если очистить его от шелухи часто навешиваемой в "умных книгах" весчь красивая и полезная:
Конечный автомат - устройство (или программа) которое на последовательность одинаковых воздействий реагирует разными откликами, но при этом:
- количество этих разных откликов ограничено (потому и автомат конечный)
- последовательность разных откликов известна и самопроизвольно не меняется
- на другие воздействия конечный автомат имеет полное право реагировать по другому, выдавая либо другую последовательность действий, либо как обычная функция - однозначный результат.
Например: конечный автомат - Кукушка_для_часов(параметр)
Кукушка_для_часов(прошёл_час) ; \\ Отклик 1 раз "ку-ку"
Кукушка_для_часов(прошёл_час) ; \\ Отклик 2 раза "ку-ку"
Кукушка_для_часов(прошёл_час) ; \\ Отклик 3 раза "ку-ку"
...
Кукушка_для_часов(прошёл_час) ; \\ Отклик 11 раз "ку-ку"
Кукушка_для_часов(прошёл_час) ; \\ 12 раз "ку-ку" последний отклик
Кукушка_для_часов(прошёл_час) ; \\ 1 раз "ку-ку" отклики начали повторяться
Кукушка_для_часов(уст_5_ку_ку); \\ другое воздействие, отклик - изменение внутреннего счётчика
Кукушка_для_часов(прошёл_час) ; \\ Отклик 5 раз "ку-ку"
...
Другой пример: генератор псевдослучайных чисел тоже выдаёт фиксированную последовательность откликов на серию одинаковых вызовов, однако конечным автоматом не является поскольку его последовательность откликов "бесконечна". Есно реальный rnd() не может быть бесконечным и рано или поздно зациклится, однако предполагается, что пользователь не сможет дождаться сего чудесного момента и потому можно считать, что rnd() генерит бесконечную последовательность

Как это пристыковать к твоей постановке вопроса?

 

_Serega_
Из постов #25 #26 у меня сложилось два варианта работы твоего "псевдо конечного автомата":
1. простая проверка на возможные ошибки типа: "если в функции только арифметика с данными в регистрах, значит она никогда не вызовет исключение при доступе к памяти", а "если в функции только копирование\перемещение данных, то она никогда не сделает деление на ноль". Тут для меня польза весьма сомнительна...
2. перебор возможных входных параметров в поисках границ допустимых значений...
В моём примере с _DIV_, _ORD_ простым перебором нужно протестить матрицу 4294967295 х 4294967295 элементов... (заметь арифметика простейшая никаких FPU, рядов, косвенных вызовов и т.д.) говоришь заменяешь асм комманды на вызов спецфункций и решение задачи перебором резко ускоряется? - ооочень любопытно ))

 

Y_Mur
Ты сразу хочешь звезд с неба
Про динозавра я не понял. Нужно правильно задавать вопрос анализатору, например ответ на возможность подмены адреса возврата может быть только 1 либо да либо нет, и вариант кода при такой постановки задачи отловится 100%:

Код (Text):

1. void main ()
2. {
3. char a[20];
4. gets(a);
5. }

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

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

ЗЫ: Представление данных в виде конечного автомата выбрано не ради самого автомата, а потому, что в дальнейшем их удобно объединять в графы.

 

_Serega_
Тема ещё живая?
Обычное целочисленное деление константы (например, 0FFFFFFFFh) на любое число (входной диапазон 1...0FFFFFFFFh) тоже даст сильно подробленный выходной диапазон при непрерывном входном

 

Y_Mur
Тема еще живая, и будет жить пока сабж не потеряет актуальность
Все правильно, только уточнение: верно если нижний диапазон делителя << верхнего диапазона делимого. Для делителей 1,2,4,8... это не относится. Там все идет по другому алгоритму.
В принципе, ограничение не большое, потому, что сабж в основном будет использоваться на проверки блока кода, насчет того, в какую часть памяти он может теоретически обратиться. Операции с умножением и делением указателей обычно кратны степени 2, так что тут все работает. Может будут еще предложения? ... Ща над рекурсией думаю, действительно актуально, и нужно.

 

Как раз они гигантские пробелы на выходе и дадут, но ты прав посчитать их легко

Над нормальной (через цикл) или "классической" - бестолково забивающей стек параметрами функции и адресами возврата, единственное назначение которых быть цепочечно выкинутими в конце процесса , которую зачем-то пихают в учебники?

 

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

 

имхо до переполнения стека )) или завершения всех итераций...

 

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

 

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