Efficient Self-Learning Techniques for SAT-Based Test Generation

摘要

SAT-based approaches are promising for automated generation of directed tests. However, due to the state space explosion problem, these methods do not scale well for complex designs. Although various heuristics are proposed to address test generation complexity, most of them require expert knowledge regarding the detailed structure and behavior information of designs explicitly, which limits their usage. This paper proposes promising techniques to derive profitable learnings from the SAT instance itself. The obtained self-learnings can efficiently reduce the chance of long distance backtracks and improve satisfying assignment convergence rate during the SAT search. Experimental results demonstrate that our method can reduce the test generation time by several orders of magnitude.