Log-based traceback system and method using centroid decomposition technique

• US 8,307,441 B2
• Filed: 11/21/2007
• Issued: 11/06/2012
• Est. Priority Date: 07/20/2007
• Status: Expired due to Fees

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Kim, Jong Hyun, Kim, Geon Lyang, Sohn, Seon Gyoung, Chang, Beom Hwan, Jeong, Chi Yoon, Ryu, Jong Ho, Na, Jung Chan, Jang, Jong Soo, Sohn, Sung Won
• Primary Examiner(s): Hoffman, Brandon
• Assistant Examiner(s): Woldemariam, Nega
• Application Number:
  US12/669,633
• Publication Number:
  US 20100212013A1
• Time in Patent Office: 1,812 Days
• Field of Search: 726/9, 726/23, 726/26, 726/27, 726/28, 726/29, 713/224, 713/201, 713/212, 713/213, 713/220, 713/223, 709/204, 709/201, 709/220, 709/224, 709/227, 707/600, 707/607, 707/608, 707/609, 707/687, 707/821, 380/200, 380/201, 380/202, 380/293, 380/227
• US Class Current: 726/23
• CPC Class Codes: H04L 2463/146 Tracing the source of attacks
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002

Abstract

There are provided a system and method for tracing back an attacker by using centroid decomposition technique, the system including: a log data input module collecting log data of an intrusion alarm from an intrusion detection system; a centroid node detection module generating a shortest path tree by applying a shortest path algorithm to network router connection information collected by a network administration server, detecting a centroid node by applying centroid decomposition technique removing a leaf-node to the shortest path tree, and generating a centroid tree whose node of each level is the detected centroid node; and a traceback processing module requesting log data of a router matched with the node of each level of the centroid tree, and tracing back a router identical to the log data of the collected intrusion alarm as a router connected to a source of an attacker by comparing the log data of the router with the log data of the collected intrusion alarm. According to the system and method, an attacker causing a security intrusion event may be quickly detected, a load on the system is reduced, and a passage host exposed to a danger or having weaknesses may be easily recognized, thereby easily coping with an attack.

Claims

1. A log-based traceback system using centroid decomposition technique, the system comprising:

a log data input module collecting log data of an intrusion alarm from an intrusion detection system;

a centroid node detection module generating a shortest path tree by applying a shortest path algorithm to network router connection information collected by a network administration server, detecting a centroid node by applying centroid decomposition technique removing a leaf-node to the shortest path tree, and generating a centroid tree whose node of each level is the detected centroid node; and

a traceback processing module requesting log data of a router matched with the node of each level of the centroid tree, and tracing back a router identical to the log data of the collected intrusion alarm by comparing the log data of the router with the log data of the collected intrusion alarm as a router connected to a source of an attacker.

2. The system of claim 1, further comprising a router control module extracting log data of the router matched with the node of each level of the centroid tree by remote-controlling the router and transferring the extracted log data to the traceback processing module.

3. The system of claim 2, further comprising an MAC (media access control) address detection module detecting MAC addresses of hosts connected to the router connected to the source of the traced back attacker and transferring the detected MAC addresses to the traceback processing module.

4. The system of claim 3, wherein the traceback processing module extracts an attack pattern from the log data of the router connected to the source of the attacker, searches an MAC address identical to the extracted attack pattern, requests an IP address corresponding to the MAC address having the attack pattern, and traces the source of the attacker.

5. The system of claim 4, further comprising a traceback result database storing attack path information that is a result of tracing back the source of the attacker.

6. The system of claim 1, wherein the centroid tree has a high level centroid node that is one finally left after repeatedly removing a subordinate leaf-node of the shortest path tree and a plurality of low level centroid nodes, which are finally left after repeatedly removing a leaf-node from a plurality of trees obtained by removing the one finally left from the shortest path tree.

7. A method of generating a centroid tree by using centroid decomposition technique, the method comprising:

collecting network router connection information from a network administration server;

generating a shortest path tree by applying a shortest path algorithm to the collected network router connection information; and

generating a centroid tree where a centroid node that is detected by applying centroid decomposition technique of removing a leaf-node of the shortest path tree becomes a node of each level.

8. The method of claim 7, wherein the generating a centroid tree comprises:

removing a low level leaf-node of the shortest path tree;

repeatedly removing a leaf-node from a tree formed of nodes left after the low level leaf-node until only one node is left;

determining the one node as a high level centroid node;

repeatedly removing a leaf-node from a plurality of trees obtained by removing the high level centroid node from the shortest path tree until only one node is finally left;

determining a plurality of nodes finally left in the plurality of trees as low level centroid nodes; and

generating a centroid tree where the high level centorid node is a root and the low level centroid node is a low level node.

9. A log-based traceback method using centroid decomposition technique, the method comprising:

collecting log data of an intrusion alarm generated from an intrusion detection system and connection information of a network router where an attack packet pass through from a network administration server;

generating a centroid tree where a centroid node that is detected by applying centroid decomposition technique of removing a leaf-node to the connection information of the network router where an attack packet passes through is a node for each level;

comparing log data of the node for each level of the centroid tree with log data of the intrusion alarm collected from the intrusion detection system to search a router connected to a source of an attacker; and

extracting an attack pattern from the log data of the router connected to the source of the attacker, searching an MAC address identical to the attack pattern, and tracing back the source of the attacker by requesting an IP address corresponding to the MAC address.

10. The method of claim 9, wherein the generating a centroid tree where a centroid node that is detected by applying centroid decomposition technique of removing a leaf-node to the connection information of the network router where an attack packet passes through is a node for each level comprises:

generating a shortest path tree by applying a shortest path algorithm to the connection information of the network router where the attack packet passes through; and

generating a centroid tree where a centroid node is detected by applying the centroid decomposition technique of removing the leaf-node of the shortest path tree is a node for each level.

11. The method of claim 10, wherein the generating a centroid tree where a centroid node is detected by applying the centroid decomposition technique of removing the leaf-node of the shortest path tree is a node for each level comprises:

removing a low level leaf-node from the shortest path tree;

repeatedly removing a leaf-node from the shortest path tree from which the low level leaf-node is removed, until only one node is left;

determining the only one node finally left as a high level centroid node;

repeatedly removing a leaf-node from a plurality of trees obtained by removing the high level centroid node from the shortest path tree until only one node is finally left;

determining a plurality of nodes finally left in the plurality of trees as low level centroid nodes; and

generating a centroid tree where the high level centorid node is a root and the low level centroid node is a low level node.

12. The method of claim 9, wherein comparing log data of the node for each level of the centroid tree with log data of the intrusion alarm collected from the intrusion detection system to search a router connected to a source of an attacker comprises:

querying log data of each node in an order of a high level of the centroid tree and from left to right in the same level and comparing the log data of the each node with log data of an intrusion path;

determining whether a node is a leaf-node or not, when there is the node with log data identical to the log data of the intrusion path as a result of the comparing; and

determining the node as the router connected to the source of the attacker when the node is the leaf-node as a result of the determining.

13. The method of claim 12, wherein, further comprising tracing back the router connected to the source of the attacker by searching whether a high level node is present, when the node is a root node and the log data thereof is not identical to the log data of the intrusion path as a result of the comparing.

14. The method of claim 12, further comprising determining a node with log data finally detected as the router connected to the source of the attacker, when the node is a low level node and the log data thereof is not identical to the log data of the intrusion path as a result of the comparing.

15. The method of claim 12, further comprising removing high level nodes of a node, which has identical log data but is not a leaf-node, from the centroid tree in the shortest path tree and returning to the comparing, when the node with the identical log data is not a leaf-node.