Abstract:
A method and apparatus for pattern matching using packet reassembly are provided. The pattern matching method using packet reassembly includes: extracting serial information in relation to a current input packet; determining whether or not pattern matching result information in relation to one or more previous packets and/or subsequent packets on the basis of the serial number of the current input packet is already stored; loading the pattern matching result information in relation to the previous packets and/or subsequent packets; and reassembling the loaded pattern matching result information in relation to the previous packets and/or subsequent packets and the current input packet and performing pattern matching with attack patterns which are already stored. Accordingly, by using packet reassembly, a method and apparatus for pattern matching capable of reducing memory usage without lowering the speed can be provided

Description:
CROSS-REFERENCE TO RELATED PATENT APPLICATIONS  
       [0001]     This application claims the benefit of Korean Patent Application Nos. 10-2004-0102392, filed on Dec. 7, 2004 and 10-2005-0054370, filed on 23 Jun. 2005, in the Korean Intellectual Property Office, the disclosures of which are incorporated herein in their entirety by reference.  
       BACKGROUND OF THE INVENTION  
       [0002]     1. Field of the Invention  
         [0003]     The present invention relates to a pattern matching method using packet reassembly and an apparatus therefor, and more particularly, to a pattern matching method providing a packet reassembly function with minimum hardware resources as a base technology for real-time network intrusion detection in a giga scale network, and an apparatus therefor.  
         [0004]     2. Description of the Related Art  
         [0005]     Since the 1980s, a variety of intrusion detection systems have been developed to protect information systems. Intrusion into an information system can be defined as trying to access an information system with an illegal intention, to manipulate information or disable the system.  
         [0006]     Due to the rapid expansion of the Internet since the 1990s, the objects of intrusion have been expanding from a single information system to the entire network.  
         [0007]     In the 2000s, intrusions targeting information systems have become more intelligent and much faster. Unlike the past intrusion type targeting only a single information system, attacks stopping the network service itself by disabling the entire network are becoming more common.  
         [0008]     Since intrusion methods are becoming more intelligent and network bandwidth is continuously increasing, a lot of current research focuses on making much faster and more accurate intrusion detection systems for protecting networks.  
         [0009]     In particular, a real-time countermeasure technology against intrusion has been established as an essential function of a network intrusion detection system. The real-time countermeasure technology detects and responds in real time to an attack on a network.  
         [0010]     As a result of the research, a variety of intrusion detection systems, such as RealSecure of ISS, IntruShield of McAfee, etc., have been installed to function in a network.  
         [0011]     At present, the most effective intrusion detection method is a rule-based intrusion detection method. In this method, by analyzing known attacks and generating attack patterns based on the analysis, all packets passing through a network are compared with the attack patterns to determine whether or not there is an intrusion. This method is effective against known intrusions.  
         [0012]     One core technology required for this rule-based intrusion detection method is pattern matching technology. The pattern matching technology examines whether or not a packet passing through a network includes a pattern specified in an intrusion detection rule. This is one of the most important intrusion detection technologies.  
         [0013]     It is difficult to apply this pattern matching technology to a high-speed network by a software method because of the complexity of searching and speed reduction with increasing rules. Also, in the case of a hardware method, high speed implementation is difficult due to the limited hardware resources.  
         [0014]     In order to solve these difficulties, much research is underway for the pattern matching technology, and in particular, a variety of studies on hardware-based pattern matching are being conducted. Implementation of the pattern matching technology in a giga scale network can be regarded as a core issue in the development of an intrusion detection system.  
         [0015]     However, in the situation where the intrusion method of networks becomes more intelligent and more attacks avoid an intrusion detection system using IP fragmentation and/or TCP segmentation, the conventional rule-based intrusion detection method cannot cope with attacks without a pattern matching technology which can reassemble IP fragmented and TCP segmented packets.  
         [0016]     In addition, if the rule-based intrusion detection method does not reassemble all packets passing through a network, the method cannot cope with an attack which avoids an intrusion detection system using this IP fragmentation or TCP segmentation. Accordingly, in order to detect this type of attack, providing a packet reassembly function to a high-speed hardware-based pattern matching technology has been emerging as an important research subject.  
         [0017]      FIG. 1  illustrates a conventional TCP reassembly method for a TCP/IP packet and  FIG. 2  illustrates a conventional IP de-fragmentation method for an IP packet. Referring to  FIGS. 1 and 2 , dividing a packet in the IP layer is referred to as IP fragmentation, and dividing a packet in the TCP layer is referred to as TCP segmentation. Reassembling the divided packets is referred to respectively as IP de-fragmentation and TCP reassembly. Also, IP de-fragmentation and TCP reassembly are collectively referred to as packet reassembly.  
         [0018]     The core part of IP de-fragmentation and TCP reassembly is reassembling the payloads of continuous packets based on the fragment offset of an IP header or the sequence number of a TCP header. Generally, IP de-fragmentation and TCP reassembly are performed in the host of a destination. If the reassembly function is not supported, attacks avoiding intrusion detection using reassembly cannot be blocked. However, an intrusion detection system does not need to perform the same reassembly process as that performed by the destination host. Since pattern matching is performed in relation to each packet, reassembly is only necessary when an attack pattern is separated between packets.  
         [0019]      FIG. 3  illustrates a conventional packet reassembly method. Referring to  FIG. 3 , the method is to find a case where an attack pattern is dispersed in continuous packets. Here, the continuous packets are not continuous in time, but are continuous in the sequence number of the TCP header or in the fragment offset of the IP header on the basis of packet reassembly. Continuous packets as shown in  FIG. 3  must be examined on the basis of a maximum intrusion pattern length (maximum rule pattern length, RLmax). That is, in the case of two continuous packets, it is necessary to reassemble and examine data with a length of about twice the maximum intrusion pattern length.  
         [0020]     However, in the case of packet reassembly for pattern matching there is a problem no less important than the length of data to be reassembled. In order to reassemble continuous packets and perform pattern matching, previous packet data should be stored in a storage unit before a next packet comes in.  
         [0021]     In addition, there is no guarantee of sequential arrival of a TCP header in order of sequence number, or of an IP header in order of fragment offset. Accordingly, at high network bandwidths, the amount of packet data that must be stored in a memory for reassembly increases. In particular, when hardware is used in order to detect intrusion in a high speed network, this increase in memory can be a serious constraint.  
         [0022]     The increase in the amount of packet data for reassembly is not limited to simple increases of the memory to be used. That is, the increase of the amount of packet data may make functions related to data processing more complicated, and this means an increase in the processing time. In particular, in the case of a high speed network being a target, the increase in the processing time can greatly degrade the performance of an intrusion detection system.  
       SUMMARY OF THE INVENTION  
       [0023]     The present invention provides a pattern matching method and apparatus using packet reassembly to overcome the limit of hardware resources by using the pattern matching result in relation to each packet in reassembly in order to utilize resources efficiently.  
         [0024]     According to an aspect of the present invention, there is provided a pattern matching apparatus using packet reassembly, including: a storage unit which stores pattern matching result information which is generated when an input packet matches a part of an attack pattern; a pattern matching unit which, if one or more packets previous to a current input packet and/or packets subsequent to the current packet on the basis of the serial number of the current input packet are received, reassembles pattern matching result information in relation to previous and/or subsequent packets and the current in put packet and performs pattern matching with attack patterns already stored; and a packet reassembly function unit which determines whether or not the pattern matching result information in relation to the packets previous to an/or subsequent to the current in put packet is already stored in the storage unit, and transmits the pattern matching result information to the pattern matching unit.  
         [0025]     According to another aspect of the present invention, there is provided a pattern matching method using packet reassembly, including: extracting serial information in relation to a current input packet; determining whether or not pattern matching result information in relation to at least one or more previous packets and/or subsequent packets on the basis of the serial number of the current input packet is already stored; if it is determined that any one of pattern matching result information items in relation to at least one or more previous packets and/or subsequent packets of the current input packet is already stored, loading the pattern matching result information in relation to the previous packets and/or subsequent packets; and reassembling the loaded pattern matching result information in relation to the previous packets and/or subsequent packets and the current input packet and performing pattern matching with already stored attack patterns. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0026]     The above and other features and advantages of the present invention will become more apparent by describing in detail exemplary embodiments thereof with reference to the attached drawings in which:  
         [0027]      FIG. 1  illustrates a conventional TCP reassembly method for a TCP/IP packet;  
         [0028]      FIG. 2  illustrates a conventional IP de-fragmentation method for an IP packet;  
         [0029]      FIG. 3  illustrates a conventional packet reassembly method;  
         [0030]      FIG. 4  is a block diagram of a pattern matching apparatus using packet reassembly according to an embodiment of the present invention;  
         [0031]      FIG. 5  is a schematic diagram showing packet reassembly performed in a pattern matching unit of  FIG. 4 ; and  
         [0032]      FIG. 6  is a flowchart of the operations performed by a pattern matching method using packet reassembly according to an embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0033]     The present invention will now be described more fully with reference to the accompanying drawings, in which exemplary embodiments of the invention are shown.  
         [0034]      FIG. 4  is a block diagram of a pattern matching apparatus using packet reassembly according to an embodiment of the present invention. Referring to  FIG. 4 , the pattern matching apparatus using packet reassembly includes a packet input unit  400 , a pattern matching unit  410 , a packet reassembly function unit  420 , a storage unit  430 , and a packet output unit  440 .  
         [0035]     The packet input unit  400  receives a packet from a source system transmitting the packet through a network, and transmits the packet to the pattern matching unit  410 .  
         [0036]     The pattern matching unit  410  performs a pattern matching operation with the packet input from the packet input unit  400 . Here, pattern matching means to examine the packet input from the packet input unit  400  by comparison with a plurality of attack patterns already set as intrusion rules in the pattern matching unit  410 , and determine whether there is a match. More specifically, for example, if the pattern matching unit  410  receives a current input packet from the packet input unit  400 , the pattern matching unit  410  transmits the serial number of the current input packet to the packet reassembly function unit  420 .  
         [0037]     In the packet reassembly function unit  420 , with the serial number of the current input packet transmitted by the pattern matching unit  410 , it is determined whether or not pattern matching result information of the previous packet and subsequent packet is already stored in the storage unit  430 . Here, if it is determined that the pattern matching result information of the previous packet and subsequent packet in relation to the current input packet is already stored in the storage unit  430 , the packet reassembly function unit  420  loads the corresponding pattern matching result information from the storage unit  430  and transmits to the pattern matching unit  410 .  
         [0038]     Here, the previous packet and subsequent packet of the current input packet are not adjacent in time, but are adjacent in order of sequence number of the TCP header or of fragment offset of the IP header on the basis of packet reassembly. Also, the previous packet or subsequent packet of the current input packet is not limited to a physically single packet, but can include a plurality of previous packets or subsequent packets.  
         [0039]     Meanwhile, if it is determined that there is no corresponding pattern matching result information, the packet reassembly function unit  420  transmits to the pattern matching unit a message indicating that there is no pattern matching result information.  
         [0040]     The storage unit  430  stores the pattern matching result information, according to the control of the packet reassembly function unit  420 , and also transmits the corresponding pattern matching result information to the packet reassembly function unit  420 .  
         [0041]     Unlike the conventional packet reassembly, the storage unit  430  does not need to store packet data in a memory, but stores only the pattern matching result information in relation to the packet and uses this for pattern matching of the next input packet. This allows the same result as reassembling packet data and performing pattern matching for all the data.  
         [0042]     Accordingly, in  FIG. 4 , if the patterns match, only pattern matching result information is stored in the storage unit  430 , and if an adjacent packet is received, and the information is called and used for pattern matching, then the reassembly function for pattern matching can be implemented with less memory and a simple hardware structure.  
         [0043]     In the pattern matching unit  410 , if any of the pattern matching result information on the previous packet and the subsequent packet is received from the packet reassembly function unit  420 , the received pattern matching result information and the current input packet are reassembled, and pattern matching is performed with predetermined attack patterns already stored.  
         [0044]     Meanwhile, in the pattern matching unit  410 , if none of the pattern matching result information on the previous packet and the subsequent packet is received from the packet reassembly function unit  420 , pattern matching is performed only with the current input packet with predetermined attack patterns already stored.  
         [0045]     Here, if patterns do not match as the result of performing pattern matching in the pattern matching unit  410 , the packet input from the packet input unit  400  is output to the packet output unit  440 . Then, in the packet output unit  440  the packet input from the pattern matching unit  410  is transmitted to the destination system through a network. Also, if the packet matches a part of a predetermined attack pattern as the result of performing pattern matching, the pattern matching unit  410  transmits the pattern matching result information on the current input packet to the packet reassembly function unit  420 . The packet reassembly function unit  420  stores the pattern matching result information on the current input packet in the storage unit  430 .  
         [0046]     Meanwhile, if the packet matches an entire predetermined attack pattern as the result of performing pattern matching, the pattern matching unit  410  performs a preset countermeasure against the current input packet, such as blocking transmission of the current input packet to the packet output unit  440 .  
         [0047]     As a first example, assuming that the serial number of a current input packet is N, a case where the current input packet N is input from the packet input unit  400  and pattern matching result information on packet (N+1) (a packet subsequent to the current input packet) is not stored, and pattern matching result information on packet (N−1) (a packet previous to the current input packet) is already stored, will now be explained. Here, the packet (N−1) previous to the current input packet or the packet (N+1) subsequent to the current input packet is not limited to a physically single packet, but may include a plurality of packets.  
         [0048]     The pattern matching unit  410  receives the transmitted packet N through the packet input unit  400 .  
         [0049]     Next, the pattern matching unit  410  transmits the serial number of the current input packet N to the packet reassembly function unit  420  in order to notify that the current input packet N is received.  
         [0050]     Next, the packet reassembly function unit  420  determines whether or not pattern matching result information in relation to the packet (N−1) previous to the current input packet and the packet (N+1) subsequent to the current input packet is already stored in the storage unit  430 , loads the pattern matching result information on the packet (N−1) already stored in the storage unit  430 , and transmits the information to the pattern matching unit  410 .  
         [0051]     If the pattern matching result information on the packet (N−1) is received, the pattern matching unit  410  reassembles the pattern matching result information on the packet (N−1) and the current input packet N, and performs pattern matching with predetermined attack patterns already stored. In this case, the result will be the same as that obtained by reassembling the packet (N−1) and the packet N data and performing pattern matching for all the data.  
         [0052]     If patterns do not match as the result of the pattern matching, the pattern matching unit  410  transmits the packet N input from the packet input unit  400  to a destination system to which the packet will be transmitted, through the packet output unit  440 .  
         [0053]     Also, if the packet matches a part of a predetermined attack pattern as the result of performing pattern matching, the pattern matching unit  410  transmits the pattern matching result information on the packet N to the packet reassembly function unit  420 . The packet reassembly function unit  420  stores the pattern matching result information of the packet N in the storage unit  430 .  
         [0054]     Meanwhile, if the packet matches an entire predetermined attack pattern as the result of performing pattern matching, the pattern matching unit  410  performs a preset countermeasure against the current input packet, such as blocking transmission of the current input packet to the packet output unit  440 .  
         [0055]     As a second example, assuming that a current input packet is N, a case where pattern matching result information on packet (N−1) is not stored in the storage unit  430  and only pattern matching result information on packet (N+1) is already stored will now be explained. Here, the packet (N−1) previous to the current input packet or the packet (N+1) subsequent to the current input packet is not limited to a physically single packet, but may include a plurality of packets.  
         [0056]     The pattern matching unit  410  receives the transmitted packet N through the packet input unit  400 .  
         [0057]     Next, the pattern matching unit  410  transmits the serial number of the current input packet N to the packet reassembly function unit  420  in order to notify that the current input packet N is received.  
         [0058]     Next, the packet reassembly function unit  420  determines whether or not pattern matching result information in relation to the packet (N−1) previous to the current input packet and the packet (N+1) subsequent to the current input packet is already stored in the storage unit  430 , loads the pattern matching result information on the packet (N+1) already stored in the storage unit  430 , and transmits the information to the pattern matching unit  410 .  
         [0059]     If the pattern matching result information on the packet (N+1) is received, the pattern matching unit  410  reassembles the pattern matching result information on the packet (N+1) and the current input packet N, and performs pattern matching with predetermined attack patterns already stored. In this case, the result will be the same as that obtained by reassembling the packet N and the packet (N+1) data and performing pattern matching for all the data.  
         [0060]     If patterns do not match as the result of the pattern matching, the pattern matching unit  410  transmits the packet N input from the packet input unit  400 , to a destination system to which the packet will be transmitted, through the packet output unit  440 .  
         [0061]     Also, if the packet matches a part of a predetermined attack pattern as the result of performing pattern matching, the pattern matching unit  410  transmits the pattern matching result information on the packet N to the packet reassembly function unit  420 . The packet reassembly function unit  420  stores the pattern matching result information of the packet N in the storage unit  430 .  
         [0062]     Meanwhile, if the packet matches an entire predetermined attack pattern as the result of performing pattern matching, the pattern matching unit  410  performs a preset countermeasure against the current input packet, such as blocking transmission of the current input packet to the packet output unit  440 .  
         [0063]     As a third example, assuming that a current input packet is N, a case where both pattern matching result information on packet (N−1) and pattern matching result information on packet (N+1) are already stored in the storage unit  430  can be understood by referring to the first and second examples. Here, the packet (N−1) previous to the current input packet or the packet (N+1) subsequent to the current input packet is not limited to a physically single packet, but may include a plurality of packets.  
         [0064]     As a fourth example, assuming that a current input packet is N, a case where both pattern matching result information on packet (N−1) and pattern matching result information on packet (N+1) are not already stored in the storage unit  430  will now be explained. Here, the packet (N−1) previous to the current input packet or the packet (N+1) subsequent to the current input packet is not limited to a physically single packet, but may include a plurality of packets.  
         [0065]     The pattern matching unit  410  receives the transmitted packet N through the packet input unit  400 .  
         [0066]     Next, the pattern matching unit  410  transmits the serial number of the current input packet N to the packet reassembly function unit  420  in order to notify that the current input packet N is received.  
         [0067]     Next, the packet reassembly function unit  420  determines whether or not pattern matching result information in relation to the packet (N−1) previous to the current input packet and the packet (N+1) subsequent to the current input packet is already stored in the storage unit  430 , and transmits a message to the pattern matching unit  410  in order to notify that both pattern matching result information on packet (N−1) and pattern matching result information on packet (N+1) are not already stored in the storage unit  430 .  
         [0068]     Since pattern matching result information on packet (N−1) and pattern matching result information on packet (N+1) are not in the storage unit  430 , the pattern matching unit  410  performs pattern matching of the current input packet N with predetermined attack patterns already stored.  
         [0069]     If patterns do not match as the result of the pattern matching of the current input packet N, the pattern matching unit  410  transmits the packet N input from the packet input unit  400 , to a destination system to which the packet will be transmitted, through the packet output unit  440 .  
         [0070]     Also, if the packet matches a part of a predetermined attack pattern as the result of performing pattern matching of the current input packet N, the pattern matching unit  410  transmits the pattern matching result information on the packet N to the packet reassembly function unit  420 . The packet reassembly function unit  420  stores the pattern matching result information of the packet N in the storage unit  430 .  
         [0071]     Meanwhile, if the packet matches an entire predetermined attack pattern as the result of performing pattern matching, the pattern matching unit  410  performs a preset countermeasure against the current input packet, such as blocking transmission of the current input packet to the packet output unit  440 .  
         [0072]      FIG. 5  is a schematic diagram showing packet reassembly performed in the pattern matching unit  410  of  FIG. 4 . Referring to  FIG. 5 , packet reassembly performed in the pattern matching unit  410  in the case of the third example described above is shown. That is, in this case, assuming that a current input packet is N, both pattern matching result information on packet (N−1) and pattern matching result information on packet (N+1) are already stored in the storage unit  430 . Though the case where the pattern matching result information of both the packet (N−1) and the packet (N+1) is stored is shown in  FIG. 5 , in another example of the present invention there can be a case where there is only one of the pattern matching result information of the packet (N−1) and the packet (N+1). Also, in still another example of the present invention, there may be a case where there is neither of the pattern matching result information of the packet (N−1) and the packet (N+1). In this case, the pattern matching unit  410  does not perform packet reassembly, only pattern matching of the current input packet N.  
         [0073]     Here, the packet (N−1) previous to the current input packet or the packet (N+1) subsequent to the current input packet is not limited to a physically single packet, but may include a plurality of packets.  
         [0074]      FIG. 6  is a flowchart of the operations performed by a pattern matching method using packet reassembly according to an embodiment of the present invention. Referring to  FIG. 6 , first, the pattern matching unit  410  receives a transmitted current input packet from the packet input unit  400  in operation S 600 .  
         [0075]     Next, the pattern matching unit  410  notifies the packet reassembly function unit  420  of the serial number of the current input packet in operation S 610 .  
         [0076]     Next, the packet reassembly function unit  420  determines whether or not pattern matching result information of a packet previous to the current input packet and/or a packet subsequent to the current packet is already stored in the storage unit  430  in operation S 620 . Here, the previous packet and subsequent packet of the current input packet are not adjacent in time, but are adjacent in order of sequence number of the TCP header or of fragment offset of the IP header on the basis of packet reassembly. Also, the previous packet or subsequent packet of the current input packet is not limited to a physically single packet, but can include a plurality of previous packets or subsequent packets.  
         [0077]     If the determination result of operation S 620  indicates that pattern matching result information of the packet previous to the current input packet and/or the packet subsequent to the current packet are already stored in the storage unit, the packet reassembly function unit  420  transmits the pattern matching result information to the pattern matching unit  410  in operation S 630 .  
         [0078]     After operation S 630 , the pattern matching unit  410  reassembles the pattern matching result information input in operation S 630  and the current input packet input from the packet input unit  400  in operation S 600 , and performs pattern matching with preset predetermined attack patterns in operation S 640 . Meanwhile, if the result of determination in operation S 620  indicates that pattern matching result information of the packet previous to the current input packet and/or the packet subsequent to the current packet are not stored in the storage unit, the pattern reassembly function unit  420  transmits to the pattern matching unit  410  a message indicating that there is no corresponding pattern matching result information in operation S 635 .  
         [0079]     After operation S 635 , the pattern matching unit  410  performs pattern matching of the current input packet input from the packet input unit  400  in operation S 600  with preset attack patterns in operation S 645 . After operations S 640  and S 645 , it is determined whether or not the packet matches attack patterns as the result of performing pattern matching in operation S 650 .  
         [0080]     If the result of determination in operation S 650  indicates that the packet matches an attack pattern, it is further determined whether or not the packet matches only a part of the attack pattern or the entire attack pattern in operation S 655 .  
         [0081]     If the result of determination in operation S 655  indicates that the packet matches only a part of the attack pattern, the pattern matching unit  410  stores the pattern matching result information of the current input packet in operation S 660 .  
         [0082]     Meanwhile, if the result of determination in operation S 655  indicates that the packet matches the entire attack pattern, the preset countermeasure is performed in operation S 665 , such as blocking transmission of the current input packet. If the result of determination in operations S 660  and S 650  indicates that the packet does not match any attack patterns, operation S 670  is performed such that the current input packet is output to the destination system through the packet output unit  440 .  
         [0083]     The present invention can also be embodied as computer readable code on a computer readable recording medium. The computer readable recording medium is any data storage device that can store data which can be thereafter read by a computer system. Examples of the computer readable recording medium include read-only memory (ROM), random-access memory (RAM), CD-ROMs, magnetic tapes, floppy disks, optical data storage devices, and carrier waves (such as data transmission through the Internet). The computer readable recording medium can also be distributed over network coupled computer systems so that the computer readable code is stored and executed in a distributed fashion.  
         [0084]     While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it will be understood by those of ordinary skill in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the present invention as defined by the following claims. The exemplary embodiments should be considered in a descriptive sense only and not for purposes of limitation. Therefore, the scope of the invention is defined not by the detailed description of the invention but by the appended claims, and all differences within the scope will be construed as being included in the present invention.  
         [0085]     The present invention relates to a packet reassembly method and apparatus, and by providing a packet reassembly function to a high speed pattern matching system for real-time intrusion detection in a giga scale network, allows the detection of intrusion using IP fragmentation and TCP segmentation.  
         [0086]     Also, the present invention enables the packet reassembly function with minimum resources in a high speed pattern matching system implemented in hardware with limited resources, such that a wider range of attacks can be prevented. In particular, since only minimum memory resources are used, the packet reassembly function can be performed in a high speed intrusion detection system.