软件安全实验2

软件安全实验二实验报告班级：学号：姓名;指导教师：实验二恶意软件特征代码法检测1.实验目的1.1掌握基于特征匹配的误用检测技术原理和方法1.2掌握基于双数组-AC算法的多模式特征匹配算法实现1.3利用构建的自动机扫描目标文件2.实验内容2.1流程图2.2构建自动机所定义的数据结构structout输出函数的链表结构体structtotal记录边数与状态数的结构体structAC存储自动机的邻接表structNEXTNEXT表的结构体2.3构建自动机所使用的函数voidinit_AC(AC*A,intn)初始化自动机的邻接表AC*CreatAC(AC*A,totalt)创建自动机的邻接表voidinit_ne()初始化NEXT表函数NEXT*CreatNEXT(ACA[],totalt)创建NEXT表，同时创建BASE表，CHECK表voidoutfun(char*output[],AC*A,totalt,out*head)创建输出函数voidFailure(AC*A,totalt,out*head)创建失效函数AC*depthfun(AC*A,totalt)计算各状态的深度voidprint(AC*A,totalt,int*f,out*head)读取测试文本并输出检测结果2.4转向函数、失效函数、输出函数的构建过程1.转向函数转向函数通过NEXT,BASE,CHECK来实现。由于邻接表存储了所有节点，因此循环查找所有头节点，若next不为NULL说明不是叶节点，可计算NEXT。若为叶节点则查找下一个状态，知道所有状态都查找过则推出。创建NEXT表的过程先从根节点开始，一层一层的创建，同时计算BASE表中的值，并填充CHECK表中的值，每一层结束后在遍历左侧的邻接表进行下一层的NEXT表创建，知道全部状态创建完成为止。Next为转向函数表（数组、链表），下标是位置偏移量，输出是状态值。Base表（数组），下标是状态值，输出是Base值。Next表中当前状态为s，输入为c时，假设应跳转为状态t，状态t在Next表中的位置=状态S的位置+状态S的Base值+输入c的ASCII码值。Check表（数组），下标是状态值，输出是下标状态的父状态的值。在创建的过程中，每一层的状态可能要作为下一层状态的父状态，因此在邻接表中记录NEXT中的pos，存储在AC中，方便最后特征码的检测。2.失效函数为了计算深度为d的s状态的失效函数值，我们考虑深度为d-1的状态r，存在某个输入a，使得g(r,a)=s。执行以下步骤来创建失效函数：Step1：state=f(r)。Step2：f(s)=g(state,a)其中a根据CHECK表得出，并现先行确定初始状态和第一层失效状态的失效函数为f(s)=0。3.输出函数输出函数以链表的方式储存。要求遍历所有从根状态到叶状态的通路，在每个分支节点处将此状态压栈，在遍历完这一个分之后弹栈，并遍历此状态的另一分支，同时在进行到每一节点的同时将字符压栈，并与模式集进行比较，若存在此模式则链接到输出链表上。在每一个状态不仅要比较本身的字符串与模式集，还需要比较此状态的失效状态字符串与输出链表，最终创立一个单向链表，保存所有需要的输出函数。2.5建立的NEXT,BASE,CHECK表检测结果NEXT表中数据BASECHECK数据以及失效函数检测结果TEXT.TXTTEXT.TXTsheishisboyfriendandheisabadguyandhisdoyishersRESULT.TXTRESULT.TXThe 3she 3his 8he 22his 37he 44she 44hers 46从以上结果可以看出，NEXTBASECHECK建立成功，数值正确，失效函数建立无误，检测结果经检查无误。由此，双数组AC的实现成功。3.程序源代码#include<iostream>#include<stdio.h>#include<stdlib.h>#include<stack>#include<string.h>usingnamespacestd;#definemax256typedefstructout{chars[10];intid;structout*next;}out;typedefstructtotal{intn;inte;}total;typedefstructAC{intid;structAC*next;charc;intpos;//建立BASE表时使用 intdep;}AC;typedefstructNEXT{intid;charc;}NEXT;intBASE[max];intCHECK[max];intf[max];NEXTne[max];voidinit_AC(AC*A,intn){intk;for(k=0;k<n;k++){(A+k)->id=-1;(A+k)->next=NULL;(A+k)->c='\0';(A+k)->pos=-1;}}AC*CreatAC(AC*A,totalt){inthead,tail; charedge; AC*ptr=NULL; init_AC(A,t.n);inti;for(i=0;i<t.n;i++){cout<<i<<"nodeshascreatesuccessful\n"; A[i].id=i;A[i].next=NULL;}for(i=0;i<t.e;i++){cout<<"startNOENDNO\n";cin>>head>>tail;cout<<"输入模式字符\n"; cin>>edge; ptr=&(A[head]); while(ptr->next!=NULL) ptr=ptr->next; AC*p=newAC;p->id=tail;p->c=edge;p->next=NULL; ptr->next=p; }returnA;}voidinit_ne(){ inti; for(i=0;i<max;i++) { ne[i].c='\0'; ne[i].id=-1; } return;}NEXT*CreatNEXT(ACA[],totalt){ne->id=0;ne->c='\0';inti,j,k;j=0;k=0;A->pos=0;while(1){if((A+j)->next==NULL) { j++;if(j>=t.n){cout<<"buildnextsucess!\n";break;}continue; }AC*temp=(A+j)->next;printf("1111\n");for(i=1;i<max;i++){if((ne+i)->id==-1){(ne+i)->id=temp->id;(ne+i)->c=temp->c;(A+temp->id)->pos=i;BASE[j]=i-(A+j)->pos-temp->c;CHECK[temp->id]=j;while(temp->next!=NULL){temp=temp->next;k=temp->c-(ne+i)->c; if((i+k)>0) { (ne+i+k)->id=temp->id; (ne+i+k)->c=temp->c; (A+temp->id)->pos=(i+k); CHECK[temp->id]=j; } else { return0; }}break;}} if(i==max) {cout<<"NEXT表已经存满！\n";returnNULL; }j++;if(j>=t.n) { cout<<"buildnextsucess!\n";break; }}returnne;}//输出函数voidoutfun(char*output[],AC*A,totalt,out*head){//out*p=NULL;AC*temp=A;intcoun[max];inti;for(i=0;i<t.n;i++){coun[i]=0;temp=(A+i)->next;while(temp!=NULL){coun[i]++;temp=temp->next;}}temp=&(A[0]);i=0;intj,k,conter=0;stack<int>s;stack<char>mod1;stack<char>mod2;charch,x;chartest[10]={'\0'}; charclear[10]={'\0'};s.push(-1); head->id=-1; head->next=NULL;while(!s.empty()){while(coun[i]!=0){if(coun[i]>1)s.push(i);for(j=0;j<coun[i];j++)temp=temp->next;coun[i]--;i=temp->id;ch=temp->c; temp=A+i;mod1.push(ch);while(!mod1.empty()){x=mod1.top();mod1.pop();mod2.push(x); conter++;} k=0;while(!mod2.empty()){x=mod2.top();test[k]=x; k++;for(j=0;j<4;j++){ if(strcmp(test,output[j])==0&&conter==1){out*lo=NULL;lo=(out*)malloc(sizeof(out));lo->id=temp->id;strcpy(lo->s,test);lo->next=head->next;head->next=lo; for(intcon=0;con<10;con++) test[con]='\0';}}mod1.push(x);mod2.pop(); conter--;}}while(i!=s.top()&&!(mod1.empty())){mod1.pop();i=CHECK[i];temp=A+i;} s.pop();}}voidFailure(AC*A,totalt,out*head){intstart=0;AC*temp=NULL;if(A->next!=NULL) temp=&(A[0]);elsereturn;f[0]=0; while(temp->next!=NULL){temp=temp->next; f[temp->id]=0;}start=temp->id+1;intstate,pos;charch;inti;for(i=start;i<t.n;i++){temp=(A+CHECK[i])->next;if(temp==NULL){printf("查找父状态失败\n");return;}do{if(i==temp->id){ch=temp->c;break;}temp=temp->next;}while(temp!=NULL);state=f[CHECK[i]];pos=(A+state)->pos+BASE[state]+ch;if((ne+pos)->c==ch){f[i]=(ne+pos)->id; out*outtemp=head; outtemp=outtemp->next; while(outtemp!=NULL) { if(outtemp->id==f[i]) { out*lo=NULL; lo=(out*)malloc(sizeof(out)); lo->id=i; strcpy(lo->s,outtemp->s); lo->next=head->next; head->next=lo; } outtemp=outtemp->next; }}elsef[i]=0;}}AC*depthfun(AC*A,totalt){AC*ptr=NULL;inti,deptemp,f; A[0].dep=0; for(i=0;i<t.n;i++) { f=0; ptr=&(A[i]); deptemp=ptr->dep; deptemp++; while(ptr->next!=NULL) { ptr=ptr->next; A[ptr->id].dep=deptemp; f=1; } if(f) A[ptr->id].dep=deptemp; }returnA;}voidprint(AC*A,totalt,int*f,out*head){FILE*fp1,*fp2;charch,s[10]={'\0'};intsum=1;fp1=fopen("test.txt","r");fp2=fopen("result.txt","w");ch=fgetc(fp1);inti=0;intk=0;//保存zi状态标号，求深度intpos,chance=0;while(ch!=EOF){pos=(A+i)->pos+BASE[i]+ch;if((ne+pos)->c==ch){ k=(ne+pos)->id;if(CHECK[k]==i){//ch=fgetc(fp1);i=(ne+pos)->id; chance=0;out*p=NULL; out*ptemp=NULL;p=head->next;while(p!=NULL){if(p->id==i){itoa(sum,s,10); fputs(p->s,fp2); fputc('\t',fp2);fputs(s,fp2);fputc('\n',fp2); ptemp=p;}p=p->next;}} else { i=f[i]; if(chance) { ch=fgetc(fp1); sum++; } chance=1; continue; }}else{i=f[i]; if(chance) { ch=fgetc(fp1); sum++; } chance=1; continue;} ch=fgetc(fp1); sum++;} cout<<"匹配结束\n";fclose(fp1);fclose(fp2);}intmain(){char*output[4]={"he","she","his","hers"}; inti; totalt; cout<<"CREATEadjacencylist\n";cout<<"Nnumberofstates,numberofedges\n";cin>>t.n>>t.e; AC*A=newAC[t.n]; AC*ptr; Cr