软件测试是现阶段保障软件质量的重要手段。软件测试中的诸如语句覆盖、路径覆盖等问题可以归结为面向路径的测试数据的生成问题。该问题在本文中简称为问题2，可以描述为：给定一个程序P和P中一条路径W，设P的输入空间为D，求(?)∈D，使得P以(?)为输入运行，所经过的路径为W。自动求解该问题将有效地提高软件测试的效率和质量。 求解问题2的实质在于约束系统的建立和求解。建立约束系统的困难是分析、化简路径W上的各种语句成分和各种数据类型，建立尽可能简洁的约束系统；求解约束系统的主要困难是处理可能存在的非线性约束。Matiyasevic和E.J.Weyuker等人的研究表明：不存在通用的有效的算法，对于任意的P和W，能生成使W被经过的输入数据。但是实际应用的需要迫使人们进行研究，并提出各种方法求解问题2。 本文首先简要介绍该领域的研究进展，将现有的求解方法分为四类——随机法、静态法、动态法和试探法，介绍和分析每一类中有代表性的方法，并探讨研究方向。 迭代松弛法是Neelam Gupta等人提出的一种自动求解问题2的方法。该方法通过分析W上各语句之间的静态、动态数据依赖关系，构造谓词片和输入依赖集，用线性算术表示对谓词函数进行线性化，仅能够用于白盒测试数据的自动生成。 Neelam Gupta等人将最小二乘解法用于求解问题2。Jon Edvardsson等人指出，对于谓词函数均为输入变量的线性函数的程序路径，Neelam Gupta等人提出的求解方法是不完备的和非终止的，并建议采用线性规划、线性(混合)整数规划方法。 本文改进迭代松弛法，省略构造谓词片和输入依赖集的过程。更进一步，当用均差作为谓词函数关于输入变量的导数的近似时，计算线性算术表示就全部转化为计算谓词残量，而后者无须分析W上各语句之间的静态、动态数据依赖关系。此时，改进后的方法比原方法生成测试数据的能力更强，能够用于黑盒测试数据的自动生成。改进后的方法建立线性约束系统的效率更高。 本文给出一种模型语言；给出一个比较完整的形式化描述，该描述可用于证明与静态、动态数据依赖关系有关的程序性质；给出迭代松弛法中各概念的形式化定义；深入研究迭代松弛法及其改进后的方法的程序理论，其结果包括：将Neelam Gupta等人提出的谓词片推广为路径静态切片，证明路径静态切片构造算法的正确性，证明改进后的方法与原方法所生成的线性约束系统相同。 本文提出一个面向路径的测试数据生成框架。该框架以改进后的迭代松弛法为核心算法，对于谓词函数均为输入变量的线性函数的程序路径，采用基于线性规划、线性(混合)整数规划的约束求解器；对于谓词函数中含有输入变量的非线性函数的程序路径，采用线性规划、线性(混合)整数规划和最小二乘解法相结合的约束求解器。它具有以下 国防科学技术大学研究生院学位论文性质：若W上各谓词函数均为输入变量的线性函数，并且所有输入变量均无整数限制；则框架迭代一次后，或者找到W的解，或者保证w不可行；当谓词函数中含有输入变量的非线性函数时，可能需要迭代多次。 本文开发了面向路径的测试数据生成框架的一个原型工具。用实际的程序路径对该工具进行实验。初步的实验结果表明框架是比较有效的，不仅能够用于白盒、黑盒测试数据的自动生成，而且能够用于面向断言的测试数据自动生成和回归测试数据的自动生成。