Responsive image

问题 C: 第3关:基于KMP算法的网络入侵检测

问题 C: 第3关:基于KMP算法的网络入侵检测

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 27
[提交][状态][讨论版][命题人:]

题目描述

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

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

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



#include<iostream>
#include<cstring>
#include<sstream>
using namespace std;
void GetNext(string pattern,int* next)
{//每个模式的下一个输出值 和 下一个输入数字组
    int j=0, k=-1;
    next[j]=k;
    while (j<(int)pattern.length()-1){
        if(k==-1||pattern[j]==pattern[k]){
            j++;
            k++;
            next[j]=k;
        }
        else{
            k=next[k];
        }
    }
}
int KMP(string target,string pattern,int* next)
{//KMP匹配算法,target为主串,pattern为子串。
//匹配成功返回主串中所含子串第一次出现的位置,否则返回-1。
//调用GetNext函数获取模式串的next数组
/**************begin************/




    /**************end************/
}
int main()
{
    int n,m;
    while (cin>>n>>m)
    {
        cin.get();     //将接收第一个返回,并阻止对netline()的输入
        string *rule=new string[n];   //规则编号组存储ip地址
        string 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++)
        {
            int *next=new int[rule[i].length()];
            if(KMP(log,rule[i],next)!=-1)
            {
                cout<<"Intrusion."<<endl;
                return 0;
            }
            delete[] next;  //删除组指针空间
        }
        cout<<"No Intrusion."<<endl;
        delete[] rule;
        return 0;
    }
}






输入描述



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

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

n + 2 ~ n + m + 1行共m行,为网络日志内容。
例如:
1 6
protocol:tcp ip:44.207.25.205 msg:"Network intrusion detected."
Proto Recv-Q Send-Q Local-Address Foreign-Address State
tcp 0 0 63.228.177.122:83999 115.120.78.164:25267 ESTABLISHED
tcp 0 0 91.62.129.226:75977 77.138.44.135:71910 ESTABLISHED
tcp 0 0 12.70.45.198:24940 44.207.25.205:7927 CLOSE_WAIT
tcp 0 0 155.212.113.157:94592 147.138.105.205:64521 LAST_ACK
tcp 0 0 148.0.118.155:33854 128.61.218.176:83248 LISTEN


输出描述

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

样例输入

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

样例输出

No Intrusion.

提示

组合提交代码,你仅需要提交


int KMP(string target,string pattern,int* next)


{//KMP匹配算法,target为主串,pattern为子串。


//匹配成功返回主串中所含子串第一次出现的位置,否则返回-1。


//调用GetNext函数获取模式串的next数组


/**************begin************/
















    /**************end************/


}




[提交][状态]
ACM算法攻关部
  • Anything about this OnlineJudge, Please Contact Administrator. Click add QQ

    OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap

    Copyright 2016 ACM算法攻关部
    关于网站改版