Distributed Black-Box Software Testing Using Negative Selection

Author

Computer Engineering Department, Azad University-Tehran Central Branch, Tehran, Iran

Abstract

In the software development process, testing is one of the most human intensive steps. Many researchers try to automate test case generation to reduce the manual labor of this step. Negative selection is a famous algorithm in the field of Artificial Immune System (AIS) and many different applications has been developed using its idea. In this paper we have designed a new algorithm based on negative selection for breeding test cases. Our approach, belongs to the category of black-box software testing. Moreover, this algorithm can be implemented in a distributed model. Two well-known case studies from software testing benchmarks is selected and results show the efficiency of this algorithm

Keywords


1]
J. King, “A New Approach to Program Testing”, In Proceedings of the International Conference on Reliable Software ACM Press, pp.228-233, 1975.
[2]
J. King, “Symbolic Execution and Program Testing”, Communications of the ACM, Vol.19, Iss.7, pp.385-394, 1976.
[3]
S. Khurshid, C. S. Pasareanu, W. Visser: Generalized symbolic execution for model checking and testing, In Proc. 9th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pp.553-568, April 2003.
[4]
K. L. McMillan, “Symbolic Model Checking”, Kluwer Academic Publishers, 1993.
[5]
W. Miller, D. Spooner, “Automatic Generation of Floating-Point Test Data”. IEEE Trans. On Software Engineering, Vol.2, No.3, pp.223-226, 1976.
[6]
B. Korel, “Automated Software Test Data Generation”, IEEE Trans. On Software Engineering, Vol.16, No8, pp.870-879,
International Journal of Smart Electrical Engineering, Vol.2, No.3, Summer 2013 ISSN: 2251-9246
157
1990.
[7]
N. Tracey, J. Clark, K. Mander, J. McDermid, “An automated framework for structural test-data generation”, In Proceedings of the International Conference on Automated Software Engineering, pp.285-288, IEEE Computer Society Press, Hawaii, USA, 1998.
[8]
D. Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning”, Addison-Wesley, 1989.
[9]
M. Mitchell, “An Introduction to Genetic Algorithms”, MIT Press, Cambridge, MA, 1996.
[10]
P. McMinn, “Search-Based Test Data Generation, A survey”, Journal on Software Testing, Verification and Reliability, Vol.14, No.2, pp.105-156, June 2004.
[11]
A. Watkins, “The Automatic Generation of Test Data Using Genetic Algorithms”, In Proceedings of the Fourth Software Quality Conference, pp.300-309, 1995.
[12]
R. Pargas, M. Harrold, and R. Peck, “Test-Data Generation Using Genetic Algorithms”, Software Testing, Verification and Reliability, Vol.9, No.4, pp.263-282, 1999.
[13]
S. Xanthakis, C. Ellis, C. Skourlas, A. Le Gall, S. Katsikas, K. Karapoulios, “Application of Genetic Algorithms to Software Testing”, In 5th International Conference on Software Engineering and its Applications, pp.625-636, Toulouse, France, 1992.
[14]
J. Wegener, A. Baresel, H. Sthamer, “Evolutionary Test Environment for Automatic Structural Testing”, Information and Software Technology, Vol.43, No.14, pp.841-854, 2001.
[15]
M. Sutton, A. Greene, P. Amini, “Fuzzing: Brute Force Vulnerability Discovery”, 2006.
[16]
B. Jones, H. Sthamer, X. Yang, and D. Eyres, “The Automatic Generation of Software Test Data Sets Using Adaptive Search Techniques”, In Proceedings of the 3rd International Conference on Software Quality Management, pp.435-444, Seville, Spain, 1995.
[17]
S. Forrest, S. Hofmeyr, A. Somayaji, “Computer Immunology”, Communications of the ACM, Vol.40, No.10, pp.88-96, 1997.
[18]
J. O. Kephart, G. B. Sorkin,W. C. Arnold, D.M. Chess, G. J. Tesauro, S. R.White, “Biologically Inspired Defences Against Computer Viruses”, Machine Learning and Data Mining: Method and Applications, R. S. (Ed) Michalski, I. Bratko, M. Kubat, John-Wiley & Son, pp.313-334, 1997.
[19]
Jung Won Kim, “Integrating Artificial Immune Algorithms for Intrusion Detection”, PhD Thesis, Department of Computer Science, University College London, July 30, 2002.
[20]
F. Gonzalez, “A Study of Artificial Immune Systems Applied to Anomaly Detection”, PhD Thesis, Division of Computer Science, University of Memphis, Memphis, TN 38152, May 2003.
[21]
J. Timmis, “Artificial Immune Systems: A Novel Data Analysis Technique Inspired by the Immune Network Theory”, PhD Thesis, Department of Computer Science,
University of Wales, Aberystwyth, 2001.
[22]
T. Knight, “MARIA: A Multilayered Unsupervised Machine Learning Algorithm Based on the Vertebrate Immune System”, PhD Thesis, The University of Kent at Canterbury, 2005.
[23]
S. Forrest, A. Perelson, L. Allen, R. Allen, Cherukuri, “Self-nonself Discrimination in a Computer”, In Proceedings of the 1994 IEEE Symposium on Research in Security and Privacy, pp.202-212, Los Alamitos, CA. IEEE Computer Society Press, 1994.
[24]
Z. Ji, D. Dasgupta, “Revisiting Negative Selection Algorithms”, Evolutionary Computation, Vol.15, No,2, pp.223-251, 2007.
[25]
F. Esponda, S. Forrest, P. Helman, “A Formal Framework for Positive and Negative Detection Schemes”, pp.357-373, IEEE Systems, Man, and Cybernetics Society, 2003.
[26]
R. G. Pressman, “Software Engineering, a Practitioner’s approach”, McGraw-Hill, 2005.
[27]
B. Beizer, “Software Testing Techniques”, Second Edition, The Coriolis Group, 1990.
[28]
G. J. Myers, ”The Art of Software Testing”, John Wiley & Sons, 2004.
[29]
L. C. Briand, Y. Labiche, Z. Bawar, “Using Machine Learning to Refine Black-Box Test Specifications and Test Suites”, Technical Report, Carleton University, 2007.
[30]
TriTyp source code,
http://www.irisa.fr/lande/gotlieb/resources/Mutants/trityp.c
[31]
Marick B., “The Craft of Software Testing”, Prentice Hall,1995.