进化测试是一种以自动生成高质量测试数据为目的的新兴的测试技术,已被成功应用于工程实践中。进化测试的基本思想就是将在不同覆盖准则下的测试数据生成问题转化成一个全局搜索的问题,利用遗传算法等进化算法的全局鲁棒寻优能力搜索所需的测试数据。然而,在结构化测试中,当程序中存在内部状态问题时,进化测试的搜索过程就会受到阻碍,并导致测试数据搜索的失败。 在面向对象程序中,内部状态问题指的是,一个特定测试目标的覆盖往往必须通过一系列的方法调用才能达到。一方面,数据成员的改变只能通过相应的方法接口;另一方面,封装的存在,对于非公有方法的的测试只能通过其相应的公有方法接口来测试,更进一步加大了问题的复杂性。本文为合理的描述面向对象程序测试内部状态问题,针对进化测试动态搜索的驱动需求提出了一种新的程序静态分析方法——分支依赖分析。作者通过对分支依赖关系的详细讨论划分,给出了分支依赖图的定义,设计分支依赖图的构建算法,并且对方法调用链进行了分析,求解控制调用分支信息添加到分支依赖图中。在课题组的共同努力下实现了分支依赖图的构建算法,并应用到了实际的工程项目中。这种依赖分析方法从粒度上突破了传统的语句级的程序依赖分析方法,是一种分支级的分析方法,所得分支依赖图本身信息量减少,更适合用于软件测试特别是进化测试,并且随着分析粒度的增大其实现算法的复杂度也随之减少。