軟件安全實(shí)驗(yàn)2

軟件安全實(shí)驗(yàn)二實(shí)驗(yàn)報(bào)告班級(jí)：學(xué)號(hào)：姓名;指導(dǎo)教師：實(shí)驗(yàn)二惡意軟件特征代碼法檢測(cè)1.實(shí)驗(yàn)?zāi)康?.1掌握基于特征匹配的誤用檢測(cè)技術(shù)原理和方法1.2掌握基于雙數(shù)組-AC算法的多模式特征匹配算法實(shí)現(xiàn)1.3利用構(gòu)建的自動(dòng)機(jī)掃描目標(biāo)文件2.實(shí)驗(yàn)內(nèi)容2.1流程圖2.2構(gòu)建自動(dòng)機(jī)所定義的數(shù)據(jù)結(jié)構(gòu)structout輸出函數(shù)的鏈表結(jié)構(gòu)體structtotal記錄邊數(shù)與狀態(tài)數(shù)的結(jié)構(gòu)體structAC存儲(chǔ)自動(dòng)機(jī)的鄰接表structNEXTNEXT表的結(jié)構(gòu)體2.3構(gòu)建自動(dòng)機(jī)所使用的函數(shù)voidinit_AC(AC*A,intn)初始化自動(dòng)機(jī)的鄰接表AC*CreatAC(AC*A,totalt)創(chuàng)建自動(dòng)機(jī)的鄰接表voidinit_ne()初始化NEXT表函數(shù)NEXT*CreatNEXT(ACA[],totalt)創(chuàng)建NEXT表，同時(shí)創(chuàng)建BASE表，CHECK表voidoutfun(char*output[],AC*A,totalt,out*head)創(chuàng)建輸出函數(shù)voidFailure(AC*A,totalt,out*head)創(chuàng)建失效函數(shù)AC*depthfun(AC*A,totalt)計(jì)算各狀態(tài)的深度voidprint(AC*A,totalt,int*f,out*head)讀取測(cè)試文本并輸出檢測(cè)結(jié)果2.4轉(zhuǎn)向函數(shù)、失效函數(shù)、輸出函數(shù)的構(gòu)建過(guò)程1.轉(zhuǎn)向函數(shù)轉(zhuǎn)向函數(shù)通過(guò)NEXT,BASE,CHECK來(lái)實(shí)現(xiàn)。由于鄰接表存儲(chǔ)了所有節(jié)點(diǎn)，因此循環(huán)查找所有頭節(jié)點(diǎn)，若next不為NULL說(shuō)明不是葉節(jié)點(diǎn)，可計(jì)算NEXT。若為葉節(jié)點(diǎn)則查找下一個(gè)狀態(tài)，知道所有狀態(tài)都查找過(guò)則推出。創(chuàng)建NEXT表的過(guò)程先從根節(jié)點(diǎn)開(kāi)始，一層一層的創(chuàng)建，同時(shí)計(jì)算BASE表中的值，并填充CHECK表中的值，每一層結(jié)束后在遍歷左側(cè)的鄰接表進(jìn)行下一層的NEXT表創(chuàng)建，知道全部狀態(tài)創(chuàng)建完成為止。Next為轉(zhuǎn)向函數(shù)表（數(shù)組、鏈表），下標(biāo)是位置偏移量，輸出是狀態(tài)值。Base表（數(shù)組），下標(biāo)是狀態(tài)值，輸出是Base值。Next表中當(dāng)前狀態(tài)為s，輸入為c時(shí)，假設(shè)應(yīng)跳轉(zhuǎn)為狀態(tài)t，狀態(tài)t在Next表中的位置=狀態(tài)S的位置+狀態(tài)S的Base值+輸入c的ASCII碼值。Check表（數(shù)組），下標(biāo)是狀態(tài)值，輸出是下標(biāo)狀態(tài)的父狀態(tài)的值。在創(chuàng)建的過(guò)程中，每一層的狀態(tài)可能要作為下一層狀態(tài)的父狀態(tài)，因此在鄰接表中記錄NEXT中的pos，存儲(chǔ)在AC中，方便最后特征碼的檢測(cè)。2.失效函數(shù)為了計(jì)算深度為d的s狀態(tài)的失效函數(shù)值，我們考慮深度為d-1的狀態(tài)r，存在某個(gè)輸入a，使得g(r,a)=s。執(zhí)行以下步驟來(lái)創(chuàng)建失效函數(shù)：Step1：state=f(r)。Step2：f(s)=g(state,a)其中a根據(jù)CHECK表得出，并現(xiàn)先行確定初始狀態(tài)和第一層失效狀態(tài)的失效函數(shù)為f(s)=0。3.輸出函數(shù)輸出函數(shù)以鏈表的方式儲(chǔ)存。要求遍歷所有從根狀態(tài)到葉狀態(tài)的通路，在每個(gè)分支節(jié)點(diǎn)處將此狀態(tài)壓棧，在遍歷完這一個(gè)分之后彈棧，并遍歷此狀態(tài)的另一分支，同時(shí)在進(jìn)行到每一節(jié)點(diǎn)的同時(shí)將字符壓棧，并與模式集進(jìn)行比較，若存在此模式則鏈接到輸出鏈表上。在每一個(gè)狀態(tài)不僅要比較本身的字符串與模式集，還需要比較此狀態(tài)的失效狀態(tài)字符串與輸出鏈表，最終創(chuàng)立一個(gè)單向鏈表，保存所有需要的輸出函數(shù)。2.5建立的NEXT,BASE,CHECK表檢測(cè)結(jié)果NEXT表中數(shù)據(jù)BASECHECK數(shù)據(jù)以及失效函數(shù)檢測(cè)結(jié)果TEXT.TXTTEXT.TXTsheishisboyfriendandheisabadguyandhisdoyishersRESULT.TXTRESULT.TXThe 3she 3his 8he 22his 37he 44she 44hers 46從以上結(jié)果可以看出，NEXTBASECHECK建立成功，數(shù)值正確，失效函數(shù)建立無(wú)誤，檢測(cè)結(jié)果經(jīng)檢查無(wú)誤。由此，雙數(shù)組AC的實(shí)現(xiàn)成功。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表時(shí)使用 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表已經(jīng)存滿！\n";returnNULL; }j++;if(j>=t.n) { cout<<"buildnextsucess!\n";break; }}returnne;}//輸出函數(shù)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("查找父狀態(tài)失敗\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狀態(tài)標(biāo)號(hào)，求深度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<<"匹配結(jié)束\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