Когда большинство вирусов было бутовыми, когда обновлялся аидстестовский вирлист, лозинский еще не впал в маразм, а касперский еще только сосал не причмокивая... Жил-был вирус, и как только он не назывался - Doodle, Yankee, Music, и еще хрен знает как.

И была в том вирусе фича, а именно - коли патчил в вирусе бедняга-программист какой байт, так байт этот на место возвращался. То есть становился обратно, как был.

И с тех пор мучают вирмэйкеры себя и людей, доставая их вопросами - как же енто он, проклятый, восстанавливается, не делая второй своей копии?

Интуитивно ясно, что внесение избыточности в информацию позволяет находить и восстанавливать помехи. Пример тому - избыточность естественных языков. Сколько избыточности вносить и как ее считать, можно прочитать у Шеннона.

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

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

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

Вот и все. Максимальное количество восстанавливаемых подряд байт равно числу столбцов. Количество строк и столбцов выбирается как вам удобнее.

Конечно, можно попросту хранить вторую копию вируса. Но ее будет легко пропатчить. И вообще, это уже совсем другая байка.

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

Пример.

Есть данные, и есть контрольные суммы по строкам и по столбцам, посчитанные XORом. Пусть байт 74 (jz) изменили на EB (jmp).

  до изменения:               после изменения:

  90 90 90 90 90   90         90 90 90 90 90   90
  90 74 12 90 90   F6         90 EB 12 90 90   69
  90 90 90 90 90   90         90 90 90 90 90   90
  90 90 90 90 90   90         90 90 90 90 90   90

  00 E4 82 00 00              00 7B 82 00 00

В результате изменятся два байта контрольных сумм - один в суммах по строкам и один в суммах по столбцам.
Таким образом мы узнали координаты измененного байта в массиве данных.
Как вычислить старое значение байта? - проXORить старую контрольную сумму на новую и на новое значение байта.

F6 xor 69 xor EB = 74, либо
E4 xor 7B xor EB = 74.

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

   с++           pascal
c = d ^ e;    c := d xor e;
a ^= b;       a := a xor b;
a++;          a := a + 1;

#include <stdio.h>
#include <stdlib.h>

#define COLS 4                    // число столбцов (x)
#define ROWS 4                    // число строк (y)

void main()
{
  unsigned char a[ROWS][COLS];    // массив данных

  for (int y=0; y<ROWS; y++)      // заполним его всякой хуйней
  for (int x=0; x<COLS; x++)
    a[y][x]=random(256);

  unsigned char oy[ROWS]={0};     // контрольные суммы: по строкам
  unsigned char ox[COLS]={0};     // по столбцам

  for (int y=0; y<ROWS; y++)      // считаем контрольные суммы
  for (int x=0; x<COLS; x++)
  {
    oy[y]^=a[y][x];
    ox[x]^=a[y][x];
  }

  int y = random(ROWS);           // пропатчим два рандомных байта
  int x = random(COLS);           // (они должны быть в одной строке)
  int r = random(256);
  printf("randomizing a[%i][%i]: %02X --> %02X\n", y,x, a[y][x], r);
  a[y][x] = r;
  x--;
  r = random(256);
  printf("randomizing a[%i][%i]: %02X --> %02X\n", y,x, a[y][x], r);
  a[y][x] = r;

  unsigned char ny[ROWS]={0};     // новые контрольные суммы
  unsigned char nx[COLS]={0};

  for (int y=0; y<ROWS; y++)      // считаем и их
  for (int x=0; x<COLS; x++)
  {
    ny[y]^=a[y][x];
    nx[x]^=a[y][x];
  }

  for (int y=0; y<ROWS; y++)      // для каждого байта данных
  for (int x=0; x<COLS; x++)
    // если не совпадают суммы по строкам и столбцам
    if ((oy[y]!=ny[y])&&(ox[x]!=nx[x]))
    {
      printf("found error in a[%i][%i]\n", y,x);
      // два варианта "старых" значений байта
      int v1 = oy[y]^ny[y]^a[y][x];
      int v2 = ox[x]^nx[x]^a[y][x];
      printf(v1==v2?"correcting\n":"trying to correct\n");
      printf("%02X -> %02X\n", a[y][x], v2);
      // в качестве восстановленного байта используем оный посчитанный
      // при помощи суммы по столбцу (v2), так как вероятность изменения
      // нескольких байт подряд (т.е. в одной строке) больше
      ny[y] ^= a[y][x] ^ v2; // корректируем контрольные суммы в
      nx[x] ^= a[y][x] ^ v2; // соответствии с восстанавливаемым байтом
      a[y][x] = v2;          // восстанавливаем байт
    }
} // main

randomizing a[3][3]: 51 --> A6
randomizing a[3][2]: FC --> 11
found error in a[3][2]
trying to correct
11 -> FC
found error in a[3][3]
correcting
A6 -> 51

Может возникнуть вопрос: какими должны быть изменения, чтобы подобный метод не смог восстановить пропатченый байт?

В основном такими:

  00 00 00 00 00   nn   Нельзя определить, какие из указанных четырех байтов
  00 A  B  00 00   **   изменились: это могут быть A и D либо B и C,
  00 C  D  00 00   **   либо любые комбинации по 3 байта, либо все 4.
  00 00 00 00 00   nn
  00 00 00 00 00   nn

  nn ** ** nn nn

То есть такая схема подсчета контрольных сумм хорошо работает только если изменения произошли в пределах одной строки/столбца. Поэтому строки эффективно делать длиннее столбцов.

Если вас заинтересовало помехозащищенное кодирование - ищите линейный блоковый код, коды M из N, коды Хэмминга и тому подобную хрень.

* * *

(x) 2000 Z0MBiE, z0mbie.cjb.net