To effectively utilize advanced multi-core processors, many software systems today are built as multithreaded programs. One challenge in developing a multithreaded program is to ensure its correctness. Unlike single-threaded programs, the behavior of a multithreaded program depends not only on program input values, but also on thread schedules. To ensure correctness, a multithreaded program must be checked for all thread schedule cases whose numbers are notoriously large due to non-determinism in
thread scheduling. Many techniques have been proposed to generate various thread schedules to test multithreaded programs and find concurrency errors. However, none of these techniques can provide effective and efficient fault detection results at the same time scales with respect to the size of a target multithreaded program.
In this dissertation, I present a new technique that utilizes concurrency coverage metrics to generate effective and efficient test executions of multithreaded programs. Concurrency coverage metrics aid in supporting multithreaded program testing by providing reasonable assessments of the testing quality. Unlike structural coverage metrics such as the branch and statement coverage metrics, it has not been well established that concurrency coverage metrics are actually useful for multithreaded program testing, and there exist only a few applications of concurrency coverage metrics for multithreaded program test generation. The first part of this dissertation, through empirical study, attempts to answer the question of whether or not the existing concurrency coverage metrics are actually useful for testing multithreaded programs. Although none of the existing metrics seems to be perfect, the study results show that the existing concurrency coverage metrics are effective at estimating fault detection ability and at providing test generation targets in multithreaded program testing. The second part of this dissertation presents a new concurrency coverage based thread scheduling algorithm that generates test executions to achieve high concurrency coverage fast. In particular, the proposed technique utilizes a new coverage metric called the combinatorial concurrency coverage metric, which supplements the existing concurrency coverage metrics by providing more fine-grained test targets. The experiment results show that the proposed technique generates more effective and more efficient test executions than do the existing multithreaded program test generation techniques. For the last part of this dissertation, I present a concurrency coverage-based regression testing technique for multithreaded programs. The proposed technique utilizes a concurrency coverage metric to identify the changed multithreaded program behavior by a code modification; it then generates the targeted test executions for the identified behaviors to effectively detect regression faults. The experiment results imply that the proposed regression testing technique is more effective and efficient than are the existing techniques at detecting regression faults of multithreaded programs.
오늘날 많은 소프트웨어는 멀티코어 하드웨어를 효과적으로 활용할 수 있는 멀티쓰레드 프로그램(multithreaded program)형태로 개발되고 있다. 멀티쓰레드 프로그램 개발의 난점 중 하나는 기존의 소프트웨어 테스팅(software testing) 방법이 멀테쓰레드 프로그램의 동시성 오류 검출과 동작정확성 검증에 효과적이지 않다는 점이다. 프로그램 입력 값에 의해서만 동작이 결정되는 비 멀티쓰레드 프로그램(단일쓰레드 프로그램)과 달리, 멀티쓰레드 프로그램의 동작은 입력 값뿐만 아니라 쓰레드 스케쥴(thread schedule), 즉 쓰레드 간 실행순서에 의해서도 영향을 받는다. 일반적인 멀티쓰레드 프로그램의 경우, 쓰레드 스케쥴이 실행 시점에 비결정적(non-deterministic) 쓰레드 스케쥴러에 의해 결정되기 때문에, 규모가 작은 프로그램에 대해서조차 발생 가능한 쓰레드 스케쥴이 극심히 많고, 별도의 장치 없이 쓰레드 스케쥴의 의도적 생성이 어렵기 때문에, 기존의 비 멀티쓰레드 프로그램을 대상으로 한 테스팅 방법으로는 효과적이고 효율적인 테스팅 수행이 어렵다. 멀티쓰레드 프로그램의 오류검출과 동작정확도 검증을 위해 현재까지 개발된 여러 기법은, 분석 능력이 제한적이거나 검증 대상 프로그램 크기에 대한 확장성이 낮아 실제 소프트웨어 개발에서 실용성이 낮은 실정이다.
본 논문은 동시성 커버리지 메트릭(concurrency coverage metric)을 활용하여 멀티쓰레드 프로그램을 효과적이고 효율적으로 테스팅하는 자동 테스팅 기법을 제안한다. 동시성 커버리지 메트릭은, 현재 널리 쓰이는 분기/구문 커버리지 메트릭과 유사하게, 검증 대상 프로그램에서 대한 테스팅 조건을 생성함으로써 멀티쓰레드 프로그램의 체계적인 테스팅을 지원하고자 제안된 방법론이다. 반면, 동시성 커버리지 메트릭이 실제 소프트웨어 테스팅에서 어느 정도 효용성을 제공하는 지 실증적으로 입증되지 않았으며, 그동안 동시성 커버리지 메트릭을 활용한 자동 테스팅 기법도 제한적인 수준이었다. 본 논문은 우선, 동시성 커버리지 메트릭이 테스트 메트릭으로서 멀티쓰레드 프로그램 테스팅에 효과적인 기능을 제공하는지를 실험적 방법으로 검토하였다. 여러 멀티쓰레드 프로그램을 이용한 실험 결과에 따르면, 현재 제안된 대부분의 동시성 커버리지 메트릭은 멀티쓰레드 프로그램 테스팅의 오류 검출능력을 추정하고 유용한 테스트 생성 지표를 제공하는데 효과적인 기능을 제공한다. 본 논문은 두 번째로, 테스팅 과정에서 높은 동시성 커버리지를 단시간에 달성하는 쓰레드 스케쥴 생성 알고리즘을 제시하고, 이를 기반으로 한 자동 테스팅 기법을 소개한다. 본 논문이 제시한 자동 테스팅 기법은, 기존에 제안된 동시성 커버리지 메트릭의 한계점을 개선한 새로운 메트릭인 조합적 동시성 커버리지 메트릭 (combinatorial concurrency coverage metric)를 활용한다. 본 논문이 제시한 자동 테스팅 기법을 기존의 멀티쓰레드 프로그램 테스팅 기법과 비교한 실험 결과에 따르면, 본 논문의 기법이 기존 기법보다 향상된 멀티쓰레드 프로그램 오류 검출 효용성과 효율성을 달성함을 알 수 있다. 마지막으로, 본 논문은 동시성 커버리지 메트릭을 활용하여 멀티쓰레드 프로그램에 대해 효과적으로 회기 테스팅(regression testing)을 수행하는 동시성 커버리지 기반 회기 테스팅 기법을 제시한다. 본 논문이 제시한 기법을 기존 기법과 비교한 실험결과에 따르면, 동시성 커버리지 기반 회기 테스팅 기법은 멀티쓰레드 프로그램 수정 과정에서 발생하는 동시성 회기 오류를 기존 기법보다 효과적이고 효율적으로 검출한다.
