Cross-Entropy-Based Replay of Concurrent Programs

Hana Chockler*, Eitan Farchi, Benny Godlin, Sergey Novikov

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter

5 Citations (Scopus)

Abstract

Replay is an important technique in program analysis, allowing to reproduce bugs, to track changes, and to repeat executions for better understanding of the results. Unfortunately, since re-executing a concurrent program does not necessarily produce the same ordering of events, replay of such programs becomes a difficult task. The most common approach to replay of concurrent programs is based on analyzing the logical dependencies among concurrent events and requires a complete recording of the execution we are trying to replay as well as a complete control over the program's scheduler. In realistic settings, we usually have only a partial recording of the execution and only partial control over the scheduling decisions, thus such an analysis is often impossible. In this paper, we present an approach for replay in the presence of partial information and partial control. Our approach is based on a novel application of the cross-entropy method, and it does not require any logical analysis of dependencies among concurrent events. Roughly speaking, given a partial recording R of an execution, we define a performance function on executions, which reaches its maximum on R (or any other execution that coincides with R on the recorded events). Then, the program is executed many times in iterations, on each iteration adjusting the probabilistic scheduling decisions so that the performance function is maximized. Our method is also applicable to debugging of concurrent programs, in which the program is changed before it replayed in order to increase the information from its execution. We implemented our replay method on concurrent Java programs and we show that it consistently achieves a close replay in presence of incomplete information and incomplete control, as well as when the program is changed before it is replayed.

Original languageEnglish
Title of host publicationFundamental Approaches to Software Engineering
Subtitle of host publication12th International Conference, FASE 2009, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009, York, UK, March 22-29, 2009. Proceedings
EditorsM Chechik, M Wirsing
Place of PublicationBERLIN
PublisherSpringer-Verlag Berlin Heidelberg
Pages201-215
Number of pages15
ISBN (Print)978-3-642-00592-3
DOIs
Publication statusPublished - 2009
Event12th International Conference on Fundamental Approaches to Software Engineering held in Conjuction with European Conference on Theory and Practice of Software - York, United Kingdom
Duration: 22 Mar 200929 Mar 2009

Publication series

NameLecture Notes in Computer Science
PublisherSPRINGER-VERLAG BERLIN
Volume5503
ISSN (Print)0302-9743

Conference

Conference12th International Conference on Fundamental Approaches to Software Engineering held in Conjuction with European Conference on Theory and Practice of Software
Country/TerritoryUnited Kingdom
CityYork
Period22/03/200929/03/2009

Keywords

  • OPTIMIZATION
  • EVENTS

Fingerprint

Dive into the research topics of 'Cross-Entropy-Based Replay of Concurrent Programs'. Together they form a unique fingerprint.

Cite this