請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46239完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 王凡(Farn Wang) | |
| dc.contributor.author | Tzu-Hsiang Lin | en |
| dc.contributor.author | 林子翔 | zh_TW |
| dc.date.accessioned | 2021-06-15T04:59:27Z | - |
| dc.date.available | 2010-08-02 | |
| dc.date.copyright | 2010-08-02 | |
| dc.date.issued | 2010 | |
| dc.date.submitted | 2010-07-27 | |
| dc.identifier.citation | [1] Linux device drivers. http://www.jollen.org/blog/2006/05/linux 1.html.
[2] L. Bergroth, H. Hakonen, and T. Raita. A survey of longest common subsequence algorithms. In SPIRE, pages 39–48, 2000. [3] P. Berkhin. Survey of clustering data mining techniques. Technical report, Accrue Software, San Jose, CA, 2002. [4] K. Burr andW. Young. Combinatorial test techniques: Table-based automation, test generation and code coverage. In Proceedings of the Intl. Conf. on Software Testing Analysis and Review, pages 503–513. West, 1998. [5] G. J. Carrette. Crashme: Random input testing, 1996. http://people.delphiforums.com/gjc/crashme.html. [6] K.-H. Cheng. Testing system software with shell commands and user-assistance. 2009. [7] D. M. Cohen, S. R. Dalal, J. Parelius, and G. C. Patton. The combinatorial design approach to automatic test generation. IEEE Software, 13(5):83–88, 1996. [8] S. Devadas, A. Ghosh, and K. Keutzer. An observability-based code coverage metric for functional simulation. In ICCAD, pages 418–425, 1996. [9] D. Maier. The complexity of some problems on subsequences and supersequences. J. ACM, 25(2):322–336, April 1978. [10] Methods for Testing and Specification (MTS), The Testing and Test Control Notation version 3 - Parts 1-8. ETSI ES 201 873-1 v3.2.1, Feb. 2007. [11] B. P. Miller, G. Cooksey, and F. Moore. An empirical study of the robustness of macos applications using random testing. Operating Systems Review, 41(1):78–86, 2007. [12] G. J. Myers. The Art of Software Testing. John Wiley & Sons, Inc., 1979. [13] M. M. Tikir and J. K. Hollingsworth. Efficient instrumentation for code coverage testing. In ISSTA, pages 86–96, 2002. [14] F. Wang. Redlib. http://sourceforge.net/projects/redlib/. [15] F. Wang. Redlib for the formal verification of embedded systems. In ISOLA ’06: Proceedings of the Second International Symposium on Leveraging Applications of Formal Methods, Verification and Validation, pages 341–346, Washington, DC, USA, 2006. IEEE Computer Society. [16] F. Wang and Y.-C. Lee. Automatic black-box regression testing for checking bug fixes. 2009. [17] F. Wang, Geng-Dian Huang. Test Plan Generation for Concurrent Real-Time Systems based on Zone Coverage Analysis. TESTCOM/FATES 2008, June 2008, Tokyo. LNCS 5047, Springer-Verlag. [18] F. Wang, G.-D. Huang, F. Yu. Symbolic Simulation of Real-Time Concurrent Systems. RTCSA2003, LNCS 2968, Springer-Verlag. [19] F. Wang, G.-D. Huang, Fang Yu. Numerical Coverage Estimation for Dense-Time Systems. in proceedings of FORTE’2003, LNCS 2767, Springer-Verlag. [20] R. Williamson. Stress-testing the linux kernel - a design process for standard- ized testing of linux, 2004. http://www.ibm.com/developerworks/linux/library/l- stress/index.html. [21] R.M. Haralick and L.G. Shapiro. Computer and Robot Vision, pages 29–31Addison-Wesley, 1993. [22] T. Back and D.B Fogel and Z Michalewicz. Evolutionary Computation 1: Basic Algorithms and Operators, pages181-182 Institute of Physics Publishing, Bristol, 2000. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46239 | - |
| dc.description.abstract | 利用RED LIB對系統程式進行自動化測試
作業系統的核心是一個很複雜的系統，其中包含了許多軟體的互動和運作上面的協調，若要對核心中的一個檔案或元件做測試，會因為使用者無法直接對待測物件操作，必須經由使用者層的應用程式來替代，使得測試過程更加困難。 將待測物及作業系統轉換成我們定義的模型語言，藉由待測物模型與作業系統模型間的互動取代軟硬體及作業系統的互動，以達到自動化測試，提高測試的效率，並降低測試成本。 當我們有待測物的模型與測試案例(test case)，要測試程式覆蓋率(coverage ratio)，一般會將測試案例一一輸入後再統計覆蓋率多高，但當測試案例的數量一多就會花費相當多的時間，又如果測試案例為隨機亂數產生的，其中可能有許多相似的案例，所以我們提出將測試案分類後再將從每類中抽出案例樣本來進行覆蓋率測試，以減少花費在相似性高的案例上的時間。 我們利用基因演算法去找出最佳分類法，我們認為相似的案例執行後，會走過類似的模型或是函數，因此我們利用字串比對作為分類的依據，再利用基因演算法找出最佳分類，經過訓練後我們只抽出每類中的某些案例來執行，不但降低許多執行時間，也可以達到將所有案例執行後的覆蓋率。針對同一個待測物，即使換了一組全新的測試案例我們也不需再次訓練，直接使用先前訓練後的結果也可達到效果。 | zh_TW |
| dc.description.abstract | We propose kernel code coverage analysis on model testing instead of testing on user application software, system software, and perform the testing on generating the commands in command line interfaces. In our approach, we can gain much higher coverage ratio than the used testing approach. We also can save more testing time or testing cost and save important information or error message when system crash occurs.
We also propose an approach use a genetic algorithm to find a appropriate way to clustering those test cases, so that testers don’t need to run every test case; they just pick few test cases from every cluster to run, and they can evaluate the whole test case bases will gain how much coverage ratio. For the same target, there is no need to train again, we can just follow the rule we have found to clustering. Our technique provides a more efficient and more accurate way to analyze coverage ratio. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T04:59:27Z (GMT). No. of bitstreams: 1 ntu-99-R97943152-1.pdf: 2538958 bytes, checksum: 178a6b1a7a598fd04d93c3d2878aab9a (MD5) Previous issue date: 2010 | en |
| dc.description.tableofcontents | CONTENTS
口試委員會審定書 # 誌謝 i 中文摘要 ii ABSTRACT iii CONTENTS iv LIST OF FIGURES vi LIST OF TABLES viii Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Purpose 1 1.3 Contribution 2 1.4 Thesis organization 3 Chapter 2 Related Work 4 Chapter 3 Framework of Model Based Kernel Code Testing 5 Chapter 4 Background 8 4.1 REDLIB & Pathg 8 4.2 Linux kernel and Linux device drivers 8 4.3 The Longest Common Subsequence 9 4.4 Genetic algorithms 10 4.5 Total correlation index 11 4.6 Tournament selection 13 Chapter 5 Model building 14 5.1 Framework of Kernel Software Testing 14 5.2 Communicating timed automata 15 5.3 How to build a model 17 5.3.1 Function call 17 5.3.2 Branches 20 5.3.3 Loop 23 5.4 Advantage of Model Based kernel testing 28 Chapter 6 Genetic Algorithm on Test Case Selection 30 6.1 Test case 30 6.2 Test case generation 31 6.3 Correlation indices based on communication 32 6.4 Test Case Cluster 32 6.4.1 Notation 34 6.4.2 Connected components analysis 37 6.4.3 Refinement 38 6.5 Training of tester for the fittest weightings 40 Chapter 7 Experiment 44 7.1 Coverage ratio 44 7.2 Weighting Training 45 7.3 Comparison 51 Chapter 8 Conclusion 55 Bibliography…………. 56 LIST OF FIGURES Fig. 1.1 the way testers used to estimating coverage ratio 2 Fig. 3.1 the framework of this work 5 Fig. 3.2 weighting training procedure 6 Fig. 3.3 test case generator 7 Fig. 4.1 the illustration of user mode, kernel mode and hardwares 9 Fig. 5.1 Communications in software testing 14 Fig. 5.2 specification of a bus-contending protocol 16 Fig. 5.3 function implement with synchronizer 18 Fig. 5.4 the model graph of synchronizer 18 Fig. 5.5 function implement with procedural call 19 Fig. 5.6 if-else structure in C language and model 20 Fig. 5.7 the model graph of if structure 21 Fig. 5.9 the model graph of switch structure 22 Fig. 5.8 switch structure in C language and model 22 Fig. 5.11 the model graph of while structure 23 Fig. 5.10 while structure in C language and model 23 Fig. 5.13 the model graph of while structure 24 Fig. 5.12 do-while structure in C language and model 24 Fig. 5.15 the model graph of for loop structure 25 Fig. 5.14 for loop structure in C language and model 25 Fig. 5.16 break structure in C language and model 26 Fig. 5.17 the model graph of for break structure 27 Fig. 5.18 continue structure in C language and model 27 Fig. 5.19 the model graph of for continue structure 28 Fig. 6.1 the distance between two points 36 Fig. 6.2 connected components analysis 37 Fig. 6.3 data after connected components analysis 38 Fig. 6.4 data after refinement clustering 39 Fig. 6.5 training flow 40 Fig. 7.1 md.c - weighting sets in generation 1 45 Fig. 7.2 md.c - weighting sets in generation 10 46 Fig. 7.3 md.c - weighting sets in generation 20 46 Fig. 7.4 md.c - weighting sets in generation 30 46 Fig. 7.5 md.c - weighting sets in generation 40 47 Fig. 7.6 md.c - weighting sets in generation 50 47 Fig. 7.7 md.c - variance of each weighting 48 Fig. 7.8 file.c - weighting sets in generation 1 48 Fig. 7.9 file.c - weighting sets in generation 10 49 Fig. 7.10 file.c - weighting sets in generation 20 49 Fig. 7.11 file.c - weighting sets in generation 30 49 Fig. 7.12 file.c - weighting sets in generation 40 50 Fig. 7.13 file.c - weighting sets in generation 50 50 Fig. 7.14 file.c - variance of each weighting 51 Fig. 7.15 the result of md.c-set 1 52 Fig. 7.16 the result of md.c-set 2 53 Fig. 7.17 the result of md.c-set 4 53 Fig. 7.18 the result of md.c-set 5 54 LIST OF TABLES Table 4.1 tournament selection 13 Table 6.1 clustering procedure 33 Table 6.2 the TCI value of received port 34 Table 6.3 the TCI value of sent port 35 Table 6.4 refinement procedure 40 Table 6.5 training procedure 42 Table 7.1 md.c - variance of each weighting 48 Table 7.2 file.c - variance of each weighting 50 Table 7.3 md.c – test case data base 52 Table 7.4 the weightings is training by md.c training set 1 52 | |
| dc.language.iso | en | |
| dc.subject | 模型測 | zh_TW |
| dc.subject | 測試案例 | zh_TW |
| dc.subject | 覆蓋率 | zh_TW |
| dc.subject | 基因演算法 | zh_TW |
| dc.subject | test case | en |
| dc.subject | genetic algorithm | en |
| dc.subject | model testing | en |
| dc.subject | coverage ratio | en |
| dc.title | 利用基因演算法挑選測試案例於系統核心模型上覆蓋率分析 | zh_TW |
| dc.title | Application of Genetic Algorithm on Test Case Selection against State Coverage of Kernel Code | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 98-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 陳俊壯,王勝德,廖純中,黃鐘揚 | |
| dc.subject.keyword | 基因演算法,覆蓋率,模型測,測試案例, | zh_TW |
| dc.subject.keyword | genetic algorithm,coverage ratio,model testing,test case, | en |
| dc.relation.page | 57 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2010-07-29 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
| 顯示於系所單位： | 電子工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-99-1.pdf 未授權公開取用 | 2.48 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。