D. Richard Kuhn – Computer Scientist, National Institute of Standards & Technology
LogiGear: How did you become interested in developing applications for combinatorial research? What led you to it personally, and what did you find fascinating about it?
Mr. Kuhn: About 12 years ago Dolores Wallace and I were investigating causes of software failures in medical devices. About that time, Raghu Kacker in our math division introduced me to some work on the design of experiments and testing, which had been done by a colleague of his at Bell Labs. The idea behind these methods was that some failures only occur as a result of an interaction between components. For example, a system may correctly produce error messages when space is exhausted or when input rate exceeds some limit, but crashes only when these two conditions are both true at the same time. Pairwise testing has been used for a long time to catch this sort of problem.
I wondered if we could determine what proportion of the medical device failures were caused by interactions, and just how complex the interactions would be – in other words, how many failures were triggered by just one parameter value, and how many only happened when 2, 3, 4, etc. conditions were simultaneously true. We were surprised to find that no one had looked at this question empirically before. It turned out that all of the failures in the FDA reports appeared to involve four or fewer parameters. This was a very limited sample in one application domain, so I started looking at others and found a similar distribution. So far we have not seen a failure involving more than 6 parameters. This does not mean there aren’t any, but the evidence so far suggests that a small number of parameter values are involved in failures. In general, most problems are caused by one or two input values, fewer by an interaction among three, and still fewer at each step as we increase interactions above three.
What’s interesting about this research is that it suggests we can significantly improve the efficiency and the effectiveness of software testing – if we can test all 4-way to 6-way interactions, we are likely to catch almost all errors, although there are a lot of caveats to that statement and we don’t want to oversell this. In particular, selection of test values is critical unless a variable has a small set of discrete values, but this problem exists for all test methods. With the Automated Combinatorial Testing for Software (ACTS) project and tool, we hope to make these methods practical for real-world testing.
LogiGear: What has been your own personal contribution to this research and development? What sort of problems are you attracted to and how have you been able to solve them?
Mr. Kuhn: The series of papers that I did on the number of parameters involved in interaction failures has helped establish an empirical basis for the work and seems to have encouraged research on combinatorial testing by others. I also developed a parallel algorithm for generating combinatorial tests, although, frankly, there hasn’t been much need for it since Jeff Lei’s IPOG algorithm in the ACTS tool is so fast. More recently I’ve worked out a way to apply combinatorial methods to testing event sequences – instead of n! Tests for n events, the number of tests is proportional to log n. This method was motivated by interoperability testing, and it has already been used successfully.
I’ve always been fascinated by large collections of data – whether there might be some interesting or useful properties hiding in a mass of numbers. This is one area where that interest seems to have paid off. Another is some work I did showing that there’s a hierarchy of fault classes for boolean expressions.
LogiGear: What do you think is the current state of this development? You’re working on developing an open-source testing tool. How practical is it now? What successes have you experienced with it and what does it need? Also, how would you like its development to proceed in the future -would you like to see it take off and be developed as a sort of ‘Linux OS’ of combinatorial testing? What would you tell those who seek to get involved in this work?
Mr. Kuhn: The ACTS tool development is being led by Jeff Lei at U. of Texas Arlington, who has been an integral part of this project since the beginning. It’s very robust and has been acquired by several hundred organizations, and so far the feedback is very positive. It appears to be easier to use and more efficient than other tools out there, but we want to integrate lessons learned and make it better for real-world projects. In particular, the constraint handling feature is being strengthened. This is what you need, for example, to prevent the generation of tests that specify Internet Explorer on a Linux system. It already has this ability, but we are learning new needs from users all the time.
I like your suggestion that ACTS could be like Linux, in that Linux has become both a freely available tool and the basis for successful commercial products and services. It would be great if ACTS followed a similar path. In fact we are already seeing commercial extensions of it.
LogiGear: And finally, where do you see your own contributions and questions heading in the future? Where do you see this group – this “movement” if you will – headed?
Mr. Kuhn: Two things I really want to work on are integrating combinatorial testing with formal specifications and model based testing, and investigating the combinatorial coverage of tests developed with other methods. Both of these efforts should help to make this kind of testing more practical and cost effective. We have a good start on both, but we need better automation and tool support. The evidence so far suggests that we can make testing more efficient, but we need real-world data to prove it. I also want to understand the relationship between test value selection and combinatorial testing – are combinatorial methods more or less sensitive than other test methods to the choice of input values? But our primary goal is to collect and analyze data on real-world projects.
LogiGear: Thank you, Mr. Kuhn.
| LogiGear Corporation LogiGear Corporation provides global solutions for software testing, and offers public and corporate software-testing training programs worldwide through LogiGear University. LogiGear is a leader in the integration of test automation, offshore resources and US project management for fast and cost-effective results. Since 1994, LogiGear has worked with hundreds of companies from the Fortune 500 to early-stage startups, creating unique solutions to exactly meet their needs. With facilities in the US and Vietnam, LogiGear helps companies double their test coverage and improve software quality while reducing testing time and cutting costs. For more information, contact Joe Hughes + 01 650.572.1400 |
