Abstract
According to the NIST report of 2002 there is a great potential to reduce the cost, and to increase the quality of the software developed in USA through the creation of automated tools that help in the software testing process. One alternative to improve the software testing process is the creation of tools that generate testing cases in an automatic way. Through the construction of Covering Arrays (CA) it is possible to obtain a minimum set of test cases with the maximum possibility of testing all the functionality of the developed software.
In this paper an approach to construct CA using the propositional satisfiability problem (SAT) is presented. The approach starts with the transformation of a CA instance into a non-conjunctive normal form (non-CNF) SAT instance. Then the SAT instance is solved through a non-CNF SAT solver, and finally the SAT solution is transformed into a CA solution. The main contributions of this work are: an efficient non-CNF SAT solver able to equals or improves previously reported results, and a simplified SAT representation to solve the CA problem.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Burr, K., Young, W.: Combinatorial test techniques: Table-based automation, test generation, and code coverage. In: Proceedings of the International Conference on Software Testing Analysis and Review, San Diego, USA, pp. 503–513 (October 1998)
Cerny, V.: A thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal Optimization Theory and Applications 45, 41–51 (1985)
Chateauneuf, M., Kreher, D.L.: On the state of strength-three covering arrays. Journal of Combinatorial Designs 10(4), 217–238 (2002)
Cohen, D.M., Parelius, J., Dalal, S.R., Patton, G.C.: The combinatorial design approach to automatic test generation. IEEE Sofware 13(5), 83–88 (1996)
Cohen, D.M., Dalal, S.R., Fredman, M.L., Patton, G.C.: The aetg system: an approach to testing based on combinatorial design. Transactions on Software Engineering 23(7), 437–444 (1997)
Cook, S.A.: The complexity of theorem-proving procedures. In: STOC 1971: Proceedings of the third annual ACM symposium on Theory of computing, pp. 151–158. ACM, New York (1971)
Dalal, S.R., Mallows, C.L.: Factor-covering designs for testing software. Technometrics 40(3), 234–243 (1998)
Davis, M., Logemann, G., Loveland, D.: A machine program for theorem-proving. Communications. ACM 5(7), 394–397 (1962)
Davis, M., Putnam, H.: A computing procedure for quantification theory. J. ACM 7(3), 201–215 (1960)
Gu, J.: Efficient local search for very large-scale satisfiability problems. SIGART Bull. 3(1), 8–12 (1992)
Hansen, P., Jaumard, B.: Algorithms for the maximum satisfiability problem. Computing 44(4), 279–303 (1990)
Hartman, A., Raskin, L.: Problems and algorithms for covering arrays. Discrete Math. 284(1-3), 149–156 (2004)
Hnich, B., Prestwich, S.D., Selensky, E., Smith, B.M.: Constraint models for the covering test problem. Constraints 11(2-3), 199–219 (2006)
Jorgensen, P.C.: Software Testing: A Craftsman’s Approach. CRC Press, New York (2002)
Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 4598, 671–680 (1983)
Kleitmain, D.J., Spencer, J.: Families of k-independent sets. Discrete Math. 6, 255–262 (1973)
Lei, Y., Tai, K.C.: In-parameter-order: A test generation strategy for pairwise testing. In: HASE 1998: The 3rd IEEE International Symposium on High-Assurance Systems Engineering, Washington, DC, USA, pp. 254–261. IEEE Computer Society, Los Alamitos (1998)
Nurmela, K.J.: Upper bounds for covering arrays by tabu search. Discrete Applied Math. 138(1-2), 143–152 (2004)
National Institute of Standards and Technology. The economic impacts of inadequate infrastructure for software testing (2002), www.nist.gov/director/prog-ofc/report02-3.pdf
Selman, B., Kautz, H.A., Cohen, B.: Local search strategies for satisfiability testing. In: Proceedings of the Second DIMACS Challange on Cliques, Coloring, and Satisfiability (1993)
Selman, B., Levesque, H., Mitchell, D.: A new method for solving hard satisifiability problems. In: AAAI 1992, San Jose, CA, pp. 440–446 (July 1992)
Sloane, N.J.A.: Covering arrays and intersecting codes. Journal of Combinatorial Designs 1(1), 51–63 (1993)
Turban, R.C.: Algorithms for covering arrays. PhD thesis, Tempe, AZ, USA, Adviser-Charles Colbourn (2006)
Williams, A.W., Probert, R.L.: A practical strategy for testing pair-wise coverage of network interfaces. In: ISSRE 1996: Proceedings of the Seventh International Symposium on Software Reliability Engineering (ISSRE 1996), Washington, DC, USA, pp. 246–256. IEEE Computer Society, Los Alamitos (1996)
Williams, A.W.: Determination of test configurations for pair-wise interaction coverage. In: TestCom 2000: Proceedings of the IFIP TC6/WG6.1 13th International Conference on Testing Communicating Systems, Deventer, The Netherlands, pp. 59–74. Kluwer, B.V. (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lopez-Escogido, D., Torres-Jimenez, J., Rodriguez-Tello, E., Rangel-Valdez, N. (2008). Strength Two Covering Arrays Construction Using a SAT Representation. In: Gelbukh, A., Morales, E.F. (eds) MICAI 2008: Advances in Artificial Intelligence. MICAI 2008. Lecture Notes in Computer Science(), vol 5317. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-88636-5_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-88636-5_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-88635-8
Online ISBN: 978-3-540-88636-5
eBook Packages: Computer ScienceComputer Science (R0)