Concolic testing is a software automated testing with the goal of visiting all the paths of the target program. Since exploring all the paths of a program is expensive, it is important to look at the most promising paths first to achieve high branch coverage. The strategy that determines which path to visit is called concolic search strategy. Conventional concolic search strategies (e.g., DFS, rev-DFS, CFG, random) sometimes have low branch coverage because they decide which path to visit without considering the correlation between functions in the target program.
In this paper, we defined data dependency between functions based on the data flow between functions through dynamic taint analysis and designed a new concolic search strategy called Taint based on data dependency between functions. If target function g has an uncovered branch that needs to be covered and function g has a high data dependency on function f (i.e., function f sends many values of variables to function g), Taint guides concolic testing to negate the branch in function f or function g to cover the uncovered branch in function g. This approach stems from the intuition that the values of variables that function f sends to function g determine the execution path of function g. Three design choices were taken into account when measuring the data dependency between functions. Dynamic taint analysis is used to extract def-use chains between functions and measure data dependency between functions. Taint can achieve 1.2%p~7.1%p higher branch coverage than using conventional concolic search strategies.
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 더 높은 분기 커버리지를 달성할 수 있다.
