Trace Generation and Deterministic Execution for Concurrent Programs

• Paulo Souza USP
• Raphael Batista USP
• Simone Souza USP
• Rafael Prado USP
• George Dourado USP
• Julio Estrella USP

DOI: https://doi.org/10.5753/wscad.2016.14256

Resumo

This paper proposes new algorithms for generation of trace files and deterministic execution of concurrent programs under test. The proposed algorithms are essential to automate the coverage testing of concurrent programs and allow to execute new synchronizations automatically, increasing the source code coverage with focus on non-determinism, and edges of communication and synchronization. Our algorithms consider programs with multiple paradigms of communication and synchronization (collective, blocking and non-blocking point-to-point message passing, and shared memory). We validate our algorithms by means of experiments based on nine representative benchmarks, which exercise non-trivial aspects of synchronization found in real applications. Our algorithms have a robust behaviour and meet their objectives. We also highlight the overhead generated with the algorithms.

Referências

Alpern, B., Ngo, T., Choi, J.-D., and Sridharan, M. (2000). Dejavu: Deterministic java replay debugger for jalape˜no java virtual machine. In OOPSLA '00, pages 165–166, NY. ACM.

Bergan, T., Anderson, O., Devietti, J., Ceze, L., and Grossman, D. (2010). Coredet: a compiler and runtime system for deterministic multithreaded exe- cution. In ASPLOS 2010, volume 38, pages 53–64. ACM.

Carver, R. and Lei, Y. (2010). A class library for implementing, testing, and debugging concurrent programs. International Journal on Software Tools for Technology Transfer, 12(1):69–88.

Carver, R. and Tai, K.-C. (1991). Replay and testing for concurrent programs. Software, IEEE, 8(2):66–74.

Dourado, G. G. M., Souza, P. S. L., Prado, R. R., Batista, R. N., Souza, S., Estrella, J., Bruschi, S., and Lourenco, J. M. S. (2016). A suite of java message-passing benchmarks to support the validation of testing models criteria and tools. In ICCS 2016, volume 80, pages 2226–2230. Elsevier.

Lei, Y. and Carver, R. (2006). Reachability testing of concurrent programs. IEEE T. on Software Engineering, 32(6):382–403.

Liu, T., Curtsinger, C., and Berger, E. D. (2011). Dthreads: efcient deterministic multithreading. In SOSP 2011, pages 327–336. ACM.

Musuvathi, M., Qadeer, S., Ball, T., Basler, G., Nainar, P. A., and Neamtiu, I. (2008). Finding and reproducing heisenbugs in concurrent programs. In OSDI 2008, pages 267–280, Berkeley. USENIX.

Prado, R. R., Souza, P. S., Dourado, G. G. M., Senger, S. R. S., Es- trella, J. C., Bruschi, S. M., and Lourenco, J. (2015). Extracting static and dynamic structural information from java concurrent programs for coverage testing. In CLEI 2015, pages 1–8, Arequipa. IEEE.

Sarmanho, F. S., Souza, P. S., Souza, S. R., and Simão, A. S. (2008). Structural testing for semaphore-based multithread programs. In ICCS 2008, pages 337–346, Berlin. Springer-Verlag.

Souza, P. S., Souza, S. R., and Zaluska, E. (2014). Structural testing for message-passing concurrent programs: an extended test model. Concurrency and Computation: Practice and Experience, 26(1):21–50.

Souza, P. S., Souza, S. S., Rocha, M. G., Prado, R. R., and Batista, R. N. (2013). Data ow testing in concurrent programs with message passing and shared memory paradigms. Elsevier, 18(0):149 – 158. ICCS 2013.