1,720,992 research outputs found
Bounded model checking of multi-threaded programs via sequentialization
No full textIn order to achieve greater computational power, processors now contain several cores that work in parallel and, consequently, multi-threaded software is rapidly becoming widespread.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.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.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
CSeq-DR
No full text<p>Artifact used to generate the results for the paper "Accurate Static Data Race Detection for C", by Emerson Sales, Omar Inverso and Emilio Tuosto</p>
CSeq: a concurrency pre-processor for sequential c verification tools (tool demonstration)
No full textSequentialization translates concurrent programs into equivalent nondeterministic sequential programs so that the different concurrent schedules no longer need to be handled explicitly. It can thus be used as a concurrency preprocessing technique for automated sequential program verification tools. Our CSeq tool implements a novel sequentialization for C programs using pthreads, which extends the Lal/Reps sequentialization to support dynamic thread creation. CSeq now works with three different backend tools, CBMC, ESBMC, and LLBMC, and is competitive with state-of-the-art verification tools for concurrent programs
CSeq-DR
No full text<p>Artifact used to generate the results for the paper "Precise Data Race Detection for C", by Emerson Sales, Omar Inverso and Emilio Tuosto</p>
On the path-width of integer linear programming
No full textWe consider the feasibility problem of integer linear programming (ILP). We show that solutions of any ILP instance can be naturally represented by an FO-definable class of graphs. For each solution, there may be many graphs representing it. However, one of these graphs is of path-width at most 2n, where n is the number of variables in the instance. Since FO is decidable on graphs of bounded path-width, we obtain an alternative decidability result for ILP. The technique we use underlines a common principle to prove decidability which has previously been employed for automata with auxiliary storage. We also show how this new result links to automata theory and program verification
Looking at Computations from a Different Angle
No full textWe present a novel framework to reason about programs based on encodings of computations as graphs. The main insight here is to rearrange the programs such that given a bound k, each computation can be explored according to any tree decomposition of width k of the corresponding behaviour graph. This produces under-approximations parameterized on k, which result in a complete method when we restrict to classes of behaviour graphs of bounded tree-width. As an additional feature, the transformation of the input program can be targeted to existing tools for the analysis, and thus, off-the-shelf tools based on fixed-point, or capable of analyzing sequential programs with scalar variables and nondeterminism, can be used.To illustrate our approach, we develop this framework for sequential programs and discuss how to extend it to handle concurrency. For the case of sequential programs, we develop a compositional approach to generate on-the-fly tree decompositions of nested words, which is based on graph-summaries. To illustrate our technique, we also implement our algorithms for C programs
Unbounded Lazy-CSeq: A Lazy Sequentialization Tool for C with unboundedly many Context Switches: (Competition Contribution)
No full textWe describe a new CSeq module for the verification of multi-threadedC programs with dynamic thread creation. This module implements a variationof the lazy sequentialization algorithm implemented in Lazy-CSeq. The mainnovelty is that we do not bound here the number of round-robin schedules in anexecution and the loops that do not contain a thread creation statement are notunwound (and thus unboundedly many iterations can be considered). As in Lazy-CSeq the number of thread creations per run is bounded as well as the depth ofrecursive calls. For the experiments we use CPAChecker as backen
On the Path-Width of Integer Linear Programming
Full text linkWe consider the feasibility problem of integer linear programming (ILP). We show that solutions of any ILP instance can be naturally represented by an FO-definable class of graphs. For each solution there may be many graphs representing it. However, one of these graphs is of path-width at most 2n, where n is the number of variables in the instance. Since FO is decidable on graphs of bounded path-width, we obtain an alternative decidability result for ILP. The technique we use underlines a common principle to prove decidability which has previously been employed for automata with auxiliary storage. We also show how this new result links to automata theory and program verification
- …
