## ПОМЕХОЗАЩИЩЕННЫЕ ВИРУСЫ

Когда большинство вирусов было бутовыми, когда обновлялся аидстестовский вирлист, лозинский еще не впал в маразм, а касперский еще только сосал не причмокивая... Жил-был вирус, и как только он не назывался - 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.

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

Пример на C++

Примечание (для тех кто не знает C):

       с++           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)