Distributed system checker

• US 7,984,332 B2
• Filed: 11/17/2008
• Issued: 07/19/2011
• Est. Priority Date: 11/17/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Tang, Jian, Zhang, Lintao, Yang, Junfeng, Yang, Mao, Zhou, Lidong, Guo, Zhenyu, Liu, Xuezheng
• Primary Examiner(s): Baderman; Scott T
• Assistant Examiner(s): Patel; Kamini
• Application Number:
  US12/272,779
• Publication Number:
  US 20100125758A1
• Time in Patent Office: 974 Days
• Field of Search: 714/31
• US Class Current: 714/31
• CPC Class Codes: G06F 11/362 Software debugging

Abstract

A distributed system checker may check a distributed system against events to detect bugs in the distributed system. The events may include machines crashes, network partitions, and packet losses, for example. The distributed system checker may check a distributed system that can have multiple threads and multiple processes running on multiple nodes. To obtain control over a distributed system, a distributed system checker may insert an interposition layer between a process and the operating system on each node.

Claims

1. A system, comprising:

a distributed system comprising a plurality of nodes, each node running a process and an operating system and comprising an interposition layer provided between the process and the operating system; and

a distributed system checker in control over the distributed system via the interposition layer on each node.

2. The system of claim 1, wherein the interposition layer is provided on an application programming interface (API) between the process and the operating system on each node.

3. The system of claim 2, wherein the distributed system checker is in control over the distributed system at the API level.

4. The system of claim 1, wherein the interposition layer simulates a plurality of events to detect a bug in the distributed system.

5. The system of claim 4, wherein the plurality of events comprise at least one of a machine crash, a network partition, a message reorder, a message loss, or an application programming interface failure.

6. The system of claim 1, wherein the distributed system checker provides an unexpected event to the nodes via the interposition layer to check the distributed system.

7. The system of claim 1, wherein the distributed system checker separates system level control and application level state exploration in checking the distributed system for a bug.

8. The system of claim 1, wherein each node in the distributed system sends and receives a plurality of messages, each message associated with a state of the node.

9. The system of claim 1, wherein the distributed system checker determines a state signature of each process in the distributed system based on a plurality of messages of each process.

10. The system of claim 1, further comprising a bounding heuristic used in a checking of the distributed system, the bounding heuristic separating each of a plurality of actions that run on the distributed system into an internal state or an external state and bounding a number of internal states between a plurality of external states.

11. A method of checking a distributed system, comprising:

adding a plurality of state and action pairs to a queue;

performing one of the actions from the state and action pairs on the distributed system; and

detecting an error in the distributed system pursuant to performing the one of the actions.

12. The method of claim 11, further comprising spawning a plurality of processes in the distributed system to create an initial state prior to performing the one of the actions from the state and action pairs on the distributed system.

13. The method of claim 11, wherein performing the one of the actions results in an additional state, further comprising adding the additional state and at least one action associated with the additional state to the queue.

14. The method of claim 11, further comprising saving a trace of the action that brought the error to the distributed system.

15. The method of claim 11, wherein performing the one of the actions from the state and action pairs on the distributed system comprises providing the action to the distributed system via an interposition layer on the distributed system.

16. A method of checking a distributed system, comprising:

providing an interposition layer to a node in the distribution system on an application programming interface (API) between a process and an operating system on the node;

simulating an event on the node via the interposition layer; and

determining whether a bug occurs in the distributed system based on the event.

17. The method of claim 16, further comprising controlling the distributed system via the interposition layer.

18. The method of claim 17, wherein controlling the distributed system comprises determining a plurality of threads in the distributed system and determining whether each of the threads is enabled.

19. The method of claim 17, wherein controlling the distributed system comprises blocking a thread in the distributed system, scheduling the thread, sending a message to proceed to the thread, monitoring the thread by the interposition layer, and passing control to a distributed system checker via the interposition layer.

20. The method of claim 16, further comprising determining whether the event is an application event or a thread scheduling event, setting the event as an external state if the event is an application event, setting the event as an internal state if the event is a thread scheduling event, and if the event is set as the internal state then bounding the internal state with a plurality of external states.