Testing and Analysis of Concurrent Programs

Multi-core processors are now pervasive, spanning from embedded systems and mobile devices, to PCs, all the way to high-end servers and distributed systems. To unleash the computing power of multi-core processors, developers have to write concurrent (multi-threaded) programs. However, writing correct and efficient concurrent programs is difficult and error-prone.

An effective approach to verify the correctness of object-oriented concurrent classes consists of automatically generating concurrent tests and checking if they exhibit concurrency failures by exploring their interleaving spaces. A concurrent test consists of multiple concurrently executing threads that exercise the public interface of a class under test. The high cost of exploring interleaving spaces poses great challenges when generating concurrent tests.

During my PhD and Post-doc I proposed new techniques to effectively generate concurrent tests. Currently, I am working on fruther improve the effectiveness of concurrent test generators.

Related publications: [1, 2, 3, 4, 5]

1. ICST 2019
   Coverage-Driven Test Generation for Thread-Safe Classes via Parallel and Conflict Dependencies Valerio Terragni, Mauro Pezzè, Francesco Adalberto Bianchi In Proceedings of the 12th IEEE Conference on Software Testing, Validation and Verification , pages 264-275 , 2019 IEEE TCSE Distinguished Paper Award [BIBTEX] [Abstract] [PDF] [Slides] [DOI]

   Thread-safe classes are common in concurrent object-oriented programs. Testing such classes is important to ensure the reliability of the concurrent programs that rely on them. Recently, researchers have proposed the automated generation of concurrent (multi-threaded) tests to expose concurrency faults in thread-safe classes (thread-safety violations). However, generating fault-revealing concurrent tests within an affordable time-budget is difficult due to the huge search space of possible concurrent tests. In this paper, we present DEPCON, an approach to effectively reduce the search space of concurrent tests by means of both parallel and conflict dependency analyses. DEPCON is based on the intuition that only methods that can both interleave (parallel dependent) and access the same shared memory locations (conflict dependent) can lead to thread-safety violations when concurrently executed. DEPCON implements an efficient static analysis to compute the parallel and conflict dependencies among the methods of a class and uses the computed dependencies to steer the generation of tests towards concurrent tests that exhibit the computed dependencies. We evaluated DEPCON by experimenting with a prototype implementation for Java programs on a set of thread-safe classes with known concurrency faults. The experimental results show that DEPCON is more effective in exposing concurrency faults than state-of-theart techniques.

   @inproceedings{terragni-icst-2019, author = {Terragni, Valerio and Pezz{\`{e}}, Mauro and Bianchi, Francesco Adalberto}, title = {Coverage-Driven Test Generation for Thread-Safe Classes via Parallel and Conflict Dependencies}, booktitle = {12th {IEEE} Conference on Software Testing, Validation and Verification}, pages = {264-275}, year = {2019}, doi = {10.1109/ICST.2019.00034} }

2. ASE 2018
   Effectiveness and Challenges in Generating Concurrent Tests for Thread-Safe Classes Valerio Terragni, Mauro Pezzè In Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering , pages 64-75 , 2018 [BIBTEX] [Abstract] [PDF] [Slides] [DOI]

   Developing correct and efficient concurrent programs is difficult and error-prone, due to the complexity of thread synchronization. Often, developers alleviate such problem by relying on thread-safe classes, which encapsulate most synchronization-related challenges. Thus, testing such classes is crucial to ensure the reliability of the concurrency aspects of programs. Some recent techniques and corresponding tools tackle the problem of testing thread-safe classes by automatically generating concurrent tests. In this paper, we present a comprehensive study of the state-of-the-art techniques and an independent empirical evaluation of the publicly available tools. We conducted the study by executing all tools on the JaConTeBe benchmark that contains 47 well-documented concurrency faults. Our results show that 8 out of 47 faults (17%) were detected by at least one tool. By studying the issues of the tools and the generated tests, we derive insights to guide future research on improving the effectiveness of automated concurrent test generation.

   @inproceedings{terragni-ase-2018, author = {Terragni, Valerio and Pezz{\`{e}}, Mauro}, title = {Effectiveness and Challenges in Generating Concurrent Tests for Thread-Safe Classes}, booktitle = {33rd {ACM/IEEE} International Conference on Automated Software Engineering}, pages = {64-75}, doi = {10.1145/3238147.3238224}, year = {2018} }

3. ESEC/ FSE 2017
   Reproducing Concurrency Failures from Crash Stacks Francesco A. Bianchi, Mauro Pezzè, Valerio Terragni (Authors are listed alphabetically) In Proceedings of the 11th Joint Meeting on Foundations of Software Engineering , pages 705-716 , 2017 [BIBTEX] [Abstract] [PDF] [Slides] [Replication Package] [DOI]

   Reproducing field failures is the first essential step for understanding, localizing and removing faults. Reproducing concurrency field failures is hard due to the need of synthesizing a test code jointly with a thread interleaving that induce the failure in the presence of limited information from the field. Current techniques for reproducing concurrency failures focus on identifying failure-inducing interleavings, leaving largely open the problem of synthesizing the test code that manifests such interleavings. In this paper, we present ConCrash, a technique to automatically generate test codes that reproduce concurrency failures that violate thread-safety from crash stacks, which commonly summarize the conditions of field failures. ConCrash efficiently explores the huge space of possible test codes to identify a failure-inducing one by using a suitable set of search pruning strategies. Combined with existing techniques for exploring interleavings, ConCrash automatically reproduces a given concurrency failure that violates the thread-safety of a class by identifying both a failure-inducing test code and corresponding interleaving. In the paper, we define the ConCrash approach, present a prototype implementation of ConCrash, and discuss the experimental results that we obtained on a known set of ten field failures that witness the effectiveness of the approach.

   @inproceedings{bianchi-fse-2017, author = {Bianchi, Francesco A. and Pezz{\`{e}}, Mauro and Terragni, Valerio}, title = {Reproducing Concurrency Failures from Crash Stacks}, booktitle = {11th Joint Meeting on Foundations of Software Engineering}, pages = {705-716}, year = {2017}, doi = {10.1145/3106237.3106292} }

4. ICSE 2016
   Coverage-driven Test Code Generation for Concurrent Classes Valerio Terragni, Shing-Chi Cheung In Proceedings of the 38th ACM/IEEE International Conference on Software Engineering , pages 1121-1132 , 2016 [BIBTEX] [Abstract] [PDF] [Slides] [DOI]

   Previous techniques on concurrency testing have mainly focused on exploring the interleaving space of manually written test code to expose faulty interleavings of shared memory accesses. These techniques assume the availability of failure-inducing tests. In this paper, we present AutoConTest, a coverage-driven approach to generate effective concurrent test code that achieve high interleaving coverage. AutoConTest consists of three components. First, it computes the coverage requirements dynamically and iteratively during sequential test code generation, using a coverage metric that captures the execution context of shared memory accesses. Second, it smartly selects these sequential codes based on the computed result and assembles them for concurrent tests, achieving increased context-sensitive interleaving coverage. Third, it explores the newly covered interleavings. We have implemented AutoConTest as an automated tool and evaluated it using 6 real-world concurrent Java subjects. The results show that AutoConTest is able to generate effective concurrent tests that achieve high interleaving coverage and expose concurrency faults quickly. AutoConTest took less than 65 seconds (including program analysis, test generation and execution) to expose the faults in the program subjects.

   @inproceedings{terragni-icse-2016, author = {Terragni, Valerio and Cheung, Shing{-}Chi}, title = {Coverage-driven Test Code Generation for Concurrent Classes}, booktitle = {38th {ACM/IEEE} International Conference on Software Engineering}, pages = {1121-1132}, year = {2016}, doi = {10.1145/2884781.2884876} }

5. ICSE 2015
   RECONTEST: Effective Regression Testing of Concurrent Programs Valerio Terragni, Shing-Chi Cheung, Charles Zhang In Proceedings of the 37th IEEE/ACM International Conference on Software Engineering , pages 246–256 , 2015 [BIBTEX] [Abstract] [PDF] [Slides] [DOI]

   Concurrent programs proliferate as multi-core technologies advance. As a result, the conventional approach that selects a sub-set of test cases for regression testing without considering interleavings is insufficient. In this paper we present RECONTEST to address the problem by selecting the new interleavings that arise due to code changes. These interleavings must be explored in order to uncover regression bugs. RECONTEST efficiently selects new interleavings by first identifying shared memory accesses that are affected by the changes, and then exploring only those problematic interleavings that contain at least one of these accesses. We have implemented RECONTEST as an automated tool and evaluated it using 13 real-world concurrent program subjects. Our results show that RECONTEST can significantly reduce the regression testing cost without missing any faulty interleavings induced by code changes.

   @inproceedings{terragni-icse-2015, author = {Terragni, Valerio and Cheung, Shing{-}Chi and Zhang, Charles}, title = {{RECONTEST:} Effective Regression Testing of Concurrent Programs}, booktitle = {37th {IEEE/ACM} International Conference on Software Engineering}, pages = {246--256}, year = {2015}, doi = {10.1109/ICSE.2015.45} }