markov.cpp

用C++编写的遗传算法,markov是应用在入侵检测上的 用的数据是 http://www.cs.unm.edu/~immsec/data/synth-sm.html 上的

// 作者　LanXiaoWei  (TianJin)  2005/10
//　　[e-mail]   
//　　这个markov是应用在入侵检测上的　用的数据是
//http://www.cs.unm.edu/~immsec/data/synth-sm.html 上的

#include <fstream>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <fstream>

using namespace std;



#define ww 5//窗口大小
#define yuzhi 1e-4//阈值大小

class Markov
{


public:
	vector<int> v;//原始的数据数组(从文件录入)
	int sum;//原始的数据数组个数
	
	vector<int> v_simple;//无重复的数据数组 元素是调用号 下标对应每个调用号
	map<int,int> m;//对于每个调用号 的记数

	double *p;
	double *q;//
	ofstream marpfile;
public:

	Markov()
	{
		marpfile.open("marp.txt",ios::trunc|ios::out);
	}

	//读入 正常数据文件 (含百万次的调用号序列)  放在 变量	vector<int> v中
	ReadFile(string s)
	{
	
		ifstream file(s.c_str(),ios::in);
		if (!file) 
			{cout<<"in ReadFile(string)  error";
			exit(-1);
			}

		string tline;
		while(getline(file,tline,'\n'))
		{
			string::size_type pos=tline.find(' ');
			string data=tline.substr(pos);
	
			v.push_back(atoi(data.c_str()));
			

		}
		
	}



	//建立	Markov模型
	CreateM()

	{	cout<<"start in CreateM"<<endl;

		//精简的vector,下标重要!!
		v_simple=v;
		sort(v_simple.begin(),v_simple.end());
		vector<int>::iterator i=unique(v_simple.begin(),v_simple.end());
		v_simple.erase(i,v_simple.end());

		
		//输出两个大小
		cout<<"v.size():"<<v.size()<<endl;
		cout<<"v_simple.size()"<<v_simple.size()<<endl;


		//建立map<int,int> 每个调用号与其出现的次数 的映射!! 
		for(vector<int>::iterator jj=v.begin();jj!=v.end();jj++)
		{	
			if(!m.count(*jj))
				m.insert(map<int,int>::value_type((*jj),1));
			else				
				m[(*jj)]+=1;//numberi[syscall]
				
		}
	

		//q 数组存放 每个调用号(在v.size()总的)中出现的概率
		q=new double[m.size()];
		int j=0;
		for(map<int,int>::iterator ii=m.begin();ii!=m.end();ii++)
		{	
			q[j]=(*ii).second/(double)v.size();//q[i] i=0~m.size()-1

			j++;
		}
		

	
		//p 存放转换矩阵 m.size()*m.size()
		p=new double[m.size()*m.size()];
		for(int z=0;z<m.size()*m.size();z++)
			p[z]=0;

		
		int precall=v[0];
		//将v的所有数据序列依次读一遍 得到numberij[][]
		for(vector<int>::iterator iii=v.begin();iii!=(v.end());iii++)
		{	
			int syscall=(*iii);
			
			int i=0;
			while(syscall!=v_simple[i])i++; 

			int j=0;
			while(precall!=v_simple[j])j++; 

			p[j*m.size()+i]++;// (j,i)	j-->i		 
			precall=syscall;
		 
		}
		

		//得到转移矩阵p
		for(int k=0;k<m.size()*m.size();k++)
		{
			int i=k/m.size();
			int j=k%m.size();

			
			int xia=v_simple[i];
			p[k]=p[k]/m[xia];

			//输出
			cout<<"Matrix: "<<v_simple[i]<<"-->"<<v_simple[j]<<":"<<"("<<p[k]<<")"<<endl;
			
		}

		
		cout<<"end of CreateM"<<endl;

	}


	//用单步来对测试数据文件(含正常和异常两种文件)测试 
	Single_Markov(string testfile)
	{
		int abn=0;//sum中的异常 个数
		//窗口的大小 从#Define 获得
		int w=ww;
	    int *s=new int [5];


		//输入测试数据文件

		ifstream file(testfile.c_str(),ios::in);
		if (!file) 
		{
			cout<<"In Single_Markov() file error";
			exit(-1);
		}
		
		//
		marpfile<<endl<<endl;
		marpfile<<"testfile:"<<testfile<<endl;

		string tline;
		int sum=0;//测试文件的调用号总数目

		for(int i=0;(i<w)&&(!file.eof());i++)
		{
			getline(file,tline,'\n');
			
			string::size_type pos=tline.find(' ');
			string data=tline.substr(pos);
			
			s[i]=atoi(data.c_str());

		}
		

		sum++;
		//第一个w窗口
		if(Markov_Work_Abnormal(s,w-1,w)) 
			abn++;
		
		
		int c=0;//
		while(getline(file,tline,'\n'))
		{
			sum++;
			string::size_type pos=tline.find(' ');
			string data=tline.substr(pos);
			//c是新的结束点	
			s[c]=atoi(data.c_str());
		
			if(Markov_Work_Abnormal(s,c,w) )
				abn++;		
			c=(c+1)%w;	
		
		}
		

		double  percent=abn/(double)sum;
		//输出
		cout<<endl<<"The Final Result:  "<<percent;
		
		delete []s;
	
	}



	Output()
	{
	/*	for(vector<int>::iterator i=v.begin();i!=v.end();i++)
		{
			cout<<(*i)<<endl;
			
		}*/


		/*for(map<int,int>::iterator i=m.begin();i!=m.end();i++)
		{
			cout<<(*i).first<<"  "<<(*i).second<<endl;
		}*/


		/*for(int i=0;i<m.size();i++)
		{
			cout<<v_simple[i]<<endl;
		}*/
		
	}


	Release()
	{
		delete []q;	
		delete []p;
		marpfile.close();

	}



	//对一个w窗口的计算 支持度
	bool Markov_Work_Abnormal(int *s,int end,int w)
	{	
		//设置阈值
		double thrashhold=double(yuzhi);
		int start=(end+1)%w;
		int i=0;
		double marp;//该w窗口的 支持度

		while(s[start]!=v_simple[i]&&i<v_simple.size())
			i++;
		//找到第一个调用号的 序号
		if (i==v_simple.size())
		{	//没找到
			marp=0;
			cout<<"find one not occur in normal data !"<<endl;
		}
		else 
			marp=q[i];
		
		//tempfile<<"q[i]:"<<q[i]<<" ";
		//与w
		for(int mm=1;mm<w;mm++)
		{	
			int j=0;
			//与w-1个p[][]的连乘
			while((s[(start+mm)%w]!=v_simple[j])&&(j<v_simple.size()))
				j++;
			if (j==v_simple.size())
				{marp*=0;
				cout<<"find one not occur in normal data !"<<endl;
				
				}
			else 
				marp*=p[i*m.size()+j];//from i to j
			//tempfile<<v_simple[i]<<"--->"<<v_simple[j]<<":"<<p[i*m.size()+j]<<" ";
			
			i=j;
		
		}
		
		marpfile<<"ont marp:"<<marp<<endl;
		//输出
		cout<<"marp:"<<marp<<endl;
		if (marp<thrashhold)
			return true;
		else 
			return false;
		
	}

}




main()
{
	Markov m;
	
	//巨大的训练 正常数据文件
	m.ReadFile("sendmail1.daemon.int");
	m.CreateM();
	

	cout<<"testfile name:"<<endl;
	string testfile;
	
	/*****测试**********/
	while(cin>>testfile)
	{	
		//对输入的测试数据文件 测试!!
		ifstream ceshi;
		ceshi.open(testfile.c_str());
		if(ceshi.fail()) 
		{
			cout<<"fail file!"<<endl;
			continue;
		}
		ceshi.close();

		m.Single_Markov(testfile);
		cout<<"testfile name:"<<endl;
		

	}		


	m.Release();
	
}