Methods and systems to identify and reproduce concurrency violations in multi-threaded programs using expressions

• US 10,387,296 B2
• Filed: 08/26/2015
• Issued: 08/20/2019
• Est. Priority Date: 06/27/2012
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Wu, Youfeng, Gottschlich, Justin, Pokam, Gilles, Hu, Shiliang, Adl-Tabatabai, Ali-Reza, Pereira, Cristiano
• Primary Examiner(s): Rivera, Anibal
• Application Number:
  US14/836,103
• Publication Number:
  US 20150363306A1
• Time in Patent Office: 1,455 Days
• 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 which a plurality of threads of a computer program are responsible for causing a concurrency violation, the method comprising:

inserting, into a first thread of the computer program, a first instruction to determine a first predicate;

inserting, into a second thread of the computer program, a second instruction to determine a second predicate;

inserting, into the computer program, a concurrency violation detector, the concurrency violation detector to cause the concurrency violation to occur when a relationship between the first predicate and the second predicate is satisfied, the inserting of the concurrency violation detector to include globally defining, with a processor, a data type including;

the first predicate, the second predicate, and an expression defining the relationship as satisfied when the first and second predicates are satisfied in an order specified in the expression; and

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

2. The method defined in claim 1, wherein the order indicates that the first predicate is to be satisfied before the second predicate.

3. The method defined in claim 2, wherein the relationship specifies that, after the first predicate is satisfied, the first thread is to be stalled until the second predicate is satisfied.

4. The method defined in claim 1, wherein the relationship specifies that, if the first predicate is satisfied before the second predicate is satisfied, the first thread is to be stalled until the second predicate is satisfied, or, if the second predicate is satisfied before the first predicate is satisfied, the second thread is to be stalled until the first predicate is satisfied in the first thread.

5. The method 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 satisfied in the threshold number of the threads.

6. An apparatus to identify which of a plurality of threads of a computer program are responsible for causing a concurrency violation, the apparatus comprising:

memory including machine readable instructions;

at least one processor to execute the machine readable instructions to;

insert, into a first thread of the computer program, a first instruction to determine a first predicate;

insert, into a second thread of the computer program, a second instruction to determine a second predicate;

insert a concurrency violation detector into the computer program by globally defining a data type to include the first predicate, the second predicate, and an expression defining a relationship between the first and second predicates, the expression to be satisfied when the first and second predicates are satisfied in an order specified in the expression, the concurrency violation detector to cause the concurrency violation to occur based on the occurrence of the relationship between the first predicate and the second predicate;

execute the computer program including the concurrency violation detector; and

respond to an occurrence of the relationship during execution of the computer program, by identifying the first thread and the second thread as responsible for the concurrency violation.

7. The apparatus defined in claim 6, wherein the order specified in the relationship indicates that the first predicate is to be satisfied before the second predicate is satisfied.

8. The apparatus defined in claim 7, wherein the relationship specifies that, after the first predicate is satisfied, the first thread is to be stalled until a time at which the second predicate is satisfied.

9. The apparatus defined in claim 6, wherein the relationship specifies that the first predicate is to be satisfied a threshold number of times.

10. At least one machine readable storage medium comprising executable instructions which, when executed, cause at least one machine to at least:

insert, into a first thread of a computer program, a first instruction to determine a first predicate;

insert, into a second thread of the computer program, a second instruction to determine a second predicate;

monitor execution of the computer program; and

activate a concurrency violation detector in response to satisfaction of a relationship between the first predicate and the second predicate during the execution of the computer program, the relationship specified in a data type defined by the concurrency violation detector, the activation of the concurrency violation detector to cause a concurrency violation to occur, and the concurrency violation detector to identify the first thread and the second thread of the computer program as causing the concurrency violation, the data type specifying the first predicate, the second predicate, and an expression defining the satisfaction of the relationship as occurring when the first and second predicates are satisfied in an order specified in the expression.

11. The at least one machine readable storage medium defined in claim 10, wherein the machine readable instructions, when executed, further cause the at least one machine to determine whether the first predicate and the second predicate are satisfied in the order.

12. The at least one machine readable storage medium defined in claim 10, wherein the relationship specifies that, if the first predicate is satisfied, the first thread is to be stalled until the second predicate is satisfied, and wherein the machine readable instructions, when executed, further cause the at least one machine to:

stall the first thread when the first predicate is determined to be satisfied; and

halt execution of the computer program when the second predicate is satisfied.

13. The at least one machine readable storage medium defined in claim 10, wherein the relationship specifies that the first predicate is to be satisfied a threshold number of times, and wherein the machine readable instructions, when executed, further cause the at least one machine to:

increment a counter when the first predicate is satisfied;

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.

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