A Scala library for testing student assignments on concurrent programming
Pages 1 - 10
Abstract
We present a lightweight library for testing concurrent Scala programs by systematically exploring multiple interleavings between user-specified operations on shared objects. Our library is targeted at beginners of concurrent programming in Scala, runs on a standard JVM, and supports conventional synchronization primitives such as `wait`, `notify`, and `synchronized`. The key component of the library is the trait `SchedulableMonitor` that accepts a thread schedule, and interleaves as per the schedule all user-specified operations invoked through multiple threads on objects implementing the trait. Using our library, we developed a unit test engine that tests concurrent operations on shared objects on thousands of schedules obtained by bounding the number of context-switches. If a unit test fails on a schedule, the test engine offers as feedback the interleaved traces of execution that resulted in the failure. We used our test engine to automatically test and evaluate two assignments: (a) lock-based producer/consumer problem, and (b) lock-free sorted list implementation, offered to a class of 150 under-graduate students of EPFL. Our evaluations show that the system is effective in detecting bugs in students' solutions.
References
[1]
Java documentation.
[2]
T. Andrews, S. Qadeer, S. K. Rajamani, J. Rehof, and Y. Xie. Zing: Exploiting program structure for model checking concurrent software. In CONCUR, 2004.
[3]
K. Beck. Embracing change with extreme programming. ’99.
[4]
A. Bouajjani, M. Emmi, C. Enea, and J. Hamza. On reducing linearizability to state reachability. In ICALP, 2015.
[5]
J. Burnim, T. Elmas, G. Necula, and K. Sen. Concurrit: testing concurrent programs with programmable state-space exploration. In USENIX Workshop, 2012.
[6]
T. Elmas, S. Qadeer, and S. Tasiran. Goldilocks: A race-aware java runtime. Commun. ACM, Nov. 2010.
[7]
M. Emmi, B. K. Ozkan, and S. Tasiran. Exploiting synchronization in the analysis of shared-memory asynchronous programs. In SPIN, 2014.
[8]
B. Fischer, O. Inverso, and G. Parlato. Cseq: a sequentialization tool for C. In TACAS, 2013.
[9]
J. Hamza. Algorithmic Verification of Concurrent and Distributed Data Structures. PhD thesis, 2015.
[10]
G. J. Holzmann. The model checker spin. TSE, 1997.
[11]
G. J. Holzmann. The SPIN model checker: Primer and reference manual. Addison-Wesley Reading, 2004.
[12]
B. Jacobs, J. Smans, and F. Piessens. A quick tour of the verifast program verifier. In APLAS, 2008.
[13]
V. Jagannath, M. Gligoric, D. Jin, Q. Luo, G. Rosu, and D. Marinov. Improved multithreaded unit testing. In FSE’11.
[14]
M. Kebrt and O. ˇSer`y. Unitcheck: Unit testing and model checking combined. In ATVA, 2009.
[15]
D. Kroening and M. Tautschnig. CBMC – C bounded model checker. In TACAS, 2014.
[16]
A. Lal, T. Touili, N. Kidd, and T. Reps. Interprocedural analysis of concurrent programs under a context bound. In TACAS, 2008.
[17]
M. Musuvathi and S. Qadeer. Iterative context bounding for systematic testing of multithreaded programs. In PLDI ’07.
[18]
M. Musuvathi and S. Qadeer. CHESS: systematic stress testing of concurrent software. In LOPSTR, 2006.
[19]
S. Qadeer. Poirot – a concurrency sleuth. In ICFEM, 2011.
[20]
I. Rabinovitz and O. Grumberg. Bounded model checking of concurrent programs. In CAV, 2005.
[21]
K. Sen. Race directed random testing of concurrent programs. In PLDI, 2008.
[22]
K. Sen and G. Agha. Cute and jcute: Concolic unit testing and explicit path model-checking tools. In CAV, 2006.
[23]
O. Shacham, N. Bronson, A. Aiken, M. Sagiv, M. Vechev, and E. Yahav. Testing atomicity of composed concurrent operations. In OOPSLA, 2011.
[24]
W. Visser, K. Havelund, G. Brat, S. Park, and F. Lerda. Model checking programs. In ASE, 2003.
Index Terms
- A Scala library for testing student assignments on concurrent programming
Recommendations
Testing atomicity of composed concurrent operations
OOPSLA '11: Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applicationsWe address the problem of testing atomicity of composed concurrent operations. Concurrent libraries help programmers exploit parallel hardware by providing scalable concurrent operations with the illusion that each operation is executed atomically. ...
Maple: a coverage-driven testing tool for multithreaded programs
OOPSLA '12Testing multithreaded programs is a hard problem, because it is challenging to expose those rare interleavings that can trigger a concurrency bug. We propose a new thread interleaving coverage-driven testing tool called Maple that seeks to expose ...
Testing atomicity of composed concurrent operations
OOPSLA '11We address the problem of testing atomicity of composed concurrent operations. Concurrent libraries help programmers exploit parallel hardware by providing scalable concurrent operations with the illusion that each operation is executed atomically. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2016
113 pages
ISBN:9781450346481
DOI:10.1145/2998392
- General Chairs:
- Aggelos Biboudis,
- Manohar Jonnalagedda,
- Sandro Stucki,
- Vlad Ureche
Copyright © 2016 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
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 30 October 2016
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
SPLASH '16
Sponsor:
SPLASH '16: Conference on Systems, Programming, Languages, and Applications: Software for Humanity
October 30 - 31, 2016
Amsterdam, Netherlands
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 108Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in