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