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





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Уже пробегало на форуме, поищи... 21.10.05 15:03  Число просмотров: 3396
Автор: HandleX <Александр М.> Статус: The Elderman
<"чистая" ссылка>
<theory>
Степень "похожести" двух строк 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-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach