Exposing concurrency failures - A comprehensive survey of the state of the art and a novel approach to reproduce field failures

Decanato - Facoltà di scienze informatiche

Data: 26 Ottobre 2018 / 09:30 - 11:00

USI Lugano Campus, room A-22, red building (Via G. Buffi 13)

You are cordially invited to attend the PhD Dissertation Defense of Francesco BIANCHI on Friday, October 26th, 2018 at 9h30 in room A-22 (red building)

 

Abstract:

With the rapid advance of multi-core and distributed architectures, concurrent systems are becoming more and more popular. Concurrent systems are extremely hard to develop and validate, as their overall behavior depends on the non- deterministic interleaving of the execution flows that comprise the system. Wrong and unexpected interleavings may lead to concurrency faults that are extremely hard to avoid, detect, and fix due to their non-deterministic nature.

This thesis addresses the problem of exposing concurrency failures. Exposing concurrency failures is a crucial activity to locate and fix the related fault and amounts to determine  both a test case and an interleaving that trigger the failure. Given the high cost of manually identifying a failure-inducing test case and interleaving among the infinite number of inputs and interleavings of the system, the problem of automatically exposing concurrency failures has been studied by researchers since the late seventies and is still a hot research topic.

This thesis advances the research in exposing concurrency failures by proposing two main contributions. The first contribution is a comprehensive survey and taxonomy of the state-of-the-art techniques for exposing concurrency failures. The taxonomy and survey provide a framework that captures the key features of the existing techniques, identify a set of classification criteria to review and compare them, and highlight their strengths and weaknesses, leading to a thorough assessment of the field and paving the road for future progresses.

The second contribution of this thesis is a technique to automatically expose and reproduce concurrency field failure. One of the main findings of our survey is that automatically reproducing concurrency field failures is still an open problem, as the few techniques that have been proposed rely on information that may be hard to collect, and identify failure-inducing interleavings but do not synthesize failure-inducing test cases. We propose a technique that advances over state-of-the-art approaches by relying on information that is easily obtainable  and by automatically identifying both a failure-inducing test case and interleaving. We empirically demonstrate the effectiveness of our approach on a benchmark of real concurrency failures taken from different popular code bases.

 

Dissertation Committee:

  • Prof. Mauro Pezzè, Università della Svizzera italiana, Switzerland (Research Advisor)
  • Prof. Matthias Hauswirth, Università della Svizzera italiana, Switzerland (Internal Member)
  • Prof. Michele Lanza, Università della Svizzera italiana, Switzerland (Internal Member)
  • Prof. Antonia Bertolino, CNR, Italy (External Member)
  • Prof. Michael Pradel, TU Darmstadt, Germany (External Member)

Facoltà