Problem1827--【串与数组】4-4 基于BM算法的网络入侵检测

1827: 【串与数组】4-4 基于BM算法的网络入侵检测

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

随着互联网的飞速发展，网络安全问题日益严重。入侵检测技术是一种积极主动防御的安全保障技术，而Snort是其中基于规则匹配的一种入侵检测技术。Snort自1998年被发明以来，历经数年的迭代更新，Snort已成为一个具有多平台(Multi-Platform)、实时(Real-Time)流量分析、网络IP数据包(Pocket)记录等特性的强大的网络入侵检测/防御系统(Network Intrusion Detection/Prevention System)，即NIDS/NIPS。

Snort首先需要使用者根据入侵行为的特征，按照一定的规范将这些特征编写成规则，最后通过检测网络数据与规则数据库中的规则是否匹配来判断入侵与否。在Snort入侵检测系统中，规则的匹配效率是影响Snort检测效率的关键。而规则匹配的核心技术是模式匹配算法。

请实现一个基于BM算法的模式匹配算法，用于网络入侵行为的检测。若检在网络日志中检测到任何一条检测规则中的ip地址，则输出“Intrusion.”，反之输出“No Intrusion.”

Input

输入共n + m + 1行，第1行两个整数n, m(n, m ≤ 100) 2 ～ n + 1行每行为一条检测规则。规则的格式为:

protocol:网络协议 ip:ip地址 msg:"附加信息"

n + 2 ～ n + m + 1行共m行，为网络日志内容。

Output

输出一行，若检在网络日志中检测到任何一条检测规则中的ip地址，则输出“Intrusion.”，反之输出“No Intrusion.”。

Sample Input Copy 

3 3
protocol:tcp ip:225.93.118.39 msg:"Network intrusion detected."
protocol:tcp ip:152.213.218.150 msg:"Network intrusion detected."
protocol:tcp ip:181.164.101.231 msg:"Network intrusion detected."
Proto Recv-Q Send-Q Local-Address Foreign-Address State
tcp 0 0 36.51.200.67:95403 40.56.49.213:29716 LAST_ACK
tcp 0 0 215.142.133.153:49323 106.54.135.230:18487 CLOSED

Sample Output Copy 

No Intrusion.

HINT

#include<iostream>
#include<cstring>
#include<sstream>
#include<algorithm>
using namespace std;
int* getBc(const string & pattern)
{//得到坏字符bc数组
    int *bc=new int[256];
    int len=pattern.length();
    for (int i=0; i<256;++i)
        bc[i]=-1;
    for (int i=0; i<len;++i)
    {
        bc[pattern[i]]=i;
    }
    return bc;
}
int* suffixes(const string & pat)
{
    const int len=pat.length();
    int num;
    int *suff=new int[len];
    suff[len-1]=len;
    for (int i=len-2;i>=0;--i)
    {
        for (num=0;num<=i&&pat[i-num]==pat[len-num-1];++num);
 
        suff[i]=num;
    }
    return suff;
}
int* getGs(const string & pat)
{
    const int len=pat.length();
    const int lastIndex=len-1;
    int *suffix=suffixes(pat);
    int *gs=new int[len];

    for(int i=0;i<len;++i)
        gs[i]=len;
   
    for(int i=lastIndex;i>= 0;--i)
    {
       
        if(suffix[i]==i+1)
        {
            for(int j=0;j<lastIndex-i;++j)
            {
                if(gs[j]==len)
                    gs[j]=lastIndex-i;
            }
        }
    }
 
    for(int i=0;i<lastIndex;++i)
    {
        gs[lastIndex-suffix[i]]=lastIndex-i;
    }
    delete[] suffix;
    return gs;
}
int BM(const string & text, const string & pat)
{//在str.ch中匹配pattern.ch，匹配成功返回主串中所含子串第一次出现的位置，否则返回-1。
//分别求坏字符数组bc和好字符数组suffix、prefix，分别计算两个策略的移动位数，取大值作为最终移动位数
    /**************begin************/
   




    /**************end************/
}
int main()
{
    int n,m;
    while (cin>>n>>m)
    {
        cin.get();     //将接收第一个返回，并阻止对netline（）的输入
        string *rule=new string[n];   //规则编号组存储ip地址
        string log="";       //log保存并接收
        for(int i=0;i<n;i++)
        {
            string t;
            getline(cin,t);
            stringstream sss(t);   //根据规范将字段左侧分成一个字符
            string pot,ip,msg;
            sss>>pot>>ip;
            rule[i]=ip.substr(3, ip.length() - 3);
        }
        for(int i=0;i<m;i++)
        {
            string t;
            getline(cin,t);
            log += t;
        }
        for(int i=0;i<n;i++)
        {
            if(BM(log,rule[i])!=-1)
            {
                cout<<"Intrusion."<<endl;
                return 0;
            }
        }
        cout<<"No Intrusion."<<endl;
        delete[] rule;  //删除组指针空间
        return 0;
    }
}

Source/Category

数据结构课程 
[Submit] [Status]