Быстрый поиск сигнатуры HEX в файле, как это делается?

[Человек_Борща]

Доброго времени суток!

От нечего делать, думаю как же реализуется алгоритм поиска HEX-сигнатуры в файле, когда база сигнатур насчитывает >5000-10000 записей, в течении нескольких секунд.

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

Ярким примером будет PEid.

Собственно как это работает?

Но куда более интересный вопрос:
Как найти уникальную последовательность байт имеея 2 файла?
Я уже пытался, найти решение 2-го вопроса, вот таким образом:

  type
    TByteArr = array of byte;
    TStringArr = array of String;


var
  Form1: TForm1;

implementation

{$R *.dfm}


function BufToHex(Buf:Byte; Size: Cardinal): string;
const
  // maps nibbles to hex digits
  cHexDigits: array[$0..$F] of Char = (
    '0', '1', '2', '3', '4', '5', '6', '7',
    '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'
  );
var
  I: Cardinal;
  PB: ^Byte;
begin
  PB := @Buf;
  Result := '';
  SetLength(Result, 2 * Size);
  I := 1;
  while I <= 2 * Size do
  begin
    Result[I] := cHexDigits[PB^ shr 4];
    Result[I + 1] := cHexDigits[PB^ and $0F];
    Inc(PB);
    Inc(I, 2);
  end;
end;

function ByteToHex(Bytes:Byte): string;
begin
  Result := BufToHex(Bytes,1);
end;

procedure TForm1.Button3Click(Sender: TObject);
const
  cSkipBytes = '|?:%d|';
var
  fs0, fs1: TfileStream;
  fs0Buff: array of Byte;
  fs1Buff: array of Byte;
  PushBit: string;
  SkipCount: Int64;
  i0, i1: LongInt;
  iSize: Int64;
begin
  Memo1.Clear;
  fs0 := TFileStream.Create(Edit1.Text, fmOpenRead);
  fs1 := TFileStream.Create(Edit2.Text, fmOpenRead);
  SkipCount := 0; //Обнуляем счётчик
  try
    Gauge1.Progress := 0;
    SetLength(fs0Buff, fs0.Size);
    SetLength(fs1Buff, fs1.Size);

    fs0.Read(fs0Buff, fs0.Size);
    fs1.Read(fs1Buff, fs1.Size);
    Gauge1.MaxValue := fs0.Size; //Базовый файл
    for i0 := 0 to Length(fs0Buff) do
    begin
      for i1 := 0 to Length(fs1Buff) do
      begin
        //Сранение 0-го файла 1-ым
        if not (fs0Buff[i0] = fs1Buff[i1]) then
        begin
          //Если кол-во пропущенный байт...
          if not (SkipCount <= 0) then
          begin
            PushBit := PushBit + Format(cSkipBytes, [SkipCount]);
            SkipCount := 0;
          end;

          PushBit := PushBit + ByteToHex(fs0Buff[i0]);
          //Пишем не изменившийся байт
          SkipCount := 0; //Обнуляем счётчик
        end
        else
        begin
          Inc(SkipCount); //Увеличиваем счётчик
        end;
      end;
      Gauge1.Progress := i0;
    end;

    //Если Тек. файл отличается от базового
    if fs1.Size > fs0.Size then
    begin
      //Болучаем отличие в рамзере
      iSize := fs1.Size - fs0.Size;
      SetLength(fs1Buff, iSize);
      fs1.Position := fs0.Size;
      fs1.Read(fs1Buff, iSize);
      Gauge1.MaxValue := iSize;
      //тупо дописываем оставшиеся байты.
      for i1 := 0 to Length(fs1Buff) do
      begin
        PushBit := PushBit + ByteToHex(fs0Buff[i1]);
        Gauge1.Progress := i1;
      end;
    end;

    Memo1.Lines.Add(PushBit);
  finally
    FreeAndNil(fs0);
    FreeAndNil(fs1)
  end;
end;

Допустим, когда имеется полиморфный вирус.
И есть 2, 3 его мутации.

как там найти уникальные байты?

[Arigato]

Есть алгоритмы быстрого поиска подстроки в строке. Наиболее простой алгоритм примерно такой:
Пусть исходная строка: S = S1S2...Sn - символы строки.
Подстрока: P1P2...Pm - ее символы.
Находим сумму: SumP := P1 + P2 + ... + Pm - суммируем коды символов.
Также находим сумму: SumS := S1 + S2 + ... + Sm - сумма m-первых кодов символов исходной строки.
Если SumP = SumS, то проверяем, не является ли последовательность S1S2...Sm нужной подстрокой. Если нет, то идем дальше.
SumS := SumS - S1 + S(m+1)
Опять сравниваем SumP = SumS.
Далее: SumS := SumS - S2 + S(m+1)
И т.д. Если на каком-то шаге SumP = SumS, то это еще не факт, что подстрока найдена, в таких случаях делается посимвольная проверка.

Есть еще алгоритм Бойера-Мура: http://ru.wikipedia.org/wiki/%D0%90%...83%D1%80%D0%B0 , он сложнее.

Разумеется, все это можно применять не только к строкам, а к любым последовательностям.

[Человек_Борща]

Хм, подыму тему ибо надо и я не понимаю..

Есть сигнатура CE 08 F9 5E D4 9B 64 1A
Я задаю её как:

const
  Sing=array[0..7] of byte=($CE, $08 ,$F9,$5E,$D4,$9B,$64,$1A);

Файл бинарный, я открываю в TMemoryStream.

В ТЗ сказано что сигнатура в конце файла.
Я могу:
1. Идти от начала и до конца
2. Начать с конца

1. понятно движение слева на право.
2. не понятно, как читать с конца? Движение курсора справа-налево, и тогда я должен искать:

const
  Sing=array[0..7] of byte=($1A, $64, $9B, $D4, $5E, $F9, $08 ,$CE);

?

Как искать саму сигнатуру в принципе?
Есть вариант, чтения байт в массив размером 8 байт и потом по-байтно сравнить с сигнатурой.

Но опять же проблема, файл может и не делится на 8.

Подскажите куда смотреть?

[Аватар]

А если так: читаем очереной блок в буфер. С помощью Pos ищем вхождение сигнатуры. Если нет проверяем последний байт буфера насчет вхождения в сигнатуру, если есть, то проверка - нет ли начала сигнатуры в конце блока. Если есть, то в следующем прочитанном блоке проверяем первые байты блока на совпадение с концом сигнатуры. И т.д. Если читать блоки с конца файла, то проверка начала и конца буфера с точностью наоборот. Если файл целиком умещается в буфер, то вообще проблем нет. Насчет эффективности уверенности нет. Предполагаю, что Pos побыстрее будет, чем программный цикл по байтам. С приведением буфера и сигнатуры к String для использования в Pos проблем нет