시스템의 확률 값 시험을 위한 신뢰구간 비교 분석

황익순,Hwang, Ik-Soon 한국전자통신학회 2010 한국전자통신학회 논문지 Vol.5 No.5

확률적 특성을 가지는 시스템의 시험을 위해서는 시험 입력을 일정 횟수만큼 반복하여 제공하고 관찰된 데이터를 기반으로 판정이 내려져야 한다. 구간 추정 기법을 이용하여 관찰된 데이터로부터 확률 값이 올바른지 여부를 판단할 수 있으며, 이 때 적절한 신뢰구간의 선택은 시험의 품질을 결정하는 중요한 요인이 된다. 본 논문에서는 다양한 크기의 표본에 대해 대표적인 구간 추정 기법인 Wald 신뢰구간과 Agresti-Coull 신뢰구간을 비교 분석한다. 각 신뢰구간이 확률 값 시험에 사용되었을 경우 올바른 구현 제품이 시험을 통과할 확률과 잘못된 구현제품이 시험을 통과하지 못할 확률을 기반으로 비교 분석을 수행하며, 확률 값이 올바른지를 판단하기 위한 양측검정뿐만 아니라 확률 값이 기준 확률 이상인지 여부를 판단하기 위한 단측검정을 사용하는 경우에 대해서도 비교 분석을 수행한다. 비교 분석 결과 양측검정의 경우 Agresti-Coull 신뢰구간을 사용할 것을 추천하며, 단측검정의 경우 큰 크기의 표본에 대해서는 Agresti-Coull 신뢰구간을, 적은 크기의 표본에 대해서는 Wald 신뢰구간 또는 Agresti-Coull 신뢰구간을 선택적으로 사용할 것을 추천한다. When testing systems that incorporate probabilistic behavior, it is necessary to apply test inputs a number of times in order to give a test verdict. Interval estimation can be used to assert the correctness of probabilities where the selection of confidence interval is one of the important issues for quality of testing. The Wald interval has been widely accepted for interval estimation. In this paper, we compare the Wald interval and the Agresti-Coull interval for various sizes of samples. The comparison is carried out based on the test pass probability of correct implementations and the test fail probability of incorrect implementations when these confidence intervals are used for probability testing. We consider two-sided confidence intervals to check if the probability is close to a given value. Also one-sided confidence intervals are considered in the comparison in order to check if the probability is not less than a given value. When testing probabilities using two-sided confidence intervals, we recommend the Agresti-Coull interval. For one-sided confidence intervals, the Agresti-Coull interval is recommended when the size of samples is large while either one of two confidence intervals can be used for small size samples.

데이타 부분을 시험하기 위한 다중 EFSM으로 구성된 프로토콜로부터의 단일 EFSM 생성 방안

황익순(Ik-Soon Hwang),장웅(Woong Jang),김태형(Tae-Hyong Kim),장민석(Min-Seok Jang),박기현(Kee-Hyun Park),이재용(Jai-Yong Lee),이상배(Sang-Bae Lee) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.8

적합성 시험에서 데이타 부분을 시험하기 위한 시험열 생성은 많은 비용이 요구되며, 이에 따라 자동화의 필요성이 강조되고 있다. 하지만 프로토콜의 구조가 다중 모듈로 구성되어 있기 때문에 단일 모듈 프로토콜을 시험열 생성의 대상으로 하는 기존의 시험열 생성 방법들을 적용할 수 없으며, 이로 인해 자동화가 어려워진다. 본 논문에서는 다중 모듈로 표현된 프로토콜을 시험하는 시험열을 생성하기 위해서 다중 모듈 모델을 등가의 단일 모듈로 변환하는 방법을 제안한다. 제안한 변환 방법은 도달성 분석(reachability analysis) 기법을 응용한 방법으로 변환 과정에서의 의미 손실(semantic loss)을 최소화할 수 있는 장점을 갖는다. 또한, 본 논문에서는 시험열 생성을 어렵게 하는 프로토콜의 불확정성 (non-determinism)을 구현에 존재하는 불확정성과 명세에 존재하는 불확정성으로 구분하였으며, 몇 가지 가정을 설정함으로써 명세에 존재하는 불확정성이 제거될 수 있음을 보인다. The necessity that test sequences are automatically generated from a protocol specification for the purpose of testing data flow in the implementation has been emphasized because the cost of the most existing data part testing strategies is prohibitively high. However, existing automatic test generation methods based on single-module structure are not applicable to real protocol having multi-module one. In this paper, we propose a method which transforms multi-module model into an equivalent single-module. Since the proposed method uses the reachability analysis technique it can minimize semantic loss of the specification during the transformation process. We also classify non-deterministic characteristics of a protocol into two parts: the one in implementation and the other in specification, and then show that the latter can be removed on some assumptions.

신뢰성있는 시험데이타 선택을 위한 경로도메인 기반 신뢰도 제시

장민석(Min-Seok Jang),황익순(Ik-Soon Hwang),김태형(Tae-Hyong Kim),전상현(Sang-Hyun Jeon),송명렬(Myong-Lyol Song),김동연(Dong-Yon Kim),이길흥(Kil-Hung Lee),이재용(Jai-Yong Lee) 한국정보과학회 1998 정보과학회논문지(B) Vol.25 No.11

프로그램시험(program testing)의 신뢰성있는 수행을 위해 현재까지 데이타부분시험(data part testing) [1-11] 분야에서 다양한 시험데이타선택방법(test data selection strategy)들이 제안되었다. 하지만 이들에 의해 추출한 시험데이타가 오류를 검출하는데 있어서 얼마나 신뢰성 있는지는 의문일 뿐만 아니라 구체적인 시험수행방법을 제시하지 못한채 이론에만 그치고 있다. 이는 오류의 유형 및 그 오류가 프로그램에 미치는 특성을 제대로 분석하지 않았기 때문에 발생한다. 본 논문의 목적은 이 문제점을 해결하기 위해 우선적으로 오류를 경로도메인 관점에서 재정의하고, 선택한 데이타의 오류검출확률 즉, 신뢰도를 수식적으로 제시함으로써, 신뢰성있는 시험데이타선택방법을 제시하기 위한 이론적 바탕을 제공하는 데에 있다. For the purpose of reliable program testing in the area of software engineering, there have been recently a variety of test data selection strategies in the field of data part testing. Not only, however, it is doubtful how reliably the test data derived from the above methods is able to detect program faults, but also in many cases they are only theoretical and the concrete testing methodology is not suggested. It is because they do not analyze the types of faults and the characteristics of their effects on program well. The object of this paper is to give the theoretical foundation for abtaing the more reliable domain-based test data selection strategy through redefining faults in the respect of path-domain, classifying them into three types and then deriving the fault detecting probability or reliability of a test data in mathematical manner.

시간적 오토마타에서 도달성 그래프의 도출기법

이상배(Sang-Bae Lee),황익순(Ik-Soon Hwang),김태형(Tae-Hyong Kim),이재용(Jai-Yong Lee),박찬민(Chan-Min Park) 한국정보과학회 2000 정보과학회논문지 : 정보통신 Vol.27 No.4

프로토콜 검증에 있어서 reachability analysis를 사용하는 방법은 널리 알려지고 많이 사용되는 방법이다. Reachability analysis를 통한 검증 방법에 있어서는 프로토콜의 동작을 나타내는 reachability graph의 생성이 중요하다. 그러나 시간이 관련되는 경우 발생하는 상태 수 폭증(state explosion) 또는 시간의 실수적 성질의 문제가 있어서 reachability graph의 생성에 큰 장애가 되어왔다. 실시간 시스템이나 프로토콜에 있어서, 타이머는 대기 시간의 한계를 지정하거나, 일정한 시간간격을 시스템에 알릴수 있도록 하는 등 시간의 상대적 기준점으로 사용되며 이외에도 여러 가지 용도로 타이머를 사용하게 되어 프로토콜을 모델링하는데 있어서 타이머는 불가결하다. 본 논문에서는 타이머를 모델링하지 못하며, 통신 프로토콜과 그 환경을 모델링하는데 적절치 못하던 기존의 방법과 달리, 타이머를 포함하며 통신 프로토콜과 그 환경을 적절히 표현할 수 있도록 시스템을 기술하는 방법과 함께 상대적 시간 개념으로 천이와 타이머를 다루는 방법을 통해서 시간 개념과 타이머가 들어있는 프로토콜의 reachability graph를 유도하는 방법을 제안하였다. 제안한 방법을 통해서 기존 방법으로는 찾아낼 수 없었던 시스템의 오류를 찾아낼 수 있었다. 이를 통해 보다 실제 프로토콜에 가깝게 모델링하고 검증할 수 있는 기반을 마련하고 있다. One of the most famous and widely used methods in protocol verification is reachability analysis. In reachability analysis, it is important to derive reachability graph which describes the behavior of a protocol. However, in the case of concerning time, there have been many obstacles to derive reachability graph due to state explosion problem and the infinite precision and length of time. In real-time system and protocol, timer can specify the bound for waiting time, or indicate a certain time interval, so that timer can be seen as a relative base point for time measure. Moreover, timer is used for so many other purposes that it would be troublesome to model the protocols without timer. In this paper, we propose a method to derive a reachability graph from protocol with timed transitions and timers by handling transitions and timers with the relative time concept. The proposed method is capable of modeling timers which was impossible by the existing methods. And we also propose a system description technique which can describe protocols with timer and its circumstances more precisely than the existing methods. With the method we would find an error which was not detected by existing method. This method can give base for realistic modeling and powerful verification of real protocol.

적합성시험에서 데이타흐름시험 개념의 형식화를 통한 시험케이스의 최적화

김태형(Tae-Hyong Kim),장민석(Min-Seok Jang),황익순(Ik-Soon Hwang),오행석(Haeng-Seok Oh),이재용(Jai-Yong Lee),이상배(Sang-Bae Lee) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.5

In this paper, we propose an optimization method of data flow test sequences in conformance testing. Test sequences for data flow test with good fault coverage are normally longer than those of control flow test, so their optimization is needed. As optimizations of control flow test sequences could have been studied on the basis of the formalized concept of the test, we formalize the concept of data flow test and optimize test sequences of the test. We first define some test measures in edges and show what test measures a test sequence has in its test measure set. Some existing data selection criteria are expressed in this way, and a new data selection criterion fit for conformance testing is proposed. As the length of data flow test sequences increases due to loops and converging states, the proposed optimization method mainly handles them through the formalized data flow test concepts. Other good points of this technique are expressed and the results of applying it to two communication protocols show its effectiveness last. 본 논문에서는 적합성시험에서 데이타흐름시험열의 최적화방법을 제안한다. 우수한 오류검출 범위를 갖는 데이타흐름시험열은 일반적으로 제어흐름시험열보다 길기 때문에 최적화가 요구된다. 제어흐름시험열의 최적화는 형식화된 시험개념을 바탕으로 연구될 수 있었으므로 마찬가지로 데이타흐름시험의 개념을 형식화하여 그 시험열을 최적화 한다. 먼저 이 각 예지에 존재하는 시험성분을 정의하고 각 시험열이 그 시험성분집합 안에 어떠한 시험성분을 가지는지를 보인다. 기존의 주요 데이타선택범주를 이러한 방법으로 표현하고 적합성시험에 알맞은 새로운 데이타 선택범주를 제안한다. 데이타흐름시험열의 길이는 주로 루프와 집중상태에 의해 증가되므로 제안된 최적화방법은 형식화된 데이타흐름시험의 개념을 통해 그 부분을 대상으로 한다. 마지막으로 제안된 방법이 가지는 다른 유용성에 대해 논의하고 두 가지 통신 프로 토콜의 시험케이스 생성에 이 기법들을 적용하여 그 효용성을 입증한다.

통신프로토콜의 적합성시험열 생성을 위한 경로 탐색 방법

황익순,장민석,이상배,이재용 延世大學校 電波通信共同硏究所 1996 電波通信論文誌 Vol.2 No.1

본 논문에서는 적합성 시험에서 EFSM(Extend Finite State Machine) 모델에 대한 데이타부분 시험열을 효율적으로 생성시켜 주는 탐색 방법에 대해 제안하였다. 이 탐색 방법에서는 depth-first search와 같은 기존의 탐색 방법과는 달리 탐색 초기에 다양한 경로가 찾아진다. 이미 제안된 시험열 생성 방법인 데이타 값을 바탕으로 하여 시험열을 생성하는 방법에서 이 탐색 방법을 이용하였을 경우 기존의 탐색방법을 이용하는 것보다 효율적으로 시험열을 생성할 수 있다. 본 논문에서는 Inres 프로토콜에 이 탐색 방법과 기존의 탐색 방법인 depth-first search를 각각 적용하여 시험열을 생성, 비교하여 보았으며, 제안된 탐색 방법을 이용하면 같은 시험 범주를 가지면서도 짧은 길이를 갖는 시험열을 효율적으로 생성할 수 있음을 알 수 있다. In this paper we proposed a searching algorithm for generating test cases, which can test data part of EFSM model in conformance test. In a different way to existing algorithm like depth-first search algorithm, this one can find various paths in the early stage of searching. When it is used in readily proposed test case generation method which is based on the value of variables and parameters it can generate test cases efficiently than in the case of depth-first search algorithm being used. We generated test cases for Inres protocol using each of proposed and depth-first search algorithm, and compared these two methods. proposed algorithm can generate much shorter test sequences efficiently than existing one.