본 논문에서는 바이너리 프로그램의 정적인 구조를 표현하는 제어 흐름 그래프를 비교하는 방법을 제안한다. 제어 흐름 그래프를 비교하기 위해서 기본 블록에 포함된 프로그램의 명령어 및 구문 정보를 비교한 후 기본 블록 사이의 유사한 정도를 측정한다. 또한, 에지 확장을 통해 기본 블록들 간의 제어 흐름을 표현하는 그래프 에지의 유사성을 함께 반영한다. 각 기본 블록 사이의 유사도 결과를 기반으로 기본 블록을 서로 매칭하고, 기본 블록 사이의 매칭 정보를 이용해서 전체 제어 흐름 그래프의 유사도를 측정한다. 본 논문에서 제안한 방법은 자바 프로그램으로부터 추출한 제어 흐름 그래프를 대상으로 제어 흐름 구조의 유사성에 따라 두 가지 기준으로 실험을 수행하였다. 그리고, 성능을 평가하기 위해서 기존의 구조적 비교 방법을 함께 실험하였다. 실험 결과로부터 에지 확장 방법은 서로 다른 프로그램에 대해 충분한 변별력을 가지고 있음을 확인할 수 있다. 프로그램 비교에 좀 더 많은 시간이 소요되지만, 구조가 유사한 프로그램에 대한 매칭 능력에서 기존의 구조적 비교 방법에 비해 우수한 결과를 보였다. 제어 흐름 그래프는 프로그램의 분석에 다양하게 활용될 수 있으며, 제어 흐름 그래프의 비교 방법은 프로그램의 유사성 비교를 통한 코드의 최적화, 유사 코드 검출, 코드의 도용 탐지 등 다양한 분야에서 응용될 수 있을 것이라 기대된다.
본 논문에서는 바이너리 프로그램의 정적인 구조를 표현하는 제어 흐름 그래프를 비교하는 방법을 제안한다. 제어 흐름 그래프를 비교하기 위해서 기본 블록에 포함된 프로그램의 명령어 및 구문 정보를 비교한 후 기본 블록 사이의 유사한 정도를 측정한다. 또한, 에지 확장을 통해 기본 블록들 간의 제어 흐름을 표현하는 그래프 에지의 유사성을 함께 반영한다. 각 기본 블록 사이의 유사도 결과를 기반으로 기본 블록을 서로 매칭하고, 기본 블록 사이의 매칭 정보를 이용해서 전체 제어 흐름 그래프의 유사도를 측정한다. 본 논문에서 제안한 방법은 자바 프로그램으로부터 추출한 제어 흐름 그래프를 대상으로 제어 흐름 구조의 유사성에 따라 두 가지 기준으로 실험을 수행하였다. 그리고, 성능을 평가하기 위해서 기존의 구조적 비교 방법을 함께 실험하였다. 실험 결과로부터 에지 확장 방법은 서로 다른 프로그램에 대해 충분한 변별력을 가지고 있음을 확인할 수 있다. 프로그램 비교에 좀 더 많은 시간이 소요되지만, 구조가 유사한 프로그램에 대한 매칭 능력에서 기존의 구조적 비교 방법에 비해 우수한 결과를 보였다. 제어 흐름 그래프는 프로그램의 분석에 다양하게 활용될 수 있으며, 제어 흐름 그래프의 비교 방법은 프로그램의 유사성 비교를 통한 코드의 최적화, 유사 코드 검출, 코드의 도용 탐지 등 다양한 분야에서 응용될 수 있을 것이라 기대된다.
In this paper, we present an effective method for comparing control flow graphs which represent static structures of binary programs. To compare control flow graphs, we measure similarities by comparing instructions and syntactic information contained in basic blocks. In addition, we also consider s...
In this paper, we present an effective method for comparing control flow graphs which represent static structures of binary programs. To compare control flow graphs, we measure similarities by comparing instructions and syntactic information contained in basic blocks. In addition, we also consider similarities of edges, which represent control flows between basic blocks, by edge extension. Based on the comparison results of basic blocks and edges, we match most similar basic blocks in two control flow graphs, and then calculate the similarity between control flow graphs. We evaluate the proposed edge extension method in real world Java programs with respect to structural similarities of their control flow graphs. To compare the performance of the proposed method, we also performed experiments with a previous structural comparison for control flow graphs. From the experimental results, the proposed method is evaluated to have enough distinction ability between control flow graphs which have different structural characteristics. Although the method takes more time than previous method, it is evaluated to be more resilient than previous method in comparing control flow graphs which have similar structural characteristics. Control flow graph can be effectively used in program analysis and understanding, and the proposed method is expected to be applied to various areas, such as code optimization, detection of similar code, and detection of code plagiarism.
In this paper, we present an effective method for comparing control flow graphs which represent static structures of binary programs. To compare control flow graphs, we measure similarities by comparing instructions and syntactic information contained in basic blocks. In addition, we also consider similarities of edges, which represent control flows between basic blocks, by edge extension. Based on the comparison results of basic blocks and edges, we match most similar basic blocks in two control flow graphs, and then calculate the similarity between control flow graphs. We evaluate the proposed edge extension method in real world Java programs with respect to structural similarities of their control flow graphs. To compare the performance of the proposed method, we also performed experiments with a previous structural comparison for control flow graphs. From the experimental results, the proposed method is evaluated to have enough distinction ability between control flow graphs which have different structural characteristics. Although the method takes more time than previous method, it is evaluated to be more resilient than previous method in comparing control flow graphs which have similar structural characteristics. Control flow graph can be effectively used in program analysis and understanding, and the proposed method is expected to be applied to various areas, such as code optimization, detection of similar code, and detection of code plagiarism.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 바이너리 프로그램의 제어 흐름 그래프사이에 유사도를 검출하기 위해서 우선 기본 블록간의 유사한 정도를 측정한다. 기본 블록 간의 유사성은 에지 확장을 통해 블록 간의 변별력을 크게 가질 수 있다.
이 수식을 통해 비교한 결과는 하나의 기본 블록에 대해서 그 블록의 실행 전후에 실행되는 기본 블록들에 동일한 구문이 얼마나 많이 포함되어 있는가를 측정한다. 기본 블록의 유사한 정도를 측정하기 위해서 그 연속적으로 실행되는 블록을 비교한 결과를 함께 고려할 수 있도록 에지를 확장한 것이다. 이는 제어 흐름 그래프 상에서 기본 블록 간의 선후 관계를 반영할 수 있고, 제어 흐름 그래프의 비교에 프로그램의 실행 절차를 반영할 수 있다.
본 논문에서 제안한 비교 방법과 기존의 구조적 비교 방법 [12, 13]을 이용해서 총 19,306 쌍에 대한 비교를 수행하였으면 결과를 분석하였다. 본 실험은 다른 제어 흐름 그래프 사이의 비교 결과에서 얼마나 변별력 있는 유사도 결과를 보여주는지 평가한다. 그래서 서로 다른 제어 흐름 그래프라면 충분히 낮은 유사도 분포를 보이는 것이 효과적이다.
본 실험은 서로 유사한 구조를 가진 제어 흐름 그래프를 비교할 때 높은 유사도를 결과로 보일 수 있는지를 평가한다. 실험을 위해서 유사한 구조의 프로그램은 원본 프로그램을 변형한 프로그램을 고려하였으며, 난독화 도구인 Smokescreen [14]과 Zelix KlassMaster(ZKM) [15]를 사용 하였다.
본 논문에서는 바이너리 프로그램의 제어 흐름 그래프를 비교하기 위해서 기본 블록의 유사도와 더불어 에지 확장을 통해 제어 흐름 그래프의 구조적인 특성을 비교한다. 각 기본 블록들은 서로간의 유사성 순서에 따라 매칭함으로써 전체 제어 흐름 그래프 사이의 매칭 관계를 확인하고 유사도를 구할 수 있다.
프로그램의 제어 흐름 그래프는 프로그램의 정적인 구조와 동작 특성을 효과적으로 기술할 수 있기 때문에 정적 분석과 동적 분석 등에서 광범위하게 사용되고 있다. 본 논문에서는 바이너리 프로그램의 구조를 표현하는 제어 흐름 그래프를 비교하는 방법을 제안하였다.
그래서, 프로그램의 특성을 이해하고 분석 정보를 활용하기 위해서 정적 분석, 동적 분석 등에서 광범위하게 사용되고 있다. 본 논문에서는 프로그램의 유사성을 판단하기 위해서 제어 흐름 그래프의 에지 확장을 통해 효과적으로 구조를 비교하는 방법을 제안한다. 제어 흐름 그래프의 비교를 위해서 그래프를 구성하는 기본 블록(basic block)들의 특성을 비교하는 방법을 사용하고 있다.
가설 설정
1에서는 두 개의 제어 흐름 그래프에서 각각 기본 블록 A와 B를 보여주고 있으며, A와 B는 연결된 에지를 통해 제어 흐름으로 연결된 기본 블록간의 관계를 보여주고 있다. 각각의 기본 블록 내에 표기된 알파벳 소문자는 기본 블록을 구성하는 프로그램 명령어를 나타낸다고 가정한다. 본 예제에서 기본 블록 A에는 3개의 명령 구문 {f, g, h}가 포함되어 있고, 기본 블록 B에는 명령 구문 {f, h, b}가 포함되어 있다.
제안 방법
본 논문에서 제안하는 에지 확장 방법은 자바로 구현한 프로그램을 대상으로 두 가지 평가 기준에 따라 실험을 수행한다. 성능을 평가하기 위해서 기존의 구조적 비교 방법[12, 13]을 함께 실험하고 성능을 비교한다.
Falke [12]와 Dullien 등 [13]은 부분적인 업데이트가 적용된 바이너리 프로그램의 차이를 비교하는 구조적 비교 방법을 제안하였다. 이 방법은 제어 흐름 그래프의 노드와 에지가 가지는 특성 정보를 비교하고 반복적으로 매칭함으로써 원본 프로그램과 수정된 프로그램의 차이를 분석하는 방법을 제안한다. 이 방법은 부분적으로 수정된 바이너리 프로그램의 비교에서 효과적인 매칭 결과를 보여준다.
기본 블록의 유사성을 비교하기 위해서 기본 블록에 포함되어 있는 명령어 및 구문 정보들을 비교한다. 기본 블록의 비교는 기본 블록이 가지는 구문 정보들을 원소로 하는 집합에 대해서 두 기본 블록에 대한 전체 집합에서 동일한 원소를 나타내는 교집합의 크기가 얼마나 큰지를 평가하는 방법을 적용한다.
기본 블록의 유사성을 비교하기 위해서 기본 블록에 포함되어 있는 명령어 및 구문 정보들을 비교한다. 기본 블록의 비교는 기본 블록이 가지는 구문 정보들을 원소로 하는 집합에 대해서 두 기본 블록에 대한 전체 집합에서 동일한 원소를 나타내는 교집합의 크기가 얼마나 큰지를 평가하는 방법을 적용한다.
나가는 에지에 대한 유사성은 이 에지를 통해서 도달하는 기본 블록들이 여러 개 있을 때, 이 기본 블록들에 포함된 명령어 및 구문 정보들의 유사성을 비교한다. 이 비교 결과는 단순히 하나의 에지만을 비교한 결과라기보다는 기본 블록을 중심으로 한 에지들의 유사성을 비교함으로써 기본 블록이 제어 흐름 그래프 상에서 독립된 원소가 아니고 전체 구조에서의 위치를 확인하고 유사한 블록을 신뢰성 있게 매칭하는 데 중요한 정보가 된다.
이 수식을 통해 비교한 결과는 하나의 기본 블록에 대해서 그 블록의 실행 전후에 실행되는 기본 블록들에 동일한 구문이 얼마나 많이 포함되어 있는가를 측정한다. 기본 블록의 유사한 정도를 측정하기 위해서 그 연속적으로 실행되는 블록을 비교한 결과를 함께 고려할 수 있도록 에지를 확장한 것이다.
본 논문에서는 기본 블록의 비교와 에지 확장의 비율을 동일하게 평가하고 α=2, β=γ=1로 설정하였다.
앞 절에서 제어 흐름 그래프를 구성하는 각 기본 블록들 사이에 유사도를 측정할 수 있는 방법을 제안하였다. 이 측정값들은 전체적으로 두 제어 흐름 그래프 사이에 유사한 기본 블록들의 분포 여부를 효과적으로 판단할 수 있는 근거를 제공한다.
본 절에서는 본 논문에서 제안한 방법의 성능을 평가하기 위한 실험 결과를 보여준다. 성능 평가 실험을 위해서 제어 흐름 그래프를 분석하고 비교하는 방법은 C언어와 파이썬[11]으로 구현하였다. 실험 대상 프로그램은 바이너리 프로그램으로서 자바로 구현된 프로그램의 클래스 파일에 포함된 바이트코드에 대한 제어 흐름 그래프를 대상으로 하였다.
기존의 구조적 비교 방법은 제어 흐름 그래프의 구조적 특성을 이용해서 기본 블록을 매칭하는 방법이다. 기본 블록의 매칭을 위해 기본 블록의 indegree, outdegree, 함수 호출 정보, 기본 블록의 재귀적 특성, 시작지점에서 최단 거리, 종료 지점까지 최단 거리 등의 특성 등을 시그너처 정보로 비교하고 최적의 매칭 블록을 찾으며, 이런 과정은 고정점을 찾을 때까지 반복적으로 수행된다.
즉, 서로 구조가 유사한 프로그램을 비교한 경우에는 높은 유사도 결과를 줄 수 있어야 하며, 유사하지 않은 프로그램을 비교한 경우에는 상대적으로 낮은 유사도를 보여야 한다. 이 두 가지 기준을 평가하기 위해서 구조가 서로 유사하지 않은 프로그램을 비교한 실험과 서로 유사한 프로그램을 비교한 실험을 각각 수행하였다.
에지 확장에서 높은 유사도를 보인 비교 대상에 대해서 원인을 찾기 위해서 프로그램을 직접 분석하였다. 비교 대상 프로그램의 제어 흐름 그래프에는 Apache Derby에 있는 SQLParserTokenManager.
수행 시간은 각각의 비교 방법으로 전체 대상 프로그램을 비교하는데 걸린 시간을 측정하였다. 기존의 구조적 비교방법은 19,306쌍의 제어 흐름 그래프를 비교하는데 5,598초가 걸렸으며, 에지 확장 방법의 경우 동일한 실험에서 6,155초가 걸렸다.
따라서 변환된 프로그램은 원본 프로그램의 기본 골격은 유지하지만 내부적인 구성이 달라진다. 본 실험에서는 Table 2에서 제시한 실험 대상 프로그램에 대해서 두 가지 난독화 도구를 이용해서 변환하고, 원본과 변환된 제어 흐름 그래프를 비교하는 실험을 수행한다.
Table 4는 서로 유사한 구조를 가지는 프로그램의 비교 실험 결과를 보여주고 있다. Smokescreen과 ZKM으로 변환 한 프로그램에 대해서 각각 비교하였으며, 성능 평가를 위해서 기존의 구조적 비교 방법도 함께 실험하였다. Smokescreen을 이용해 변환한 프로그램의 비교 실험에서 에지 확장 방법의 유사도는 최소 49.
이 유사도 값을 평균적으로 반영하기 위해서 가중치 비율을 α=β+γ로 실험을 수행하였다.
그래프 구조를 비교하기 위해서는 그래프를 구성하는 두 가지 원소인 기본 블록과 에지의 비교 결과를 적절히 조율할 필요가 있다. 본 논문에서는 기본 블록의 유사성을 비교하기 위해서 두 기본 블록 사이의 유사도 m()과 에지 확장을 반영하는 유사도 m1(), m2()를 함께 반영하고 있다. 이 유사도 값을 평균적으로 반영하기 위해서 가중치 비율을 α=β+γ로 실험을 수행하였다.
본 논문에서는 제어 흐름 그래프의 비교를 위해서 그래프를 구성하는 기본 블록들이 가지는 내부 정보를 비교하는 방법을 사용하고 있다. 기본 블록에 포함된 프로그램의 명령어나 구문 정보를 비교함으로써 기본 블록 사이의 유사성을 확인할 수 있다.
기본 블록에 포함된 프로그램의 명령어나 구문 정보를 비교함으로써 기본 블록 사이의 유사성을 확인할 수 있다. 또한, 기본 블록 사이에 제어 흐름을 표현하는 에지의 정보를 반영하기 위해서 에지 확장 방법을 제안하였다. 에지 확장은 기본 블록을 매칭할 때 들어가는 에지와 나가는 에지로 인접한 기본 블록들의 관계를 함께 고려함으로써 프로그램의 수정에 강인한 제어 구조를 반영할 수 있다.
본 논문에서 제안한 방법의 성능을 평가하기 위해서 자바프로그램으로부터 추출한 제어 흐름 그래프를 대상으로 실험을 하였다. 실험은 구조의 유사성에 따라 두 가지 기준으로 실험을 수행하였으며, 비교를 위해서 기존의 구조적 비교 방법을 함께 실험하였다. 기존의 구조적 비교 방법은 서로 다른 프로그램에 대한 변별력은 매우 우수하였지만, 서로 유사한 프로그램에 비교는 충분한 신뢰성을 가지지 못하였다.
대상 데이터
성능 평가 실험을 위해서 제어 흐름 그래프를 분석하고 비교하는 방법은 C언어와 파이썬[11]으로 구현하였다. 실험 대상 프로그램은 바이너리 프로그램으로서 자바로 구현된 프로그램의 클래스 파일에 포함된 바이트코드에 대한 제어 흐름 그래프를 대상으로 하였다.
Table 2에서 본 실험에서 비교 대상으로 사용한 벤치마크 프로그램의 정보를 보여주고 있다. 대상 프로그램은 자바로 구현된 데이터베이스 프로그램인 Apache Derby, Mckoi SQL Database, SmallSQL Database를 이용하였다. 실험의 신뢰성을 높이기 위해서 대상 프로그램에서 추출한 제어 흐름 그래프 중에서 에지와 기본 블록의 개수가 모두 40개 이상인 197개의 제어 흐름 그래프를 대상으로 하였으며, 에지와 기본 블록의 평균값은 122개와 91개, 최대값은 각각 590개와 506개이다.
대상 프로그램은 자바로 구현된 데이터베이스 프로그램인 Apache Derby, Mckoi SQL Database, SmallSQL Database를 이용하였다. 실험의 신뢰성을 높이기 위해서 대상 프로그램에서 추출한 제어 흐름 그래프 중에서 에지와 기본 블록의 개수가 모두 40개 이상인 197개의 제어 흐름 그래프를 대상으로 하였으며, 에지와 기본 블록의 평균값은 122개와 91개, 최대값은 각각 590개와 506개이다.
서로 다른 구조를 가진 제어 흐름 그래프를 비교하기 위해서 실험 대상이 되는 197개의 제어 흐름 그래프를 각각 서로 비교하였다. 본 논문에서 제안한 비교 방법과 기존의 구조적 비교 방법 [12, 13]을 이용해서 총 19,306 쌍에 대한 비교를 수행하였으면 결과를 분석하였다.
수행 시간은 각각의 실험에서 총 197쌍의 유사한 구조를 가진 제어 흐름 그래프를 비교하는데 걸린 총 소요 시간을 측정하였다. 기존의 구조적 비교 방법은 Smokescreen과 ZKM을 이용한 실험에서 각각 63초와 79초가 걸렸으며, 에지 확장 방법은 118초와 141초가 걸려서 2배 정도 많은 시간이 걸렸다.
본 논문에서 제안한 방법의 성능을 평가하기 위해서 자바프로그램으로부터 추출한 제어 흐름 그래프를 대상으로 실험을 하였다. 실험은 구조의 유사성에 따라 두 가지 기준으로 실험을 수행하였으며, 비교를 위해서 기존의 구조적 비교 방법을 함께 실험하였다.
데이터처리
에지 확장 방법의 성능을 평가하기 위해서 기존의 제어 흐름 그래프 구조적 비교 방법 [12, 13]을 함께 구현하고 실험 결과를 비교하였다. 기존의 구조적 비교 방법은 제어 흐름 그래프의 구조적 특성을 이용해서 기본 블록을 매칭하는 방법이다.
서로 다른 구조를 가진 제어 흐름 그래프를 비교하기 위해서 실험 대상이 되는 197개의 제어 흐름 그래프를 각각 서로 비교하였다. 본 논문에서 제안한 비교 방법과 기존의 구조적 비교 방법 [12, 13]을 이용해서 총 19,306 쌍에 대한 비교를 수행하였으면 결과를 분석하였다. 본 실험은 다른 제어 흐름 그래프 사이의 비교 결과에서 얼마나 변별력 있는 유사도 결과를 보여주는지 평가한다.
이론/모형
본 논문에서 제안하는 에지 확장 방법은 자바로 구현한 프로그램을 대상으로 두 가지 평가 기준에 따라 실험을 수행한다. 성능을 평가하기 위해서 기존의 구조적 비교 방법[12, 13]을 함께 실험하고 성능을 비교한다. 실험 결과를 통해서 본 논문에서 제안한 방법이 유사한 구조를 가진 수정된 프로그램의 비교에서 기존의 방법에 비해 효과적인 결과를 보인다는 것을 확인할 수 있다.
본 실험은 서로 유사한 구조를 가진 제어 흐름 그래프를 비교할 때 높은 유사도를 결과로 보일 수 있는지를 평가한다. 실험을 위해서 유사한 구조의 프로그램은 원본 프로그램을 변형한 프로그램을 고려하였으며, 난독화 도구인 Smokescreen [14]과 Zelix KlassMaster(ZKM) [15]를 사용 하였다. 이 도구는 원본 프로그램에 대해서 실행 결과는 동일하지만 역분석이 어렵고 디컴파일이 안되도록 프로그램으로 변환하는 역할을 한다.
성능/효과
성능을 평가하기 위해서 기존의 구조적 비교 방법[12, 13]을 함께 실험하고 성능을 비교한다. 실험 결과를 통해서 본 논문에서 제안한 방법이 유사한 구조를 가진 수정된 프로그램의 비교에서 기존의 방법에 비해 효과적인 결과를 보인다는 것을 확인할 수 있다.
기본 블록의 매칭은 서로 유사하다고 평가되는 블록들을 순서대로 매칭하게 된다. 본 논문에서 제안한 방법은 다양한 형태 또는 임의로 수정된 제어 흐름 그래프에 대해서 기존의 구조적 비교 방법 [12, 13]보다 광범위하게 적용할 수 있다.
제어 흐름 그래프를 비교할 때, 기본 블록의 제어 흐름을 나타내는 에지의 유사성을 함께 고려한 다면 보다 신뢰성 있는 비교 결과를 얻을 수 있을 것이다. 이를 위해서 제어 흐름 그래프의 기본 블록이 가지는 에지의 비교 결과를 확장함으로써 효과적으로 비교할 수 있다.
Table 3은 본 실험의 결과를 요약해서 보여준다. 에지 확장 비교 방법은 총 비교 결과 나타나는 유사도가 최소 0.0% 에서 100.0% 사이에 분포했으며, 평균 11.1%의 유사도를 보였다. 기존의 구조적 비교 방법은 비교 결과 유사도가 0.
1%의 유사도를 보였다. 기존의 구조적 비교 방법은 비교 결과 유사도가 0.0% 에서 최대 89.4%까지 범위에 분포하였으며 평균 유사도는 0.8% 였다. 본 실험 결과에서 나타나는 실험 결과를 볼 때 기존의 구조적 비교 방법이 에지 확장 방법 보다 낮은 유사도 분포를 보임으로써 서로 다른 프로그램에 대한 변별력이 우수한 것으로 평가된다.
8% 였다. 본 실험 결과에서 나타나는 실험 결과를 볼 때 기존의 구조적 비교 방법이 에지 확장 방법 보다 낮은 유사도 분포를 보임으로써 서로 다른 프로그램에 대한 변별력이 우수한 것으로 평가된다.
이 프로그램은 개발자가 직접 작성한 코드가 아니고, SQL 구문을 파싱하기 위해서 파서 생성기인 JavaCC를 이용해서 자동 생성된 SQL 파서 프로그램이었다. JavaCC의 코드 생성 패턴의 유사성 때문에 유사한 형태의 제어 흐름 그래프를 포함하는 코드로 생성되었고, 에지 확장을 이용한 방법에서 높은 유사도를 보였던 것이다. 기존의 구조적 방법에서 또한 80% 이상의 높은 기본 블록 매칭을 보이기도 하였다.
기존의 구조적 방법에서 또한 80% 이상의 높은 기본 블록 매칭을 보이기도 하였다. 따라서 에지 확장을 이용한 방법에서 높은 유사도를 보인 비교 대상은 실제로 유사한 구조를 가진 제어 흐름 그래프로 분석되었고, 전체 평균 유사도 11.1%로써 서로 다른 프로그램을 구분하기에 충분히 낮은 유사도 값을 보이는 것으로 평가된다.
낮은 유사도 구간에서 많은 비교 결과가 위치할수록 다른 프로그램에 대한 변별력이 우수 하다고 평가할 수 있다. 결과에서 기존의 구조적 비교 방법은 대부분의 비교 결과가 10% 미만의 구간에 위치하고있으며 변별력이 아주 우수한 것으로 평가된다. 상대적으로 에지 확장 방법은 높은 유사도 구간에 결과들이 위치하고 있지만, 대부분의 비교 결과는 30% 이하의 낮은 유사도 구간에 분포하고 있으며 서로 다른 프로그램임을 변별할 수 있음을 확인할 수 있다.
결과에서 기존의 구조적 비교 방법은 대부분의 비교 결과가 10% 미만의 구간에 위치하고있으며 변별력이 아주 우수한 것으로 평가된다. 상대적으로 에지 확장 방법은 높은 유사도 구간에 결과들이 위치하고 있지만, 대부분의 비교 결과는 30% 이하의 낮은 유사도 구간에 분포하고 있으며 서로 다른 프로그램임을 변별할 수 있음을 확인할 수 있다. 또한 70% 이상의 높은 유사도를 보이는 대부분의 제어 흐름 그래프는 JavaCC에 의해서 자동 생성된 프로그램의 제어 흐름 그래프의 비교 결과인 것으로 확인되었다.
상대적으로 에지 확장 방법은 높은 유사도 구간에 결과들이 위치하고 있지만, 대부분의 비교 결과는 30% 이하의 낮은 유사도 구간에 분포하고 있으며 서로 다른 프로그램임을 변별할 수 있음을 확인할 수 있다. 또한 70% 이상의 높은 유사도를 보이는 대부분의 제어 흐름 그래프는 JavaCC에 의해서 자동 생성된 프로그램의 제어 흐름 그래프의 비교 결과인 것으로 확인되었다.
서로 다른 프로그램에 대한 변별력에서 기존의 구조적 비교 방법은 기본 블록의 시그너쳐 정보가 다르면 기본 블록의 매칭 대상에서 배제되기 때문에 서로 다른 구조를 가진 경우 효과적인 결과를 보였다. 반면 에지 확장 방법은 서로 시그너처 정보가 다르더라도 명령어의 패턴에 일부분 유사성이 있다면 부분적인 매칭을 고려하기 때문에 상대적으로 높은 유사도 분포를 보인 것으로 보인다.
Smokescreen과 ZKM으로 변환 한 프로그램에 대해서 각각 비교하였으며, 성능 평가를 위해서 기존의 구조적 비교 방법도 함께 실험하였다. Smokescreen을 이용해 변환한 프로그램의 비교 실험에서 에지 확장 방법의 유사도는 최소 49.6%에서 100% 사이에 분포하고 있으며 평균 유사도는 92.9%로 과반수 이상이 90% 이상의 높은 유사도를 보이고 있음을 확인할 수 있다. 반면에 구조적 비교 방법은 최소 0.
3%의 유사도를 보이고 있다. ZKM으로 변환한 프로그램에 대한 실험 결과에서 에지 확장은 최소 23.3%의 유사도를 보였으며, 평균 77.1%의 유사도를 보임으로써 Smokescreen을 통한 비교 실험보다 유사도가 다소 낮아진 결과를 보이고 있다. 기존의 구조적 방법도 마찬가지로 유사도의 평균이 30.
4%로 Smokescreen에 비해서 낮아졌음을 확인할 수 있다. 본 실험 결과로부터 Smokescreen 이나 ZKM을 이용해 수정된 프로그램에 대해서 에지 확장을 적용한 방법이 기존의 구조적 비교 방법 보다 높은 유사도 값을 보이고 있으며, 구조적 유사성을 탐지하는데 보다 효과적임을 확인할 수 있다.
4는 본 실험 결과로 나온 결과의 유사도 범위별 분포 비율을 보여주고 있다. Smokescreen을 이용한 실험 결과에서 에지 확장 방법은 15% 정도의 결과는 100% 매칭 관계를 확인할 수 있었으며 80% 이상의 결과는 유사도가 90% 이상의 범위에 위치함으로써 매우 높은 유사도 분포를 확인할 수 있었다. 기존의 구조적 방법은 90% 이상 높은 유사도를 보인 결과는 상대적으로 적었으며, 35% 이상의 결과는 10% 이하의 낮은 유사도를 보임으로써 매칭이 효과적으로 이루어지지 않음을 알 수 있다.
Smokescreen을 이용한 실험 결과에서 에지 확장 방법은 15% 정도의 결과는 100% 매칭 관계를 확인할 수 있었으며 80% 이상의 결과는 유사도가 90% 이상의 범위에 위치함으로써 매우 높은 유사도 분포를 확인할 수 있었다. 기존의 구조적 방법은 90% 이상 높은 유사도를 보인 결과는 상대적으로 적었으며, 35% 이상의 결과는 10% 이하의 낮은 유사도를 보임으로써 매칭이 효과적으로 이루어지지 않음을 알 수 있다.
ZKM을 이용한 실험 결과에서 에지 확장 방법은 Smokescreen을 이용한 실험 보다 낮은 유사도 구간에 분포 비율이 높아졌다. 에지 확장 방법의 경우 25% 정도의 결과는 100% 일치하는 결과를 얻을 수 있었지만, 40% 정도의 결과는 50-70% 구간에 분포하고 있다.
그리고, 50% 이상의 상대적으로 높은 유사도 구간에 대부분의 결과들이 분포하고 있다. 기존의 구조적 비교 방법은 과반수에 해당하는 결과가 10% 미만의 유사도를 보였으며, 전체적으로 에지 확장을 통한 방법에 비해서 매칭 능력이 떨어지는 결과를 보였다. ZKM을 이용한 실험에서 유사도가 상대적으로 낮게 나온 것은 ZKM을 통한 변환이 제어 흐름 그래프의 구조적인 형태에 보다 많은 변화를 주기 때문이다.
본 논문에서 제안한 에지 확장 방법이 유사한 프로그램의 비교에서 기존의 구조적 비교 방법 보다 우수한 성능을 보인 것은 프로그램의 내용이 수정되더라도 제어 흐름 그래프의 기본 골격이 유지된다면 선후 관계에 있는 기본 블록의 관계 또한 그대로 유지되는 경향이 강하기 때문인 것으로 분석된다. 유사도가 낮게 나온 결과는 난독화를 통한 변화가 제어 흐름 그래프의 변형 뿐만 아니라 명령어 자체의 치환과 같은 복합적인 수정을 포함하고 있기 때문이다.
이런 접근 방법은 수행 성능에 있어서 빠른 비교 및 매칭이 가능하고, 프로그램에서 일부 영역에 한정된 업데이트만 적용된 경우에 서로 다른 부분을 찾아낼 때 효과적으로 적용이 가능하다. 하지만, 프로그램의 전반적인 수정으로 인해 기본 블록의 시그너처 정보의 변화가 많은 경우 매칭을 통한 비교가 효과적이지 못한 것으로 나타났다. 본 실험 결과를 통해서 에지 확장 방법은 임의의 제어 흐름 그래프를 비교할 때 보다 신뢰성 있는 결과를 보여준다는 것을 알 수 있다.
하지만, 프로그램의 전반적인 수정으로 인해 기본 블록의 시그너처 정보의 변화가 많은 경우 매칭을 통한 비교가 효과적이지 못한 것으로 나타났다. 본 실험 결과를 통해서 에지 확장 방법은 임의의 제어 흐름 그래프를 비교할 때 보다 신뢰성 있는 결과를 보여준다는 것을 알 수 있다.
에지 확장은 기본 블록을 매칭할 때 들어가는 에지와 나가는 에지로 인접한 기본 블록들의 관계를 함께 고려함으로써 프로그램의 수정에 강인한 제어 구조를 반영할 수 있다. 제어 흐름 그래프 사이의 유사도를 구하기 위해서 기본 블록과 에지 확장을 통해 구해진 유사도에 따라 기본 블록을 매칭하고, 매칭된 결과를 이용해서 전체 프로그램의 유사도를 검출할 수 있다.
기존의 구조적 비교 방법은 서로 다른 프로그램에 대한 변별력은 매우 우수하였지만, 서로 유사한 프로그램에 비교는 충분한 신뢰성을 가지지 못하였다. 에지 확장 방법은 서로 다른 프로그램에 대한 충분한 변별력을 가지고 있었으며, 구조가 유사한 프로그램에 대한 매칭 능력에서 기존의 방법에 비해 효과적인 결과를 보였다. 다만, 수행 성능에 있어서 에지 확장 방법은 기본 블록의 매칭을 위해서 기본 블록 내의 명령어를 모두 고려해야하기 때문에 기존의 방법에 비해서 상대적으로 많은 시간이 걸리는 경향이 있었다.
후속연구
그래프는 노드와 에지로 구성되기 때문에 그래프의 유사도를 측정하기 위해서 노드 뿐만 아니라 에지의 유사성 역시 고려하여야 한다. 제어 흐름 그래프를 비교할 때, 기본 블록의 제어 흐름을 나타내는 에지의 유사성을 함께 고려한 다면 보다 신뢰성 있는 비교 결과를 얻을 수 있을 것이다. 이를 위해서 제어 흐름 그래프의 기본 블록이 가지는 에지의 비교 결과를 확장함으로써 효과적으로 비교할 수 있다.
프로그램에 따라 하나의 기본 블록에 대해 나가는 에지와 들어오는 에지는 여러 개인 경우가 일반적이며 많은 수의 기본 블록들이 연관되기 때문에 노드와 에지에 대한 가중치 비율을 프로그램의 특성에 맞게 조정할 필요가 있다. 향후 다양한 프로그램에서 실험을 통해 기본 블록과 제어 흐름 사이의 유사도 반영 비율을 조율한다면 비교 결과의 신뢰성을 개선할 수 있을 것이다.
제어 흐름 그래프의 비교는 프로그램의 유사성 비교를 통한 코드의 최적화, 유사 코드 검출, 코드의 도용 탐지 뿐만 아니라 최근에는 악성 코드의 검출에도 활용되고 있다. 제어 흐름 그래프의 효율적인 비교는 프로그램의 다양한 분석 방법에 적용할 수 있으며, 향후 여러 응용 사례에서 적용될 수 있을 것이라 기대된다.
질의응답
핵심어
질문
논문에서 추출한 답변
바이너리 프로그램의 제어 흐름 그래프는 무엇인가?
바이너리 프로그램의 제어 흐름 그래프는 프로그램의 정적인 구조를 효과적으로 기술할 수 있는 자료 구조이다. 그래서, 프로그램의 특성을 이해하고 분석 정보를 활용하기 위해서 정적 분석, 동적 분석 등에서 광범위하게 사용되고 있다.
최대 공통 부분 그래프를 찾는 문제를 실제 환경에 활용하기 어려운 이유는 무엇인가?
일반적인 그래프의 비교 방법으로 두 그래프의 동일성을 비교하기 위해서 최대 공통 부분 그래프(maximum common subgraph) [6]를 이용하는 방법이 있는데, 최대 공통 부분 그래프를 찾는 문제는 NP-Hard 문제로 그 계산의 복잡도가 비효율적이기 때문에 실제 환경에 직접 활용하기 어렵다. 이를 보완하기 위해서 최대 공통 부분 그래프를 활용한 근사 비교 방법 [7, 8]에 관한 연구가 수행되고 있다.
비교 대상이 되는 그래프의 노드들이 레이블을 가지고 있지 않을 때 노드 간의 비교는 어떻게 하는가?
첫 번째는 비교 대상이 되는 그래프의 노드들이 레이블(label)을 가지고 있지 않는 경우이다. 이 경우 각 노드는 어떤 값을 가지고 있지 않는 경우이며, 노드간의 비교는 연결된 에지의 동일성 여부로 판단하게 된다. 두 번째는 그래프의 노드가 레이블을 가지고 있는 경우이다.
참고문헌 (15)
Renhard Wilhelm and Dieter Maurer, Compiler Design, Addison-Wesley, 1995.
Ruben Smelik, Arend Rensink, and Harmen Kastenberg, Specification and Construction of Control Flow Semantics, In Proceedings of IEEE Symposium on Visual Languages and Human-Centric Computing, pp.65-72, Sept., 2006.
Danilo Bruschi, Lorenzo Martignoni, and Mattia Monga, Detecting Self-Mutating Malware Using Control-Flow Graph Matching, In Proceedings of Detection of Intrusions and Malware & Vulnerability Assessment (DIMVA 2006), LNCS 4064, pp.129-143, 2006.
Guillaume Bonfante, Matthieu Kaczmarek, and Jean-Yves Marion, Control Flow to Detect Malware, Inter-Regional Workshop on Rigorous System Development and Analysis 2007.
Guillaume Bonfante, Matthieu Kaczmarek, and Jean-Yves Marion, Control Flow Graphs as Malware Signatures, International Workshop on the Theory of Computer Viruses, 2007.
Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
John W. Raymond1 and Peter Willett, Maximum common subgraph isomorphism algorithms for the matching of chemical structures, Journal of Computer-Aided Molecular Design, 16: pp.521-533, 2002.
Faisal N. Abu-Khzam, Nagiza F. Samatova, Mohamad A. Rizk, and Michael A. Langston, The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover, In IEEE/ACS International Conference on Computer Systems and Applications (AICCSA 2007), pp.367-373, May, 2007.
Zhiping Zeng, Anthony K. H. Tung, Jianyong Wang, Jianhua Feng, and Lizhu Zhou, Comparing Stars: On Approximating Graph Edit Distance, International Conference on Very Large Data Bases (VLDB 2009), 2009.
Laura Zager, Graph similarity and matching, MS Thesis, Dept of EECS, MIT, 2005.
Halvar Flake, Structural Comparison of Executable Objects, In Proceedings of the IEEE Conference on Detection of Intrusions and Malware & Vulnerability Assessment (DIMVA), pp.161-173, 2004
Thomas Dullien and Rolf Rolles, Graph-based comparison of executable objects, University of Technology in Florida, 2005.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.