Back to search

University of Southampton

Bounded model checking of multi-threaded programs via sequentialization

Abstract

dc:description.abstract

In order to achieve greater computational power, processors now contain several cores that work in parallel and, consequently, multi-threaded software is rapidly becoming widespread.<br/><br/>The inherently nondeterministic nature of concurrent computations can cause errors that show up rarely and are difficult to reproduce and repair. Traditional testing techniques perform an explicit exploration of the possible program executions, and are thus not adequate to spot such bugs. They need to be complemented by symbolic verification techniques that analyse multiple thread interactions simultaneously.<br/><br/>Sequentialization consists in translating a given concurrent program into a corresponding non-deterministic sequential program that simulates executions of the original program. We investigate on whether combining sequentialization (to symbolically represent thread interleavings) with bounded model-checking (BMC) can be effective for finding errors in concurrent software.<br/><br/>Specifically, we target multi-threaded C programs with POSIX threads. We make the following contributions: (1) evaluate the Lal-Reps sequentialization schema in combination with BMC; (2) propose and evaluate a new sequentialization schema specifically tailored to BMC and aimed at fast bug finding; (3) present a framework for building tools based on sequentialization.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Inverso, Omar
Advisor dc:contributor.advisor
  • Parlato, Gennaro

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Inverso, Omar. Bounded model checking of multi-threaded programs via sequentialization. doctoral thesis, University of Southampton, 2015.