Sách 'Introduction to Combinatorial Testing' - Kuhn, Kacker & Lei về kỹ thuật kiểm thử tổ hợp

• Tác giả: D. Richard Kuhn
• Chuyên ngành: Kiểm thử phần mềm
• Đề tài: Giới thiệu về kiểm thử tổ hợp
• Loại tài liệu: Sách giáo khoa
• Năm xuất bản: 2013
• Địa điểm: Boca Raton

Tóm tắt

I. Tổng quan về kiểm thử tổ hợp trong kỹ thuật phần mềm

Kiểm thử tổ hợp là phương pháp kiểm thử phần mềm dựa trên việc tạo ra các tổ hợp giá trị đầu vào để phát hiện lỗi. Phương pháp này xuất phát từ thực tế rằng phần lớn lỗi phần mềm do sự tương tác giữa hai hoặc nhiều tham số gây ra. Thay vì kiểm tra tất cả tổ hợp có thể, kiểm thử tổ hợp chọn lọc các tổ hợp đại diện với mức phủ t-way. Khái niệm này được phát triển bởi các nhà nghiên cứu D. Richard Kuhn, Raghu N. Kacker và Yu Lei. Hệ thống kiểm thử (SUT) có thể là một hàm, một lớp, một ứng dụng hoặc toàn bộ hệ thống bao gồm phần cứng và phần mềm. Kiểm thử tổ hợp giúp giảm đáng kể số lượng test case cần thực hiện mà vẫn đảm bảo khả năng phát hiện lỗi cao. Đây là phương pháp được ứng dụng rộng rãi trong kiểm thử phần mềm hiện đại.

1.1. Định nghĩa kiểm thử tổ hợp

Kiểm thử tổ hợp là kỹ thuật xây dựng bộ kiểm thử sao cho các tổ hợp giá trị tham số đầu vào được phủ ở mức t-way. Mỗi test case kiểm tra một tập hợp các giá trị kết hợp từ nhiều tham số khác nhau. Phương pháp này dựa trên nguyên tắc rằng lỗi thường phát sinh từ sự tương tác giữa một số lượng nhỏ các yếu tố. Kiểm thử tổ hợp không yêu cầu kiểm tra mọi tổ hợp có thể xảy ra. Thay vào đó, nó tạo ra tập test case tối thiểu đảm bảo mọi tổ hợp t-way đều được kiểm tra ít nhất một lần.

1.2. Vai trò của kiểm thử tổ hợp

Kiểm thử tổ hợp đóng vai trò quan trọng trong việc đảm bảo chất lượng phần mềm. Phương pháp này giúp phát hiện lỗi do tương tác giữa các tham số mà kiểm thử đơn lẻ không thể tìm thấy. Nghiên cứu thực tế cho thấy kiểm thử bốn chiều có thể phát hiện tất cả lỗi với số lượng test case giảm đến 95% so với bộ test ban đầu. Kiểm thử tổ hợp áp dụng được cho cả cấu hình hệ thống và dữ liệu đầu vào. Đây là công cụ hiệu quả giúp tối ưu quy trình kiểm thử trong các dự án phần mềm quy mô lớn.

II. Phân tích vấn đề kiểm thử truyền thống và giới hạn

Kiểm thử truyền thống đối mặt với thách thức lớn khi số lượng tham số đầu vào tăng lên. Phương pháp kiểm thử tuần tự yêu cầu thực hiện tất cả tổ hợp có thể, dẫn đến số lượng test case khổng lồ. Ví dụ, một hệ thống với nhiều tham số cấu hình như số kết nối đồng thời, bộ nhớ, hệ điều hành, kích thước cơ sở dữ liệu sẽ tạo ra hàng triệu tổ hợp. Việc kiểm tra toàn bộ trở nên bất khả thi về thời gian và chi phí. Kiểm thử ad hoc dựa trên kinh nghiệm thường bỏ sót các tổ hợp quan trọng. Nhiều sự kiện trong hệ thống có số lượng tham số lớn, việc tạo tất cả tổ hợp n-way trở nên không thực tế. Các phương pháp truyền thống không đảm bảo mức phủ tổ hợp đầy đủ, dẫn đến nguy cơ bỏ sót lỗi nghiêm trọng trong sản phẩm phần mềm.

2.1. Bài toán tổ hợp trong kiểm thử

Bài toán tổ hợp trong kiểm thử phát sinh khi số lượng tham số và giá trị tăng lên. Với n tham số, mỗi tham số có k giá trị, số tổ hợp tối đa là k^n. Con số này tăng theo cấp số nhân, khiến việc kiểm thử toàn bộ trở nên bất khả thi. Ví dụ, mười tham số với năm giá trị mỗi tham số tạo ra gần mười triệu tổ hợp. Bài toán này đặt ra yêu cầu cấp thiết về phương pháp kiểm thử thông minh hơn. Kiểm thử tổ hợp ra đời để giải quyết vấn đề này một cách hiệu quả.

2.2. Hạn chế của kiểm thử đơn lẻ

Kiểm thử đơn lẻ chỉ kiểm tra từng tham số riêng biệt, bỏ qua sự tương tác giữa các yếu tố. Nhiều lỗi phần mềm chỉ xuất hiện khi hai hoặc nhiều tham số kết hợp với nhau. Phương pháp này không phát hiện được lỗi do tương tác giữa các thành phần trong hệ thống. Thực tế kiểm thử sự kiện DOM cho thấy nhiều lỗi chỉ được phát hiện khi kiểm tra tổ hợp ba chiều trở lên. Kiểm thử đơn lẻ tạo cảm giác an toàn sai lầm cho đội ngũ phát triển. Đây là lý do kiểm thử tổ hợp trở thành phương pháp thay thế hiệu quả.

III. Phương pháp kiểm thử tổ hợp cấu hình và đầu vào

Kiểm thử tổ hợp có hai phương pháp chính: kiểm thử tổ hợp cấu hình và kiểm thử tổ hợp dữ liệu đầu vào. Phương pháp thứ nhất chọn lọc tổ hợp giá trị của các tham số cấu hình. Ví dụ, máy chủ được kiểm thử bằng cách thiết lập tất cả tổ hợp bốn chiều của các tham số như số kết nối, bộ nhớ, hệ điều hành, loại cơ sở dữ liệu. Bộ kiểm thử được chạy trên mỗi cấu hình khác nhau. Phương pháp thứ hai chọn lọc tổ hợp giá trị dữ liệu đầu vào để tạo thành test case hoàn chỉnh. Mức phủ tổ hợp t-way đảm bảo mọi tương tác t tham số đều được kiểm tra. Giá trị t thường từ hai đến sáu tùy thuộc vào yêu cầu kiểm thử. Nghiên cứu trên sự kiện DOM cho thấy kiểm thử bốn chiều phát hiện được tất cả lỗi với hiệu quả vượt trội.

3.1. Kiểm thử tổ hợp cấu hình hệ thống

Kiểm thử tổ hợp cấu hình tập trung vào các tham số có thể tùy chỉnh của hệ thống. Các tham số bao gồm số kết nối đồng thời, dung lượng bộ nhớ, hệ điều hành, kích thước cơ sở dữ liệu và loại hệ quản trị cơ sở dữ liệu. Cùng một bộ kiểm thử được chạy trên nhiều cấu hình khác nhau. Phương pháp này đảm bảo mọi tổ hợp t-way của tham số cấu hình đều được kiểm tra. Kiểm thử tổ hợp cấu hình đặc biệt hữu ích cho hệ thống cần hoạt động trên nhiều môi trường khác nhau.

3.2. Kiểm thử tổ hợp dữ liệu đầu vào

Kiểm thử tổ hợp dữ liệu đầu vào tạo ra test case hoàn chỉnh từ các tổ hợp giá trị. Mỗi test case chứa tổ hợp giá trị từ nhiều tham số đầu vào khác nhau. Bộ kiểm thử được thiết kế để đảm bảo mức phủ t-way cho tất cả tham số. Phương pháp này áp dụng cho kiểm thử chức năng của ứng dụng. Nghiên cứu thực tế trên ba mươi lăm sự kiện DOM cho thấy hiệu quả vượt trội. Kiểm thử bốn chiều phát hiện tất cả lỗi DOM với số test case giảm chín mươi lăm phần trăm so với phương pháp truyền thống.

IV. Kết luận và ứng dụng thực tế kiểm thử tổ hợp

Kiểm thử tổ hợp đã chứng minh hiệu quả vượt trội trong thực tế kiểm thử phần mềm. Phương pháp này giúp giảm đáng kể số lượng test case mà vẫn đảm bảo khả năng phát hiện lỗi cao. Nghiên cứu trên sự kiện DOM cho thấy kiểm thử bốn chiều phát hiện tất cả lỗi với số test giảm chín mươi lăm phần trăm. Ứng dụng của kiểm thử tổ hợp mở rộng từ kiểm thử cấu hình đến kiểm thử dữ liệu đầu vào. Công cụ kiểm thử tổ hợp ngày càng được phát triển và hoàn thiện. Phương pháp này đặc biệt phù hợp cho các hệ thống phức tạp với nhiều tham số tương tác. Kiểm thử tổ hợp trở thành tiêu chuẩn trong quy trình đảm bảo chất lượng phần mềm hiện đại. Đầu tư vào kiểm thử tổ hợp mang lại lợi ích lâu dài cho doanh nghiệp phần mềm.

4.1. Kết quả nghiên cứu thực tế

Nghiên cứu thực tế trên ba mươi lăm sự kiện DOM cho thấy hiệu quả vượt trội của kiểm thử tổ hợp. Kiểm thử bốn chiều phát hiện tất cả lỗi DOM với số test case giảm chín mươi lăm phần trăm. Đối với các sự kiện có nhiều tham số như Click và Mouse, kiểm thử tổ hợp mang lại lợi ích lớn nhất. Chín trong ba mươi lăm sự kiện cần kiểm thử sáu chiều để phủ tất cả tổ hợp. Kết quả này khẳng định giá trị thực tiễn của phương pháp kiểm thử tổ hợp trong phát triển phần mềm.

4.2. Ứng dụng trong công nghiệp phần mềm

Kiểm thử tổ hợp được ứng dụng rộng rãi trong công nghiệp phần mềm hiện đại. Phương pháp này áp dụng cho kiểm thử hệ thống nhúng, ứng dụng web và hệ thống phân tán. Các công ty công nghệ lớn sử dụng kiểm thử tổ hợp để tối ưu quy trình kiểm thử. Công cụ tự động hóa giúp tạo test case tổ hợp nhanh chóng và chính xác. Kiểm thử tổ hợp đặc biệt hiệu quả cho hệ thống có nhiều tham số cấu hình. Phương pháp này giúp giảm chi phí kiểm thử while tăng khả năng phát hiện lỗi.

Trích đoạn nội dung tài liệu

Free ebooks ==> www.com CHAPMAN & HALL/CRC INNOVATIONS IN SOFTWARE ENGINEERING AND SOFTWARE DEVELOPMENT Introduction to Combinatorial Testing D. Richard Kuhn Raghu N. Kacker Yu Lei www.com Free ebooks ==> www.com Introduction to Combinatorial Testing Chapman & Hall/CRC Innovations in Software Engineering and Software Development Series Editor Richard LeBlanc Chair, Department of Computer Science and Software Engineering, Seattle University AIMS AND SCOPE This series covers all aspects of software engineering and software development. Books in the series will be innovative reference books, research monographs, and textbooks at the undergraduate and graduate level. Coverage will include traditional subject matter, cutting-edge research, and current industry practice, such as agile software development methods and service-oriented architectures. We also welcome proposals for books that capture the latest results on the domains and conditions in which practices are most ef- fective. PUBLISHED TITLES Software Development: An Open Source Approach Allen Tucker, Ralph Morelli, and Chamindra de Silva Building Enterprise Systems with ODP: An Introduction to Open Distributed Processing Peter F. Linington, Zoran Milosevic, Akira Tanaka, and Antonio Vallecillo Software Engineering: The Current Practice Václav Rajlich Fundamentals of Dependable Computing for Software Engineers John Knight Introduction to Combinatorial Testing D. Richard Kuhn, Raghu N. Kacker, and Yu Lei Free ebooks ==> www.com CHAPMAN & HALL/CRC INNOVATIONS IN SOFTWARE ENGINEERING AND SOFTWARE DEVELOPMENT Introduction to Combinatorial Testing D. Richard Kuhn Raghu N. Kacker Yu Lei www.com CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2013 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U. Government works Version Date: 20130426 International Standard Book Number-13: 978-1-4665-5230-2 (eBook - PDF) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information stor- age or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.com (http://www.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that pro- vides licenses and registration for a variety of users. For organizations that have been granted a pho- tocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.com and the CRC Press Web site at http://www.com Contents Preface, xiii Authors, xvii Note of Appreciation, xix Nomenclature, xxi Chapter 1 ■ Combinatorial Methods in Testing 1 1.1 SOFTWARE FAILURES AND THE INTERACTION RULE 1 1.2 TWO FORMS OF COMBINATORIAL TESTING 8 1.1 Covering Array Definition 12 1.2 Size of Covering Arrays 13 1.4 THE TEST ORACLE PROBLEM 15 1.5 QUICK START: HOW TO USE THE BASICS OF COMBINATORIAL METHODS RIGHT AWAY 16 1.6 CHAPTER SUMMARY 17 REVIEW 18 Chapter 2 ■ Combinatorial Testing Applied 21 2.1 DOCUMENT OBJECT MODEL 21 Carmelo Montanez-Rivera, D. Richard Kuhn, Mary Brady, Rick Rivello, Jenise Reyes Rodriguez, and Michael Powers 2.1 Constructing Tests for DOM Events 22 v vi   ◾   Contents 2.2 Combinatorial Testing Approach 25 2.4 Cost and Practical Considerations 29 2.2 RICH WEB APPLICATIONS 30 Chad M.1 Systematic Variable Detection in Semantic URLs 31 2.2 JavaScript Fault Classification and Identification 31 2.3 CHAPTER SUMMARY 35 Chapter 3 ■ Configuration Testing 37 3.1 RUNTIME ENVIRONMENT CONFIGURATIONS 37 3.2 HIGHLY CONFIGURABLE SYSTEMS AND SOFTWARE PRODUCT LINES 39 3.3 INVALID COMBINATIONS AND CONSTRAINTS 44 3.1 Constraints among Parameter Values 44 3.2 Constraints among Parameters 46 3.4 COST AND PRACTICAL CONSIDERATIONS 48 3.5 CHAPTER SUMMARY 49 REVIEW 50 Chapter 4 ■ Input Testing 51 4.1 PARTITIONING THE INPUT SPACE 51 4.2 INPUT VARIABLES VERSUS TEST PARAMETERS 55 4.3 FAULT TYPE AND DETECTABILITY 57 4.4 BUILDING TESTS TO MATCH AN OPERATIONAL PROFILE 61 4.6 COST AND PRACTICAL CONSIDERATIONS 66 4.7 CHAPTER SUMMARY 67 REVIEW 68 Contents   ◾   vii Chapter 5 ■ Test Parameter Analysis 71 Eduardo Miranda 5.1 WHAT SHOULD BE INCLUDED AS A TEST PARAMETER 72 5.3 CLASSIFICATION TREE METHOD 76 5.1 Flexible Manufacturing System Example 81 5.5 SELECTING THE SYSTEM UNDER TEST 103 5.6 COMBINATORIAL TESTING AND BOUNDARY VALUE ANALYSIS 106 5.7 CHAPTER SUMMARY 111 REVIEW 111 Chapter 6 ■ Managing System State 113 George Sherwood 6.1 TEST FACTOR PARTITIONS WITH STATE 114 6.1 Partitions for Expected Results 115 6.2 Partitions with Constraints 116 6.3 Direct Product Block Notation 116 6.2 TEST FACTOR SIMPLIFICATIONS 119 6.1 All the Same Factor Value 119 6.2 All Different Factor Values 119 6.3 Functionally Dependent Factor Values 119 6.4 Hybrid Factor Values 121 6.3 SEQUENCE UNIT REPLAY MODEL 122 6.4 SINGLE REGION STATE MODELS 126 6.5 MULTIPLE REGION STATE MODELS 133 6.6 CHAPTER SUMMARY 137 REVIEW 140 Free ebooks ==> www.com viii   ◾   Contents Chapter 7 ■ Measuring Combinatorial Coverage 143 7.1 SOFTWARE TEST COVERAGE 144 7.1 Simple t-Way Combination Coverage 146 7.4 Variable-Value Configuration Coverage 149 7.3 USING COMBINATORIAL COVERAGE 152 7.4 COST AND PRACTICAL CONSIDERATIONS 156 7.5 ANALYSIS OF (t + 1)-WAY COVERAGE 160 7.6 CHAPTER SUMMARY 161 REVIEW 161 Chapter 8 ■ Test Suite Prioritization by Combinatorial Coverage 163 Renee Bryce and Sreedevi Sampath 8.1 COMBINATORIAL COVERAGE FOR TEST SUITE PRIORITIZATION 163 8.4 REVIEW OF EMPIRICAL STUDIES 169 8.5 TOOL: COMBINATORIAL-BASED PRIORITIZATION FOR USER-SESSION-BASED TESTING 173 8.1 Apache Logging Module 173 8.2 Creating a User Session–Based Test Suite from Usage Logs Using CPUT 173 8.3 Prioritizing and Reducing Test Cases 173 www.com Contents   ◾   ix 8.6 OTHER APPROACHES TO TEST SUITE PRIORITIZATION USING COMBINATORIAL INTERACTIONS 174 8.7 COST AND PRACTICAL CONSIDERATIONS 175 8.8 CHAPTER SUMMARY 176 REVIEW 176 Chapter 9 ■ Combinatorial Testing and Random Test Generation 179 9.1 COVERAGE OF RANDOM TESTS 180 9.2 ADAPTIVE RANDOM TESTING 184 9.3 TRADEOFFS: COVERING ARRAYS AND RANDOM GENERATION 186 9.4 COST AND PRACTICAL CONSIDERATIONS 189 9.5 CHAPTER SUMMARY 190 REVIEW 191 Chapter 10 ■ Sequence-Covering Arrays 193 10.1 SEQUENCE-COVERING ARRAY DEFINITION 193 10.2 SIZE AND CONSTRUCTION OF SEQUENCE- COVERING ARRAYS 195 10.1 Generalized t-Way Sequence Covering 197 10.3 USING SEQUENCE-COVERING ARRAYS 198 10.4 COST AND PRACTICAL CONSIDERATIONS 199 10.5 CHAPTER SUMMARY 199 REVIEW 202 Chapter 11 ■ Assertion-Based Testing 203 11.1 BASIC ASSERTIONS FOR TESTING 204 11.2 STRONGER ASSERTION-BASED TESTING 208 11.3 COST AND PRACTICAL CONSIDERATIONS 209 11.4 CHAPTER SUMMARY 210 REVIEW 210 x   ◾   Contents Chapter 12 ■ Model-Based Testing 213 12.2 ACCESS CONTROL SYSTEM EXAMPLE 215 12.4 INTEGRATING COMBINATORIAL TESTS INTO THE MODEL 218 12.5 GENERATING TESTS FROM COUNTEREXAMPLES 222 12.6 COST AND PRACTICAL CONSIDERATIONS 224 12.7 CHAPTER SUMMARY 225 REVIEW 225 Chapter 13 ■ Fault Localization 227 13.1 FAULT LOCALIZATION PROCESS 228 13.2 New Test Generation 230 13.2 LOCATING FAULTS: EXAMPLE 231 13.1 Generating New Tests 234 13.3 COST AND PRACTICAL CONSIDERATIONS 235 13.4 CHAPTER SUMMARY 236 REVIEW 236 Chapter 14 ■ Evolution from Design of Experiments 237 14.2 PAIRWISE (TWO-WAY) TESTING OF SOFTWARE SYSTEMS 239 14.3 COMBINATORIAL t-WAY TESTING OF SOFTWARE SYSTEMS 245 14.4 CHAPTER SUMMARY 246 Contents   ◾   xi Chapter 15 ■ Algorithms for Covering Array Construction 247 Linbin Yu and Yu Lei 15.4 COST AND PRACTICAL CONSIDERATIONS 255 15.2 Mixed-Strength Covering Arrays 256 15.3 Extension of an Existing Test Set 257 15.5 CHAPTER SUMMARY 258 REVIEW 258 APPENDIX A: MATHEMATICS REVIEW, 261 A.1 Permutations and Combinations 261 A.4 Number of Tests Required 264 A.2 Combining Operators 266 APPENDIX B: EMPIRICAL DATA ON SOFTWARE FAILURES, 267 APPENDIX C: RESOURCES FOR COMBINATORIAL TESTING, 273 APPENDIX D: TEST TOOLS, 277 D.1 ACTS USER GUIDE 278 xii   ◾   Contents D.1 t-Way Test Set Generation 278 D.2 Command Line Interface 279 D.1 Create New System 284 D.2 Build Test Set 288 D.4 Save/Save as/Open System 291 D.5 Import/Export Test Set 291 D.6 Verify t-Way Coverage 292 REFERENCES, 293 Preface S oftware testing has always faced a seemingly intractable prob- lem: for real-world programs, the number of possible input combi- nations can exceed the number of atoms in the ocean, so as a practical matter it is impossible to show through testing that the program works correctly for all inputs. Combinatorial testing offers a (partial) solution. Empirical data show that the number of variables involved in failures is small. Most failures are triggered by only one or two inputs, and the number of variables interacting tails off rapidly, a relationship called the interaction rule. Therefore, if we test input combinations for even small numbers of variables, we can provide very strong testing at low cost. As always, there is no “silver bullet” answer to the problem of software assur- ance, but combinatorial testing has grown rapidly because it works in the real world. This book introduces the reader to the practical application of combina- torial methods in software testing. Our goal is to provide sufficient depth that readers will be able to apply these methods in their own testing proj- ects, with pointers to freely available tools. Included are detailed explana- tions of how and why to use various techniques, with examples that help clarify concepts in all chapters. Sets of exercises or questions and answers are also included with most chapters. The text is designed to be acces- sible to an undergraduate student of computer science or engineering, and includes an extensive set of references to papers that provide more depth on each topic. Many chapters introduce some of the theory and mathemat- ics of combinatorial methods. While this material is needed for thorough knowledge of the subject, testers can apply the methods using tools (many freely available and linked in the chapters) that encapsulate the theory, even without in-depth knowledge of the underlying mathematics. We have endeavored to be as prescriptive as possible, but experienced testers know that standardized procedures only go so far. Engineering xiii xiv   ◾   Preface judgment is as essential in testing as in development. Because analysis of the input space is usually the most critical step in testing, we have devoted roughly a third of the book to it, in Chapters 3 through 6. It is in this phase that experience and judgment have the most bearing on the success of a testing project. Analyzing and modeling the input space is also a task that is easy to do poorly, because it is so much more complex than it first appears. Chapters 5 and 6 introduce systematic methods for dealing with this problem, with examples to illustrate the subtleties that make the task so challenging to do right. Chapters 7 through 9 are central to another important theme of this book—combinatorial methods can be applied in many ways during the testing process, and can improve conventional test procedures not designed with these methods in mind. That is, we do not have to com- pletely re-design our testing practices to benefit from combinatorial meth- ods. Any test suite, regardless of how it is derived, provides some level of combinatorial coverage, so one way to use the methods introduced in this book is to create test suites using an organization’s conventional proce- dures, measure their combinatorial coverage, and then supplement them with additional tests to detect complex interaction faults. The oracle problem—determining the correct output for a given test—is covered in Chapters 10 and 11.