동적 테인트 분석을 활용한 효과적인 동적 기호 실행 탐색 전략

Abstract

Concolic 테스팅은 대상 프로그램의 모든 경로를 탐색하는 것을 목표로 테스트 케이스를 생성하는 소프트웨어 자동화 테스팅 기법이다. 하지만 프로그램의 모든 경로를 탐색하는 것은 많은 비용이 들기 때문에, 분기 커버리지를 높이 달성할 수 있는 가장 유망한 경로부터 먼저 살펴보는 것이 중요하다. 어떤 경로부터 탐색할지 결정하는 전략을 Concolic 탐색 전략이라고 부른다. 기존의 Concolic 탐색 전략들(DFS, rev-DFS, CFG, random)은 대상 프로그램에 있는 함수들 간의 데이터 의존도를 고려하지 않고 방문할 분기를 결정하기 때문에 분기 커버리지가 낮게 나오는 경우가 있다. 본 연구는 동적 테인트 분석을 통해 함수 간 데이터 의존도를 함수 간 데이터 흐름을 기반으로 정의하고 함수 간 데이터 의존도를 바탕으로 새로운 concolic 탐색 전략 Taint를 설계하였다. Taint는 타겟 함수 g의 커버하지 못한 분기를 커버하고자 할 때, 함수 f에 대한 함수 g의 데이터 의존도가 높은 경우(즉, 함수 f에서 함수 g로 변수의 값들을 많이 보내고), 함수 f의 분기를 부정하거나 함수 g의 분기를 부정해서 함수 g에서 커버하지 못한 분기를 커버하도록 하는 휴리스틱이다. 이러한 접근 방식은 함수 f가 함수 g로 보낸 변수의 값들이 함수 g의 실행 경로를 결정한다는 직관에서 비롯된다. 또한, 함수 간 데이터 의존도를 계산할 때, 고려해야 할 여러 가지 요소들 중에서 3가지 요소들을 고려하였다. 동적 테인트 분석은 함수 간 데이터 의존도의 측정에 기반이 되는 함수 간 데이터 흐름을 추출하기 위해 사용되었다. Taint는 기존의 Concolic 탐색 전략들을 사용했을 때보다 1.2%p~7.1%p 더 높은 분기 커버리지를 달성할 수 있다.