Mailing List Archive

Boyer-Moore
Hi,

Can you please point me to a paper or any other source that could help in
understanding the Boyer-Moore implementation in ClamAV?
Is it very different from the original Boyer-Moore algorithm?
Any help is really appreciated.

Thanks much,

~Moe
_______________________________________________
http://lurker.clamav.net/list/clamav-devel.html
Please submit your patches to our Bugzilla: http://bugs.clamav.net
Re: Boyer-Moore [ In reply to ]
An extended version of Boyer-Moore (BMEXT) is implemented in ClamAV. The
only difference lies in the use of Extended Bad Character Rule instead of
the BCR used in original B-M algorithm. I searched the Internet for a paper
related to BMEXT but found none.

On Thu, May 20, 2010 at 12:00 AM, Mohammed Al-Saleh <moealsaleh@gmail.com>wrote:

> Hi,
>
> Can you please point me to a paper or any other source that could help in
> understanding the Boyer-Moore implementation in ClamAV?
> Is it very different from the original Boyer-Moore algorithm?
> Any help is really appreciated.
>
> Thanks much,
>
> ~Moe
> _______________________________________________
> http://lurker.clamav.net/list/clamav-devel.html
> Please submit your patches to our Bugzilla: http://bugs.clamav.net
>



--
Vishrut Sharma
Member of ACM, SDN,
MSDNAA, NSR
_______________________________________________
http://lurker.clamav.net/list/clamav-devel.html
Please submit your patches to our Bugzilla: http://bugs.clamav.net
Re: Boyer-Moore [ In reply to ]
I've read ClamAV's Boyer-Moore implementation.
It does not seem to me that it uses Boyer-Moore algorithm at all.
The first step in adding BM patterns is the hashing step where you make
linked lists of patterns based on the hashing 3 characters from the pattern.
When scanning a buffer, specific linked lists will be matched against the
buffer based on the hashed results of buffer, again. When reaching a pattern
that could be the match, ClamAV does a very sequential string matching.
Check this code from matcher-bm.c
found = 1;
for(j = 0; j < p->length + p->prefix_length && off < length; j++,
off++) {
if(bp[j] != pt[j]) {
found = 0;
break;
}
}

Some body correct me if I am mistaken or add something I am missing.

Thanks,

~Moe




On Wed, May 19, 2010 at 12:47 PM, Vishrut Sharma <v.vishrut@gmail.com>wrote:

> An extended version of Boyer-Moore (BMEXT) is implemented in ClamAV. The
> only difference lies in the use of Extended Bad Character Rule instead of
> the BCR used in original B-M algorithm. I searched the Internet for a paper
> related to BMEXT but found none.
>
> On Thu, May 20, 2010 at 12:00 AM, Mohammed Al-Saleh <moealsaleh@gmail.com
> >wrote:
>
> > Hi,
> >
> > Can you please point me to a paper or any other source that could help in
> > understanding the Boyer-Moore implementation in ClamAV?
> > Is it very different from the original Boyer-Moore algorithm?
> > Any help is really appreciated.
> >
> > Thanks much,
> >
> > ~Moe
> > _______________________________________________
> > http://lurker.clamav.net/list/clamav-devel.html
> > Please submit your patches to our Bugzilla: http://bugs.clamav.net
> >
>
>
>
> --
> Vishrut Sharma
> Member of ACM, SDN,
> MSDNAA, NSR
> _______________________________________________
> http://lurker.clamav.net/list/clamav-devel.html
> Please submit your patches to our Bugzilla: http://bugs.clamav.net
>
_______________________________________________
http://lurker.clamav.net/list/clamav-devel.html
Please submit your patches to our Bugzilla: http://bugs.clamav.net
Re: Boyer-Moore [ In reply to ]
On 05/23/2010 04:11 AM, Mohammed Al-Saleh wrote:
> I've read ClamAV's Boyer-Moore implementation.
> It does not seem to me that it uses Boyer-Moore algorithm at all.

It is a multi-pattern version of Boyer Moore, I don't know its exact name.

Boyer-Moore algorithm itself allows you to search for 1 pattern in 1
string.
The one in ClamAV allows you to search for N patterns in 1 string, in a
single scan, without significantly increasing the time needed when N is
large.

Best regards,
--Edwin
_______________________________________________
http://lurker.clamav.net/list/clamav-devel.html
Please submit your patches to our Bugzilla: http://bugs.clamav.net