| Newsgroups |
gmane.comp.security.virus.clamav.devel |
| Message-ID |
<[email protected]> |
Sorry for late reply.
My implementation as follow:
I modified the original algorithm, when cur state is root, using the 2-gram hash table to accelerate filtering.
In following implementation, building dat table dependent on the Trie structure that had been builded.
References:
http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=31365&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D31365
---------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include "common.h"
#include "my_dat_ac.h"
#define T_SIZE 655360
#define printf(fmt,arg...)
struct input_list {
unsigned char node;
struct bfs_list *next;
};
enum {
T_MUL_ST = 1, // multi-state
T_SIN_ST, // sigle-state
T_TER_ST, // terminal-state
T_SEP_ST // separate-state
};
struct _state_node {
struct my_ac_patt * list;
uint32_t fail;
};
struct _state_build {
struct input_list *valid_input_bfs;
struct input_list *valid_input_bfs_last;
uint16_t type;
uint8_t from_char;
struct _state_node state;
};
struct _state_build build_new[T_SIZE] = {};
static uint32_t new[T_SIZE] = {};
static uint32_t base[T_SIZE] = {};
static uint32_t check[T_SIZE] = {};
static struct _state_node check_match[T_SIZE] = {};
static uint32_t old[T_SIZE] = {};
static uint32_t dat_hash[65536] = {};
static int my_input_enqueue(struct input_list **bfs, struct input_list **last, unsigned char n)
{
struct input_list *new;
new = (struct input_list *) malloc(sizeof(struct input_list));
if(!new) {
cli_errmsg("bfs_enqueue: Can't allocate memory for input_list\n");
return CL_EMEM;
}
new->next = NULL;
new->node = n;
if(*last) {
(*last)->next = new;
*last = new;
} else {
*bfs = *last = new;
}
return CL_SUCCESS;
}
static int my_input_dequeue(struct input_list **bfs, struct input_list **last)
{
struct input_list *lpt;
int pt;
if(!(lpt = *bfs)) {
return -1;
} else {
*bfs = (*bfs)->next;
pt = lpt->node;
if(lpt == *last)
*last = NULL;
free(lpt);
return pt;
}
}
static int my_input_queue_foreach(struct input_list **bfs)
{
struct input_list *lpt;
int pt;
if(!(lpt = *bfs)) {
return -1;
} else {
*bfs = (*bfs)->next;
pt = lpt->node;
return pt;
}
}
extern struct bitmap_state *get_bit_popcnt_next_state(struct bitmap_state *pcur_state, unsigned char a);
static int max_check_index = 0;
int my_dat_ac_build(struct my_matcher *root)
{
int count1 =0;
struct bfs_list *multi_bfs = NULL, *multi_bfs_last = NULL;
struct bfs_list *sep_bfs = NULL, *sep_bfs_last = NULL;
int res;
uint8_t a;
struct input_list *tmp;
//init value------s : = 1 ; new(s) : = 1 ; queue := { s } ;
int i;
for(i=0;i<T_SIZE;i++)
base[i] = 2;
struct bitmap_state *bitmap_st = root->ac_root;
struct bitmap_state *bitmap_st1;
uint32_t s = bitmap_st->state_id , s1;
new[s] = bitmap_st->state_id;
old[bitmap_st->state_id] = s;
//base[new[s]] = bitmap_st->state_id;
my_bfs_enqueue(&multi_bfs, &multi_bfs_last, (void*)bitmap_st);
/* Routine for multistates */
while((bitmap_st = my_bfs_dequeue(&multi_bfs, &multi_bfs_last)) != (void*)queue_NULL) {
s = (uint32_t)bitmap_st->state_id;
printf("-----M-----%03d(%03d)----------\n", s, new[s]);
/* Let s be the next state in queue */
abcd:
tmp = build_new[s].valid_input_bfs;
while((res = my_input_queue_foreach(&tmp)) != -1) {
a = (uint8_t)res;
if(check[base[new[s]] + a] != 0){
base[new[s]] = base[new[s]] + 1;
goto abcd;
}
}
while((res = my_input_dequeue(&build_new[s].valid_input_bfs, &build_new[s].valid_input_bfs_last)) != -1) {
/*for each a in list[s]*/
a = (uint8_t)res;
// while(check[base[new[s]] + a] != 0){
// base[new[s]] = base[new[s]] + 1;
// }
check[base[new[s]] + a] = new[s];
bitmap_st1 = get_bit_popcnt_next_state(bitmap_st, a);
s1 = bitmap_st1->state_id;
new[s1] = base[new[s]] + a;
old[base[new[s]] + a] = s1;
if(new[s1] > max_check_index){
max_check_index = new[s1];
}
printf("o_stat %03d -%02x- new_stat %03d;;;;%d\n", s1, a, new[s1], ++count1);
//build hash
if(bitmap_st1->level == 2){
uint8_t hash_str[2];
hash_str[0] = build_new[s].from_char;
hash_str[1] = build_new[s1].from_char;
uint16_t hash_val = *(uint16_t*)hash_str;
dat_hash[hash_val] = new[s1];
}
// check_match[new[s1]].fail = new[build_new[s1].state.fail];
// check_match[new[s1]].list = build_new[s1].state.list;
if(build_new[s1].type != T_SEP_ST){
my_bfs_enqueue(&multi_bfs, &multi_bfs_last, (void*)bitmap_st1);
}
else {
my_bfs_enqueue(&sep_bfs, &sep_bfs_last, (void*)bitmap_st1);
}
}
}
/* Routine for single state */
while((bitmap_st = my_bfs_dequeue(&sep_bfs, &sep_bfs_last)) != queue_NULL) {
s = (uint32_t)bitmap_st->state_id;
printf("-----S-----%03d(%03d)----------\n", s, new[s]);
while(build_new[s].type != T_TER_ST){
a = (uint8_t)my_input_dequeue(&build_new[s].valid_input_bfs, &build_new[s].valid_input_bfs_last);
while(check[base[new[s]] + a] != 0){
base[new[s]] = base[new[s]] + 1;
}
check[base[new[s]] + a] = new[s];
bitmap_st1 = get_bit_popcnt_next_state(bitmap_st, a);
s1 = bitmap_st1->state_id;
new[s1] = base[new[s]] + a;
old[base[new[s]] + a] = s1;
if(new[s1] > max_check_index){
max_check_index = new[s1];
}
//build hash
if(bitmap_st1->level == 2){
uint8_t hash_str[2];
hash_str[0] = build_new[s].from_char;
hash_str[1] = build_new[s1].from_char;
uint16_t hash_val = *(uint16_t*)hash_str;
dat_hash[hash_val] = new[s1];
}
printf("o_stat %03d -%02x- new_stat %03d;;;;%d\n", s1, a, new[s1], ++count1);
// check_match[new[s1]].fail = new[build_new[s1].state.fail];
// check_match[new[s1]].list = build_new[s1].state.list;
s = s1;
bitmap_st = bitmap_st1;
}
}
printf("max_check_index %d\n", max_check_index);
for(i = 0;i<=max_check_index;i++)
{
check_match[i].fail = new[build_new[old[i]].state.fail];
check_match[i].list = build_new[old[i]].state.list;
}
return 0;
}
static unsigned int fail_count[32] = {};
uint32_t my_dat_ac_fail_proc(unsigned char a, uint32_t s)
{
#if 0
// return 1;
// uint32_t t;
// s = check_match[s].fail;
// t = a + base[s];
// if(check[t] != s)
// return 1;
// else
// return t;
static int tdfsdfasdf = 1;
tdfsdfasdf++;
return 1;
#else
uint32_t t;
int i = 0;
do{
fail_count[i++]++;
if(s == 1) return s;
s = check_match[s].fail;
t = a + base[s];
}while(check[t] != s);
return t;
#endif
}
static uint32_t st_hash_fail_count = 0;
static uint32_t st_hash_ref_count = 0;
uint32_t my_dat_ac_fail_proc_hash(uint32_t s, uint8_t *buffer, uint32_t *i, uint32_t length)
{
uint32_t t;
int k = 0;
uint32_t j;
do{
fail_count[k++]++;
if(s == 1){//root
loop:
j = *i;
//hash search
for(;j<length-1;j++)
{
st_hash_ref_count++;
if(dat_hash[*(uint16_t*)(buffer+j)]){
*i = j+1;
return dat_hash[*(uint16_t*)(buffer+j)];
}
st_hash_fail_count++;
}
*i = j+1;
return 0;
}
s = check_match[s].fail;
if(s == 1)
goto loop;
t = buffer[*i] + base[s];
}while(check[t] != s);
return t;
}
int my_dat_ac_scanbuff(const unsigned char *buffer, uint32_t length,const struct my_matcher *root)
{
int i;
// for(i = 1;i< root->ac_nodes+1;i++)
// {
// //printf("old s %03d 's type is %d\n", i, build_new[i].type);
// printf("old s %03d new_stat is %d\n", i, new[i]);
// }
// for(i = 0;i< T_SIZE;i++)
// {
// if(check_match[i].fail == 0)
// printf("stat %05d fail null[%d]\n", old[i], i);
// }
// fprintf(stdout, "trans num: %d\n", my_ac_trans_sum(root));
//return 0;
memset((void*)fail_count, 0x00, sizeof(fail_count));
uint32_t s = 1, t;
printf("my_dat_ac_scanbuff\n", i, build_new[i].type);
int count = 0;
for (i = 0; i < length; i++) {
t = buffer[i] + base[s];
if(check[t] != s){
//fail
//t = my_dat_ac_fail_proc(buffer[i], s);
t = my_dat_ac_fail_proc_hash(s, buffer, &i, length);
//continue;
}
// if(s == 1)
// st_hash_ref_count++;
printf("%05d --%02x--> %05d\n", old[s], buffer[i], old[t]);
s=t;
if(check_match[s].list){
//final
//fprintf(stdout, "hit:sigid %d:pos %d:\n", check_match[s].list->sigid, i);
count++;
}
}
// fprintf(stdout, "hit count %d, st_hash_fail_count %u st_hash_ref_count %u\n", count, st_hash_fail_count, st_hash_ref_count);
// for(i = 0;i<8;i++)
// fprintf(stdout, "%u,", fail_count[i]);
// fprintf(stdout, "\n");
return s;
}
int my_dat_update_input(uint32_t s, unsigned char a, uint32_t t)
{
printf("id:%03d -- %02x -- id:%03d\n", s, a, t);
my_input_enqueue(&build_new[s].valid_input_bfs, &build_new[s].valid_input_bfs_last, a);
build_new[t].from_char = a;
return 0;
}
int my_dat_update_patlist(uint32_t s, struct my_ac_patt *list)
{
build_new[s].state.list = list;
return 0;
}
int my_dat_update_fail(uint32_t s,uint32_t fail)
{
build_new[s].state.fail = fail;
return 0;
}
int my_dat_update_terminal(uint32_t s)
{
build_new[s].type = T_TER_ST;
return 0;
}
int my_dat_update_type(struct bitmap_state **st_array, uint16_t array_len)
{
int i = array_len-1;
if(build_new[st_array[i]->state_id].type !=0)
return 0;
int flag = 0;
for(; i>=0;i--)
{
if(st_array[i]->sumary[_bitmap_group] > 1 || flag)
{
build_new[st_array[i]->state_id].type = T_MUL_ST;
flag = 1;
}
else
build_new[st_array[i]->state_id].type = T_SEP_ST;
}
return 0;
}
_______________________________________________
http://lurker.clamav.net/list/clamav-devel.html
Please submit your patches to our Bugzilla: http://bugs.clamav.net