Automated black-box testing of functional correctness using function approximation

ABSTRACT

We consider black-box testing of functional correctness as a special case of a satisfiability or constraint solving problem. We introduce a general method for solving this problem based on function approximation. We then describe some practical results obtained for an automated testing algorithm using approximation by piecewise polynomial functions.

REFERENCES

• 1: J. W. de Bakker, Mathematical Theory of Program Correctness, Prentice-Hall, Inc., Upper Saddle River, NJ, 1980
• 2: Francesco Bergadano , Daniele Gunetti, Testing by means of inductive program learning, ACM Transactions on Software Engineering and Methodology (TOSEM), v.5 n.2, p.119-145, April 1996 [doi>10.1145/227607.227611]
• 3: T.A. Budd, D. Angluin, Two notions of correctness and their relation to testing, Acta Informatica 18, 31--45, 1982.
• 4: E.W. Cheney, Approximation Theory, American mathematical Society Chelsea Publishing, Providence, Rhode Island, 1966.
• 5: R.A. DeMillo, R.J. Lipton, F.G. Sayward, Hints on test data selection: help for the practicing programmer, IEEE Computer 11(4), 34--41, 1978.
• 6: H.B. Enderton, A Mathematical Introduction to Logic, Academic Press, 1972.
• 7: R.G. Hamlet, Testing programs with the aid of a compiler, IEEE Transactions on Software Engineering, 3(4), 279--290, 1977.
• 8: Jacques Loeckx , Kurt Sieber, The foundations of program verification (2nd ed.), John Wiley & Sons, Inc., New York, NY, 1987
• 9: A.J. Offut, J. Pan, Automatically detecting equivalent mutants and infeasible paths, The Journal of Software Testing, Verification and Reliability 7 (3), 165--192, 1997.
• 10: M.S. Phadke, Planning efficient software tests, Crosstalk 10 (10), 11--15, 1997.
• 11: Kathleen Romanik, Approximate testing and its relationship to learning, Theoretical Computer Science, v.188 n.1-2, p.79-99, Nov. 30, 1997 [doi>10.1016/S0304-3975(96)00241-1]
• 12: Kathleen Romanik , Jeffrey Scott Vitter, Using Vapnik-Chervonenkis dimension to analyze the testing complexity of program segments, Information and Computation, v.128 n.2, p.87-108, Aug. 1, 1996 [doi>10.1006/inco.1996.0065]
• 13: Elaine J. Weyuker, Assessing Test Data Adequacy through Program Inference, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.4, p.641-655, Oct. 1983 [doi>10.1145/69575.357231]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

General Terms:
Algorithms, Theory, Verification

Keywords:
approximation, black-box test, constraint solving, formal specification, functional test, satisfiability problem, test coverage