Test Case Generation for Boolean Expressions by Cell Covering

This paper characterizes Boolean expression faults as changes of the topological structures in terms of shrinking and/or expanding regions in K-map. A cell-covering is a set of cells (test cases) in K-map to cover the fault regions such that faults guarantee to be detected. Minimizing cell covering can be formulated as an Integer Linear Programming (ILP) problem. By analyzing the structures of the constraint coefficient matrix, the original problem can be decomposed into sub-programs that can be solved instead of the original problem, and this significantly reduces the time needed for ILP execution. An efficient approximate algorithm with a tight theoretical bound is used to address those complex Boolean expressions by corresponding the cell-covering problem to the set-covering problem. The optimal approach and the approximate approach are combined into a hybrid process to identify test cases based on the fraction analysis on the ILP relaxation. The proposed approach is evaluated by three sets of Boolean expressions and the results are compared with three leading approaches with respect to test sizes, time consumption and fault detection capabilities. For most Boolean expressions encountered, the proposed approach obtains optimal solutions quickly, and produces near-optimal solutions rapidly for those rare and complex expressions.