Article

A serializability violation detector for shared-memory server programs

Authors:

Rastislav Bodík,

Mark D. HillAuthors Info & Claims

PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation

Pages 1 - 14

https://doi.org/10.1145/1065010.1065013

Published: 12 June 2005 Publication History

Abstract

We aim to improve reliability of multithreaded programs by proposing a dynamic detector that detects potentially erroneous program executions and their causes. We design and evaluate a Serializability Violation Detector (SVD) that has two unique goals: (I) triggering automatic recovery from erroneous executions using backward error recovery (BER), or simply alerting users that a software error may have occurred; and (II) helping debug programs by revealing causes of error symptoms.Two properties of SVD help in achieving these goals. First, to detect only erroneous executions, SVD checks serializability of atomic regions, which are code regions that need to be executed atomically. Second, to improve usability, SVD does not require a priori annotations of atomic regions; instead, SVD approximates them using a heuristic. Experimental results on three widely-used multithreaded server programs show that SVD finds real bugs and reports modest false positives. The goal of this paper is to develop a detector suitable for (I) BER-based avoidance of erroneous program executions; and (II) alerting users as software errors occur. We argue that such a detector should have the following two properties.

References

[1]

H. Agrawal and J. R. Horgan. Dynamic Program Slicing. In Proceedings of the SIGPLAN 1990 Conference on Programming Language Design and Implementation, pages 246--256, June 1990.

Digital Library

[2]

A. R. Alameldeen, M. M. K. Martin, C. J. Mauer, K. E. Moore, M. Xu, D. J. Sorin, M. D. Hill, and D. A. Wood. Simulating a 2M Commercial Server on a 2K PC. IEEE Computer, 36(2):50--57, Feb. 2003.

Digital Library

[3]

Apache HTTP Server Project. http://www.apache.org/.

[4]

D. F. Bacon and S. C. Goldstein. Hardware-Assisted Replay of Multiprocessor Programs. Proceedings of the ACM/ONR Workshop on Parallel and Distributed Debugging, published in ACM SIGPLAN Notices, pages 194--206, 1991.

Digital Library

[5]

P. Barford and M. Crovella. Generating Representative Web Workloads for Network and Server Performance Evaluation. In Proceedings of the 1998 ACM Sigmetrics Conference on Measurement and Modeling of Computer Systems, pages 151--160, June 1998.

Digital Library

[6]

M. Burrows and K. R. M. Leino. Finding stale-value errors in concurrent programs. Technical report, Compaq Systems Research Center Technical Note (2002-04), May 2002.

[7]

C.-Y. Cher and T. N. Vijaykumar. Skipper: a microarchitecture for exploiting control-flow independence. In Proceedings of the 34th Annual IEEE/ACM International Symposium on Microarchitecture, pages 4--15, Dec. 2001.

Digital Library

[8]

J.-D. Choi, K. Lee, A. Loginov, R. O'Callahan, V. Sarkar, and M. Sridharan. Efficient and precise datarace detection for multithreaded object-oriented programs. In Proceedings of the SIGPLAN 2002 Conference on Programming Language Design and Implementation, pages 258--269, June 2002.

Digital Library

[9]

J.-D. Choi and S.-L. Min. Race Frontier: Reproducing Data Races in Parallel-Program Debugging. In Proceedings of the 3rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP), pages 145--154, July 1991.

Digital Library

[10]

M. Christiaens and K. D. Bosschere. TRaDe, a topological approach to on-the-fly race detection in java programs. In Proceedings of the Java Virtual Machine Research and Technology Symposium (JVM'01), 2001.

Digital Library

[11]

J. D. Collins, D. M. Tullsen, and H. Wang. Control Flow Optimization Via Dynamic Reconvergence Prediction. In Proceedings of the 37th Annual IEEE/ACM International Symposium on Microarchitecture, pages 129--140, Dec. 2004.

Digital Library

[12]

A. Dinning and E. Schonberg. The Empirical Comparison of Monitoring Algorithms for Access Anomaly Detection. In Proceedings of the 2nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP), pages 1--10, Mar. 1990.

Digital Library

[13]

D. Engler and K. Ashcraft. RacerX: effective, static detection of race conditions and deadlocks. In Proc. 19th Symposium on Operating System Principles, pages 237--252, Oct. 2003.

Digital Library

[14]

K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger. The notions of consistency and predicate locks in a database system. Communications of the ACM, 19(11):624--633, 1976.

Digital Library

[15]

C. Flanagan and S. N. Freund. Atomizer: a dynamic atomicity checker for multithreaded programs. In Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 256--267, 2004.

Digital Library

[16]

C. Flanagan and S. Qadeer. A Type and Effect System for Atomicity. In Proceedings of the SIGPLAN 2003 Conference on Programming Language Design and Implementation, June 2003.

Digital Library

[17]

Y.-K. Jun and K. Koh. On-the-Fly Detection of Access Anomalies in Nested Parallel Loops. In Proceedings of the ACM/ONR Workshop on Parallel and Distributed Debugging (PADD), pages 107--117, 1993.

Digital Library

[18]

L. Lamport. Time, Clocks and the Ordering of Events in a Distributed System. Communications of the ACM, 21(7):558--565, July 1978.

Digital Library

[19]

P. S. Magnusson et al. Simics: A Full System Simulation Platform. IEEE Computer, 35(2):50--58, Feb. 2002.

Digital Library

[20]

C. J. Mauer, M. D. Hill, and D. A. Wood. Full System Timing-First Simulation. In Proceedings of the 2002 ACM Sigmetrics Conference on Measurement and Modeling of Computer Systems, pages 108--116, June 2002.

Digital Library

[21]

B. P. Miller and J.-D. Choi. A Mechanism for Efficient Debugging of Parallel Programs. In Proceedings of the SIGPLAN 1988 Conference on Programming Language Design and Implementation, pages 135--144, June 1988.

Digital Library

[22]

S. L. Min and J.-D. Choi. An Efficient Cache-based Access Anomaly Detection Scheme. In Proceedings of the Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 235--244, Apr. 1991.

Digital Library

[23]

MySQL AB. http://www.mysql.com/.

[24]

R. H. B. Netzer and B. P. Miller. What are Race Conditions?: Some Issues and Formalizations. ACM Letters on Programming Languages and Systems, 1(1):74--88, Mar. 1992.

Digital Library

[25]

C. Papadimitriou. The Theory of Database Concurrency Control. Computer Science Press, Rockville, Maryland, 1986.

Digital Library

[26]

D. Perkovic and P. Keleher. A Protocol-Centric Approach to On-The-Fly Race Detection. IEEE Transactions on Parallel and Distributed Systems, 11(10):1058--1072, Oct. 2000.

Digital Library

[27]

PostgreSQL Global Development Group. http://www.postgresql.org/.

[28]

K. Poulsen. SecurityFocus News: Tracking the blackout bug. http://www.securityfocus.com/news/8412.

[29]

M. Prvulovic and J. Torrellas. ReEnact: Using Thread-Level Speculation Mechanisms to Debug Data Races in Multithreaded Codes. In Proceedings of the 30th Annual International Symposium on Computer Architecture, pages 110--121, June 2003.

Digital Library

[30]

M. Prvulovic, Z. Zhang, and J. Torrellas. ReVive: Cost-Effective Architectural Support for Rollback Recovery in Shared-Memory Multiprocessors. In Proceedings of the 29th Annual International Symposium on Computer Architecture, pages 111--122, May 2002.

Digital Library

[31]

B. Richards and J. R. Larus. Protocol-based Data-race Detection. In SIGMETRICS symposium on Parallel and Distributed Tools, pages 40--47, 1998.

Digital Library

[32]

M. Ronsse and K. D. Bosschere. Non-intrusive On-the-fly Data Race Detection using Execution Replay. In Automated and Algorithmic Debugging, Nov. 2000.

[33]

S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A Dynamic Data Race Detector for Multithreaded Programs. ACM Transactions on Computer Systems, 15(4):391--411, Nov. 1997.

Digital Library

[34]

D. J. Sorin, M. M. K. Martin, M. D. Hill, and D. A. Wood. SafetyNet: Improving the Availability of Shared Memory Multiprocessors with Global Checkpoint/Recovery. In Proceedings of the 29th Annual International Symposium on Computer Architecture, pages 123--134, May 2002.

Digital Library

[35]

U.S.-Canada Power System Outage Task Force. Final Report on the August 14th Blackout in the United States and Canada. Technical report, Department of Energy, 2004.

[36]

C. von Praun and T. Gross. Object-Race Detection. In Proceedings of the Conference on Object-Oriented Programming, Systems, Languages and Application (OOPSLA), Oct. 2001.

Digital Library

[37]

Wisconsin Multifacet GEMS Simulator. http://www.cs.wisc.edu/gems/.

[38]

M. Xu, R. Bodík, and M. D. Hill. A "Flight Data Recorder" for Enabling Full-system Multiprocessor Deterministic Replay. In Proceedings of the 30th Annual International Symposium on Computer Architecture, pages 122--133, June 2003.

Digital Library

Cited By

Ma XAshraf IChan W(2023)Davida: A Decentralization Approach to Localizing Transaction Sequences for Debugging Transactional Atomicity ViolationsIEEE Transactions on Reliability10.1109/TR.2022.317668072:2(808-826)Online publication date: Jun-2023
https://doi.org/10.1109/TR.2022.3176680
Wong WGao RLi YAbreu RWotawa FLi D(2023)Software Fault Localization: an Overview of Research, Techniques, and ToolsHandbook of Software Fault Localization10.1002/9781119880929.ch1(1-117)Online publication date: 21-Apr-2023
https://doi.org/10.1002/9781119880929.ch1
Gong SAltinbüken DFonseca PManiatis P(2021)SnowboardProceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles10.1145/3477132.3483549(66-83)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3477132.3483549
Show More Cited By

Index Terms

A serializability violation detector for shared-memory server programs
1. General and reference
  1. Cross-computing tools and techniques
    1. Reliability
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
  2. Software organization and properties
    1. Extra-functional properties
      1. Software reliability

Recommendations

Dynamic detection of atomic-set-serializability violations
ICSE '08: Proceedings of the 30th international conference on Software engineering

Previously we presented atomic sets, memory locations that share some consistency property, and units of work, code fragments that preserve consistency of atomic sets on which they are declared. We also proposed atomic-set serializability as a ...
A serializability violation detector for shared-memory server programs
Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation

We aim to improve reliability of multithreaded programs by proposing a dynamic detector that detects potentially erroneous program executions and their causes. We design and evaluate a Serializability Violation Detector (SVD) that has two unique goals: (...
Sequential verification of serializability
POPL '10

Serializability is a commonly used correctness condition in concurrent programming. When a concurrent module is serializable, certain other properties of the module can be verified by considering only its sequential executions. In many cases, concurrent ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation

June 2005

338 pages

ISBN:1595930566

DOI:10.1145/1065010

General Chair:
Vivek Sarkar
IBM Research
,
Program Chair:
Mary Hall
USC/ISI

ACM SIGPLAN Notices Volume 40, Issue 6
Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation
June 2005
325 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1064978
Issue’s Table of Contents

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PLDI05

Sponsor:

PLDI05: ACM SIGPLAN Conference on Programming Language Design and Implementation 2005

June 12 - 15, 2005

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

187
Total Citations
View Citations
1,117
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ma XAshraf IChan W(2023)Davida: A Decentralization Approach to Localizing Transaction Sequences for Debugging Transactional Atomicity ViolationsIEEE Transactions on Reliability10.1109/TR.2022.317668072:2(808-826)Online publication date: Jun-2023
https://doi.org/10.1109/TR.2022.3176680
Wong WGao RLi YAbreu RWotawa FLi D(2023)Software Fault Localization: an Overview of Research, Techniques, and ToolsHandbook of Software Fault Localization10.1002/9781119880929.ch1(1-117)Online publication date: 21-Apr-2023
https://doi.org/10.1002/9781119880929.ch1
Gong SAltinbüken DFonseca PManiatis P(2021)SnowboardProceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles10.1145/3477132.3483549(66-83)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3477132.3483549
Chu JYu THuffman Hayes JHan XZhao Y(2021)Effective fault localization and context‐aware debugging for concurrent programsSoftware Testing, Verification and Reliability10.1002/stvr.179732:1Online publication date: 13-Oct-2021
https://doi.org/10.1002/stvr.1797
Mathur UViswanathan MLarus JCeze LStrauss K(2020)Atomicity Checking in Linear Time using Vector ClocksProceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3373376.3378475(183-199)Online publication date: 9-Mar-2020
https://dl.acm.org/doi/10.1145/3373376.3378475
Wei GChen YRompf T(2019)Staged abstract interpreters: fast and modular whole-program analysis via meta-programmingProceedings of the ACM on Programming Languages10.1145/33605523:OOPSLA(1-32)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360552
Ter-Gabrielyan ASummers AMüller P(2019)Modular verification of heap reachability properties in separation logicProceedings of the ACM on Programming Languages10.1145/33605473:OOPSLA(1-28)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360547
Siraichi MSantos VCollange CPereira F(2019)Qubit allocation as a combination of subgraph isomorphism and token swappingProceedings of the ACM on Programming Languages10.1145/33605463:OOPSLA(1-29)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360546
Fernando VJoshi KMisailovic S(2019)Verifying safety and accuracy of approximate parallel programs via canonical sequentializationProceedings of the ACM on Programming Languages10.1145/33605453:OOPSLA(1-29)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360545
Bastani OZhang XSolar-Lezama A(2019)Probabilistic verification of fairness properties via concentrationProceedings of the ACM on Programming Languages10.1145/33605443:OOPSLA(1-27)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360544
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten