Bob Binder
07-24-2003, 07:38 PM
"Cagdas Ozgenc" <co19@removeme.cornell.edu> wrote in message news:<bfoge9$a6a$1@news01.cit.cornell.edu>... Greetings. Some of my collegues are extensively developing applications that deal with NP-complete problems. Approaches mostly involve attacking the search space in a random fashion backed up by heuristics. So far we can only assume that the apps are working as designed and do not have any idea how to test these kind of apps at any level (unit, system, etc). Random behavior makes it very hard for us to write test cases. Constraints that guarantee to hold only expose themselves at the very macro level. At the end we feel as if we had built a very complicated random number generator. Things happen, the app comes up with an output. We run it on various input data and then speculate on its effectiveness. The only kind of debugging we can do is to make sure that the apps don't crash. Nothing in terms of functionality. There are lots of heuristic functions, probability calculations. Who knows whether they are producing the desired output. Any suggestions?
Background reading:
Zohar Manna and Richard Waldinger. "The logic of computer
programming," _IEEE Transactions on Software Engineering_
SE-4(3):199-229, May 1978.
Elaine J. Weyuker. "On testing non-testable programs." _The Computer
Journal_ 25(4):465-70, 1982.
William E. Howden, "A Functional Approach to Program Testing and
Analysis", _IEEE Transactions on Software Engineering_ 12(10) Oct
1986, 997-1005.
and
-- _Functional Program Testing and Analysis_. New York: McGraw-Hill,
Inc. 1987.
Specific steps:
Identify and place as many invariants in the code as you can. See
chapter 17, "Assertions" in my _Testing Object-Oriented Systems_, in
particular section 17.2.2.
See chapter 18, "Oracles" of my _Testing Object-Oriented Systems_ for
more about evaluation strategies.
Use mutation to assess your existing test suites and assertions. For a
nice overview, see Larry J. Morell and Lionel E. Deimel, _Unit
Analysis and Testing._ SEI Curriculum Module SEI-CM-9-2.0.
Carnegie-Mellon University, Software Engineering Institute, June 1992.
Try using model checking on the results -- this has proven to be very
useful in revealing incorrect results in very large output sets,
including crypto apps. See Clarke, Gurmberg, and Peled, _Model
Checking_, for more.
Hth
Bob Binder
Background reading:
Zohar Manna and Richard Waldinger. "The logic of computer
programming," _IEEE Transactions on Software Engineering_
SE-4(3):199-229, May 1978.
Elaine J. Weyuker. "On testing non-testable programs." _The Computer
Journal_ 25(4):465-70, 1982.
William E. Howden, "A Functional Approach to Program Testing and
Analysis", _IEEE Transactions on Software Engineering_ 12(10) Oct
1986, 997-1005.
and
-- _Functional Program Testing and Analysis_. New York: McGraw-Hill,
Inc. 1987.
Specific steps:
Identify and place as many invariants in the code as you can. See
chapter 17, "Assertions" in my _Testing Object-Oriented Systems_, in
particular section 17.2.2.
See chapter 18, "Oracles" of my _Testing Object-Oriented Systems_ for
more about evaluation strategies.
Use mutation to assess your existing test suites and assertions. For a
nice overview, see Larry J. Morell and Lionel E. Deimel, _Unit
Analysis and Testing._ SEI Curriculum Module SEI-CM-9-2.0.
Carnegie-Mellon University, Software Engineering Institute, June 1992.
Try using model checking on the results -- this has proven to be very
useful in revealing incorrect results in very large output sets,
including crypto apps. See Clarke, Gurmberg, and Peled, _Model
Checking_, for more.
Hth
Bob Binder