Finding Minimum Locating Arrays Using a CSP Solver

• Autorzy: Konishi Tatsuya , Kojima Hideharu , Nakagawa Hiroyuki , Tsuchiya Tatsuhiro

Identyfikatory

DOI

10.3233/FI-2020-1929

• Języki publikacji: EN

Abstrakty

EN

Combinatorial interaction testing is an efficient software testing strategy. If all interactions among test parameters or factors needed to be covered, the size of a required test suite would be prohibitively large. In contrast, this strategy only requires covering t-wise interactions where t is typically very small. As a result, it becomes possible to significantly reduce test suite size. Locating arrays aim to enhance the ability of combinatorial interaction testing. In particular, (1̅ , t) -locating arrays can not only execute all t-way interactions but also identify, if any, which of the interactions causes a failure. In spite of this useful property, there is only limited research either on how to generate locating arrays or on their minimum sizes. In this paper, we propose an approach to generating minimum locating arrays. In the approach, the problem of finding a locating array consisting of N tests is represented as a Constraint Satisfaction Problem (CSP) instance, which is in turn solved by a modern CSP solver. The results of using the proposed approach reveal many (1̅ , t) -locating arrays that are smallest known so far. In addition, some of these arrays are proved to be minimum.

Słowa kluczowe

EN

combinatorial interaction testing; constraint satisfaction problem; locating array; software testing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 174, nr 1
• Strony: 27--42
• Opis fizyczny: Bibliogr. 35 poz., tab., wykr.

Twórcy

autor

Konishi Tatsuya

• Graduate School of Information Science and Technology, Osaka University, Suita, Japan

autor

Kojima Hideharu

• Graduate School of Information Science and Technology, Osaka University, Suita, Japan

autor

Nakagawa Hiroyuki

• Graduate School of Information Science and Technology, Osaka University, Suita, Japan

autor

Tsuchiya Tatsuhiro

• Graduate School of Information Science and Technology, Osaka University, Suita, Japan

Bibliografia

• [1] Kuhn DR, Kacker RN, Lei Y. Introduction to combinatorial testing. CRC Press, 2013. ISBN-10:1466552298, 13:978-1466552296.
• [2] Nie C, Leung H. A Survey of Combinatorial Testing. ACM Comput. Surv., 2011. 43(2):11:1-11:29. doi:10.1145/1883612.1883618.
• [3] Kuhn DR, Wallace DR. Software fault interactions and implications for software testing. IEEE Transactions on Software Engineering, 2004. 30(6):418-421. doi:10.1109/TSE.2004.24.
• [4] Colbourn CJ, McClary DW. Locating and detecting arrays for interaction faults. Journal of combinatorial optimization, 2008. 15:17-48. doi:10.1007/s10878-007-9082-4.
• [5] Hnich B, D Prestwich S, Selensky E, M Smith B. Constraint Models for the Covering Test Problem. Constraints (2006), 2006. 11:199-219. doi:10.1007/s10601-006-7094-9.
• [6] Tang Y, Colbourn CJ, Yin J. Optimality and Constructions of Locating Arrays. Journal of Statistical Theory and Practice, 2012. 6:20-29. doi:10.1080/15598608.2012.647484.
• [7] Fredman ML, Patton GC, Dalal SR, Cohen DM. The AETG System: An Approach to Testing Based on Combinatorial Design. IEEE Transactions on Software Engineering, 1997. 23(7):437-444. doi:10.1109/32.605761.
• [8] Czerwonka J. Pairwise Testing in Real World. Practical Extensions to Test Case Generators. In: Proc. of the 24th Annual Pacific Northwest Software Quality Conference. 2006 pp. 419-430.
• [9] Soh T, Tamura N, Banbara M. Scarab: A Rapid Prototyping Tool for SAT-Based Constraint Programming Systems. Theory and Applications of Satisfiability Testing - SAT 2013 Volume 7962 of the series Lecture Notes in Computer Science, 2013. pp. 429-436. doi.org/10.1007/978-3-642-39071-5_34.
• [10] Tamura N, Taga A, Kitagawa S, Banbara M. Compiling finite linear CSP into SAT. Constraints, 2009. 14(2):254-272. doi:10.1007/s10601-008-9061-0.
• [11] Berre DL, Parrain A. The Sat4j library, release 2.2. Journal on Satisfiability, Boolean Modeling and Computation, 2010. 7:59-64. URL https://hal.archives-ouvertes.fr/hal-00868136.
• [12] Audemard G, Simon L. Predicting learnt clauses quality in modern sat solvers. Proc. 21st International Jont Conference on Artifical Intelligence. ser. IJCAL’09, 2009. pp. 399-404.
• [13] Aldaco AN, Colbourn CJ, Syrotiuk VR. Locating Arrays: A New Experimental Design for Screening Complex Engineered Systems. SIGOPS Oper. Syst. Rev., 2015. 49(1):31-40. doi:10.1145/2723872.2723878.
• [14] Compton R, Mehari MT, Colbourn CJ, De Poorter E, Syrotiuk VR. Screening interacting factors in a wireless network testbed using locating arrays. In: 2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). 2016 pp. 650-655. doi:10.1109/INFCOMW.2016.7562157.
• [15] Colbourn CJ, Syrotiuk VR. Coverage, Location, Detection, and Measurement. In: 2016 IEEE Ninth International Conference on Software Testing, Verification and Validation Workshops (ICSTW). 2016 pp. 19-25. doi:10.1109/ICSTW.2016.38.
• [16] Colbourn CJ, Fan B, Horsley D. Disjoint Spread Systems and Fault Location. SIAM Journal on Discrete Mathematics, 2016. 30(4):2011-2026. doi:10.1137/16M1056390.
• [17] Shi C, Tang Y, Yin J. Optimal locating arrays for at most two faults. Science China Mathematics, 2012. 55(1):197-206. doi:10.1007/s11425-011-4307-5.
• [18] Colbourn CJ, Fan B. Locating one pairwise interaction: Three recursive constructions. Journal of Algebra Combinatorics Discrete Structures and Applications, 2016. 3(3):127-134. doi:10.13069/jacodesmath.17551.
• [19] Konishi T, Kojima H, Nakagawa H, Tsuchiya T. Finding minimum locating arrays using a SAT solver. IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), 2017. pp. 276-277. doi:10.1109/ICSTW.2017.49.
• [20] Nagamoto T, Kojima H, Nakagawa H, Tsuchiya T. Locating a Faulty Interaction in Pair-wise Testing. In: Proc. of IEEE 20th Pacific Rim International Symposium on Dependable Computing. 2014 pp. 155-156. doi:10.1109/PRDC.2014.26.
• [21] Seidel SA, Sarkar K, Colbourn CJ, Syrotiuk VR. Separating Interaction Effects Using Locating and Detecting Arrays. In: Iliopoulos C, Leong HW, Sung WK (eds.), Combinatorial Algorithms. Springer International Publishing, Cham. ISBN 978-3-319-94667-2, 2018 pp. 349-360.
• [22] Colbourn CJ, Syrotiuk VR. On a Combinatorial Framework for Fault Characterization. Mathematics in Computer Science, 2018. 12(4):429-451. doi:10.1007/s11786-018-0385-x.
• [23] Moser RA, Tardos G. A Constructive Proof of the General LovÁSz Local Lemma. J. ACM, 2010. 57(2):11:1-11:15. doi:10.1145/1667053.1667060.
• [24] Jin H, Tsuchiya T. Constrained locating arrays for combinatorial interaction testing. arXiv e-prints, 2017. arXiv:1801.06041. 1801.06041.
• [25] Jin H, Kitamura T, Choi EH, Tsuchiya T. A Satisfiability-Based Approach to Generation of Constrained Locating Arrays. In: 2018 IEEE International Conference on Software Testing, Verification and Validation Workshops. 2018 pp. 285-294. doi:10.1109/ICSTW.2018.00062.
• [26] Jin H, Tsuchiya T. Deriving Fault Locating Test Cases from Constrained Covering Arrays. In: 2018 IEEE 23rd Pacific Rim International Symposium on Dependable Computing (PRDC). 2018 pp. 233-240. doi:10.1109/PRDC.2018.00044.
• [27] Banbara M, Matsunaka H, Tamura N, Inoue K. Generating combinatorial test cases by efficient SAT encodings suitable for CDCL SAT solvers. In: Proc. of the 17th international conference on Logic for programming, artificial intelligence, and reasoning, LPAR’10. Springer-Verlag, Berlin, Heidelberg. 2010 pp. 112-126. ISBN: 3-642-16241-X, 978-3-642-16241-1.
• [28] Nanba T, Tsuchiya T, Kikuno T. Using Satisfiability Solving for Pairwise Testing in the Presence of Constraints. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2012. E95.A(9):1501-1505. doi:10.1587/transfun.E95.A.1501.
• [29] Yamada A, Kitamura T, Artho C, Choi E, Oiwa Y, Biere A. Optimization of Combinatorial Testing by Incremental SAT Solving. In: Proc. of the 8th IEEE International Conference on Software Testing, Verification and Validation, ICST 2015. 2015 pp. 1-10. doi:10.1109/ICST.2015.7102599.
• [30] Colbourn CJ. Combinatorial Aspects of Covering Arrays. Le Matematiche, 2004. 58:121-167.
• [31] Borazjany MN, Yu L, Lei Y, Kacker R, Kuhn R. Combinatorial Testing of ACTS: A Case Study. In: Proc. of the 5th International Conference on Software Testing, Verification and Validation. 2012 pp. 591-600. doi:10.1109/ICST.2012.146.
• [32] Cohen DM, Dalal SR, Fredman ML, Patton GC. The AETG System: An Approach to Testing Based on Combinatiorial Design. IEEE Trans. Software Eng., 1997. 23(7):437-444. doi:10.1109/32.605761.
• [33] Walker II RA, Colbourn C. Tabu search for covering arrays using permutation vectors. Journal of Statistical Planning and Inference 139, 2009. 139(1):69-80. URL https://doi.org/10.1016/j.jspi.2008.05.020.
• [34] Nurmela KJ. Upper bounds for covering arrays by tabu search. Discrete Appl. Math., 2004. 138(1-2):143-152. doi:10.1016/S0166-218X(03)00291-9.
• [35] Shiba T, Tsuchiya T, Kikuno T. Using artificial life techniques to generate test cases for combinatorial testing. In: Proc. of 28th Annual International Computer Software and Applications Conference (COMPSAC’04). 2004 pp. 71-77. doi:10.1109/CMPSAC.2004.1342808.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).