Article

Bita: Coverage-guided, automatic testing of actor programs

Authors:

Samira Tasharofi,

Michael Pradel,

Ralph JohnsonAuthors Info & Claims

ASE '13: Proceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering

Pages 114 - 124

https://doi.org/10.1109/ASE.2013.6693072

Published: 11 November 2013 Publication History

Publisher Site Get Access

Abstract

Actor programs are concurrent programs where concurrent entities communicate asynchronously by exchanging messages. Testing actor programs is challenging because the order of message receives depends on the nondeterministic scheduler and because exploring all schedules does not scale to large programs. This paper presents Bita, a scalable, automatic approach for testing non-deterministic behavior of actor programs. The key idea is to generate and explore schedules that are likely to reveal concurrency bugs because these schedules increase the schedule coverage. We present three schedule coverage criteria for actor programs, an algorithm to generate feasible schedules that increase coverage, and a technique to force a program to comply with a schedule. Applying Bita to real-world actor programs implemented in Scala reveals eight previously unknown concurrency bugs, of which six have already been fixed by the developers. Furthermore, we show our approach to find bugs 122x faster than random scheduling, on average.

References

[1]

https://github.com/uzh/signal-collect/issues/58.

[2]

"Fyrie redis," https://github.com/derekjw/fyrie-redis/tree/akka-1.2.

[3]

"Gatling stress tool," http://gatling-tool.org/.

[4]

"Geotrellis," http://www.azavea.com/products/geotrellis/.

[5]

"Signal/collect," http://uzh.github.io/signal-collect/.

[6]

G. Agha, ACTORS: a model of concurrent computation in distributed systems. Cambridge, MA, USA: MIT Press, 1986.

[7]

J. Armstrong, "Making reliable distributed systems in the presence of software errors," Ph.D. dissertation, Kungl Tekniska Högskolan, 2003, http://www.erlang.org.

[8]

J. Bonér, V. Klang, R. Kuhn et al., "Akka library," http://akka.io.

[9]

A. Bron, E. Farchi, Y. Magid, Y. Nir, and S. Ur, "Applications of synchronization coverage," in PPOPP, 2005, pp. 206-212.

Digital Library

[10]

S. Burckhardt, P. Kothari, M. Musuvathi, and S. Nagarakatte, "A randomized scheduler with probabilistic guarantees of finding bugs," in ASPLOS, 2010, pp. 167-178.

Digital Library

[11]

S. Bykov, A. Geller, G. Kliot, J. R. Larus, R. Pandya, and J. Thelin, "Orleans: cloud computing for everyone," in SOCC, 2011, pp. 16:1-16:14.

Digital Library

[12]

F. Chen, T. F. Serbanuta, and G. Rosu, "jPredictor: a predictive runtime analysis tool for java," in ICSE, 2008, pp. 221-230.

Digital Library

[13]

M. Christakis and K. Sagonas, "Detection of asynchronous message passing errors using static analysis," in PADL, 2011, pp. 5-18.

Digital Library

[14]

M. Christakis and K. F. Sagonas, "Detection of asynchronous message passing errors using static analysis," in PADL, 2011, pp. 5-18.

Digital Library

[15]

K. Claessen, M. Palka, N. Smallbone, J. Hughes, H. Svensson, T. Arts, and U. T. Wiger, "Finding race conditions in Erlang with QuickCheck and PULSE," in ICFP, 2009, pp. 149-160.

Digital Library

[16]

K. E. Coons, S. Burckhardt, and M. Musuvathi, "GAMBIT: effective unit testing for concurrency libraries," in PPOPP, 2010, pp. 15-24.

Digital Library

[17]

E. Deniz, A. Sen, and J. Holt, "Verification and coverage of message passing multicore applications." ACM T Des Automat El, p. 23, 2012.

Digital Library

[18]

O. Edelstein, E. Farchi, Y. Nir, G. Ratsaby, and S. Ur, "Multithreaded Java program test generation," IBM Syst J, vol. 41, no. 1, pp. 111-125, 2002.

Digital Library

[19]

C. Flanagan and S. N. Freund, "Adversarial memory for detecting destructive races," in PLDI, 2010, pp. 244-254.

Digital Library

[20]

L.-Å. Fredlund and H. Svensson, "Mcerlang: a model checker for a distributed functional programming language," in ICFP, 2007, pp. 125-136.

Digital Library

[21]

Q. Gao, W. Zhang, Z. Chen, M. Zheng, and F. Qin, "2ndstrike: toward manifesting hidden concurrency typestate bugs," in ASPLOS, 2011, pp. 239-250.

Digital Library

[22]

P. Godefroid and N. Nagappan, "Concurrency at Microsoft - an exploratory survey," in EC2, 2008.

[23]

P. Haller and F. Sommers, Actors in Scala. Artima, 2012.

Digital Library

[24]

C. Hewitt, P. Bishop, and R. Steiger, "A universal modular actor formalism for artificial intelligence," in IJCAI, 1973, pp. 235-245.

Digital Library

[25]

S. Hong, J. Ahn, S. Park, M. Kim, and M. J. Harrold, "Testing concurrent programs to achieve high synchronization coverage," in ISSTA, 2012, pp. 210-220.

Digital Library

[26]

J. Huang and C. Zhang, "Persuasive prediction of concurrency access anomalies," in ISSTA, 2011, pp. 144-154.

Digital Library

[27]

V. Jagannath, M. Gligoric, D. Jin, Q. Luo, G. Rosu, and D. Marinov, "Improved multithreaded unit testing," in ESEC/FSE, 2011, pp. 223-233.

Digital Library

[28]

P. Joshi, M. Naik, C.-S. Park, and K. Sen, "CalFuzzer: An extensible active testing framework for concurrent programs," in CAV, 2009, pp. 675-681.

Digital Library

[29]

R. K. Karmani, A. Shali, and G. Agha, "Actor frameworks for the JVM platform: a comparative analysis," in PPPJ, 2009, pp. 11-20.

Digital Library

[30]

B. Krena, Z. Letko, and T. Vojnar, "Coverage metrics for saturation-based and search-based testing of concurrent software," in RV, 2011, pp. 177-192.

Digital Library

[31]

Z. Lai, S.-C. Cheung, and W. K. Chan, "Detecting atomic-set serializability violations in multithreaded programs through active randomized testing," in ICSE, 2010, pp. 235-244.

Digital Library

[32]

S. Lauterburg, M. Dotta, D. Marinov, and G. A. Agha, "A framework for state-space exploration of Java-based actor programs," in ASE, 2009, pp. 468-479.

Digital Library

[33]

Y. Lei and W. E. Wong, "A novel framework for nondeterministic testing of message-passing programs." in HASE, 2005, pp. 66-75.

Digital Library

[34]

B. Long, D. Hoffman, and P. Strooper, "Tool support for testing concurrent Java components," IEEE Tr Softw Eng, vol. 29, no. 6, pp. 555-566, Jun. 2003.

Digital Library

[35]

S. Lu, W. Jiang, and Y. Zhou, "A study of interleaving coverage criteria," in ESEC/FSE, 2007, pp. 533-536.

Digital Library

[36]

M. Musuvathi, S. Qadeer, T. Ball, G. Basler, P. A. Nainar, and I. Neamtiu, "Finding and reproducing Heisenbugs in concurrent programs," in OSDI, 2008, pp. 267-280.

Digital Library

[37]

C.-S. Park and K. Sen, "Randomized active atomicity violation detection in concurrent programs," in FSE, 2008, pp. 135-145.

Digital Library

[38]

S. Park, S. Lu, and Y. Zhou, "CTrigger: exposing atomicity violation bugs from their hiding places," in ASPLOS, 2009, pp. 25-36.

Digital Library

[39]

V. Pech, D. König, R. Winder et al., "GPars," http://gpars.codehaus.org/.

[40]

W. Pugh and N. Ayewah, "Unit testing concurrent software," in ASE, 2007, pp. 513-516.

Digital Library

[41]

K. Sen, "Effective random testing of concurrent programs," in ASE, 2007, pp. 323-332.

Digital Library

[42]

K. Sen, "Race directed random testing of concurrent programs," in PLDI, 2008, pp. 11-21.

Digital Library

[43]

K. Sen and G. Agha, "Automated systematic testing of open distributed programs," in FASE, 2006, pp. 339-356.

Digital Library

[44]

F. Sorrentino, A. Farzan, and P. Madhusudan, "PENELOPE: weaving threads to expose atomicity violations," in FSE, 2010, pp. 37-46.

Digital Library

[45]

S. R. S. Souza, S. R. Vergilio, P. S. L. Souza, A. S. Simão, and A. C. Hausen, "Structural testing criteria for message-passing parallel programs," Concurr Comput: Pract Exper, vol. 20, no. 16, pp. 1893-1916, Nov. 2008.

Digital Library

[46]

S. Tasharofi, "Efficient testing of actor programs with nondeterministic behavior," University of Illinois at Urbana-Champaign, Tech. Rep., 2013, http://hdl.handle.net/2142/45680.

[47]

S. Tasharofi, M. Gligoric, D. Marinov, and R. Johnson, "Setac: A framework for phased deterministic testing of scala actor programs," in Scala Days, 2011.

[48]

S. Tasharofi, R. K. Karmani, S. Lauterburg, A. Legay, D. Marinov, and G. Agha, "TransDPOR: A novel dynamic partial-order reduction technique for testing actor programs," in FMOODS/FORTE.

Digital Library

[49]

R. N. Taylor, D. L. Levine, and C. D. Kelly, "Structural testing of concurrent programs," IEEE Tr Softw Eng, vol. 18, no. 3, pp. 206-215, 1992.

Digital Library

[50]

W. Visser, K. Havelund, G. P. Brat, S. Park, and F. Lerda, "Model checking programs," Autom Software Eng, vol. 10, no. 2, pp. 203-232, 2003.

Digital Library

[51]

C.-S. D. Yang, A. L. Souter, and L. L. Pollock, "All-du-path coverage for parallel programs," in ISSTA, 1998, pp. 153-162.

Digital Library

[52]

J. Yu, S. Narayanasamy, C. Pereira, and G. Pokam, "Maple: a coveragedriven testing tool for multithreaded programs," in OOPSLA, 2012, pp. 485-502.

Digital Library

[53]

W. Zhang, J. Lim, R. Olichandran, J. Scherpelz, G. Jin, S. Lu, and T. W. Reps, "ConSeq: detecting concurrency bugs through sequential errors," in ASPLOS, 2011, pp. 251-264.

Digital Library

[54]

W. Zhang, C. Sun, and S. Lu, "ConMem: detecting severe concurrency bugs through an effect-oriented approach," in ASPLOS, 2010, pp. 179-192.

Digital Library

Cited By

Menard CLohstroh MBateni SChorlian MDeng ADonovan PFournier CLin SSuchert FTanneberger TKim HCastrillon JLee E(2023)High-performance Deterministic Concurrency Using Lingua FrancaACM Transactions on Architecture and Code Optimization10.1145/361768720:4(1-29)Online publication date: 26-Oct-2023
https://dl.acm.org/doi/10.1145/3617687
Ganji MAlimadadi STip FChandra SBlincoe KTonella P(2023)Code Coverage Criteria for Asynchronous ProgramsProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616292(1307-1319)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616292
Bagherzadeh MFireman NShawesh AKhatchadourian R(2020)Actor concurrency bugs: a comprehensive study on symptoms, root causes, API usages, and differencesProceedings of the ACM on Programming Languages10.1145/34282824:OOPSLA(1-32)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428282
Show More Cited By

Recommendations

Scheduling of deteriorating jobs with release dates to minimize the maximum lateness

In this paper, we consider the problem of scheduling n deteriorating jobs with release dates on a single (batching) machine. Each job's processing time is a simple linear function of its starting time. The objective is to minimize the maximum lateness. ...
Primary-secondary bicriteria scheduling on identical machines to minimize the total completion time of all jobs and the maximum T-time of all machines

In this paper, we study a new primary-secondary bicriteria scheduling problem on identical machines. The primary objective is to minimize the total completion time of all jobs and the secondary objective is to minimize the maximum T-time of all machines,...
Minimizing Total Completion Time Subject to Job Release Dates and Preemption Penalties

Extensive research has been devoted to preemptive scheduling. However, little attention has been paid to problems where a certain time penalty must be incurred if preemption is allowed. In this paper, we consider the single-machine scheduling problem of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASE '13: Proceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering

November 2013

765 pages

ISBN:9781479902156

General Chair:
Ewen Denney
SGT, NASA, Ames Research Center, Moffett Field
,
Program Chairs:
Tevfik Bultan
University of California, Santa Barbara
,
Andreas Zeller
Saarland University, Saarbrücken, Germany

Sponsors

NASA: National Aeronatics and Space Administration
SIGAI: ACM Special Interest Group on Artificial Intelligence
IEEE: IEEE Computer Society Technical Committee on Design Automation
SIGSOFT: ACM Special Interest Group on Software Engineering
Microsoft: Microsoft

Publisher

IEEE Press

Publication History

Published: 11 November 2013

Check for updates

Qualifiers

Article

Conference

ASE '13

Sponsor:

NASA
SIGAI
IEEE
SIGSOFT
Microsoft

ASE '13: Automated Software Engineering

November 11 - 15, 2013

CA, Silicon Valley, USA

Acceptance Rates

Overall Acceptance Rate 82 of 337 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
43
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Menard CLohstroh MBateni SChorlian MDeng ADonovan PFournier CLin SSuchert FTanneberger TKim HCastrillon JLee E(2023)High-performance Deterministic Concurrency Using Lingua FrancaACM Transactions on Architecture and Code Optimization10.1145/361768720:4(1-29)Online publication date: 26-Oct-2023
https://dl.acm.org/doi/10.1145/3617687
Ganji MAlimadadi STip FChandra SBlincoe KTonella P(2023)Code Coverage Criteria for Asynchronous ProgramsProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616292(1307-1319)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616292
Bagherzadeh MFireman NShawesh AKhatchadourian R(2020)Actor concurrency bugs: a comprehensive study on symptoms, root causes, API usages, and differencesProceedings of the ACM on Programming Languages10.1145/34282824:OOPSLA(1-32)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428282
De Bleser JDi Nucci DDe Roover C(2020)A Delta-Debugging Approach to Assessing the Resilience of Actor Programs through Run-time Test PerturbationsProceedings of the IEEE/ACM 1st International Conference on Automation of Software Test10.1145/3387903.3389303(21-30)Online publication date: 7-Oct-2020
https://dl.acm.org/doi/10.1145/3387903.3389303
Ozkan BMajumdar ROraee S(2019)Trace aware random testing for distributed systemsProceedings of the ACM on Programming Languages10.1145/33606063:OOPSLA(1-29)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360606
Ozkan BMajumdar RNiksic FBefrouei MWeissenbacher G(2018)Randomized testing of distributed systems with probabilistic guaranteesProceedings of the ACM on Programming Languages10.1145/32765302:OOPSLA(1-28)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276530
Sulzmann MStadtmüller KSabel DThiemann P(2018)Two-Phase Dynamic Analysis of Message-Passing Go Programs Based on Vector ClocksProceedings of the 20th International Symposium on Principles and Practice of Declarative Programming10.1145/3236950.3236959(1-13)Online publication date: 3-Sep-2018
https://dl.acm.org/doi/10.1145/3236950.3236959
Hedden BZhao X(2018)A Comprehensive Study on Bugs in Actor SystemsProceedings of the 47th International Conference on Parallel Processing10.1145/3225058.3225139(1-9)Online publication date: 13-Aug-2018
https://dl.acm.org/doi/10.1145/3225058.3225139
Bianchi FMargara APezze M(2018)A Survey of Recent Trends in Testing Concurrent Software SystemsIEEE Transactions on Software Engineering10.1109/TSE.2017.270708944:8(747-783)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1109/TSE.2017.2707089
Billes MMøller APradel M(2017)Systematic black-box analysis of collaborative web applicationsACM SIGPLAN Notices10.1145/3140587.306236452:6(171-184)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3140587.3062364
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.

Media

Figures

Other

Tables

View Table of Contents