Контрольные суммы

Существенно уменьшить объемы требуемой памяти позволяет отказ от сигнатур в пользу контрольных сумм. Контрольная сумма — результат применения к произвольному набору данных некой Хеш — функции, рассчитывающей короткий «дайджест» постоянной длины.

В базе данных антивируса можно хранить не сами сигнатуры, а их короткие контрольные суммы. Такие же суммы рассчитываются «на лету» по содержимому тестируемых файлов. Несовпадение хранимого образца с результатом расчета означает отсутствие соответствующего вируса. А совпадение — лишь очень высокую вероятность заражения. Причина кроется в сути контрольных сумм: они, как и любые другие хеш-функции, представляют собой отображение большого множества «объектов»-прообразов на малое множество «дайджестов»-образов. Соответственно, всегда возможна Коллизия: несколько различных «объектов» могут иметь одинаковые «дайджесты», в частности «плохие» контрольные суммы могут оказаться не только у зараженных, но и у вполне «здоровых» файлов. Невысокая вероятность коллизий и трудность их целенаправленного генерирования — суть критерии качества того или иного метода расчета контрольных сумм. С этой точки зрения хороши так называемые «криптографические» хеш-функции: MD5, SHA-1, RIPEMD, ГОСТ 34.11-94 и др. К сожалению, эти алгоритмы довольно сложны с вычислительной точки зрения и не способны обеспечить высокую скорость расчета контрольных сумм. Поэтому на практике в антивирусах нашли применение несколько менее стойкие к коллизиям, зато гораздо быстрее вычислимые «технические» хеш-функции.

Чаще всего используются Циклические избыточные коды . Метод использования основан на представлении блока данных в виде непрерывного полинома с битовыми коэффициентами. В качестве контрольного кода используется остаток от деления этого полинома на более короткий «порождающий» полином, Имеющий длину N битов. Техника деления такова: 1) в конец блока данных добавляется N-1 нулевых битов; 2) вместо арифметического деления используется операция «сложение по модулю 2»; 3) сложение с «левыми» нулями промежуточных остатков не производится.