페트리 네트를 이용한 시스템 속성의 명세 및 분석 = Specification and Analysis of System Properties by using Petri nets

국문 초록 (Abstract)

소프트웨어 시스템 모델링에서는 정형적 기법으로 소프트웨어를 모델링하고 분석하여 소프트웨어 시스템이 가지는 문제점들을 구현에 앞서 미리 찾아 해결하고자 한다. 페트리 네트는 그래픽 정형 명세 언어로 병행적 시스템, 실시간 시스템, 통신 프로토콜 등의 소프트웨어 시스템 모델링 및 분석에 널리 이용되고 있다. 페트리 네트 분석에서, 교착상태(deadlock), 수행가능성(liveness) 등의 일반적인 시스템 특성 분석은 주로 도달성 분석을 통해 이루어지며 시스템 요구사항에 관한 고유 특성 분석은 모델 검사(model checking) 방법을 통해 이루어진다 하지만 도달성 분석과 모델 검사 방법에서는 기본적으로 시스템의 모든 가능한 상태들을 나열하여 분석하므로 모델의 규모가 커짐에 따라 상태가 기하급수적으로 증가하는 상태 폭발(state explosion) 문제가 발생한다. 이 논문에서는 상태 폭발을 회피하면서 시스템의 요구사항을 체계적으로 분석할 수 있는 새로운 방법을 제안하고자 한다. 먼저 분석하고자 하는 요구사항을 속성 네트로 나타낸 후, 시스템 모델과 속성 네트를 합성하여 분석한다. 이러한 합성 분석에서는 분석 대상 속성과 연관되지 않는 모델의 부분들을 축약 규칙에 따라 축약함으로써 분석 도메인을 점진적으로 줄어 나갈 수 있으며 요구사항 만족 여부를 간단히 검사할 수 있는 장점이 있다.

다국어 초록 (Multilingual Abstract)

Software system modeling has a goal for finding and solving system's problems by describing and analyzing system model in formal notations. Petri nets, as graphical formalism, have been used in describing and analyzing the software systems such as parallel systems, real-time system, and protocols. In the analysis of Petri nets, general system properties such as deadlock and liveness are analyzed by the reachability analysis. On the other side, specific properties such as functional requirements and constraints are checked by model-checking. However, since these analysis methods are based on enumeration of ail possible states, there nay be state explosion problem, which means that system states exponentially increase as the size of system is larger. In this paper, we propose a new method for mechanically checking system properties with avoiding state explosion problem. At first, system properties are described in property nets then the system model and the property net are composed and analyzed. In the compositional analysis, system parts irrelevant to the specific property are reduced to minimize the analysis domain of the system. And it is possible to mechanically check whether a specific property is satisfied or not.

참고문헌 (Reference)

1 J. B. Jorgensen, "Verification of Coloured Petri Nets Using State Spaces with Equivalence Classes" 1997.

2 Dirk O. Keck, "The Feature and Service Interaction Problem in Telecommunications Systems：A Survey" 24 (24): 1998-,

3 T. Murata, "Proceedings of The IEEE" 77 (77): 1989.

4 H. J. Genrich, "Petri Nets：Applications and Relationships to other Models of Concurrency" Springer- Verlag 207-247, 1987.

5 Wolfgang Reisig, "Petri Nets：An Introduction" 1985.

6 W. J. Lee, "Integration and Analysis of Use Cases Using Modular Petri Nets in Requirements Engineering" 24 (24): 1115-1130, 1998.

7 "ITU-TITU-T Intelligent Network CS-2 Recommendations Q.1220-Q.1225" 1997.

8 Wei Jen Yeh, "Controlling State Explosion in Reachability Analysis" purdue university 1993.

9 G. Bucci, "Compositional Validation of Time- Critical Systems Using Communicating Time Petri Nets" 21 (21): 969-992, 1995.

10 K. Jensen, "Coloured Petri Nets：Basic Concepts^Analysis methods^Practical Use" Springer-Verlag 1 : 1992.

11 S. C. Cheung, "Checking Subsystem Safety Properties in Compositional Reachability Analysis" 144-154, 1996.

12 E. M. Clarke,E. A. Emerson, "Automatic Verification of Finite-State Concurrent Systems using Temporal Logic Specifications" no.2 : 244-263, 1896.

13 C. Ghezzi,D. Mandrioli,S. Modasca, "A Unified High-Level Petri Net Formalism for Timed-Critical Systems" 17 (17): 160-172, 1991.

14 T. Suzuki, "A Protocol Modeling and Verification Approach Based on a Specification Language and Petri Nets" 16 (16): 523-536, 1990.