Здравствуйте, я ламер и нуб. Не все сразу стали охуенными специалистами, поэтому не надо смеяться ) Есть некая функция, на вход которой подается блок данных, на выходе хеш-значение этих данных, размером 16 байт. В зависимости от хеш значения, необходимо передать управление на какую-то ветку кода. Если бы это был, например, 2-х байтное значение, тогда можно было бы сделать таблицу перехода, т.е. использовать хеш в качестве индекса в неком массиве. Вариантов хеш значения может быть несколько миллионов, соответственно, такое количество переходов должно быть. Я не совсем понимаю, как это лучше реализовать. Читал где-то про ступенчатый метод (если я правильно это назвал), но не совсем понимаю технически, как это можно реализовать. Конечная задача - реализация конечного автомата, т.е. на вход в функцию подаются некие состояния, функция снимает с них хеш и должна вызвать соответсвующую ветку алгоритма. Буду благодарен специалистам данного форума за технически развернутые ответы. Спасибо за внимание.
для начала нужно научиться нормально выражаться. способов миллион. зависит от конечной цели. можно создать мапу соответствия хеш-адрес. можно, как заметил Booster, находить остаток от деления хеша на размер массива (тогда нужен _правильный_ хеш - чтобы одинаковых остатков не было). можно switch-case (даже, наверное, будет лучше, тем более, если подсчитать вероятность переходов и расположить case'ы начиная с максимальной).
У нормального хеша другая задача - дать близким входным данным сильно различающийся выход. Для этого их и делают такими длинными. Ваша задача в другом (если я правильно догадался) сводить большие блоки данных в малое число состояний. Это называется "задача классификации" и хеш тут можно делать, если вы играете на бирже - там все равно зависимостей нет и все дурят заказчиков как хотят. А по хорошему - ищете литературу, читаете и реализуете. Задача давно решенная, если конечно есть закономерность. Если вы внимательно читали правила форума, то тут таким не занимаются, а Интернет он большой ОДНАКА... Если конечно ваша цель, чтобы ваша программа выполняла "случайные действия" на предмет обучения на входных последовательностях, тогда да хеш годится - вариантов тьма : можно использовать биты как переключатели, можно вырезать "кусочек". Но только опять это глупо, т.к. и для распознавания и для обучения есть "готовые решения". Нет идей хороших как из этого пользу получить.
господину Booster: Велика вероятность того, что у разных хешей может быть одинаковый остаток от деления. Поэтому данный вариант не очень подходит. господину cupuyc: понял Вас, извините. не совсем понял про карту соответствия. и по скорости не понятно что будет. switch-case может быть довольно долгим, тк вариантов хешей и состояний может быть несколько млн. господину Pavia: не совсем понял. т.е. хеши должны быть упорядочены по возрастанию? потом берется серидина массива, сравнивается со своим хешем, если хеш больше, делим опять массив пополам и сравниваем дальше? я правильно Вас понял. тогда не совсем понял, как упорядочить данный массив хешей, и как это реализуется. если я правильно Вас понял, то Вы говорите про этот метод: http://algolist.manual.ru/search/bin_search.php если нет, поправьте пожалуйста. господину valterg: с точки зрения алгоритма поиска хеша нужно сделать точно также как это делает каспер (имею ввиду поиск по сигнатурам). т.е. он берет файл, в некоторых точках по определенным правилам снимает хеш, ищем хеш по базе, потом говорит, что это вирус такой-то. причем количесвто записей в его базе, насколько я понял, не сильно влияют на скорость поиска хеша на соответствие некоему вирусу. уважаемые господа, спасибо всем за Ваши ответы, но решения пока не нашел. единственное, что пока вижу, это понять, как каспер быстро ищет хеши по своим базам. теперь ближе к самой задаче, которая стоит. сразу скажу, что задача не более чем лабораторный эксперимент, и предполагается только пару тестов в домашних условиях. есть некоторый кусок кода, выполненный в шелкод-стиле, т.е. тупо буфер с данными, куда передается управление и алгоритм начинает работать самостоятельно. также точно известно, какие диапазоны значений могут принимать некоторые регистры на определенных инструкциях. мои интересы требуют того, чтобы алгоритм работал только на нужных мне машинах, т.е. чтобы его было сложно заставить правильно работать на других машинах. как это вижу я. пример. инструкция №10 (EAX = {0x11, 0x22}, ESI = {0x33, 0x44, 0x55}). инструкция №11 (EBX = {0x55, 0x00}, EDX = {0x77, 0x11}). теперь расшифровка. в моем шелкоде в инструкции №10 регистры EAX могут принимать значения 0x11 и 0x22. другие не может. ESI может принимать значения 0x33, 0x44, 0x55, другие не может. аналогично с инструкцией №11. теперь нужно вызвать некий конечный автомат, который бы генерировал тело шелкода (инструкции) в зависимости от состояний (значений некоторых регистров), которые подаются внутрь алгоритма. Требованию к автомату: - автомат должен быть аппаратно привязанным. т.е. гененерировал правильное тело шелкода только на той машине, где нужно. Для этого можно получить некое значение от аппаратуры. - должно быть невозможным получить весь шелкод в первоначальном виде, тупо вызвав функцию автомата в цикле, перебирая все инструкции. Для этого мы делаем автомат зависим от значений неких регистров в каждой конкретной инструкции. таким образом, чтобы получить автоматически весь шелкод в первоначальном виде, реверсеру нужно знать, какие значения могут принимать регистры в каждой конкретной инструкции. - в качестве защиты от отладки можно снимать тайминги при каждом генерированнии инструкций. если тайминг превышвает некое значение, мы предполагаем, что идет отладка приложения и алгоритм начинает генерировать фейк-инструкции. пример всевдокода. чтобы получить опкод инструкции №10 я должен вызвать функцию автомата примерно так: Код (Text): IN: dwOpcodeNumber номер опкода, в нашем случае = 10 dwFlags регистры, которые надо учитывать при получении хеша. в нашем случае = PRESENT_EAX | PRESENT_ESI dwHardwareID некое значение, сгенерированное от аппаратуры машины pContext указатель на структуру CONTEXT с регистрами. Обрабатываться будут только те инструкции, которые обозначены в флагах. OUT: BYTE *pbOpcode указатель на сгенерированный опкод BYTE *GetOpcode (dwOpcodeNumber, dwFlags, dwHardwareID, CONTEXT *pContext) { BYTE *pbBuf = (BYTE *) LocalAlloc (LPTR, 16); HASH hHASH = GetHash (dwOpcodeNumber, dwFlags, dwHardwareID, pContext); switch (hHASH) { case 0x11aa: memcpy (pbBuf, &"0x55", 1); // "push ebp" break; case XXX: ... break; default: memcpy (pbBuf, &"FAKE OPCODE", 5); } return pbBuf; } по теме алгоритма, сколько он будет занимать места у юзера - не важно. самое слабое место - я не могу понять как мне передавать управлению некоему куску кода в зависимости от хеша. разумеется, скорость должна быть приемлемой при нескольких млн.хеш значений. самое близкое из реализаций подобной задачи я вижу у каспера. уважаемые господа, не могли бы Вы чуть подробнее описать, как такая задача решается у каспера.
user1 Типо защита такая, Ptr = f(ID) ? Знайте что реально достаточно одного рабочего экземпляра такого приложения, сразу будет написан эмулятор среды/пропатчено и пр. и эта софтина пойдёт по сети.
user1 >Велика вероятность того, что у разных хешей может быть одинаковый остаток от деления. Поэтому данный вариант не очень подходит. Если функция хорошая, то не велика. Коллизии могут быть, по-этому должен быть массив массивов.
Это вам показалось. Касперский ищет по сигнатурам. Как не знаю, но думаю там дерево. Есть параллельная тема про сигнатуры - кроме касперского, есть антивирусы с открытыми исходниками - изучаем.
Booster строка из 10 только маленьких букв английского алфавита имеет 22^10 возможных вариантов. число из 10 арабских цифер имеет 10^10 возможных вариантов ежу понятно, что от коллизий никуда не деться. тоэтому, хэш функция пытается в первую очередь уменьшить количество вариантов за счет маловерояных. потом, уменьшает и нормирует получившееся число методом взятия остатка от деления на нормирующее число. поиск, обычно, осуществляется не через кэйс, а через разреженную таблицу. методы разрешения коллизий - отдельная тема, таких методов > 1. наиболее прост, употребим и описан - цепочечный.
уважаемые господа, спасибо Вам за ответы. господин Clerk, извините, не совсем понял, что значит будет эмулятор среды и как он будет эмулировать др.версии. Технология. Сначала генерится шелкод в нормальном виде. Генерация метаморфная, т.е. шелкод с точки зрения команд будет уникальным. После этого узнаем в какой инструкции какие значения (или диапазоны) могут быть, после этого засовываем полученные данные в конечный автомат, который привязываем к железу. т.е. не будет 2х одинаковых шелкодом, на разных аппаратных платформах, поэтому я не совсем понял, как можно автоматизировать (эмулировать) все версии. Пожалуйста, поясните. массив массивов? и по каким правилам должна осуществляться выборка и инициализация по такому массиву? поясните примером пожалуйста, господин Booster. господин valterg, спасибо за совет буду искать АВ с исходниками. извините, я тогда видимо вообще не понял понятия остаток от деления хеш значения. какой остаток? деления на что? нормирующее число, разреженная таблица, разрешение коллизий - Вы один сегодня пополнили мой словарь слов. господин qqwe, я математический ламер. Вы бы не могли привести какой-то пример. например, у нас есть 16 байтное хеш-значение, нам надо передать куда-то управление. какой примерно должен быть алгоритм. я вижу, у Вас за плечами хорошая математическая основа, а у меня все знания по математике сводятся к WIN+R -> calc -> Enter в винде и ALT+= в HIEW. поэтому буду Вам очень признателен за какие-либо полезные линки разбору хеш-значений, но которые не сильно уводят в глубокую матемитику. спасибо.
user1 qqwe уже в общем объяснил. Первичный массив индексируется малым хешем, что позволяет держать его размер небольшим. Каждый элемент первичного массива это тоже массив(назовём его вторичным), в них собственно и хранятся сами указатели. И в случае если во вторичном массиве более одного элемента, то далее определяем каким-то дополнительным методом, например ищем элемент сравнением(в данном случае указатель) или полным по большому хешу или как-то ещё. В общем это канонический принцип работы хеш дерева.
user1 с каких пор это служит оправданием? ленитесь разбираться сами -> платите тем, кто ленится меньше. взамен чувствуете себя _большим_боссом_на_которого_работают_ например, у нас есть фонарик с 16тью кнопками, нам надо сходить в магазин, какой примерно должен быть звук? ,каспадиин?? вы чтото поняли? я тоже нет насчет хешей, то это не чтото одно, а просто общее название класса методов для получения большого разброса результатов при близких входных значениях. например, для рассчета хэша можно пользоваться методами для рассчета псевдослучайных значений. хэши описаны много где. очень серьезно и подробно у кнута. но вам лучше что нибудь вроде "алгоритмы. построение и анализ" кормэна. ничегошный туториальчик. с картинками. хотя, японцы, брешут, уже в виде комиксов все это пишут. ибо без этого японцу, даже самому жалкому и тупому - голодная смерть.
Народ очнитесь. У user1 есть задача, которой мы пока не знаем, он придумал НЕПРАВИЛЬНОЕ ее решение и теперь просит совета. Но советы не лучше. Он еще не выбрал хеш и только спасовал перед проблемами. На фига брать "большой" хеш и потом делать остатки и т.п. Если нужна "хешированная таблица" - берем сразу хеш под нее (это делалось лет надцать назад, и наверняка сейчас при работе с именами переменных в компиляторах) и работаем. Коллизии неизбежны, а методы борьбы известны. Про все остальное говорить вообще бесполезно, т.к. база знаний user1 маловата и задачка ему точно не по зубам
valterg ну так, а я что говорю ? ну так да. и почему советы плохие? а что еще посоветовать человеку, который не рассказывает свою задачу, только все бредит о слове "хэш" вперемешку с утверждениями, что он бесконечно далек от математики и на сближение итти не намерен?
уважаемые господа, спасибо всем за ответы и участие. буду изучать доп.материалы по данной теме. qqwe, уровень знаний в матем.слабый, это правда. но почему не хочу идти на сближение? в той мере, в которой нужно для решения задачи, придется немного углубиться, сильно страшного в этом ничего не вижу. Вам спасибо за литературу.
user1 Весьма просто. Например вы к какимто параметрам системы сделали привязку. Чтоб инфу о железе получить вам нужно обратиться к ядру. Путь один. Данные мы можем подсунуть любые. А какой там код, пермутирующий или другой какой не имеет значения, аналогично и накрытие виртуальными машинами. Достаточно сказать что я не разу не юзал платный софт.
