Automated test data generation has been a major academic interest. We present Multi Directional Search (MDS), a new search-based test data generation algorithm. Unlike, Alternating Variable Method, the most commonly used search-based test data generation algorithm, traverses the variable in the function's input vector and change the value of the one variable at a time, MDS changes the value of multiple variables simultaneously. We implemented MDS on CAVM, a search-based test data generation tool for C which uses Extended AVM to handle dynamic data structure. MDS is developed to attached to and used prior to Extended AVM. We call MDS attached Extended AVM "Extended AVM+". We compare Extended AVM+ against Extended AVM using 15 functions and 55 test targets. As a result, Extended AVM+ was able to generate test data with less costs than Extended AVM.
자동화된 소프트웨어 테스트 데이터 생성은 오랫동안 학계의 주요 관심사였다. 이 논문에서는 새로운 검색기반 테스트 데이터 생성 알고리즘인 다방향 탐색(Multi Directional Search, MDS)를 제안한다. 기존에 가장 널리 사용된 검색기반 테스트 데이터 생성 알고리즘인 교대변수법(Alternating Variable Method, AVM)이 함수의 입력 벡터내 변수들을 순회하며 변수의 값을 하나씩 바꾸는 것과 달리 다방향 탐색은 여러 개의 변수들을 동시에 바꾼다. 다방향 탐색을 C를 대상으로 하는 검색 기반 테스트 데이터 생성 툴인 CAVM에 구현하였다. CAVM은 동적 데이터 구조를 처리하기 위해 확장된 AVM(Extended AVM)를 사용한다. 다방향 탐색은 Extended AVM에 부착되어 그에 선행되어 수행되기 위하여 개발되었으며 다방향 탐색이 부착된 Extended AVM을 Extended AVM+라고 명명하였다. 15개의 함수와 55개의 테스트 타겟에 대하여 Extended AVM+와 Extended AVM을 비교한 결과, Extended AVM+이 Extended AVM보다 적은 비용으로 테스트 데이터를 생성할 수 있었다.