All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Checking Just Pairs of Threads for Efficient and Scalable Incremental Verification of Multithreaded Programs

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10447448" target="_blank" >RIV/00216208:11320/23:10447448 - isvavai.cz</a>

  • Result on the web

    <a href="https://doi.org/10.1145/3573074.3573082" target="_blank" >https://doi.org/10.1145/3573074.3573082</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1145/3573074.3573082" target="_blank" >10.1145/3573074.3573082</a>

Alternative languages

  • Result language

    angličtina

  • Original language name

    Checking Just Pairs of Threads for Efficient and Scalable Incremental Verification of Multithreaded Programs

  • Original language description

    Many techniques of automated verification target multithreaded programs, because subtle interactions between threads may trigger concurrency errors such as deadlocks and data races. However, techniques and tools involving systematic exploration of the whole space of possible thread interleavings do not scale to large software systems, despite various clever algorithmic optimizations. A viable approach is to use incremental verification techniques that, in each run, focus just on the recently modified code and the relatively small number of affected execution traces, and therefore can provide results (bug reports) very quickly.In this paper we present a new algorithm for incremental verification of multithreaded programs based on the pairwise approach, whose key idea is systematic exploration of all possible thread interleavings just for specific relevant pairs of threads.We implemented the algorithm with Java Pathfinder as the backend verification tool, and evaluated it on several multithreaded Java programs. Results show that our incremental algorithm (1) can find errors very fast, (2) greatly reduces time needed for complete safety verification, and (3) it can find the same errors as full verification of the whole state space.

  • Czech name

  • Czech description

Classification

  • Type

    D - Article in proceedings

  • CEP classification

  • OECD FORD branch

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Result continuities

  • Project

    <a href="/en/project/GA20-07487S" target="_blank" >GA20-07487S: Scalable Techniques for Analysis of Complex Properties of Computer Systems</a><br>

  • Continuities

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Others

  • Publication year

    2023

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Data specific for result type

  • Article name in the collection

    ACM SIGSOFT Software Engineering Notes

  • ISBN

  • ISSN

    0163-5948

  • e-ISSN

  • Number of pages

    5

  • Pages from-to

    27-31

  • Publisher name

    ACM

  • Place of publication

    New York, USA

  • Event location

    Michigan, United States

  • Event date

    Oct 10, 2022

  • Type of event by nationality

    WRD - Celosvětová akce

  • UT code for WoS article