[devel] Re: bloom filters

[Alexey Tourbin <at@altlinux.ru>]

[-- Attachment #1: Type: text/plain, Size: 2034 bytes --]

On Mon, Sep 19, 2005 at 12:18:34AM +0400, Alexey Tourbin wrote:
> Bloom filter используется, например, в spellchecker'ах, когда нужно
> захешировать все "правильные" слова.  Произвольное неправильное слово
> может с очень небольшой вероятность определиться как правильное.

Возвращаюсь к нашим баранам.  Есть список символов def "с адресом" --
эти символы провайдятся, и есть список символов ref "без адреса" --
которые, стало быть, кто-то должен провайдить.

$ awk -F'\t' '{print$NF}' def |sort -u >defsym
$ awk -F'\t' '{print$NF}' ref |sort -u >refsym
$ head defsym
A
A20Proc16
AAAAddAVPToMessage
AAABuildMsgBuffer
AAACloneAVP
AAAConvertAVPToString
AAACreateAVP
AAAFindMatchingAVP
AAAFreeAVP
AAAFreeMessage
$ wc -l defsym refsym
 1592688 defsym
 174130 refsym
 1766818 total
$

Ассиметрия в природе.  Провайдится гораздо больше, чем требуется.
Теперь попробуем воткнуть сюда фильтр Блума.

$ bloom -n 1592688 defsym >defsym.bf
$ ls -s1 defsym defsym.bf
56872 defsym
 1864 defsym.bf
$

Вот!  Меньше минимум на порядок, во всех отношениях.
Пробуем проверить malloc:

$ bloom -e malloc defsym.bf; echo $?
0
$ bloom -e Malloc defsym.bf; echo $?
1
$

Ну.  Работает.  Как и следовало ожидать.  То есть превентивная мера,
которую можно применить для проверки *всех* ELF'ов, а не только
публичных библиотек, состоит в том, что обнаруженные undefined symbols
из вывода `ldd -r' нужно попробовать отыскать в общем "отстойнике".
Если их там нет, то пакет нужно *точно* давить.  Кстати, false positive
в данном случае означает, что по ошибке можно пропустить пакет, который
следовало бы задавить, потому что символ в отстойники будет "найден"
(это в некотором смысле лучше, чем задавить пакет невинный).  Если
добавить в bloom.c элемент случайности, то сбой проверки будет одиночным
явлением.  (Вообще, по поводу сбоев: вероятность сбоев нужно оценивать
комплексно; например, учитывать вероятность выхода из строя сборочных
серверов, которая, кажется, выше статистического 1 процента.)

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]