информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Где водятся OGRыЗа кого нас держат?Все любят мед
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Блокировка российских аккаунтов... 
 Отзыв сертификатов ЦБ РФ, ПСБ,... 
 Памятка мирным людям во время информационной... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Степень "похожести" двух строк 21.10.05 14:03  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
Задача - защититься от флуда в виде дублирующихся сообщений либо незначительно отличающихся (флудер может приписывать к каждому следующему сообщению случайный символ в конце, удалять символ, заменять символ в середине и еще бесчисленное множество вариантов). В силу обстоятельств, защититься, запрещая много постов с одного IP я не могу.

Пока у меня есть только две идеи на этот счет. Первое - сравнивать длины строк. Вообще нормальные сообщения обычно значительно отличаются по длине. Если же поступает несколько сообщения с одной длиной или с длиной, отличающейся на единицу - есть подозрение на флуд. Способ хоть и простой, но сомнительный.

Второй вариант - вычислять контрольную сумму каждого сообщения (просто складывая ASCII-коды символов). Если контрольные суммы идущих подряд сообщений отличаются незначительно, опять же - флуд. Однако такой вариант тоже неоднозначен.

Можно проводить глубокий анализ сообщений, отыскивая похожие фрагменты, но такой вариант кажется трудоемким, что не позволительно, да и не совсем ясен механизм (например, как поступать при таком анализе, если в пост ставлена цитата?).

Может быть будут идеи как ещё это можно реализовать, особо при этом не загружая сервер?

Заранее благодарю.
Ищи "fuzzy string searching" 24.10.05 13:39  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
Пара ссылок:
http://en.wikipedia.org/wiki/Levenshtein_distance
http://en.wikipedia.org/wiki/Bitap_algorithm

Вот только не лучше ли прикрутить старого доброго байеса? Потратить немного времени на обучение и спамеры (и флудеры как разновидность спамеров) будут сосать
точнее, ищи шинглы 24.10.05 14:06  
Автор: paganoid Статус: Member
<"чистая" ссылка>
http://www.spamtest.ru/document.html?context=15932&pubid=32

кстати, не думаю, что баеса можно этому научить - стоп-слов то нету
Придумал решение! 21.10.05 23:52  
Автор: Heller <Heller> Статус: Elderman
Отредактировано 22.10.05 00:09  Количество правок: 2
<"чистая" ссылка>
Оно как всегда просто и эффективно.

То же самое, что я предлагал в топике, о котором вспомнил HandleX (http://bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=19&m=115424), только подсчитывать количество слов сраз в двух сообщениях. Как я сразу не догадался? :)

ЗЫ. Кстати, это решение, которое я тогда предлагал, на поверку оказалось эффективным. Пока ещё ни одного нормального сообщения просто так не отсёк, но и ни одного флудера не пропустил. Константу выбрал 1.5. Если кому надо, то вот код на Perl:

sub analys() {
 my ($c2, $srctext);
 $srctext=join (" ", @_);
# я не стал сильно заморачиваться с оптимизацией :)
# потом поправлю
 $c2=0;
 @srctext=split /[^\w\x84-\xFF]+/, $srctext;
# разбиение идет по нетекстовым сомволам для KOI8-R
 @srctext=grep {length>3;} @srctext;
 if (!@srctext) {@srctext=split /[^\w\x84-\xFF]+/, $srctext}
# аналогично
 for (my $i=0;$i<=$#srctext;$i++) {
  if (!defined($srctext[$i])) {next}
  $c2++;
  for (my $j=$i+1;$j<=$#srctext;$j++) {if ($srctext[$i] eq $srctext[$j]) {undef $srctext[$j]}}
 }
 return $c2!=0?($#srctext+1)/$c2:0;
}

---
А если флудер начнёт постить циклическки 2 и более разных сообщения? Например одно типа «Форум ацтой», второе «Вебмастир казёл», третье «Хостер урод», и потом всё сначала? :-)) 22.10.05 09:21  
Автор: HandleX <Александр М.> Статус: The Elderman
<"чистая" ссылка>
С такой модификацией. 21.10.05 15:10  
Автор: lunc <Alexander Krizhanovsky> Статус: Member
<"чистая" ссылка>
> Второй вариант - вычислять контрольную сумму каждого
> сообщения (просто складывая ASCII-коды символов). Если
> контрольные суммы идущих подряд сообщений отличаются
> незначительно, опять же - флуд. Однако такой вариант тоже
> неоднозначен.

С такой модификацией.
Считаем какой-то вес (хоть сумму символов, хоть еще что) не для всего сообщения, а для некоторых кусков (нужно выбрать оптимальный их размер). Сравнивать не только значения весов, но и количество "совпавших" элементов, их общее количество и схожесть их между собой.
Пример:
abcd | emkf | fdmp | zz
добавляем в начало:
zzza | bcde | mkff | dmpz | z

Таким образом сильно будут отличапться только первыйэлемент. Здесь нужно будет создавать дерево или хэш для сохранения веов.
Для выбора кнстант, по которым можноопределить похожие элементы, можно обучить систему -- анализировать сообщения разных пользователей, корректировать свою чувствительность.
Не совсем понятно 21.10.05 22:55  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
> С такой модификацией.
> Считаем какой-то вес (хоть сумму символов, хоть еще что) не
> для всего сообщения, а для некоторых кусков (нужно выбрать
> оптимальный их размер). Сравнивать не только значения
> весов, но и количество "совпавших" элементов, их общее
> количество и схожесть их между собой.
> Пример:
> abcd | emkf | fdmp | zz
> добавляем в начало:
> zzza | bcde | mkff | dmpz | z
>
> Таким образом сильно будут отличапться только
> первыйэлемент.
Честно говоря не заметил, чтобы остальные элементы, кроме первого, были сильно похожи. Как по хешам, так и по количеству повторяющихся символов. То ли я не так понял, то ли где-то ошибка. Этот вариант возможен, если выбирать длинные блоки, но это чаще всего невозможно из-за малого размера сообщений. Потом, в этом случае, ИМХО, достаточно делать то-то одно - либо считать количество символов в каждом блоке, либо счтать checksum для каждого блока.

> Здесь нужно будет создавать дерево или хэш
> для сохранения веов.
Зачем? Сообщения не большие и хранить нужно максимум два-три посладних. Простой массив хорошо пойдет.

> Для выбора кнстант, по которым можноопределить похожие
> элементы, можно обучить систему -- анализировать сообщения
> разных пользователей, корректировать свою чувствительность.

Меня это натолкнуло на похожий метод, но более простой и эффективный, ИМХО. Делается почти всё то же самое:
1. Разбиваем оба сообщения на небольшие блоки.
2. Сравниваем количество одинаковых символов для каждой пары соответствующих блоков обоих сообщений, записываем полученную последовательность.

Например:
Админ
- де|бил,ха-хаха! |Щас т|ебе с|айт з|афлуж|у!!!
Админ
-д!|ебил,хах|а-ха!Щас |тебе |сайт |зафлу|жу!!!
5, 4, 4, 4, 4, 4, 4, 4, 4 (последний блок можно не рассматривать).
Получается, что в целом - отличие в символах для каждой пары блоков постоянно, за исключением конечно числа блоков. Соответственно, пара таких сообщений является флудом. Для надежности можно проводить анализ два раза с разной длиной блоков, а длину блока выбирать исходя из длины сообщения.
Я имел ввиду, например, следующее. Определяем хэш функцию... 22.10.05 02:45  
Автор: lunc <Alexander Krizhanovsky> Статус: Member
<"чистая" ссылка>
> > С такой модификацией.
> > Считаем какой-то вес (хоть сумму символов, хоть еще
> что) не
> > для всего сообщения, а для некоторых кусков (нужно
> выбрать
> > оптимальный их размер). Сравнивать не только значения
> > весов, но и количество "совпавших" элементов, их общее
> > количество и схожесть их между собой.
> > Пример:
> > abcd | emkf | fdmp | zz
> > добавляем в начало:
> > zzza | bcde | mkff | dmpz | z
> >
> > Таким образом сильно будут отличапться только
> > первыйэлемент.
> Честно говоря не заметил, чтобы остальные элементы, кроме
> первого, были сильно похожи. Как по хешам, так и по
> количеству повторяющихся символов. То ли я не так понял, то
> ли где-то ошибка.
Я имел ввиду, например, следующее. Определяем хэш функцию типа:
a1 ^ (a2 << 2) ^ (a3 << 4) ^ (a4 << 6)
ai -- это символ в блоке. Например для 2 сообщений: при каждои попадании при первом сообщении значение ячейки хэш таблицы увеличивается на 1, при втором уменьшается на 1 (начальное значение 0). Проходим хэш -- считаем не нулевые ячейки (пусть это будет N). Может быть здесь будет лучше для каждой ячейки хэш таблицы задавать не точное значение, а интервал значений хыш функции (ну или сразу функцию такую задать).

> Этот вариант возможен, если выбирать
> длинные блоки, но это чаще всего невозможно из-за малого
> размера сообщений.
По моему, вообще чем меньше сообщение, тем сложнее определить его отклонение -- в моем варианте я бы ввел функцию, зависящую от длинны сообщения для определения является ли N флудовым значением.
Блоки нужны для большей (по моему мнению) устойчивости, как к сильным изменениям в одной части сообщения, так и к маленьким равномерно распределенным изменениям.
Уже пробегало на форуме, поищи... 21.10.05 15:03  
Автор: HandleX <Александр М.> Статус: The Elderman
<"чистая" ссылка>
Я помню только это: 21.10.05 22:16  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
Я помню только это: http://bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=19&m=115424, но у меня несколько другая задача.

http://bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=19&m=115424
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2022 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach