Clam open source unix antivirus scanner development

chatsiri | 2 Feb 2012 04:53

Why the function ac_maketrans defined size of array is 256?

Hello All,

     I  debug code of clamav.  Aho-Corasick( AC) Algorithms concepts for 
matching between virus and signature files. Step for AC is build trie ( 
keyword tree)  for inserting signature from virus database files. I  
have question in step build tire before matching with input information. 
Why source code in "static int ac_maketrans(struct cli_matcher *root)" 
[1]  define size of array is 256?.
      In addition, Do you using the Depth First Search Algorithm( DFS) 
for building trie?

Thanks you,
Chatsiri Rattana

1) http://goo.gl/bIqdx
_______________________________________________
http://lurker.clamav.net/list/clamav-devel.html
Please submit your patches to our Bugzilla: http://bugs.clamav.net

headers

Török Edwin | 2 Feb 2012 10:02

Re: Why the function ac_maketrans defined size of array is 256?

On 02/02/2012 05:53 AM, chatsiri wrote:
> Hello All,
> 
>     I  debug code of clamav.  Aho-Corasick( AC) Algorithms concepts for matching between virus and signature
files. Step for AC is build trie ( keyword tree)  for inserting signature from virus
> database files. I  have question in step build tire before matching with input information. Why source
code in "static int ac_maketrans(struct cli_matcher *root)" [1]  define size of array is 256?.

Because the trie matches byte-by-byte, so each node has 256 children, and that includes the root.

>      In addition, Do you using the Depth First Search Algorithm( DFS) for building trie?

ac_maketrans uses BFS.

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

headers

Chatsiri Ratana | 3 Feb 2012 02:18

Re: Why the function ac_maketrans defined size of array is 256?

----- Original message -----
> On 02/02/2012 05:53 AM, chatsiri wrote:
> > Hello All,
> > 
> > I   debug code of clamav.   Aho-Corasick( AC) Algorithms concepts for
> > matching between virus and signature files. Step for AC is build trie
> > ( keyword tree)   for inserting signature from virus database files. I 
> > have question in step build tire before matching with input
> > information. Why source code in "static int ac_maketrans(struct
> > cli_matcher *root)" [1]   define size of array is 256?.
> 
> Because the trie matches byte-by-byte, so each node has 256 children,
> and that includes the root.
What's contain in node? My view, Node contains a signature files for matching with virus in files.right? My
plan for optimized algorithm code of string matching with GPU.
> 
> > In addition, Do you using the Depth First Search Algorithm( DFS) for
> > building trie?
> 
> ac_maketrans uses BFS.
> 
> Best regards,
> --Edwin
> _______________________________________________
> 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

(Continue reading)

headers

Tomasz Kojm | 3 Feb 2012 16:59

Re: Why the function ac_maketrans defined size of array is 256?

On Fri, 03 Feb 2012 08:18:24 +0700 Chatsiri Ratana
<chatsiri <at> chatsiri.com> wrote:
> ----- Original message -----
>> On 02/02/2012 05:53 AM, chatsiri wrote:
>>> Hello All,
>>>
>>> I   debug code of clamav.   Aho-Corasick( AC) Algorithms concepts for
>>> matching between virus and signature files. Step for AC is build trie
>>> ( keyword tree)   for inserting signature from virus database files. I 
>>> have question in step build tire before matching with input
>>> information. Why source code in "static int ac_maketrans(struct
>>> cli_matcher *root)" [1]   define size of array is 256?.
>>
>> Because the trie matches byte-by-byte, so each node has 256 children,
>> and that includes the root.
> What's contain in node? My view, Node contains a signature files for matching with virus in files.right?
My plan for optimized algorithm code of string matching with GPU.

I'd suggest you have a look at the source code - all the information is
there.

--

-- 
   oo    .....         Tomasz Kojm <tkojm <at> clamav.net>
  (\/)\.........         http://www.ClamAV.net/gpg/tkojm.gpg
     \..........._         0DCA5A08407D5288279DB43454822DC8985A444B
       //\   /\              Fri Feb  3 16:57:08 CET 2012
_______________________________________________
http://lurker.clamav.net/list/clamav-devel.html
Please submit your patches to our Bugzilla: http://bugs.clamav.net

(Continue reading)