In this dissertation, we propose automatic test derivation methods for testing interoperability of communication protocols, such as the ATM/B-ISDN signaling protocol and TCP. In the past, researches on testing communication protocols have mainly concentrated on conformance testing to check the conformance of the implementation of a protocol with regard to the protocol specification. Researches on interoperability testing with more than one interoperable entity mainly focused on general concepts and experiences of interoperability testing and systematic generation of interoperability test suites. However, little work has been reported on data part testing in interoperability test and work on test generation dealing with simultaneous inputs. This dissertation addresses two different aspects of automatic derivation of interoperability test suites; for both control and data parts of the protocol, and for complex scenarios caused by simultaneous inputs on several interfaces of the system under test (SUT).
Regarding data part testing, our proposed method first derives a $\emph{skeleton}$ test suite for control part through $\emph{reachability analysis}$. Next, it parameterizes each test case. Finally, it completes the test suite by actualizing the test cases by assigning values to their parameters. By constructing test case space based on $\emph{stable states}$ and by basing test case actualization step on $\emph{orthogonal arrays}$ used in experimental design techniques $\emph{state space explosion}$ can be avoided. In order to demonstrate the feasibility and effectiveness, the proposed method is applied to the ATM/B-ISDN signaling protocol and TCP. The application result shows that the method surpasses the conventional methods in both test size and coverage.
Conventional methods examine only single input at a time in interoperability test generation, and thus their test cases are unable to test more complex behaviors of the protocol. We extend our test generation method to generating interoperability test cases dealing with complex situations in which implementations seem to be more error-prone. For this, when building state space of protocol behavior, it allows additional inputs while the preceding input is still being processed, and also allows simultaneous inputs on different interfaces of the SUT known as $\emph{multiple stimuli}$. We also propose a test minimization method that reduces the increased test cases due to the $\emph{multiple stimuli}$ in an automatic way, keeping the same $\emph{transition coverage}$ as the original ones. Compared with the conventional methods, the experiment shows that the proposed extended test generation method generates more interoperability test cases resulting in higher transition coverage, 26% higher for TCP and 12% for ATM signaling protocol. In addition, the test minimization method reduces the interoperability test cases down to 94% of the case study for the ATM signaling protocol maintaining the same transition coverage.
통신 시스템의 상호운용성이 보장되기 위해서는 상호운용성 시험이 필수적이다. 상호운용성 시험에 있어서의 대부분의 연구는 상호운용성 시험 케이스를 도출하는데 집중되어 왔다. 하지만 프로토콜의 데이터 부분을 고려하는 연구는 거의 없으며, 도출된 상호운용성 시험 케이스는 다중 자극에 의해 발생할 수 있는 프로토콜의 복잡한 동시적 상호작용은 커버하지 못한다.
본 논문에서는 상호운용성 시험을 위한 자동 시험 도출 방법들을 제안하였다. 첫째로, 프로토콜의 제어 부분과 데이터 부분을 모두 다루는 새로운 방법을 제안하였고, 그 구현된 프로그램을 ATM 신호 프로토콜과 TCP에 적용되었다. 둘째로, 제어부분에 대한 시험 생성 방법을 다중 자극 원리에 기반하여 확장하였고, 이는 결과적으로 프로토콜 명세로부터 있을 수 있는 복잡한 시나리오를 커버하는 시험 케이스들를 추가적으로 도출한다. 또한, 시험 시간과 비용을 줄이기 위하여 이들 시험 케이스의 분량을 최소화하는 알고리즘들을 제안하였다.
시험 생성 시 데이터 부분을 고려하게 되면, 시스템 상태 및 변수 값들의 조합을 최소화하는 것이 문제가 된다. 시험 생성 방법이 유용하고 처리할 수 있는 수준이 될 수 있도록, 우리 방법은 다음 세가지 단계를 갖추고 있다. (1) 프로토콜의 제어 부분만을 고려하여 두 개의 유한 상태 기계를 결합하여 시험 스위트 골격 도출하기, (2) 시험 스위트 골격의 메시지 매개변수화, 그리고 (3) 데이터 부분을 고려하기 위하여 실험계획법을 사용하여 적합한 개수 내에서 시험 스위트에 값을 부여하는 실제화 단계이다. 유한 상태 기계들을 결합할 때는 프로토콜의 제어 부분에 대한 가능한 경로 및 안정 상태에 기반하여 구성되므로 상태 범위가 폭발적으로 확장되지는 않는다. 게다가 생성된 시험 스위트는 높은 시험 커버리지를 그대로 유지한다. 즉, 매개변수 값의 조합에 있어서 모든 가능한 쌍들이 커버되며 그 회수 또한 동일하다. 이러한 접근법은 상호운용이 되는 않는 부분을 보다 빠르게 탐지할 수 있도록 하여 보다 단기간에 높은 품질의 프로토콜을 설계할 수 있도록 돕는다.
본 논문의 다른 중요한 기여는 제어 부분에 대한 상호운용성 시험 생성법을 확장하여 실제 프로토콜 동작에서 있을 수 있는 복잡한 시나리오까지 커버할 수 있도록 한 것이다. 이 확장된 방법은 시험 대상 시스템에 다중의 입력을 허용하는 상호운용성 시험 케이스를 자동적으로 도출하고 이를 다시 최소화한다. 이것은 우리 방법이 기존의 방법들 및 앞서 제안된 우리 방법에서 가정하고 있는 단일 자극 원리 대신에 다중 자극 원리를 수용한다는 것이다. 결과적으로 우리의 확장된 방법을 통해 얻어지는 트랜지션 커버리지는 검증 기법을 통하여 얻어지는 것과 동일한 동작 범위를 커버하는 것이다. 잘 설계된 프로토콜은 $\emph{경주 상태}$, 즉, 이벤트의 예상치 못한 상대적인 타이밍에 의해 발생하게 되는 비정상적 동작을 처리할 수 있어야 한다. 다시 말하면, 프로토콜 설계자가 특정 이벤트가 항상 다른 것 보다 먼저 일어날 것이라고 잘못 가정하고 있는 것이다. 우리의 확장된 방법은 구현물이 이러한 경주 상태를 처리할 수 있는지를 시험하는 상호운용성 시험 케이스들을 도출할 수 있으며, 또한 프로토콜 상에서 경주 상태가 나타날 수 있는지 보기 위해 설계 단계에서 이용될 수도 있다.
이 다중 자극 원리를 수용하기 위하여, 상호운용성 시험 스위트 도출 알고리즘의 토대가 되는 정형 모델을 개발하였다. 확장된 시험 생성법은 ATM 신호 프로토콜과 TCP의 일부분에 적용되었다. 실험 결과를 통하여 우리 방법이 기존보다 높은 트랜지션 커버리지를 갖는 시험 스위트들을 도출한다는 것을 보였다. 이것은 TCP에 대하여는 26% 높았으며, ATM의 경우는 12% 높은 커버리지였다. 이 추가적인 커버리지가 바로 프로토콜 명세에 의해 허용되는 복잡한 동시적인 상호작용에 대한 것이다.
시험 케이스를 실제 환경에서 실행하는 데에는 많은 비용이 들기 때문에 시험 규모를 줄일 수 있는 세 개의 자동 최소화 알고리즘 또한 개발하였다. 이 알고리즘들은 동일한 트랜지션 커버리지를 유지하면서도 상호운용성 시험 케이스를 상당량 줄였다.
향후 연구로, 자동적으로 도출된 상호운용성 시험 스위트를 실제 환경에서의 프로토콜 제품에 적용하는 방법에 관한 연구가 남아 있다. 제안된 방법을 다중 자극 원리에 기반하면서 데이터 부분까지 시험 할 수 있는 쪽으로 확장하는 것 또한 연구 대상이다. 다른 연구 방향으로는 제안된 방법을 GSM 혹은 CDMA 프로토콜과 같은 이동 통신 프로토콜에 적용해보거나, 제안된 방법론과 TTCN3의 기본 접근방법을 비교해 볼 수 있을 것이다.
