문서명: Review of Search based Techniques in Software Testing
저자: Rakesh Roshan 외 2인, 인도
문서 유형: 대학 연구 논문, 2012년 저널 출판(총 4페이지)
검색 기반 테스팅(Search Based Software Testing)에 대한 기존 문헌들을 조사한 자료
초록
소프트웨어 테스팅에서 가장 많은 노력을 필요로 하는 작업은 테스트 케이스 생성이다. 테스트의 성공은 테스트 케이스의 효과성에 크게 좌우된다. 테스트 케이스 생성 작업을 용이하게 하고 소프트웨어 테스팅을 수행하기 위해 다양한 접근 방식이 제안되었으며, 최근 수동 테스트 케이스 생성에서 자동 테스트 케이스 생성으로 패러다임이 전환되었다. 이 논문은 검색 기반 소프트웨어 테스팅(SBST) 접근 방식을 검토하고 이 분야에서 수행되는 연구의 추세를 예측하며 향후 소프트웨어 테스팅에서 예상되는 새로운 가능성을 탐구하고자 한다.
서론
검색 기반 소프트웨어 테스팅(Search-based software testing: SBST)은 힐 클라이밍(hill climbing), 유전 알고리즘(genetic algorithms) 등과 같은 임의의 또는 지시적 검색 기술을 사용하여 소프트웨어 테스팅 및 V&V(Verification & Validation) 도메인의 문제를 해결하는 것이다. 검색 기반 소프트웨어 테스팅(SBST)은 검색 기반 소프트웨어 엔지니어링(SBSE)의 일부로 SBSE의 범위가 확대되면서 자연스럽게 연구자들의 관심을 끌고 있다.
최근 몇 년 동안 검색 기반 소프트웨어 테스팅(SBST)이 부상했으며, 특히 주어진 기준을 충족하는 테스트 데이터를 생성하는 기술이 발전했다. McMinn 등이 수행한 검색 기반 소프트웨어 테스트 생성에 대한 조사는 화이트 박스 테스트, 블랙 박스 테스트, 그레이 박스 테스트, 그리고 비기능적 속성(non- functional properties)의 검증을 위한 검색 기반 기술의 적용을 보여준다. 검색 기반 소프트웨어 테스팅은 화이트 박스 접근 방식과 블랙 박스 접근 방식을 사용하여 구현할 수 있다.
관련 문헌 연구
1976년 Miller et al.
검색 기반 소프트웨어 테스팅(Search Based Software Testing)이라는 용어는 1976년 Miller 등에 의해 처음 사용되었다. 그들의 접근 방식은 그 당시에는 완전 새로운 것이었고 테스트 데이터 생성을 위한 효과적인 기술임이 입증되었다. 이 접근 방식이 부동 소수점 입력 데이터를 생성하는 데 효율적으로 적용되었다. 시간이 지남에 따라 진화적 접근 방식(evolutionary approach)과 같은 검색 기반 소프트웨어 테스트와 관련된 다양한 개념이 생겨났고, 이 목적을 위해 유전 알고리즘(Genetic algorithms)이 주로 사용되었다. 유전적 테스트 케이스 생성은 각 노드가 함수이고 그 입력이 해당 노드의 자식 노드인 트리처럼 진화한다. 문제별 적합도 함수(problem specific fitness function)에 따라 개체들이 각 세대에서 유지되는 다음 모집단을 채우는 데 사용된다.
2009년 Antoniol et al., 2008년 Scarfone et al.
Antoniol 등은 소프트웨어 취약성을 탐지하기 위해 검색 기반 테스트 접근 방식을 평가하였다[3]. 그들의 연구는 검색 기반 테스트 분야에서 흥미로운 오픈 연구 과제를 제시하는데, 주요 추진 영역은 소프트웨어 취약성이지만 역설적으로 소프트웨어 취약성이 없다고 해서 보안 리스크가 줄어들지는 않는다[3]. 또한 보안은 고립된 프로그램, 주어진 환경 또는 네트워크 구성에 국한되지 않는다. 최근 NIST의 정보 보안 테스트 및 평가 기술 가이드[4]에서는 침투 테스트(penetration testing)의 전경을 나열하였다. 침투 테스트는 현실 세계의 실제 공격을 모방하며 다양한 방법으로 수행할 수 있다.
2009년 Windisch et al.
Windisch 등은 검색 기반 테스트 기술[6] 내에서 입력 신호를 생성하기 위한 두 가지 새로운 접근 방식을 제안하였다. 그들은 이 기술을 적용하여 연속 시스템(continuous systems)에 대한 유효한 신호를 생성한다. 이러한 접근 방식은 현실적인 신호 집합을 근사화하는 문제에 실험적으로 적용했을 때 매우 효과적인 것으로 나타났다. 신호를 근사화하고 검색 기반 소프트웨어 테스트 내에서 특정 목표에 도달하는 것은 모두 적합도 값 피드백을 기반으로 하므로 직접 비교가 가능하다. 결과에 따르면 두 접근 방식 모두 약간의 사소한 문제가 있음에도 불구하고 소프트웨어 테스트에 적용할 때 신호 생성 및 최적화에 적합하다.
2008년 Blanco et al.
Blanco 등은 BPEL 비즈니스 프로세스의 자동 테스트 케이스 생성을 위해 메타 휴리스틱 기술인 '산점 검색(Scatter Search)'을 기반으로 하는 접근 방식을 제시하였다[5]. 전이 커버리지(transition coverage)가 적절성 기준(adequacy criterion)으로 사용된다. 이 접근 방식은 같은 저자가 제시한 TCSS-LS 알고리즘의 진화형으로, C로 작성된 프로그램에 대한 분기 커버리지(branch coverage) 기준으로 테스트 케이스를 생성한다.
2009년 Marchetto et al.
Marchetto 등은 테스트 케이스 다양성(test case diversity)을 측정 기준으로 가장 유망한 것을 선택하기 위해 긴 상호작용 시퀀스의 광대한 공간을 탐색하기 위한 검색 기반 알고리즘을 조사하였다. 또 다른 논문에서 Marchetto 등은 AJAX 웹 애플리케이션에서 상태 기반 테스트(state-based testing) 사용을 조사하고 특히 이 기술로 인해 발생하는 특정 오류에 집중하였다. 이 기술은 AJAX 애플리케이션에 대한 유한 상태 머신의 동적 추출 및 의미적으로 상호 작용하는 이벤트(semantically interacting events)에 기반한 테스트 케이스 집합을 식별하는 것을 목표로 한다. 경험적 증거는 이러한 종류의 기술이 오류를 찾는 데 효과적임을 보여준다. 자동으로 생성된 테스트 케이스가 전문 테스터가 수동으로 수행한 신중한 기능 테스트의 테스트 케이스와 비슷하였다. 안타깝게도 의미적으로 상호 작용하는 이벤트에 기반한 이 기술의 주요 단점 중 하나는 매우 많은 수의 테스트 케이스로 구성된 테스트 케이스 모음(testing suites)을 생성한다는 점이며 이로 인해 유용성이 제한될 수 있다[7].
2009년 Afzal et al., 2010년 Harman et al.
Afzal 등은[2] 유전 프로그래밍(genetic programming)을 사용하여 결함 예측(fault prediction)을 목표로 하는 실험을 하고 효율성 향상 측면에서 기존 방식들과 비교하였다. 이 연구자들은 결함 수 데이터를 예측하기 위한 유전 프로그래밍 사용을 평가하였다. Harman 등은 달성된 커버리지를 손상시키지 않고 이를 수행하는 세 가지 알고리즘을 소개하였다. 그들은 분기 커버리지(branch coverage)를 위한 적지 않은 검색 공간을 포함하는 다섯 가지 벤치마크 프로그램에서 세 가지 알고리즘의 효과성에 대한 실증적 연구 결과도 제시했다. 결과에 따르면 커버리지를 잃지 않고도 검색 기반 테스트에서 생성된 테스트 케이스 수를 줄일 수 있다. 검색 기반 테스트의 분기 커버리지 기반 방식은 자동화된 테스트 데이터 생성 문제를 재공식화 하였다. 그들은 검색 기반 구조적 테스트 데이터 생성 문제의 새로운 공식을 도입하는데, 그 목표는 테스트 케이스 수를 최소화하는 동시에 커버리지를 최대화하는 것이며, 주어진 테스트 모음(test suite)에 대해 테스트 중인 소프트웨어의 동작을 확인하는데 관련된 인간 오라클 비용/노력도 고려한다.
2010년 Zhao et al.
Zhao 등은 확장된 유한 상태 머신(Extended Finite State Machines: EFSM) 모델에서 실행 가능한 전환 경로(feasible transition paths: FTP)에 대한 자동화된 테스트 데이터 생성 시스템을 제시하였다. 그들은 널리 사용되는 4개의 EFSM 모델에 시스템을 적용하여 생성한 테스트 데이터에 상관관계(correlation) 및 형식화(formalization)에 대한 통계적 테스트를 사용하여 테스트 효율성의 통계적 속성을 조사하였다. 중요하고 고무적인 발견은 FTP에서 테스트 생성 비용과 조건의 수치적 동등연산자(numerical equal operators) 수 사이에 밀접한 양의 상관관계가 있다는 것이다.
2010년 Li et al.
Li 등은 테스트 케이스 우선순위를 위한 5개의 검색 알고리즘을 연구하고 이러한 알고리즘의 성능을 비교하기 위해 시뮬레이션 실험을 수행하였다. 이 연구의 목표는 심층적인 조사를 수행하고 비교 결과의 일반성을 개선하는 것이다. 이 시뮬레이션 연구는 두 가지 유용한 지침을 제공한다.
(1) Additional Greedy Algorithm(AGA) 및 Optimal Greedy Algorithm(OGA)과 같은 효율적인 검색 알고리즘 사용하라. 이 알고리즘들이 대부분의 경우 다른 세 가지 검색 알고리즘보다 성능이 뛰어나다. 따라서 이 두 가지 검색 알고리즘을 우선적으로 사용하는 것이 좋다.
(2) 중첩 비율(Ratio of Overlapping)[8]은 이러한 다섯 가지 검색 알고리즘의 성능을 더 잘 조사하기 위해 도입되었다. 논문[9]의 결과에 따르면, AGA와 OGA라는 두 가지 최상의 검색 알고리즘의 성능은 중첩 비율(RO)이 약 3일 때 최대이고 RO가 증가하면 감소하기 시작한다.
2010년 Afzal et al.
Afzal 등은 단위, 기능, 통합 및 시스템 테스트 단계를 빠져나간 결함 수를 예측하기 위한 다음의 다섯 가지 기술을 평가하였다.
i. 입자 군집 최적화 기반 인공 신경망(Particle swarm optimization based artificial neural networks: PSO-ANN),
ii. 인공 면역 인식 시스템(Artificial immune recognition systems: AIRS),
iii. 유전자 발현 프로그래밍(Gene expression programming: GEP),
iv. 유전자 프로그래밍(Genetic programming: GP)
v. 다중 회귀(Multiple regression: MR),
논문 [10]의 연구 목적은 알맞은 단계에서 알맞은 결함을 찾아냄으로써 다양한 테스트 단계에서 개선 가능성을 정량화하는 것이다. 단위 및 기능 테스트 단계에서는 AIRS와 PSO-ANN이 더 나은 성과를 보인 반면 GP는 통합 및 시스템 테스트 단계에서 더 나은 성과를 보였다. 이 연구는 다양한 검색 기반 기술이 다양한 테스트 단계에서 개선 가능성을 예측하는 데 적용될 수 있으며 GP는 4개 테스트 단계 중 2개에서 더 일관된 성과를 보인다는 결론을 내렸다. 이 연구가 다른 소프트웨어 품질 평가 연구와 다른 점은 첫째, 여기서 관심 있는 종속 변수는 다양한 테스트 단계를 빠져나가 소프트웨어 테스트 후반에 시정조치(재작업)를 트리거하는 결함 수이고, 둘째, 프로젝트 수준에서 여러 독립 변수(즉 작업 상태, 테스트 진행 상태, 결함 유입 등을 나타내는 변수)를 사용한다.
2010년 Lindlar et al.
Lindlar 등은 테스트 케이스 평가를 위해 실제 전자 제어 장치를 사용하여 진화적 기능 테스트(evolutionary functional testing)를 수행하는 접근 방식을 제시하였다. 대규모 산업 시스템에 사용하도록 설계된 테스트 환경에서 광범위한 사례 연구를 수행하여 그 역량을 평가했다. 연구 결과에 따르면 논문에서 제안된 접근 방식이 Hardware-in-the-Loop 테스트 환경 내에서 임베디드 제어 시스템의 자동화된 기능 테스트에 적합한 것으로 나타났다.
2010년 De-Souza et al.
De-Souza 등은 검색 기반 소프트웨어 엔지니어링(SBSE)의 인간 경쟁력(human competitiveness)에 대한 포괄적인 실험 연구를 보고하였다. 이 실험은 4가지의 잘 알려진 SBSE 문제(즉 차기 릴리스 문제, 다목적 차기 릴리스 문제, 워크그룹 형성 문제, 다목적 테스트 케이스 선택 문제)에 대해 수행되었다. 이러한 각 문제에 대해 점점 크기가 커지는 두 인스턴스가 생성되고, 메타 휴리스틱과 인간 피험자가 이를 해결한다. 연구자들은 63명의 전문 소프트웨어 엔지니어가 일부 또는 모든 문제 인스턴스를 해결하고 함께 128개의 응답을 생성하는 실험을 수행하였다. 이 비교 분석은 검색 기반 소프트웨어 테스트에서 생성된 결과가 인간 경쟁력이 있다고 할 수 있음을 강력히 시사한다.
2011년 Romano et al.
Romano 등이 제안한 검색 기반 테스트 데이터 생성 접근 방식에서는 NPE(NullPointerException) 식별이 이루어진다. 이 접근 방식은 두 단계로 구성된다. (i) 기존 기술에 의존하는 절차 간 데이터 및 제어 흐름 분석으로 입력 매개변수와 잠재적 NPE 간의 경로를 식별하고, (ii) 이러한 경로를 커버하는 것을 목표로 테스트 데이터 모집단을 진화시키는 유전 알고리즘이 적용된다. 이 알고리즘은 임의의 데이터 구조를 포함하는 복잡한 입력을 처리할 수 있다. 논문 [12]에 제안된 접근 방식은 NPE 버그가 인위적으로 도입된 6개의 Java 오픈 소스 시스템의 클래스 클러스터를 테스트하여 평가되었다. 결과에 따르면 이 접근 방식은 실제로 NPE 버그를 식별할 수 있으며 무작위 테스트보다 성능이 우수하다. 또한 이 접근 방식이 Apache 라이브러리의 버그 추적 시스템에 게시된 일부 실제 NPE 버그를 어떻게 식별할 수 있는지 보여준다.
2011년 Yano et al.
Yano 등은 MOST라는 확장된 유한 상태 머신(extended finite state machines: EFSM)에서 테스트 케이스를 생성하는 다목적 진화적 접근 방식을 소개한다. EFSM에서 테스트하는 것은 일반적으로 주어진 커버리지 기준이 충족될 때까지 다양한 전이 경로(transition paths)를 실행하는 것을 말한다. FSM의 기존 테스트 생성 방법은 오로지 제어 측면만 고려하므로 경로에서 가드 조건(guard conditions)의 충돌로 인해 EFSM에 적용할 때 많은 실행 불가능한 경로(infeasible paths)를 생성할 수 있다.
참고 문헌
[1] P. McMinn, “Search-based software test data generation: A survey,” Journal of Software Testing Verification and Reliability, pp. 105-156, June, 2004.
[2] W. Afzal, R. Torkar and R. Feldt, “A systematic review of search based testing for non-functional system properties,” Journal of Information and Software Technology, vol. 51, 2009.
[3] G. Antoniol, “Search Based Software Testing for Software Security: Breaking Code to Make it,” in Proceedings of the International Conference on Software Testing Verification and Validation Workshops, pp 87- 100, 2009.
[4] K. Scarfone, M. Souppaya, A. Cody, and A. Orebaugh, “Technical guide to information security testing and assessment,” U.S. Dept. Of Commerce - National Institute of Standards and Technology, Technical Report, pp. 800-811, September 2008.
[5] R. Blanco, J. Tuya, B. Adenso-Díaz, “Automated test data generation using a scatter search approach”, Journal of Information and Software Technology, vol. 51, pp.708-720,2008.
[6] A. Windisch and N.A.Moubayed, “Signal Generation for Search-Based Testing of Continuous Systems,” in Proceedings of IEEE International Conference on Software Testing Verification and Validation, pp 121- 130, 2009.
[7] X. Yuan and A. M. Memon, “Using GUI run-time state as feedback to generate test cases,” in Proceedings of the 29th International Conference on Software Engineering, Washington, DC, USA, May 23–25, pp. 396–405, 2007.
[8] A.Marchetto and P.Tonella,“Search-Based Testing of AjaxWeb Applications,” in Proceedings of IEEE International Symposium on Search Based Software Engineering, pp 3-12, 2009.
[9] S.Li, N.Bian, Z.Chen, D.You, Y.He, “A Simulation Study on Some Search Algorithms for Regression Test Case Prioritization” 10th IEEE International Conference on Quality Software, pp 72-81, 2010.
[10] W.Afzal, R.Torkar and R.Feldt,“Search-based prediction of fault-slip-through in large software projects”, 2nd IEEE International Symposium on Search Based Software Engineering, pp 79-88, 2010.
[11] J.T. De-Souza, C. L. Maia, F. G. De-Freitas and D.P. Coutinho, “The Human Competitiveness of Search Based Software Engineering,” 2nd IEEE International Symposium on Search Based Software Engineering, pp 143-152, 2010.
[12] D. Romano, M. Di Penta, G.Antoniol,“An Approach for Search Based Testing of Null Pointer Exceptions,” Fourth IEEE International Conference on Software Testing, Verification and Validation, pp 160-169, 2011.