책 요약 – 페트리 네트 모델링 by Jorgensen

출처: Software Testing A Craftsman’s Approach, Paul C. Jorgensen, Fourth Edition, 2014년
4장 Graph Theory for Testers, 68~70페이지 

 

테스팅에 널리 사용되는 그래프 중에서 시스템 레벨 동작을 설명하는 데 적합한 페트리 네트(Petri Nets)에 대해 소개한다.

 

---

 

Petri Nets

페트리 네트는 1963년 Carl Adam Petri의 박사 학위 논문 주제였다. 오늘날 페트리 네트는 동시성(concurrency) 및 분산 처리(distributed processing) 특성을 가지는 프로토콜이나 기타 애플리케이션을 위한 모델로 사용된다.

페트리 네트는 방향 그래프의 특별한 형태인 이분 방향 그래프(bipartite directed graph)이다. 이분 그래프는 두 개의 노드 집합(즉, V1과 V2)과 하나의 에지 집합 E를 가지며, 모든 에지는 집합 V1과 V2 중 하나를 초기 노드로 나머지를 터미널 노드로 갖는다는 제약이 있다. 페트리 네트에서 두 노드 집합 중 하나는 "플레이스(Places)" 다른 하나는 "트랜지션(Transitions)"이라고 불리며, 각각 P와 T로 표시된다. P는 T의 입력 및 출력이다. 이 입력 및 출력 관계가 함수이며, 다음 정의에서와 같이 In과 Out으로 표시된다.

 

정의.

페트리 네트는 이분 방향 그래프(P, T, In, Out)이다. P와 T는 노드의 서로소 집합이고, In과 Out은 에지의 집합으로 In ⊆ P × T이고 Out ⊆ T × P이다.

 

그림 4.7의 샘플 페트리 네트에서 집합 P, T, In, Out이 각각 아래와 같다.

P = {p1, p2, p3, p4, p5}

T = {t1, t2, t3}

In = {<p1, t1>, <p5, t1>, <p5, t2>, <p2, t2>, <p3, t3>}

Out = {<t1, p3>, <t2, p4>, <t3, p4>}

그림 4.7 페트리 네트

 

페트리 네트는 유한 상태 기계(finite state machine)보다 더 흥미로운 방식으로 실행이 가능하다. 다음 몇 가지 정의는 페트리 네트 실행에 관한 것이다.

 

정의.

마킹된 페트리 네트는 5-튜플(P, T, In, Out, M)이며, 여기서 (P, T, In, Out)은 기본 페트리 네트이고 M은 플레이스에 양의 정수를 매핑한 집합이다.

 

집합 M을 페트리 네트의 마킹 집합이라고 한다. M의 엘리먼트가 n-튜플이며, n은 집합 P에 있는 플레이스의 수이다. 그림 4.7 페트리 네트의 경우, 집합 M이 <n1, n2, n3, n4, n5> 형식의 엘리먼트를 포함하며, 여기서 n은 각 플레이스와 관련된 정수로 해당 플레이스에 "들어온" 토큰의 수를 나타낸다. 토큰은 모델링 상황에 맞게 해석할 수 있는 추상적 정보이다. 예를 들어, 토큰이 특정 플레이스가 사용된 횟수를 나타내거나, 특정 플레이스에 있는 내용물 개수를 나타내거나, 또는 해당 플레이스가 참(true)인지 여부를 나타낼 수도 있다. 그림 4.8은 마킹된 페트리 네트를 보여준다.

 

그림 4.8 마킹된 페트리 네트

 

정의.

페트리 네트에서 트랜지션은 그 입력 플레이스 각각에 적어도 하나의 토큰이 있는 경우 활성화(enabled)된다.

 

그림 4.8의 마킹된 페트리 네트에서 마킹 튜플이 <1, 1, 0, 2, 0>이다. 이 페트리 네트에는 활성화된 트랜지션이 없으며, 만약 플레이스 p3에 토큰을 넣으면 트랜지션 t3이 활성화된다.

 

 

정의.

활성화된 페트리 네트 트랜지션이 발사(실행)되면 그 입력 플레이스 각각에서 토큰 하나가 제거되고 그 출력 플레이스 각각으로 토큰 하나가 추가된다.

 

그림 4.9의 경우 왼쪽 페트리 네트에서 전환 t2가 활성화되었고 오른쪽 그림에서 발사 완료되었다. 그림 4.9에서 페트리 네트의 마킹 시퀀스가 두 개의 튜플을 포함하는 데, 첫 번째는 t2가 활성화되었을 때의 페트리 네트를 보여주고, 두 번째는 t2가 발사된 후의 페트리 네트를 보여준다. 

M = {<1, 1, 0, 2, 1>, <1, 0, 0, 3, 0>}

 

그림 4.9 트랜지션 t2 발사 전과 후

 

그림 4.9를 다시 살펴보면 왼쪽 네트(트랜지션 발사 전)에서 플레이스 p1, p2, p5 위치가 모두 마킹되어 있다. 이러한 마킹으로는 t1 및 t2 트랜지션이 모두 활성화된다. 우리가 트랜지션 t2를 실행하기로 선택하면 플레이스 p5에 있는 토큰이 제거되고 t1이 더 이상 활성화되지 않는다. 마찬가지로, 만약 t1을 발사하기로 선택한다면, t2가 비활성화된다. 이 패턴은 '페트리 네트 충돌(Petri net conflict)’로 알려져 있다. 좀 더 구체적으로 트랜지션 t1과 t2가 플레이스 p5에 관하여 충돌한다고 말한다. 페트리 네트 충돌은 두 트랜지션 사이의 흥미로운 형태의 인터액션을 보여준다.

 

모델 기반 시스템 테스트 커버리지

시스템 테스터는 페트리 네트의 모든 플레이스, 모든 트랜지션, 그리고 모든 트랜지션 시퀀스를 커버하는 스레드 테스트(thread tests)를 고안할 수 있다.

페트리 네트에 전통적인 테스트 적정성 기준(test adequacy criteria)을 적용하여 firing sequences, transition sequences 같은 컨커런트 시스템을 위한 테스트 커버리지 기준을 제안한 연구도  존재한다(아래 참고 문헌). 

S. Morasca, M. Pezze, Using high-level Petri nets for testing concurrent and real-time systems, in: H. Zedan (Ed.), Real-Time Systems, Theory and Applications, North-Holland, Amsterdam, 1990. 

Hong Zhu, Xudong He, A methodology of testing high-level Petri nets, Information and Software Technology 44(2002), 473-489