Automated software testing with context-free grammars and covering arrays

点击翻译按钮获取中文摘要

Computer software plays a central role in the modern world: in the Internet and consumer electronics, but also in the plants which generate electrical power, refine chemicals and manufacture automobiles. Software bugs are expensive, costing billions per year to repair. Software testing is the primary way that bugs are discovered before software is released for use. Testing is expensive. Often the cost of testing a software product exceeds the cost of developing the software. Much of testing today is manual; testers run the software, imitating actual use. Because of the complexity of modern software, many tests are required. The tests are re-run against each new version of the software. With automated testing, testers write special test software to perform the tests. The test software uses sophisticated mathematical techniques to generate large numbers of test cases. The test software is expensive to develop but inexpensive to run, making automated testing much more efficient in the long run. The proposed research will develop test software. We will apply context-free grammars and covering arrays, techniques developed by research mathematicians, to software testing. While our work can be used to test any kind of software, we will focus on a few specific kinds. The extended markup language (XML) has become the dominant data exchange format on the web. It is so widely used that bugs in XML applications can have serious consequences. Computers in modern factories and chemical plants are controlled by specialized computers. It turns out that these computers are vulnerable to web-based network attacks. Failures in these computers can have extremely serious consequences. Finally, we have found that automated testing techniques can be used to generate tests for students as well as software. We will use these techniques to develop web applications which test students on their knowledge of computer programming.