Помехозащищенные вирусы

Z0mbie
Top Device Online [6]
Июнь 2000

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

                for (int x=0; x&lt;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 --&gt; %02X\n", y,x, a[y][x], r);

        a[y][x] = r;

        x--;

        r = random(256);

        printf("randomizing a[%i][%i]: %02X --&gt; %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);

                                // два варианта "старых" значений байта</i>

                                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, коды Хэмминга и тому подобную хрень.

[Вернуться к списку] [Комментарии (0)]

до изменения						после изменения
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

до изменения						после изменения
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

VX Heavens

Помехозащищенные вирусы

до изменения						после изменения
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