D. Richard Kuhn – Computer Scientist, National Institute of Standards & Technology
LogiGear: How did you get into software testing? What did you find interesting about it?
Mr. Kuhn: About 10 years ago Dolores Wallace and I were investigating the causes of software failures in medical devices, using 15 years of data from the FDA. About that time, Raghu Kacker, in NIST’s math division, introduced me to some work that his colleague at Bell Labs, Sid Dalal, had done on pairwise and interaction testing for software. The idea behind these methods is that some failures only occur as a result of interaction between some components. For example, a system may correctly produce error messages when file space is exhausted or user input 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 the interaction of two or more parameters, 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. The reason this is significant is that if we can test all 4-way to 6-way interactions, we are likely to catch almost all errors, although there are many caveats to that statement and we don’t want to oversell this.
LogiGear: You are working in very special field of software testing. It’s quite different to common software testing like: Unit tests, Automation testing, GUI Testing, etc…. So what kind of work are you doing? How did you pick those specific topics? Can you help explain this type of testing to our readers?
Mr. Kuhn: NIST’s mission is to develop better measurement and test methods, so Raghu and I proposed an internal project to build on the empirical findings discussed earlier. The first problem that had to be solved was to find ways of efficiently generating tests that cover all t-way combinations, for t=2, 3, 4, etc. This is a hard mathematical problem that has been studied for a century or more. Jeff (Yu) Lei had developed a very efficient algorithm to cover 2-way combinations as part of his dissertation at NC State, so we talked to him about extending the algorithm for t-way combinations. He did this successfully and we worked with him to incorporate the algorithm into a practical tool for testers, which is now being used at more than 300 companies.
The tool, ACTS, makes it easy for testers to enter parameter names and values for each, then generates test values that cover 2-way through 6-way combinations. For realistic applications, this can produce thousands of tests in some cases, so we have also worked on ways to automate the oracle problem for testing – how to determine the expected results for a particular set of input. This allows testing to be (almost) fully automated, so running hundreds or even thousands of tests can be done at a reasonable cost.
LogiGear: How can a college student prepare to go into software testing and become really good at it? What should he/she look for in teachers, courses, and methods?
Mr. Kuhn: The biggest challenge in software assurance is how to do it economically. Assurance methods used for life-critical software, such as in aviation, are too expensive for most applications, yet every year we become more dependent on software working correctly. One of the best ways to reduce cost, as in other fields, is to bring more science and technology to bear on the problem, so courses that focus more on the science than on managing testing will be important. Testing is only one part of assurance. An important area of research is how to integrate formal methods for specification and proof with testing, including combinatorial interaction testing.
LogiGear: What sort of graduate programs? Also, in your opinion, what are some of the more interesting research questions people are asking now and what do you think they’ll be researching in, say, 5 years?
Mr. Kuhn: Graduate programs with an established program in software engineering will be good choices for work in software assurance. In addition to how to integrate formal methods with combinatorial testing, important questions include: how to order or prioritize tests to find faults more quickly, how to identify the particular combination(s) that caused a failure, how to extend these methods to very large problems, and above all, determining the effectiveness of these methods in the real world. It would be nice if these problems were solved quickly, but I’m sure they will still be important in 5 years. Combinatorial testing has grown very rapidly in the past 10 years, from around 4 or 5 papers a year in the 1990s though 2002, to more than 50 per year recently, so it seems to be attracting a good deal of attention from researchers.
LogiGear: Lastly, who do you consider to be some of the leaders in this field and what are they doing?
Mr. Kuhn: In addition to Jeff Lei (U. Texas, Arlington) and Jim Lawrence (George Mason U.), who have been part of our team since the beginning, Charles Colbourn, at ASU, is the expert on t-way covering arrays and algorithms. We’re working with Renee Bryce (Utah State) and Sreedevi Sampath (U. of Maryland Baltimore County), who are looking at test prioritization. Myra Cohen (U. Nebraska-Lincoln) has done a good deal of work on both the theory and application of these methods. There are many other leaders including Sid Dalal, George Sherwood (from former AT&T, Bellcore, SAIC) , and Alan Hartman (from IBM)
A lot of people are now working on getting these methods into practice. Among those we are working with are Jim Higdon at Eglin Air Force Base and Justin Hunter of Hexawise. Turning research ideas into something that works in the real world can be more challenging than the research in some ways.
LogiGear: Thank you, Mr. Kuhn