臺灣博碩士論文加值系統

In modern life, applications of embedded systems have become popular. Therefore, methods by which to test them have become important issues. Conventional software testing has become a well-known issue, but the testing for embedded software is different from computer software testing. In the case of computer software, whether there is any bug in the development application is the only consideration; that is to say, libraries, the operating system, drivers, and hardware do not require consideration. Further, the execution speed of a computer is usually faster than the speed of an embedded system, so computer software testing is constrained much less by execution speed and memory size. Fortunately, an embedded system is usually designed for only a few tasks, so it is not as complex as a computer. In this thesis, we propose an interface interaction test model to generate test case sequences that can detect faults from the application layer to the driver layer. First, we define embedded software interfaces and collect messages between each interface in the embedded software. Next, we use all messages to construct message sequence charts (MSCs) and a finite state machine that is semantically equivalent to MSCs. Finally, we can generate test case sequences from a global finite state machine.

嵌入式系統的應用在現代生活中隨處可見，於是如何測試變成了重要的議題。傳統的軟體測試已經是個熟知的問題，但是嵌入式軟體測試與電腦軟體測試截然不同。對於電腦軟體而言，通常只需要考慮開發的應用程式本身是否有錯誤，也就是說並不需要考慮函式庫、作業系統、驅動程式和硬體。而且電腦的執行速度通常比嵌入式系統來的快，所以電腦軟體在測試方面受到執行速度和記憶體容量的限制也較少。慶幸的是，嵌入式系統一般只提供少數功能，所以也不會像電腦般複雜。本篇論文中，我們提出了一個介面互動測試模型來產生能偵測從應用層到驅動層錯誤的測試個案序列。首先，藉由訂義嵌入式軟體的介面並收集介面間的訊息傳遞，然後利用消息序列圖將訊息表達成圖表，接著再將圖表轉換成等價的有限狀態機。最後，再利用有限狀態機產生出測試個案序列。

Abstract in Chinese i
Abstract ii
Acknowledgements iii
Content iv
List of Tables vii
List of Figures viii
Chapter 1 Introduction 1
Chapter 2 Related Work 4
2.1 Embedded System and Embedded Software Testing 4
2.2 Interface Test Model 6
2.3 Message Sequence Chart 8
Chapter 3 Enhanced Interface Interaction Test Model 10
3.1 Event-Oriented Specification Language 11
3.2 System Interface Definition 13
3.3 MSC Structure Building 14
3.4 GFSM Construction 20
Chapter 4 Experiment 28
4.1 Experimental Environment 28
4.2 Experimental Results and Analysis 31
4.2.1 Case Study: Framebuffer Viewer 31
4.2.2 Criteria and Metrics 34
4.2.3 Experimental Analysis 36
Chapter 5 Conclusions and Future Work 40
References 42
Appendix 45
A. Experimental Environment 45
B. 32-Bit Instruction Format 45

[1] J. W. Grenning, Test-Driven Development for Embedded C, Oreilly & Associates Inc, May 2011.

[2] B. Broekman, E. Notenboom, Testing Embedded Software, Addison-Wesley Professional, December 2002.

[3] E. Sutter, Embedded System Firmware Demystified, CMP, 2002.

[4] G. J. Myers, The Art of Software Testing, John Wiley&Sons, Inc, 2004.

[5] A.A Jerraya, W. Wolf, “Hardware/Software Interface Codesign for Embedded Systems,” IEEE Computer, pp.63-69, 2005.

[6] A. Sung, B. Choi, S. Shin, “An Interface Test Model for Hardware-dependent Software and Embedded OS API of the Embedded System,” Computer Standards & Interface, Vol.29, pp.430-443, 2007.

[7] J. Seo, A. Sung, B. Choi, S. Kang, “Automating Embedded Software Testing on an Emulated Target Board,” Proceeding of Automation of Software Test Minneapolis, USA, 20-26 May 2007.

[8] ITU-T Recommendation Z.120 Message Sequence Chart (MSC), 1999.

[9] H. Abelson, G. J. Sussman, Structure and Interpretation of Computer Programs, MIT Press, 2 edition, 1996.

[10] D. Harel, “Statecharts: A Visual Formalism for Complex Systems,” Science of Computer Programming, pp.231-274, 1987.

[11] OMG Unified Modeling Language (OMG UML), Superstructure: V2.1.1, 2007.

[12] ITU-T Recommendation Z.100 Specification and Description Language (SDL), 1999.

[13] Ferenc Belina, Dieter Hogrefe, Amardeo Sarma, “SDL with Applications from Protocol Specification”, Prentice Hall International, 1991

[14] R. B. Binder, “Design for Testability in Object-Oriented Systems,” Comm. ACM, pp.87-100, September, 1994.

[15] R. Love, Linux Kernel Development, Developer’s Library, Sams, 1stedition, 2003.

[16] A. Rubini, G. Kroah-Hartman, J. Corbet, Linux Device Drivers, O’RELLY, 3rdedition, 2001.

[17] N. H. Lee, S. D. Cha, “Generating Test Sequences from A Set of MSCs,” Computer Networks, New York, USA, Vol. 42, Issue 3, pp. 405-417, June 2003.

[18] R. Alur and M. Yannakakis, “Model Checking of Message Sequence Charts,” Proceedings of the Tenth International Conference on Concurrency Theory, pp. 114–129, 1999.

[19] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd edition, The MIT Press, 2001.

[20] Embedded GNU C Library, http://www.eglibc.org/home

[21] The Linux kernel archives, http://www.kernel.org/

[22] A. Simao, A. Petrenko, J.C. Maldonado, "Comparing finite state machine test," Software, IET , vol.3, no.2, pp.91-105, April 2009.

[23] S. Goren, F.J. Ferguson, "Testing finite state machines based on a structural coverage metric," Test Conference, 2002. Proceedings. International , vol., no., pp. 773- 780, 2002

[24] D. Lee and M. Yannakakis. ”Principles and Methods of Testing Finite State Machines-A Survey,” Proceedings of the IEEE, 84(8): 1090-1123, 1996.

[25] . M. Memon and Q. Xie, Q., “Studying the Fault-Detection Effectiveness of GUI Test Cases for Rapidly Evolving Software,” IEEE Transactions on Software Engineering, Vol. 31, No. 10, pp. 884-896, 2005.
[26] Y. S. Ma, J. Offutt, and Y. R. Kwon, “MuJava: A Mutation System for Java,” Proceedings of the 28th International Conference on Software Engineering, pp.827-830, Shanghai, China, 2006.

[27] G. Rothermel, R. H. Untch, C. Chu, and M. J. Harrold, “Prioritizing Test Cases For Regression Testing,” IEEE Transactions on Software Engineering, Vol. 27, No. 10, pp.929-948, Oct 2001.

[28] P. R. Srivastava, “Test Case Prioritization,” Journal of Theoretical and Applied Information Technology, Vol. 4, No. 3, pp. 178-181, Mar 2008.

[29] A. G. Malishevsky, J.R. Ruthruff, G. Rothermel, and S.Elbaum, “Cost-cognizant Test Case Prioritization,” Technical Report TR-UNL-CSE-2006-0004, University of Nebraska-Lincoln, Mar 2006.

[30] M. J. Rummel, G. M. Kapfhammer, and A. Thall, “Towards the Prioritization of Regression Test Suites with Data Flow Information,” In Proceedings of the 20th Symposium on Applied Computing, pp.1499-1504, Santa Fe, New Mexico, USA, 13-17 Mar. , 2005.