Feature Interaction Detection by Bounded Model Checking

Tomoyuki YOKOGAWA  Tatsuhiro TSUCHIYA  Masahide NAKAMURA  Tohru KIKUNO  

IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.12   pp.2579-2587
Publication Date: 2003/12/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Dependable Computing)
Category: Dependable Communication
bounded model checking,  SAT,  feature interaction,  

Full Text: PDF(590.3KB)>>
Buy this Article

Feature interaction is the term used in telephony systems to refer to inconsistent conflict between multiple communication services. Feature interaction is considered a major obstacle to developing reliable telephony systems and many approaches have been explored to resolve it. In this paper we present an automatic method for detecting latent feature interaction in service specifications. This method uses bounded model checking as its basis. The basic idea behind bounded model checking is to reduce the detection problem to the propositional satisfiability (SAT) decision problem. For asynchronous systems like telecommunication systems, however, traditional bounded model checking does not work well because resulting propositional formulas tend to become very large. We propose a new encoding scheme to overcome this problem and show the effectiveness through comparative experiments with traditional bounded model checking and other model checking methods.