Mechanism for tracing back anonymous network flows in autonomous systems
A system and method of tracing network flows in an autonomous communications system are described. The Autonomous System may be formed of multiple subgroups depending on size and application. Each subgroup contains multiple, interconnected routers which participate in transporting data flow across the Autonomous System (AS). A Director within the AS has a full and complete vision of the network topology. When it is desired to trace a particular flow because of an identified attack, selected routers in key locations—through which that particular flow travels—mark packets with labels which enable the tracing of the path. These labels permit the source of the attack, at least in so far as it travels through the AS, to be identified. If the number of entry (or key) points to the AS is larger than the number of available labels, the AS will be divided into subgroups, the flow is traced from subgroup to subgroup.
1. A method of determining a source of data packet flow into a plurality of network nodes forming an Autonomous System and connected to network devices that are external to the Autonomous System in a communication network, said Autonomous System including a Director that signals network nodes in said Autonomous System to initiate marking of packets, said method comprising:
detecting, by a detecting entity and according to a signature, packets of a particular flow for which the source is to be determined, said detecting entity signaling said Director to start a tracing process;
said Director requesting some of said network nodes to mark a subset of packets received by network nodes from said network devices through incoming interfaces during a period of time when marking network nodes are being identified and discontinue marking packets by said network nodes when there are no more marking network nodes to be identified, the marking including a router label that identifies a particular network node for each packet and an external interface label that identifies a particular incoming interface for each packet;
identifying, by a detecting network node, ones of said network nodes that are marking packets of the particular flow; and
for each identified network node that is marking packets of the particular flow, recording said router label and said external interface label as a source of the particular flow.
2. The method as defined in claim 1 , further comprising:
dividing the Autonomous System into multiple subgroups; and
determining sources across the multiple subgroups.
3. The method as defined in claim 2 , further comprising:
considering each subgroup is considered separately; and
removing sources which are links between subgroups for further consideration.
4. The method as defined in claim 1 , further comprising:
assigning dynamically the identification of said network node by said router label.
5. The method as defined in claim 1 , further comprising:
assigning dynamically the identification of said incoming interfaces, on said network nodes, by said external interface label.
6. The method as defined in claim 1 , further comprising:
marking the packets using any IP field, including IP Options.
7. The method as defined in claim 1 , wherein the detecting entity, which signals said Director to begin said tracing process, is said detecting network node.
8. The method as defined in claim 1 , wherein the detecting entity is a Last Router in the Autonomous System, the Last Router being located in the Autonomous System immediately before a victim of an attack.
9. The method as defined in claim 1 , wherein the detecting entity is a victim node in the Autonomous System, or directly connected to the Autonomous System.
10. The method as defined in claim 1 , further comprising:
removing all pre-existing markings on IP packets coming from external nodes with said network nodes requested to mark packets.
11. The method as defined in claim 1 , further comprising:
removing all pre-existing markings on IP packets coming from external nodes with said network nodes.
12. The method as defined in claim 1 ,
wherein said some of said network nodes are nodes having an interface connected to network equipment belonging to one of the following:
a. a different subgroup;
b. a different Autonomous System; and
c. end-user premises.
13. A system for determining sources of data packet flow into a plurality of network nodes forming an Autonomous System and connected to network devices that are external to the Autonomous System in a communication network comprising:
means, at some of the network nodes, to mark a subset of packets received by said network nodes from one or more of said network devices through incoming interfaces during a period of time when marking network nodes are being identified and discontinue marking packets by said network nodes when there are no more marking network nodes to be identified, the marking including a router label that identifies a particular network node for each packet and an external interface label that identifies a particular incoming interface for each packet;
means, at a detecting network node, to identify ones of said network nodes that are marking packets of that particular flow;
means for each identified marking network node to record said router label and said external interface label as a source of the particular flow; and
a Director in the Autonomous System for receiving a signal to proceed from a detecting entity that has discriminated, according to a signature, packets of a particular flow for which the source is to be determined, said Director initiating flow tracing in response to said signal to proceed by signaling said some of the network nodes to carry out said marking of packets.
14. The system as defined in claim 13 , further including:
means to coordinate all necessary entities and to communicate across different Autonomous Systems.
15. The system as defined in claim 13 ,
wherein the Autonomous System is divided into multiple subgroups and source determination is conducted across the multiple subgroups, from one to another.
16. The system as defined in claim 13 ,
wherein the signal is generated by said detecting network node, wherein said detecting network node is a Last Router in the Autonomous System, the Last Router being located in the AS immediately before a victim of an attack.
17. The system as defined in claim 13 ,
wherein the signal is generated by a victim node in the Autonomous System, or directly connected to the Autonomous System.
18. The system as defined in claim 13 ,
wherein the signal is generated by a trusted entity from another domain including the Director of an adjacent Autonomous System.
19. The system as defined in claim 13 ,
wherein the Director passes the labels to the network devices dynamically.
20. The system as defined in claim 13 , wherein the Director pre-assigns labels to network devices.
21. The system as defined in claim 13 , wherein the Director employs a combination of dynamic and static label assignment.
22. The system as defined in claim 13 ,
wherein said some of said network nodes are nodes having an interface connected to network equipment belonging to one of the following:
a. a different subgroup;
b. a different Autonomous System; and
c. end-user premises.