METHODS AND SYSTEMS TO IDENTIFY AND REPRODUCE CONCURRENCY VIOLATIONS IN MULTI-THREADED PROGRAMS USING EXPRESSIONS

• US 20150363306A1
• Filed: 08/26/2015
• Published: 12/17/2015
• Est. Priority Date: 06/27/2012
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Wu, Youfeng, Pokam, Gilles, Hu, Shiliang, Adl-Tabatabai, Ali-Reza, Gottschlich, Justin
• Granted Patent: US 10,387,296 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/36 Preventing errors by testing or debugging software
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466
• CPC Class Codes: G06F 11/3632 of specific synchronisation aspects
• CPC Class Codes: G06F 11/3636 by tracing the execution of the program
• CPC Class Codes: G06F 11/3672 Test management
• CPC Class Codes: G06F 11/3688 for test execution, e.g. scheduling of test suites
• CPC Class Codes: G06F 8/434 Pointers; Aliasing
• CPC Class Codes: G06F 8/70 Software maintenance or management
• CPC Class Codes: G06F 9/448 Execution paradigms, e.g. implementations of programming paradigms

Abstract

Methods and systems to identify threads responsible for causing a concurrency bug in a computer program having a plurality of concurrently executing threads are disclosed. An example method disclosed herein includes defining, with a processor, a data type. The data type including a first predicate, the first predicate being invoked using a first program instruction inserted in a first thread of the plurality of threads, a second predicate, the second predicate being invoked using a second program instruction inserted in a second thread of the plurality of threads, and an expression defining a relationship between the first predicate and the second predicate. The method further includes, in response to determining the relationship is satisfied during execution of the computer program, identifying the first thread and the second thread as responsible for the concurrency bug.

Claims

1. A method to identify threads responsible for causing a concurrency bug in a computer program having a plurality of concurrently executing threads, the method comprising:

defining, with a processor, a data type including;

a first predicate, the first predicate being invoked using a first program instruction inserted in a first thread of the plurality of threads;

a second predicate, the second predicate being invoked using a second program instruction inserted in a second thread of the plurality of threads; and

an expression defining a relationship between the first predicate and the second predicate;

in response to determining the relationship is satisfied during execution of the computer program, identifying the first thread and the second thread as responsible for the concurrency bug.

2. A method as defined in claim 1, wherein the relationship defines an order in which the first and second predicates are to be met.

3. A method as defined in claim 2, wherein the order indicates that the first predicate is to be met before the second predicate.

4. A method as defined in claim 3, wherein the relationship specifies that, after the first predicate is met, the first thread is to be stalled until the second predicate is met.

5. A method as defined in claim 1, wherein the relationship specifies that, if the first predicate is met before the second predicate is met, the first thread is stalled until the second predicate is met, or, if the second predicate is met before the first predicate, the second thread is stalled until the first predicate is met in the first thread.

6. A method as defined in claim 1, wherein the relationship specifies that either the first predicate or the second predicate is to be met.

7. A method as defined in claim 1, wherein the relationship specifies that the first predicate is to be met a threshold number of times.

8. A method as defined in claim 1, wherein the first predicate is invoked in a threshold number of the plurality of threads, and the relationship specifies that the first predicate is to be concurrently met in the threshold number of threads.

9. An apparatus to identify threads responsible for causing a concurrency bug in a computer program having a plurality of concurrently executing threads, the apparatus comprising:

a memory to store machine readable instructions and a data type definition, the data type definition specifying;

a first program instruction invoking a first predicate, the first program instruction to be inserted into a first thread of the plurality of threads;

a second program instruction invoking a second predicate, the second program instruction to be inserted into a second thread of the plurality of threads;

an expression defining a relationship between the first predicate and the second predicate; and

a processor to execute the machine readable instructions to respond to an occurrence of the relationship being satisfied during execution of the computer program, by identifying the first thread and the second thread as responsible for the concurrency bug.

10. An apparatus as defined in claim 9, wherein the relationship specifies an order in which the first and second predicates are to be met.

11. An apparatus as defined in claim 10, wherein the order specified in the relationship indicates that the first predicate is to be met before the second predicate is met.

12. An apparatus as defined in claim 11, wherein the relationship specifies that, after the first predicate is met, the first thread is to be stalled until a time at which the second predicate is met.

13. An apparatus as defined in claim 9, wherein the relationship specifies that the first predicate is to be met a threshold number of times.

14. A machine readable storage medium comprising instructions which, when executed, cause a machine to at least:

monitor execution of a computer program having a plurality of concurrently executing threads; and

identify a first thread and a second thread of the plurality of threads as causing a concurrency bug, when a relationship specified in a data type is satisfied during execution of the computer program, the data type specifying;

a first predicate, the first predicate being invoked using a first program instruction in the first thread of the computer program;

a second predicate, the second predicate being invoked using a second program instruction in the second thread of the plurality of threads; and

an expression defining the relationship between the first predicate and the second predicate.

15. A machine readable storage medium as defined in claim 14, wherein the relationship defines a specific order in which the first and second predicates are to be met and wherein the machine readable instructions, when executed, further cause the machine to:

determine whether the first predicate and the second predicate are met in the specific order.

16. A machine readable storage medium as defined in claim 14, wherein the relationship specifies that, if the first predicate is met, the first thread is to be stalled until the second predicate is met and wherein the machine readable instructions, when executed, further cause the machine to:

to stall the first thread if the first predicate is determined to be met; and

to halt execution of the computer program if the second predicate is met.

17. A machine readable storage medium as defined in claim 14, wherein the relationship specifies that the first predicate is to be met a threshold number of times and wherein the machine readable instructions, when executed, further cause the machine to:

increment a counter when the first predicate is met;

determine whether the counter is equal to the threshold number; and

if the counter is equal to the threshold number, determine that the relationship is satisfied.

18. A machine readable storage medium as defined in claim 14, wherein the first program instruction is inserted into a first set of the plurality of threads, the first set containing at least a threshold number of threads, the relationship specifies that the first predicate is to be met in the threshold number of threads concurrently, and the machine readable instructions, when executed, further cause the machine to determine that the relationship is satisfied if the first predicate is met in the threshold number of threads concurrently.