Test conditions for fault classes in Boolean specifications

ABSTRACT

Fault-based testing of software checks the software implementation for a set of faults. Two previous papers on fault-based testing [Kuhn 1999; Tsuchiya and Kikuno 2002] represent the required behavior of the software as a Boolean specification represented in Disjunctive Normal Form (DNF) and then show that faults may be organized in a hierarchy. This article extends these results by identifying necessary and sufficient conditions for fault-based testing. Unlike previous solutions, the formal analysis used to derive these conditions imposes no restrictions (such as DNF) on the form of the Boolean specification.

REFERENCES

• 1: DeMillo, R. A., Lipton, R. J., and Sayward, F. G. 1978. Hints on test data selection: Help for the practicing programmer. IEEE Computer 11, 4 (April), 34--41.
• 2: Richard A. DeMillo , A. Jefferson Offutt, Constraint-Based Automatic Test Data Generation, IEEE Transactions on Software Engineering, v.17 n.9, p.900-910, September 1991 [doi>10.1109/32.92910]
• 3: P. G. Frankl , S. N. Weiss, An Experimental Comparison of the Effectiveness of Branch Testing and Data Flow Testing, IEEE Transactions on Software Engineering, v.19 n.8, p.774-787, August 1993 [doi>10.1109/32.238581]
• 4: R. M. Hierons, Comparing test sets and criteria in the presence of test hypotheses and fault domains, ACM Transactions on Software Engineering and Methodology (TOSEM), v.11 n.4, p.427-448, October 2002 [doi>10.1145/606612.606615]
• 5: IEEE. 1990. IEEE Standard Glossary of Software Engineering Terminology, ANSI/IEEE Std. 610.12. New York: Institute of Electrical and Electronics Engineers.
• 6: Kapoor, K. and Bowen, J. P. 2004. Ordering mutants to minimise test effort in mutation testing. In 4th International Workshop, Formal Approaches to Software Testing (FATES). Lecture Notes in Computer Science, vol. 3395. Springer-Verlag, 195--209.
• 7: Kalpesh Kapoor , Jonathan P. Bowen, A formal analysis of MCDC and RCDC test criteria: Research Articles, Software Testing, Verification & Reliability, v.15 n.1, p.21-40, March 2005 [doi>10.1002/stvr.v15:1]
• 8: D. Richard Kuhn, Fault classes and error detection capability of specification-based testing, ACM Transactions on Software Engineering and Methodology (TOSEM), v.8 n.4, p.411-424, Oct. 1999 [doi>10.1145/322993.322996]
• 9: Man F. Lau , Yuen T. Yu, An extended fault class hierarchy for specification-based testing, ACM Transactions on Software Engineering and Methodology (TOSEM), v.14 n.3, p.247-276, July 2005 [doi>10.1145/1072997.1072998]
• 10: L. J. Morell, A Theory of Fault-Based Testing, IEEE Transactions on Software Engineering, v.16 n.8, p.844-857, August 1990 [doi>10.1109/32.57623]
• 11: A. Jefferson Offutt, Investigations of the software testing coupling effect, ACM Transactions on Software Engineering and Methodology (TOSEM), v.1 n.1, p.5-20, Jan. 1992 [doi>10.1145/125489.125473]
• 12: A Jefferson Offutt , Yiwei Xiong , Shaoying Liu, Criteria for Generating Specification-Based Tests, Proceedings of the 5th International Conference on Engineering of Complex Computer Systems, p.119, October 18-22, 1999
• 13: Okun, V., Black, P. E., and Yesha, Y. 2004. Comparison of fault classes in specification-based testing. Inform. Softw. Tech. 46, 8 (June), 525--533.
• 14: Paradkar, A., Tai, K. C., and Vouk, M. A. 1996. Automatic test-generation for predicates. IEEE Trans. Reliab. 45, 4 (Dec.), 515--530.
• 15: Debra J. Richardson , Margaret C. Thompson, An Analysis of Test Data Selection Criteria Using the RELAY Model of Fault Detection, IEEE Transactions on Software Engineering, v.19 n.6, p.533-553, June 1993 [doi>10.1109/32.232020]
• 16: RTCA. 1992. Software Considerations in Airborne Systems and Equipment Certification, DO-178B. Washington DC, USA.
• 17: Kuo-Chung Tai, Theory of Fault-Based Predicate Testing for Computer Programs, IEEE Transactions on Software Engineering, v.22 n.8, p.552-562, August 1996 [doi>10.1109/32.536956]
• 18: Tatsuhiro Tsuchiya , Tohru Kikuno, On fault classes and error detection capability of specification-based testing, ACM Transactions on Software Engineering and Methodology (TOSEM), v.11 n.1, p.58-62, January 2002 [doi>10.1145/504087.504089]
• 19: Sergiy A. Vilkomir , Jonathan P. Bowen, From MC/DC to RC/DC: formalization and analysis of control-flow testing criteria, Formal Aspects of Computing, v.18 n.1, p.42-62, March 2006 [doi>10.1007/s00165-005-0084-7]
• 20: Vouk, M. A., Tai, K. C., and Paradkar, A. 1994. Empirical studies of predicate-based software testing. In 5th International Symposium on Software Reliability Engineering. IEEE Computer Society, 55--64.
• 21: K. S. How Tai Wah, An analysis of the coupling effect I: single test data, Science of Computer Programming, v.48 n.2-3, p.119-161, August 2003 [doi>10.1016/S0167-6423(03)00022-4]
• 22: Weyuker, E. J. 2002. Thinking formally about testing without a formal specification. In Formal Approaches to Testing of Software (FATES), A Satellite Workshop of CONCUR'02. 1--10.
• 23: E. Weyuker , T. Goradia , A. Singh, Automatically Generating Test Data from a Boolean Specification, IEEE Transactions on Software Engineering, v.20 n.5, p.353-363, May 1994 [doi>10.1109/32.286420]
• 24: W. Eric Wong , Aditya P. Mathur, Reducing the cost of mutation testing: an empirical study, Journal of Systems and Software, v.31 n.3, p.185-196, Dec. 1995 [doi>10.1016/0164-1212(94)00098-0]
• 25: Hong Zhu , Patrick A. V. Hall , John H. R. May, Software unit test coverage and adequacy, ACM Computing Surveys (CSUR), v.29 n.4, p.366-427, Dec. 1997 [doi>10.1145/267580.267590]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
      D.2.5 Testing and Debugging

General Terms:
Theory, Verification

Keywords:
Boolean specification, Fault-based testing, fault classes