KR100930902B1 - Attack traceback method in mobile adhook network - Google Patents

Abstract

In consideration of the resource constraints of the MANET, the method of backtracking an attack source node according to an aspect of the present invention in which a head node included in each cluster digests all packets and stores them in a bloom filter is performed by a plurality of nodes. A method of backtracking an attack source node in a clustered Mobile Ad-hoc Network using a Weighted Clustering Algorithm, comprising: (a) NIDS in which the head node of each cluster is mounted on the head node. Activating a Network-Based Intrusion Detection module to monitor all packets; (b) the head node of each cluster storing a digest for the monitored packets in a Bloom Filter; (c) if the head node of each cluster receives a backtrace message generated by a member node included in the cluster, whether the head node of an adjacent cluster includes a digest associated with the attack packet included in the backtrace message. Requesting confirmation; (d) backtracking the attack source node using response acknowledgment messages received from head nodes of adjacent clusters; And (e) filtering all traffic originating from the attack source node.

 Go, Adhook, MANET, Bloom Filter, Traceback

Description

Method for Traceback for Attacked Node in Mobile Ad-hoc Network}

The present invention relates to mobile adhook network security, and more particularly, to a method for backtracking an initial attack node on a mobile adhook network.

In general, a mobile ad-hoc network (hereinafter referred to as 'MANET') is defined as a network in which mobile nodes autonomously communicate through a number of hops in the absence of an existing communication infrastructure. .

This MANET has distinct characteristics from existing networks, such as dynamic topology changes, limited bandwidth of the network, limited energy of the host, and limited physical security. These characteristics make MANET inherently vulnerable to many malicious attacks.

In particular, when a Denial of Service (DoS) attack is applied to MANET, which reduces or denies service to legitimate users by consuming resources of a remote host or network, The problem of energy consumption is even worse.

Since the fundamental solution to such an attack is to track the source of the attack and stop the attack at the location, various traceback methods have been proposed to track the source of the attack. Representative examples of such traceback methods include Probabilistic Packet Marketing (PPM), ITrace (ICMP Traceback), and Logging.

However, the above-described conventional attack source traceback method is most suitable for fixed wired networks, and applying such a method directly to a MANET has the following problems.

First, in a wired network environment, all packets constituting a single attack flow use the same routing path, but in MANET, all nodes constituting the network can move freely and the topology of the network changes from time to time. It can also be changed from time to time, there is a problem that it is limited to find the source of the attack in the MANET environment using the conventional traceback method.

Second, the conventional traceback method is proposed under the assumption that most routers in the network are secure, but the nodes acting as routers in MANET cannot be traced back to the origin of attack because they are easily attacked by their characteristics. There is a problem.

The present invention is to solve the above-described problem, in consideration of the resource constraints of the MANET, the head node included in each cluster digests all the packets to store in the bloom filter reverse attack source node inverse It is a technical task to provide a tracking method.

Another object of the present invention is to provide a method for backtracking an attack source node in a mobile adhook network that can keep information stored in a bloom filter up to date in consideration of characteristics of a MANET having a dynamic topology.

A method for backtracking an attack source node according to an aspect of the present invention for achieving the above object is a mobile ad-hoc network in which a plurality of nodes are clustered using a WCA (Weighted Clustering Algorithm) A method of backtracking an attack source node in a network, the method comprising: (a) activating a network-based intrusion detection (NIDS) module mounted on a head node by a head node of each cluster to monitor all packets; (b) the head node of each cluster storing a digest for the monitored packets in a Bloom Filter; (c) if the head node of each cluster receives a backtrace message generated by a member node included in the cluster, whether the head node of an adjacent cluster includes a digest associated with the attack packet included in the backtrace message. Requesting confirmation; (d) backtracking the attack source node using response acknowledgment messages received from head nodes of adjacent clusters; And (e) filtering all traffic originating from the attack source node.

In this case, step (b) comprises: (b1) generating digests of n bit size by inputting some bit size data of the monitored packet for k hash functions; (b2) expanding the size of each entry of the bloom filter of 2 ⁿ entries to n bits; (b3) setting all bits of the entry associated with the digest of the bloom filter to a first value; And (b4) when the value of the bit except the most significant bit becomes a second value by decreasing a value corresponding to a bit except the most significant bit among the bits of each entry as time passes, deleting the corresponding entry from the bloom filter. Characterized in that it comprises a step.

In one embodiment, the step (b), if the entry corresponding to the previous input and the entry corresponding to the current input of the bloom filter entries overlap, all bits except the most significant bit of the bits of the entry And resetting to a first value.

Meanwhile, in the step (b1), some bit size data of the monitored packet is generated by combining an IP header having a size of 20 bytes of the packet and the first 8 bytes of the IP data. It is characterized by setting a value that can be changed when each packet is transmitted through each node of the IP header as a second value.

As described above, according to the present invention, since the head node included in each cluster digests all packets and stores them in a bloom filter in consideration of resource constraints of the MANET, information exchanged in the entire network can be efficiently managed. It can be effective.

 In addition, according to the present invention, by adding a time tag to each entry of the bloom filter, old data can be deleted in the bloom filter, thereby keeping the information stored in the bloom filter up to date.

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.

1 is a flowchart illustrating a packet storage method for backtracking an attack source node in a mobile adhook network according to an embodiment of the present invention.

First, as illustrated, nodes included in a mobile ad-hoc network (hereinafter referred to as 'MANET') are clustered using a WCA (Weighted Clustering Algorithm) (step 100). At this time, each node is clustered and head nodes and member nodes are determined among the nodes included in each cluster. Here, the head node means serving to store the monitored packets by monitoring packets to be described later, and the member node means all other nodes except the head node in each cluster.

In one embodiment, each head node is equipped with a Network-Based Intrusion Detection System (NIDS) module. The NIDS module refers to a system module that monitors packets transmitted through the network and monitors intrusion of outsiders or leakage of data by insiders.These NIDS modules analyze and store certain intrusion patterns in a database. Based on the intrusion pattern, it monitors the intrusion of outsiders or the leakage of data by insiders through monitoring.

Thereafter, the head node of each cluster monitors all packets by activating the NIDS module (step 110). Next, the head node of each cluster stores the digest of the monitored packets (step 120). At this time, since each head node stores a large amount of storage space when storing the monitored packet, in one embodiment, the head node generates a digest of the corresponding packets, and then stores the generated digest in a bloom filter. do.

The bloom filter is a data structure that can effectively deal with storage space problems. It is used to check whether a specific set is included. As shown in FIG. 2, the size of the data filter is stored using k independent hash functions. It is a kind of hash table that creates each digest of n bits and uses it as an index of a 2 ⁿ size bit table. The values of these bit tables are all initialized to zero, and the bit fields associated with the digest are set to one.

Then, in order to check what information exists on the table, the information is again generated using k hash functions, and the internal table bits are examined by indexing the generated k digests. As a result, if the k table bits related to the generated digest are all 1, the information exists on the table. If any of the bits is 0, the information does not exist on the table.

Hereinafter, a method in which the head node of each cluster stores a digest of monitored packets in a bloom filter will be described in detail with reference to FIG. 3.

First, data of a part of the monitored packet is extracted (operation 300). Here, the extraction of the data of the partial region of the monitored packet is to limit the size of data that is input to the hash function in relation to the performance problem of the system.

In one embodiment, a 28-byte data obtained by extracting and combining the 20-byte IP header and the first 8 bytes of the IP payload from the packet having the structure as shown in FIG. 4 is input to the hash function. Can be used. At this time, all values that can be changed when each node forwards a packet, such as TOS (Type of Service), TTL, Checksum, and Option, are filled with 0 in the IP header area.

On the other hand, in generating the input data of the hash function, unlike in the wired environment, the wireless environment frequently causes retransmission due to collision at a lower layer, and therefore, the bloom filter may include a digest input for the same IP packet as the previous input. This is reported as a false collision on the input to the bloom filter. Therefore, when the Identification field value in the IP header area of the specific IP packet is the same as the Identification field value of the previous IP packet, it is preferable to exclude the corresponding IP packet from the input data generation target.

Referring to FIG. 3 again, the extracted data is input into k hash functions to generate an n-bit digest (step 310), and each entry of the bloom filter is expanded to n bits (step 320).

The reason for extending each entry to n bits is to define a time tag for each entry in order to automatically delete old data stored in a bloom filter when a predetermined time elapses. Specifically, the reason that the data stored in the bloom filter should be deleted is that when the size of the bloom filter is fixed and continuous input data is generated, all bits of the bloom filter are set to 1, and the subsequent bloom filter This is because every request makes the result always false positive.

In order to solve this problem, in the conventional wired network, after a predetermined time, the entire table of the bloom filter is stored separately at a designated place, and a method of initializing the bit table is used. However, in the case of MANET, there is no proper location to store the entire bit table separately because of the characteristics of the network being configured independently and having very limited resources. In addition, since MANET is an environment in which the routing information of a network changes frequently due to its dynamic characteristics, data previously stored in a bloom filter is very likely to be useless data.

Therefore, in the present invention, in order to select and delete old data stored in the bloom filter, the size of each entry is expanded to n bits as shown in FIG. 5, except for the most significant bit (MSB) of n bits. Use n-1 bits as the time tag representing the survival time of the entry.

At this time, the time tag is decremented by 1 every time interval determined by the system internal timer. When the value is finally 0, the entry is deleted from the bit table of the bloom filter.

Next, the most significant bit of the entry related to the digest among the entries of the bloom filter is set to 1, and the time tag values of the entry are all set to 1 (step 330). That is, the value of all bits of the entry associated with the input digest is set to one. Thereafter, the bit value corresponding to the time tag among the bits of each entry is decreased by one as time and elapses (step 340).

Meanwhile, while performing the above-described process, it is determined whether the entry corresponding to the previous input and the entry corresponding to the current input are overlapped (operation 350), and if duplicated, the time tag among the bits of the corresponding entry The value of all bits is reset to 1 (step 360). This ensures that entries that overlap in the previous input and the current input remain valid for the survival time within the table of the previous input, and remain valid on the table for the lifetime of the current input even when the previous input is deleted over time.

Finally, when the value of the bit corresponding to the time tag among the bits of each entry becomes 0, the corresponding entry is deleted from the Bloom filter (step 370).

6 illustrates a time tag setting of each entry and a time tag resetting process for duplicate entries. First, as shown in Fig. 6A, three entries are set by the first input. At this time, the most significant bit of each entry is set to 1, and the value of all bits corresponding to the time tag is also set to 1.

Thereafter, as shown in Fig. 6B, three times are set by the second input after the time t has elapsed. At this time, since some of the entries overlap with the entry set by the first input, the value of all bits corresponding to the time tag of the duplicate entry is reset to 1, and the bit corresponding to the time tag of the non-overlapping entry is t. It can be seen that the decrease.

Then, as shown in Fig. 6C, after the time s has elapsed from the time t, the entry set by the first input is deleted on the bit table of the Bloom filter. At this time, it can be seen that entries duplicated with the second input are valid on the table without being deleted.

Hereinafter, an example of a process in which the head node of each cluster stores the digest of the monitored packet in the bloom filter will be described. As shown in FIG. 7, it is assumed that 28 bytes of data monitored as an input of the hash function are used, and that the size of the digest, which is the output of the hash function, is 16 bits, and the size of an entry in the bit table is 8 bits. Assume In this case, the number of entries in the bit table is 64K (2 ⁿ = 2 ¹⁶ ).

That is, each entry is composed of 7 bits which play the role of time tag and the most significant bit which plays the role of existing in Bloom filter. Since the size of the time tag is 7 bits, the range of values that the time tag can have is 0 to 127 (0 to 2 ⁷ -1). Therefore, the entire bit table has a size of 64 KB.

Meanwhile, as shown in FIG. 7, since the most significant bit is set to 1 for the entry related to each digest and the time tag of the remaining n-1 bit size of the entry is set to the maximum value, the time tag value is 127. (0x7F = 0111 1111b).

In the Bloom filter configured as described above, an entry and deletion process of an entry over time and elapses is illustrated in FIG. 8. As shown in FIG. 8A, three entries are set for the first input, and as shown in FIG. 8B, the time tag value of the entry decreases after a predetermined time. On the other hand, as shown in FIG. 8C, when the second input occurs, since the fourth entry overlaps with the previous input, it can be seen that the time tag value of the fourth entry is reset to 127 which is the maximum value.

9 is a flowchart illustrating a method for backtracking an attack source node in a mobile adhook network according to an embodiment of the present invention.

First, a first head node of a first cluster receives a backtracking message from a first member node included in the first cluster (step 900). At this time, all nodes included in the cluster are equipped with a host-based IDS to detect an attack on the node itself. When each node is detected, the attack packet itself, the target node, and the attack are detected. The traceback message including the detected time information is transmitted to the head node of the cluster to which it belongs.

Thereafter, the first head node authenticates the received backtracking message (step 910). Authentication is necessary here because an attack can be made using an illegal traceback request.

Next, the first head node queries the head nodes of the clusters adjacent to it, for example, the second head node of the second cluster whether it has a digest associated with the attack packet (step 920).

Thereafter, when the second head node of the second cluster has a digest associated with the attack packet, the second head node transmits an acknowledgment that it has a digest to the first head node (step 930).

Next, the second head node queries the head nodes of the clusters adjacent to the cluster to which it belongs, for example, the third head node of the third cluster whether it has a digest associated with the attack packet (step 940).

Thereafter, when the third head node of the third cluster has a digest associated with the attack packet, the third head node transmits an acknowledgment that it has a digest to the second head node (step 950). During this process, a head node that does not have a digest associated with an attack packet naturally falls out of the traceback process by ignoring the traceback request.

By repeating the above process, the traceback request has a direction to the cluster including the attack source node. In this process, a message loop may occur, so the traceback message preferably includes a unique identifier such as a sequence number. .

Thereafter, the first head node generates a backtracking graph using an order of acknowledgments sequentially generated by each headnode and location information of each headnode (step 960), and uses the generated backtracking graph. In operation 970, the cluster including the attack source node is determined.

When the cluster including the attack source node is detected through the above-described process, it is possible to respond to the attack by taking measures such as filtering all traffic generated from the attack source node in the cluster.

The above-described attack source node traceback method is illustrated in FIG. 10. Referring to FIG. 10, the attack node A attacks the target node V through the routing path. In this process, the head node of the cluster to which the node in the path of attack packet belongs keeps this packet information. Subsequently, the head node CH4 of the cluster to which the target node V belongs to makes a backtrace request to the adjacent cluster head nodes CH1, CH3, and CH7, and the head node CH3 that detects the attack sends a response thereto. Thereafter, the head node CH3 makes a request to the neighboring cluster head node again, among which the head node CH5 responds. Through this process, the head node CH4 can generate a traceback graph called CH3-CH5-CH6, which indicates that the attack occurred in the cluster managed by the head node CH6.

The attack source node traceback method described above may be implemented in the form of a program that can be executed using various computer means. In this case, the program for executing the attack source node traceback method may be a hard disk, a CD-ROM, a DVD, It is stored in a computer-readable recording medium such as a ROM, a RAM, or a flash memory.

Those skilled in the art to which the present invention pertains will understand that the present invention can be implemented in other specific forms without changing the technical spirit or essential features.

Therefore, it is to be understood that the embodiments described above are exemplary in all respects and not restrictive. The scope of the present invention is shown by the following claims rather than the detailed description, and all changes or modifications derived from the meaning and scope of the claims and their equivalent concepts should be construed as being included in the scope of the present invention. do.

1 is a flow chart illustrating a packet storage method for backtracking an attack source node in a mobile adhook network according to an embodiment of the present invention.

2 shows the operation of a bloom filter.

3 is a flowchart showing how a head node stores a digest of monitored packets in a Bloom filter.

4 shows the structure of an IP packet.

5 shows the structure of an entry extended to n bits.

FIG. 6 is a diagram illustrating a time tag setting of an entry and a time tag reset process for duplicate entries. FIG.

7 is a diagram illustrating an example of a process in which a head node stores a digest of a monitored packet in a bloom filter.

FIG. 8 is a view illustrating a process of inputting and deleting entries over time in the bloom filter illustrated in FIG. 7.

9 is a flowchart illustrating a method for traceback of an attack source node in a mobile adhook network according to an embodiment of the present invention.

FIG. 10 is a schematic diagram showing the attack origin node traceback method shown in FIG. 9; FIG.

Claims (5)

As a method of backtracking an attack source node in a mobile ad-hoc network in which a plurality of nodes are clustered using a weighted clustering algorithm (WCA), (a) a head node of each cluster activating a network-based intrusion detection (NIDS) module mounted in the head node to monitor all packets; (b) the head node of each cluster storing a digest for the monitored packets in a Bloom Filter; (c) if the head node of each cluster receives a backtrace message generated by a member node included in the cluster, whether the head node of an adjacent cluster includes a digest associated with the attack packet included in the backtrace message. Requesting confirmation; (d) backtracking the attack source node using response acknowledgment messages received from head nodes of adjacent clusters; And (e) filtering all the traffic originating from the attack source node. According to claim 1, wherein step (b), (b1) generating digests of n bit size by inputting some bit size data of the monitored packet for k hash functions; (b2) expanding the size of each entry of the bloom filter of 2 ⁿ entries to n bits; (b3) setting all bits of the entry associated with the digest of the bloom filter to a first value; And (b4) If the value of the bit except the most significant bit becomes a second value by decreasing a value corresponding to a bit except the most significant bit among the bits of each entry as time elapses, the entry is deleted from the bloom filter. A method for backtracking an attack source node in a mobile adhook network, comprising the steps of: The method of claim 2, (b5) if an entry corresponding to a previous input and an entry corresponding to a current input of the entries of the bloom filter overlap, resetting all bits except the most significant bit among the bits of the corresponding entry to a first value And attack source node backtracking method in a mobile adhook network. The method of claim 2, wherein in step (b1), Partial bit size data of the monitored packet is generated by combining the IP header of 20 bytes of the packet and the first 8 bytes of the IP data, the attack source node backtracking method in a mobile ad-hook network. The method of claim 4, wherein And setting a value that can be changed as each packet is transmitted through each node of the IP header as a second value.

Images