Large-scale network querying and reporting

• US 8,904,039 B1
• Filed: 04/12/2011
• Issued: 12/02/2014
• Est. Priority Date: 11/10/2008
• Status: Active Grant

• Current Assignee: Tanium Inc.
• Original Assignee: Tanium Inc.
• Inventors: Hindawi, Orion, Hindawi, David, Lincroft, Peter, Lippincott, Lisa
• Primary Examiner(s): Keehn, Richard G
• Application Number:
  US13/084,923
• Time in Patent Office: 1,330 Days
• Field of Search: 709/217, 709/243
• US Class Current: 709/243
• CPC Class Codes: H04L 12/6418 Hybrid transport

Abstract

A server receives “registration” messages from nodes in a network, sufficiently infrequently to prevent overburden. Registration messages include information about registering nodes, other nodes, or node relationships. The server sends “instruction” messages to registering nodes, requesting information about the network. Each registering node obtains the requested information, and forwards those messages to other nodes, which act similarly. Nodes receiving instruction messages sometimes send “reporting” messages to the server, providing information it originally requested. The server thus receives detailed information about the network, without communicating with too many nodes, and without aggregating too much of that information. The server can interact with users using only resources growing at O(1) with the size of the network.

Claims

1. A computer-implemented method, comprising:

at a server of a network comprising a non-static collection of machines;

receiving an information request through an interface provided by the server, the information request specifying a type of information to be collected from the non-static collection of machines;

in response to the information request, sending a request message to a first machine of a message propagation path formed by a plurality of machines currently coupled to the network,

wherein the request message specifies the type of information to be collected,

wherein the request message is propagated along the message propagation path from the first machine, through one or more intermediate machines of the message propagation path, to a second machine of the message propagation path, and

wherein, during the propagation of the request message from the first machine to the second machine, the request message accumulates respective local result information available to each machine along the message propagation path before being forwarded to a next machine along the message propagation path; and

receiving a report message from the second machine, wherein the report message is generated by the second machine based on at least the result information accumulated in the request message received by the second machine, wherein each of the first machine and the one or more intermediate machines has performed a statistical evaluation of the accumulated result information in the request message to determine whether to continue the propagation of the request message to another machine along the propagation path and to determine whether to report currently accumulated result information to the server.

2. The method of claim 1, further comprising:

at the server of the network;

receiving respective registration messages from each of the plurality of machines currently coupled to the network, wherein each of the plurality of machines is configured to send registration messages to the server at a respective frequency such that a load on the server has an upper bound limited to a constant with respect to a varying size of said network.

3. The method of claim 1, further comprising:

at the server of the network;

sending an instruction message to the first machine of the message propagation path formed by the plurality of machines currently coupled to the network, wherein the instruction message specifying (1) an action to be performed by a subset of the plurality of machines and (2) a criterion for selecting the subset of the plurality of machines, and wherein the instruction is propagated through each machine of the message propagation path, and each machine of the message propagation path receives the instruction message from a respective machine, if any, immediately preceding said each machine in the message propagation path, determines whether to perform the action based on whether the criterion is satisfied by said each machine, and forwards the instruction message to a respective machine, if any, immediately succeeding said each machine in the message propagation path.

4. The method of claim 3, wherein the instruction message is generated automatically, without user input, by the server.

5. The method of claim 3, wherein the instruction message is generated in response to user input.

6. The method of claim 1, wherein the request message includes a header, a termination code, and one or more elements of payload information, and wherein the payload information includes a hash code corresponding to a logical representation of the information request.

7. The method of claim 1, wherein the request message includes an indicator of a time to live (TTL) for the request message, the TTL being measured by a specified number of hops from machine to machine in the network.

8. A non-transitory computer-readable medium having instructions stored thereon, the instructions, when executed by one or more processors, cause the processors to perform operations comprising:

at a server of a network comprising a non-static collection of machines;

receiving an information request through an interface provided by the server, the information request specifying a type of information to be collected from the non-static collection of machines;

in response to the information request, sending a request message to a first machine of a message propagation path formed by a plurality of machines currently coupled to the network,

wherein the request message specifies the type of information to be collected,

wherein the request message is propagated along the message propagation path from the first machine, through one or more intermediate machines of the message propagation path, to a second machine of the message propagation path, and

wherein, during the propagation of the request message from the first machine to the second machine, the request message accumulates respective local result information available to each machine along the message propagation path before being forwarded to a next machine along the message propagation path; and

receiving a report message from the second machine, wherein the report message is generated by the second machine based on at least the result information accumulated in the request message received by the second machine, wherein each of the first machine and the one or more intermediate machines has performed a statistical evaluation of the accumulated result information in the request message to determine whether to continue the propagation of the request message to another machine along the propagation path and to determine whether to report currently accumulated result information to the server.

9. The computer-readable medium of claim 8, wherein the operations further comprise:

at the server of the network;

receiving respective registration messages from each of the plurality of machines currently coupled to the network, wherein each of the plurality of machines is configured to send registration messages to the server at a respective frequency such that a load on the server has an upper bound limited to a constant with respect to a varying size of said network.

10. The computer-readable medium of claim 8, wherein the operations further comprise:

at the server of the network;

sending an instruction message to the first machine of the message propagation path formed by the plurality of machines currently coupled to the network, wherein the instruction message specifying (1) an action to be performed by a subset of the plurality of machines and (2) a criterion for selecting the subset of the plurality of machines, and wherein the instruction is propagated through each machine of the message propagation path, and each machine of the message propagation path receives the instruction message from a respective machine, if any, immediately preceding said each machine in the message propagation path, determines whether to perform the action based on whether the criterion is satisfied by said each machine, and forwards the instruction message to a respective machine, if any, immediately succeeding said each machine in the message propagation path.

11. The computer-readable medium of claim 10, wherein the instruction message is generated automatically, without user input, by the server.

12. The computer-readable medium of claim 10, wherein the instruction message is generated in response to user input.

13. The computer-readable medium of claim 8, wherein the request message includes a header, a termination code, and one or more elements of payload information, and wherein the payload information includes a hash code corresponding to a logical representation of the information request.

14. The computer-readable medium of claim 8, wherein the request message includes an indicator of a time to live (TTL) for the request message, the TTL being measured by a specified number of hops from machine to machine in the network.

15. A server system of a network comprising a non-static collection of machines, comprising:

one or more processors; and

memory having instructions stored thereon, the instructions, when executed by the one or more processors, cause the processors to perform operations comprising;

receiving an information request through an interface provided by the server, the information request specifying a type of information to be collected from the non-static collection of machines;

in response to the information request, sending a request message to a first machine of a message propagation path formed by a plurality of machines currently coupled to the network,

wherein the request message specifies the type of information to be collected,

wherein the request message is propagated along the message propagation path from the first machine, through one or more intermediate machines of the message propagation path, to a second machine of the message propagation path, and

wherein, during the propagation of the request message from the first machine to the second machine, the request message accumulates respective local result information available to each machine along the message propagation path before being forwarded to a next machine along the message propagation path; and

receiving a report message from the second machine, wherein the report message is generated by the second machine based on at least the result information accumulated in the request message received by the second machine, wherein each of the first machine and the one or more intermediate machines has performed a statistical evaluation of the accumulated result information in the request message to determine whether to continue the propagation of the request message to another machine along the propagation path and to determine whether to report currently accumulated result information to the server.

16. The server system of claim 15, wherein the operations further comprise:

receiving respective registration messages from each of the plurality of machines currently coupled to the network, wherein each of the plurality of machines is configured to send registration messages to the server at a respective frequency such that a load on the server has an upper bound limited to a constant with respect to a varying size of said network.

17. The server system of claim 15, wherein the operations further comprise:

sending an instruction message to the first machine of the message propagation path formed by the plurality of machines currently coupled to the network, wherein the instruction message specifying (1) an action to be performed by a subset of the plurality of machines and (2) a criterion for selecting the subset of the plurality of machines, and wherein the instruction is propagated through each machine of the message propagation path, and each machine of the message propagation path receives the instruction message from a respective machine, if any, immediately preceding said each machine in the message propagation path, determines whether to perform the action based on whether the criterion is satisfied by said each machine, and forwards the instruction message to a respective machine, if any, immediately succeeding said each machine in the message propagation path.

18. The server system of claim 17, wherein the instruction message is generated automatically, without user input, by the server.

19. The server system of claim 17, wherein the instruction message is generated in response to user input.

20. The server system of claim 15, wherein the request message includes a header, a termination code, and one or more elements of payload information, and wherein the payload information includes a hash code corresponding to a logical representation of the information request.

21. The server system of claim 15, wherein the request message includes an indicator of a time to live (TTL) for the request message, the TTL being measured by a specified number of hops from machine to machine in the network.