Method to efficiently trigger concurrency bugs based on expected frequencies of execution interleavings

Patent metadata

Field	Value
Publication number	US-10191833-B2
Application number	US-201514961504-A
Country	US
Kind code	B2
Filing date	Dec 7, 2015
Priority date	Dec 7, 2015
Publication date	Jan 29, 2019
Grant date	Jan 29, 2019

Abstract

A method includes determining a set of shared memory access instructions and execution frequencies and selecting one or more groups of instructions that access a same memory location. The method also includes finding pairs of instructions from each group, for which another access to the same memory location may occur between execution of the instructions in the pair, and estimating a probability that a data race may occur using a time gap between the instructions and the execution frequencies, and generating a list of instruction tuples that include the pair of instructions. The method includes calculating a score for each instruction in the tuples, the score representing a likelihood of triggering a data race by injecting a delay before an instruction. The method includes selecting instructions having a score indicating a lower than a threshold probability that the instruction will comprise a last access of a data race.

First claim

We claim:

1. A method for triggering concurrency bugs, comprising:
determining a set of shared memory access instructions of a program using binary analysis of the program;
determining, during runtime, an execution frequency, memory access time, and location of memory accessed for each shared memory access instruction in the set of shared memory access instructions;
selecting, from the set of shared memory access instructions, one or more groups of instructions, wherein each instruction in the group accesses a same memory location as other instructions in its group;
finding pairs of instructions from each group that access the same memory location from a first thread and finding instructions that access the same memory location from another thread, and estimating for each pair of instructions a probability that a data race may occur using an average time gap between the instructions in the pair and the execution frequencies;
generating a list of instruction tuples, wherein each tuple includes the pair of instructions from the first thread, the instructions that access the same memory location from another thread, and the average time gap;
calculating a score for each instruction pair in the list using the instruction tuples, wherein calculating the score comprises calculating a score based at least in part on the average time gap and an exponential of a frequency of the instruction that accesses the same memory location from another thread, a n d wherein the score represents a likelihood of triggering a data race by injecting a delay before an instruction in the tuple;
selecting instructions from scored instructions, each selected instruction having a score indicating a lower than a threshold score that the instruction will comprise a last access of a data race;
injecting a delay before a selected instruction in the tuple; and
executing the program with the injected delay to trigger a data race in the instructions to identify a low probability bug.

2. The method of claim 1 , wherein injecting the delay further comprises:
injecting the delay to increase the average time gap between accesses of the shared memory location by the pair of instructions, wherein injecting the delay increases the probability that a third instruction accesses the same memory location between accesses of the same memory location by the pair of instructions.

3. The method of claim 1 , wherein an average time gap is determined by determining an average time spent between accesses of the same memory location over a period of measurement.

4. The method of claim 1 , wherein an average time gap is determined by determining an average or minimal time gap of multiple accesses of the same memory location by the pair of instructions.

5. The method of claim 1 , wherein selecting one or more groups of shared memory access instructions comprises observing a range of memory locations accessed by each instruction in a first set of shared memory access instructions and determining if two or more ranges overlap.

6. A non-transitory computer-readable storage medium containing a program which, when executed by one or more processors, performs operations for scheduling computing resources, the operations comprising:
determining a set of shared memory access instructions of a program using binary analysis of the program;
determining, during runtime, an execution frequency, memory access time, and location of memory accessed for each shared memory access instruction in the set of shared memory access instructions;
selecting, from the set of shared memory access instructions, one or more groups of instructions, wherein each instruction in the group accesses a same memory location as other instructions in its group;
finding pairs of instructions from each group that access the same memory location from a first thread and finding instructions that access the same memory location from another thread, and estimating for each pair of instructions a probability that a data race may occur using an average time gap between the instructions in the pair and the execution frequencies;
generating a list of instruction tuples, wherein each tuple includes the pair of instructions from the first thread, the instructions that access the same memory location from another thread, and the average time gap;
calculating a score for each instruction pair in the list using the instruction tuples, wherein calculating the score comprises calculating a score based at least in part on the average time gap and an exponential of a frequency of the instruction that accesses the same memory location from another thread, and wherein the score represents a likelihood of triggering a data race by injecting a delay before an instruction in the tuple;
selecting instructions from scored instructions, each selected instruction having a score indicating a lower than a threshold score that the instruction will comprise a last access of a data race; and
injecting a delay before a selected instruction in the tuple; and
executing the program with the injected delay to trigger a data race in the instructions to identify a low probability bug.

7. The non-transitory computer-readable storage medium of claim 6 , wherein injecting the delay further comprises:
injecting the delay to increase the average time gap between accesses of the shared memory location by the pair of instructions, wherein injecting the delay increases the probability that a third instruction accesses the same memory location between accesses of the same memory location by the pair of instructions.

8. The non-transitory computer-readable storage medium of claim 6 , wherein an average time gap is determined by determining an average time spent between accesses of the same memory location over a period of measurement.

9. The non-transitory computer-readable storage medium of claim 6 , wherein an average time gap is determined by determining an average or minimal time gap of multiple accesses of the same memory location by the pair of instructions.

10. The non-transitory computer-readable storage medium of claim 6 , wherein selecting one or more groups of shared memory access instructions comprises observing a range of memory locations accessed by each instruction in a first set of shared memory access instructions and determining if two or more ranges overlap.

11. A system, comprising:
a processor; and a memory, wherein the memory includes a program executable in the processor to perform operations for scheduling computing resources, the operations comprising:
determining a set of shared memory access instructions of a program using binary analysis of the program;
determining, during runtime, an execution frequency, memory access time, and location of memory accessed for each shared memory access instruction in the set of shared memory access instructions;
selecting, from the set of shared memory access instructions, one or more groups of instructions, wherein each instruction in the group accesses a same memory location as other instructions in its group;
finding pairs of instructions from each group that access the same memory location from a first thread and finding instructions that access the same memory location from another thread, and estimating for each pair of instructions a probability that a data race may occur using an average time gap between the instructions in the pair and the execution frequencies;
generating a list of instruction tuples, wherein each tuple includes the pair of instructions from the first thread, the instructions that access the same memory location from another thread, and the average time gap;
calculating a score for each instruction pair in the list using the instru

Assignees

• Vmware Inc

Inventors

• Chen Bo
• Chen Hao

Classifications

• G06F11/3632 Primary

  of specific synchronisation aspects · CPC title