Abstract:
In general, the invention is directed to techniques of identifying an infected network device in a computer network where traffic to and from the infected network device is not necessarily routed through a single point on the computer network. For example, individual line cards in network devices count incoming network flows from network devices in host tables. The host tables of all line cards of all participating network devices are then correlated. It is then determined whether the number of flows from a network device outweighs the number of flows to the network device to a significant degree. If so, the network device may be considered suspicious. Packets from a suspicious network device may be rerouted to a network security device for more thorough inspection.

Description:
TECHNICAL FIELD 
       [0001]    The invention relates to computer networks, and particularly to computer network security. 
       BACKGROUND  
       [0002]    Computer viruses and worms are major threats to corporate and home computer networks. Viruses and worms may cause exposure of sensitive information, congestion of computer networks, hardware and software malfunction, and other problems. Many viruses and worms attempt to replicate themselves on as many network devices as possible. To replicate itself, a virus or worm on an infected network device may cause the network device to attempt to create network connections to other network devices. If the network device successfully creates a network connection to another network device, the virus or worm may use the network connection to transmit a copy of itself to the other network device or to cause the other network device to execute malicious code. 
         [0003]    In general, an infected network device is not preprogrammed with network addresses of network devices within the network (e.g., an enterprise network) that are online and able to accept connections with the infected network device. Consequently, the infected network device typically performs a portscan of network addresses to find vulnerable systems by attempting to establish network connections over a series of network addresses. For example, the infected network device may send an invitation to create a network connection (e.g., a Transport Control Protocol SYN message) to each Internet Protocol address in a local subnet (e.g., 68.122.053.xxx). Because the infected network device is sending invitations to network devices that may not exist or may not accept network connections, many of the invitations sent by the infected network device are rejected or simply fail. An infected network device that sends many invitations to create network connections without many of these invitations being accepted is sometimes referred to as a “suspicious network device.” 
         [0004]    A network security device may use a threshold random walk algorithm to identify suspicious network devices. A network security device using the threshold random walk algorithm maintains a counter for each network device that has sent an invitation through the network security device. The network security device increments the counter for a network device whenever an invitation from the network device is accepted and decrements the counter for the network device whenever an invitation from the network device is rejected. If the counter for a network device falls below a minimum threshold, this indicates that the network device is sending many invitations to other network devices without many of those network devices accepting the invitations. Hence, the network security device may suspect that the network device has been infected by a virus or other threat. The network security device may then quarantine the suspected infected network device. 
       SUMMARY 
       [0005]    In general, the invention is directed to techniques of identifying an infected network device in a computer network where traffic to and from the infected network device is not necessarily routed through a single point on the computer network. For example, in one embodiment, individual line cards in network devices distributed throughout the network count incoming network flows from network devices. The line cards of the distributed network devices may, for example, maintain host tables that store statistics for the network flows identified by each line card. Control units in each of the network devices correlate the host tables of all line cards of all participating network devices. The control units then determine whether the number of flows from a network device outweighs the number of flows to the network device to a significant degree. If so, the control units may consider the network device to be suspicious. The control units may then reroute packets from a suspicious network device to a network security device for more thorough inspection. 
         [0006]    For example, a router in an enterprise network may include a set of line cards. Each line card maintains a hash table and a host table. When a line card receives a packet from the enterprise network, the line card determines whether the packet represents a rejection of a network connection (e.g., a TCP RST packet). If the packet does not represent a rejection of a network connection, the line card determines whether the packet is part of a flow in the hash table. If the packet is not part of a flow in the hash table, the line card enters a new flow in the hash table and increments counters in the host table for the source address of the packet and the destination address of the packet. Next, e.g., periodically, a control unit in the router may correlate the host tables in the line cards into a device host table. The control unit may coordinate with control units of other routers in the enterprise network to correlate device host tables of other distributed devices into a system host table. The control unit, operating on behalf of the distributed devices, may then analyze the system host table to identify network devices for which the number of failed connection attempts exceeds a given threshold. If the number of failed connection attempts exceeds the threshold, the control unit may determine that the identified network devices may be attempting to initiate many network connections that either fail or that other devices are rejecting. Because this is a hallmark of an infected network device, the control unit may instruct the line cards to reroute network traffic from the network devices to an intrusion detection and prevention device that may determine whether the network devices are, in fact, infected. In this way, the routers of the enterprise network may cooperate to identify suspicious network devices even though all traffic from a given network device may not necessarily flowing through a common point in the enterprise network, as is often the case in networks that utilize asymmetric routing. 
         [0007]    In one embodiment, a method comprises determining whether a difference between a number of network flows sent from a host device on a network via a plurality of network paths and a number of network flows sent to the host device on the network via the plurality of network paths exceeds a first threshold. The method also comprises rerouting network traffic from the host device when it is determined that the difference exceeds the first threshold. 
         [0008]    In another embodiment, a network device comprises a threat identification module to determine whether a difference between a number of network flows sent from a host device on a network via a plurality of network paths and a number of network flows sent to the host device on the network via the plurality of network paths exceeds a first threshold. The network device also comprises a traffic redirection module to reroute network traffic from the host device when the threat identification module determines that the difference exceeds the first threshold. 
         [0009]    In another embodiment, a computer-readable medium comprises instructions. The instructions cause a programmable processor of a network device to determine whether a difference between a number of network flows sent from a host device on a network via a plurality of network paths and a number of network flows sent to the host device on the network via the plurality of network paths exceeds a first threshold. The instructions also cause the processor to reroute network traffic from the host device when it is determined that the difference exceeds the first threshold. 
         [0010]    The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0011]      FIG. 1  is a block diagram illustrating an exemplary asymmetrically routed network in which routers cooperate to implement a distributed random walk technique to identify any suspicious host devices. 
           [0012]      FIG. 2  is a block diagram illustrating an exemplary router that uses a distributed random walk technique to identify potentially infected host devices within an asymmetrically routed network. 
           [0013]      FIG. 3  is a flowchart illustrating an exemplary operation of a flow module in a line card of a router that uses a distributed random walk technique to identify potentially infected host devices within an asymmetrically routed network. 
           [0014]      FIG. 4  is a flowchart illustrating an exemplary operation of a control unit of a router that uses a distributed random walk technique to identify potentially infected host devices that are suspicious. 
           [0015]      FIG. 5  is a tabular diagram illustrating an exemplary configuration of line card host tables. 
           [0016]      FIG. 6  is a tabular diagram illustrating an exemplary configuration of device host tables. 
           [0017]      FIG. 7  is a tabular diagram illustrating an exemplary configuration of a system host table. 
           [0018]      FIG. 8  is a graph representing an exemplary difference between a number of flows sourced by a host device and a number of flows sent to the host device over time. 
       
    
    
     DETAILED DESCRIPTION 
       [0019]      FIG. 1  is a block diagram illustrating an exemplary system  2  that includes an asymmetrically routed network  6  in which routers  8 A and  8 B cooperate to implement a distributed random walk technique to identify any suspicious host devices. For purposes of example, system  2  is shown as including routers  8 A and  8 B that cooperate to implement a distributed random walk technique to identify any host devices that are suspicious. For ease of illustration, only two host devices  4 A and  4 B (collectively, host devices  4 ) are shown, and the host devices may be personal computers, servers, network data centers, intermediate network devices, television set-top boxes, network telephones, network appliances, mobile devices, and so on. 
         [0020]    Network  6  may be an enterprise network. For example, a corporation may maintain network  6  to facilitate communication for employees&#39; computers and for communication with clients and customers. Host devices  4  may be coupled directly or indirectly to network  6 . For example, host device  4 A may be indirectly coupled to network  6  via an internet service provider and the Internet or via a private network link. Meanwhile, host device  4 B may be directly coupled to network  6 , as could be the case if host device  4 B is a network device coupled to a local area network (LAN) of an enterprise. 
         [0021]    System  2  illustrates a simplified example of an asymmetrically routed network. That is, traffic flowing in one direction from host device  4 A to host device  4 B flows through a different path than traffic flowing in the opposite direction. As described herein, routers  8 A cooperate to detect any of host devices  4  that may become infected with computer viruses or worms. For example, such malicious computer programs may cause host devices  4  to attempt to create network connections through network  6  to other ones of host devices  4 . The malicious programs may then attempt to use these network connections for illegitimate purposes. For example, a malicious program executing on host device  4 A could use a network connection to host device  4 B to make host device  4 B execute a copy of the malicious program. In another example, the malicious program executing on host device  4 A could use a network connection to host device  4 B to cause host device  4 B to send sensitive information, such as credit card numbers, to host device  4 A. 
         [0022]    In most cases, malicious programs are not preprogrammed with knowledge of the network addresses of host devices  4  and with knowledge of which ones of host devices  4  accept network connections. Therefore, malicious programs may cause the infected host device to attempt to create many network connections in an attempt to identify network addresses of host devices  4  and to identify which ones of host devices  4  accept network connections. Many of these attempts will fail either because no host device exists with a given network address or because host devices  4  refuse to create network connections with the infected host device. Thus, a hallmark indication of viral infection is a host device that attempts to create a significantly greater number of network connections than are accepted. Furthermore, if one or more of host devices  4  makes many unsuccessful attempts to create network connections with a particular host device, this may be an indication that the particular host device is “under attack.” That is, a malicious program executing on one or more of host devices  4  may be targeting a particular device for some illegitimate purpose. 
         [0023]    In order to create network connections to other host devices, host devices  4  send connection requests through network  6 . Each connection request typically includes a source address field, a destination address field, a protocol field, a source port field, and a destination port field. For example, if the connection request is from host device  4 A to host device  4 B, the source address field contains the network address of host device  4 A, the destination address field contains the network address of host device  4 B. A set of packets sharing the same values for the source address field, the destination address field, the protocol field, the source port field, and the destination port field may be referred to as a “network flow.” 
         [0024]    Each of routers  8  may include sets of line cards to send and receive packets, including connection requests and connection acknowledgements. The line cards may be interconnected by a high-speed switch. The line cards of the routers  8  may, for example, maintain host tables that store statistics for the network flows identified by each line card. For example, when a line card in one of routers  8  receives a packet from one of host devices  4  or another one of routers  8 , the line card determines whether the packet represents a rejection of a connection (e.g., a TCP RST packet). If the packet represents a rejection of a connection, the line card forwards the packet. Otherwise, if the packet does not represent a rejection of a connection, the line card extracts information that identifies a flow for the packet. In other words, the line card extracts the source address field, the destination address field, the protocol field, the source port field, and the destination port field of the packet. The line card may then access a hash table to determine whether the line card has previously received another packet in the same flow. That is, the line card may perform a hash function on the source address field, the destination address field, the protocol field, the source port field, and the destination port field of a packet. If the hash table does not contain an entry for the resulting hash value, the line card regards the packet as being part of a new flow and creates an entry in the hash table for the hash value. If the line card has previously received another packet in the same flow as the packet, the line card updates a timestamp in the hash table and forwards the packet without updating its LC host table. 
         [0025]    If the line card has not previously received another packet in the same flow as the packet, the line card modifies the LC host table to record the detected flow. Importantly, the flow need not represent an established connection. Rather, the line card even records connection attempts (e.g., SYN packets) and connection acknowledgements (e.g., SYN-ACKS) between host devices. In one embodiment, the host table within each line card contains an entry for each network address that has been used in a packet as a source address or as a destination address. Each entry in the host table contains a host source counter and a destination source counter. For each new flow, the line card updates its host table by incrementing the source counter for the network address of the source device and incrementing the destination counter for network address of the destination device. In this way, the line card maintains a record of the number of flows each host device sources and a record of the number of flows for which each host device operates as a destination. 
         [0026]    Periodically, each of the control units of routers  8  correlate the LC host tables of their respective line cards into a respective “device host table.” For example, the control unit merges the LC host tables from its line cards and into a device host table by creating an entry in the device host table for each unique entry in the line card host tables. That is, the control unit creates an entry in the device host table for each network address that has been specified as either a source address or a destination address in a packet flow received by any of the line cards. For each of the entries in the device host table, the control unit sums the source counters of each equivalent entry of the line card host tables and sums the destination counters of each equivalent entry in the line card host tables. In this way, the control unit maintains a record of the number of flows through the router for which a host device is a source and a record of the number of flows through the router for which a host device is a destination. 
         [0027]    After correlating the host tables of the line cards into device host tables, the control units of routers  8  may correlate the device host tables of each of routers  8  into system host tables. For example, a control unit of one of routers  8  may send a request for device host table information to each of the other routers in a peer-to-peer fashion using a network management protocol such as Link Level Discovery Protocol (LLDP). In response, the other routers communicate their respective device host tables to the requesting router. The receiving router then correlates the distributed host tables into a single system host table for asymmetrically routed network  6 . 
         [0028]    To correlate the device host tables, the control unit of the receiving router creates an entry in the system host table for each unique entry in the device host tables. For each of the entries in the system host table, the control unit sums the source counters of each equivalent entry of the device host tables and sums the destination counters of each equivalent entry of the device host tables. In this way, the control unit maintains a record of the number of flows through network  6  for which a host device is a source and a record of the number of flows through network  6  for which a host device is a destination. 
         [0029]    Control units of routers  8  may use system host tables to identify any suspicious network devices, which may provide an indication that the device has been infected by a virus or other threat. For example, a control unit of one of routers  8  may analyze a system host table to compare the relative number of flows through network  6  for which a host device is a source to the number of flows for which the host device is a destination. For example, the control unit may subtract the destination counter in the system host table for a host device from the source counter for that host device. If the difference exceeds a given threshold, the control unit may consider the host device to be suspicious. 
         [0030]    In the situation where a host device is sourcing significantly more flows than the host device is receiving, in view of the realization that host devices generally communicate using bidirectional flows, the control unit may determine that the host device is may be attempting to create network connections with other host devices that either do not exist or that are rejected the connection attempts. In this manner the control unit may use the system host table to identify indicators that one of host devices  4  within asymmetrically routed network  6  is infected with a computer virus or worm even though neither router  8 A or  8 B necessarily views all of the traffic to and from that host device. Furthermore, if the relative number of flows through network  6  for which a host device is a destination compared with the number of flows for which the host device is a source exceeds a second threshold, the control unit may consider the host device to be under attack. 
         [0031]    When a control unit of one of routers  8  considers one of host devices  4  to be suspicious, the control unit may cause packets from the host device to be rerouted to an Intrusion Detection and Prevention (“IDP”) device  10 . In addition, when a control unit of one of routers  8  considers one of host devices  4  to be under attack, the control unit may cause packets addressed to the host device to be rerouted to IDP device  10 . For example, a control unit of router  8 A may send instructions to each line card in router  8 A to update forwarding tables in the line cards such that the line cards forward packets from the suspected host device to IDP device  10 . IDP device  10  may then inspect packets from the suspected host device to determine whether the packets contain other indications that malicious software has actually infected the suspected host device. For instance, IDP device  10  may deeply inspect the contents of the packets for signatures of malicious software. If IDP device  10  confirms that malicious software has infected the suspected host device, IDP device  10  may cause the suspected host device to be quarantined. For example, IDP device  10  may send instructions to routers  8  to drop packets from the suspected host device. In addition, IDP device  10  may send an alert regarding the possible infection to a user of the suspected host device. 
         [0032]    The present invention may provide one or more advantages. For example, the present invention may be able to identify potentially infected host devices when flows to and from the host devices, including network connection requests and acknowledgements, may follow different paths through a network. For this reason, it is not necessary for all network traffic to flow through a common point on the network in order to identify potentially infected host devices. Because not all network traffic must flow through a common point on the network, the present invention may remove a significant bottleneck. Furthermore, because the present invention does not require the deep inspection of packets in a network security device (e.g., IDP device  10 ) to initially detect potentially infected host devices, a line card may implement embodiments of the present invention while forwarding packets at line speed. 
         [0033]      FIG. 2  is a block diagram illustrating an exemplary router  8 A that uses a distributed random walk technique to identify potentially infected ones of host devices  4  within an asymmetrically routed network. As illustrated in the example of  FIG. 2 , router  8 A comprises a control unit  20 , a switch fabric  22 , and a set of line cards  24 A through  24 N (collectively, line cards  24 ). Line cards  24 A through  24 N may send packets to or receive packets from network paths  26 A through  26 N, respectively. Network paths  26 A through  26 N may be referred to herein as network paths  26 . 
         [0034]    Each of line cards  24 A through  24 N include flow modules  28 A through  28 N, hash tables  30 A through  30 N, forwarding tables  32 A through  32 N, and LC host tables  34 A through  34 N, respectively. Flow modules  28 A through  28 N may be collectively referred to herein as flow modules  28 , hash tables  30 A through  30 N may be collectively referred to herein as hash tables  30 , forwarding tables  32 A through  32 N may be collectively referred to as forwarding tables  32 , and LC host tables  34 A through  34 N may be collectively referred to herein as LC host tables  34 . 
         [0035]    When one of line cards  24  receives a packet from a respective one of network paths  26 , a respective one of flow modules  28  extracts flow information from the packet. For example, if line card  24 A receives a SYN packet or a SYN-ACK packet from network path  26 A, flow module  28 A extracts flow information from the packet. In particular, flow module  28 A may extract a source address field, a destination address field, a protocol field, a source port field, and a destination port field from the network packet. After extracting flow information from the packet, flow module  28 A may perform a hash function on the flow information to obtain a hash value. Flow module  28 A may then determine whether hash table  30 A contains an entry for the hash value. Each entry in hash table  30 A may be a timestamp that indicates the last time flow module  28 A used the entry. Given an appropriate hash function and hash table data structure, flow module  28  may be able to perform the hash function and the hash table look up at line speed. In some embodiments, hash table  30 A may be replaced by a flow database that stores flow information or otherwise. 
         [0036]    If hash table  30 A contains an entry for the hashed flow information, flow module  28 A does not consider the received packet to be a part of a new flow. Because flow module  28 A does not consider the received packet to be a part of a new flow, flow module  28 A may update the timestamp of the entry in hash table  30 A for the extracted flow information. Flow module  28 A may then forward the packet on network  6  via one of network paths  26  according to forwarding information stored in forwarding table  32 A. However, if hash table  30 A does not contain an entry for the hashed flow information, flow module  28 A adds a new entry to hash table  30 A for the hashed flow information. 
         [0037]    Flow module  28 A may periodically purge entries from hash table  30 A when the timestamp indicates use the timestamp of a record in hash table  30 A to purge old entries from hash table  30 A. For example, if a timestamp of a record in hash table  30 A indicates a time more than five minutes ago, flow module  28 A may delete the record in hash table  30 A. When flow module  28 A receives a packet, flow module  28 A sets a timestamp of a record in hash table  30 A for the flow of the packet to the current time. In this way, hash table  30 A is more likely to contain only active network flows. 
         [0038]    In addition to adding a new entry to hash table  30 A when hash table  30 A does not contain an entry for the hashed flow information, flow module  28 A also modifies LC host table  34 A to record the new flow. LC host table  34 A contains entries for each host device specified as a source device or as a destination device in network flows that have recently passed through line card  24 A. Each entry in LC host table  34 A includes a source counter and a destination counter. The source counter of an entry for a host device in LC host table  34 A specifies the number of flows that have recently passed through line card  24 A that have specified the host device as a source device. The destination counter of an entry for a host device in LC host table  34 A specifies the number of flows that have recently passed through line card  24 A that have specified the host device as a destination device. 
         [0039]    To modify LC host table  34 A, flow module  28 A may first determine whether LC host table  34 A contains an entry for the source device specified in the packet. If LC host table  34 A does not contain an entry for the source device specified in the packet, flow module  28 A adds an entry in LC host table  34 A for the source device specified in the packet. Flow module  28 A then sets a source counter in the entry for the source device specified in the packet to one. On the other hand, if LC host table  34 A contains an entry for the source device specified in the packet, flow module  28 A increments the source counter in the entry by one. 
         [0040]    After determining whether LC host table  34 A contains an entry for the source device specified in the packet, flow module  28 A determines whether LC host table  34 A contains an entry for the destination device specified in the packet. If LC host table  34 A does not contain an entry for the destination device specified in the packet, flow module  28 A adds an entry in LC host table  34 A for the destination device specified in the packet. Flow module  28 A then sets a destination counter in the entry for the destination address specified in the packet to one. On the other hand, if LC host table  34 A contains an entry for the destination device specified in the packet, flow module  28 A increments the destination counter in the entry by one. 
         [0041]    Each entry in LC host table  34 A may also contain a host bitmap field and a port bitmap field. In some embodiments, flow module  28 A may use the host bitmap field to compress the source and destination counters into a single fixed width field. This compression may be useful when LC host tables  34 A are correlated as explained below. 
         [0042]    A line card correlation module  36  in control unit  20  may periodically correlate LC host tables  34  into a device host table  38 . For example, line card correlation module  36  may periodically request that each of line cards  24  send copies of LC host tables  34  to line card correlation module  36 . After receiving the copies of LC host tables  34 , line card correlation module  36  creates an entry in device host table  38  for each unique entry in LC host tables  34 . Thus, device host table  38  contains entries for each host device specified as a source device or as a destination device in network flows that have recently passed through router  8 A. Like LC host tables  34 , each entry in device host table  38  includes a source counter and a destination counter. The source counter of an entry for a host device in device host table  38  specifies the number of flows that have recently passed through router  8 A that have specified the host device as a source device. In other words, the source counter for an entry for a host device in device host table  38  is the sum of the source counters for the host device in each of LC host tables  34 . The destination counter of an entry for a host device in device host table  38  specifies the number of flows that have recently passed through router  8 A that have specified the host device as a destination device. In other words, the destination counter for an entry for a host device in device host table  36  is the sum of the destination counters for the host device in each of LC host tables  34 . 
         [0043]    A device correlation module  40  in control unit  20  may periodically correlate device host table  38  with other device host tables in other ones of routers  8  into a system host table  42 . For example, device correlation module  40  may periodically request that each of routers  8  send copies of their device host tables to device correlation module  40 . After receiving copies of the device host tables, device correlation module  40  creates an entry in system host table  42  for each unique entry in the device host tables. Thus, system host table  42  contains entries for each host device specified as a source device or as a destination device in network flows that have recently passed through routers  8 . Like device host table  38 , each entry in system host table  42  includes a source counter and a destination counter. The source counter of an entry for a host device in system host table  42  specifies the number of flows that have recently passed through routers  8  that have specified the host device as a source device. In other words, the source counter for an entry for a host device in system host table  42  is the sum of the source counters for the host device in each of the device host tables. The destination counter of an entry for a host device in system host table  42  specifies the number of flows that have recently passed through routers  8  that have specified the host device as a destination device. In other words, the destination counter for an entry for a host device in system host table  42  is the sum of the destination counters for the host device in each of the device host tables. 
         [0044]    A threat identification module  44  in control unit  20  analyzes system host table  42  to identify ones of host devices  4  that are suspicious or potentially under attack. For example, for each entry in system host table  42 , threat identification module  44  may calculate a difference by subtracting the destination counter for the host from the source counter. If the difference is above a first threshold (e.g., plus fifty), threat identification module  44  may consider the host device associated with the entry to be suspicious because the host device is sourcing more flows (including connection requests, e.g., SYN packets) than the host device is receiving (including connection acknowledgements, e.g., SYN-ACK packets). On the other hand, if the difference is below a second threshold (e.g., negative fifty), threat identification module  44  may consider the host device to be potentially under attack because the host device is receiving significantly more flows (including connection requests, e.g., SYN packets) than the host device is sending (including connection requests, e.g., SYN packets). 
         [0045]    When threat identification module  44  determines that one of host devices  4  is suspicious or potentially under attack, threat identification module  44  sends an alert to a traffic redirection module  46  in control unit  20 . Traffic redirection module  46  is responsible for rerouting network traffic from the suspected one host devices  4  to IDP device  10  when threat identification module  44  determines that the difference between the number of network flows sent from a host device on network  6  via network paths  26  and a number of network flows sent to the host device on network  6  via network paths  26  exceeds the first threshold. For example, traffic redirection module  46  may send instructions to line cards  24  to modify forwarding tables  32  in response to the alert from threat identification module  44 . If threat identification module  44  determines that one of host devices  4  is suspicious, traffic redirection module  46  may send instructions to line cards  24  to modify forwarding tables  32  such that line cards  24  forward packets from the suspected host device to IDP device  10 . If threat identification module  44  determines that one of host devices  4  is potentially under attack, traffic redirection module  46  may send instructions to line cards  24  to modify forwarding tables  32  such that line cards  24  forward packets to the potentially attacked host device to IDP device  10 . In this way, IDP device  10  may inspect the packets more thoroughly. 
         [0046]      FIG. 3  is a flowchart illustrating an exemplary operation of a flow module (e.g., flow module  28 A) in line card  24 A of router  8 A that uses a distributed random walk technique to identify potentially infected host devices within an asymmetrically routed network. Initially, flow module  28 A receives a packet from network path  26 A ( 50 ). After receiving the packet, flow module  28 A determines whether the packet represents a rejection of a network connection ( 51 ). If the packet represents a rejection of a network connection (“YES” of  51 ), flow module  28 A forwards the packet ( 58 ). On the other hand, if the packet does not represent a rejection of a network connection (“NO” of  51 ), flow module  28 A extracts flow information from the packet ( 52 ). 
         [0047]    Flow module  28 A uses the extracted flow information to determine whether the packet belongs to a new flow ( 54 ). For example, flow module  28 A may perform a hash function on the extracted flow information to derive a hash value. Flow module  28 A may then determine that the flow is a new flow if hash table  30 A does not contain an entry for that hash value or does not contain an entry with a recent timestamp. If the packet does not belong to a new flow (“NO” of  54 ), flow module  28 A may update a timestamp in the entry of hash table  30 A with flow information that matches the extracted flow information ( 56 ). Flow module  28 A may then forward the packet ( 58 ). On the other hand, if the packet does belong to a new flow (“YES” of  54 ), flow module  28 A may add an entry for the new flow to hash table  30 A ( 60 ). For instance, flow module  28 A may create an entry containing a timestamp in hash table  30 A at a hash value of the extracted flow information. 
         [0048]    After flow module  28 A adds an entry for the new flow to hash table  30 A, flow module  28 A determines whether LC host table  34 A contains an entry for a destination host specified in the packet ( 62 ). If LC host table  34 A does not contain an entry for the destination host specified in the packet (“NO” of  62 ), flow module  28 A adds an entry to LC host table  34 A for the destination host specified in the packet ( 64 ). 
         [0049]    After adding the entry to LC host table  34 A for the destination host specified in the packet or if LC host table  34 A already contains an entry for the destination host specified in the packet (“YES” of  62 ), flow module  28 A determines whether LC host table  34 A contains an entry for the source host specified in the packet ( 66 ). If LC host table  34 A does not contain an entry for the source host specified in the packet (“NO” of  62 ), flow module  28 A adds an entry to LC host table  34 A for the source host specified in the packet ( 68 ). 
         [0050]    After adding the entry to LC host table  34 A for the source host device specified in the packet or if LC host table  34 A already contains an entry for the source host device specified in the packet (“YES” of  66 ), flow module  28 A increments a source counter in the entry of LC host table  34 A for the source host device specified in the packet ( 70 ). Flow module  28 A then increments a destination counter in the entry of LC host table  34 A for the destination host device specified in the packet ( 72 ). Once flow module  28 A has incremented the destination counter, flow module  28 A may update the timestamp for the flow of the packet in hash table  30 A ( 56 ) and forward the packet ( 58 ). 
         [0051]      FIG. 4  is a flowchart illustrating an exemplary operation of a control unit (e.g., control unit  20 ) of router  8 A that uses a distributed random walk technique to identify potentially infected host devices that are suspicious. Initially, line card correlation module  36  in control unit  20  requests copies of LC host tables  34  in line cards  24  ( 80 ). After requesting the copies of LC host tables  34 , line card correlation module  36  correlates LC host tables  34  into device host table  38  ( 82 ). As described above, to correlate LC host tables  34  into device host table  38 , line card correlation module  36  may create a host entry in device host table  38  for each unique host entry in LC host tables  34 . Line card correlation module  36  may then sum the source counters for each host entry in LC host tables  34  and sum the destination counters for each host entry in LC host tables  34  to derive source counters and destination counters for the host entries in device host table  38 . 
         [0052]    After correlating LC host tables  34  into device host table  38 , device correlation module  40  in control unit  20  may request copies of device host tables from each other one of routers  8  ( 84 ). After requesting the copies of device host tables from each other one of routers  8 , device correlation module  40  may correlate the device host tables into system host table  42  ( 86 ). As described above, device correlation module  40  correlates device host tables by creating a host entry in system host table  42  for each unique host entry in the device host tables. Device correlation module  40  then sums the source counters for each host entry in the device host tables and sums the destination counters for each host entry in the device host tables in system host table  42 . 
         [0053]    Once device correlation module  40  has correlated the device host tables into system host table  42 , threat identification module  44  determines whether a source counter in a first host entry of system host table  42  minus a destination counter of the first host entry of system host table  42  is greater than a first threshold ( 88 ). If the result of the source counter minus the destination counter is greater than the first threshold (“YES” of  88 ), traffic redirection module  46  instructs line cards  24  to update forwarding tables  32  such that line cards  24  forward packets from the host device specified by the first host entry to IDP device  10  ( 90 ). After traffic redirection module  46  sends the instructions to line cards  24 , threat identification module  44  compares source counters and destination counters of a second host entry in system host table  42 , and so on ( 92 ). 
         [0054]    On the other hand, if the result of the source counter minus the destination counter for the first host entry in system host table  42  is not greater than the first threshold (“NO” of  88 ), threat identification module  44  determines whether the source counter minus the destination counter for the first host entry is less than a second threshold ( 94 ). If threat identification module  44  determines that the source counter minus the destination counter for the first host entry is less than the second threshold (“YES” of  94 ), traffic redirection module  46  instructs line cards  24  to update forwarding tables  32  such that line cards  24  forward packets addressed to the host device specified by the first host entry to IDP device  10  ( 96 ). After instructing line cards  24  or if the source counter minus the destination counter is not less than the second threshold (“NO” of  94 ), threat identification module  44  compares source counters and destination counters for a second host entry in system host table  42 , and so on ( 92 ). 
         [0055]      FIG. 5  is a tabular diagram illustrating an exemplary configuration of LC host tables. The example of  FIG. 5  shows four LC host tables: LC host table  100 A, LC host table  100 B, LC host table  100 C, and LC host table  100 D. Collectively, these LC host tables may be referred to herein as LC host tables  100 . LC host table  100 A and LC host table  100 B may represent the LC host tables on a first one of routers  4  while LC host table  100 C and LC host table  100 D may represent the LC host tables on a second one of routers  4 . Each of LC host tables  100  includes a host column, a source counter column, a destination counter column and one or more rows. Each of the rows represents an entry in a LC host table. 
         [0056]    Each of the rows in LC host tables  100  are records of a number of network flows through a line card sourced by a host device and a number of network flows through the line card sent to the host device. For example, the host field of a row may contain a network address of a host device. The source counter field of a row may contain a count of network flows through a line card sourced by a host device specified by the network address of the host field of the row. The destination counter field of a row may contain a count of network flows through the line card sent to the host device specified by the network address of the host field of the row. For example, a host field of a first row of LC host table  100 A specifies the network address 207.142.131.284. The source counter field of the first row of LC host table  100 A specifies “45” as the number of flows through the line card that have specified the network address 207.142.131.284 as a source. The destination counter field of the first row of LC host table  100 A specifies “42” as the number of flows through the line card that have specified the network address 207.142.131.284 as a destination. 
         [0057]      FIG. 6  is a tabular diagram illustrating an exemplary configuration of device host tables. The example of  FIG. 6  shows two device host tables: device host table  110 A and device host table  110 B. Collectively, device host tables  110 A and  110 B may be referred to herein as device host tables  110 . Each of device host tables  110  includes a host column, a source counter column, a destination counter column, and one or more rows. 
         [0058]    Each of device host tables  110  contains a row for each unique host value in their respective set of LC host tables  100 . For example, device host table  110 A may contain a row for each row in LC host tables  100 A and  100 B; device host table  110 B may contain a row for each row in LC host tables  100 C and  100 D. For example, LC host table  100 A contains rows having host values 207.142.131.284, 207.142.131.040, and 207.142.085.079. LC host table  100 A contains rows having host values 56.123.078.254, 207.142.131.040, and 207.142.085.079. Because device host table  110 A contains a row for each row in device host tables  100 A and  100 B having a unique host value, device host table  100 A contains rows having host values 207.142.131.284, 207.142.131.040, 207.142.085.079, and 56.123.078.254. 
         [0059]    The source counter values of each row in device host tables  110  are sums of the source counter values of rows in their respective sets of LC host tables  100  with the same host values. For example, the source counter values of the row having host value 207.142.131.040 in device host table  110 A (i.e.,  230 ) is the sum of the source counter value of the row having host value 207.142.131.040 in LC host table  100 A (i.e.,  180 ) and the source counter value of the row having host value 207.142.131.040 in LC host table  100 B (i.e.,  50 ). 
         [0060]    Similarly, the destination counter values of each row in device host tables  110  are sums of the destination counter values of rows in their respective sets of LC host tables  100  with some host values. For example, the destination counter values of the row having host value 207.142.131.040 is device host tables  110 A (i.e.,  132 ) is the sum of the destination counter value of the row having host value 207.142.131.040 in LC host table  100 A (i.e.,  120 ) and the source counter value of the row having host value 207.142.131.040 in LC host table  100 B (i.e.,  12 ). 
         [0061]      FIG. 7  is a tabular diagram illustrating an exemplary configuration of a system host table  120 . Like LC host tables  100  and device host tables  110 , system host table  120  also includes a host column, a source counter column, a destination counter column, and one or more rows. 
         [0062]    System host table  120  contains a row for each row in device host tables  110  having a unique host value. For example, device host table  110 A includes rows having host values 207.142.131.284, 207.142.131.040, 207.142.085.079, and 56.123.078.254. Device host table  110 B includes rows having host values 142.43.121.284, 207.142.131.040, 207.142.085.079, and 56.123.078.254. Because system host table  120  contains a row for each row in device host tables  110  having a unique host value, system host table  120  contains rows having host values 207.142.131.284, 207.142.131.040, 207.142.085.079, 56.123.078.254, and 142.43.121.284. 
         [0063]    The source counter values of each row in system host table  120  are sums of the source counter values of rows in device host tables  110  having the same host values. For example, the source counter value of the row having host value 207.142.131.040 in system host table  120  (i.e.,  488 ) is the sum of the source counter value of the row having host value 207.142.131.040 in device host table  110 A (i.e.,  230 ) and the source counter value of the row having host value 207.142.131.040 in device host table  110 B (i.e.,  258 ). 
         [0064]    Similarly, the destination counter values of each row in system host table  120  are sums of the destination counter values of rows in device host tables  110  having the same host values. For example, the destination counter value of the row having host value 207.142.131.040 in system host table  120  (i.e.,  275 ) is the sum of the destination counter value of the row having host value 207.142.131.040 in device host table  100 A (i.e.,  132 ) and the destination value of the row having host value 207.142.131.040 in device host table  110 B (i.e.,  143 ). 
         [0065]      FIG. 8  is a graph representing an exemplary difference between a number of flows sourced by a host device and a number of flows sent to the host device over time. As illustrated in the example of  FIG. 8 , the vertical axis represents a difference between a number of network flows sourced by a host device and a number of flows sent to the same host device. For example, threat identification module  44  may calculate the difference by subtracting a number of flows sent to a host device from a number of flows sourced by the host device. The horizontal axis represents time. 
         [0066]    Short horizontal lines in  FIG. 8  represent the difference at a given time. For example, from time  1  to time  2 , the difference is +5. In other words, the host device has sourced five more flows than the host device has been sent. From time  2  to time  3 , the difference is −10. In other words, the host device has sourced negative ten more flows than the host device has been sent. This means the host device has been sent ten more flows than the host device has sourced. 
         [0067]    The exemplary graph of  FIG. 8  also shows a first and a second threshold. The first threshold may represent a difference at which threat identification module  44  considers the host device to be suspicious. The second threshold may represent a difference at which threat identification module  44  considers the host device to be under attack. For example, from time  11  to time  12 , the difference is +30. Because the difference of +30 is above the first threshold, threat identification module  44  may consider the host device to be suspicious. 
         [0068]    In other embodiments, threat identification module  44  may calculate the difference by subtracting the number of flows sourced by a host device from the number of flows sent to the host device. In these embodiments, positive differences in the exemplary graph of  FIG. 8  indicate that a host device has been sent more flows than the host device has sourced. The first threshold may therefore indicate a level at which threat identification module  44  may suspect that the host device is under attack. Similarly, negative differences in the exemplary graph of  FIG. 8  indicate that a host device has sourced more flows than the host device has been sent. The second threshold may therefore indicate a level at which threat identification module  44  may suspect that the host device is potentially infected. 
         [0069]    Various embodiments of the invention have been described. For example, the invention has been explained within the context of routers. Nevertheless, this is not the exclusive embodiment. For example, the invention may be implemented in firewall devices or otherwise. Furthermore, rather than using actual numbers of flows, approximate numbers of flows may be used. These and other embodiments are within the scope of the following claims.