Development on ATM Conformance Tester

!4- 적합성 시험 생성기 개발

$EVELOPMENT ON !4- #ONFORMANCE 4ESTER

민재홍*( -IN 기술기준연구팀 책임연구원 이부호"( ,EE 표준시험연구팀 선임연구원

!4-프로토콜 적합성 시험 생성 도구 개발을 프로토콜 개발 통합환경과 연계하여 개발한다즉 생성된 )/ &3-중간모델을 대상으로 연구된 가장 짧은 길이의 시험 스위트TEST SUITE 를 생성하는 알고리즘을 편리하고 용이하게 적용하기 위해 데이터 구조화 및 컴퓨터 내에서의 표현 등을 위한 초기화 작업기능을 3$, %DITOR  3IMULATOR를 활용하여 확인한다그리고 !43!BSTRACT 4EST 3UITE 생성은 5)/시퀀스를 결정 하고 454와 도착상태의 5)/시퀀스를 결합한 시험 SUBSEQUENCE생성과 SYMMETRIC ARGUMENTATION과정을 거처 2#02URAL #HINESE 0OSTMAN 4OUR생성 알고리즘 구현을 통해 완전 시험 스위트 생성도구를 개발하 고프로토콜 검정기와 연계하여 통합된 환경에서 사용할 수 있도록 개발한다

)

프로토콜 적합성 시험은 프로토콜의 구현물)

)MPLEMENTATION 이 원래 명세3 3PECI`CATION 에 합당하게 구현되었는지를 시험하는 것으로 통 신프로토콜 제품 구현 과정에서 중요한 역할을 한다 일반적으로 적합성 시험의 정의는 주어 진 명세 3를 기초로 하여 생성된 시험 계열TEST CASE 로서 구현물 )가 명세 3에 대해 프로토콜 행 위BEHAVIOR 와 능력CAPACITY 이 일치하는지를 시 험하는 것이다

적합성 시험의 국제적인 호환성을 보장하기 위 해 )3/와 )45에서 공동 프로젝트로 적합성 시험 과정 자체의 표준화를 추진해 왔는데 이러한 노 력의 결실이 )3)3/ 표준 또는 8)45 시리즈 표준으로 <적합성 시험 방법론 및 프레

임워크#4-& #ONFORMANCE 4ESTING -ETHODOLOGY AND &RAMEWORK 로 제작되었다 #4-& 방법은 자 연어로 서술된 표준으로부터 구현의 표준에 대한 적합성을 시험하는 전반적인 절차인데 자연어영 어 로 서술된 프로토콜 국제 표준들은 자연어로 서술된 명세 자체가 구현자의 해석방법 여부에 따 라 다르게 구현될 수 있고 또 자연어로 된 명세 로부터 시험 계열 생성은 수작업적인 성격이어서 컴퓨터를 이용한 생성과정의 자동화가 어려워 복 잡한 프로토콜의 경우 효과적인 적합성 시험을 위 한 계열 생성에 많은 어려움을 겪어왔다

이러한 문제점들은 형식기술방법&$4 &OR MAL $ESCRIPTION 4ECHNIQUES 에 의한 규격명세기술 에 의하여 극복될 수 있다 이 접근방법으로 형식 언어의 사용을 통하여 규격기술의 정확성을 기할



!4- 적합성 시험 생성기 개발

수 있고 또 형식기술방법에 의해 명세화된 규격 으로부터 최적의 시험 스위트 생성과 시험과정의 컴퓨터를 이용한 자동화를 통하여 시험시간과 비 용을 감소시킬 수 있다

본 고에서는 프로토콜 개발 도구 통합환경 구 현을 위해 한국전자통신연구원 표준연구센터에 서 개발한 적합성 시험 생성기를 동일환경 하 에 구성할 목적으로 상용 3$,3PECI`CATION AND

$ESCRIPTION ,ANGUAGE %DITOR  3IMULATOR )NTER FACE를 고려하여 기술한다 이를 위해 우선 최적 의 적합성 시험 스위트 생성을 위한 프레임워 크FRAMEWORK 를 제시하고 이러한 프레임워크에 기초한 적합성 관계도 정의한다 마지막으로 정의 된 적합성 관계에 대한 시험 스위트 생성 알고리 즘 개발을 위한 전체적인 PILOT 시스템의 구성 및 기능에 대해서도 기술한다

))

)/ &3-&INITE 3TATE -ACHINE 으로 표현된 명세에 대한 프로토콜 적합성 시험을 위한 접 근 방법은 명세에 정의된 )/ &3-의 각 천 이TRANSITION 에 대하여 구현의 천이 동작을 확 인하는 방법인데 이 방법을 경험적 확인 방 법CHECKING EXPERIMENT METHOD 이라 한다 이 방 법은 각 스테이트STATE 에서 각각의 시험 대상 천 이에 대한 INPUT과 이 INPUT에 대한 OUTPUT이 구현 에서도 올바르게 이루어졌는지를 확인하고 구현 에서 결과적으로 도착한 스테이트에 대해서도 검 정하는 과정으로 구성된다 즉 이러한 각 천이를

시험하기 위한 시험 계열은 INPUTOUTPUT 시퀀스 로 이루어진다

현재까지 경험적 확인 방법에 근거하여 여러 종류의 시험 계열 생성방법이 연구되어져 왔는데 시험대상 천이에 대한 시험 후 구현의 결과 스테 이트 확인 방법에 따라 5)/5NIQUE )NPUT /UT PUT 방법 $3$ISTINGUISHING 3EQUENCE 방법 그리 고 #3#HARACTERIZATION 3ET 방법 등으로 나뉘어 진다 이러한 방법들은 명세의 각 스테이트에서 시험대상 천이 <INPUTOUTPUT 시퀀스에 이 시퀀 스에 의해 도착한 스테이트의 유일한 )/ 시퀀스 를 연계CONCATENATION 하여 시험하므로 구현에서 도착 스테이트를 검정하는 방법이다

이러한 방법들을 자세히 살펴보면 )/ &3-으 로 표현된 프로토콜 명세 3와 구현 )가 STRONGLY CONNECTED 이고 DETERMINISTIC하며 MINIMAL이고 또 구현 )의 스테이트 수가 명세 3의 그것과 일치하 는 상태에서 트레이스 동치TRACE EQUIVALENCE 또 는 관찰 동치OBSERVATIONAL EQUIVALENCE 관계로 요 약된다

일반적으로 BLACK BOX로 취급되는 구현 내에서 출력 오류 및 천이 오류를 검출하는 목적의 적합 성 시험 문제는 위와 같은 제한된 프레임워크 내 에서 취급되지 않으면 해결 가능치 않는 문제가 된다

시스템 또는 통신 프로토콜에 해당하는 명세 )/ &3-과 구현에 해당하는 )/ &3-에 있어서 BLACK BOX로 고려되는 구현 )/ &3-이 명세 )/

&3-에 일치하는지를 결정하기 위해 사용되는 시 험 스위트 생성을 위한 프레임워크는 다음과 같 다



전 전 전

전자자자통자통통통신신신동신동동동향향향향분분분분석석석석 제권 제호 년 월

 먼저 )/ &3- 3와 )/ &3- ) 사이에 적합성 관계 정의

 )/ &3- 3로부터 시험 계열 입력 부분 43I와 기대되어지는 시험 계열 출력 부분 43O를 생성

 43_I를 BLACK BOX로 취급되는 )/ &3- )의 입력 부분PORT 에 적용

 )/ &3- )의 출력 부분에서 실제 출력 부분 43A를 관찰

 )/ &3- 3와 )/ &3- )의 적합성을 결정하기 위하여 43_O와 43_A비교

출력 오류와 천이 오류를 걸러내기 위한  에 서  의 적합성 시험단계에서 일반적으로 두 가 지 문제가 야기된다 단계 에서 일반적으로 구현 )/ &3-을 원하는 스테이트로 위치시킬 수 없다 는 것이고 두번째로 단계 에서 시험 계열의 <IN PUT을 적용한 후에 원하는 <OUTPUT을 구현 )/

&3-으로부터 얻은 경우라도 구현 )/ &3-이 해 당 스테이트에 위치하였는지 알 수 없다는 것이다

첫번째 문제를 관리한계CONTROLLABILITY LIMIT 라 하 고 두번째 문제를 관찰한계OBSERVABILITY LIMIT 라 한다

일반적으로 CONTROLLABILITY LIMIT 문제를 해결하 기 위해서 초기 상태 3_O로부터 시작하여 원하는 스테이트까지 가장 짧은 패스SHORTEST PATH 를 이 용하여 스테이트에 도착한 후 해당 천이를 시험 하게 되고 OBSERVABILITY LIMIT 문제를 해결하기 위 해 시험하는 천이 후에 도착한 스테이트의 유일한 INPUTOUTPUT 시퀀스를 시험 계열에 포함시켜 적 용한 후 구현 )/ &3-의 결과 스테이트를 확인하 는 방법을 사용한다 이러한 유일한 INPUTOUTPUT 시퀀스로 5)/ 시퀀스 $3 시퀀스 #3 시퀀스 등 을 사용한다

본 연구에서는 5)/ 시퀀스를 사용하여 OBSERV ABILITY LIMIT 문제를 해결한다 왜냐하면 $3 시퀀 스나 #3 시퀀스 등은 존재를 위한 기본 조건이 모 델 )/ &3- 자체가 완전하게 명세화되어야 하나 5)/ 시퀀스는 이러한 요구조건이 없으며 또 일반 적으로 통신 프로토콜을 모델링하는 )/ &3-은 부분적으로 명세화 되어 있기 때문이다 또 $3 시 퀀스나 #3 시퀀스는 찾기가 어렵고 존재 여부도 일반적으로 판단하기에 매우 어렵다 다른 한편으 로는5)/ 시퀀스는 대부분의 )/ &3-이 모든 스 테이트들에 대해 존재하며 길이도 $3 시퀀스나

#3 시퀀스에 비해 짧기 때문에 결과적으로 짧은 시험 스위트 생성을 보장한다

위의 프레임워크의  과  를 해결하기 위해 필요한 가정들은 다음과 같다

{ )/ &3- 3는 결정적DETERMINISTIC 이고 강하게 연결된STRONGLY CONNECTED 모든 스테이트들은 5)/ 시퀀스를 가져야 한다

{ )/ &3- )는 DETERMINISTIC하고 MINIMAL하다

{ 또 구현 )/ &3-과 명세 )/ &3-의 스테이트 수가 같다

{ 마지막으로 명세 )/ &3- 모든 입력 심볼들은 구현 )/ &3-의 입력 집합SET 에 포함되어야 한다

)))

적합성 관계로서명세 )/ &3-과 구현 )/

&3- 사이에 구성CONF 을 다음과 같이 정의한다

{ 정의 입력 시퀀스 집합에 대한 스테이트 동치



!4- 적합성 시험 생성기 개발

)I를 구현 )/ &3-의 한 스테이트라 하고 3J를 명세 ) / &3-의 하나의 스테이트라고 할 경 우 6d y3_J 즉 입력 시퀀스의 집합이라 하면

)_Ii V3J IF g₎)_I P  g₃3_J P  FOR P  6

여기서 g는 )/ &3-의 출력 기능OUTPUT FUNC TION 이다

{ 정의 구성

구현 )/ &3- 구성 명세 )/ &3- I_

)i y3 3

여기서 )_그리고 3_은 두 )/ &3-의 초기 스테 이트이다

위의 정의는 두 결정형 )/ &3-의 N OBSER VABLE한 트레이스 동치 또는 관찰 동치에 해당 한다

{ 정의 시험 계열 4EST CASE

시험 계열은 입력들의 한정된 길이의 y3_ 에 속하는 시퀀스이다

{ 정의 시험 스위트 4EST SUITE

시험 계열들의 집합을 시험 스위트라 한다

{ 정의 0ASS OF A TEST SUITE

43를 시험 스위트라 하면 주어진 구현 )/

&3-) 는 시험 스위트를 패스한다고 이야기하 면서 다음과 같이 표기한다

)/ &3-) PASS 43 I_ g)) P

 g33 P FOR  P  43

{ 정의 완전 시험 스위트 #OMPLETE TEST SUITE 주어진 시험 스위트 43와 명세 )/ &3-3 에 있어서 모든 구현 )/ &3-) 가 다음 조건을

만족할 때 43는 )/ &3-3 에 대한 구성 관계 에 있어서 완전한 시험 스위트라 한다

)/ &3-) CONF )/ &3-3 I_ &3-)PASS 43

그러면 )6장에서는 위에 언급된 적합성 관계 에 대한 완전 시험 스위트 43를 자동 생성하는 시 스템 구현에 대해서 살펴보자

)6

 전체 시스템 구성

적합성 시험 생성기에서는 프로토콜을 3$,로 명세한 후 3$, %DITOR  3IMULATOR 도구를 사용하 여 시뮬레이션 과정을 통하여 생성된 파일을 입력 으로 한다 )/ &3- 생성에서는 입력으로 주어지 는 시뮬레이션 파일을 !43 생성을 위한 중간 모 델인 )/ &3-으로 변환한다 검정에서는 중간 모 델인 )/ &3- 3가 강하게 연결되고 DETERMINIST한 지를 검정한다

!43 생성에서는 블랙박스 검사에서의 OB SERVABILITY LIMIT 문제를 해결하기 위한 가장 짧 은 5)/ 시퀀스를 결정하고 4544RANSITION 5N DER 4EST 와 도착상태의 5)/ 시퀀스를 결합한 시 험 렬SUBSEQUENCE 를 생성하고 생성된 모든 시 험 SUBSEQUENCE를 대칭적으로 구성한 대칭그래 프SYMMETRIC GRAPH 를 생성한 후 2#0 TOUR 계 산을 통한 EULER TOUR GRAPH를 생성한다

5)/ 시퀀스를 사용하여 )/ &3- 모델로부터 의 시험 계열 자동 생성을 위한 여러 가지 방법 들이 제안되었다 이중 5)/ 방법과 5)/_V방법은 )54에서 신뢰성 있는 재설정을 가정한 다중 시험



전 전 전

전자자자통자통통통신신신동신동동동향향향향분분분분석석석석 제권 제호 년 월

그림  완전 시험 스위트 생성과정

접근에 속한다 5)/ 방법이  완전 오류영역 을 파악하지 못하는데 비해 5)/_V방법은 완전 오 류영역을 파악한다

본 시스템에서 구현한 방법은 최적화 기술을 사용한 단일 시험 접근으로서 위의 방법들에 비 해 )54에 의해 제공되어져야 하는 재설정 기능을 요구하지 않는 기술이다 이 방법의 주된 내용은 구현 )/ &3- 내에 명세 )/ &3-에 명세화된 각 천이가 존재하는 지를 검사하기 위해 명세 )/

&3-으로부터 단일 시험 계열을 생성하는 방법이 다 이 방법에 기초한 기본 개념은 다음과 같다

 명세 )/ &3- 내에서 명세화된 각 천이를 위해 시험 SUBSEQUENCE를 생성하는데 각 시험 SUB SEQUENCE들은 454의 입력 심볼과 이 천이에 의해 도착한 스테이트의 5)/ 시퀀스의 연계로 구성된다

  에서 구성된 모든 시험 SUBSEQUENCE들을 적 어도 한 번 탐색하는 단일 최적SINGLE OPTIMAL



I/O FSM 생성

시뮬레이션 파일 I/O FSM

Strongly Connected Check

Determinist Check

UIO 생성

시험 Subsequence 생성

Symmetric Augmentation

RCP Tour 생성 UIO Table

Symmetric Graph

Test Subsequence

Euler Tour Graph ATS

생성 검정

시작

종료 TTCN 변환 TTCN.MP

!4- 적합성 시험 생성기 개발

시험 계열을 2URAL #HINESE 0OSTMAN2#0 TOUR 개념을 사용하여 생성한다

44#.4REE AND 4ABULAR #OMBINED .OTATION 변환에서는 위의 단계에서 생성된 EULER TOUR GRAPH가 !43에 해당하므로 이 !43를 표준화된 시험 스위트 표기법인 44#.으로 변환한다

위의 기본 개념을 사용하여 3$, 형태로 나타 내어진 !4- 프로토콜 명세로부터 완전 시험 스위 트 43를 생성하는 전체시스템 구성은 그림  과 같다

 단계별 상세 기능

가 )/ &3- 생성

!4- 프로토콜 명세로부터 )/ &3- 생성은 상용화된 3$, %DITOR  3IMULATOR를 사용하여 생 성하는데 이 도구의 기능 중 3$, 명세로부터 시뮬레이션 과정을 거쳐 생성된 파일로부터 )/

&3- 중간 모델을 생성한다 다음 그림  는 중간 모델 생성과정을 나타낸다

그림  )/ &3-생성과정

{ 초기 )/ &3- 생성

시뮬레이션 파일로부터 상태 이벤트)NPUT

/UTPUT  도달 상태 의 형태를 취하는 초기 )/

&3-을 생성한다 이때 시뮬레이션 파일에서 처 음 도출되는 상태를 초기 상태 로 한다

{ 최소화-INIMIZATION

초기 )/ &3-에서 중복되는 천이를 제거하여 최소 천이 )/ &3-을 생성한다 생성된 )/

&3- 파일은 !43 생성의 입력으로 사용된다

)/ &3- 내의 상태는  q q q N인 상태번호로 표 시되고 각각의 상태번호와 해당하는 상태명을 참조할 수 있는 테이블이 생성된다

나 3TRONGLY #ONNECTED 검정

)/ &3-혹은 방향화된 그래프 의 어떤 스테 이트또는 그래프의 노드 에서도 어떠한 다른 스 테이트또는 그래프의 노드 로도 패스PATH 가 존 재할 때 강한 연결 특성을 가졌다고 하며 이 특 성은 주어진 프로토콜 명세)/ &3- 혹은 그래 프 가 DEADLOCK이나 LIVELOCK 성질이 없음을 의미 한다

)/ &3- -의 강한 연결 상태를 확인하 기 위해 그래프 재표기 시스템을 적용한다 그 래프 재표기 시스템에 의한 강하게 연결된 요 소COMPONENT 를 찾는 알고리즘은 고전적인 그 래프 이론에 의거한 강하게 연결된 요소를 찾 는 알고리즘에 비해 더욱 효과적이다 왜냐하 면 고전적인 STRONGLY CONNECTED COMPONENT 계 산 알고리즘은 /-AXN E 여기서 N은 노드 의 수이고 E는 아크의 수 의 시간을 요구하는 반면 그래프 재표기 알고리즘은 /Np 를 요구한다 일반적인 모든 프로토콜을 명세한 그래프혹은 )/ &3- 는 E의 수가 N의 수 보다 훨씬 크기 때문에 더욱 효과적이다 그림

 은 그래프 재표기 알고리즘을 이용한 STRONGLY CONNECTED 검정과정을 설명한다



시뮬레이션 파일

I/O FSM 초기 I/O FSM

생성

최소화 시작

참조표상태 종료

전 전 전

전자자자통자통통통신신신동신동동동향향향향분분분분석석석석 제권 제호 년 월

{ '23'RAPH 2EWRITING 3YSTEM )NITIALIZE )/ &3-을 입력받아 초기상태는2ED"LUE 로 그 외의 상태는 'REEN'REEN 으로 레이블을 설 정한다

{ '23

초기화된 )/ &3-에서 그래프 재표기법을 사 용하여 )/ &3-의 상태 레이블을 천이에 따라 갱신하다

{ 3TRONGLY #ONNECTED #HECK

)/ &3-의 상태 중에서 레이블이 2ED"LUE 로 갱신되어 있지 않는 상태가 존재하는지를 검사 한다 만약 어떤 상태의 레이블이 2ED"LUE 로 설정되어 있지 않다면 이 상태는 초기상태와 강 한 연결STRONGLY CONNECTED 관계가 성립하지 않 으므로 DEADLOCK 또는 LIVELOCK이 걸린 상태이다

그림  3TRONGLY #ONNECTED검정과정

다 결정성 검정$ETERMINIST CHECK

)/ &3-을 입력으로 하여 어떤 상태에서 같 은 이벤트)NPUT/UTPUT 에 의한 다른 천이가 존 재하는지를 검사한다 검정과정은 적합성 시험 스

위트 생성을 위하여 반드시 선행되어야 하는 과정 으로써 STRONGLY CONNECTED 특성과 결정성 특성이 만족하여야 !43 생성 단계로 넘어간다

라 5)/ 생성

본 시스템에서는 블랙박스 검사에서 OBSERV ABILITY LIMIT 문제를 해결하기 위해서 5)/ 시퀀스 를 사용한다 5)/ 시퀀스는 주어진 )/ &3-의 스 테이트 3_I를 위해 5)/3_I 로 표기하는 데 즉 3I 스 테이트를 위해 명세화된 유일한 INPUTOUTPUT 시 퀀스 5)/3I IO IO qrqrqrIPOP 로 나타 내어진다

다음은 주어진 )/ &3-의 모든 스테이트들을 위해

 길이 @의 모든 천이가 어느 스테이트 3_I에만 홀 로 존재하는지 검사초기에는 @   

 만약 스텝 @에서 길이 @의 5)/와 3I를 위해 존 재하지 않으며 모든 천이에 대해 검사한 후 길 이 @  로써 반복한다

 주어진 )/ &3-의 다른 모든 스테이트에 대 해서  과  를 반복한다

그림  는 위의 과정에 대한 흐름을 나타낸다

{ 5)/ 초기화

)/ &3-의 상태 수만큼의 배열을 가지는 5)/

표TABLE 를 생성하고 처음에 길이 @의 값을

최소 경로 로 설정하고 5)/를 구한다

{ 길이 @인 5)/ 검색

어떤 상태 3에서 유일하게 존재하는 길이 @인 천이순서 TS를 검색한다 만약 길이 @인 5)/가 존재하면 5)/ 표의 해당 상태의 5)/ 항목에 TS를 삽입하고 존재하지 않으면 @  로써 길 이PATH 를 증가시켜 반복 수행한다 둘 이상 존



I/O FSM GRS Initialize

Strongly Connected Check 시작

종료 GRS

!4- 적합성 시험 생성기 개발

그림  5)/생성과정

재하는 5)/에 대해서는 마지막에 검색된 천이 순서를 삽입한다

{ 5)/ 표 생성

생성된 5)/ 표를 파일로 출력한다 이 때 각 상 태의 5)/는 최소 경로의 5)/ 시퀀스이며 각 상 태마다 유일하게 하나씩 존재한다

마 시험 3UBSEQUENCE 생성

위의 소절에서 구해진 모든 스테이트들의 가 장 짧은 길이의 5)/ 시퀀스를 결정한 후 주어진 )/ &3- 내의 모든 천이에 대해 )/ &3-과 5)/

표를 입력으로 하여 )/ &3- 내의 모든 천이에 대 해서 시험 대상 천이인 454에 도착상태의 5)/ 시 퀀스를 더한 시험 SUBSEQUENCE를 생성한다 즉 다 음과 같은 형태를 지닌 시험 SUBSEQUENCE를 생성 한다

433IJ 42IJ 5)/3J

여기서 4SS_IJ는 시험 SUBSEQUENCE 4R_IJ는 상태 I에 서 상태 J로 가는 천이 는 연결자 심볼 그리고 5)/3_J 는 42_IJ에 의해 도착하는 상태 J의 5)/ 시 퀀스를 나타낸다

모든 구해진 시험 SUBSEQUENCE를 원래의 )/

&3-에 새로 첨가하면 새로운 그래프 '^6^

%^ 가 생성되는데 '^는 다음과 같다

'^ 6^ %^  6^ 6와 %^ % ;%%C

여기서 %C FVI V_K E_Lr5)/VJ  VI VJ >)%

그리고 TAIL5)/V_J V_K G

위의 식에서 TAIL5)/V_J 는 5)/VJ 의 수행 후 에 도착한 스테이트이고 %_C는 시험 SUBSEQUENCE 4_33IJ 42_IJ 5)/3_J 를 나타낸다 그림  는 시험 SUBSEQUENCE 생성과정을 나타낸다

그림  시험 3UBSEQUENCE생성과정

바 3YMMETRIC !UGMENTATION

위에서 구한 모든 시험 SUBSEQUENCE를 한 번 포 함하는 %ULER 4OUR를 계산하는데 있어 '^를 SYM METRIC하게 하기 위해서는 4SS를 중심으로 <aOW MAXIMUM COST MINIMUM 개념으로 4SS는 한 번 포함하고 원래 기존의 천이 4R을 부분적으로 포 함하여 새로운 형태의 SYMMETRIC한 그래프 '를 구해야 하는데SYMMETRIC AUGMENTATION  이 그래 프 '에서 %ULER 4OUR를 구하는 문제가 2URAL #HI NESE 0OSTMAN 0ROBLEM 해결 문제로 압축된다



I/O FSM

UIO 표 UIO 초기화

UIO표 생성 시작

종료 길이 l인 UIO 검색

길이1 증가

Yes

No

시작

Test Subsequence

Graph 시험 Subsequence

Graph 생성 I/O FSM

UIO 표

시험Subsequence 생성

종료

전 전 전

전자자자통자통통통신신신동신동동동향향향향분분분분석석석석 제권 제호 년 월

그림  3YMMETRIC !UGMENTATION과정

새롭게 얻어진 그래프 '^6^ %^ 에서 초기 스테이트에서 출발하여 모든 4_33IJ들을 한 번 포함 하고 다시 초기 스테이트로 돌아오는 TOUR가 최적 의 완전 시험 스위트에 해당한다 이러한 TOUR를

%ULER TOUR라고 하는데 %ULER TOUR가 존재하는 조 건은 얻어진 그래프 '^6^ %^ 가 SYMMETRIC해야 한다 즉 모든 정점에 들어오는 입력수와 나가는

입력수가 같아야 한다는 것이다 이러한 과정이 SYMMETRIC AUGMENTATION 과정이다 그림  은 이 러한 과정을 나타낸다

사 2#0 4OUR 생성

3YMMETRIC AUGMENTATION 과정을 통해 생성된 '를 입력으로 하여 각각의 천이를 모두 한 번씩



I/O FSM 입력

I/O FSM i := 0

시작

i < nbState Yes 입력 Tss(i)와 출력 Tss(i) 개수 측정

index의 값은?

index = 0

index > 0 index < 0

index[i] ⇒ S

Symmetric Graph G* 생성 1

Symmetric Graph

1

종료

Index[i] = Tssin(i) – Tssin(i)

index[i] ⇒ S index[i] ⇒ M index[i] ⇒ T

M에 있는 Tr을 사용하여 S와 T 사이의 cost를 0으로 구성

!4- 적합성 시험 생성기 개발

그림  2#0 4OUR생성과정

거치는 %ULER 4OUR 'RAPH를 생성한다 이렇게 생 성된 그래프가 최적의 완전 시험 스위트에 해당한 다

{ 초기화

3YMMETRIC GRAPH '의 상태 개수만큼의 벡터

VECTOR 를 생성하고 PTR을 초기 상태로 설정한 다

{ 2#0 4OUR

시작 상태에서부터 각각의 천이를 모두 한 번씩

거치는 2#0 TOUR를 계산한다2#0 TOUR 알고리 즘 참조 그림  

{ %ULER 4OUR 'RAPH 생성

2#0 TOUR로부터 최적의 완전 시험 스위트를 생 성한다

아44#. 변환

)3 의 0ART에서는 추상시험스위트!43 의 명세를 표준화된 방법을 기술하는 44#.에 대



Symmetric Graph G*

시작

No

Yes

Yes No

Euler Tour Graph

초기화

RCP Tour

Euler Tour Graph 생성

벡터[nbState] 생성

Ptr := 0

State[ptr]에서 입력 Tssij = 탐색

탐색되지 않은 Tss_ij?

벡터[i] += ptr

탐색되지 않은 state[i]의 Tss?

Ptr = i Euler Tour Graph 생성

(최적의 완전 시험 스위트) 초기 상태에서 벡터의 마지막 요소로부터 검색

종료

전 전 전

전자자자통자통통통신신신동신동동동향향향향분분분분석석석석 제권 제호 년 월

해 기술되어 있다 /3)/PEN 3YSTEM )NTERCONNEC TION 에 기초를 둔 표준의 모든 시험 스위트들의 개발은 이 표준화된 표기법을 사용한다

그림  44#.변환 과정

본 시스템에서 최적화 기술로 생성한 시험 스 위트는 다음과 같은 모델로 나타낼 수 있다

<A_B_q INPUT_OUTPUT_q 5)/_q A_B_q INPUT_ OUTPUT_q 5)/_

이 모델에서는 두 개의 시험의 경우 즉 A_B_q INPUT_OUTPUT_q 5)/_과 A_B_q INPUT_OUTPUT_q 5)/로 나눌 수 있으며 INPUT_OUTPUT INPUT OUTPUT는 앞에서 언급한 454로서 4EST BODY이 며 는 연계 심볼이고 5)/_ 5)/_는 INPUT_

OUTPUT_ INPUT_OUTPUT_에 의해 도착한 상태의 5)/ 시퀀스를 나타내며 POSTAMBLE로 취급된다

AB과 A_B는 454가 아닌 기존의 천이 중 2#0 TOUR에서 최적 시험 계열 생성을 위해 반복적으 로 사용되어진 천이이며 초기치PREAMBLE 로 취 급되어 진다 변환된 44#.은 시험 케이스 동 적 행위표4EST #ASE $YNAMIC "EHAVIOR TABLE 와 PREAMBLE 또는 POSTAMBLE을 나타내는 시험 단계 동적 행위표4EST 3TEP $YNAMIC "EHAVIOR TABLE 들 로 구성되어진다그림  

6

초고속정보통신망 구축을 위한 광대역 종합 정 보 통신망" )3$. 구현을 위해 국내외적으로 많 은 연구가 이루어지고 있다 !4- 기술 및 서비 스 전개에 있어 성공의 핵심 사항은 표준화와 여 러 구현 제품간의 상호운용성을 보장하는 것이라 고 할 수 있는데 실제로 여러 이기종 제품간의 상 호운용성을 보장하기 위해서는 시스템이 지원하 는 모든 인터페이스에 대해 적합성 시험 및 개발 과정에서의 명세에 대한 체계적인 검정이 수행되 어야 한다

최근 정보통신관련 37들은 인터넷의 보급에 힘입어 정보의 공유 전자상거래 인트라넷 형성 등 그 규모나 성능면에서 기능의 복잡성 및 다양 화에 따른 종류의 시스템 및 소프트웨어를 요구 하고 있다 그러나 이용 환경 및 요구 변화가 어떤 형태로 달라지던지 관계없이 사용자와 개발자 그 사이에 존재하는 시스템의 관계는 전통적인 소프 트웨어 개발방법론에서 생겨나는 문제들 예를 들 어 사용자의 요구조건을 충분히 이해하고 표현하 지 못함으로써 신뢰성 있는 통신 프로토콜 소프트 웨어 개발에 대한 구체적인 방안을 제시하지 못하 는 단점이 있다

정형기법은 위와 같은 비정형적인 사용자 요 구사항으로부터 정형적인 사용자 요구사항을 유 도하여 이를 통한 명세의 무결성 및 완전성을 검 정하여 신뢰성 있는 통신 프로토콜 소프트웨어를 개발하는 방법으로 나아가서는 이를 통해 목적코 드의 상당 부분을 자동 생성시킴으로써 코딩노력 을 절감시킬 뿐 아니라 신뢰성 있는 소프트웨어를 생산할 수 있는 기반을 제공한다



시작

TTCN.MP 생성 TTCN 초기화

TTCN.MP Label 생성 및

저장 Symmetric

Graph UIO 표 I/O FSM

종료

!4- 적합성 시험 생성기 개발

!4- 프로토콜 적합성 시험도구에 대한 통합 환경하에 구성하기 위한 기능을 확인 q 연구한다

즉 생성된 )/ &3- 중간모델을 대상으로 연구된 가장 짧은 길이의 시험 스위트를 생성하는 알고 리즘을 편리하고 용이하게 적용하기 위해 데이터 구조화 및 컴퓨터 내에서의 표현 등을 위한 초기 화 작업기능을 확인하고 5)/ 시퀀스 생성 및 시 험 SUBSEQUENCE 생성과 대칭 검증SYMMETRIC ARGU MENTATION 과정을 거처 2#0 TOUR 생성 알고리즘 구현을 통해 기 개발된 완전 시험 스위트 생성도 구의 기능을 시험한다

또한 개발된 3$, 검정기와 적합성 시험 생성 기를 /BJECT 'EODE %DITER 기능에 관계된 도구들 과 통합하여 사용자들이 쉽고 편하게 쓸 수 있도 록 환경구현 및 통합 모듈을 구현한다

본 연구 결과로 얻어질 프로토콜 개발 통합환 경은 본 과제에서 추진중인 !4- 적합성 시험기 술 연구의 일부로 활용이 가능하며 향후 (!."

)3$.의 개발품에 대한 적합성상호운용성 시험 서비스의 제공에 활용될 기반기술 연구로 활용이 기대된다 또 세기 정보화 사회를 위한 핵심 기 술인 !4-" )3$. 0#3 ). 등 국책과제로 수행 되는 각종 프로토콜 개발과정에서 프로토콜 개발 통합환경으로 활용될 수 있다

참 고 문 헌

;= 진병문 외 인 정보통신 프로토콜 공학 한국전자통신연 구원 

;= 박용범 김태균 김성운 <,43 명세 검증을 위한 모델 검 증기 개발 한국정보처리학회논문지 제권 호   PP p

;= 김성운 외 인 <적합성 시험에서 그래프 재표기 시스템 을 활용한 강한 연결 판단 방법 한국정보처리학회논문 지 제권 호   PP p

;= 06 +OPPOL AND +# 4AI <#ONFORMANCE 4ESTING OF 0RO TOCOL 3PECI`CATION AS ,ABELED 4RANSITION 3YSTEM )NTER NATIONAL 7ORKSHOP ON 0ROTOCOL 4EST 3YSTEM  %VRY

&RANCE 3EPT  PP p

;= %- #LARKE %! %MERSON AND !0 3ISTLA <!UTOMATIC 6ERI`CATION OF &INITE 3TATE #ONCURRENT 3YSTEMS 5SING 4EMPORAL 3PECI`CATIONS !#- 4RANSACTIONS ON 0ROGRAM MING ,ANGUAGES AND 3YSTEMS 6OL  .O   PP

p

;= 2 #LEAVELAND - $REIMULLER AND " 3TE_EN <&ASTER -ODEL #HECKING FOR THE -ODAL } #ALCULUS TO APPEAR IN 0ROCEEDINGS OF THE  7ORKSHOP ON #OMPUTER !IDED 6ER I`CATION ,ECTURE .OTES IN #OMPUTER 3CIENCE 

;= %! %MERSON AND # , ,EI <%bCIENT -ODEL #HECKING IN

&RAGMENTS OF THE 0ROPOSITIONAL } #ALCULUS 0ROCEEDINGS OF THE &IRST 3YMPOSIUM ON ,OGIC IN #OMPUTER 3CIENCE 

PP p

;= ! !RNOLD AND " #RUBILLE <! ,INEAR !LGORITHM 4O 3OLVE

&IXED 0OINT %QUATIONS ON 4RANSITION 3YSTEM )NFORMATION 0ROCESSING ,ETTERS 6OL   3EPT  PP p

;= 2 !LUR AND $, $ILL <! 4HEORY OF 4IMED !U TOMATA 4HEORETICAL #OMPUTER 3CIENCE 6OL  

PP p

;= !/ !HO *% (OPCROFT AND *$ 5LLMAN 4HE $ESIGN AND

!NALYSIS OF #OMPUTER !LGORITHMS !DDISON 7ESLEY 2EAD ING -ASS 

;= 진병문 김성운 최영한 <!UTOMATED 4EST 'ENERATION FROM 3PECI`CATIONS "ASED ON &ORMAL $ESCRIPTION 4ECH NIQUES %42) *OURNAL 6OL  .O    PP

p