Login | Register For Free | Help
Search for: (Advanced)

Mailing List Archive: ClamAV: devel

Why the function ac_maketrans defined size of array is 256?

 

 

ClamAV devel RSS feed   Index | Next | Previous | View Threaded


chatsiri at chatsiri

Feb 1, 2012, 7:53 PM

Post #1 of 4 (767 views)
Permalink
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


edwin at clamav

Feb 2, 2012, 1:02 AM

Post #2 of 4 (725 views)
Permalink
Re: Why the function ac_maketrans defined size of array is 256? [In reply to]

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


chatsiri at chatsiri

Feb 2, 2012, 5:18 PM

Post #3 of 4 (719 views)
Permalink
Re: Why the function ac_maketrans defined size of array is 256? [In reply to]

----- 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


tkojm at clamav

Feb 3, 2012, 7:59 AM

Post #4 of 4 (718 views)
Permalink
Re: Why the function ac_maketrans defined size of array is 256? [In reply to]

On Fri, 03 Feb 2012 08:18:24 +0700 Chatsiri Ratana
<chatsiri [at] chatsiri> 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>
(\/)\......... 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

ClamAV devel RSS feed   Index | Next | Previous | View Threaded
 
 


Interested in having your list archived? Contact Gossamer Threads
 
  Web Applications & Managed Hosting Powered by Gossamer Threads Inc.