João Lourenço
Changing the world, one student at a time…
Computer Science Department, NOVA School of Science and Technology, NOVA University Lisbon, Quinta da Torre, P-2829-516 CAPARICA, Portugal — joao.lourenco [AT] fct [DOT] unl [DOT] pt (email)
Detection of Transactional Memory Anomalies using Static Analysis
- Citation:
- Teixeira, B., J. M. Lourenço, E. Farchi, R. J. Dias, and D. Sousa, "Detection of Transactional Memory Anomalies using Static Analysis", Proceedings of the 8th Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging (PADTAD'10), New York, NY, USA, ACM, pp. 26–36, 2010.
Abstract:
Transactional Memory allows programmers to reduce the number of synchronization errors introduced in concurrent programs, but does not ensures its complete elimination. This paper proposes a pattern matching based approach to the static detection of atomicity violation, based on a path-sensitive symbolic execution method to model four anomalies that may affect Transactional Memory programs. The proposed technique may be used to to bring to programmer's attention pairs of transactions that the programmer has mis-specified, and should have been combined into a single transaction. The algorithm first traverses the AST tree, removing all the non-transactional blocks and generating a trace tree in the path sensitive manner for each thread. The trace tree is a Trie like data structure, where each path from root to a leaf is a list of transactions. For each pair of threads, erroneous patterns involving two consecutive transactions are then checked in the trace tree. Results allow to conclude that the proposed technique, although triggering a moderate number of false positives, can be successfully applied to Java programs, correctly identifying the vast majority of the relevant erroneous patterns.
Download PDF:
