Method and apparatus for tracing packets

Abstract

A system and method for performing source path isolation in a network. The system comprises an intrusion detection system (IDS), a source path isolation server (SS 1 ) and at least one router configured to operate as a source path isolation router (SR 1 ) operating within an autonomous system. When IDS detects a malicious packet, a message is sent to SS 1. SS 1 in turn generates a query message (QM) containing at least a portion of the malicious packet. Then, QM is sent to participating routers located one hop away. SR 1 uses the query message to determine if it has observed the malicious packet by comparing it with locally stored information about packets having passed through SR 1. SR 1 sends a reply to SS 1, and SS 1 uses the reply to identify the ingress point into the network of the malicious packet.

1 - 20 . (canceled) 
   
   
       21 . A system for determining a point of entry of a malicious packet into a network using a representation of the malicious packet, the system comprising:
 an intrusion detection system for detecting the malicious packet in the network; and   an isolation server responsive to operation of the intrusion detection system, for isolating the malicious packet;   wherein the system is operable such that the point of entry of the malicious packet is determined.   
   
   
       22 . The system of  claim 21  and wherein the isolation server further comprises: computer code for generating a message containing identification information about the malicious packet. 
   
   
       23 . The system of  claim 22  and wherein the isolation server further comprises: computer code for forwarding the message to certain of a plurality of routers displaced one hop away from the server. 
   
   
       24 . The system of  claim 23  and wherein the certain of the plurality of routers comprises:
 computer code for generating a hash value of the identification information;   computer code for establishing a bit map of hash values representative of those of packets which are transmitted through the certain of the plurality of routers; and   computer code for comparing the hash value against the hash values.   
   
   
       25 . A computer program product embodied on a computer readable medium for determining whether a target packet has been encountered in a network, comprising:
 computer code for sending a message identifying the target packet to at least one network component;   computer code for receiving a reply containing information associated with the target packet from the at least one network component; and   computer code for processing the reply to extract the information; and   computer code for using the information, wherein the computer program product is operable such that it is determined whether the target packet has been encountered in the network.   
   
   
       26 . The computer program product of  claim 25  and wherein a detection device is incorporated into a server including at least a portion of the computer code. 
   
   
       27 . The computer program product of  claim 25  and wherein the network further includes a host, the host including capability for placing packets onto the network. 
   
   
       28 . The computer program product of  claim 25  and wherein the computer code for sending operates to include the target packet into the message. 
   
   
       29 . The computer program product of  claim 25  and wherein the message comprises a representation of the target packet. 
   
   
       30 . The computer program product of  claim 29  and wherein the representation is a hash of at least a portion of the target packet. 
   
   
       31 . The computer program product of  claim 25  and wherein the at least one network component is located one hop away from a server. 
   
   
       32 . The computer program product of  claim 25  and wherein the at least one network component is located more than one hop away from a server. 
   
   
       33 . The computer program product of  claim 25  and wherein a first component of the at least one network component forwards the reply to another of the at least one network component. 
   
   
       34 . The computer program product of  claim 33  and wherein the first component is a router. 
   
   
       35 . The computer program product of  claim 25  and wherein the information is hash information derived from hashing at least a portion of the message to obtain a query hash value. 
   
   
       36 . The computer program product of  claim 25  and wherein the computer code for determining is accomplished using a source path isolation technique. 
   
   
       37 . The computer program product of  claim 36  and wherein the source path isolation technique includes a breadth-first search. 
   
   
       38 . The computer program product of  claim 36  and wherein the source path isolation technique includes a depth-first search. 
   
   
       39 . A method for determining whether a target packet has been encountered in a network, comprising:
 sending a message identifying the target packet to at least one network component;   receiving a reply containing information associated with the target packet from the at least one network component; and   processing the reply to extract the information; and   using the information, wherein it is determined whether the target packet has been encountered in the network.