基于卡诺格覆盖的布尔表达式测试及缺陷诊断理论与方法研究

The correctness and validity of the Boolean expressions lay the foundation of the correctness and robustness of software applications. In the past two decades, several strategies for test case selection have been proposed, such as MAX-A/B, MC/DC, MUMCUT and Minimal-MUMCUT. Although the existing researches on Boolean expression testing have made some valuable results, but in this area there is still a lack of formal model studies about the space distribution of Boolean expression faults, which makes it difficult to establish an effective testing strategy. The project aims at systematical researches on Boolean expressions testing at theoretical, technological and application levels. This project mainly focuses in-depth on three aspects: (1) propose a theoretical framework of Boolean expression testing and the fault diagnosis based on cell covering, where cells mean the cells on Karnaugh-map; (2) put forward a generalized total unimodularity approach to solve the optimization problem of test case selection for Boolean expressions and an approach of fault diagnosis based on duality; (3) propose an assurance-based approach to address complex faults of Boolean expressions to generate higher order mutants for Boolean expressions. The innovative contributions of the proposal include the following:.1. Theoretical framework based on cell covering approach: Establish a topological model for Boolean expressions and faults. Define a cell cover problem and prove to guarantee to detect corresponding Boolean expression faults. On the other hand, given a failure of test case, diagnose what fault occurs to the expression..2. Generalized total unimodularity approach: The optimization model of test case selection requires integer solutions, which implies high computing complexity. The project proposes to transfer the matrix of constraints of the optimal models of certain Boolean expression faults, such that the coefficient matrix meets the property of total unimodularity, to reduce the computation complex. The project will diagnose faults of Boolean expressions based on test results and duality approach..3. Assurance-based approach: The complex types of Boolean expression faults are considered difficult to handle. The project introduces an assurance-based approach to formally characterize the faults that users would address and are willing to pay the corresponding cost in terms of computing time. The approach will be applied to address the complex types of faults, such as EIF(./+) and TRF, such that higher order mutants of Boolean expressions can be generated. The mutants will be used for the evaluations of the test cases generated..In addition, the project will develop an on-line prototype system to support the applications of Boolean expression testing, including generation of minimum test cases, high order mutants, and reports on the test case sizes, time consumptions, and mutant scores.

高效诊断布尔表达式缺陷、保证布尔表达式正确性是保障软件系统质量的重要基础之一。虽然现有的布尔表达式测试研究已经取得了一些有价值的成果，但缺乏对布尔表达式缺陷分布及诊断形式化模型研究，难以确立有效的测试及缺陷诊断策略。本课题旨在理论、技术及应用验证三个层面系统地研究布尔表达式测试及缺陷诊断。研究内容主要包括三个方面：（1）基于卡诺格覆盖的布尔表达式测试及缺陷诊断理论框架；（2）基于广义全单模约束矩阵的布尔表达式测试用例选择及缺陷诊断最优化技术；（3）基于用户质量保证期望模型的布尔表达式高阶变体生成方法。本课题特色与创新：分析布尔表达式缺陷拓扑空间变化规律，提出基于最小卡诺格覆盖测试理论、及诊断缺陷方法；分析最优化算法效率，提出广义全单模判定方法；分析布尔表达式高阶变体特征，提出用户质量保证期望模型。在本课题理论及技术研究的基础上，实现一个在线布尔表达式测试及缺陷诊断原型系统。

布尔表达式可以出现在软件生命周期不同阶段的工件（Work product）中。从早期的软件需求规约，到软件概要设计和详细设计，再到软件代码实现，布尔表达式广泛用于描述不同抽象层次的逻辑约束关系，表示应用领域中各种逻辑条件。高效诊断布尔表达式缺陷、保证布尔表达式正确性是保障软件系统质量的重要基础之一。本课题旨在理论、技术及应用验证三个层面系统地研究布尔表达式测试及缺陷诊断。研究内容主要包括三个方面:(1)基于卡诺格覆盖的布尔表达式测试及缺陷诊断理论框架;(2)基于广义全单模约束矩阵的布尔表达式测试用例选择及缺陷诊断最优化技术;(3)基于用户质量保证期望模型的布尔表达式高阶变体生成方法。..本课研究成果包括 (1)设计了一种基于卡诺格覆盖的布尔表达式测试及缺陷诊断理论框架，包括九种单缺陷和其组合的双项双缺陷和单项双缺陷;(2)基于广义全单模约束矩阵的布尔表达式测试用例选择及缺陷诊断最优化技术，建立基于对偶规划的布尔表达式缺陷诊断模型，分析模型的诊断能力，证明了九种布尔表达式单缺陷诊断的规则，提出了最小搜索域方法，以最小增量测试集确保诊断九种单缺陷;(3)基于用户质量保证期望模型的布尔表达式高阶变体生成方法。布尔表达式测试及缺陷诊断本质上是NP难问题，本课题研究基于用户质量保证期望模型，可以根据用户需求控制高阶变体的生成方法时间复杂度，支持验证布尔表达式测试及缺陷诊断方法。..本课题发表了14篇相关的学术论文，一项授权专利，3项专利处在实质审查中，培养16名硕士毕业生。本课题研究科学意义：（1）分析布尔表达式缺陷拓扑空间变化规律，提出基于最小卡诺格覆盖测试理论、及诊断缺陷方法;（2）分析最优化算法效率，提出广义全单模判定方法; （3）分析布尔表达式高阶变体特征，提出用户质量保证期望模型。在本课题理论及技术研究的基础上，迭代设计并实现一个在线布尔表达式测试及缺陷诊断原型系统。