臺灣博碩士論文加值系統

在軟體測試上，我們的reachability testing[1]主要就是針對並行程式來作分析測試的，它最主要的目的就是要把所有同步事件的interleaves找出來以供使用者分析參考，針對這一方面的研究，有提高效能的，也有向外應用的研究，例如web service、dynamic effective testing、多核心競爭的分析等等。
　　這項研究主要的目的就是改進reachability testing系統的效能，在提高reachability testing系統效能上的議題也蠻多人作研究。在現實生活中，我們所測試的並行程式軟體，一定會相當的龐大，在跑reachability testing 會很耗時，有的時候也許會是五、六個小時，大者甚至一個禮拜左右，像這樣我們一定要提升這個系統的效能，對著此系統作假設、省略和一些演算法的改進。我的研究最主要是針對reachability testing裡的prefix-based replay作改進，保留目前執行的狀態，到下次執行prefix-based replay的時候，利用restore state的方法直接到目的地去執行replay，使用這樣的方式去提高我們reachability testing的效能。目前對提高效能的方面已經有相當的成果了，在未來的工作是要跟目前dynamic effective testing作整合 ，也可以在裡面利用此方法，來作更進一步的提高效率的功能。

In software testing, our reachability testing [1] for concurrent program is mainly for testing, which main purpose is to find out all the interleaves for user analysis of reference for research in this area, there are improve the performance, but also from outside the application of research, such as web service, dynamic effective testing, analysis of multi-core competition and so on.
　　The main purpose of this study is to improve the effectiveness of the system reachability testing, reachability testing system to improve performance also were the subject of further study. In real life, we have a concurrent software, and it will be quite large. Running reachability testing will be very time-consuming, and some time may be five or six hours, or even the largest of about a week like this. We enhance the effectiveness of the system, make any assumptions at this system, omitted, and some algorithm improvements. My research is mainly in the reachability testing for prefix-based replay for improvement. It would retain the current status of execution to the next prefix-based replay ,it would jump directly to the destination to do it, and use this method to accelerate reachability testing. At present, this method has been in the fine performance of the experimental results.In future work, it would be with the current dynamic effective testing for integration, it could also use this method to further improve the efficiency they provide.

中文摘要 ....................................................................................................................... I
ABSTRACT ................................................................................................................. II
1. 簡介 ........................................................................................................................... 1
1.1 SOFTWARE TESTING ............................................................................................ 2
1.1.1 Static analysis............................................................................................. 4
1.1.2 Dynamic testing ......................................................................................... 5
1.2 APPROACHES TO TESTING CONCURRENT SOFTWARE .......................................... 5
1.2.1 Nondeterministic Testing ........................................................................... 6
1.2.2 Deterministic Testing ................................................................................. 7
1.2.3 Reachability Testing ................................................................................... 8
1.2.4 Model Checking ....................................................................................... 12
1.2.5 Dynamic Effective testing(DET) ............................................................. 12
1.2.6 State Storing in Prefix-Based Replay ...................................................... 16
2. 文獻探討 .............................................................................................................. 19
2.1 REACHABILITY TESTING ................................................................................... 19
2.2 RACE GRAPH .................................................................................................... 20
2.3 TESTING CONCURRENT PROGRAMS USING VALUE SCHEDULES .......................... 21
3. 實作方法 ................................................................................................................ 24
3.1 設計STATE ....................................................................................................... 25
3.2 針對ENTRY和EXIT PROTOCOL的修改 ........................................................... 28
3.3 RESTORE和STORE STATE的時間點 ................................................................ 31
3.4 PREFIX-BASED REPLAY主程式裡面的修改 .............................................................. 37 IV
3.5 特殊的並行程式 ................................................................................................................ 41
4. 實驗結果 .............................................................................................................. 47
5. 討論和未來工作 .................................................................................................. 59
6. REFERENCES .................................................................................................... 60

[1] G. H. Hwang, K.C. Tai, and T.L. Huang, "Reachability Testing: An Approach To Testing Concurrent Software", Int’l J. Software Eng. and Knowledge Eng., vol. 5, no. 4, pp. 493-510, Dec. 1995.
[2] Abraham Silberschatz, Peter Baer Galvin, and Greg Gagne,"Operating System Concepts", John Wiley & Sons, ISBN: 0471417432, 6th edition (June 26, 2001).
[3] K.C. Tai and Richard H. Carver,"Testing of Distributed Programs", Chapter 33 in Parallel and Distributed Computing Handbook, editor A. Y. Zomaya, McGraw-Hill, 1996.
[4] Gwan-Hwan Hwang, Sheng-Jen Chang, and Huey-Der Chu, "Technology for Testing Nondeterministic Client/Server Database Applications", IEEE Transaction on Software Engineering, Volume 30, Number 1, pp. 59-77, Jan., 2004.
[5] L. Peterson, "Myths About the Mutual Exclusion Problem", Information Processing Letters, Volume 12, Number 3 (1981).
[6] S. Y. Hsu and C. G. Chung,"A heuristic approach to path selection problem in concurrent program testing", Proc. 3rd IEEE Workshop on Future Trends of Distributed Computing System(1992) pp. 86-92.
[7] K. C. Tai, R. H. Carver, "Use of sequencing constraints for specifying, testing and debugging concurrent programs", Proc. 1994 Int. Conf. Parallel and Distributed Systems (December 1994) pp. 280-287.
[8] R. N. Taylor, D. L. Levine, and C. D. Kelly, "Structural testing of concurrent programs", IEEE Trans. Softw. Eng. 18,3(1992) 206-215,
[9] R. D. Yang and C.G. Chung, "Path analysis testing of concurrent programs",Information and Software Technology 34, 1(1992) 43-56.
[10] Richard N. Taylor, "A General-Purpose Algorithm for Analyzing Concurrent Programs", Communication of the ACM, Volume 21, Number 7, July 1978.
[11] Michael Young and Richard N. Taylor, "Combining Static Concurrency Analysis with Symbolic Execution", IEEE Transaction on Software Engineering, Volume 14, Number 10, October 1988.
[12] Charles E. McDowell, "A Practical Algorithm for Static Analysis of Parallel Programs", Journal of Parallel and Distributed Computing, 6, 515-536(1989).
[13] G.J. Holzmann. The Model Checker SPIN. IEEE Trans. Soft. Engin., Vol.23, No.5, pages 279–295, May 1997.
[14] J. Burch, E. Clarke, K. McMillan, D. Dill, and L. Hwang. Symbolic model checking: 1020 states and beyond. In IEEE Symposium on Logic in Computer Science, pages 428-439, 1990.
[15] JavePathFinder page, http://javapathfinder.sourceforge.net/.
[16] A. Pnueli. A temporal logic of concurrent programs.
[17] Jun Chen, Steve MacDonald,"Testing Concurrent Programs using Value Schedules",ASE’07.November 5-9,2007.
[18] Soot, http://www.sable.mcgill.ca/soot/