모델 검사기와 검색 기반 알고리즘을 이용한 모델 기반의 테스트 스위트 자동 생성에 대한 연구

Abstract

모델 검사기를 이용한 테스트 케이스 도출은 모델로부터 테스트 케이스를 생성하여 검증에 필요한 시간을 최적화하는 모델 기반 테스팅 분야의 유망한 방법 중 하나이다. 하지만 모델 검사기는 시스템의 모든 사례를 검사하여 품질을 보증하는 도구이기 때문에, 이를 사용할 때 상태 공간 폭발 문제를 야기할 수 있다. 또한, 테스트 스위트 도출에 있어서 중복된 테스트의 생성이 빈번하다는 단점이 있다. 따라서 모델 검사기를 이용하여 테스트 케이스를 생성할 땐 넓은 탐색 공간의 제한과 테스트 케이스 최적화에 대해 고려해야 한다.

본 논문에서는 모델 검사기와 유전 알고리즘을 이용하여 테스트 스위트를 생성할 때, 테스트 스위트의 효율을 향상시키기 위한 가중치 기반의 탐색 기법과 실행 경로를 고려한 테스트 스위트 최적화 기법을 제안한다. 통과하기 어려울 것으로 예상되는 전이에 가중치를 부여하고, 적응형 랜덤 알고리즘으로 탐색할 공간을 선택하면 상태 공간 폭발 문제를 해결할 수 있다. 또한, 입력 인자를 통해 테스트 스위트 내의 실행 경로를 구분하고 그리디 알고리즘을 적용하여 커버리지에 관여하지 않는 경로는 삭제하는 최적화 기법을 도입하였다. 이 방법은 경로의 실행 가능성을 유지하면서도 최적화된 테스트 스위트를 도출한다.; Model-based test case generation techniques, which create tests from formal software models to optimize the time required for verification, attract great interest. Among them, test case generation using model checker is one of the promising method. However, since a model checker is a tool for ensuring the quality of the program by examining all possible executions of a system, it can cause a state space explosion problem. In addition, there is a disadvantage of generating redundant test cases. Therefore, when deriving test cases using model checker, the method to limit the state space explosion and optimize test cases should be considered.

This paper proposes a weight-based state space search method and a test suite optimization technique based on an execution path for test suite generation using a model checker and search-based algorithm. A weight-based state space search can solve the state space explosion problem by weighting the transition which is hard to pass through and selecting the space to search using adaptive random algorithm. The optimization technique distinguishes execution paths from the test suite based on the input parameters and deletes the path which does not ensure coverage using a greedy algorithm. The proposed method derives an optimized test suite which contains feasible test cases.