Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Một phương pháp hiệu quả để phát hiện lỗi đồng thời trong các chương trình hướng đối tượng
Tóm tắt
Các bộ xử lý đa lõi và đa luồng đã trở thành tiêu chuẩn cho các bộ xử lý hiện đại. Do đó, các chương trình đồng thời ngày càng trở nên phổ biến mặc dù việc viết và hiểu chúng là một thách thức. Mặc dù lỗi rất dễ xuất hiện trong mã đồng thời, nhưng các phương pháp phát hiện lỗi truyền thống như kiểm tra mô hình, chứng minh định lý và phân tích mã không thể mở rộng một cách hiệu quả cho các chương trình đồng thời. Kiểm thử là một kỹ thuật không thể thiếu để phát hiện lỗi đồng thời, nhưng nó đòi hỏi rất nhiều công việc thủ công và không hiệu quả. Bài báo này trình bày một phương pháp tự động để phát hiện lỗi đồng thời trong các lớp của ngôn ngữ lập trình hướng đối tượng. Phương pháp này sử dụng một thuật toán heuristic để tự động tạo ra các trường hợp kiểm thử có thể kích hoạt lỗi hiệu quả. Sau đó, mỗi trường hợp kiểm thử được thực thi tự động và một phương pháp nhanh chóng được áp dụng để xác định lỗi đồng thời thực sự từ các kết quả thực thi bất thường. Chúng tôi đã triển khai một nguyên mẫu của phương pháp và áp dụng nó cho một số lớp Java điển hình. Đánh giá cho thấy phương pháp của chúng tôi hiệu quả và nhanh hơn so với công trình trước đó.
Từ khóa
#lỗi đồng thời #chương trình hướng đối tượng #kiểm thử tự động #thuật toán heuristic #JavaTài liệu tham khảo
Godefroid P, Nagappan N. Concurrency at Microsoft: an exploratory survey. In: Workshop on Exploiting Concurrency Efficiently and Correctly, Princeton, 2008
Poulsen K. Tracking the blackout bug Security Focus. 2004-04-07. http://www.securityfocus.com/news/8412
Leveson N G. SafeWare: System Safety and Computers. Boston: Addison-Wesley Professional, 1995
McDowell C E, Helmbold D P. Debugging concurrent programs. ACM Comput Surv, 1989, 4: 593–622
Musuvathi M, Qadeer S. Iterative context bounding for systematic testing of multithreaded programs. ACM SIGPLAN Not, 2007, 6: 446–455
Flanagan C, Freund S. FastTrack: efficient and precise dynamic race detection. ACM SIGPLAN Not, 2009, 44: 121–133
Park S, Vuduc R W, Harrold M J. Falcon: fault localization in concurrent programs. In: Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering, Cape Town, 2010. 245–254
Park S, Lu S, Zhou Y. CTrigger: exposing atomicity violation bugs from their hiding places. ACM SIGPLAN Not, 2009, 44: 25–36
Burckhardt S, Kothari P, Musuvathi M, et al. A randomized scheduler with probabilistic guarantees of finding bugs. ACM SIGPLAN Not, 2010, 45: 167–178
Coons K E, Burckhardt S, Musuvathi M. GAMBIT: effective unit testing for concurrency libraries. ACM SIGPLAN Not, 2010, 45: 15–24
Pradel M, Gross T R. Fully automatic and precise detection of thread safety violations. ACM SIGPLAN Not, 2012, 47: 521–530
Schildt H. Java 7 the Complete Reference. 8th Ed. New York: Mc-Graw Hill, 2011
Lu S, Park S, Seo E, et al. Learning from mistakes: a comprehensive study on real world concurrency bug characteristics. ACM SIGPLAN Not, 2008, 43: 329–339
Shacham O, Bronson N, Aiken A, et al. Testing atomicity of composed concurrent operations. ACM SIGPLAN Not, 2011, 46: 51–64
Nistor A, Luo Q, Pradel M, et al. Ballerina: automatic generation and clustering of efficient random unit tests for multithreaded code. In: ICSE 2012 Proceedings of the 2012 International Conference on Software Engineering, Piscataway, 2012. 727–737
Marino D, Musuvathi M, Narayanasamy S. LiteRace: effective sampling for lightweight data-race detection. ACM SIGPLAN Not, 2009, 44: 134–143
Praun C V, Gross T R. Object race detection. ACM SIGPLAN Not, 2001, 36: 70–82
Callahan R O, Choi J D. Hybrid dynamic data race detection. ACM SIGPLAN Not, 2003, 38: 167–178
Flanagan C, Freund S N, Yi J. Velodrome: a sound and complete dynamic atomicity checker for multithreaded programs. ACM SIGPLAN Not, 2008, 43: 293–303
Lu S. Finding atomicity-violation bugs through unserializable interleaving testing. IEEE Trans Softw Eng, 2012, 38: 844–860
Naik M, Park C S, Sen K, et al. Effective static deadlock detection. In: ICSE’ 09 Proceedings of the 31st International Conference on Software Engineering, Vancouver, 2009. 386–396
Joshi S, Lahiri S K, Lal A. Underspecified harnesses and interleaved bugs. ACM SIGPLAN Not, 2012, 47: 19–30
Herlihy M, Wing J M. Linearizability: a correctness condition for concurrent objects. ACM Trans Program Lang Syst, 1990, 12: 463–492
Burckhardt S, Dern C, Musuvathi M, et al. Line-Up: a complete and automatic linearizability checker. ACM SIGPLAN Not, 2010, 45: 330–340
Godefroid P, Klarlund N, Sen K. DART: directed automated random testing. ACM SIGPLAN Not, 2005, 40: 213–223
Pacheco C, Lahiri S K, Ernst M D, et al. Feedback-directed random test generation. In: ICSE’ 07 Proceedings of the 29th international conference on Software Engineering, Minneapolis, 2007. 75–84
Krishnamoorthy S, Hsiao M S, Lingappan L. Strategies for scalable symbolic execution-driven test generation for programs. Sci China Inf Sci, 2011, 54: 1797–1812