Since repeated executions of a concurrent program with an identical input may yield different results depending upon execution paths, concurrent program testing derives and executes test sequences which correspond to interleavings of concurrent events. This thesis presents an approach to specification-based testing of Java multithreaded programs with representative sequences generated from a Statecharts specification. Representative sequences are a subset of all possible interleavings of concurrent events that define the behaviors of a concurrent program.
Because a program's correctness may be determined by checking whether a program implemented all behaviors described in its specification or not, the program can be regarded as being correct if it can supply an alternative execution that has the same effects as the program's behavior for each representative sequence. Based on this observation, we employ each representative sequence as a seed to acquire its equivalent sequences to reveal the same behavior. In test execution, the traditional deterministic testing is inefficient since it controls a program's execution according to only a given test sequence. Therefore, we have developed a new type of deterministic testing which controls a program's execution according to equivalent sequences. It can efficiently determine whether a program reveals the expected behavior by implementing at least one of equivalent sequences or not.
The environment for concurrent program testing generally consists of components to support test sequence generation and test execution. We have developed a flexible environment that supports two testing strategies: one is to check whether a program implements at least one equivalent sequence and the other is to check whether a program implements all equivalent sequences. In contrast to previous works which test an entire program based on either of the strategies, our environment can select a testing method suitable for the testing strategy to a type of behavior. In order to investigate the effectiveness of our environment, a prototype system has been implemented and applied to simple examples.
같은 입력을 가지고 병행 프로그램을 반복적으로 수행했을 때, 어떤 수행 순서를 따랐는가에 의해서 다른 결과를 보일 수 있다. 따라서, 병행 프로그램의 명세 기반 시험기법에서는 명세로부터 시험 시퀀스를 생성하고, 프로그램이 그 시험 시퀀스를 따라서 수행될 수 있는지를 확인하다. 본 논문에서는 대표 시퀀스를 시험 시퀀스로 사용하는 자바 다중 스레드 프로그램에 대한 명세 기반 시험 기법을 제안한다. 대표 시퀀스는 병행 이벤트의 인터리빙에 의해서 생성할 수 있는 모든 시퀀스들의 일부분으로, 각 대표 시퀀스는 병행 프로그램에서 보일 수 있는 각 행위를 대표하는 시퀀스이다.
프로그램 시험에서는 일반적으로 프로그램이 명세에서 기술한 모든 행위를 표현할 수 있다면 정당하다고 할 수 있다. 따라서, 프로그램이 각 행위에 대한 동치 시퀀스들 중에서 일부분을 구현하고 있다면 그 프로그램은 예상 행위를 표현할 수 있으며, 이를 통해서 정당하다고 간주할 수 있다. 각 대표 시퀀스들로부터 생성할 수 있는 동치 시퀀스들은 그 대표 시퀀스와 동일한 행위를 표현한다. 기존에 제안되었던 결정적 시험 수행 방법은 프로그램이 하나의 시험 시퀀스에 대해서만 구현 여부를 확인하기 때문에, 위와 같은 상황에 적용하기에는 비효율적이다. 따라서, 본 연구에서는 동치 시퀀스들을 모두 고려할 수 있는 새로운 결정적 시험 수행 방법을 개발하였다. 새로운 시험 수행 방법의 제어기는 프로그램이 적어도 하나의 동치 시퀀스를 구현함으로서 예상 행위를 표현할 수 있는지를 효율적으로 판단할 수 있다.
병행 프로그램을 위한 시험 환경은 일반적으로 시험 시퀀스 생성과 시험 수행을 모두 포함한다. 우리는 두가지의 시험 전략을 모두 지원할 수 있는 시험 환경을 개발하였다. 병행 프로그램 시험에서 사용하는 시험 전략으로는 프로그램이 적어도 하나의 동치 시퀀스를 구현하였는지를 확인하는 것과 모든 동치 시퀀스들을 구현하였는지를 확인하는 것이 있다. 기존의 연구들이 하나의 시험 전략에 따라서 전체 프로그램을 시험하는데 반해서, 우리의 시험 환경에서는 각각의 행위에 대해서 다른 시험 전략을 적용할 수 있다. 이러한 시험 환경의 효용성을 보이기 위해 도구가 구현되었으며, 명세와 프로그램으로 구성된 간단한 예제에 실제로 적용하였다.
