Automatic testing of software with structurally complex inputs
Automatic testing of software with structurally complex inputs
复制标题
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
D. Marinov
中科院分区：
文献类型：
--
作者：
D. Marinov
现代软件普遍使用结构复杂的数据，如链接数据结构。为这样的软件生成测试套件的标准方法，即在套件中手动生成输入，是乏味且容易出错的。本文提出了一种新的方法，用于生成结构复杂的测试输入套件，提出了一种技术，自动化这种方法，描述了Korat工具，实现这种技术的Java，并评估Korat在测试一组数据结构实现的有效性。我们的方法允许开发人员使用熟悉的实现语言（如Java）来描述有效测试输入的属性。具体来说，用户提供一个命令式谓词（返回真值的一段代码），如果输入满足所需属性，则返回true，否则返回false。Korat实现了我们的技术解决强制性谓词：给定一个谓词和谓词的输入的大小上的约束，Korat自动生成有界穷举测试套件，该测试套件由所有输入组成，在给定的范围内，满足由谓词确定的属性。为了生成这些输入，Korat通过对候选输入执行谓词来系统地搜索有界输入空间。Korat通过基于谓词的执行和仅生成非同构输入来修剪搜索，从而有效地做到了这一点。有界穷举测试是一种在给定的小范围内对所有输入进行测试的方法。我们的一组10个链接和基于数组的数据结构的实验表明，Korat可以有效地产生有界穷举测试套件，即使是非常大的输入空间，这些测试套件可以实现高语句，分支，突变覆盖率的命令谓词。此外，使用我们的技术产生结构复杂的测试输入，使测试人员在工业中检测故障，在真实的，生产质量的应用。（副本可从麻省理工学院图书馆，RM。14-0551，剑桥，MA 02139-4307。电话：617-253-5668;传真：617-253-1690。）
Modern software pervasively uses structurally complex data such as linked data structures. The standard approach to generating test suites for such software, manual generation of the inputs in the suite, is tedious and error-prone. This dissertation proposes a new approach for generating suites with structurally complex test inputs; presents a technique that automates this approach; describes the Korat tool that implements this technique for Java; and evaluates the effectiveness of Korat in testing a set of data-structure implementations. Our approach allows the developer to describe the properties of valid test inputs using a familiar implementation language such as Java. Specifically, the user provides an imperative predicate—a piece of code that returns a truth value—that returns true if the input satisfies the required property and false otherwise. Korat implements our technique for solving imperative predicates: given a predicate and a bound on the size of the predicate's inputs, Korat automatically generates the bounded-exhaustive test suite that consists of all inputs, within the given bound, that satisfy the property identified by the predicate. To generate these inputs, Korat systematically searches the bounded input space by executing the predicate on the candidate inputs. Korat does this efficiently by pruning the search based on the predicate's executions and by generating only non-isomorphic inputs. Bounded-exhaustive testing is a methodology for testing the code on all inputs within the given small bound. Our experiments on a set of ten linked and array-based data structures show that Korat can efficiently generate bounded-exhaustive test suites from imperative predicates even for very large input spaces and that these test suites can achieve high statement, branch, and mutation coverage. Moreover, the use of our technique for generating structurally complex test inputs has enabled testers in industry to detect faults in real, production-quality applications. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)