Unit-level test adequacy criteria for visual dataflow languages and a testing methodology

ABSTRACT

Visual dataflow languages (VDFLs), which include commercial and research systems, have had a substantial impact on end-user programming. Like any other programming languages, whether visual or textual, VDFLs often contain faults. A desire to provide programmers of these languages with some of the benefits of traditional testing methodologies has been the driving force behind our effort in this work. In this article we introduce, in the context of prograph, a testing methodology for VDFLs based on structural test adequacy criteria and coverage. This article also reports on the results of two empirical studies. The first study was conducted to obtain meaningful information about, in particular, the effectiveness of our all-Dus criteria in detecting a reasonable percentage of faults in VDFLs. The second study was conducted to evaluate, under the same criterion, the effectiveness of our methodology in assisting users to visually localize faults by reducing their search space. Both studies were conducted using a testing system that we have implemented in Prograph's IDE.

REFERENCES

• 1: Agrawal, H., Horgan, J., London, S., and Wong, W. 1995. Fault localization using execution slices and dataflow tests. In Proceedings of the 6th IEEE International Symposium on Software Reliability Engineering. 143--151.
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: Azem, A., Belli, F., Jack, O., and Jedrzejowicz, P. 1993. Testing and reliability of logic programs. In Proceedings of the 4th International Symposium on Software Reliability Engineering. 318--327.
• 4: Belli, F. and Jack, O. 1995. A Test coverage notion for logic programming. In Proceedings of the 6th IEEE International Symposium on Software Reliability Engineering. IEEE Computer Society, Los Alamitos, CA, 133--142.
• 5: Massimo Bernini , Mauro Mosconi, VIPERS: a data flow visual programming environment based on the Tcl language, Proceedings of the workshop on Advanced visual interfaces, p.243-245, June 01-04, 1994, Bari, Italy [doi>10.1145/192309.192361]
• 6: Boulus, J., Karam, M. R., Koteiche, Z., and Ollaic, H. 2006. XQueryViz: An XQuery visualization tool. In Proceedings the 10th International Conference on Extended Database Technologies. Munich, Germany, 1155--1158.
• 7: Margaret Burnett , Richard Hossli , Tim Pulliam , Brian VanVoorst , Xiaoyang Yang, Toward Visual Programming Languages for Steering Scientific Computations, IEEE Computational Science & Engineering, v.1 n.4, p.44-62, December 1994 [doi>10.1109/99.338768]
• 8: Shi-Kuo Chang , Michael J. Tauber , Bing Yu , Jing-Sheng Yu, A Visual Language Compiler, IEEE Transactions on Software Engineering, v.15 n.5, p.506-525, May 1989 [doi>10.1109/32.24700]
• 9: Christ, R. 1975. Review and analysis of color coding research for visual displays. Human Factors. 17, 6, 542--570.
• 10: L. A. Clarke, A System to Generate Test Data and Symbolically Execute Programs, IEEE Transactions on Software Engineering, v.2 n.3, p.215-222, May 1976 [doi>10.1109/TSE.1976.233817]
• 11: L. A. Clarke , A. Podgurski , D. J. Richardson , S. J. Zeil, A Formal Evaluation of Data Flow Path Selection Criteria, IEEE Transactions on Software Engineering, v.15 n.11, p.1318-1332, November 1989 [doi>10.1109/32.41326]
• 12: Del Frate, F., Garg, P., Mathur, A., and Pasquini, A. 1995. On the correlation between code coverage and software reliability. In proceedings of the 6th International Symposium on Software Reliability Engineering. 124--132.
• 13: Fisk, D. 2003. Full metal jacket: A pure visual dataflow language built on top of Lisp. In Proceedings of the International Lisp Conference. New York, NY, 232--238.
• 14: 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]
• 15: Frankl, P., Weiss, S., Weyuker, E. J. 1985. ASSET: A system to select and evaluate tests. In Proceedings of the IEE Conference on Software Tools. 72--79.
• 16: P. G. Frankl , E. J. Weyuker, An Applicable Family of Data Flow Testing Criteria, IEEE Transactions on Software Engineering, v.14 n.10, p.1483-1498, October 1988 [doi>10.1109/32.6194]
• 17: Gren, T. R. G. and Petre, M. 1996. Usability analysis of visual programming environments: A “cognitive dimensions” framework. J. Visual Lang. Comput. 7, 2, 131--174.
• 18: Gupta, R., Harrold, M. J., and Soffa, M. L. 1996. Program slicing-based regression testing techniques. J. Softw. Test. Veri. Rel. 6, 2, 83--112.
• 19: Harrold, M. J. and Soffa, M. L. 1988. An incremental approach to unit testing during maintenance. In Proceedings of the Conference on Software Maintenance. 362--367.
• 20: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 21: Monica Hutchins , Herb Foster , Tarak Goradia , Thomas Ostrand, Experiments of the effectiveness of dataflow- and controlflow-based test adequacy criteria, Proceedings of the 16th international conference on Software engineering, p.191-200, May 16-21, 1994, Sorrento, Italy
• 22: James A. Jones , Mary Jean Harrold , John Stasko, Visualization of test information to assist fault localization, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581397]
• 23: Marcel R. Karam , Trevor J. Smedley, A Testing Methodology for a Dataflow Based Visual Programming Language, Proceedings of the IEEE 2001 Symposia on Human Centric Computing Languages and Environments (HCC'01), p.280, September 05-07, 2001
• 24: Marcel Karam , Jihad Boulos , Hala Ollaic , Zeina Koteiche, XQueryViz: A Visual Dataflow XQuery Tool, Proceedings of the Advanced Int'l Conference on Telecommunications and Int'l Conference on Internet and Web Applications and Services, p.196, February 19-25, 2006
• 25: Kelso J. 2002. A visual programming environment for functional languages. Ph. D. Thesis. Murdoch University, Australia.
• 26: Kimura, T. D., Choi, J. W., and Mack, J. M. 1990. Show and tell: a visual programming language. In E. P. Glinert Ed. Visual Progrmming Environments. IEEE Computer Society Press, 397--404.
• 27: Kuhn, W. and Frank, A. U. 1997. The use of functional programming in the specification and testing process. In Proceedings of the International Conference and Workshop on Interoperating Geographic Information Systems.
• 28: J. W. Laski , B. Korel, A Data Flow Oriented Program Testing Strategy, IEEE Transactions on Software Engineering, v.9 n.3, p.347-354, May 1983 [doi>10.1109/TSE.1983.236871]
• 29: B. Korel , J. Laski, A tool for data flow oriented program testing, Proceedings of the second conference on Software development tools, techniques, and alternatives, p.34-37, December 1985, San Francisco, California, United States
• 30: Ben Liblit , Mayur Naik , Alice X. Zheng , Alex Aiken , Michael I. Jordan, Scalable statistical bug isolation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 31: Luo, G., Bochmann, G., Sarikaya, B., and Boyer, M. 1992. Control-flow based testing of Prolog programs. In Proceedings of the 3rd International Symposium on Software Reliability Engineering. 104--113.
• 32: Marten#8482;. 2007. http://www.andescotia.com.
• 33: R. Mark Meyer , Tim Masterson, Towards a better visual programming language: critiquing Prograph's control structures, Proceedings of the fifth annual CCSC northeastern conference on The journal of computing in small colleges, p.181-193, April 2000, Ramapo College of New Jersey, Mahwah, New Jersey, United States
• 34: Gerald M. Murch, Physiological principles for the effective use of color, IEEE Computer Graphics and Applications, v.4 n.11, p.49-54, Nov. 1984
• 35: Ntafos, S. C. 1984. On required element testing. IEEE Trans. Softw. Eng. 10, 6, 795--803.
• 36: A. Jefferson Offutt , Jie Pan , Kanupriya Tewary , Tong Zhang, An experimental evaluation of data flow and mutation testing, Software—Practice & Experience, v.26 n.2, p.165-176, Feb. 1996 [doi>10.1002/(SICI)1097-024X(199602)26:2<165::AID-SPE5>3.0.CO;2-K]
• 37: Ouabdesselam, F. and Parissis, I. 1995. Testing techniques for dataflow synchronous programs. In Proceedings of the 2nd International Workshop on Automated and Algorithmic Debugging. 249--260.
• 38: Barry E. Paton, Sensors, transducers, & LabVIEW, Prentice Hall PTR, Upper Saddle River, NJ, 1998
• 39: D. E. Perry , G. E. Kaiser, Adequate testing and object-oriented programming, Journal of Object-Oriented Programming, v.2 n.5, p.13-19, Jan./Feb. 1990
• 40: Sandra Rapps , Elaine J. Weyuker, Selecting Software Test Data Using Data Flow Information, IEEE Transactions on Software Engineering, v.11 n.4, p.367-375, April 1985 [doi>10.1109/TSE.1985.232226]
• 41: Gregg Rothermel , Mary Jean Harrold, A safe, efficient regression test selection technique, ACM Transactions on Software Engineering and Methodology (TOSEM), v.6 n.2, p.173-210, April 1997 [doi>10.1145/248233.248262]
• 42: Gregg Rothermel , Lixin Li , Christopher DuPuis , Margaret Burnett, What you see is what you test: a methodology for testing form-based visual programs, Proceedings of the 20th international conference on Software engineering, p.198-207, April 19-25, 1998, Kyoto, Japan
• 43: Gregg Rothermel , Margaret Burnett , Lixin Li , Christopher Dupuis , Andrei Sheretov, A methodology for testing spreadsheets, ACM Transactions on Software Engineering and Methodology (TOSEM), v.10 n.1, p.110-147, Jan. 2001 [doi>10.1145/366378.366385]
• 44: Shafer, D. 1994. The Power of Prograph CPX, The Reader Network.
• 45: Ben Shneiderman, Designing the user interface (2nd ed.): strategies for effective human-computer interaction, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 46: Weiser, M. 1984. Program slicing. IEEE Trans. Softw. Eng. 10, 4, 352--357.
• 47: E J Weyuker, Axiomatizing software test data adequacy, IEEE Transactions on Software Engineering, v.12 n.12, p.1128-1138, Dec.1986
• 48: E. J. Weyuker, More Experience with Data Flow Testing, IEEE Transactions on Software Engineering, v.19 n.9, p.912-919, September 1993 [doi>10.1109/32.241773]
• 49: Jeannette M. Wing , Amy Moormann Zaremski, A formal specification of a visual language editor, Proceedings of the 6th international workshop on Software specification and design, October 25-26, 1991, Como, Italy
• 50: W. Eric Wong , Joseph R. Horgan , Saul London , Aditya P. Mathur, Effect of test set minimization on fault detection effectiveness, Proceedings of the 17th international conference on Software engineering, p.41-50, April 24-28, 1995, Seattle, Washington, United States [doi>10.1145/225014.225018]
• 51: A. Woodruff , M. Stonebraker, Buffering of intermediate results in dataflow diagrams, Proceedings of the 11th International IEEE Symposium on Visual Languages, p.187, September 05-09, 1995
• 52: Yang, S., Burnett, M., Dekoven, E., and Zloof, M. 1997. Representation design benchmarks: a design-time aid for VPL navigable static representations. J. Visual Lang. Comput. 8, 5/6, 563--599.
• 53: Daqian Zhang , Kang Zhang, Reserved Graph Grammar: A Specification Tool for Diagrammatic VPLs, Proceedings of the 1997 IEEE Symposium on Visual Languages (VL '97), p.284, April 23-26, 1997

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.7 Visual Programming
  D.2 SOFTWARE ENGINEERING
      D.2.6 Programming Environments

General Terms:
Algorithms, Languages, Verification

Keywords:
Software testing, color, fault detection, fault localization, visual dataflow languages