Feature Interaction Verification Using Unbounded Model Checking with Interpolation

DOI HANDLE Web Site 被引用文献1件 参考文献26件 オープンアクセス
  • MATSUO Takafumi
    Graduate School of Information Science and Technology, Osaka University
  • TSUCHIYA Tatsuhiro
    Graduate School of Information Science and Technology, Osaka University
  • KIKUNO Tohru
    Graduate School of Information Science and Technology, Osaka University

この論文をさがす

抄録

In this paper, we propose an unbounded model checking method for feature interaction verification for telecommunication systems. Unbounded model checking is a SAT-based verification method and has attracted recent attention as a powerful approach. The interpolation-based approach is one of the most promising unbounded model checking methods and has been proven to be effective for hardware verification. However, the application of unbounded model checking to asynchronous systems, such as telecommunication systems, has rarely been practiced. This is because, with the conventional encoding, the behavior of an asynchronous system can only be represented as a large propositional formula, thus resulting in large computational cost. To overcome this problem we propose to use a new scheme for encoding the behavior of the system and adapt the unbounded model checking algorithm to this encoding. By exploiting the concurrency of an asynchronous system, this encoding scheme allows a very concise formula to represent system's behavior. To demonstrate the effectiveness of our approach, we conduct experiments where 21 pairs of telecommunication services are verified using several methods including ours. The results show that our approach exhibits significant speed-up over unbounded model checking using the traditional encoding.

収録刊行物

被引用文献 (1)*注記

もっと見る

参考文献 (26)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ