Systems and methods for determining the network topology of a network

• US 7,317,693 B1
• Filed: 05/12/2004
• Issued: 01/08/2008
• Est. Priority Date: 05/12/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Sourcefire Incorporated (Cisco Systems, Inc.)
• Inventors: Roesch, Martin, Vogel, William Andrew III
• Primary Examiner(s): Pezzlo; John
• Application Number:
  US10/843,376
• Time in Patent Office: 1,336 Days
• Field of Search: 370/252, 370254-258, 370/386, 370/469, 370/338, 709223-226
• US Class Current: 370/252
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/18 Protocol analysers

Abstract

A packet transmitted on a network is read and decoded. A network device and its operating system are identified by analyzing the decoded packet. If more than one operating system is identified from the decoded packet, the operating system is selecting by comparing confidence values assigned to the operating systems identified. A service running on the network device is identified from the decoded packet or subsequent packets that are read, decoded and analyzed. The network topology of a network is determined by reading, decoding, and analyzing a plurality of packets. A flow between two network devices is determined by reading, decoding, and analyzing a plurality of packets. Vulnerabilities are assigned to operating systems and services identified by reading, decoding, and analyzing packets. Network configuration policy is enforced on operating systems and services identified by reading, decoding, and analyzing packets.

Claims

1. A method for passively and automatically identifying a router on a network, comprising:

reading a first packet transmitted on the network;

decoding the first packet into a first plurality of protocol fields;

identifying a first one of address resolution protocol and dynamic host configuration protocol from the first plurality of protocol fields;

identifying a first Internet protocol address and a first primary media access control address from the first one of address resolution protocol and dynamic host configuration protocol;

reading a second packet transmitted on the network;

decoding the second packet into a second plurality of protocol fields;

identifying a second one of address resolution protocol and dynamic host configuration protocol from the second plurality of protocol fields;

identifying a second Internet protocol address and a second primary media access control address from the second one of address resolution protocol and dynamic host configuration protocol;

reading a third packet transmitted on the network;

decoding the third packet into a third plurality of protocol fields;

identifying an Internet protocol address and a media access control address from the third plurality of protocol fields; and

if the Internet protocol address comprises the second Internet protocol address and the media access control address comprises the first primary media access control address, then identifying an initiator of the first packet as the router.

2. The method of claim 1, wherein the first plurality of protocol fields comprises two or more of a network protocol field, a transport protocol field, and an application protocol field.

3. The method of claim 1, wherein the second plurality of protocol fields comprises two or more of a network protocol field, a transport protocol field, and an application protocol field.

4. The method of claim 1, wherein the third plurality of protocol fields comprises a network protocol field.

5. A method for passively and automatically identifying a router on a network, comprising:

reading a first packet transmitted on the network;

decoding the first packet into a first plurality of protocol fields;

identifying a first one of address resolution protocol and dynamic host configuration protocol from the first plurality of protocol fields;

identifying a first Internet protocol address and a first primary media access control address from the first one of address resolution protocol and dynamic host configuration protocol;

reading a second packet transmitted on the network;

decoding the second packet into a second plurality of protocol fields;

identifying an Internet protocol address and a media access control address from the second plurality of protocol fields, wherein the Internet protocol address does not comprise the first Internet protocol address and the media access control address comprises the first primary media access control address;

determining a number of hops traveled by the second packet from the second plurality of protocol fields; and

if the number of hops is not equal to zero, identifying an initiator of the first packet as the router.

6. The method of claim 5, wherein the first plurality of protocol fields comprises two or more of a network protocol field, a transport protocol field, and an application protocol field.

7. The method of claim 5, wherein the second plurality of protocol fields comprises two or more of a network protocol field, a transport protocol field, and an application protocol field.

8. The method of claim 5, wherein determining the number of hops comprises:

comparing the second plurality of protocol fields to an operating system identifying structure;

selecting a matched operating system;

reading a default starting time-to-live value for the matched operating system from the operating system identifying structure;

reading a packet time-to-live value from the second plurality of protocol fields; and

calculating the number of hops by comparing the default starting time-to-live value to the packet time-to-live value.

9. A method for passively and automatically identifying a subnet on a network, comprising:

reading a first packet transmitted on the network;

decoding the first packet into a first plurality of protocol fields;

identifying a first one of address resolution protocol and dynamic host configuration protocol from the first plurality of protocol fields;

identifying a first Internet protocol address and a first primary media access control address from the first one of address resolution protocol and dynamic host configuration protocol;

reading a second packet transmitted on the network;

decoding the second packet into a second plurality of protocol fields;

identifying a second one of address resolution protocol and dynamic host configuration protocol from the second plurality of protocol fields;

identifying a second Internet protocol address and a second primary media access control address from the second one of address resolution protocol and dynamic host configuration protocol;

reading a third packet transmitted on the network;

decoding the third packet into a third plurality of protocol fields;

identifying a source Internet protocol address, a source media access control address, a destination Internet protocol address, and a destination media access control address from the third plurality of protocol fields; and

if the source Internet protocol address comprises the first Internet protocol address, the source media access control address comprises the first primary media access control address, the destination Internet protocol address comprises the second Internet protocol address, and the destination media access control address comprises the second primary media access control address, then identifying a network encompassing an initiator of the first packet and an initiator of the second packet as the subnet.

10. The method of claim 9, wherein the first plurality of protocol fields comprises two or more of a network protocol field, a transport protocol field, and an application protocol field.

11. The method of claim 9, wherein the second plurality of protocol fields comprises two or more of a network protocol field, a transport protocol field, and an application protocol field.

12. The method of claim 9, wherein the third plurality of protocol fields comprises a network protocol field.

13. The method of claim 9, further comprising calculating a smallest address space for the subnet from the first Internet protocol address and the second Internet protocol address.

14. The method of claim 13, wherein calculating the smallest address space comprises:

performing a bitwise exclusive-OR operation with the first Internet protocol address and the second Internet protocol address to produce an intermediate result;

calculating a network mask of the subnet by counting the significant bits of the intermediate result;

selecting one of the first Internet protocol address and the second Internet protocol address and performing a bitwise AND operation with the network mask to produce a network number; and

defining the smallest address space as the network mask and the network number.

15. The method of claim 13, further comprising expanding the smallest address space for the subnet by identifying an additional host on the subnet and using the additional host'"'"'s address to expand the smallest address space for the subnet.

16. The method of claim 15, wherein expanding the smallest address space for the subnet by identifying an additional host on the subnet and using the additional host'"'"'s address to expand the smallest address space for the subnet comprises:

reading a fourth packet transmitted on the network;

decoding the fourth packet into a fourth plurality of protocol fields;

identifying a fourth one of address resolution protocol and dynamic host configuration protocol from the fourth plurality of protocol fields;

identifying a fourth Internet protocol address and a fourth primary media access control address from the fourth one of address resolution protocol and dynamic host configuration protocol;

reading a fifth packet transmitted on the network;

decoding the fifth packet into a fifth plurality of protocol fields;

identifying a second source Internet protocol address, a second source media access control address, a second destination Internet protocol address, and a second destination media access control address from the fifth plurality of protocol fields; and

if the second source Internet protocol address comprises the first Internet protocol address, the second source media access control address comprises the first primary media access control address, the second destination Internet protocol address comprises the fourth Internet protocol address, and the second destination media access control address comprises the fourth primary media access control address, then expanding the smallest address space of the subnet to comprise an initiator of the fourth packet.

17. The method of claim 15, wherein expanding the smallest address space for the subnet by identifying an additional host on the subnet and using the additional host'"'"'s address to expand the smallest address space for the subnet comprises:

reading a fourth packet transmitted on the network;

decoding the fourth packet into a fourth plurality of protocol fields;

identifying a fourth one of address resolution protocol and dynamic host configuration protocol from the fourth plurality of protocol fields;

identifying a fourth Internet protocol address and a fourth primary media access control address from the fourth one of address resolution protocol and dynamic host configuration protocol;

reading a fifth packet transmitted on the network;

decoding the fifth packet into a fifth plurality of protocol fields;

identifying a second source Internet protocol address, a second source media access control address, a second destination Internet protocol address, and a second destination media access control address from the fifth plurality of protocol fields;

if the second source Internet protocol address comprises the second Internet protocol address, the second source media access control address comprises the second primary media access control address, the second destination Internet protocol address comprises the fourth Internet protocol address, and the second destination media access control address comprises the fourth primary media access control address, then expanding the smallest address space of the subnet to contain an initiator of the fourth packet.

18. A method for passively and automatically determining a distance between a first subnet and a second subnet on a network, comprising:

identifying a network device with a network device Internet protocol address, a network device primary media access control address, and a network device time-to-live value on the first subnet;

identifying a router with a router Internet protocol address and a router primary media access control address on the second subnet;

reading a packet transmitted on the network;

decoding the packet into a plurality of protocol fields;

identifying a source Internet protocol address, a source media access control address, a destination Internet protocol address, and a packet time-to-live value from the plurality of protocol fields; and

if the source Internet protocol address comprises the network device Internet protocol address, the source media access control address comprises the router primary media access control address, and the destination Internet protocol address is within an address space of the second subnet, then determining the distance as the difference between the network device time-to-live value and the packet time-to-live value.

19. The method of claim 18, wherein identifying the network device with the network device Internet protocol address, the network device primary media access control address, and the network device time-to-live value on the first subnet comprises:

reading a first packet transmitted on the network;

decoding the first packet into a first plurality of first protocol fields;

identifying a first one of address resolution protocol and dynamic host configuration protocol from the first plurality of protocol fields;

identifying a first Internet protocol address and a first primary media access control address from the first one of address resolution protocol and dynamic host configuration protocol;

identifying a first time-to-live value from the first plurality of protocol fields; and

if an address space of the first subnet encompasses the first Internet protocol address, then determining that the network device Internet protocol address comprises the first Internet protocol address, the network device primary media access control address comprises the first primary media access control address, and the network device time-to-live value comprises the first time-to-live value.

20. A method for passively and automatically creating an inferred subnet on a network, comprising:

identifying a router with a router Internet protocol address and a router primary media access control address on a known subnet;

reading a packet transmitted on the network;

decoding the packet into a plurality of protocol fields;

identifying a source Internet protocol address, a source media access control address, and a destination Internet protocol address from the plurality of protocol fields; and

if the address space of the known subnet does not encompass the source Internet protocol address, the source media access control address comprises the router primary media access control address, and the destination Internet protocol address is within an address space of the known subnet, then creating the inferred subnet and adding the source Internet protocol address to the inferred subnet.

21. The method of claim 20, further comprising setting an initial mask of the subnet to 255.255.255.255.

22. The method of claim 20, further comprising:

comparing the plurality of protocol fields to an operating system identifying data structure;

selecting a matched operating system;

reading a default time-to-live value for the matched operating system from the operating system identifying data structure;

reading a packet time-to-live value from the plurality of protocol fields;

calculating a distance between the inferred subnet and the known subnet from the difference between the default time-to-live value and the packet time-to-live value; and

determining an inferred subnet based on the distance.