Труды КНЦ вып.18 (ОКЕАНОЛОГИЯ вып. 4/2013(18))

объектов в виде графа с последующим извлечением из него подграфов, обладающих заданными характеристиками. Эти подграфы и будут представлять искомые кластеры. Очевидным алгоритмом кластеризации с помощью графов, находящим удовлетворяющие поставленным условиям кластеры, является алгоритм на основе поиска клик: 1) Для всех образцов сообщений в обучающей выборке попарно вычисляется значение меры сходства маршрутной информации. 2) Множество образцов сообщений представляется в виде полного неориентированного взвешенного графа, в котором вершинами являются образ­ цы сообщений, а веса рёбер между ними равны значению меры их сходства. 3) Из графа удаляются все рёбра, вес которых не достигает некоторого заданного порогового значения. 4) В оставшемся графе находятся максимальные клики, которые и будут являться искомыми кластерами. Нахождение клик - идеальная ситуация, когда в найденных кластерах попарное значение меры сходства между любыми членами кластера не будет превышать заданного порогового значения. Однако на практике это требование может оказаться чрезмерно строгим и привести к обнаружению или очень малого количества групп, или большого количества групп, состоящих из очень маленького числа членов, которые будут неинформативны и бесполезны. Во избежание такой ситуации требование поиска максимальных клик предлагается смягчить и вместо поиска максимальных клик предлагается использовать поиск к-сетей. Тогда будут найдены такие группы образцов сообщений, для любого члена которых сходство маршрутной информации со всеми остальными членами группы кроме к - 1 находится в пределах заданного порогового значения. Это предложение основано на том предположении, что если значение меры сходства маршрутной информации пары образцов сообщений не достигает заданного порогового значения, то при малых значениях к (к = 2 , 3) косвенно их восприятие спама всё равно можно считать сходным на основании наличия большого числа общих схожих образцов. Такой подход позволит определять в обучающей выборке сообщений большие и информативные кластеры, характеристики которых потенциально могут описывать некоторый ботнет. Поиск максимальных клик в графе - хорошо известная задача, одним из самых популярных алгоритмов решения которой является алгоритм Брона- Кербоша [9]. Для поиска максимальных к -сетей в графе может быть применён модифицированный алгоритм Брона-Кербоша, описанный в [10]. Заключение В данной работе предложена концепция идентификации ботнетов- источников рассылок почтового спама с помощью кластеризации обучающей выборки сообщений, на основе, содержащейся в них маршрутной информации. Такой подход потенциально обеспечивает большую эффективность в сравнении с методами идентификации спама, основанными на рассмотрении собственно тела письма как объекта идентификации. Эта эффективность обусловлена тем фактом, что характеристики источника нежелательных рассылок существенно 143