Username   Password       Forgot your password?  Forgot your username? 


A Concurrent Harmful Races Identification Algorithm using Hadoop and Multiple Cloud Servers

Volume 14, Number 10, October 2018, pp. 2332-2342
DOI: 10.23940/ijpe.18.10.p9.23322342

Suxia Zhua,b, Yanan Wua,b, Guanglu Suna,b, and Jianda Suna

aSchool of Computer Science and Technology, Harbin University of Science and Technology, Harbin, 150080, China
bResearch Center of Information Security and Intelligent Technology, Harbin University of Science and Technology, Harbin, 150080, China

(Submitted on July 9, 2018; Revised on August 8, 2018; Accepted on September 15, 2018)


Data race is widespread in multi-thread programs and can lead to serious failures. To improve the reliability of programs, many race detectors have been proposed. However, most of the detectors use binary instrumentation to detect potential races, imposing higher runtime overhead. Most of the potential races are false positive, which consumes manual effort to identify the harmful races. In order to reduce runtime overhead of identifying harmful races, we propose two concurrent strategies that reduce runtime overhead from the detection potential races stage and the verification harmful races stage. Unlike previous work, the detection and verification races are in one execution. In this paper, the Hadoop distributed system is used to detect the potential races concurrently from the trace, and then the weighted Round-Robin algorithm is used to divide all potential races to multiple cloud servers. Harmful races are verified concurrently in multiple cloud servers by controlling thread scheduling. The experimental results show that our method for identifying harmful races is more efficient. Compared with RaceFuzzer and ReceChecker, the runtime overhead is reduced by an average of 72% and 46% respectively. In addition, a good speedup is achieved in this paper.


References: 22

                1. B. Kasikci, C. Zamfir, and G. Candea. “Data Races vs. Data Race Bugs: Telling the Difference with Portend,” ACM Sigarch Computer Architecture News, Vol. 40, No. 1, pp. 185-198, 2012
                2. Z. D. Wu, K. LU, and X. Wang, “Surveying Concurrency Bug Detectors based on Types of Detected Bugs,” Science China Information Sciences, Vol. 60, No. 3, pp. 031101, 2017
                3. Y. Shi, S. Park, Z. N. Yin, S. Lu, Y. Y. Zhou, W. G. Chen, et al., “Do I Use the Wrong Definition?: DeFuse: Definition-use Invariants for Detecting Concurrency and Sequential Bugs,” in Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, pp. 160-174, 2010
                4. Z. D. Wu, K. Lu, X. P. Wang, X. Zhou, and C. Chen, “PFinder: Efficiently Detecting Bugs in Concurrent Programs through Parallelizing Race Verification,” in Proceedings of International Conference on Computer Engineering & Systems, pp. 151-156, IEEE, 2015
                5. S. Lu, S. Park, E. Seo, and Y. Zhou, “Learning from Mistakes: A Comprehensive Study on Real World Concurrency Bug Characteristics,” in Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pp. 329-339, Seattle, WA, USA, 2008
                6. D. Engler, K. Ashcraft, “RacerX: Effective, Static Detection of Race Conditions and Deadlocks,” in Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP), pp. 237-252, 2003
                7. P. Pratikakis, J. S. Foster, and M. Hicks, “Locksmith: Practical Static Race Detection for C,” ACM Transactions on Programming Languages and Systems, Vol. 33, No. 3, pp. 1-55, 2011
                8. K. Serebryany and T. Iskhodzhanov, “ThreadSanitizer: Data Race Detection in Practice,” in Proceedings of the Workshop on Binary Instrumentation and Applications, pp. 62-71, New York, USA, 2009
                9. R. O’Callahan and J. -D. Choi, “Hybrid Dynamic Data Race Detection,” in Proceedings of ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 167-178, 2003
                10. K. Sen, “Race Directed Random Testing of Concurrent Programs,” in Proceedings of the 29th Annual ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pp. 11-21, 2008
                11. K. Lu, Z. Wu, X. Wang, C. Chen, and X. Zhou, “RaceChecker: Efficient Identification of Harmful Data Races,” in Proceedings of Euromicro International Conference on Parallel, Distributed and Network-Based Processing, pp. 78-85, IEEE Computer Society, 2015
                12. Z. D. Wu, K. Lu, X. P. Wang, X. Zhou, and C. Chen, “Detecting Harmful Data Races Through Parallel Verification,” Journal of Supercomputing, Vol. 71, No. 8, pp. 2922-2943, 2015
                13. Z. Xu, L. Kai, W. Xiaoping, and L. Xu, “Exploiting Parallelism in Deterministic Shared Memory Multi-Processing,” Journal of Parallel and Distributed Computing, Vol. 72, No. 5, pp. 716-727, 2012
                14. K. Shvachko, H. Kuang, S. Radia, et al. “The Hadoop Distributed File System,” in Proceedings of IEEE Conference on Mass Storage Systems and Technologies, pp. 1-10, IEEE Computer Society, 2010
                15. J. Y. Wang, T. Wang, Z. Y. Yang, Y. Mao, N. F. Mi, and B. Sheng, “SEINA: A Stealthy and Effective Internal Attack in Hadoop Systems,” in Proceedings of International Conference on Computing, Networking and Communications, Santa Clara, CA, USA, 2017
                16. Z. Ding, R. Wang, J. Hu, and Y. Liu, “Detecting Bugs of Concurrent Programs with Program Invariants,” in Proceedings of IEEE International Conference on Software Quality, Reliability and Security Companion, pp. 1-15, 2016
                17. Z. Wu, K. Lu, and X. Wang, “Identifying Repeated Interleavings to Improve the Efficiency of Concurrency Bug Detectionm,” in Proceedings of International Conference on Algorithms and Architectures for Parallel Processing, pp. 175-188, Springer International Publishing, 2015
                18. T. White and D. Cutting. “Hadoop: The Definitive Guide,” O’reilly Media Inc Gravenstein Highway North, Vol. 215, No. 11, pp. 1-4, 2012
                19. C. K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, et al., (2005) “Pin: Building Customized Program Analysis Tools with Dynamic Instrumentation,” in Proceedings of the 26th annual ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pp. 190-200, 2005
                20. R. L. Ma, H. Jang, and Q. X. Zhang, “An Improved Fast Searching Method of Hash Table,” Computer Engineering & Science, Vol. 30, No. 9, pp. 66-68, 2008
                21. S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta, “The SPLASH-2 Programs: Characterization and Methodological Considerations,” in Proceedings of the 22th Annual International Symposium on Computer Architecture (ISCA), pp. 24-36, 1995
                22. J. W. Voung, R. Jhala, and S. Lerner, “RELAY: Static Race Detection on Millions of Lines of Code,” in Proceedings of the 15th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE), pp. 205-214, Cavtat near Dubrovnik, Croatia, 2007


                              Please note : You will need Adobe Acrobat viewer to view the full articles.Get Free Adobe Reader

                              This site uses encryption for transmitting your passwords.