15.2. Составить программу (псевдокод1), реализующую простейший алгоритм вычисления контрольной суммы (цифровой подписи) произвольного файла.
Контрольная сумма – последовательность бит фиксированной длинны, которая ставится в соответствие файлу. При изменении файла с определенной вероятностью (пропорциональной длине контрольной суммы) изменяется и его контрольная сумма. Сравнив контрольную сумму исходного и полученного файла, можно сделать вывод о том, подвергался ли он искажениям.
Простейший
алгоритм подсчета контрольной суммы
произвольного файла заключается в
побитном сложении всех его битов (по
модулю 22,
т.е. 1
1=0, 1
0=0, 1
0=1, 0
1=1)
Программа на псевдокоде будет выглядеть примерно так («примерно так» – цитата из лекции):
sum:=0;
for I to bit_ length (file) sum:=Sum
get_bit (file, i);
//здесь предполагается, что функция bit_ length (file) возвращает количество бит в файле file, а функция get_bit (file, i) возвращает i-ый бит файла file.
15.3. Из двух строк (последовательностей) символов выделить сигнатуру максимальной длины. Рассказать об основных подходах к выбору сигнатур в антивирусах для поиска деструктивных программ.
Рассмотрим методы обнаружения антивирусом своих жертв.
Обнаружение, основанное на сигнатурах – метод работы антивирусов и систем обнаружения вторжений, при котором антивирус, просматривая файл (или передаваемый по сети пакет), обращается к словарю, в котором содержатся сигнатуры известных атак или вирусов. Под сигнатурой понимается фрагмент кода, однозначно идентифицирующий вирус. Например, вирус Email-Worm.Win32.Happy содержит строку <<Happy New Year 1999!!>>, которая с низкой вероятностью может встретиться в другой программе.
Основной принцип, по которому выделяются сигнатуры – она должна содержать (слово содержать было пропущено, по смыслу подходит) только уникальные строки из этого файла, настолько характерные, чтобы гарантировать минимальную возможность ложного срабатывания. Разработка сигнатур осуществляется вручную путем кропотливого исследования нескольких файлов, зараженных (или принадлежащих) одним вирусом.
Автоматическая генерация сигнатур (особенно в условиях полиморфных вирусов3) пока не дает удовлетворительных результатов.
Каждый современный антивирус имеет обширную (несколько сот тысяч) базу сигнатур, которая регулярно обновляется. Проблема обнаружения, основанного на сигнатурах, заключаеся в том, что новый вирус (сигнатуры которого еще нет в базе) может беспрепятственно обойти антивирусную защиту. При этом создание сигнатуры и доставка ее пользователем занимает несколько десятков часов, в то время как теоретически, вирус может захватить весь интернет меньше, чем за 30 секунд.
Программа, выделяющая сигнатуру максимальной длины в двух строках, получает на вход две строки str1 и str2, после чего просматривает все возможные фрагменты строки str1 (сначала подстроки разной длины, начинающиеся с первого символа, затем подстроки, начинающиеся со второго символа и т.д., то есть используют два вложенных цикла). Каждая из этих подстрок проверяется, например, вхождением в str2. Если вхождение существует, проверяется длина подстроки, и если она больше ранее запомненной, эта подстрока запоминается вместе со своей длиной. Результатом работы программы будет самая длинная из найденных подстрок.
len:=0; {изначально максимальная длина подстроки = 0}
signature:=” “;
for i:=1 to length (str1)-1 do
for j:=i+1 to length (str1) do begin
substr:=copy (str1,I,j);
if pos (substr, str2)>0 then
if length (substr)>len then begin
signature:=substr;
len:=length (substr);
end;
end;
{результатом является подстрока signature}