ABSTRACT
Thread-safe classes are pervasive in concurrent, object-oriented software. However, many classes lack documentation regarding their safety guarantees under multi-threaded usage. This lack of documentation forces developers who use a class in a concurrent program to either carefully inspect the implementation of the class, to conservatively synchronize all accesses to it, or to optimistically assume that the class is thread-safe. To overcome the lack of documentation, we present TSFinder, an approach to automatically classify classes as supposedly thread-safe or thread-unsafe. The key idea is to combine a lightweight static analysis that extracts a graph representation from classes with a graph-based classifier. After training the classifier with classes known to be thread-safe and thread-unsafe, it achieves an accuracy of 94.5% on previously unseen classes, enabling the approach to infer thread safety documentation with high confidence. The classifier takes about 3 seconds per class, i.e., it is efficient enough to infer documentation for many classes.
- {n. d.}. JBoss Platform issue 1416472.Google Scholar
- https://bugzilla.redhat.com/show_bug.cgi?id=1416472.Google Scholar
- {n. d.}. NX issue 239. https://track.radensolutions.com/issue/NX-239.Google Scholar
- {n. d.}. RESTEasy issue 1669. https://issues.jboss.org/browse/RESTEASY-1669.Google Scholar
- Rahul Agarwal, Liqiang Wang, and Scott D. Stoller. 2005. Detecting Potential Deadlocks with Static Analysis and Run-Time Monitoring. In Haifa Verification Conference, Vol. 3875. Springer, 191–207. Google ScholarDigital Library
- Glenn Ammons, Rastislav Bodík, and James R. Larus. 2002. Mining specifications. In Symposium on Principles of Programming Languages (POPL). ACM, 4–16. Google ScholarDigital Library
- Blake Anderson, Daniel Quist, Joshua Neil, Curtis Storlie, and Terran Lane. {n. d.}. Graph-based malware detection using dynamic analysis. 7, 4 ({n. d.}), 247–258. Google ScholarDigital Library
- Cyrille Artho, Klaus Havelund, and Armin Biere. 2003. High-level data races. Software Testing, Verification and Reliability 13, 4 (2003), 207–227.Google ScholarCross Ref
- Francesco A. Bianchi, Mauro Pezze, and Valerio Terragni. 2017. Reproducing Concurrency Failures from Crash Stacks. In FSE. Google ScholarDigital Library
- Karsten M. Borgwardt and Hans-Peter Kriegel. 2005. Shortest-Path Kernels on Graphs. In Proceedings of the Fifth IEEE International Conference on Data Mining (ICDM ’05). IEEE Computer Society, Washington, DC, USA, 74–81. Google ScholarDigital Library
- Karsten M. Borgwardt, Cheng Soon Ong, Stefan Schönauer, S. V. N. Vishwanathan, Alex J. Smola, and Hans-Peter Kriegel. 2005. Protein Function Prediction via Graph Kernels. Bioinformatics 21, 1 (Jan. 2005), 47–56. bioinformatics/bti1007 Google ScholarDigital Library
- Ulrik Brandes, Markus Eiglsperger, Ivan Herman, Michael Himsolt, and M. Scott Marshall. 2002. GraphML Progress Report Structural Layer Proposal. Springer Berlin Heidelberg, Berlin, Heidelberg, 501–512. 3-540-45848-4_59Google Scholar
- Sebastian Burckhardt, Pravesh Kothari, Madanlal Musuvathi, and Santosh Nagarakatte. 2010. A randomized scheduler with probabilistic guarantees of finding bugs. In Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). 167–178. Google ScholarDigital Library
- Jong-Deok Choi, Keunwoo Lee, Alexey Loginov, Robert O’Callahan, Vivek Sarkar, and Manu Sridharan. 2002. Efficient and Precise Datarace Detection for Multithreaded Object-Oriented Programs. In Conference on Programming Language Design and Implementation (PLDI). 258–269. Google ScholarDigital Library
- Ankit Choudhary, Shan Lu, and Michael Pradel. 2017. Efficient Detection of Thread Safety Violations via Coverage-Guided Generation of Concurrent Tests. In International Conference on Software Engineering (ICSE). Google ScholarDigital Library
- Orit Edelstein, Eitan Farchi, Yarden Nir, Gil Ratsaby, and Shmuel Ur. 2002. Multithreaded Java program test generation. IBM Systems Journal 41, 1 (2002), 111–125. Google ScholarDigital Library
- Michael D. Ernst, Alberto Lovato, Damiano Macedonio, Fausto Spoto, and Javier Thaine. 2016. Locking discipline inference and checking. In Proceedings of the 38th International Conference on Software Engineering, ICSE 2016, Austin, TX, USA, May 14-22, 2016. 1133–1144. Google ScholarDigital Library
- Cormac Flanagan and Stephen N. Freund. 2000. Type-based race detection for Java. 219–232.Google Scholar
- Cormac Flanagan and Stephen N. Freund. 2004. Atomizer: a dynamic atomicity checker for multithreaded programs. In Symposium on Principles of Programming Languages (POPL). ACM, 256–267. Google ScholarDigital Library
- Cormac Flanagan and Stephen N. Freund. 2009. FastTrack: efficient and precise dynamic race detection. In Conference on Programming Language Design and Implementation (PLDI). ACM, 121–133. Google ScholarDigital Library
- Cormac Flanagan and Shaz Qadeer. 2003. A type and effect system for atomicity. ACM, 338–349. Google ScholarDigital Library
- Eibe Frank, Mark A. Hall, Geoffrey Holmes, Richard Kirkby, and Bernhard Pfahringer. 2005. WEKA - A Machine Learning Workbench for Data Mining. In The Data Mining and Knowledge Discovery Handbook. 1305–1314.Google Scholar
- Mark Gabel and Zhendong Su. 2008. Javert: Fully Automatic Mining of General Temporal Properties from Dynamic Traces. In Symposium on Foundations of Software Engineering (FSE). ACM, 339–349. Google ScholarDigital Library
- Thomas Gärtner, Peter Flach, and Stefan Wrobel. 2003. On graph kernels: Hardness results and efficient alternatives. In Learning Theory and Kernel Machines. Springer, 129–143.Google Scholar
- Hugo Gascon, Fabian Yamaguchi, Daniel Arp, and Konrad Rieck. {n. d.}. Structural Detection of Android Malware Using Embedded Call Graphs. In Proceedings of the 2013 ACM Workshop on Artificial Intelligence and Security (2013) (AISec ’13). ACM, New York, NY, USA, 45–54. Google ScholarDigital Library
- Zaïd Harchaoui and Francis Bach. 2007. Image classification with segmentation graph kernels. In Computer Vision and Pattern Recognition, 2007. CVPR’07. IEEE Conference on. IEEE, 1–8.Google ScholarCross Ref
- Johannes Henkel, Christoph Reichenbach, and Amer Diwan. 2007. Discovering Documentation for Java Container Classes. IEEE Transactions on Software Engineering 33, 8 (2007), 526–543. Google ScholarDigital Library
- He Jiang, Jingxuan Zhang, Zhilei Ren, and Tao Zhang. 2017. An Unsupervised Approach for Discovering Relevant Tutorial Fragments for APIs. In Proceedings of the 39th International Conference on Software Engineering (ICSE ’17). IEEE Press, Piscataway, NJ, USA, 38–48. Google ScholarDigital Library
- Pallavi Joshi, Mayur Naik, Chang-Seo Park, and Koushik Sen. 2009. CalFuzzer: An Extensible Active Testing Framework for Concurrent Programs. In Conference on Computer Aided Verification. Springer, 675–681. Google ScholarDigital Library
- Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. 2003. Marginalized Kernels Between Labeled Graphs. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning (ICML’03). AAAI Press, 321–328. http://dl.acm.org/citation.cfm?id=3041838.3041879 Google ScholarDigital Library
- Risi Imre Kondor and John D. Lafferty. 2002. Diffusion Kernels on Graphs and Other Discrete Input Spaces. In Proceedings of the Nineteenth International Conference on Machine Learning (ICML ’02). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 315–322. http://dl.acm.org/citation.cfm?id=645531.655996 Google ScholarDigital Library
- Choonghwan Lee, Feng Chen, and Grigore Rosu. 2011. Mining Parametric Specifications. In International Conference on Software Engineering (ICSE). 591– 600. Google ScholarDigital Library
- Timothy C. Lethbridge, Janice Singer, and Andrew Forward. 2003. How Software Engineers Use Documentation: The State of the Practice. IEEE Software 20, 6 (2003), 35–39. Google ScholarDigital Library
- Zhenmin Li and Yuanyuan Zhou. 2005. PR-Miner: Automatically Extracting Implicit Programming Rules and Detecting Violations in Large Software Code. In European Software Engineering Conference and Symposium on Foundations of Software Engineering (ESEC/FSE). ACM, 306–315. Google ScholarDigital Library
- Z. Lin, H. Zhong, Y. Chen, and J. Zhao. 2016. LockPeeker: Detecting latent locks in Java APIs. In 2016 31st IEEE/ACM International Conference on Automated Software Engineering (ASE). 368–378. Google ScholarDigital Library
- Shan Lu, Joseph Tucek, Feng Qin, and Yuanyuan Zhou. 2006. AVIO: detecting atomicity violations via access interleaving invariants. In Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). ACM, 37–48. Google ScholarDigital Library
- Brandon Lucia and Luis Ceze. 2009. Finding concurrency bugs with contextaware communication graphs. In Symposium on Microarchitecture (MICRO). ACM, 553–563. Google ScholarDigital Library
- P. W. McBurney, S. Jiang, M. Kessentini, N. A. Kraft, A. Armaly, M. W. Mkaouer, and C. McMillan. 2017. Towards Prioritizing Documentation Effort. IEEE Transactions on Software Engineering PP, 99 (2017), 1–1. 2017.2716950Google Scholar
- Maged M Michael and Michael L Scott. 1996. Simple, fast, and practical nonblocking and blocking concurrent queue algorithms. In Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing. ACM, 267–275. Google ScholarDigital Library
- Madanlal Musuvathi, Shaz Qadeer, Thomas Ball, Gérard Basler, Piramanayagam Arumuga Nainar, and Iulian Neamtiu. 2008. Finding and Reproducing Heisenbugs in Concurrent Programs. In Symposium on Operating Systems Design and Implementation. USENIX, 267–280. Google ScholarDigital Library
- Mayur Naik, Chang-Seo Park, Koushik Sen, and David Gay. 2009. Effective static deadlock detection. In International Conference on Software Engineering (ICSE). IEEE, 386–396. Google ScholarDigital Library
- Adrian Nistor, Qingzhou Luo, Michael Pradel, Thomas R. Gross, and Darko Marinov. 2012. BALLERINA: Automatic Generation and Clustering of Efficient Random Unit Tests for Multithreaded Code. In International Conference on Software Engineering (ICSE). 727–737. Google ScholarDigital Library
- Robert O’Callahan and Jong-Deok Choi. 2003. Hybrid dynamic data race detection. In Symposium on Principles and Practice of Parallel Programming (PPOPP). ACM, 167–178. Google ScholarDigital Library
- Michael Pradel and Thomas R. Gross. 2009. Automatic Generation of Object Usage Specifications from Large Method Traces. In International Conference on Automated Software Engineering (ASE). 371–382. Google ScholarDigital Library
- Michael Pradel and Thomas R. Gross. 2012. Fully Automatic and Precise Detection of Thread Safety Violations. In Conference on Programming Language Design and Implementation (PLDI). 521–530. Google ScholarDigital Library
- Michael Pradel and Thomas R. Gross. 2013. Automatic Testing of Sequential and Concurrent Substitutability. In International Conference on Software Engineering (ICSE). 282–291. Google ScholarDigital Library
- Michael Pradel, Markus Huggler, and Thomas R. Gross. 2014. Performance Regression Testing of Concurrent Classes. In International Symposium on Software Testing and Analysis (ISSTA). 13–25. Google ScholarDigital Library
- Liva Ralaivola, Sanjay J Swamidass, Hiroto Saigo, and Pierre Baldi. 2005. Graph kernels for chemical informatics. Neural networks 18, 8 (2005), 1093–1110. Google ScholarDigital Library
- Jan Ramon and Thomas Gärtner. 2003. Expressivity versus efficiency of graph kernels. In Proceedings of the first international workshop on mining graphs, trees and sequences. 65–74.Google Scholar
- Inderjot Kaur Ratol and Martin P. Robillard. 2017. Detecting fragile comments. In Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering, ASE 2017, Urbana, IL, USA, October 30 - November 03, 2017. 112–122. Google ScholarDigital Library
- Martin P. Robillard. 2009. What Makes APIs Hard to Learn? Answers from Developers. IEEE Software 26, 6 (2009), 27–34. Google ScholarDigital Library
- Malavika Samak and Murali Krishna Ramanathan. 2014. Multithreaded Test Synthesis for Deadlock Detection. In Conference on Object-Oriented Programming ASE ’18, September 3–7, 2018, Montpellier, France Andrew Habib and Michael Pradel Systems, Languages and Applications (OOPSLA). 473–489. Google ScholarDigital Library
- Malavika Samak and Murali Krishna Ramanathan. 2015. Synthesizing tests for detecting atomicity violations. In ESEC/FSE. 131–142. Google ScholarDigital Library
- Malavika Samak, Murali Krishna Ramanathan, and Suresh Jagannathan. 2015. Synthesizing racy tests.. In PLDI. 175–185. Google ScholarDigital Library
- Malavika Samak, Omer Tripp, and Murali Krishna Ramanathan. 2016. Directed synthesis of failing concurrent executions. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2016, part of SPLASH 2016, Amsterdam, The Netherlands, October 30 - November 4, 2016. 430–446. Google ScholarDigital Library
- Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas E. Anderson. 1997. Eraser: A Dynamic Data Race Detector for Multithreaded Programs. ACM Transactions on Computer Systems 15, 4 (1997), 391–411. Google ScholarDigital Library
- Bernhard Schölkopf and Alexander J Smola. 2002. Learning with kernels: Support vector machines, regularization, optimization, and beyond. the MIT Press.Google Scholar
- Koushik Sen. 2008. Race directed random testing of concurrent programs. In Conference on Programming Language Design and Implementation (PLDI). ACM, 11–21. Google ScholarDigital Library
- Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. 2011. Weisfeiler-Lehman Graph Kernels. J. Mach. Learn. Res. 12 (Nov. 2011), 2539–2561. http://dl.acm.org/citation.cfm?id=1953048. Google ScholarDigital Library
- 2078187Google Scholar
- S Joshua Swamidass, Jonathan Chen, Jocelyne Bruand, Peter Phung, Liva Ralaivola, and Pierre Baldi. 2005. Kernels for small molecules and the prediction of mutagenicity, toxicity and anti-cancer activity. Bioinformatics 21, suppl 1 (2005), i359–i368. Google ScholarDigital Library
- Ewan Tempero, Craig Anslow, Jens Dietrich, Ted Han, Jing Li, Markus Lumpe, Hayden Melton, and James Noble. 2010. Qualitas Corpus: A Curated Collection of Java Code for Empirical Studies. In Asia Pacific Software Engineering Conference (APSEC). Google ScholarDigital Library
- Valerio Terragni and Shing-Chi Cheung. 2016. Coverage-Driven Test Code Generation for Concurrent Classes. In ICSE. Google ScholarDigital Library
- Yuan Tian, Ferdian Thung, Abhishek Sharma, and David Lo. 2017. APIBot: question answering bot for API documentation. In Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering, ASE 2017, Urbana, IL, USA, October 30 - November 03, 2017. 153–158. Google ScholarDigital Library
- Christoph Treude and Martin P. Robillard. 2016. Augmenting API Documentation with Insights from Stack Overflow. In Proceedings of the 38th International Conference on Software Engineering (ICSE ’16). ACM, New York, NY, USA, 392–403. Google ScholarDigital Library
- Raja Vallée-Rai, Phong Co, Etienne Gagnon, Laurie J. Hendren, Patrick Lam, and Vijay Sundaresan. 1999. Soot - a Java bytecode optimization framework. In Conference of the Centre for Advanced Studies on Collaborative Research (CASCON). IBM, 125–135. Google ScholarDigital Library
- S. V. N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, and Karsten M. Borgwardt. {n. d.}. Graph Kernels. 11 ({n. d.}), 1201–1242. http://dl.acm.org/citation. cfm?id=1756006.1859891Google Scholar
- Willem Visser, Klaus Havelund, Guillaume P. Brat, Seungjoon Park, and Flavio Lerda. 2003. Model Checking Programs. Automated Software Engineering 10, 2 (2003), 203–232. Google ScholarDigital Library
- Bimal Viswanath, M. Ahmad Bashir, Mark Crovella, Saikat Guha, Krishna P. Gummadi, Balachander Krishnamurthy, and Alan Mislove. 2014. Towards Detecting Anomalous User Behavior in Online Social Networks.. In USENIX Security. 223–238. Google ScholarDigital Library
- Christoph von Praun and Thomas R. Gross. 2001. Object Race Detection. In Conference on Object Oriented Programming, Systems, Languages and Applications (OOPSLA). 70–82. Google ScholarDigital Library
- Christoph von Praun and Thomas R. Gross. 2003. Static conflict analysis for multithreaded object-oriented programs. In Conference on Programming Languages Design and Implementation. ACM, 115–128. Google ScholarDigital Library
- C. Wagner, G. Wagener, R. State, and T. Engel. {n. d.}. Malware analysis with graph kernels and support vector machines. In 2009 4th International Conference on Malicious and Unwanted Software (MALWARE) (2009-10). 63–68. org/10.1109/MALWARE.2009.5403018Google ScholarCross Ref
- Liqiang Wang and Scott D. Stoller. 2006. Accurate and efficient runtime detection of atomicity errors in concurrent programs. In Symposium on Principles and Practice of Parallel Programming, (PPOPP). ACM, 137–146. Google ScholarDigital Library
- Takashi Washio and Hiroshi Motoda. 2003. State of the Art of Graph-based Data Mining. SIGKDD Explor. Newsl. 5, 1 (July 2003), 59–68. 959242.959249 Google ScholarDigital Library
- Andrzej Wasylkowski and Andreas Zeller. 2009. Mining Temporal Specifications from Object Usage. In International Conference on Automated Software Engineering (ASE). IEEE, 295–306. Google ScholarDigital Library
- Boris Weisfeiler and AA Lehman. 1968. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsia 2, 9 (1968), 12–16.Google Scholar
- John Whaley, Michael C. Martin, and Monica S. Lam. 2002. Automatic Extraction of Object-Oriented Component Interfaces. In Symposium on Software Testing and Analysis (ISSTA). ACM, 218–228. Google ScholarDigital Library
- Amy Williams, William Thies, and Michael D. Ernst. 2005. Static Deadlock Detection for Java Libraries. In European Conference on Object-Oriented Programming (ECOOP). Springer, 602–629. Google ScholarDigital Library
- Henry Wong and Scott Oaks. 2004. Java Threads (3rd edition ed.). O’Reilly Media, Inc.Google Scholar
- Min Xu, Rastislav Bodík, and Mark D. Hill. 2005. A serializability violation detector for shared-memory server programs. In Conference on Programming Language Design and Implementation (PLDI). ACM, 1–14. Google ScholarDigital Library
- Jinlin Yang, David Evans, Deepali Bhardwaj, Thirumalesh Bhat, and Manuvir Das. 2006. Perracotta: Mining temporal API rules from imperfect traces. In International Conference on Software Engineering (ICSE). ACM, 282–291. Google ScholarDigital Library
- Mu Zhang, Yue Duan, Heng Yin, and Zhiruo Zhao. {n. d.}. Semantics-Aware Android Malware Classification Using Weighted Contextual API Dependency Graphs. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security (2014) (CCS ’14). ACM, New York, NY, USA, 1105–1116. Google ScholarDigital Library
- Yu Zhou, Ruihang Gu, Taolue Chen, Zhiqiu Huang, Sebastiano Panichella, and Harald Gall. 2017. Analyzing APIs Documentation and Code to Detect Directive Defects. In Proceedings of the 39th International Conference on Software Engineering (ICSE ’17). IEEE Press, Piscataway, NJ, USA, 27–37. 2017.11 Google ScholarDigital Library
Index Terms
- Is this class thread-safe? inferring documentation using graph-based learning
Recommendations
Towards generating thread-safe classes automatically
ASE '20: Proceedings of the 35th IEEE/ACM International Conference on Automated Software EngineeringThe existing concurrency model for Java (or C) requires programmers to design and implement thread-safe classes by explicitly acquiring locks and releasing locks. Such a model is error-prone and is the reason for many concurrency bugs. While there are ...
Thread contracts for safe parallelism
PPoPP '11We build a framework of thread contracts, called Accord, that allows programmers to annotate their concurrency co-ordination strategies. Accord annotations allow programmers to declaratively specify the parts of memory that a thread may read or write ...
Inferring locks for atomic sections
PLDI '08: Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and ImplementationAtomic sections are a recent and popular idiom to support the development of concurrent programs. Updates performed within an atomic section should not be visible to other threads until the atomic section has been executed entirely. Traditionally, ...
Comments