Newsgroups: fido7.su.virus From: herm1t <...@...z2.fidonet.org> Date: Mon, 21 Feb 2005 17:41:38 +0300 Subject: Виpyсы и война клонов [..skipped...] Ищем похожие вирусы =================== возьмем один пакет с исходниками вирусов, распарсим каждый вирус, отбросим аргументы комманд и данные. останется голый и непритязательный скелет вида: "mov/mov/add/mov/cmp/je/jmp..." ну и так далее, в таком же духе. закодируем все это безобразие целыми числами: "1/1/2/1/3/4/5..." (готовый список инструкций был украден из nasm [2]). пусть это будут цепочки V0,V1,...Vn. возьем алгоритм нечеткого сравнения AN EXTENSION OF UKKONEN'S ENHANCED DYNAMIC PROGRAMMING ASM ALGORITHM [1] для каждой пары цепочек (Vi,Vj) [таких пар у нас наберется n*(n - 1)/2.] расчитаем "edit distance" [минимальное количество простых операций требующихся для трансформации одной строки в другую. типичный набор операций - удаление, вставка, замена, перестановка символов]. таким образом мы получили полный взвешенный ненаправленный граф. на все про все понадобилось около 2000 строк кода на Си, включая всякий утиль. Ж;-) быстрый компьютер совсем не помешает (test-set из 400 вирусов общитывался на P4/1.8 чуть меньше часа). хотя конечно же в моей реализации (как всегда, на скорую руку) еще остается немалый простор для оптимизации. стоит также учесть, что задача хорошо распараллеливается. все любят картинки? ;-) преобразуем получившуюся матрицу в скрипт, для какого-нибудь визуализатора (я пробовал himmeli и graphviz [3]), чтобы не получить черный квадрат, отсеем те ребра, метрика которых превышает некий заданый порог. получившийся в результате работы dot(1) пост-скрипт можно посмотреть gv(1) [4] выглядит красиво. Ж;-) попытаемся из этой красоты извлечь какую-нибудь пользу. Ж-) на картинке невооруженным взглядом видны почтенные вирусные семейста, над некоторыми из них эксперименты по скрещеванию и выведению новых видов проходили настолько интенсивно, что на нашей картинке тот же Leprosy.* напоминает взрыв на макаронной фабрике. Ж-) видно также, что классификация вирусов совсем нелегкое дело: 7son.284 * 64/ \64 / \ 7son.332 *--2--* Riot.Fire.473 \ / 24\ / 24 * Riot.426 что значит эта цифра "2"? это значит, что для того, чтобы превратить один вирус в другой, нам потребуется нажать две кнопки в текстовом редакторе. (речь идет естественно про код, а не про пламенные послания I. Riot'а? Ж;-) не может же КЛ ошибаться, называя вирус Riot.Fire.473, а не 7son.Riot? натравим diff(1) на исходники обоих вирусов и выясним, что отличаются они преимущественно текстовыми строками. Ж-))) небось и две разные записи в базе имеются для детектирования столь непохожих друг на друга вирусов. Ж-) а пользователи удивляются: "чего базы большие, чего базы большие?" ... Ж-) поверьте, приведенный мною пример далеко не единственный. p.s. дополнив получившиеся данные информацией о хронологии можно построить "генеалогическое древо" вирусов, о других применениях я тут пока рассказывать не стану. Ж;-) 1) http://www.acm.org/~hlb/publications/asm/asm.html 2) http://sf.net/projects/nasm/ 3) http://www.graphviz.org/ 4) http://wwwthep.physik.uni-mainz.de/~plass/gv/