본 논문에서는 스택 사용 패턴을 기반으로 소프트웨어 유사도를 분석하는 기법을 제안한다. 스택은 함수가 수행될 때 사용하는 인자와 지역 변수를 관리하는 메모리 공간이다. 따라서 스택 사용 패턴을 분석하면, 소프트웨어가 어떤 함수들을 어떤 방식으로 사용하는지 유추할 수 있으며, 이를 통해 소프트웨어의 유사성을 분석할 수 있다. 제안된 기법은 함수 호출 그래프 생성기, 스택 사용 패턴 분석기, 그리고 유사도 비교 측정기로 구성된다. 함수 호출 그래프 생성기는 call과 return 명령어를 분석하여 함수 호출 그래프를 생성하며, 스택 사용 패턴 분석기는 함수 호출시 사용하는 스택 프레임의 변화를 기반으로 스택 크기의 변화를 모니터링 한다. 마지막으로 유사도 비교 측정기는 LCS (Longest Common Subsequence)를 사용하여 두 개의 스택 사용 패턴 간에 유사도를 비교한다. 5개의 실제 소프트웨어를 기반으로 한 실험 결과 제안 기법이 유사도를 적절하게 분석하는 것으로 관찰되었다.
In this paper, we propose a novel software similarity analysis scheme which is based on the stack usage pattern. Stack is a memory area used for maintaining arguments and local variables during the execution of a function. Hence, by investigating the stack usage pattern, we can infer how a program makes use of functions and what their relations are, which gives an opportunity to analyze the software similarity. The proposed scheme consists of three components, namely, function call graph generator, stack usage pattern investigator, and similarity comparator. The generator constructs the function call graph by examining the call and return instructions in a binary, while the investigator monitors the changes of stack by checking the alteration of stack frames during function invocations. Finally, the comparator evaluates the similarity between two stack usage patterns by applying the LCS (Longest Common Subsequence) algorithm. Experimental results with real 5 applications have shown that the proposed scheme can analyze the similarity effectively.
