Abstract:
The present invention provides a traceback method including: receiving data including router information according to a path of an attacker; filtering the data to hash the data, and storing the resultant hashed information; determining whether the data is normally received on the basis of the hashed information; and predicting a path loss on the basis of the determination result. Therefore, it is possible to perform an accurate IP traceback using a probabilistic packing marking method and a hash-based traceback method.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
       [0001]    This application claims priority to and the benefit of Korean Patent Application No. 10-2007-0132622 filed in the Korean Intellectual Property Office on Dec. 17, 2007, the entire contents of which are incorporated herein by reference. 
       BACKGROUND OF THE INVENTION 
       [0002]    (a) Field of the Invention 
         [0003]    The present invention relates to a traceback method. Particularly, the present invention relates to a method based on a Markov chain model. 
         [0004]    The present invention was supported by the IT R&amp;D program of MIC/IITA [2006-S-009-02, Development of WiBro Service and Operation Standard]. 
         [0005]    (b) Description of the Related Art 
         [0006]    Tracebacks in an IP (Internet protocol) layer that deal with the transmission of packets over a network are classified into a proactive IP traceback and a reactive IP traceback. In addition, the tracebacks are classified into a router-based traceback, a technique for implementing a management system for packet information, a traceback based on a specific network, and a traceback based on a management technique. 
         [0007]    The proactive IP traceback includes two representative methods, that is, a probabilistic packet marking method and an Internet control message protocol (ICMP) traceback method. 
         [0008]    In the probabilistic packet marking method, two routers adjacent to a path of packets mark their information on the packets with a predetermined probability, and find an attack source on the basis of the information marked on the packets when a distributed denial of service (DDoS) attack occurs. 
         [0009]    The probabilistic packet marking method probabilistically marks information on the packets to reduce the overhead of the router and to minimize a marking size. Therefore, the probabilistic packet marking method can solve the problems of the traceback due to fragmentation. 
         [0010]    The ICMP traceback method copies the content of a specific ICMP traceback message and forwards the copied message to all the routers. The ICMP traceback method can efficiently access the routers, but has a disadvantage in that an attacker will transmit a fraudulent ICMP traceback message to a victim host. 
         [0011]    A hash-based traceback method is a representative example of the reactive IP traceback. In the hash-based traceback method, a source patch isolation engine (SPIE)-based traceback server is provided, the entire network is classified into sub-groups, and an agent is provided for each of the sub-groups, thereby managing the network. Each router has a data generation agent (DGA) function. The DGA function applies a hash function to packet information transmitted to each router to hash the packet information. That is, the hash-based traceback method stores and manages IP header information and payload information, and generates a database using a Bloom filter having a hash-based data structure. 
         [0012]    If a destination intrusion detection system detects hacking and an illegal act, the agent managing the network group compares information stored in a DGA router in the group with hacking packet information, analyzes the comparison result, and transmits the analyzed result to an SPIE system, thereby reconstructing a transmission path of the packet related to the hacking. 
         [0013]    The above information disclosed in this Background section is only for enhancement of understanding of the background of the invention and therefore it may contain information that does not form the prior art that is already known in this country to a person of ordinary skill in the art. 
       SUMMARY OF THE INVENTION 
       [0014]    The present invention has been made in an effort to provide a traceback method having an advanced traceback performance, which is a combination of a proactive traceback method and a reactive traceback method. 
         [0015]    According to an aspect of the present invention, a traceback method includes: receiving data including router information according to the path of an attacker; filtering the data to hash the data, and storing the hashed information; determining whether the data is normally received on the basis of the hashed information; and predicting a path loss on the basis of the determination result. 
         [0016]    The router information may be included in the data by probabilistic packet marking. 
         [0017]    The router information may be marked on the data by a transition probability corresponding to a router. 
         [0018]    The router information of a plurality of routers may include the results obtained by performing an exclusive OR operation on IDs of the plurality of routers. 
         [0019]    The filtering and storing of the information may include separating an Internet protocol header and query information from the data using a Bloom filter, and storing the Internet protocol header and the query information. 
         [0020]    The determination of whether the data is normally received on the basis of the hashed information may include examining the Internet protocol header to determine whether the data is normally received. 
         [0021]    The determination of whether the data is normally received on the basis of the hashed information may include, when it is determined that the data is abnormally received, predicting the path loss. 
         [0022]    The predicting of the path loss may include setting the plurality of routers as nodes, generating a transition probability matrix on the basis of the transition probabilities of the nodes, generating the incidence of each of the nodes on the basis of the transition probability matrix, and determining priorities of the nodes on the basis of the incidences. 
         [0023]    The determination of whether the data is normally received may include determining whether there is router information. 
         [0024]    According to another aspect of the present invention, a signal receiving apparatus includes: a receiver that receives data including router information according to the path of an attacker; a filter that groups the data and classifies acknowledgement information of the groups; a storage unit that stores the acknowledgement information; and a determining unit that determines whether the data is normally received on the basis of the acknowledgement information and predicts the path of the attacker. 
         [0025]    The acknowledgement information may include mobile router information of the attacker. 
         [0026]    The mobile router information may be included in the data according to Markov chain-based probabilistic packet marking. 
         [0027]    The router information may include a transition probability corresponding to a router. 
         [0028]    The router information of a plurality of routers may be generated by performing an exclusive OR operation on IDs of the plurality of routers. 
         [0029]    The acknowledgement information may include an Internet protocol header and query information. 
         [0030]    The determining unit may examine the Internet protocol header to determine whether the data is normally received. 
         [0031]    When it is determined that the data is abnormally received, the determining unit may predicts the path loss. 
         [0032]    The determining unit may calculate the incidence of each of the routers on the basis of a transition probability matrix for the plurality of routers and determine priorities of the routers on the basis of the incidences. 
         [0033]    The determining unit may determine whether the data is normally received on the basis of whether there is the router information. 
         [0034]    According to the above-mentioned aspects of the present invention, it is possible to perform an accurate IP traceback using a probabilistic packing marking method and a hash-based traceback method. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0035]      FIG. 1  is a diagram illustrating data hacking in a broadband wireless Internet system according to the present invention. 
           [0036]      FIGS. 2A to 2C  are diagrams illustrating a process of marking router IDs according to the movement of an attacker. 
           [0037]      FIG. 3  is a diagram illustrating the path of the attacker in a network graph. 
           [0038]      FIG. 4  is a diagram schematically illustrating the structure of a router of a victim host. 
           [0039]      FIG. 5  is a flowchart illustrating a traceback operation of the router of the victim host. 
           [0040]      FIGS. 6A and 6B  are diagrams illustrating a method of predicting an expected path shown in  FIG. 5 . 
       
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENTS 
       [0041]    In the following detailed description, only certain exemplary embodiments of the present invention have been shown and described, simply by way of illustration. As those skilled in the art would realize, the described embodiments may be modified in various different ways, all without departing from the spirit or scope of the present invention. Accordingly, the drawings and description are to be regarded as illustrative in nature and not restrictive. Like reference numerals designate like elements throughout the specification. 
         [0042]    In the specification, unless explicitly described to the contrary, the word “comprise” and variations such as “comprises” or “comprising” will be understood to imply the inclusion of stated elements but not the exclusion of any other elements. In addition, the terms “-er”, “-or”, and “module” described in the specification mean units for processing at least one function and operation and can be implemented by hardware components or software components and combinations thereof. 
         [0043]    In the specification, a terminal may be referred to as a mobile station (MS), a mobile terminal (MT), a subscriber station (SS), a portable subscriber station (PSS), user equipment (UE), or an access terminal (AT). The terminal may include some or all of the functions of the mobile terminal, the subscriber station, the portable subscriber station, and the user equipment. 
         [0044]    In the specification, a node may be referred to as a base station (BS), an access point (AP), a radio access station (RAS), a node B, a base transceiver station (BTS), or a mobile multihop relay (MMR)-BS. The node may include some or all of the functions of the access point, the radio access station, the node B, the base transceiver station, and the MMR-BS. 
         [0045]    Hereinafter, a traceback method using a Markov chain model will be described. 
         [0046]      FIG. 1  is a diagram illustrating data hacking in a broadband wireless Internet system according to the present invention, and  FIGS. 2A to 2C  are diagrams illustrating a process of marking a router ID according to the movement of an attacker. 
         [0047]    Referring to  FIG. 1 , an access network  100  includes a mobile station  10 , a radio access station (RAS)  20 , and a router  30 . 
         [0048]    The router (ACR 1 )  30  is for connecting separated networks using the same transmission protocol. The router  30  connects network layers, and has functions of packet switching, packet forwarding, packet filtering, and routing. 
         [0049]    The radio access station  20  transmits signals generated by the mobile station  10 , and registers positional information for checking the position of the mobile station  10  existing in the access network  100  controlled by the radio access station  20 . 
         [0050]    The router  30  of the radio access station  20  controlling the access network  100  including the mobile station  10  generates a binary router ID to perform marking. 
         [0051]    That is, the router  30  stores router information of received request packet data, marks the router ID on the router information of response packet data, and transmits the response packet data. 
         [0052]    Meanwhile, as shown in  FIG. 1 , when the mobile station  10  of the attacker moves from one access network to another network, a handover occurs. When the mobile station of the attacker reaches an access network  200 , which is a final destination, after a plurality of handovers occur, the mobile station of the attacker has an effect on a victim host  70  of the access network  200 . Here, the access network  200  includes a router (ACR n )  40  and a radio access station (RAS)  50 . 
         [0053]    As shown in  FIG. 2A , when the mobile station  10  of a hacker is handed over to a network including a router V of a victim host through the third and sixth routers ACR 3  and ACR 6 , router IDs of the path are continuously marked on an option field of an IP header of packet data by an exclusive OR operation, as shown in  FIG. 2B . 
         [0054]    The router ID is represented by an arbitrary binary value, as shown in  FIG. 2C . 
         [0055]    In this case, the routers ACR 3  and ACR 6  on the path perform probabilistic packet marking using the Markov chain on the router IDs. 
         [0056]    The state of each of the routers through which the mobile station passes for probabilistic packet marking may be represented by the following set: 
         [0057]    {??, ACR 3 , ACR 6 , (V), ACR 3  and ACR 6 , (ACR 6 , V), (ACR 3 , V), (ACR 3 , ACR 6 , V)}. 
         [0058]    In this case, each state has a transition probability, and a transition probability matrix may be formed on the basis of the transition probability and a total number of transitions. 
         [0059]    The transition probability between the router to which the attacker belongs first and the third router ACR 3  and the transition probability between the sixth router ACR 6  and the router V of the victim host are calculated. 
         [0060]    The calculation of the transition probabilities satisfy Equation 1 given below: 
         [0000]        P ( T ( G )= ACR   i )=(the number of sources reached  ACR   i )/the total number of sources*[ P   m (1− P   m ) d(ACRi, v)−1 .  [Equation 1] 
         [0061]    In addition, the calculation satisfies 
         [0000]    
       
         
           
             
               
                 P 
                  
                 
                   ( 
                   
                     
                       T 
                        
                       
                         ( 
                         G 
                         ) 
                       
                     
                     = 
                     φ 
                   
                   ) 
                 
               
               = 
               
                 1 
                 - 
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                     P 
                      
                     
                       ( 
                       
                         
                           T 
                            
                           
                             ( 
                             G 
                             ) 
                           
                         
                         = 
                         
                           ACR 
                           i 
                         
                       
                       ) 
                     
                   
                 
               
             
             , 
           
         
       
     
         [0062]    (where T(G) indicates a packet type in a network graph G, ACR i  indicates an i-th router in the network graph G, Pm indicates the probability marking values of all routers (1/d), d indicates the distance between the router and a victim host that is most distant from the router, and d(ACR i , v)−1 indicates the distance between the victim host V and ACRi). 
         [0063]      FIG. 3  is a diagram illustrating the path of an attacker in the network graph. 
         [0064]    When the mobile station  10  of the attacker performs a plurality of handovers and the router V of the last victim host is defined through the first router ACR 1 , the third router ACR 3 , and the sixth router ACR 6 , the router V of the victim host traces back the IP of the attacker. 
         [0065]      FIG. 4  is a diagram schematically illustrating the structure of the router of the victim host,  FIG. 5  is a flowchart illustrating a traceback operation of the router of the victim host, and  FIGS. 6A and 6B  are diagrams illustrating a method of predicting an expected path of  FIG. 5 . 
         [0066]    Referring to  FIG. 4 , a router  400  of a victim host includes a receiver  410 , a Bloom filter  420 , a database  430 , and a determining unit  440 . 
         [0067]    When a victim host is defined, the router  400  of the victim host receives data packets using the receiver  410 , filters the data packets using the Bloom filter  420 , and hashes the filtered data packets (S 301 ). Then, the router  400  stores the hashed data in the database  430  (S 303 ). 
         [0068]    The Bloom filter  420  allows a predetermined amount of false positives to make up for the defects of the hash function. Therefore, it is important to reduce the false positives. Therefore, it is determined only whether there is a router ID, but it is not determined whether to store the router ID in its original form, which makes it possible to store a large amount of data information using a small database  430 . 
         [0069]    Then, the determining unit  440  searches interested query information from the stored data to know the packet type and the storage format of the stored data. The determining unit  440  uses them to generate information for IP traceback (S 305 ). 
         [0070]    Then, the determining unit  440  examines the IP header of the stored data to determine whether the data is normally transmitted (S 307 ). 
         [0071]    When it is determined that the data is normally transmitted, the determining unit  440  immediately perform the IP traceback (S 311 ). When it is determined that a transmission loss occurs, the determining unit  440  finds a lost portion using a prediction module and then performs a traceback (S 309 ). 
         [0072]    In order to find the lost portion, the determining unit sets each router in the network graph G shown in  FIG. 3  as a node, and calculates the transition probability between the nodes with the number of nodes increased as shown in  FIG. 6B , and calculates a transition probability matrix Q. 
         [0073]    As shown in  FIG. 6A , the transition probability matrix Q is operated on the initial probability of each node to calculate the incidence of each node. 
         [0074]    When the second to sixth routers between the first router of the attacker and the router of the victim host are set as nodes and the incidence of each node is calculated, (0.2260, 0.0904, 0.2203, 0.1243, 0.2203, 0.1186) T  shown in  FIG. 5A  is obtained. 
         [0075]    When the incidences are arranged in ascending order, it is possible to know priorities in ascending order, and it is possible to perform a traceback by determining the priorities as the path of the attacker. 
         [0076]    When the IP traceback is actually implemented as shown in  FIGS. 6A and 6B , the priorities are set in the order of Attacker&gt;ACR 3 &gt;ACR 6 &gt;ACR 5 &gt;Victim Host&gt;ACR 2 , which correspond to the actual route. 
         [0077]    Therefore, if marking is not performed due to the packet loss of the router ACR 6 , the router ACR 5  may also be considered to have the highest probability of a packet loss. Therefore, it is possible to exclude other routes from the traceback. 
         [0078]    As such, it is possible to reconstruct a transmission path in consideration of both whether a transmission loss occurs and whether packets are normally transmitted. Therefore, this embodiment is more effective than the traceback method according to the related art. 
         [0079]    The above-described exemplary embodiment of the present invention can be applied to programs that allow computers to execute functions corresponding to the configurations of the exemplary embodiments of the invention or recording media including the programs as well as the method and apparatus. Those skilled in the art can easily implement the applications from the above-described exemplary embodiments of the present invention. 
         [0080]    While this invention has been described in connection with what is presently considered to be practical exemplary embodiments, it is to be understood that the invention is not limited to the disclosed embodiments, but, on the contrary, is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims.