Document Open Access Logo

Targeted Test Generation for Actor Systems

Authors Sihan Li, Farah Hariri, Gul Agha

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2018.8.pdf
  • Filesize: 0.69 MB
  • 31 pages

Document Identifiers

Author Details

Sihan Li
  • Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, USA
Farah Hariri
  • Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, USA
Gul Agha
  • Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, USA

Cite As Get BibTex

Sihan Li, Farah Hariri, and Gul Agha. Targeted Test Generation for Actor Systems. In 32nd European Conference on Object-Oriented Programming (ECOOP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 109, pp. 8:1-8:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ECOOP.2018.8

Abstract

This paper addresses the problem of targeted test generation for actor systems. Specifically, we propose a method to support generation of system-level tests to cover a given code location in an actor system. The test generation method consists of two phases. First, static analysis is used to construct an abstraction of an entire actor system in terms of a message flow graph (MFG). An MFG captures potential actor interactions that are defined in a program. Second, a backwards symbolic execution (BSE) from a target location to an "entry point" of the actor system is performed. BSE uses the MFG constructed in the first phase of our targeted test generation method to guide execution across actors. Because concurrency leads to a huge search space which can potentially be explored through BSE, we prune the search space by using two heuristics combined with a feedback-directed technique. We implement our method in Tap, a tool for Java Akka programs, and evaluate Tap on the Savina benchmarks as well as four open source projects. Our evaluation shows that the Tap achieves a relatively high target coverage (78% on 1,000 targets) and detects six previously unreported bugs in the subjects.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Software testing and debugging
Keywords
  • actors
  • symbolic execution
  • test generation
  • static analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Erlang Introduction. http://erlang.org/faq/introduction.html. Google Scholar
  2. Java Akka. https://doc.akka.io/docs/akka/current/actors.html?language=java. Google Scholar
  3. Orleans. https://dotnet.github.io/orleans/index.html. Google Scholar
  4. Scala Akka. https://doc.akka.io/docs/akka/current/index-actors.html?language=scala. Google Scholar
  5. Wala. http://wala.sourceforge.net. Google Scholar
  6. Gul Agha. Actors: A Model of Concurrent Computation in Distributed Systems. MIT Press, Cambridge, MA, USA, 1986. Google Scholar
  7. Gul Agha. Concurrent Object-oriented Programming. Commun. ACM, 33(9):125-141, 1990. Google Scholar
  8. Gul A Agha, Ian A Mason, Scott F Smith, and Carolyn L Talcott. A foundation for actor computation. Journal of Functional Programming, 7(1):1-72, 1997. Google Scholar
  9. Joe Armstrong. Programming Erlang: Software for a Concurrent World. Pragmatic Bookshelf, 2007. Google Scholar
  10. Domagoj Babić, Lorenzo Martignoni, Stephen McCamant, and Dawn Song. Statically-directed dynamic automated test generation. In Proceedings of the 2011 International Symposium on Software Testing and Analysis, pages 12-22. ACM, 2011. Google Scholar
  11. Satish Chandra, Stephen J Fink, and Manu Sridharan. Snugglebug: a powerful approach to weakest preconditions. ACM Sigplan Notices, 44(6):363-374, 2009. Google Scholar
  12. Dominik Charousset, Raphael Hiesgen, and Thomas C Schmidt. Caf-the C++ actor framework for scalable and resource-efficient applications. In Proceedings of the 4th International Workshop on Programming based on Actors Agents and Decentralized Control, pages 15-28. ACM, 2014. Google Scholar
  13. Florence Charreteur and Arnaud Gotlieb. Constraint-based test input generation for java bytecode. In Software Reliability Engineering (ISSRE), 2010 IEEE 21st International Symposium on, pages 131-140. IEEE, 2010. Google Scholar
  14. Leonardo de Moura and Nikolaj Bjørner. Z3: An efficient smt solver. In C. R. Ramakrishnan and Jakob Rehof, editors, Tools and Algorithms for the Construction and Analysis of Systems, pages 337-340, Berlin, Heidelberg, 2008. Google Scholar
  15. Peter Dinges and Gul Agha. Targeted test input generation using symbolic-concrete backward execution. In Proceedings of the 29th ACM/IEEE international conference on Automated software engineering, pages 31-36. ACM, 2014. Google Scholar
  16. Josselin Feist, Laurent Mounier, and Marie-Laure Potet. Guided dynamic symbolic execution using subgraph control-flow information. In International Conference on Software Engineering and Formal Methods, pages 76-81. Springer, 2016. Google Scholar
  17. Pranav Garg, Franjo Ivancic, Gogul Balakrishnan, Naoto Maeda, and Aarti Gupta. Feedback-directed unit test generation for C/C++ using concolic execution. In Proceedings of the 2013 International Conference on Software Engineering, pages 132-141. IEEE Press, 2013. Google Scholar
  18. Istvan Haller, Asia Slowinska, Matthias Neugschwandtner, and Herbert Bos. Dowsing for overflows: A guided fuzzer to find buffer boundary violations. In USENIX Security Symposium, pages 49-64, 2013. Google Scholar
  19. Carl Hewitt. Viewing control structures as patterns of passing messages. Artificial intelligence, 8(3):323-364, 1977. Google Scholar
  20. Atsushi Igarashi, Benjamin C Pierce, and Philip Wadler. Featherweight Java: a minimal core calculus for Java and GJ. ACM Transactions on Programming Languages and Systems (TOPLAS), 23(3):396-450, 2001. Google Scholar
  21. Shams Imam and Vivek Sarkar. Savina-an actor benchmark suite. In 4th International Workshop on Programming based on Actors, Agents, and Decentralized Control, AGERE, 2014. Google Scholar
  22. Steven Lauterburg, Mirco Dotta, Darko Marinov, and Gul Agha. A Framework for State-Space Exploration of Java-Based Actor Programs. In Proceedings of the 2009 IEEE/ACM International Conference on Automated Software Engineering, ASE '09, pages 468-479, Washington, DC, USA, 2009. Google Scholar
  23. Shan Lu, Soyeon Park, Eunsoo Seo, and Yuanyuan Zhou. Learning from mistakes: a comprehensive study on real world concurrency bug characteristics. In ACM Sigplan Notices, volume 43, pages 329-339. ACM, 2008. Google Scholar
  24. Kin-Keung Ma, Khoo Yit Phang, Jeffrey Foster, and Michael Hicks. Directed symbolic execution. Static Analysis, pages 95-111, 2011. Google Scholar
  25. Paul Dan Marinescu and Cristian Cadar. Katch: high-coverage testing of software patches. In Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering, pages 235-245. ACM, 2013. Google Scholar
  26. Matthew Might, Yannis Smaragdakis, and David Van Horn. Resolving and exploiting the k-CFA paradox: illuminating functional vs. object-oriented program analysis. In ACM Sigplan Notices, volume 45, pages 305-315. ACM, 2010. Google Scholar
  27. Ana Milanova, Atanas Rountev, and Barbara G Ryder. Parameterized object sensitivity for points-to analysis for Java. ACM Transactions on Software Engineering and Methodology (TOSEM), 14(1):1-41, 2005. Google Scholar
  28. Stas Negara, Rajesh K Karmani, and Gul Agha. Inferring ownership transfer for efficient message passing. In ACM SIGPLAN Notices, volume 46, pages 81-90. ACM, 2011. Google Scholar
  29. Oswaldo Olivo, Isil Dillig, and Calvin Lin. Detecting and exploiting second order denial-of-service vulnerabilities in web applications. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 616-628. ACM, 2015. Google Scholar
  30. Carlos Pacheco, Shuvendu K. Lahiri, Michael D. Ernst, and Thomas Ball. Feedback-Directed Random Test Generation. In Proceedings of the 29th International Conference on Software Engineering, ICSE '07, pages 75-84, Washington, DC, USA, 2007. Google Scholar
  31. Andrea Rosà, Lydia Y Chen, and Walter Binder. Profiling actor utilization and communication in Akka. In Proceedings of the 15th International Workshop on Erlang, pages 24-32. ACM, 2016. Google Scholar
  32. Jan Schäfer and Arnd Poetzsch-Heffter. JCoBox: Generalizing Active Objects to Concurrent Components. In Theo D'Hondt, editor, ECOOP 2010 - Object-Oriented Programming, pages 275-299, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  33. Koushik Sen and Gul Agha. Automated systematic testing of open distributed programs. In International Conference on Fundamental Approaches to Software Engineering, pages 339-356. Springer, 2006. Google Scholar
  34. Koushik Sen, Darko Marinov, and Gul Agha. CUTE: a Concolic Unit Testing Engine for C. In Proceedings of the 10th European Software Engineering Conference Held Jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering, ESEC/FSE-13, pages 263-272, New York, NY, USA, 2005. Google Scholar
  35. Yannis Smaragdakis, Martin Bravenboer, and Ondrej Lhoták. Pick your contexts well: understanding object-sensitivity. In ACM SIGPLAN Notices, volume 46, pages 17-30. ACM, 2011. Google Scholar
  36. Samira Tasharofi, Peter Dinges, and Ralph E Johnson. Why do scala developers mix the actor model with other concurrency models? In European Conference on Object-Oriented Programming, pages 302-326. Springer, 2013. Google Scholar
  37. Samira Tasharofi, Rajesh K Karmani, Steven Lauterburg, Axel Legay, Darko Marinov, and Gul Agha. TransDPOR: A novel dynamic partial-order reduction technique for testing actor programs. In Formal Techniques for Distributed Systems, pages 219-234. Springer, 2012. Google Scholar
  38. Samira Tasharofi, Michael Pradel, Yu Lin, and Ralph Johnson. Bita: Coverage-guided, automatic testing of actor programs. In Automated Software Engineering (ASE), 2013 IEEE/ACM 28th International Conference on, pages 114-124. IEEE, 2013. Google Scholar
  39. Ganesha Upadhyaya and Hridesh Rajan. Effectively mapping linguistic abstractions for message-passing concurrency to threads on the Java virtual machine. ACM SIGPLAN Notices, 50(10):840-859, 2015. Google Scholar
  40. Carlos Varela and Gul Agha. Programming dynamically reconfigurable open systems with salsa. SIGPLAN Not., 36(12):20-34, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact