臺灣博碩士論文加值系統

對於並行程式而言，非決定性行為代表即使給予相同的輸入值，在多次執行的過程中仍可能產出不同的執行結果。非決定性行為導因於：並行程式給予相同輸入的多次執行中，內部指令具有多種執行順序。因此如何儘可能地找出所有執行順序、達到完整測試，一直是測試並行程式時的主要課題。然而當程式中具有忙碌等待迴圈而衍生重複進入相同狀態時，程式執行將衍生無窮多種執行順序，造成無法對所有執行順序完整測試。此論文提出一動態測試方法，藉由執行所有可達的狀態與狀態間轉移，充分測試具有迴圈行為的並行程式。相較於驗證並行程式時常用的模型檢驗方法，本文提出的測試方法具有：毋須對受測程式預先靜態分析，並降低與受測程式間的程式語言耦合度等優點。測試過程中僅需分析程式執行後產生的同步行為序記錄，用以分析執行中的競爭行為並限制執行時的狀態走訪情形；因此我們提出的測試方法將更易於根據需求移植至其他程式語言。最後透過實驗數據，我們將實證此種針對具有迴圈行為並行程式的充分測試可被系統化地完成。

Concurrent programs exhibit nondeterministic behavior in that multiple executions thereof with the same input might produce different sequences of synchronization events and different results. This is because different executions of a concurrent program with the same input may exhibit different interleavings. Thus, one of the major issues in the testing of concurrent programs is how to explore different interleavings or exhaust all the possible interleavings of the target programs. However, for terminating concurrent programs that have cyclic state spaces due to using iterative statements such as busy-waiting loops, they might have an infinite number of feasible synchronization sequences; that is, there is an infinite number of possible interleavings, which makes it impossible to explore all the possible interleavings for this type of concurrent program. To overcome this problem, we propose a testing scheme called dynamic effective testing that can perform state-cover testing for nondeterministic terminating concurrent programs with an infinite number of synchronization sequences. Dynamic effective testing does not require static analysis of the target concurrent program or the assistance of a model checker, and thus is loosely coupled to the syntax of the target concurrent program. It only needs to analyze sequences of synchronization events produced by the execution of the concurrent programs for race detection and state-traversal control. Therefore, the method is easy to port to different programming languages. The implementation and experimental results obtained with real code demonstrate that source-code-level dynamic testing can be systematically performed on nondeterministic concurrent programs with infinite synchronization sequences.

Table of Contents i
List of Figures iii
中文摘要 vi
Abstract vii
Chapter 1. Introduction 1
1.1. Different types of testing for concurrent programs 2
1.2. Model-checking free techniques 4
Chapter 2. Related Works 10
2.1. Reachability testing 11
2.2. CHESS and dynamic partial order reduction 13
Chapter 3. Problems in Concurrent Testing 15
3.1. The termination problem 15
4.1. Boundless state reiteration problem 17
Chapter 4. Dynamic Termination Decision 24
4.1. Termination-dependency relationship 24
4.2. Without considering the termination-dependency relationship 26
4.3. With considering the termination-dependency relationship 29
Chapter 5. Effective Test Set and Dynamic Effective Testing 42
5.1. The execution state and effective test set 42
5.2. The framework for dynamic effective testing 46
5.3. Transformation of SYN-sequences to implement dynamic effective testing 47
5.4. Implementation of transformation function  based on the partial ordering of synchronization events 65
5.4.1. The information required about synchronization events for dynamic effective testing 65
5.4.2. Deriving a unique totally ordered sequence of execution states from a SYN-sequence 69
5.5. Event compression for busy-waiting loops 75
5.6. Derivation of A Simplified Reachable State Graph 79
Chapter 6. Extension for Single-Port-Multiple-Receivers Message-Passing Concurrent Programs 85
6.1. The shortcoming of traditional race-table algorithm 86
6.2. The proposed solution 88
6.3. A Running Example 91
6.4. The correctness of the proposed scheme 93
Chapter 7. Implementation and experimental results 102
7.1. Experimental results of dynamic termination decision 102
7.2. Experimental results of dynamic effective testing 103
Chapter 8. Conclusions and future work 110
References 112
Appendix A 120
Appendix B 122

1. C. E. McDowell and D. P. Helmold, “Debugging Concurrent Programs,” ACM Computing Surveys, Volume 21, Issue 4, pp. 593-622, December 1989. DOI = http://dx.doi.org/10.1145/76894.76897.
2. K.-C. Tai and R. H. Carver, “Testing of Distributed Programs,” Chapter 33 in Parallel and Distributed Computing Handbook, McGraw-Hill, 1996. ISBN 0070730202.
3. A. Dinning, “A Survey of Synchronization Methods for Parallel Computers,” IEEE Computer, Volume 22, Issue 7, pp. 66-77, July 1989. DOI = http://dx.doi.org/10.1109/2.30733.
4. A. Silberschatz, P. B. Galvin, and G. Gagne. Operating System Concepts (8th Edition). Wiley, 2008. ISBN 0471417432.
5. W. R. Adrion, M. A. Branstad, and J. C. Cherniavsky, “Validation, Verification, and Testing of Computer Software,” ACM Computing Surveys, Volume 14, Issue 2, pp. 159-192, June 1982. DOI = http://dx.doi.org/10.1145/356876.356879.
6. R. S. Pressman. Software Engineering: A Practitioner’s Approach (5th Edition). McGraw-Hill Education, 2000. ISBN 978-0071181822.
7. D. Heimbold and D. Luckham, “Debugging Ada Tasking Programs,” IEEE Software, Volume 2, Issue 2, pp. 47-57, March 1985. DOI = http://dx.doi.org/10.1109/MS.1985.230351.
8. K.-C. Tai, “Testing of Concurrent Software,” In Proceedings of the 13th Annual International Computer Software and Applications Conference, pp. 62-64, 1989. DOI = http://dx.doi.org/10.1109/CMPSAC.1989.65057.
9. J. Gait, “A Probe Effect in Concurrent Programs,” Software: Practice and Experience, Volume 15, Issue 3, pp. 225-233, March 1986. DOI = http://dx.doi.org/10.1002/spe.4380160304.
10. S. D. Stoller, “Testing Concurrent Java Programs Using Randomized Scheduling,” In Proceedings of the 2nd Workshop on Runtime Verification (RV’02), Electronic Notes in Theoretical Computer Science, Volume 70, Issue 4, pp. 142-157, December 2002. DOI = http://dx.doi.org/10.1016/S1571-0661(04)80582-6.
11. Y. Eytani, E. Farchi, and Y. Ben-Asher, “Heuristics for Finding Concurrent Bugs,” In Proceedings of the International Parallel and Distributed Processing Symposium, 2003. DOI = http://dx.doi.org/10.1109/IPDPS.2003.1213514.
12. O. Edelstein, E. Farchi, Y. Nir, G. Ratsaby, and S. Ur, “Multithreaded Java Program Test Generation,” IBM Systems Journal, Volume 41, Issue 1, pp. 111–125, 2002. DOI = http://dx.doi.org/10.1147/sj.411.0111.
13. R. N. Taylor, “A General-Purpose Algorithm for Analyzing Concurrent Programs,” Communications of the ACM, Volume 26, Issue 5, pp. 361-376, May 1983. DOI = http://dx.doi.org/10.1145/69586.69587.
14. M. Young and R. N. Taylor, “Combining Static Concurrency Analysis with Symbolic Execution,” IEEE Transactions on Software Engineering, Volume 14, Number 10, pp. 1499-1511, October 1988. DOI = http://dx.doi.org/10.1109/32.6195.
15. C. E. McDowell, “A Practical Algorithm for Static Analysis of Parallel Programs,” Journal of Parallel and Distributed Computing, Volume 6, Issue 3, pp. 515-536, June 1989. DOI = http://dx.doi.org/10.1016/0743-7315(89)90004-X.
16. R. Carver and K.-C. Tai, “Deterministic Execution Testing of Concurrent Ada Programs,” In Proceedings of the Conference on Tri-Ada '89: Ada Technology in Context: Application, Development, and Deployment, pp. 528-544, 1989. DOI = http://dx.doi.org/10.1145/74261.74301.
17. R. Carver and K.-C. Tai, “Replay and Testing for Concurrent Programs,” IEEE Software, Volume 8, Issue 2, pp. 66-74, March 1991. DOI = http://dx.doi.org/10.1109/52.73751.
18. J. Chen and S. MacDonald, “Testing Concurrent Programs Using Value Schedules,” In Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE’07), pp. 313-322, November 2007. DOI = http://dx.doi.org/10.1145/1321631.1321678.
19. C. Harvey and P. Strooper, “Testing Java Monitors through Deterministic Execution,” In Proceedings of the 13th Australian Software Engineering Conference (ASWEC'01), pp. 61-67, 2001. DOI = http://dx.doi.org/10.1109/ASWEC.2001.948498.
20. B. Long, D. Hoffman, and P. Strooper, “Tool Support for Testing Concurrent Java Components,” IEEE Transactions on Software Engineering, Volume 29, Issue 6, pp. 555-566, June 2003. DOI = http://dx.doi.org/10.1109/TSE.2003.1205182.
21. W. Pugh and N. Ayewah, “Unit Testing Concurrent Software,” In Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE’07), pp. 513-516, 2007. DOI = http://dx.doi.org/10.1145/1321631.1321722.
22. E. M. Clarke, O. Grumberg, and D. Peled. Model Checking. The MIT Press, December 1999. ISBN 9780262032704.
23. M. Huth and M. Ryan. Logic in Computer Science: Modelling and Reasoning about Systems. Cambridge University Press, August 2004. ISBN 978-0521543101.
24. Java PathFinder. http://babelfish.arc.nasa.gov/trac/jpf.
25. K. Havelund, “Using Runtime Analysis to Guide Model Checking of Java Programs,” In Proceedings of SPIN Model Checking and Software Verification (SPIN 2000), Lecture Notes in Computer Science, Volume 1885, pp. 245-264, 2000. DOI = http://dx.doi.org/10.1007/10722468_15.
26. MAGIC website. http://www.cs.cmu.edu/~chaki/magic/.
27. S. Chaki, J. Ouaknine, K. Yorav, and E Clarke, “Automated Compositional Abstraction Refinement for Concurrent C Programs: A Two-Level Approach,” In Proceedings of Workshop on Software Model Checking (SoftMC 2003), Electronic Notes in Theoretical Computer Science, Volume 89, Issue 3, pp. 417-432, September 2003. DOI = http://dx.doi.org/10.1016/S1571-0661(05)80004-0.
28. CHESS: Find and Reproduce Heisenbugs in Concurrent Programs. http://research.microsoft.com/en-us/projects/chess/.
29. M. Musuvathi, S. Qadeer, and T. Ball. CHESS: A Systematic Testing Tool for Concurrent Software, Microsoft Research Technical Report MSR-TR-2007-149, 2007.
30. G.-H. Hwang. A Systematic Parallel Testing Method for Concurrent Programs. Master Thesis, Institute of Computer Science and Information Engineering, National Chiao-Tung University, Taiwan, 1993.
31. G.-H. Hwang, K.-C. Tai, and T.-L. Huang, “Reachability Testing: An Approach to Testing Concurrent Software,” International Journal of Software Engineering and Knowledge Engineering, Volume 5, Issue 4, pp. 493-510, December 1995. DOI = http://dx.doi.org/ 10.1142/S0218194095000241.
32. G.-H. Hwang, S.-J. Chang, and H.-D. Chu, “Technology for Testing Nondeterministic Client/Server Database Applications,” IEEE Transactions on Software Engineering, Volume 30, Number 1, pp. 59-77, January 2004. DOI = http://dx.doi.org/10.1109/TSE.2004.1265736.
33. K.-C. Tai, “Reachability Testing of Asynchronous Message-passing Programs,” In Proceedings of the 2nd International Workshop on Software Engineering for Parallel and Distributed Systems, pp. 50-61, 1997. DOI = http://dx.doi.org/10.1109/PDSE.1997.596826.
34. Y. Lei and K.-C. Tai, “Efficient Reachability Testing of Asynchronous Message-Passing Programs,” In Proceedings of the 8th IEEE International Conference on Engineering for Complex Computer Systems, pp. 35-44, 2002. DOI = http://dx.doi.org/10.1109/ICECCS.2002.1181496.
35. R. H. Carver and Y. Lei, “A General Model for Reachability Testing of Concurrent Programs,” In Proceedings of Formal Methods and Software Engineering (ICFEM 2004), Lecture Notes in Computer Science, Volume 3308, pp. 76-98, 2004. DOI = http://dx.doi.org/10.1007/978-3-540-30482-1_14.
36. Y. Lei and R. H. Carver, “Reachability Testing of Concurrent Programs,” IEEE Transactions on Software Engineering, Volume 32, Issue 6, pp. 382-403, June 2006. DOI = http://dx.doi.org/10.1109/TSE.2006.56.
37. K. Sen and G. Agha, “Automated Systematic Testing of Open Distributed Programs,” In Proceedings of the 9th International Conference on Fundamental Approaches to Software Engineering (FASE 2006), Lecture Notes in Computer Science, Volume 3922, pp. 339-356, March 2006. DOI = http://dx.doi.org/10.1007/11693017_25.
38. T. J. LeBlanc and J. M. Mellor-Crummey, “Debugging Parallel Programs with Instant Replay,” IEEE Transactions on Computers, Volume C-36, Issue 4, pp. 471-482, April 1987. DOI = http://dx.doi.org/10.1109/TC.1987.1676929.
39. K. Sen, “Effective Random Testing of Concurrent Programs,” In Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE’07), pp. 323-332, 2007. DOI = http://dx.doi.org/10.1145/1321631.1321679.
40. P. Joshi, M. Naik, C.-S. Park, and K. Sen, “CALFUZZER: An Extensible Active Testing Framework for Concurrent Programs,” In Proceedings of the 21st International Conference on Computer Aided Verification (CAV'09), Lecture Notes in Computer Science, Volume 5643, pp. 675-681, 2009. DOI = http://dx.doi.org/10.1007/978-3-642-02658-4_54.
41. ConTest - A Tool for Testing Multi-threaded Java Applications. http://www.haifa.ibm.com/projects/verification/contest/.
42. O. Edelstein, E. Farchi, E. Goldin, Y. Nir, G. Ratsaby, and S. Ur, “ConTest - A User's Perspective,” In Proceesings of the 5th International Conference on Achieving Quality in Software (AQUIS 2002), 2002.
43. Y. Nir-Buchbinder and S. Ur, “Multithreaded Unit Testing with ConTest.” http://www.ibm.com/developerworks/java/library/j-contest.html.
44. R. H. Carver and Y. Lei, “Distributed Reachability Testing of Concurrent Programs,” Concurrency and Computation: Practice and Experience, Volume 22, Issue 18, pp. 2445-2466, December 2010. DOI = http://dx.doi.org/10.1002/cpe.1573.
45. Y. Lei, R. H. Carver, R. Kacker, and D. Kung, “A Combinatorial Testing Strategy for Concurrent Programs,” Software Testing, Verification and Reliability, Volume 17, Issue 4, pp. 207-225, December 2007. DOI = http://dx.doi.org/10.1002/stvr.369.
46. M. Musuvathi and S. Qadeer, “Fair Stateless Model Checking,” In Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI’08), pp. 362-371, 2008. DOI = http://dx.doi.org/10.1145/1375581.1375625.
47. M. Musuvathi and S. Qadeer, “Iterative Context Bounding for Systematic Testing of Multithreaded Programs,” In Proceedings of ACM Conference on Programming Language Design and Implementation (PLDI’07), pp. 446-455, 2007. DOI = http://dx.doi.org/10.1145/1250734.1250785.
48. G. J. Holzmann, “Tracing Protocols,” AT&;T Technical Journal, Volume 64, Number 10, pp. 2413-2433, December 1985.
49. P. Godefroid, G. J. Holzmann, and D. Pirottin, “State-space Caching Revisited,” Formal Methods in System Design, Volume 7, Issue 3, pp. 227-241, November 1995. DOI = http://dx.doi.org/10.1007/BF01384077.
50. P. C. Dillinger and P. Manolios, “Fast, All-Purpose State Storage,” In Proceedings of the 16th SPIN Workshop, Model Checking Software, Lecture Notes in Computer Science, Volume 5578, pp. 12-31, 2009. DOI = http://dx.doi.org/10.1007/978-3-642-02652-2_6.
51. C. Flanagan and P. Godefroid, “Dynamic Partial-order Reduction for Model Checking Software,” In Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’05), pp. 110-121, 2005. DOI = http://dx.doi.org/10.1145/1040305.1040315.
52. Y. Yang, X. Chen, G. Gopalakrishnan, and R. M. Kirby, “Efficient Stateful Dynamic Partial Order Reduction,” In Proceedings of the 15th SPIN Workshop, Model Checking Software, Lecture Notes in Computer Science, Volume 5156, pp. 288-305, 2008. DOI = http://dx.doi.org/10.1007/978-3-540-85114-1_20.
53. C. Tian, V. Nagarajan, R. Gupta, and S. Tallam, “Automated Dynamic Detection of Busy-wait Synchronizations,” Software: Practice and Experience, Volume 39, Issue 11, pp. 947-972, August 2009. DOI = http://dx.doi.org/10.1002/spe.922.
54. A. M. Ben-Amram and C. S. Lee, “Program Termination Analysis in Polynomial Time,” ACM Transactions on Programming Languages and Systems (TOPLS), Volume 29, Issue 1, January 2007. DOI = http://dx.doi.org/10.1145/1180475.1180480.
55. M. Bruynooghe, M. Codish, J. P. Gallagher, S. Genaim, and W. Vanhoof, “Termination Analysis of Logic Programs Through Combination of Type-Based Norms,” ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 29, Issue 2, April 2007. DOI = http://dx.doi.org/10.1145/1216374.1216378.
56. M. Sipser, Section 5.1: Undecidable Problems from Program Theory, Introduction to the Theory of Computation (3rd Edition), Course Technology, 2012. ISBN 113318779X
57. R. W. Sebesta. Concepts of Programming Languages (10th Edition), Addison-Wesley, 2012. ISBN 0131395319
58. A. V. Aho, R. Sethi, and J. D. Ullman. Compilers Principles, Techniques, and Tools (2nd Edition), Prentice Hall, 2006. ISBN 0321486811
59. A. Ho, S. Smith, and S. Hand. On Deadlock, Livelock, and Forward Progress, Technical Report, UCAM-CL-TR-633, University of Cambridge, Computer Laboratory, May 2005.
60. K.-C. Tai, “Definitions and Detection of Deadlock, Livelock, and Starvation in Concurrent Programs,” In Proceedings of the 1994 International Conference on Parallel Processing – Volume 2, ICPP '94, pp. 69-72, August 1994. DOI = http://dx.doi.org/10.1109/ICPP.1994.84.
61. R. Kirner, “On the Halting Problem of Finite-State Programs,” In Proceedings of the 14. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'07), October 2007.
62. L. Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System,” Communications of the ACM, Volume 21, Issue 7, pp. 558-565, July 1978. DOI = http://dx.doi.org/10.1145/359545.359563.
63. A. B. Kahn, “Topological Sorting of Large Networks,” Communications of the ACM, Volume 5, Issue 11, pp. 558–562, November 1962. DOI = http://dx.doi.org/10.1145/368996.369025.
64. O. Vernet and L. Markenzon, “Hamiltonian Problems for Reducible Flowgraphs,” In Proceedings of the 17th International Conference of the Chilean Computer Science Society (SCCC 1997), pp. 264–267, November 1997. DOI = http://dx.doi.org/10.1109/SCCC.1997.637099.
65. G. L. Peterson, “Myths About the Mutual Exclusion Problem,” Information Processing Letters, Volume 12, Number 3, pp. 115-116, June 1981.
66. J. Bloch. Effective Java (2nd Edition), Addison-Wesley, May 2008. ISBN 978-0321356680
67. B. Goetz, T. Peierls, J. Bloch, and J. Bowbeer. Java Concurrency in Practice, Addison-Wesley, May 2006. ISBN 978-0321349606
68. Y.-Y. Li. The Formal Verification of SYN-Sequence Generated in Dynamic Testing, Master Thesis, Department of Computer Science and Information Engineering, National Taiwan Normal University, Taiwan, 2009.
69. V. K. Garg, “Enumerating Global States of a Distributed Computation,” In Proceedings of International Conference on Parallel and Distributed Computing Systems (PDCS 2003), pp. 134-139, November 2003.
70. Graphviz - Graph Visualization Software. http://www.graphviz.org/.
71. E. W. Dijkstra. Cooperating Sequential Processes, Technical Report, Technological University, Eindhoven, the Netherlands, 1965.
72. N. Rungta and E. G. Mercer, “Clash of The Titans: Tools and Techniques for Hunting Bugs in Concurrent Programs,” In Proceedings of the 7th Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging (PADTAD’09), 2009. DOI = http://dx.doi.org/10.1145/1639622.1639631.
73. L.-T. Tsao. Dynamic Testing for Non-determinisitc Service-Oriented Architecture Application, Master Thesis, Department of Computer Science and Information Engineering, National Taiwan Normal University, Taiwan, 2009.
74. Web Services Architecture, W3C Working Group Note, 11 February, 2004. http://www.w3.org/TR/ws-arch/.
75. Web Services Business Process Execution Language Version 2.0, OASIS Standard, 11 April, 2007. http://docs.oasis-open.org/wsbpel/2.0/OS/wsbpel-v2.0-OS.html.
76. G.-H. Hwang, C.-S. Lin, L.-T. Tsao, K.-H. Chen, and Y.-Y. Li, “A Framework and Language Support for Automatic Dynamic Testing of Workflow Management Systems,” In Proceedings of the 3rd IEEE International Symposium on Theoretical Aspects of Software Engineering (TASE 2009), pp. 139-146, July 2009. DOI = http://dx.doi.org/10.1109/TASE.2009.22.
77. K. Heljanko, “Model Checking with Finite Complete Prefixes Is PSPACE-Complete,” In Proceedings of the 11th International Conference on Concurrency Theory (CONCUR 2000), Lecture Notes in Computer Science, Volume 1877, pp. 108-122, 2000. DOI = http://dx.doi.org/10.1007/3-540-44618-4_10.
78. J. C. King, “Symbolic Execution and Program Testing,” Communications of the ACM, Volume 19, Issue 7, pp. 385-394, July 1976. DOI = http://dx.doi.org/10.1145/360248.360252.
79. W. R. Stevens. UNIX Network Programming, Volume 2: Interprocess Communications (2nd Edition), Prentice Hall, March 2012. ISBN 978-0132974295
80. Java Message Service Specification, Version 1.1, Sun Microsystems, April 2002.
81. L. Lamport, "A New Solution of Dijkstra's Concurrent Programming Problem," Communication of the ACM, Volume 17, Number 8. pp. 453-455, August 1974. DOI = http://dx.doi.org/10.1145/361082.361093.