Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Степень "похожести" двух строк 21.10.05 14:03
Автор: Heller <Heller> Статус: Elderman
|
Задача - защититься от флуда в виде дублирующихся сообщений либо незначительно отличающихся (флудер может приписывать к каждому следующему сообщению случайный символ в конце, удалять символ, заменять символ в середине и еще бесчисленное множество вариантов). В силу обстоятельств, защититься, запрещая много постов с одного IP я не могу.
Пока у меня есть только две идеи на этот счет. Первое - сравнивать длины строк. Вообще нормальные сообщения обычно значительно отличаются по длине. Если же поступает несколько сообщения с одной длиной или с длиной, отличающейся на единицу - есть подозрение на флуд. Способ хоть и простой, но сомнительный.
Второй вариант - вычислять контрольную сумму каждого сообщения (просто складывая ASCII-коды символов). Если контрольные суммы идущих подряд сообщений отличаются незначительно, опять же - флуд. Однако такой вариант тоже неоднозначен.
Можно проводить глубокий анализ сообщений, отыскивая похожие фрагменты, но такой вариант кажется трудоемким, что не позволительно, да и не совсем ясен механизм (например, как поступать при таком анализе, если в пост ставлена цитата?).
Может быть будут идеи как ещё это можно реализовать, особо при этом не загружая сервер?
Заранее благодарю.
|
|
Придумал решение! 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
|
|
|
|