#include "sbom.h"
#define CHECK 0
static int max_memory=0;
/*
* malloc memory function
*/
static void * SBOM_MALLOC (int n)
{
void *p;
p = malloc (n);
if (p)
max_memory += n;
return p;
}
void GetMem( int * memnum)
{
*memnum=max_memory/1024;
}
/************************************************************************/
/* Queue Operation Function from Snort AC Algorithm */
/************************************************************************/
//Simple QUEUE NODE
typedef struct _qnode
{
int state;
struct _qnode *next;
}QNODE;
//Simple QUEUE Structure
typedef struct _queue
{
QNODE * head, *tail;
int count;
}QUEUE;
//Queue Init Operation
static void queue_init (QUEUE * s)
{
s->head = s->tail = 0;
s->count = 0;
}
//Queue Add Operation
static void queue_add (QUEUE * s, int state)
{
QNODE * q;
if (!s->head)
{
q = s->tail = s->head = (QNODE *) SBOM_MALLOC (sizeof (QNODE));
// MEMASSERT (q, "queue_add");
q->state = state;
q->next = 0;
}
else
{
q = (QNODE *) SBOM_MALLOC (sizeof (QNODE));
// MEMASSERT (q, "queue_add");
q->state = state;
q->next = 0;
s->tail->next = q;
s->tail = q;
}
s->count++;
}
//Queue Remove Operation
static int queue_remove (QUEUE * s)
{
int state = 0;
QNODE * q;
if (s->head)
{
q = s->head;
state = q->state;
s->head = s->head->next;
s->count--;
if (!s->head)
{
s->tail = 0;
s->count = 0;
}
// AC_free (q);
free(q);
}
return state;
}
//Queue Count Operation
static int queue_count (QUEUE * s)
{
return s->count;
}
//Queue Free Operation
static void queue_free (QUEUE * s)
{
while (queue_count (s))
{
queue_remove (s);
}
}
#if defined(SAVE_STATE)
void SaveState(void* vp, FILE* fp)
{
SBOM_Machine* sbom = (SBOM_Machine*)vp;
int j,i=0;
PatternList* p;
fprintf(fp,"SBOM INFO\n");
for(i=0;i<sbom->num_state;i++)
{
fprintf(fp,"\n----state: %d----\n",i);
fprintf(fp,"state->end:%d\n",sbom->state[i].state_id);
fprintf(fp,"supply link:%d\n",sbom->state[i].supplyNode);
for(j=0;j<256;j++)
{
if(sbom->state[i].nextNode[j]!=-1)
{
fprintf(fp,"next[%c]=%d\n",j,sbom->state[i].nextNode[j]);
}
}
p=sbom->state[i].pat;
if(p)
{
fprintf(fp,"pattern:{");
while(p)
{
for(j=0;j<p->n;j++)
fprintf(fp,"%c",p->pattern[j]);
fprintf(fp,",");
p=p->next;
}
fprintf(fp,"}\n");
}
}
}
void SaveSbom(SBOM_Machine *sbom, char* file)
{
int i = 0;
FILE* fp = fopen(file,"w");
SaveState(sbom,fp);
fclose(fp);
}
#endif
/************************************************************************/
/* STATIC FUNCTION IMPLEMENTATION */
/************************************************************************/
static void BFSTraverse(SBOM_Machine* sbom, int (*visit)(void* p,int n))
{
unsigned char* visited=NULL;
int u,w,v=0;
int i = 0;
QUEUE Q, *q=&Q;
visited = (unsigned char*)SBOM_MALLOC(sbom->num_state);
memset(visited,0,sbom->num_state);
queue_init(q);
for(v=0;v<sbom->num_state;v++)
{
if(visited[v]==0){
visited[v]=1;
visit(sbom,v);
queue_add(q,v);
while(queue_count(q)>0)
{
u=queue_remove(q);
for(i=0;i<256;i++)
{
if(w=sbom->state[u].nextNode[i]!=-1)
{
if(visited[w]==0)
{
visited[w]=1;
visit(sbom,w);
queue_add(q,w);
}
}
}
}
}
}
queue_free(q);
free(visited);
}
static unsigned char* SBOM_Reverse(unsigned char *pat,int n)
{
unsigned char *ch = NULL;
int i = 0;
ch = (unsigned char*)SBOM_MALLOC(n);
for(i=0; i<n;i++)
{
ch[n-1-i]=pat[i];
}
return ch;
}
//use len min of patterns to build trie
static void AddPatternTrie(SBOM_Machine* sbom, PatternList* pat)
{
int i = 0;
unsigned char* p ,*h= NULL;
unsigned int state=0, next,n;
PatternList *pt = NULL;
n=0;
sbom->state[0].state_id = 0;
while (pat)
{
state = 0;
/*reserve pattern*/
h=p = SBOM_Reverse(pat->pattern,pat->n);
i=sbom->lmin;
p=h+pat->n-sbom->lmin;
for (; i > 0; p++, i--)
{
next = sbom->state[state].nextNode[*p];
if(next==-1)
break;
state = next;
}
//
for (; i > 0; p++, i--)
{
sbom->num_state++;
sbom->state[state].nextNode[*p] = sbom->num_state;
sbom->state[sbom->num_state].state_id =sbom->num_state;
state=sbom->num_state;
}
pt = (PatternList*)SBOM_MALLOC(sizeof(PatternList));
memcpy(pt,pat,sizeof(PatternList));
pt->next=sbom->state[state].pat;
sbom->state[state].pat=pt;
free(h);
h=NULL;
p=NULL;
pat=pat->next;
}
sbom->num_state++;
}
//Travel Factor Oracle
static int TravelOracle(void* pv,int state)
{
int i;
int par,cur,down;
SBOM_Machine* sbom=(SBOM_Machine*)pv;
par = state;
for(i=0;i<256;i++)
{
cur = sbom->state[par].nextNode[i];
if(cur==-1)
continue;
down = sbom->state[par].supplyNode;
while(down!=-1&&sbom->state[down].nextNode[i]==-1)
{
sbom->state[down].nextNode[i]=cur;
down=sbom->state[down].supplyNode;
}
if(down !=-1)
{
sbom->state[cur].supplyNode = sbom->state[down].nextNode[i];
}
else
{
sbom->state[cur].supplyNode = 0;
}
}
return 0;
}
void* SBOM_New()
{
SBOM_Machine* sbom = (SBOM_Machine*)SBOM_MALLOC(sizeof(SBOM_Machine));
if(!sbom)
return NULL;
memset(sbom,0,sizeof(SBOM_Machine));
return sbom;
}
void SBOM_Free(void*sb)
{
int i = 0;
PatternList* p,*t;
SBOM_Machine* sbom = (SBOM_Machine*)sb;
for(i=0;i<sbom->max_state;i++)
{
p = sbom->state[i].pat;
while(p)
{
t = p->next;
memset(p,0,sizeof(PatternList));
free(p);
p = t;
}
memset(&sbom->state[i],0,sizeof(SBOM_State));
}
free(sbom->state);
sbom->state = NULL;
p = sbom->pat;
while(p)
{
t = p->next;
// free(p->pattern);
memset(p,0,sizeof(PatternList));
free(p);
p = t;
}
free(sbom);
}
int SBOM_Preproccess(void* par1, void*pv)
{
SBOM_Machine* sbom = (SBOM_Machine*)par1;
PatternList *list,* p = (PatternList*)pv;
SBOM_State* root=sbom->state;
int lmin = 32768;
int lmax = 0;
int i = 0;
sbom->max_state = 0;
list = p;
sbom->pat = p;
//find pattern min len and max len, max states
while(p)
{
if(p->n<lmin)
lmin = p->n;
if(p->n>lmax)
lmax = p->n;
sbom->total_pattern_bytes+=p->n;
p=p->next;
sbom->num_pat++;
}
sbom->lmin = lmin;
sbom->lmax = lmax;
sbom->max_state = sbom->lmin* sbom->num_pat;
sbom->state = (SBOM_State*)SBOM_MALLOC(sbom->max_state*sizeof(SBOM_State));
memset(sbom->state,-1,sbom->max_state*sizeof(SBOM_State));
for(i=0;i<sbom->max_state;i++)
{
sbom->state[i].pat=NULL;
}
//build trie
p=list;
AddPatternTrie(sbom,p);
root = sbom->state;
sbom->state[0].supplyNode=-1;
// build oracle
BFSTraverse(sbom,TravelOracle);
#if defined(SAVE_STATE)
SaveSbom(sbom,"sbom.txt");
#endif
return sbom->num_pat;
}
/*
int SBOM_Search(void* vp,unsigned char * T, int m, int ( *callback )( void *data,int), void * data )
{
SBOM_MachineS* sbom = (SBOM_MachineS*)vp;
int i,pos ,j=0;
unsigned char* Tx = (unsigned char* )data;
int root, cur;
PatternListS* list;
int nfound = 0;
int n = T-Tx;
int id = 0;
root = 0;// sbom->state;
pos=0;
while(pos<=m-sbom->lmin)
{
j =sbom->lmin-1;
cur=root;
while(j>=0&&cur!=-1)
{
cur = sbom->state[cur].nextNode[T[pos+j]];
j--;
}
if(cur!=-1 && j<=0)
{
for(i=0;i<sbom->state[cur].pat_num;i++)
{
list = (PatternListS*)&sbom->pat[sbom->state[cur].match
