Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Reexamination Certificate
1998-06-30
2001-08-28
Powell, Mark (Department: 2762)
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
Reexamination Certificate
active
06282527
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of problem solving utilizing artificial intelligence techniques. In particular, this invention relates to a method and apparatus utilizing Evolutionary Computation techniques for the adaptive solution of sequential problems. More particularly, the invention applies genetic algorithms for identifying certain software system behavior.
STATEMENT OF THE PROBLEM
Computers are essentially problem solving machines. Most computer systems are configured to solve a particular problem. The problem is known and defined and the computer provides the computational power to receive and process data to determine a solution within the framework of the defined problem. A more difficult computational challenge is presented by problems, which are undefined or changing. These problems require a more human-like or thinking approach to find a solution. An example of such a problem is the testing of complex software systems. Complex computer software systems have a set of potential stimuli that approach infinity. Therefore the problem of selecting more interesting test cases (stimuli combinations) from the universe of possible test cases is one of great interest in the field of software testing.
The testing of software systems has become more difficult and more important as the complexity of software systems has increased. One reason software systems are tested is to identify defects. The system operation giving rise to the defects is then altered to ensure that the defects no longer occur. An objective of any software system testing approach is to maximize testing coverage and defect discovery rate. Ideally one needs to exercise every component or sub-system of a software system and do so with every permutation of possible stimuli in order to find every defect arising from every piece of the software system.
Present software systems are so complex that the number of permutations of possible stimuli approach infinity. It is not possible, within a reasonable amount of time, to fully exercise a complex software system to be sure that every defect has been discovered. Further, present software systems often include different types of software sub-systems, which interact in order to bring about the over-all desired results. For example, a word processor such as Word allows the insertion of OLE objects within a Word document. One common example of this is an Excel worksheet inserted within a Word document. With existing software test systems one needs to know that choosing to insert an Excel worksheet into Word documents means switching from the Word environment to the Excel environment. This must be built into the model of the software system under test. Present test systems are capable of testing each sub-system individually but are not capable of testing the complex interactions between the sub-systems.
Existing software testing systems utilize traditional computing techniques. Existing software testing systems model the software system under test (the “target system” or the “target software system”) as a discrete state machine. This requires a great deal of knowledge about the intended operation of the target system and a significant investment up-front to model the target system prior to testing. One result of the discrete state machine model used in existing testing systems is that existing testing systems are applicable to a specific target software system or at best a general class of target software systems. It is therefore not possible to dynamically test multiple, interacting target systems simultaneously using existing software testing systems. Another problem with the discrete state machine model of the target system is that testing criteria are not easily modified. In existing systems, the test system code must itself be modified if one wants to modify the criteria by which the test of the target system is conducted.
Given that there are an infinite number of inputs or stimuli that can be applied to a complex software system, selection of test cases is critical to maximizing testing coverage and defect discovery rate. A “test case” defines a set of input or stimuli to apply to a target system. Some existing software testing systems randomly select test cases. Other existing software testing systems use probabilistic methods to select test cases. For example, it might be known that a certain feature of a target system was particularly difficult to code and therefore one might decide to select test cases that will exercise that certain feature. Some existing software testing systems use Markov process modeling techniques to select test cases. Existing software testing systems are incapable of learning from past test cases and using that learning to select better or more interesting future test cases.
Once a defect is identified, current software testing systems offer no way to “minimize” the steps of the test case which produce the defect. For example, if a test of a target system results in a defect after 20 hours of continuous testing, there may be hundreds of thousands of inputs made to the target system during the test and no efficient way of determining which of those inputs or combination of inputs actually caused the defect to occur. To “minimize the defect” is to reduce the steps or actions of the test case down to the smallest set of steps that bring about the same defect produced by the larger test case.
There exists a need for an adaptive problem solving system. There exists a further need for a software testing system that selects more interesting test cases by learning from the results of previous test cases. There exists a need that the adaptive software testing system that learns from previous results to start testing with a robust set of initial test cases that are efficiently and intelligently determined. There exists a further need for a software testing system that minimizes a defect-producing test case down to a minimum number of steps that produce the same defect. There exists a related need for a target system test representation that is flexibly applied to different types of target systems and allows for the efficient modification of test criteria. Finally, there exists a need for a software testing system capable of dynamically testing the interaction of multiple target software systems.
STATEMENT OF THE SOLUTION
The above-identified problems, and others, are solved and a technical advance achieved in the field by the adaptive problem solving system of the present invention. A method and apparatus for applying hybrid Evolutionary Computation techniques is provided which enables a user to define a problem from which the system converges to a solution by evolving a population of organisms. In the case of the system of the present invention applied to a software testing application, the population of organisms are a population of test cases which can be applied to software system under test (a “target software system”). The system of the present invention generates an initial population of “interesting” test cases through the use of goal-seeking and user-defined hints. The system of the present invention evolves the population of organisms to select ever more “interesting” test cases where “interesting” is defined by the user. The system of the present invention learns from the results of past test cases to quickly select interesting test cases. One embodiment of the present invention defines “interesting” to mean that a test case produces high code coverage or finds a defect, thus test coverage and defect discovery rate are maximized. Of course, if the definition of “interesting” is modified for other embodiments of the invention, then other characteristics are maximized. When a defect in the target system is discovered, the test system of the present invention operates to minimize the number of steps in a test case to the minimum number of steps necessary to produce the defect. Minimization of the number of steps necessary to produce a defect makes the work of isolating, debugging and fixing defects easier thus
Gounares Alexander
Sikchi Prakash
Banner & Witcoff , Ltd.
Holmes Michael B.
Microsoft Corporation
Powell Mark
LandOfFree
Adaptive problem solving method and apparatus utilizing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive problem solving method and apparatus utilizing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive problem solving method and apparatus utilizing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2457122