Эффективность парсинга шаблонов подписи - PullRequest
Новая
       47

Эффективность парсинга шаблонов подписи

0 голосов
/ 31 мая 2018

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

Одна сложность, с которой я сталкиваюсь, это подстановочные знаки и медленная скорость сканирования.У пользователя есть тысячи шаблонов длиной до 200 символов каждый или даже больше.

Например, этот шаблон используется для проверки того, был ли файл скомпилирован под C ++, тогда как «?»символ является подстановочным знаком (который может соответствовать любому одному символу):

55 8B EC 53 8B 5D 08 56 8B 75 0C 85 F6 57 8B 7D 10 ??????????????????????????01

Шаблоны, подобные этому, все сложены в файл различной длины, поэтому, я думаю, вы поймете общую идею.

Это код, который я использую (работает нормально, но очень медленно по сравнению с другими инструментами, которые выполняют сканирование шаблонов за считанные секунды, например ExeInfoPE или Die) 

        static bool compare(string[] mask, byte[] buffer, int position)
    {
        var i = 0; // index
        foreach (string x in mask) // loop through the mask
        {
            if (x.Contains("?")) // is current mask position a wildcard?
            {
            }// if so skip comparison
            else if (byte.Parse(x, System.Globalization.NumberStyles.HexNumber) == buffer[position + i]) // else try to compare
            {
            }// succeeded, move onto next byte
            else
                return false; // failed, pattern not found
            ++i; // increment the index.
        }
        return true; // pattern was found
    }

Любойидеи о том, как значительно увеличить скорость при сохранении поддержки подстановочных знаков, чтобы мой инструмент можно было использовать в реальном мире?

1 Ответ

0 голосов
/ 31 мая 2018

Вы можете-должны предварительно преобразовать маски в byte?[] (или, проще говоря, byte[] плюс bool[] isWildcard, что верно, если есть подстановочный знак), если у вас есть несколько файлов для сопоставления.Это byte.Parse(x, System.Globalization.NumberStyles.HexNumber) работа, которая, если у вас есть 1000 файлов, будет бесполезно повторяться 1000 раз.

Другая проблема ... Насколько велика buffer?Я действительно надеюсь, что вы читаете только до 4 КБ (и даже меньше ... вы можете предварительно проверить все маски, чтобы увидеть, какая из них самая большая) данных из каждого файла, и что вы не читаете весь файл.

Во-вторых, вы можете попытаться проиндексировать шаблоны, по крайней мере, для первого байта шаблона (но помните, что вы должны обработать регистр, начинающийся с ?).

Несколько случайных комментариев:

  • не ясно, что вы действительно пытаетесь сделать.Нужна дополнительная информация.Сколько файлов вам нужно отсканировать?1 или 2 или много (10+, 100+?)?

  • ваши шаблоны начинаются с фиксированной позиции в файле или, по крайней мере, всегда присутствуют в определенной точке файла (например, MZ-сигнатура exe-файлов, то есть перваядва символа файла) или они могут быть где угодно?
    Многие программы "обманывают": они не загружают весь файл.Они загружают маленькие кусочки.Как например первые 4 КБ и последние 4 КБ.Они «знают», что их модель должна быть там.Поэтому, если вы загрузите весь файл, вы наверняка будете медленнее.

  • первые байты ваших шаблонов, как они распределены статистически?Например ... У вас есть 1000 шаблонов, и есть 256 возможных значений байта.Первый байт шаблона распределяется равномерно по всем возможным значениям?Таким образом, существует в среднем 4 шаблона, которые начинаются с каждого возможного значения байта (4 шаблона, начинающиеся с «A», 4, начинающиеся с «B» и т. Д.), Или есть некоторые байты, которые присутствуют гораздо чаще (еслинапример, есть 100 шаблонов, которые начинаются с 'A'), поскольку в первом случае можно проиндексировать шаблоны по первому байту и быстро выбрать небольшое подмножество шаблонов, имеющих только первый байт, во втором - первый байтнедостаточно дискриминанта для выбора подмножества шаблонов для проверки.

В общем случае у меня будет две структуры: 

Dictionary<byte, List<Pattern>> PatternsByFirstByte

и 

List<Pattern> PatternsWithFirstCharacterWildcard

Таким образом, для каждого байта вы должны проверить небольшое количество шаблонов из PatternsByFirstByte и всех шаблонов PatternsWithFirstCharacterWildcard.Но это работает, если первый байт достаточно дискриминантен.Более продвинутым было бы создание полной структуры trie для хранения / индексации паттернов и / или обработки подстановочного знака в нулевой позиции (?? xx yy) другим способом.Ясно, что (?? ?? xx yy) эквивалентно (xx yy) с начальной позицией> = 2. Затем вы можете поместить в словарь шаблон xx yy и поместить где-нибудь аннотацию, что позиция должна быть> =2, как в самом классе Pattern, тогда будет: 

class Pattern
{
    public readonly byte?[] Bytes;
    public int MinimumStartingPosition;
}
...