An Approach to Identifying Structural Similarity of Control Flow Graphs of Software
Hyun-il Lim · Journal of Digital Contents Society · 2020
제어 흐름 그래프는 소프트웨어의 특성을 나타내기 위한 기본적인 데이터 구조이다. 소프트웨어의 특성을 분석하는 것은 소프트웨어 개발 및 소프트웨어 표절 탐지 또는 악성 프로그램 탐지 등 다양한 응용 분야에 유용하게 활용되고 있다. 본 논문에서는 소프트웨어 분석 방법으로 제어 흐름 그래프의 구조적 유사성을 계산하기 위해 기본 블록의 분석과 에지의 연결 관계를 반영하는 방법을 제안한다. 제어 흐름 그래프의 구조는 기본 블록과 에지의 관계를 통해 표현되기 때문에 기본 블록의 특성과 에지의 관계를 분석하고 두 제어 흐름 그래프에서 구조적으로 유사한 기본 블록의 매칭을 찾는 방법을 적용한다. 매치된 기본 블록의 관계로 부터 두 제어 흐름 그래프 사이의 구조적 유사성을 계산한다. 본 논문의 구조적 유사성 비교 방법을 평가하기 위해 서로 다른 실행 구조를 가진 자바 프로그램을 대상으로 실험을 수행하였다. 실험 결과에서 본 논문에서 제안한 방법은 소프트웨어의 구조적 특성에 따라 구조적 유사성을 비교하는 데 효과적으로 적용될 수 있음을 확인할 수 있었다.