Abstract
In the 21st century our society is becoming more and more dependent on software systems. The safety of these systems and the quality of our lives is increasingly dependent on the quality of such systems. A key element in the manufacture and quality assurance process in software engineering is the testing of software and hardware systems. The construction of efficient combinatorial covering suites has important applications in the testing of hardware and software. In this paper we define the general problem, discuss the lower bounds on the size of covering suites, and give a series of constructions that achieve these bounds asymptotically. These constructions include the use of finite field theory, extremal set theory, group theory, coding theory, combinatorial recursive techniques, and other areas of computer science and mathematics. The study of these combinatorial covering suites is a fascinating example of the interplay between pure mathematics and the applied problems generated by software and hardware engineers. The wide range of mathematical techniques used, and the often unexpected applications of combinatorial covering suites make for a rewarding study.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Azar J., Motwani R., and Naor J., Approximating probability distributions using small sample spaces. Combinatorica 18: 151–171 (1998).
Boroday S. Y., Determining essential arguments of Boolean functions. (in Russian), in Proceedings of the Conference on Industrial Mathematics, Taganrog (1998), 59–61. The translation is a personal communication from the author.
Boroday S.Y. and Grunskii I. S., Recursive generation of locally complete tests. Cybernetics and Systems Analysis 28: 20–25 (1992).
Bose R. C., Parker E. T., and Shrikhande S., Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler’s conjecture. Can. J. Math. 12: 189–203 (1960).
Bush K. A., Ageneralization of the theorem due to MacNeish. Ann. Math. Stat. 23: 293–295 (1952).
Bush K. A., Orthogonal arrays of index unity. Annals of Mathematical Statistics 23: 426–434 (1952).
Chandra A. K., Kou L. T., Markowsky G., and Zaks S., On sets of Boolean n-vectors with all k-projections surjective. Acta Inform. 20: 103–111 (1983).
Chateauneuf M. A. and Kreher D. L., On the state of strength 3 covering arrays. J. Combinatorial Designs, Journal of Combinatorial Designs 10 (2002), no. 4, 217–238. Available at http://www.math.mtu.edu/~kreher/.
Chateauneuf M. A., Colbourn C. J., and Kreher D. L., Covering arrays of strength 3. Designs, Codes, and Cryptography, 16: 235–242 (1999).
Chowla S., Erdös P., and Straus E. G., On the maximal number of pairwise orthogonal Latin squares of a given order. Canad. J. Math. 13: 204–208 (1960).
Cohen D. M., Dalal S. R., Fredman M. L., and Patton G. C., The AETGSystem: An approach to Testing Based on Combinatorial Design. IEEE Transactions on Software Engineering, 23: 437–444 (1997).
Colbourn C. J. and Dinitz J. H., The CRC Handbook of Combinatorial Designs. CRC Press (1996).
Dill D., Murø Description Language and Verifier. http://sprout.stanford.edu/dill/murphi.html.
Edelman A., The mathematics of the Pentium division bug. SIAM Review 39: 54–67 (1997).
Erdös P., Ko C., and Rado R., Intersection theorems for systems of finite sets. Quart. J. Math. Oxford 12: 313–318 (1961).
Farchi E., Hartman A., and Pinter S. S., Using a model-based test generator to test for standards conformance. IBM Systems Journal 41: 89–110 (2002).
Fisher R. A., An examination of the different possible solutions of a problem in incomplete blocks. Ann. Eugenics 10: 52–75 (1940).
Gal S., Rendezvous search on a line. Operations Research 47: 974–976 (1999).
Gargano L., Körner J., and Vaccaro U., Capacities: from information theory to extremal set theory. J. Comb. Theory, Ser. A. 68: 296–316 (1994).
Gargano L., Körner J., and Vaccaro U., Sperner capacities. Graphs and Combinatorics, 9: 31–46 (1993).
Godbole A. P., Skipper D. E., and Sunley R. A., t-Covering arrays: Upper bounds and Poisson approximations. Combinatorics, Probability, and Computing 5: 105–117 (1996).
Greene C., Sperner families and partitions of a partially ordered set. In Combinatorics (ed. M. Hall Jr. and J. van Lint) Dordrecht, Holland, (1975) pp. 277–290.
Harborth H. and Kemnitz A., Calculations for Bertrand’s Postulate. Math. Magazine 54: 33–34 (1981).
Katona G. O. H., Two applications (for search theory and truth functions) of Sperner type theorems. Periodica Math. Hung. 3: 19–26 (1973).
Kleitman D. J. and Spencer J., Families of k-independent sets. Discrete Math. 6: 255–262 (1973).
Lei Y. and Tai K. C., In-parameter order: A test generation strategy for pairwise testing. in Proc. 3rd IEEE High Assurance Systems Engineering Symposium, (1998) pp. 254–161.
Leveson N. and Turner C. S. An investigation of the Therac-25 accidents. IEEE Computer, 26: 18–41 (1993).
Lim W. S. and Alpern S., Minimax rendezvous on the line. SIAM J. Control and Optim. 34: 1650–1665 (1996).
Lions J. L., Ariane 5 Flight 501 failure, Report by the Inquiry Board. http://sunnyday.mit.edu/accidents/Ariane5accidentreport.html.
Metsch K., Improvement of Bruck’s completion theorem. Designs, Codes and Cryptography 1: 99–116 (1991).
Naor J. and Naor M., Small-bias probability spaces: efficient constructions and applications. SIAM J. Computing, 22: 838–856 (1993).
Naor M., Schulman L. J., and Srinvasan A., Splitters and near-optimal randomization. Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), (1996), pp. 182–191.
Nurmela K., Upper bounds for covering arrays by tabu search. Discrete Applied Mathematics, 138: 143–152 (2004).
Peled D. A., Software reliability methods. Springer, New York (2001).
Rényi A., Foundations of probability. Wiley, New York, (1971).
Roux G., k-propriétés dans les tableaux de n colonnes; cas particulier de la k-surjectivité et de la k-permutativité. Ph. D. Dissertation, University of Paris 6, (1987).
Seroussi G. and Bshouty N. H., Vector sets for exhaustive testing of logic circuits. IEEE Trans. Information Theory, 34: 513–522 (1988).
Sloane N. J. A., Covering arrays and intersecting codes. J. Combinatorial Designs 1: 51–63 (1993).
Stevens B., Ling A., and Mendelsohn E., A direct construction of transversal covers using group divisible designs. Ars Combin. 63: 145–159 (2002).
Stevens B., Moura L., and Mendelsohn E., Lower bounds for transversal covers. Designs, Codes, and Cryptography, 15: 279–299 (1998).
Tang D. T. and Chen C. L., Iterative exhaustive pattern generation for logic testing. IBM J. Res. Develop. 28: 212–219 (1984).
Tang D. T. and Woo L. S., Exhaustive test pattern generation with constant weight vectors. IEEE Trans. Computers 32: 1145–1150 (1983).
Web W. W., The Vandermonde determinant, http://www.webeq.com/WebEQ/2.3/docs/tour/determinant.html
West D. B., Introduction to Graph Theory. Prentice Hall NJ, (1996).
Williams A. W., Determination of Test Configurations for Pair-Wise Interaction Coverage. in Proceedings of the 13th International Conference on the Testing of Communicating Systems (TestCom 2000), Ottawa Canada, (2000) pp. 59–74.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer Science + Business Media, Inc.
About this chapter
Cite this chapter
Hartman, A. (2005). Software and Hardware Testing Using Combinatorial Covering Suites. In: Golumbic, M.C., Hartman, I.BA. (eds) Graph Theory, Combinatorics and Algorithms. Operations Research/Computer Science Interfaces Series, vol 34. Springer, Boston, MA. https://doi.org/10.1007/0-387-25036-0_10
Download citation
DOI: https://doi.org/10.1007/0-387-25036-0_10
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-24347-4
Online ISBN: 978-0-387-25036-6
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)