An extended fault class hierarchy for specification-based testing

Abstract

Kuhn, followed by Tsuchiya and Kikuno, have developed a hierarchy of relationships among several common types of faults (such as variable and expression faults) for specification-based testing by studying the corresponding fault detection conditions. Their analytical results can help explain the relative effectiveness of various fault-based testing techniques previously proposed in the literature. This article extends and complements their studies by analyzing the relationships between variable and literal faults, and among literal, operator, term, and expression faults. Our analysis is more comprehensive and produces a richer set of findings that interpret previous empirical results, can be applied to the design and evaluation of test methods, and inform the way that test cases should be prioritized for earlier detection of faults. Although this work originated from the detection of faults related to specifications, our results are equally applicable to program-based predicate testing that involves logic expressions.

References

1. Ammann, P., Ding, W., and Xu, D. 2001. Using a model checker to test safety properties. In Proceedings of the 7th Annual International Conference on Eng. of Complex Computer Systems (ICECCS '01). 212--221.
2. Ammann, P. E. and Black, P. E. 2001. A specification-based coverage metric to evaluate test sets. Int. J. Reliab. Qual. Safety Eng. 8, 4 (Dec.), 275--299.
3. Atlee, J. M. and Buckley, M. A. 1996. A logic-model semantics for SCR software requirements. In Proceedings of 1996 International Symposium on Software Testing and Analysis (ISSTA '96). 280--292.
4. Atlee, J. M. and Gannon, J. 1993. State-based model checking of event-driven system requirements. IEEE Trans. Softw. Eng. 19, 1 (Jan.), 24--40.
5. Black, P. E., Okun, V., and Yesha, Y. 2000a. Mutation of model checker specifications for test generation and evaluation. In Proceedings of Mutation 2000. 14--20.
6. Black, P. E., Okun, V., and Yesha, Y. 2000b. Mutation operators for specifications. In Proceedings of the 15th Automated Software Engineering Conference (ASE 2000). 81--88.
7. Chan, W., Anderson, R. J., Beame, P., Burns, S., Modugno, F., Notkin, D., and Reese, J. D. 1998. Model checking large software specifications. IEEE Trans. Softw. Eng. 24, 7 (July), 498--520.
8. Chang, J., Richardson, D. J., and Sankar, S. 1996. Structural specification-based testing with ADL. In Proceedings of 1996 International Symposium on Software Testing and Analysis (ISSTA '96). 62--70.
9. Chen, T. Y. and Lau, M. F. 1997. Two test data selection strategies towards testing of Boolean specifications. In Proceedings of the 21st International Computer Software and Application Conference (COMPSAC '97). 608--611.
10. Chen, T. Y. and Lau, M. F. 2001. Test case selection strategies based on Boolean specifications. Softw. Test. Verif. Reliab. 11, 3 (Sept.), 165--180.
11. Chen, T. Y., Lau, M. F., and Yu, Y. T. 1999. MUMCUT: A fault-based strategy for testing Boolean specifications. In Proceedings of Asia-Pacific Software Engineering Conference (APSEC '99). 606--613.
12. Chen, T. Y. and Yu, Y. T. 1994. On the relationship between partition and random testing. IEEE Trans. Softw. Eng. 20, 12 (Dec.), 977--980.
13. Chen, T. Y. and Yu, Y. T. 1996. On the expected number of failures detected by subdomain testing and random testing. IEEE Trans. Softw. Eng. 22, 2 (Feb.), 109--119.
14. Chilenski, J. J. and Miller, S. P. 1994. Applicability of modified condition/decision coverage to software testing. IEE/BCS Softw. Eng. J. 9, 5 (Sept.), 193--200.
15. Daran, M. and Thévenod-Fosse, P. 1996. Software error analysis: A real case study involving real faults and mutations. In Proceedings of 1996 International Symposium on Software Testing and Analysis (ISSTA '96). 158--171.
16. DeMillo, R. A., Lipton, R. J., and Sayward, F. G. 1978. Hints on test data selection: Help for the practicing programmer. Computer 11, 4 (Apr.), 34--41.
17. Dick, J. and Faivre, A. 1993. Automating the generation and sequencing of test cases from model-based specifications. In Proceedings of the First International Symposium of Formal Methods Europe (FME 1993). Lecture Notes in Computer Science, vol. 670. Springer, Berlin, Germany, 19--23.
18. Dupuy, A. and Leveson, N. 2000. An empirical evaluation of the MC/DC coverage criterion on the HETE-2 satellite software. In Proceedings of Digital Aviation Systems Conference (DASC 2000).
19. Duran, J. W. and Ntafos, S. C. 1984. An evaluation of random testing. IEEE Trans. Softw. Eng. 10, 4 (July), 438--444.
20. Elbaum, S., Malishevsky, A. G., and Rothermel, G. 2002. Test case prioritization: A family of empirical studies. IEEE Trans. Softw. Eng. 28, 2 (Feb.), 159--182.
21. Foster, K. A. 1980. Error sensitive test cases analysis (ESTCA). IEEE Trans. Softw. Eng. 6, 2 (May), 258--264.
22. Foster, K. A. 1984. Sensitive test data for logic expressions. ACM SIGSOFT Softw. Eng. Notes 9, 2 (Apr.), 120--125.
23. Gargantini, A. and Heitmeyer, C. 1999. Using model checking to generate tests from requirements specifications. In Proceedings of the 7th European Software Engineering Conference and the 7th ACM SIGSOFT Symposium on the Foundations of Software Engineering. Lecture Notes in Computer Science, vol. 1687. Springer, Berlin, Germany, 146--162.
24. Gargantini, A. and Riccobene, E. 2001. ASM-based testing: Coverage criteria and automatic test sequence generation. J. Univers. Comput. Sci. 7, 11 (Nov.), 1050--1167.
25. Gargantini, A. and Riccobene, E. 2003. Automatic model driven animation of SCR specifications. In Proceedings of the Sixth International Conference on Fundamental Approaches to Software Engineering (FASE 2003). Lecture Notes in Computer Science, vol. 2621. Springer, Berlin, Germany, 294--309.
26. Heimdahl, M. P. and Leveson, N. G. 1996. Completeness and consistency in hierarchical state-based requirements. IEEE Trans. Softw. Eng. 22, 6 (June), 363--377.
27. Heitmeyer, C. and Bharadwaj, R. 2000. Applying the SCR requirements method to the light control case study. J. Univers. Comput. Sci. 6, 7 (Aug.), 650--678.
28. Hierons, R. M. 1997. Testing from a Z specification. Softw. Test. Verif. Reliab. 7, 1 (Mar.), 19--33.
29. Hierons, R. M. 2002. Comparing test sets and criteria in the presence of test hypotheses and fault domains. ACM Trans. Softw. Eng. Method. 11, 4 (Oct.), 427--448.
30. Jones, J. A. and Harrold, M. J. 2003. Test-suite reduction and prioritization for modified condition/decision coverage. IEEE Trans. Softw. Eng. 29, 3 (Mar.), 195--209.
31. Kobayashi, N., Tsuchiya, T., and Kikuno, T. 2002. Non-specification-based approaches to logic testing for software. Inf. Softw. Tech. 44, 2 (Feb.), 113--121.
32. Kuhn, D. R. 1999. Fault classes and error detection capability of specification-based testing. ACM Trans. Softw. Eng. Method. 8, 4 (Oct.), 411--424.
33. Lau, M. F. and Yu, Y. T. 2001. On the relationships of faults for Boolean specification based testing. In Proceedings of Australian Software Engineering Conference (ASWEC 2001). 21--28.
34. Leveson, N. G., Cha, S. S., and Shimeall, T. J. 1991. Safety verification of ADA programs using software fault trees. IEEE Softw. 8, 4 (July), 48--59.
35. Leveson, N. G., Heimdahl, M. P. E., Hildreth, H., and Reese, J. D. 1994. Requirements specification for process-control systems. IEEE Trans. Softw. Eng. 20, 9 (Sept.), 684--707.
36. Madeira, H., Costa, D., and Vieira, M. 2000. On the emulation of software faults by software fault injection. In Proceedings of International Conference on Dependable Systems and Networks (DSN 2000). 417--426.
37. Myers, G. J. 1979. The Art of Software Testing, 2nd ed. John Wiley, New York, NY.
38. Offutt, A. J., Lee, A., Rothermel, G., Untch, R. H., and Zapf, C. 1996. An experimental determination of sufficient mutant operators. ACM Trans. Softw. Eng. Method. 5, 2 (Apr.), 99--118.
39. Offutt, A. J., Liu, S., Abdurazik, A., and Ammann, P. 2003. Generating test data from state-based specifications. Softw. Test. Verif. Reliab. 13, 1 (Mar.), 25--53.
40. Paradkar, A., Tai, K., and Vouk, M. 1997. Specification-based testing using cause-effect graphs. Ann. Softw. Eng. 4, 133--157.
41. Richardson, D. J. and Thompson, M. C. 1993. An analysis of test data selection criteria using the RELAY model of fault detection. IEEE Trans. Softw. Eng. 19, 6 (June), 533--553.
42. RTCA/DO-178B. 1992. Software Considerations in Airborne Systems and Equipment Certification. RTCA, Inc., Washington, DC.
43. Stock, P. and Carrington, D. 1996. A framework for specification-based testing. IEEE Trans. Softw. Eng. 22, 11 (Nov.), 777--793.
44. Tai, K. C. 1996. Theory of fault-based predicate testing for computer programs. IEEE Trans. Softw. Eng. 22, 8 (Aug.), 552--562.
45. Tai, K. C. and Su, H. K. 1987. Test generation for Boolean expressions. In Proceedings of the 11th International Computer Software and Application Conference (COMPSAC '87). 278--284.
46. Tsuchiya, T. and Kikuno, T. 2002. On fault classes and error detection capability of specification-based testing. ACM Trans. Softw. Eng. Method. 11, 1 (Jan.), 58--62.
47. Vouk, M. A., Tai, K. C., and Paradkar, A. 1994. Empirical studies of predicate-based software testing. In Proceedings of International Symposium on Software Reliability Engineering. 55--64.
48. Weyuker, E. J., Goradia, T., and Singh, A. 1994. Automatically generating test data from a Boolean specification. IEEE Trans. Softw. Eng. 20, 5 (May), 353--363.
49. Yu, Y. T. and Lau, M. F. 2002. Prioritization of test cases in MUMCUT test sets: An empirical study. In Proceedings of the 7th International Conference on Reliable Software Technologies---Ada-Europe 2002. Lecture Notes in Computer Science, vol. 2361. Springer, Berlin, Germany, 245--256.
50. Yu, Y. T., Lau, M. F., and Chen, T. Y. 2003. Automatic generation of test cases from Boolean specifications using the MUMCUT strategy. Submitted for publication.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Verification

• Software and its engineering

  • Software creation and management

    • Designing software

      • Requirements analysis

    • Software development process management

    • Software verification and validation

      • Formal software verification

      • Software defect analysis

        • Software testing and debugging

  • Software organization and properties

    • Software functional properties

      • Formal methods

        • Software verification

• Theory of computation

  • Semantics and reasoning

    • Program reasoning

      • Program verification