Optimizing The Automatic Test Generation For Boolean Expressions

Software testing can help developers to discover faults in the program,which is an effective way to improve the quality of software.Its basic idea is to select a limited test case set to compose the inputs of program,and then observe the output results.With the increasing testing cost,the industry is more and more inclined to use automated testing rather than traditional manual testing.Compared with manual testing,automated testing has many advantages,such as low cost,high accuracy and high efficiency.There exist many large Boolean expressions in safety-critical system like interlocking software due to the complex control logic.So it is very important to ensure the correct-ness of Boolean expressions.Test generation for Boolean expressions has always been a hot topic in the field of testing.After years of research,there appears some classic algo-rithms such as BOR,MI and MUMCUT.However,these algorithms pay more attention to the fault-detecting ability of test cases and the reduction degree of test sets than the time complexity.In the case of small scale inputs,it is not so important.But when faced with some large-scale inputs,these classic algorithms become unable to return the results in an acceptable time,which greatly increases the testing cost.This paper mainly studies test generation algorithms for large Boolean expressions and focuses on optimizing the time complexity.Our purpose is to reduce the time cost as much as possible under the condition of ensuring a high fault-detecting ability.Our contributions are as follow:1.Transform Meaningful Impact into a SAT problem and design a test generation algo-rithm based on DPLL,which improves the performance of original MI and enables it to handle large DNF more efficiently.2.Take mutation testing as evaluation function and design a test generation algorithm based on genetic algorithm.It does not depend on input format,so it can deal with the test generation task of general expressions more efficiently.3.Design an interlocking rule based test generation solution which transforms the in-terlocking Boolean into general Boolean by instantiation and cycle unrolling.And then take switch control as an example to illustrate the whole solution.