预发布大型软件系统,具有规模庞大、多语言实现、含大量第三方二进制组件等特点,现有的测试方法和技术无法有效实现高效、全面、无误报、跨语言和跨平台的测试目标。本文重点研究了如何将动态测试用例方法应用于预发布二进制软件测试。以构建高效、精确、全面且具有重定向性的高性能动态测试用例生成系统为目的,从系统的体系结构及操作系统的无关性、完备路径可达约束的判定与收集以及缺陷发掘的性能优化等方面进行了深入的研究。本文的主要工作和创新如下:1.当前面向二进制代码缺陷发掘的动态测试用例生成系统往往依赖于目标ISA的细节。本文提出和设计了支持测试系统可重定向的高效元指令集体系结构MetaISA。MetaISA可以精确描述二进制语义,简化动态测试用例生成过程中的约束收集和构建,并提升其性能。实际算法实现中,只需构建新的元指令映射等模块就可实现重定向到新ISA的目标。修改量仅占系统20.9万行代码中的1%。2.已有动态测试用例生成技术因收集的路径可达约束不完备,导致生成大量偏离目标路径的测试用例,测试效率低。本文提出了基于动态测试用例生成的精确可达路径覆盖方法DBAPC,该方法是国际上第一个针对大规模二进制程序进行精确全路径覆盖的缺陷发掘方法。该方法通过构建完备的二进制分支可达判定理论,提出了完备分支可达判定条件的动态收集与构建方法、精确约束求解方法等,设计了测试规模可伸缩的缺陷发掘框架,实现了对大规模二进制程序的精确全路径覆盖的缺陷发掘。可以证明,基于完备分支可达约束的DBAPC方法,能够以最少的测试用例覆盖所有输入数据可控的可达分支路径。3.已有的约束表示与收集方法在对大型二进制软件进行动态路径分析时,其时空复杂度可能以指数方式迅速增加,导致符号化路径分析无法继续。本文提出了具有线性时空复杂度的DBAPC优化方法。该方法通过单赋值污点指令变换技术,将DBAPC方法稳定在线性空间复杂度内;在此基础上定义并构建了可有效描述污点间定值引用关系的单赋值污点传播有向无环图TSADAG和相关算法;最后基于我们提出的目标分支条件相干性理论,设计了最简分支可达约束的线性复杂度收集算法。DBAPC优化方法可有效将路径约束收集过程的空间复杂度保持在线性复杂性,简化了判定分支可达所需的约束集合,大大降低了求解器的求解开销,保证了对大型二进制软件的深度缺陷发掘的高效性。4.已有动态测试用例生成技术无法精确处理指针语义,导致生成大量失效的测试用例,致使测试效率低、测试不全面且指针非法访问漏报率高。基于DBAPC方法,本文进一步提出了支持精确指针语义处理的E-DBAPC方法:提出了基于路径约束的字节精度的完备指针指向分析算法BPSC-PTA,可精确分析污点可控指针的完备可指向区域;基于对污点可控指针的完备指向分析,明确判别指针引用间的潜在数据依赖关系;提出了E-TSADAG扩展方法,满足指针引用间的潜在数据依赖关系、定值引用关系以及约束关系的描述需求;基于E-TSADAG,设计了污点可控路径的完备路径约束收集算法,使求解得到的测试用例具备精确定向性。E-DBAPC方法能够在进行路径动态分析与覆盖的同时,还可根据对污点可控指针的可指向区域的完备分析,精确发掘当前路径上的所有指针越界访问缺陷。5.基于DBAPC/E-DBAPC方法,我们设计和实现了Hunter系统。该系统是国际上首个面向大规模二进制软件缺陷发掘的精确动态测试用例生成系统,已被总参某部采购。Hunter系统具有广泛的平台兼容性,可以针对任意操作系统的多种指令集的二进制软件进行缺陷发掘。Hunter系统通过采用基于虚拟化平台支持的符号化与具体化混合执行的加速技术和操作系统无关的基于虚拟机事件监控的进程/线程识别等技术,有效提高了发掘性能,增强了多系统平台支持能力。测试表明,Hunter系统可以高效自动发掘Benchmark中的所有已知软件缺陷。同时,实际软件系统测试中,Hunter系统先后发现了Word 2007等大型商业应用软件的27个获得厂商承认的致命缺陷,并对定位出错代码和出错原因提供了有效指导。