본 논문은 binary diffing이 아닌 binary code diffing에 대한 survey를 제공한다.
하지만 binary diffing과 공유될 수 있는 주요 개념/용어를 정의하고 있기도 하고, binary diffing과 binary code diffing은 상호보완적일 수 있기 때문에 정리할만한 논문이었다.
특히 binary code diffing에 대한 개념/용어 정의, 어떤 분야에 사용될 수 있는지, 각 연구들을 어떻게 평가할 수 있는지(binary code diffng 한정) 등은 특히 주목할만하다.
(개념과 용어 정의는 Section II.B에, binary code diffing이 쓰이는 분야는 Section IV에, 기원과 발전 과정은 Section V에, 식별된 접근 방식들은 Section VI에 나와있다.)
Abstract
바이너리 코드 유사성 접근 방식(binary code similarity approaches)은 둘 이상의 바이너리 코드를 비교하여 유사점과 차이점을 식별하는 행위를 뜻한다. 바이너리 코드를 비교하는 능력은 패치 분석, 버그 탐색, malware 탐지 및 분석과 같이 소스 코드를 사용할 수 없는 시나리오에서 많은 real-world 응용 프로그램을 비교 가능하게 한다. 지난 20년 동안 수많은 바이너리 코드 유사성 접근 방식이 제안되었지만 연구 분야는 아직 체계적으로 분석되지 않았다. 본 논문에서 최초로 바이너리 코드 유사성에 대한 survey를 제공한다. 61개의 바이너리 코드 유사성 접근 방식을 분석한다. 이 접근 방식은 (1) 지원하는 응용 프로그램, (2) 접근 방식의 특성, (3) 접근 방식 구현 방법, (4) 평가에 사용되는 벤치마크와 방법론 네 가지 측면에서 체계화된다. 또한 survey에서 해당 분야의 scope과 기원, 지난 20년 동안의 발전, 그리고 앞으로의 challenge에 대해 논의한다.
Keywords - Code diffing, Code search, Cross-architecture, Program executables
I. INTRODUCTION
바이너리 코드 유사성 접근 방식은 두 개 이상의 바이너리 코드 조각(예: basic block, 함수, 전체 프로그램 등)을 비교하여 유사점과 차이점을 식별하는 것을 의미한다. 프로그램 소스 코드를 사용할 수 없는 시나리오에서는 바이너리 코드를 비교하는 것이 기본이며, 이런 시나리오는 COTS(commercial-of-the-shelf) 프로그램, legacy 프로그램, malware에서 발생한다. 바이너리 코드 유사성은 버그 탐색, malware clustering, malware detection, 패치 생성, 패치 분석, 프로그램 버전 간 정보 porting, 소프트웨어 도난 감지와 같은 real-world 응용 프로그램의 다양한 범위에서 사용될 수 있다.
함수명, 변수명, 소스 주석, 데이터 구조 정의를 포함한 컴파일 과정으로 인해 많은 프로그램 의미가 손실되기 때문에 바이너리 코드 유사성을 식별하는 것은 어렵다. 또한 프로그램 소스 코드가 변경되지 않은 경우에도 컴파일 과정에서 도입된 2차 변경으로 인해 소스를 다시 컴파일하면 바이너리 코드가 변경될 수 있다. 예를 들어, 다른 컴파일러를 사용하고, 컴파일러 최적화를 변경하고, 다른 타겟 운영 체제와 CPU 아키텍처를 선택할 때 결과 바이너리 코드가 크게 변경될 수 있다. 또한 소스 코드와 생성된 바이너리 코드 모두에 난독화를 적용하여 원본 코드를 숨길 수 있다.
지난 20년 동안 수많은 바이너리 코드 유사성 접근 방식이 제안되었지만, 체계적인 survey가 없다. 이전 survey들은 packer 도구의 바이너리 코드 난독화 기술, 바이너리 코드 타입 추론, 동적 malware 분석 기술을 다루었다. 바이너리 코드 유사성은 난독화를 해결해야 하고, 바이너리 코드 타입 추론은 유사한 바이너리 분석 플랫폼을 활용할 수 있으며, malware는 종종 바이너리 코드 유사성 접근 방식의 대상이기 때문에 관련 주제다. 그러나 바이너리 코드 유사성은 분석된 논문들의 주제와 잘 분리되어 있다. 다른 survey에서는 유사성 검색을 위한 해싱이나 numerical과 binary feature vector에 대한 유사성 metric과 같이 코드에 국한되지 않은 모든 바이너리 데이터에 대한 유사성 탐지를 연구했다. 이와 대조적으로, 본 survey는 바이너리 코드를 비교하는 접근 방식, 즉 executable byte stream을 디스어셈블하는 접근 방식에 중점을 둔다.
본 문서는 바이너리 코드 유사성에 대한 최초의 survey를 제시한다. 먼저 컴퓨터 보안, 소프트웨어 엔지니어링, 프로그래밍 언어 및 기계 학습과 같은 다양한 컴퓨터 과학 분야의 연구 분야에서 발표된 100편 이상의 논문을 조사하는 체계적인 선택 과정을 통해 61개의 바이너리 코드 유사성 접근 방식을 식별한다. 그런 다음, 61가지 접근 방식의 네 가지 측면을 체계화한다: (1) 적용 가능한 애플리케이션, (2) 접근 방식의 특성, (3) 접근 방식이 구현된 방식, (4) 이를 평가하는 데 사용된 벤치마크 및 방법론. 또한 바이너리 코드 유사성의 범위와 기원, 지난 20년 동안의 발전, 그리고 앞으로의 과제에 대해 설명한다.
바이너리 코드 유사성 접근 방식은 접근 방식, 구현, 평가가 매우 다양하다. 이 survey는 이러한 각 측면을 체계화하고 여러 차원에 걸쳐 61가지 접근 방식을 표로 요약하여 유사점과 차이점을 빠르게 이해할 수 있도록 한다.
예를 들어, 접근 방식 체계화에는 다음 정보가 포함된다:
- 비교되는 바이너리 코드의 입력 조각 수(예: 일대일, 일대다, 다대다)
- 분석된 바이너리 코드 조각의 granularity(예: basic block, 함수, 프로그램)
- syntactical representation, 그래프, code semantics에서 비교가 발생하는지 여부
- 사용된 분석 유형(예: static, dynamic, symbolic)
- scalability에 사용된 기술(예: hashing, embedding, indexing)
구현 방식 체계화에는 접근 방식을 구축하는 데 사용되는 바이너리 분석 플랫폼, 이에 사용된 프로그래밍 언어, 비교되는 바이너리 코드의 입력 부분에 대해 지원되는 아키텍처 및 접근 방식이 공개적으로 릴리즈되었는지 여부가 포함된다. 평가 체계화는 접근 방식이 평가되는 데이터 set과 평가 유형(예: 정확도, 이전 작업과의 비교, 성능) 및 컴파일러 및 컴파일 옵션 변경, 다른 아키텍처 및 난독화와 같은 일반적인 code transformation에 직면하여 접근 방식의 robustness를 평가하는 방법을 다룬다.
본 survey는 체계화 외에도 바이너리 코드 유사성이 바이너리 코드 ‘비교’에서 ‘search’로 어떻게 발전했는지, ‘단일 아키텍처’에서 ‘아키텍처 간 접근 방식’으로 초점이 이동한 방법에 대해서도 설명한다.
Paper structure
본 논문은 다음과 같이 구성되어 있다. 섹션 II에서는 바이너리 코드 유사성에 대한 개요를 제공한다. 섹션 III에서는 survey의 범위와 논문 선택 과정을 자세히 설명한다. 섹션 IV는 바이너리 코드 유사성의 적용을 요약한다. 섹션 V는 지난 20년 동안 이 분야의 발전을 요약한다. 섹션 VI는 61개의 바이너리 코드 유사성 접근 방식을, 섹션 VII는 구현을, 섹션 VIII는 평가의 특성을 체계화한다. 섹션 IX에서는 향후 연구방향을 논의하고 섹션 X에서 결론을 짓는다.
II. OVERVIEW
본 섹션에서는 먼저 컴파일 과정에 대한 배경 지식을 제공한다(§II-A). 그런 다음 바이너리 코드 유사성 문제(§II-B)에 대한 개요를 제시한다.
A. Compilation Process
바이너리 코드는 컴파일을 통해 생성되며 CPU에서 직접 실행할 수 있는 기계어 코드를 의미한다. 표준 컴파일 프로세스는 프로그램의 소스 코드 파일을 입력으로 사용한다. 선택한 컴파일러 및 최적화 수준과 특정 플랫폼(아키텍처, word size, OS에 의해 정의되는)을 위해 컴파일하여 오브젝트 파일을 생성한다. 그런 다음 이러한 오브젝트 파일은 stand-alone executable이나 라이브러리인 바이너리 프로그램에 링크된다.
바이너리 코드 유사성 접근 방식은 일반적으로 표준 컴파일 프로세스에 소스 코드 변환 및 바이너리 코드 변환이라는 두 가지 선택적 단계를 추가하는 Figure 1과 같이 확장된 컴파일 프로세스를 처리한다. 두 가지 유형의 변환은 일반적으로 semantics를 보존하며(즉, 프로그램 기능을 변경하지 않음) 가장 일반적으로 난독화, 즉 분산 바이너리 프로그램의 리버스 엔지니어링을 방해하기 위해 사용된다. 소스 코드 변환은 pre-compilation에서 발생한다. 따라서 입력과 출력은 모두 소스 코드다. 대상 플랫폼에 관계없이 적용할 수 있지만 프로그램을 작성하는 데 사용되는 프로그래밍 언어에 따라 다를 수 있다. 반면에 바이너리 코드 변환은 컴파일 후에 발생한다. 따라서 입력 및 출력은 바이너리 코드다. 사용된 프로그래밍 언어와 독립적이지만 대상 플랫폼에 따라 다를 수 있다.
난독화는 malware에서 기본적으로 사용하는데, 지적 재산권을 보호하기 위해 일반 프로그램에도 적용될 수 있다. 소스 코드 변환(예: Tigress)과 바이너리 코드 변환(예: packer)을 사용하는 기성(:off-the-shelf) 난독화 도구가 존재한다. 패킹은 malware에서 널리 사용되는 바이너리 코드 변환이다. 새 버전의 malware familmy가 준비되면 malware 개발자는 결과 실행 파일을 압축하여 기능을 숨기고 상용 malware detector의 탐지를 우회한다. 패킹 프로세스는 실행 파일을 입력으로 사용하고 동일한 기능을 가진 다른 실행 파일을 생성하지만 원래 코드는 숨겨져 있다(예: 데이터로 암호화되고 런타임에 압축 해제됨). 패킹 프로세스는 일반적으로 동일한 입력 실행 파일에 여러 번 적용되어 malware detector와 다르게 보이는 동일한 소스 코드의 polymorphic variation을 생성한다. 요즘은 대부분의 malware가 패킹되어 있고 malware는 기성 언패커를 사용할 수 없는 커스텀 패커를 사용하는 경우가 많다. 바이너리 코드 유사성의 주요 문제는 컴파일 프로세스가 동일한 소스 코드에 대해 다른 바이너리 코드 representation을 생성할 수 있다는 것이다. 개발자는 Figure 1의 두 회색 상자 부분(소스 코드 변환과 바이너리 코드 변환)을 수정하여 동일한 소스 코드에서 의미론적으로는 동일하지만, 서로 다른 바이너리 프로그램을 생성할 수 있다. 이러한 수정 중 일부는 표준 컴파일 프로세스로 인한 것일 수 있다. 예를 들어, 프로그램 효율성을 향상시키기 위해 컴파일러의 최적화 수준을 변경하거나 컴파일러를 완전히 변경할 수 있다. 두 변경 사항 모두 소스 코드가 변경되지 않은 상태로 남아 있음에도 불구하고 생성된 바이너리 코드를 변환한다. 작성자는 다른 아키텍처에 적합한 프로그램 버전을 얻기 위해 대상 플랫폼을 변경할 수도 있다. 이 경우 새로운 타겟 아키텍처가 다른 명령어 set을 사용한다면 생성된 바이너리 코드가 근본적으로 다를 수 있다. 작성자는 의도적으로 난독화 변환을 적용하여 동일한 소스 코드의 polymorphic variant을 생성할 수도 있다. 생성된 변형은 일반적으로 원래 소스 코드에서 정의한 것과 동일한 기능을 한다. 바이너리 코드 유사성 접근 방식의 목표는 동일한 소스 코드에 해당하지만 다른 변환을 거친 바이너리 코드의 유사성을 식별해내는 것이다. 바이너리 코드 유사성 접근 방식이 robust하다는 의미는 컴파일 및 난독화 변환에도 유사성을 여전히 인식하는 것이다.
B. Binary Code Similarity Overview
바이너리 코드 유사성 접근 방식은 바이너리 코드 조각을 비교하는데, 그 세 가지 주요 특징은 다음과 같다:
- (1) 비교 타입 (identical, similar, equivalent)
- (2) 비교되는 바이너리 코드 조각의 granularity (예: instructions, basic blocks, functions)
- (3) 비교되는 입력 조각의 수 (일대일, 일대다, 다대다)
다음으로 이 세 가지 특성에 대해 자세히 설명한다. 단순화를 위해 두 입력에 대한 비교 유형과 비교 세분성을 설명한 다음 여러 입력으로 일반화한다.
Comparison type
- identical (이하 동일한)
두 개 또는 그 이상의 바이너리 코드는 동일한 syntax, 즉 동일한 표현을 사용하는 경우 identical하다. 바이너리 코드는 raw byte의 16진수 문자열, 디스어셈블된 instruction sequence, CFG와 같은 다양한 방식으로 표현될 수 있다. 여러 바이너리 코드 조각이 동일한지 여부를 결정하는 것은 확인하기 쉬운 boolean decision(동일한지 아닌지)이다. 간단히 각 조각의 내용에 암호화 해시(SHA256 등)를 적용한다. 해시가 같으면 조각이 동일하다. 그러나 이러한 간단한 접근 방식은 많은 경우 유사성을 감지하지 못한다. 예를 들어, 동일한 컴파일 매개변수(즉, 동일한 컴파일러 버전, 동일한 최적화 수준, 동일한 대상 플랫폼)를 사용하여 동일한 프로그램 소스 코드를 두 번 컴파일하면 파일 해시가 다른 두 개의 실행 파일이 생성된다. 이는 실행 파일에 자동으로 계산되어 생성된 실행 파일의 헤더에 포함되는 컴파일 날짜와 같이 두 컴파일에서 서로 다른 메타데이터가 포함될 수 있기 때문에 발생한다.
- equivalent (이하 동등한)
두 개의 바이너리 코드는 semantics가 같을 경우, 즉 정확히 동일한 기능을 제공하는 경우 equivalent하다. 동등성은 바이너리 코드의 syntax를 고려하지 않는다. 분명히, 두 개의 동일한 바이너리 코드 조각은 동일한 의미를 갖지만 다른 바이너리 코드 조각도 있을 수 있다. 예를 들어, mov %eax, $0와 xor %eax, %eax는 모두 레지스터 EAX의 값을 0으로 설정하기 때문에 의미적으로 동일한 x86 instruction이다. 유사하게, 두 개의 서로 다른 대상 아키텍처에 대해 컴파일된 동일한 소스 코드는 동등한 실행 파일을 생성해야 하며, 아키텍처가 다른 명령어 set을 사용하는 경우 syntax가 완전히 다를 수 있다. 두 개의 임의 프로그램이 기능적으로 동일하다는 것을 증명하는 것은 halting problem를 해결하는 것으로 축소되는 결정 불가능한 문제다. 실제로 바이너리 코드 동등성을 결정하는 것은 작은 바이너리 코드 조각에 대해서만 수행할 수 있는 매우 비용이 많이 드는 프로세스다.
- similar (이하 유사한)
syntax, structure, semantics가 유사한 경우 두 개의 바이너리 코드 조각이 similar한 것으로 간주될 수 있다. syntax 유사성은 코드 표현을 비교한다. 예를 들어, clone detection 접근 방식은 syntax가 유사한 경우 바이너리 코드의 타겟 부분이 일부 소스 바이너리 코드의 복제라고 간주한다. structure 유사성은 바이너리 코드의 그래프 표현(예: CFG, CG)을 비교한다. 이는 syntactic similarity와 semantic similarity의 중간쯤 된다. 여기서 쓰이는 직관은 바이너리 코드의 control flow가 데이터에 대한 결정과 같은 semantics를 어느 정도 포착한다는 것이다. 또한 그래프 표현은 동일한 기능의 여러 syntax 표현을 캡처한다. 그러나 예를 들어 함수를 인라인하여 의미론에 영향을 주지 않고 그래프 구조를 수정할 수 있다. semantic 유사성은 코드의 기능을 비교한다. 의미론적 유사성에 대한 간단한 접근 방식은 OS API 또는 시스템 호출을 통해 프로그램과 환경 간의 상호 작용을 비교하는 것이다. 그러나 유사한 시스템 호출을 가진 두 프로그램은 출력에 대해 상당히 다른 처리를 수행할 수 있으므로 fine-grained semantic 유사성 접근 방식은 코드의 syntax 독립적인 비교에 중점을 둔다.
일반적으로 더 robust한 접근 방식은 캡처할 수 있는 변환이 많을수록 비용도 더 많이 든다. syntax 유사성 접근 방식은 가장 저렴하지만 가장 non-robust하다. register reallocation, instruction reordering, replacing instructions, 의미상 동일한 명령어로 명령어 교체와 같은 바이너리 코드의 간단한 변경에 민감하다. 구조적 유사성은 중간이다. 다중 syntax 변환에 대해 강력하지만 코드 인라인 또는 사용하지 않는 함수 매개변수 제거와 같은 코드 구조를 변경하는 변환에 민감하다. 의미론적 유사성은 코드 syntax 및 구조의 변경에도 불구하고 의미론 보존 변환에 대해 강력하지만 큰 바이너리 코드 조각에 대해 계산하는 데 비용이 매우 많이 든다.
Comparison granularity
바이너리 코드 유사성 접근 방식은 다른 granularity에서 적용될 수 있다. 일반적인 granularity는 instruction, basic block, function, 전체 프로그램이다. 일부 접근 방식은 coarser granularity에서 비교를 수행하기 위해 finer granularity에서 다른 비교를 사용한 다음 finer granularity 결과를 결합한다. 예를 들어, 두 프로그램이 유사한지 여부를 비교하기 위해 접근 방식은 두 프로그램 간에 동일한 함수의 비율을 결정할 수 있다. 따라서 input granularity( 접근 방식이 비교하는 이진 코드의 입력 조각의 granularity)와 approach granularity(접근 방식에서 서로 다른 비교의 granularity)을 구분한다.
Figure 2와 같이 finer granularity에서 특정 비교를 적용하면 coarser granularity에서 수행할 수 있는 비교 유형이 제한될 수 있다. 이 그림은 바이너리 코드의 두 조각이 finer granularity(예: basic block)에서 동일한지 여부를 계산하여 두 조각을 포함하는 coarser granularity(예: 해당 함수)가 동일하거나 동등하거나 유사하다는 것을 계산하는 데 사용할 수 있음을 보여준다. 그러나 더 finer granularity에서의 유사성은 coarser granularity 코드가 동등하거나 동일하다고 추론하는 데 사용할 수 없다. 예를 들어, 두 함수를 비교할 때 basic block이 모두 비슷하다고 해서 기능이 동일하거나 동등하다고 결론을 내릴 수 없다. 반면에 유사성은 가장 일반적인 비교 유형이며 finer granularity 비교 유형을 사용하여 추론할 수 있다.
Number of inputs
바이너리 코드 유사성 접근 방식은 두 개 이상의 바이너리 코드 조각을 비교할 수 있다. 두 개 이상의 조각을 비교하는 것은 한 조각을 나머지 조각과 비교하거나 각 조각을 다른 모든 조각과 비교하는 것으로 더 나눌 수 있다. 따라서 입력 수와 비교 방법에 따라 일대일(OO: one-to-one), 일대다(OM: one-to-many) 및 다대다(MM: many-to-many)의 세 가지 접근 방식을 식별한다. 입력 조각의 소스는 애플리케이션에 따라 다르다. 그것들은 동일한 프로그램 버전(예: 동일한 실행 파일의 두 가지 함수), 동일한 프로그램의 두 가지 버전 및 두 개의 다른 프로그램에서 올 수 있다.
- OO (one-to-one)
일대일 접근 방식은 바이너리 코드의 original piece(source, old, plaintiff, reference 등으로도 불림)을 바이너리 코드의 target piece(new, patched, upgrade 등으로도 불림)와 비교한다. 대부분의 OO 접근 방식은 바이너리 코드 비교를 수행한다 즉, 타겟(패치된) 버전에서 추가, 제거 또는 수정된 항목을 식별하기 위해 동일한 프로그램의 두 개의 연속적 또는 가까운 버전을 비교한다. 바이너리 코드 diffing의 세분성은 대부분 함수이며 diffing은 오리지날 프로그램 버전의 함수와 타겟 프로그램 버전의 다른 함수 간의 매핑을 얻으려고 시도한다. 추가된 함수는 타겟 함수에 매핑할 수 없는 오리지날 함수다. 제거된 함수는 오리지날 함수에 매핑할 수 없는 타겟 함수다. 수정된 함수는 동일하지 않은 매핑된 함수다.
- OM (one-to-many)
일대다 접근 방식은 바이너리 코드의 쿼리 조각을 여러 타겟 바이너리 코드 조각과 비교한다. 대부분의 OM 접근 방식은 바이너리 코드 검색을 수행한다. 즉, 쿼리 조각이 타겟 조각과 유사한지 검색하고 바이너리 코드의 상위 k개 가장 유사한 타겟 조각을 반환한다. 타겟 조각은 동일한 프로그램의 여러 버전(쿼리 조각이 가져온 버전과 다름), 동일한 아키텍처용으로 컴파일된 다른 프로그램 또는 다른 아키텍처용으로 컴파일된 프로그램에서 가져올 수 있다.
- MM (many-to-many)
OO 및 OM 접근 방식과 달리 다대다 접근 방식은 소스 조각과 타겟 조각을 구분하지 않는다. 모든 입력 조각은 동일한 것으로 간주되어 서로 비교된다. 이러한 접근 방식은 일반적으로 바이너리 코드 클러스터링을 수행한다. 즉, 클러스터라고 하는 유사한 바이너리 코드 조각의 그룹을 출력한다.
III. SCOPE & PAPER SELECTION
최신 기술에 대한 survey를 집중적이고 관리하기 쉽게 유지하려면 범위를 정의하는 것이 중요하다. 이에 바이너리 코드를 비교하는 작업에 집중한다는 제한 사항을 설정했다. 이 제한은 차례로 다음 네 가지 제약을 도입한다.
1) 소스 코드에 대한 액세스가 필요한 접근 방식, 즉 source-to-source와 source-to-binary 유사성 접근 방식은 제외한다.
2) bytecode에서 동작하는 접근 방식은 제외한다.
3) system call 또는 OS API 호출을 통한 프로그램과 환경의 상호 작용에 대해서만 유사성을 비교하는 behavioral approach는 제외한다.
4) 바이너리 코드를 file hashes, fuzzy hashes, signature-based approaches와 같이 구조가 없는 raw bytes sequence로 간주하는 접근 방식은 제외한다. 접근 방식은 raw byte를 instructions로 디스어셈블해야 한다. byte-level 접근 방식을 설명하는 논문은 포함하지 않지만 분석된 접근 방식에서 이러한 기술 중 일부(예: fuzzy hashing)의 사용을 조사한다.
또한 survey의 범위를 관리하기 쉽게 유지하기 위해 다음과 같은 제약 조건을 도입한다.
6) 학술기관의 기술 보고서 및 피어리뷰에 게재된 논문으로 조사를 제한한다. 따라서 우리는 도구를 분석하지 않고, 도구의 접근 방식을 설명하는 연구를 분석한다.
7) 새로운 바이너리 코드 유사성 접근 방식이나 기법을 제안하지 않고 단순히 목표를 위한 과정으로 기성 바이너리 코드 유사성 도구를 적용하는 논문은 제외한다.
Paper selection
후보 논문을 식별하기 위해 먼저 다음과 같은 컴퓨터 보안 및 소프트웨어 엔지니어링 분야의 상위 14개 분야에서 지난 20년 동안 발표된 모든 논문을 체계적으로 조사했다: IEEE S&P, ACM CCS, USENIX Security, NDSS, ACSAC, RAID, ESORICS, ASIACCS, DIMVA, ICSE, FSE, ISSTA, ASE, and MSR. 모든 관련 바이너리 코드 유사성 접근 방식이 해당 학회에 게시된 것은 아니며, 이는 특히 초기 접근 방식에 해당된다. 다른 곳에서 후보 논문을 식별하기 위해 code search, binary diffing, bug search와 같은 바이너리 코드 유사성 및 해당 응용 프로그램과 관련된 용어를 사용하여 Google Scholar와 같은 전문 검색 엔진에 광범위하게 쿼리했다. 또한 놓쳤을 수 있는 추가 논문에 대한 후보 논문의 참고 문헌을 주의 깊게 조사했다. 이 탐색을 통해 100개 이상의 후보 논문을 식별했다. 그런 다음 각 후보 논문을 읽고 위의 범위 제약 조건을 충족하는 바이너리 코드 유사성 접근 방식을 제안했는지 확인했다.
결론적으로, 접근 방식이 체계화된 Table I에서 61개의 바이너리 코드 유사성 연구 작업을 식별했다. Table I의 처음 세 열에는 접근 방식의 이름, 출판 연도, 작업이 출판된 장소가 나와 있다. 연구 작업은 출판 날짜별로 정렬되어 해당 분야 발전의 타임라인을 만든다. 논문은 가능한 경우 시스템 이름으로 식별되고, 그렇지 않은 경우 각 저자의 성의 이니셜과 출판 연도에 의해 식별된다. 총 61편의 논문이 37곳에서 출판되었다. 바이너리 코드 유사성은 아주 많은 학문에 걸쳐있다. 대부분의 논문은 컴퓨터 보안 분야(20개 분야 36개 논문), 소프트웨어 엔지니어링(8개 분야 13개 분야), 시스템(4개 분야 6개 분야), 머신 러닝(2개 분야 2개 분야) 분야에 있다. 바이너리 코드 유사성 논문이 가장 많은 곳은 DIMVA(6), ASE(4), CCS(3), USENIX Security(3), PLDI(3)이다.
IV. APPLICATIONS
본 섹션에서는 바이너리 코드 유사성 분석이 가능한 응용 프로그램들을 설명하여 그 중요성을 강조한다. 분석된 61개의 논문 중 36개는 응용 프로그램을 보여준다. 즉, 하나 이상의 응용 프로그램에 대한 정량적 평가 또는 사례 연구를 제시한다. 다른 23개의 논문은 바이너리 diffing 도구, 바이너리 코드 검색 플랫폼, binary clone detection approach와 같은 여러 응용 프로그램에 사용할 수 있는 일반적인 바이너리 코드 유사성 기능을 제시한다.
Table II는 식별된 8가지 응용 프로그램을 요약한다. 일부(예: F2004, BINSEQUENCE)는 여러 개의 응용 프로그램을 보여주기는 하지만 36개 논문의 대부분은 단일 응용 프로그램을 보여준다. 애플리케이션의 속성 중 하나는 애플리케이션이 동일한 프로그램의 다른 버전(패치 분석, 패치 생성, 포팅 정보, malware 계보)을 비교하는지, 다른 프로그램(malware 클러스터링, malware 감지, 소프트웨어 도용 감지)을 비교하는지 또는 두 가지 사례 모두에 적용될 수 있는지(bug search) 여부다. 다음으로 이러한 응용 프로그램에 대해 자세히 설명한다.
Bug search
바이너리 코드 유사성의 가장 인기 있는 응용 프로그램은 바이너리 코드의 타겟 조각이 있는 대규모 repository에서 알려진 버그를 찾는 것이다. 코드 재사용으로 인해 동일한 코드가 여러 프로그램 또는 동일한 프로그램의 여러 부분에 나타날 수 있다. 따라서 버그가 발견되면 버그가 있는 코드를 재사용하고 동일하거나 유사한 버그를 포함할 수 있는 유사한 코드를 식별하는 것이 중요하다. 버그 검색 접근 방식은 query buggy 바이너리 코드 조각을 입력으로 사용하고 repository에서 유사한 바이너리 코드 조각을 검색한다. 이 문제의 변형은 cross-platform bug search 으로, repository에 있는 바이너리 코드의 타겟 조각이 다른 플랫폼(예: x86, ARM, MIPS)에 대해 컴파일되었을 수 있다.
Malware detection
바이너리 코드 유사성은 주어진 실행 파일을 이전에 알려진 악성 코드 샘플 set과 비교하여 악성 코드를 탐지하는 데 사용할 수 있다. 유사도가 높으면 입력 샘플이 이전에 알려진 malware 계열의 변종일 가능성이 높다. 많은 malware 탐지 접근 방식은 시스템 또는 API 호출 동작을 비교한다. 그러나 섹션 III에서 설명한 것처럼 바이너리 코드 유사성을 사용하는 접근 방식에 중점을 둔다.
Malware clustering
malware 탐지의 발전은 유사하고 알려진 악성 실행 파일을 패밀리로 클러스터링하는 것이다. 각 패밀리 클러스터는 동일한 악성 프로그램의 실행 파일을 포함해야 하며, 이는 악성 프로그램의 다른 버전일 수 있으며 버전의 polymorphic(예: packed) variation일 수 있다. malware 탐지와 유사하게 바이너리 코드를 비교하는 접근 방식에 중점을 두고 system call이나 네트워크 트래픽을 기반으로 하는 순수한 행동 접근 방식을 제외한다.
Malware lineage
동일한 프로그램에 속하는 것으로 알려진 실행 파일 set이 주어지면 계보 접근 방식은 노드가 프로그램 버전이고 에지가 여러 버전에 걸쳐 프로그램의 발전을 캡처하는 그래프를 작성한다. 리니지 접근 방식은 일반적으로 버전 정보를 사용할 수 없기 때문에 malware에 가장 유용하다. 입력 샘플은 동일한 패밀리에 속해야 하므로 malware 계보는 종종 malware 클러스터링의 결과를 기반으로 한다.
Patch generation and analysis
가장 초기의 바이너리 코드 유사성 응용 프로그램이자 가장 인기 있는 응용 프로그램 중 하나는 동일한 프로그램의 두 개의 연속된 버전 또는 가까운 버전을 비교하여 새 버전에서 패치된 내용을 식별하는 것이다. 이것은 벤더가 패치 세부 정보를 공개하지 않는 독점 프로그램에서 가장 유용하다. diffing은 프로그램을 업데이트하기 위해 효율적으로 릴리즈할 수 있는 작은 바이너리 코드 패치를 생성한다. 또한 취약점을 수정하는 보안 패치를 자동으로 식별하고 해당 보안 패치를 분석하며 취약한 이전 버전에 대한 exploit을 생성하는 데에 사용할 수도 있다.
Porting information
바이너리 코드 유사성은 동일한 프로그램의 가까운 두 버전 간에 정보를 porting하는 데 사용할 수 있다. 가까운 버전은 일반적으로 많은 양의 코드를 공유하기 때문에 한 버전에 대해 수행된 분석은 새 버전에서 대부분 재사용할 수 있다. 예를 들어 초기 바이너리 코드 유사성은 악성코드 리버스 엔지니어링을 통해 얻은 profiling data와 분석 결과를 포팅한다.
Software theft detection
바이너리 코드 유사성은 소스 코드 도난, 바이너리 코드 재사용, 라이센스 없이 재구현되는 특허 알고리즘 또는 라이센스 위반과 같은 plantiff 프로그램에서 코드의 무단 재사용을 식별하는 데 사용할 수 있다(e.g. GPL code in a commercial application). 이러한 침해를 감지하기 위한 초기 접근 방식은 plaintiff 프로그램의 고유한 기능을 캡쳐하는 서명과 같은 소프트웨어 birthmark를 사용했다. 그러나 섹션 III에서 설명한 것처럼 서명 기반 접근 방식을 제외하고 바이너리 코드 유사성을 사용하는 접근 방식에 중점을 둔다.
V. BINARY CODE SIMILARITY EVOLUTION
이 섹션에서는 바이너리 코드 유사성의 기원과 지난 20년 동안의 발전을 설명하고 몇 가지 주목할만한 접근 방식을 강조한다.
The origins
바이너리 코드 유사성의 기원은 동일한 프로그램의 두 연속하는(또는 가까운) 버전 간의 차이점을 캡처하는 패치(또는 델타)를 생성하는 문제에 있다. text diffing 도구는 1970년대부터 존재했으며(인기 있는 UNIX diff는 1974년에 릴리즈됨) SCCS나 RCS와 같은 초기 소스 코드 버전 관리 시스템에 통합되었다. 무선 네트워크의 인기가 증가하고 일부 장치의 제한된 리소스로 인해 바이너리, 즉 텍스트가 아닌 두 버전 간의 차이점을 캡처한 작은 패치(파일 전체를 전송하는 대신)를 전송하여 효율성을 높이는 기술에 대한 관심이 높아졌다. 1991년 Reichenberger는 파일 구조에 대한 지식 없이 임의의 바이너리 파일 간에 패치를 생성하는 diffing 기술을 제안했다. 이 접근 방식은 텍스트 diffing의 line-level granularity 대신 byte-level에서 동작했으며, 패치에 나타나야 하는 바이트 시퀀스를 효율적으로 식별했다(업데이트된 버전에만 나타나서 원본 파일에는 나타나지 않기 때문에). RTPATCH, BDIFF95, XDELTA와 같은 바이너리 패치를 생성하고 적용하기 위한 여러 도구가 곧 등장했다. 이러한 도구는 byte-level에서 동작했으며 모든 타입의 파일을 구별할 수 있었다.
첫 번째 바이너리 코드 유사성 접근 방식은 1999년에 등장했다. 그해에 Baker는 executable code의 차이를 압축하는 접근 방식을 제안하고 DEC Alpha 실행 파일에 대한 패치를 생성하는 EXEDIFF라는 프로토타입 diffing 도구를 구축했다. 그들의 직관은 동일한 프로그램의 두 가지 실행 프로그램의 버전을 비교할 때 많은 변경 사항이 소스 코드의 직접적인 변경이 아니라 컴파일 프로세스로 인한 2차 변경 사항을 나타낸다는 것이라는 판단이다. 그들이 언급한 한 가지 예시는 재컴파일 시 변경될 수 있는 레지스터 할당이다. 그들이 언급한 또 다른 예시는 최신 버전에 추가된 코드가 이전 코드의 일부를 대체하므로 컴파일 프로세스가 올바른 주소를 가리키도록 대체된 코드의 포인터 값을 조정해야 한다는 것이다. 그들의 아이디어는 패치 시 2차 변경 사항을 재구성하여 패치에 포함될 필요가 없도록 하여 패치 크기를 줄이는 것이었다. EXEDIFF는 raw bytes를 instuction으로 디스어셈블하여 코드 구조를 활용한 바이너리 코드 간의 유사성 계산에 중점을 둔 가장 초기의 접근 방식이다.
또한 1999년에 Wang은 광범위하게 프로파일된 이전 버전에서 새 버전으로 프로파일 정보를 전파하여 재프로파일링의 필요성을 줄이기 위해 두 가지 버전의 Windows DLL 라이브러리 실행 파일을 align하는 도구인 BMAT를 발표했다. 그들의 접근 방식은 함수와 basic block을 비교하는 첫 번째 방법이다(EXEDIFF는 두 개의 instruction 시퀀스를 비교했다). 먼저 두 실행 파일의 함수를 매칭한 다음 매칭된 각 함수 내에서 유사한 블록을 매칭시켰다. 블록을 비교하기 위해 해싱 기술을 사용했다. 해싱은 포인터 변경을 처리하기 위해 relocation 정보를 제거했지만 순서를 구분했다.
The first decade
EXEDIFF 및 BMAT의 초기 연구 후에 다음 10년(2000-2009년) 동안 7개의 바이너리 코드 유사성 접근 방식만을 식별했다. 그러나 이들 중 일부는 바이너리 코드 유사성을 순전히 syntactical에서 semantic도 포함하도록 확장하므로 매우 영향력이 있다. 바이너리 코드 비교(OO)에서 바이너리 코드 클러스터링(MM) 및 바이너리 코드 검색(OM)도 포함하도록 범위를 넓힌다. 악성코드에 바이너리 코드 유사성을 적용한다. 2004년 Thomas Dullien(alias Halvar Flake)은 동일한 바이너리 프로그램의 두 가지 버전에서 함수를 align하는 callgraph isomorphism을 heuristic하게 구성하여 코드의 구조적 특징에 초점을 맞춘 graph-based binary code diffing approach을 제안했다. 이것은 일부 컴파일러 최적화에 의해 도입된 함수 내부의 instruction reordering을 처리하는 첫 번째 접근 방식이다. 후속 연구는 매칭된 함수 내부의 basic block도 매칭하도록 접근 방식을 확장했으며(BMAT에서 수행됨) instruction reordering에도 불구하고 유사한 basic block을 식별하기 위해 SPP(Small Primes Product) 해시를 도입했다. 이 두 작업은 IDA 디스어셈블러에 대한 인기 있는 BINDIFF 바이너리 코드 diffing 플러그인의 기초다.
2005년에 Kruegel은 악성코드의 polymorphic variation을 탐지하기 위해 graph coloring 기술을 제안했다. 이것은 semantic similarity와 MM 비교를 수행한 첫 번째 접근 방식이다. 그들은 유사한 기능을 가진 instruction을 14개의 semantic class로 분류했다. 그런 다음 해당 클래스를 사용하여 inter-procedural control-flow graph (ICFG)에 색상을 지정했다. graph coloring은 junk insertion, instruction reordering, instruction replacement와 같은 syntactical obfuscation에 대해 robust하다. 2008년 Gao는 동일한 프로그램의 두 버전 간의 semantic 차이를 식별하기 위해 BINHUNT를 제안했다. 이것은 code equivalence를 확인하는 첫 번째 접근 방식이다. symbolic execution과 constraint solver를 사용하여 두 개의 basic block이 동일한 기능을 제공하는지 확인한다.
2009년에 Xin은 SMIT를 발표했는데, 이는 특정 악성코드 샘플을 이용해 repository에서 유사한 악성코드를 찾는 접근 방식이다. SMIT는 최초의 OM 및 binary code search 접근 방식이다. 데이터베이스에서 악성코드 callgraph를 인덱싱하고 graph edit distance를 사용하여 유사한 callgraph를를 가진 악성코드를 찾는다.
The last decade
최근 10년(2010-2019) 동안 52가지 접근 방식이 확인되었다. 2015년부터 cross-architecture 버전(16개 접근 방식)에 중점을 둔 바이너리 코드 검색 접근 방식에 초점을 맞추었으며 최근에는 머신 러닝 접근 방식에 중점을 둔다. 2013년 Wei는 쿼리 함수의 바이너리 코드를 제공하는 바이너리 코드 검색 엔진인 RENDEZVOUS를 제안했으며, repository에서 유사한 syntax와 구조적 특징을 가진 다른 함수를 찾는다. 전체 프로그램에서 함수와 같은 더 작은 바이너리 코드 조각으로 search granularity를 줄이면 clone detection 및 bug search와 같은 응용 프로그램 배열이 가능하다(SMIT).
대부분의 바이너리 코드 검색 접근 방식은 bug search 애플리케이션을 대상으로 한다. 이 응용 프로그램은 2012년 Jang에 의해 소스 코드에서 처음 처리되었다. 2014년 David는 버그 검색에 중점을 둔 최초의 바이너 코드 검색 접근 방식인 TRACY를 제안했다. TRACY는 CFG의 실행 경로인 tracelet의 개념을 사용하여 취약한 함수와 유사한 함수를 찾는다. 2015년 Pewny는 최초의 cross-architecture 바이너리 코드 검색 접근 방식인 MULTI-MH를 발표했다. MULTI-MH는 input-output semantics로 함수를 인덱싱한다. 하나의 CPU 아키텍처(예: x86)용으로 컴파일된 함수가 주어지면 MULTI-MH는 다른 아키텍처(예: MIPS)용으로 컴파일된 유사한 함수를 찾을 수 있다. 이 문제는 임베디드 장치의 인기로 인해 빠르게 주목을 받았다. 2016년에 Lageman은 두 함수가 동일한 소스 코드에서 컴파일되었는지 여부를 결정하기 위해 neural network를 train했다. 딥 러닝의 사용은 αDIFF(2018), INNEREYE(2019) 및 ASM2VEC(2019) 등 지난 2년 동안 증가했다.
VI. APPROACHES
이 섹션에서는 바이너리 코드 유사성 접근 방식을 체계화하여 Table I의 Approach Characteristics column을 설명한다. 가독성을 위해 이 섹션을 읽는 동안 별도의 페이지에서 Table 1을 읽을 것을 추천한다.
A. Comparison Type
- Columns: Input Comparison; Approach Comparison
이 섹션에서는 접근 방식 입력 간의 비교 유형과 접근 방식에서 사용할 수 있는 finer granularity 비교에 대해 설명한다.
Input comparison
유사성을 식별하기 위해 분석된 61개의 모든 연구의 입력을 비교한다. 즉, 바이너리 코드의 작은 조각에 대해서만 효율적으로 해결할 수 있는 undecidable problem이기 때문에 identical input 또는 input equivalence를 식별하는 접근 방식은 없다(해시로 충분하기 때문). 따라서 입력 비교를 기반으로 바이너리 코드 유사성 접근 방식을 일대일(OO, 21개 접근 방식), 일대다(OM, 30개 접근 방식), 다대다(MM, 10개 접근 방식)로 분류한다. OM 접근 방식이 우세한 것은 지난 10년 동안 바이너리 코드 검색에 대한 높은 관심 때문이다.
OO 접근 방식에서 OM 또는 MM 접근 방식을 구축하는 것은 항상 가능하다. 예를 들어, OM 접근 방식은 두 입력 간의 유사성을 반환하는 OO 접근 방식을 사용하여 주어진 바이너리 코드의 쿼리 조각을 n개의 대상 각각과 비교하는 방식으로 간단하게 구현할 수 있다. 그런 다음 유사도를 감소시켜 n개의 대상에 순위를 지정하고 상위 k개 항목 또는 유사성 임계값 이상의 항목을 반환한다. 그러나 대부분의 OM 접근 방식은 비효율적이므로 이러한 간단한 구현을 피한다. 성능을 향상시키는 두 가지 주요 솔루션은 각 입력에서 feature vector를 추출하고 인덱스가 있는 repository에 바이너리 코드의 대상 조각을 저장하는 것이다. 각 입력에 대한 feature vector를 얻으면 입력당 한 번만 feature를 추출할 수 있다. 이는 feature 추출에 비용이 많이 들 때 상당한 이점을 제공한다(예: feature 추출에 다른 입력으로 바이너리 코드 조각을 여러 번 실행해야 하는 BLEX의 경우). feature vector가 추출되면 두 feature vector 간의 유사성 metric이 사용된다. 이 유사성 metric은 feature vector가 종종 numerical이거나 boolean이기 때문에 일반적으로 계산의 비용이 적다. 일부 접근 방식은 유사성 metric을 제안하는 데에 반해, 다른 접근 방식은 거리 metric을 제안하기 때문에 쉽게 혼동할 수 있다. metric이 0과 1 사이에서 정규화될 때 거리는 단순히 1에서 유사도를 뺀 값이라는 점을 명심하는 것이 중요하다. OM 접근 방식에서 사용하는 다른 솔루션은 feature vector에 있는 feature의 subset에 인덱스를 추가하는 것이다. 인덱스는 바이너리 코드의 입력 부분의 feature vector와 유사할 가능성이 더 높은 선택된 타겟의 feature vector 사이에만 유사성 metric을 적용하여 비교 횟수를 줄이는 데 사용할 수 있다.
Approach comparison
대부분의 접근 방식은 similarity(42개 접근 방식), equivalence(5), identical(2)과 같은 단일 타입의 비교를 사용한다. 접근 방식에서 한 가지 타입의 비교만 사용하더라도 입력 비교와 다를 수 있다. 예를 들어, EXEDIFF는 두 프로그램을 비교하는 과정에서 동일한 instruction을 찾는다. 서로 다른 granularity에서 여러 개의 비교 타입을 사용하는 12가지 접근 방식이 있다. 그 중 6개는 동일한 바이너리 코드 조각(BMAT, DR2005, SWPQS2006, BINCLONE)을 빠르게 식별하거나 그래프 동형(SMIT, SPAIN)과 같은 값비싼 비교를 줄이기 위해 finer granularity에서 동일한 비교를 사용한다. 다른 6개는 semantic similarity을 인식하기 위해 finer granularity에서 동등성 비교를 사용한다.
B. Granularity
- Columns: Input Granularity; Approach Granularities
finer granularity(예: 함수)를 사용하여 coarser granularity(예: 전체 프로그램)를 비교하는 것이 일반적이기 때문에 접근 방식(즉, approach granularity)에서 비교된 바이너리 코드 조각의 granularity에서 input granularity를 분리한다.
우리는 8개의 비교 granularity를 식별했다: instruction(I), related instruction set(I*), basic block(B), related basic block set(B*), function(F), related function set(F*) , trace(T), 전체 프로그램(P). instruction, basic block, function, 전체 프로그램은 설명이 필요 없는 표준 granularity이다. related instruction(I*)은 연속적이거나(예: n-gram) property(e.g., data dependent)를 공유한다. 그것들은 다른 basic block에 속할 수도 있고 심지어 다른 함수에 속할 수도 있다. 예를 들어, TRACY는 출력 변수에 집합적으로 영향을 미치는 instruction들을 그룹화한다. related basic block(B*)은 구조적 속성(예: CFG의 graphlets)을 공유하거나 동일한 실행 경로에 속한다. set 내의 basic block은 동일하거나 여러 함수에 속할 수 있다. 관련 함수(F*)는 라이브러리, 클래스, 모듈과 같은 프로그램 구성 요소를 구현한다. trace granularity는 동일한 입력에서 두 바이너리 프로그램의 실행 추적을 비교한다.
가장 일반적인 입력 granularity는 함수(26개 접근 방식)이고 그다음으로 전체 프로그램(25개), 관련 basic block(4개)이다. 전체 프로그램은 OO 접근 방식(16/21)에 대해 선호되는 입력 granularity다. 그 이유는 대부분의 바이너리 코드 비교 접근 방식은 입력 프로그램의 모든 함수와 입력 프로그램을 클러스터링하는 경향이 있는 MM 접근 방식 간에 일대일 매핑을 설정하려고 시도하기 때문이다. 반면에 함수는 바이너리 코드 검색 접근 방식(21/30)에 대해 선호되는 granularity다. 또 다른 네 가지 바이너리 코드 검색 접근 방식은 B*를 사용하여 함수의 subset만 포함하거나 함수 경계를 넘는 코드 재사용을 식별한다.
가장 일반적인 접근 방식 granularity은 함수(30개 접근 방법)와 basic block(20개)이다. 대부분의 접근 방식(47/61)은 서로 다른 입력 granularity와 접근 granularity를 사용한다. 즉, finer approach를 사용하여 coarser input granularity를 비교한다. 동일한 입력 및 접근 granularity를 사용하는 대부분의 접근 방식은 기능 검색을 수행한다(12/14). 동등성 비교를 수행하는 11가지 접근 방식은 효율성이 낮기 때문에 fine granularity로 수행한다. 이때 각 granularity는 B 6개, I* 5개, F 1개다. 일부 접근 방식은 직접 비교되지 않는 fine granularity로 함수를 누적하므로 approach granularities column에 표시되지 않는다. 예를 들어, GEMINI는 basic block feature를 누적하여 함수 granularity에서 numerical vector를 생성한다. 따라서 함수만 비교된다.
C. Syntactic Similarity
- Column: Syntactic similarity
syntactic approach는 코드 표현의 유사성을 포착하며, 보다 구체적으로 instruction 시퀀스를 비교한다. 가장 일반적으로 시퀀스 내의 instruction은 가상 주소 공간에서 연속적이며 동일한 함수에 속한다. 시퀀스 내의 instruction은 먼저 정규화될 수 있다(예: mnemonic만 고려하거나 opcode만 고려하거나 operand를 클래스로 정규화). VI-J 섹션에서 instruction 정규화에 대해 자세히 설명하고 이 subsection의 나머지 부분에서 instruction sequence를 참조한다.
instruction 시퀀스는 고정 또는 가변 길이일 수 있다. 고정 크기 시퀀스는 instruction stream(예를 들어 함수에서 선형으로 정렬된 instruction 위에) window를 sliding시켜서 얻는다. 이 프로세스는 windows size, 즉 시퀀스의 instruction 수와 stride, 즉 다음 시퀀스를 생성하기 위해 윈도우의 시작 부분을 슬라이드하는 명령어의 수로 특징지어진다. stride가 윈도우 크기보다 작으면 연속 시퀀스가 겹친다. stride가 1일 때 결과 시퀀스를 n-gram이라고 한다. 예를 들어, instruction mnemonic {mov, push, add}의 순서가 주어지면 두 개의 2-gram이 추출된다: {mov, push}와 {push, add}. n-gram을 사용하는 연구는 IDEA, MBC, RENDEZVOUS, MUTANTXS, EXPOSE, ILINE, KAM1N0 등 7개다. 고정 크기 시퀀스는 구성 가능한 stride가 1보다 큰 SWPQS2006에서도 사용된다. RENDEZVOUS는 n-gram 외에도 n-perms, 시퀀스 내에서 instruction reordering을 캡처하는 정렬되지 unordered n-gram을 사용한다. n-perm은 여러 n-gram을 캡처할 수 있다. 예를 들어 2-perm {mov, push}는 2-gram {mov, push}과 {push, mov}를 캡처한다.
instruction 시퀀스를 비교하는 가장 일반적인 방법은 hashing, embedding, alignment다. 해싱은 가변 길이 instruction 시퀀스에서 고정 길이 값을 얻기 위해 6가지 접근 방식(BMAT, DR2005, SWPQS2006, SMIT, BINCLONE, SPAIN)에서 사용된다. 해시 값이 같으면 시퀀스도 비슷하다. 5가지 접근 방식은 n-gram 시퀀스에서 임베딩을 생성한다(IDEA, MBC, MUTANTX-S, EXPOSE, KAM1N0). 세 가지 접근 방식(EXEDIFF, TRACY, BINSEQUENCE)은 두 시퀀스를 align하여 삽입, 제거, 수정된 instruction을 설명하기 위해 두 시퀀스 중 하나에 gap을 삽입하여 두 시퀀스 사이의 매핑을 생성한다. 이러한 접근 방식은 instruction이 align될 때 유사성 점수를 정의하고 instruction이 gap과 align될 때 gap 점수를 정의한다. 다른 덜 일반적인 비교 방법은 boolean feature의 벡터(ILINE)와 인코딩 시퀀스를 인덱싱(RENDEZVOUS)을 위한 문자열로 사용하는 것이다.
D. Semantic Similarity
- Column: Semantic similarity
semantic 유사성은 비교되는 코드가 유사한 효과를 갖는지를 포착한다. 바이너리 코드 조각의 의미는 프로세스 상태에서 생성하는 변경, 즉 레지스터 및 메모리 내용에 대한 업데이트로 설명할 수 있다. 의미론적 유사성을 계산하는 26가지 접근 방식을 식별한다. basic block은 제어 흐름이 없는 straight-line code이기 때문에 대부분 basic block granularity에서 semantics를 캡처한다. sematics를 캡처하는 데에 instruction classification, input-output pairs, symbolic formulas 세 가지 방법이 사용된다.
Instruction classification
바이너리 코드 유사성에 의미론을 도입하는 첫 번째 접근 방식인 KKMRV2005는 instruction을 14개의 클래스(예: arithmetic, logic, data transfer)로 분류하고 14비트 값을 사용하여 basic block의 instruction 클래스를 캡처했다. 이 semantic color bitvector는 basic block의 효과를 캡처한다. 이 접근 방식은 나중에 BMM2006, BEAGLE, FOSSIL 및 SIGMA에서 채택되었다. insturction 분류는 의미론적 유사성을 계산하는 데 사용할 수 있지만 두 개의 바이너리 코드가 동일한지 아닌지를 결정할 수는 없다.
Input-output pairs
직관적으로 두 개의 바이너리 코드 조각은 동일한 입력이 주어지면 가능한 모든 입력에 대해 동일한 출력을 생성하는 경우 기능적으로 동일하다고 할 수 있다. 이러한 동등성은 코드 표현과 무관하며 중간 프로그램 상태를 무시하고 코드가 실행된 후 최종 상태를 비교한다. 이 접근 방식은 Jiang이 소스 코드에 대해 제안했으며 나중에 BINHASH, MXW2015, BLEX, MULTI-MH, BINGO, CACOMPARE, SPAIN, KS2017, IMF-SIM과 같은 수많은 바이너리 코드 유사성 접근 방식에서 사용되었다. 동일한 입력으로 바이너리 코드의 두 부분을 모두 실행하고 출력을 비교하여 프로세스를 여러 번 반복하는 작업이 포함된다. 입력에 대해 출력이 다른 경우 바이너리 코드의 두 부분은 동일하지 않다. 불행히도 두 부분이 동등하다는 것을 결정하기 위해 접근 방식은 가능한 모든 입력을 테스트해야 하며, 이는 현실적이지 않다. 따라서 실제로 이 접근 방식은 테스트된 입력의 비율에 비례하는 신뢰도로 바이너리 코드의 두 부분이 동일할 가능성이 있거나 동일하지 않은지만 결정할 수 있다. 테스트된 입력은 일반적으로 무작위로 선택되지만 프로그램 데이터 섹션(CACOMPARE)에서 값을 가져오는 것과 같은 다른 선택 규칙을 사용할 수도 있다. 일반적으로 동적 접근 방식이지만 일부 접근 방식(예: MULTI-MH)은 정적으로 추출된 symbolic formulas에 대한 concrete input을 평가한다.
Symbolic formula
symbolic formulas는 좌변이 출력 변수이고 우변이 출력 변수를 파생하는 방법을 캡처하는 리터럴 및 입력 변수의 논리적 표현인 assignment statement이다. 예를 들어, add %eax,%ebx instruction은 symbolic formula EBX2 = EAX + EBX1로 나타낼 수 있다. 여기서 EBX2와 EBX1은 instruction 실행 전후의 EBX 레지스터 값을 나타내는 심볼이다. BINHUNT, IBINHUNT, BINHASH, EXPOSE, TRACY, RMKNHLLP2014, TEDEM, COP, MULTI-MH, ESH, XMATCH와 같은 11가지 접근 방식은 symbolic formula를 사용한다. 그중 8가지 접근 방식은 basic block granularity에서 symbolic formula를 추출하고, XMATCH 및 EXPOSE는 함수의 반환 값에 대한 수식을 추출하고, BINSIM은 시스템 호출의 인수가 파생된 방법을 캡처하는 실행 추적에서 symbolic formula를 추출한다. 다음 세 가지 방법이 symbolic formula을 비교하는 데 사용된다: thorem prover를 사용하여 동등성을 확인하고, 수식의 Semantic hash를 비교하여 동등성을 확인하고, 수식의 그래프 표현의 유사성을 계산한다.
- Theorem prover
BINHUNT는 STP, Z3와 같은 theorem prover를 사용하여 두 기호식이 동일한지 확인하는 아이디어를 도입했다(즉, 입력 변수가 동일한 값을 공유한다고 가정할 때 두 공식을 실행한 후 출력 변수에 항상 동일한 값이 포함되는지 여부). 이 접근 방식의 주요 제한 사항은 pair-wise equivalence queries만 수행할 수 있고, 해결 시간이 공식 크기에 따라 빠르게 증가하고, 솔버가 일부 쿼리에 대한 답변을 반환하지 못할 수 있기 때문에 계산 비용이 많이 든다는 것이다. 바이너리 코드 조각에는 각각 고유한 기호식으로 표시되는 여러 출력(메모리의 레지스터 및 변수)이 있을 수 있다. 이러한 접근 방식은 모든 pair 별 비교를 시도하고 일치하는 모든 변수가 동일한 값을 포함하도록 변수의 permutation이 있는지 확인해야 한다.
- Semantic hashes
theorem prover를 사용하는 대신 공식을 정규화하고(예: 공통 레지스터명을 사용) 단순화(예: 상수 전파 적용)한 후 두 기호식에 동일한 해시가 있는지 확인하는 방법이 있다. 이는 두 기호식이 동일한 해시를 가지고 있으면 동일해야 한다는 직관에서 비롯된다. 다음 세 가지 접근 방식은 의미론적 해시를 사용한다: BINHASH, BINJUICE 및 GITZ. 의미론적 해시는 효율적이지만 정규화 및 단순화 후에도 두 개의 동등한 공식이 다른 해시를 가질 수 있다는 점에서 제한적이다. 예를 들어, 공식 중 하나에서 symbolic term을 reordering하면(예: instruction reordering으로 인해) 다른 해시가 생성된다.
- Graph distance
XMATCH와 TEDEM은 basic block의 기호식을 트리로 표현하고 graph/tree edit distance를 적용하여 유사도를 계산한다. graph/tree edit distance를 계산하는 것은 semantic hash를 비교하는 것보다 비용이 많이 들지만 그래프 표현은 term reordering을 처리할 수 있는 semantic hash보다 이점이 있다.
E. Structural Similarity
- Column: Structural similarity
구조적 유사성은 바이너리 코드의 그래프 표현에 대한 유사성을 계산한다. 그래프는 동일한 코드의 여러 구문 표현을 캡처할 수 있고 의미론적 정보로 주석을 달 수 있기 때문에 구문 유사성과 의미론적 유사성 사이에 있다. 구조적 유사성은 다른 그래프에서 계산할 수 있다. 가장 일반적인 세 가지는 intra-procedural control flow graph (CFG), the inter-procedural control flow graph (ICFG), callgraph (CG)이다. 세 가지 모두 방향 그래프다. CFG와 ICFG에서 node는 basic block이고 edge는 제어 흐름 전환(예: 분기, 점프)을 의미한다. CFG의 basic block은 단일 함수에 속한다. 각 함수에는 자체 CFG가 있다. ICFG의 basic block은 모든 프로그램 함수에 속한다. 프로그램당 하나의 ICFG가 있다. CG에서 노드는 함수이고 edge는 caller-callee 관계를 캡처한다.
구조적 접근 방식 이면의 직관은 CG, ICFG, CFG가 유사한 코드에 대해 구조가 거의 변하지 않는 상당히 안정적인 표현이라는 것이다. CG나 ICFG에서 작동하는 접근 방식에는 전체 프로그램 입력 granularity가 있는 반면 CFG에서 작동하는 접근 방식에는 함수 granularity가 있거나 전체 프로그램 유사성을 향한 단계로 함수 유사성을 사용할 수 있다. 구조적 유사성 접근 방식은 레이블이 지정된 그래프를 사용할 수 있다. 예를 들어, F2004 및 DR2005는 CG의 노드 레이블을 사용하여 함수의 CFG에 대한 구조적 정보(예: instruction과 edge 수)를 캡처한다. 다른 접근 방식은 basic block(예: KKMRV2005, BINJUICE) 또는 임베딩(GENIUS, GEMINI, §VI-F 참조)의 semantics를 캡처하는 feature vector로 CFG/ICFG의 basic block에 레이블을 지정한다. edge 레이블을 사용하여 제어 흐름 전송 유형(BMM2006)을 캡처하거나 소스 및 대상 노드의 semantuc 레이블을 집계할 수 있다(FOSSIL).
구조적 유사성은 27개 접근 방식에서 사용된다. 14가지 접근 방식은 CFG에서만 동작하고, 5개는 CFG와 CG 모두, 4개는 ICFG에서만, 2 개는 CG에서만 동작한다. 또한 non-standard graph를 사용하는 세 가지 접근 방식이 있다. SIGMA는 CFG, CG , 레지스터 흐름 그래프의 정보를 결합한 semantic integrated graph를 제안하고 QSM2015과 LIBV는 execution dependence graph를 사용한다. 이 하위 섹션의 나머지 부분에서는 그래프 유사성을 계산하는 데 사용되는 다양한 접근 방식에 대해 설명한다.
(Sub)Graph isomorphism
대부분의 구조적 유사성 접근 방식은 그래프 동형(isomorphism)의 변화를 확인한다. 두 그래프 G와 H의 동형은 노드 집합 사이의 edge-preserving bijection f로, 두 노드 u, v가 G에서 인접하면 f(u)와 f(v)도 H에서 인접하다. 그래프 동형은 node set cardinality가 두 그래프에서 동일해야 하므로 바이너리 코드 유사성에 대해 엄격하다. 따라서 그 대신 G가 H와 동형인 subgraph를 포함하는지 여부를 결정하는 subgraph 동형을 확인하는 접근 방식을 사용한다. subgraph 동형은 알려진 NP-complete problem이다. 다른 접근 방식은 maximum common subgraph(MCS) isomorphism을 확인하는데, 이는 가장 큰 부분 그래프가 두 그래프와 동형이고 NP-complete다. 두 문제의 복잡도가 높아서 비교해야 하는 그래프 pair의 수와 비교되는 그래프의 크기를 줄이려고 시도한다. 예를 들어, DR2005는 동일한 해시(일치)가 있는 CFG와 노드 및 edge의 수가 매우 다른 CFG(일치할 가능성 없음)를 비교하지 않는다. IBINHUNT는 basic block에 taint 레이블을 할당하여 고려할 노드 수를 줄인다. 동일한 taint 레이블이 있는 노드만 subgraph 동형에서 고려된다. 필터링을 통과하는 후보 그래프 쌍의 경우 greedy와 backtracking으로 그룹화할 수 있는 근사 알고리즘이 사용된다.
- Greedy
이러한 접근 방식은 neighborhood exploration을 수행한다. 일치하는 노드의 초기 set이 먼저 식별된다. 그런 다음 이미 일치하는 노드의 이웃(즉, 부모 또는 자식)만 확인하여 매칭을 재귀적으로 확장한다. BMAT, F2004, DR2005, LKI2013, TEDEM, MULTI-MH, KLKI2016, KAM1N0, BINSEQUENCE, BINARM이 이 접근 방식을 사용한다. 그리디 알고리즘의 한계는 초기 오류가 전파되어 정확도가 크게 감소한다는 것이다.
- Backtracking
백트래킹 알고리즘은 solution을 다시 방문하여 잘못된 일치를 수정하고 새로운 매칭이 전체 매칭을 개선하지 않으면 되돌린다(BMM2006, BINHUNT, IBINHUNT, MXW2015, QSM2015, DISCOVRE). 백트래킹은 비용이 더 많이 들지만 local optimal matching를 피함으로써 정확도를 향상시킬 수 있다.
Optimization
네 가지 접근 방식(SMIT, BINSLAYER, CXZ2014, GENIUS)에서 사용하는 대안은 그래프 유사성을 최적화 문제로 모델링 하는 것이다. 두 개의 CFG와 두 개의 basic block 사이의 cost function이 주어지면 최소 비용으로 두 개의 CFG 사이의 전단사 매핑을 찾는다. 이러한 bipartite matching은 그래프 구조를 무시한다. 즉, edge 정보를 사용하지 않는다. 이를 해결하기 위해 SMIT와 BINSLAYER는 연결된 basic block에 더 낮은 비용을 할당한다. 매칭을 수행하기 위해 SMIT, BINSLAYER, CXZ2014는 Hungarian 알고리즘을 사용하고 GENIUS는 유전 알고리즘을 사용한다.
K-subgraph matching
KKMRV2005는 그래프를 k-subgraph로 나눌 것을 제안했다. k-subgraph는 각 subgraph에 k 개의 연결된 노드만 포함되는 그래프다. 그런 다음 각 k-subgraph 대한 fingerprint을 생성하고, 두 그래프의 유사도는 일치하는 k-subgraph의 최대 개수에 해당한다. BEAGLE, CXZ2014, RENDEZVOUS, FOSSIL과 같은 네 가지 다른 접근 방식이 나중에 이 접근 방식을 활용했다.
Path similarity
함수 유사성을 경로 유사성 비교로 변환하는 세 가지 접근 방식(COP, SIGMA, BINSEQUENCE)이 있다. 먼저 CFG에서 일련의 실행 경로를 추출한 다음 실행 경로 간의 경로 유사성 metric을 정의하고 마지막으로 경로 유사성을 함수 유사도로 결합한다.
Graph embedding
§VI-F에서 자세히 설명하겠지만 GENIUS, VULSEEKER, GEMINI에서 사용하는 또 다른 방법은 각 그래프에서 real-valued feature vector를 추출한 다음 feature vector의 유사성을 계산하는 것이다.
F. Feature-Based Similarity
- Column: Feature-based, Machine learning
유사성을 계산하는 일반적인 방법(28가지 접근 방식)은 바이너리 코드의 조각을 벡터 또는 feature set으로 표현하여 유사한 바이너리 코드 조각이 유사한 feature vector 또는 feature set를 갖도록 하는 것이다. feature는 바이너리 코드의 syntactic, semantic 또는 structural property를 캡처한다. feature는 Boolean, numeric 또는 categorical일 수 있다. 범주형 feature에는 instruction의 mnemonic과 같은 discrete value이 있다. feature vector는 일반적으로 모든 numeric feature 또는 모든 boolean feature를 가지며 후자는 bitvector라고 한다. 범주형 feature는 일반적으로 one-hot encoding을 사용하여 boolean feature로 먼저 인코딩되거나 임베딩을 사용하여 실수 값 feature로 인코딩된다. 28개 접근 방식 중 21개는 numeric feature vector를 사용하고 6개는 feature set을 사용하며 BINCLONE은 비트 벡터를 사용한다. feature가 추출되면 feature vector 또는 feature set 간의 유사성 metric을 사용하여 유사성을 계산한다. 일반적인 유사성 metric은 feature set에 대한 Jaccard index, 비트 벡터에 대한 dot product, numeric vector에 대한 Euclidean distance이다 또는 cosine distance이다.
Figure 3은 feature 기반 유사성에 대한 두 가지 대안적 방법을 보여준다. 상위 방법은 feature 선택과 feature 인코딩 두 단계로 구성된다. feature 선택은 분석가가 domain knowledge를 사용하여 대표적인 feature를 식별하는 수동 과정이다. 하위 방식은 학습 데이터에서 임베딩이라고 하는 real-valued feature vector를 자동으로 생성하는 방법을 학습하는 것이다. 임베딩은 8개의 최근 접근 방식(GENIUS, GEMINI, αDIFF, VULSEEKER, RLZ2019, INNEREYE, ASM2VEC, SAFE)에서 사용된다. 임베딩은 자연어 처리(NLP)에서 실수 값을 사용하여 범주형 feature를 인코딩하는 데 사용되며, 이는 one-hot encoding에 비해 차원을 줄이고 feature vector의 밀도를 증가시켜 딥 러닝 알고리즘에 도움이 된다. 임베딩은 자동 feature 추출 및 효율적인 유사성 계산을 가능하게 한다. 그러나 임베딩의 feature는 학습된 내용에 대한 정보를 제공하지 않는다.
바이너리 코드 유사성 임베딩은 캡처한 속성과 granularity로 분류할 수 있다. 임베딩을 사용한 최초의 바이너리 코드 유사성 접근 방식은 GENIUS이고, 이후 VULSEEKER와 GEMINI가 등장했다. 세 가지 접근 방식 모두 함수의 ACFG, 즉 선택된 basic block feature로 주석이 달린 노드가 있는 CFG에 대한 그래프 임베딩을 구축한다. GENIUS가 클러스터링 및 graph edit distance를 사용하여 임베딩을 계산하는 반면 VULSEEKER 및 GEMINI는 값비싼 그래프 작업을 피하는 신경망을 훈련하여 효율성을 향상시킨다. 이후의 접근 방식(αDIFF, RLZ2019, INNEREYE, ASM2VEC, SAFE)은 instruction 또는 raw byte, co-ocurrencence에 초점을 맞춰 수동으로 선택한 feature를 피한다. NLP에서는 word co-occurrence(예: word2vec)을 캡처하는 단어 임베딩을 추출한 다음 이를 기반으로 하는 문장 임베딩을 작성하는 것이 일반적이다. RLZ2019와 INNEREYE는 instruction를 단어로, basic block을 문장으로 간주하여 유사한 접근 방식을 사용한다. SAFE는 유사한 접근 방식을 사용하여 basic block이 아닌 임베딩 함수를 생성한다. 또한 함수의 다른 실행 경로를 따라 instruction co-ocurrence를 캡처하는 경로 임베딩을 결합하여 함수 임베딩을 얻는 ASM2VEC도 관련되어 있다. instruction co-ocurrence를 사용하는 대신 αDIFF는 convolutional network를 사용하여 함수의 raw bytes sequence에서 직접 embedding하는 함수를 계산한다.
Machine learning
우리는 바이너리 코드 유사성 접근 방식에서 머신 러닝의 세 가지 용도를 식별한다. (1) 위에서 설명한 대로 임베딩 생성, (2) 비지도 학습(BINHASH, MUTANTX-S, ILINE, RMKNHLLP2014, KLKI2016, GENIUS), (3) 바이너리 코드 조각이 동일한 소스 코드에서 컴파일되는 경우 확률(BINDNN, IMFSIM)로 분류한다. BINDNN은 바이너리 코드 유사성을 위한 neural network를 처음으로 사용했다. 임베딩을 생성하는 대신 BINDNN은 neural network classifier를 직접 사용하여 두 함수가 동일한 소스 코드에서 컴파일되었는지 확인한다. 놀랍게도 BINDNN은 neural network classifier을 사용하여 임베딩을 구축하는 것을 포함해 이후의 바이너리 코드 유사성 접근 방식에서 인용되지 않는다.
G. Hashing
- Column: Locality sensitive hashing
해시는 임의의 크기의 데이터를 고정된 크기의 값으로 매핑하는 함수다. 해시 값은 저장하기 쉽고, 계산하기에 효율적이며, 비교하기에 효율적이므로 인덱싱에 적합하다. 해시는 raw-byte level에서 동작한다. 바이너리 코드용으로 특별히 설계된 것이 아니라 임의의 바이너리 데이터용으로 설계되었다. 그러나 바이너리 코드 유사성을 위해 암호화 해시, locality-sensitive 해시, 실행 파일 해시의 세 가지 해시 클래스가 사용되었다. 암호화 해시는 유사한 입력이 아니라 동일한 입력을 캡처한다. 그것들은 fine granularity(예: basic block)에서 중복을 빠르게 식별하기 위해 일부 바이너리 코드 유사성 접근 방식에서 사용된다. locality-sensitive 해시는 유사한 입력에 대해 유사한 해시 값을 생성한다(입력의 작은 차이가 완전히 다른 해시 값을 생성하는 암호화 해시와 달리). 실행 파일 해시는 실행 파일을 입력으로 사용하지만 해시 계산은 import table 또는 실행 파일 헤더의 필드와 같은 실행 파일의 일부만 고려한다. 그들의 목표는 동일한 악성코드의 다형성 변종에 대해 동일한 해시 값을 출력하는 것이다.
Locality sensitive hashing (LSH)
LSH는 유사한 입력에 대해 유사한 해시 값을 생성하여 nearest neighbor search를 효율적으로 근사한다. LSH 알고리즘은 일반적으로 주어진 입력에 여러 해시 함수를 적용하고 유사한 입력에 대해 동일한 해시 값을 생성한다. 즉, 유사한 입력에 대한 충돌 확률을 높인다. LSH는 성능을 향상시키기 위해 바이너리 코드 유사성에 사용된다. 예를 들어, 바이너리 코드 조각을 인덱싱하기 위해 OM 접근 방식에서 사용하여 효율적인 바이너리 코드 검색을 가능하게 한다(KAM1N0, GEMINI, INNEREYE). LSH를 사용하는 11개 접근 방식 중 7개는 MinHash(BINHASH, MULTI-MH, GENIUS, BINSEQUENCE, BINSHAPE, CACOMPARE, BINSIGN)를 사용하고, 2개는 사용되는 알고리즘을 지정하지 않으며(GEMINI, INNEREYE), SWPQS2006은 Gionis의 알고리즘을 사용하고 KAM1N0은 자체 ALSH(Adaptive Locality Sensitive Hashing)를 제안한다.
fuzzy 해싱은 임의 파일의 유사성을 계산하는 데 사용되는 널리 사용되는 LSH의 한 종류다. 예를 들어 VirusTotal 파일 분석 서비스는 제출된 파일에 대한 ssdeep 해시를 레포트한다. 다른 fuzzy 해시로는 tlsh, sdhash, mrsh-v2가 있다. 61가지 접근 방식 중 어느 것도 사용하지 않지만 실행 파일에 자주 적용되기 때문에 간단히 설명하겠다. 실행 파일에 적용될 때 fuzzy 해시는 바이너리 코드의 유사성도 캡쳐할 수 있고, 실행 파일에 있는 데이터의 유사도 캡처할 수 있다. 이 문제는 최근 Pagani에 의해 조사되었다. 그 결과 .text 섹션의 코드에만 적용될 때 전체 프로그램 유사성에 사용될 때보다 훨씬 더 나쁘게 작동한다고 한다. 사실 그들은 올바른 위치에서의 바이트 변경, extra nop instructions, instruction swapping이 유사성을 상당히 저하시킬 수 있음을 보여준다(어떤 경우에는 0으로 떨어짐). 그들은 다른 최적화를 사용하여 동일한 소스 코드를 컴파일할 때 실행 파일의 데이터 섹션이 동일하게 유지된다는 것을 관찰했는데, 이것이 fuzzy 해시가 전체 실행 파일에서 더 잘 작동하는 주요 이유인 것 같다.
Executable file hashes
이 해시 클래스는 특히 실행 파일용으로 설계되었다. 동일한 악성코드의 다형성 변종에 대해 동일한 해시 값을 출력하도록 설계되었다. 해시 계산은 동일한 실행 파일을 단순히 repacking하거나 resigning할 때 변경될 가능성이 적은 실행 파일 부분만 고려한다. 그것들은 61가지 접근 방식 중 어느 것에도 사용되지 않지만 완전성을 위해 세 가지 인기 있는 해시에 대해 간략하게 설명하겠다. peHash는 초기 스택 크기, 힙 크기와 같이 컴파일 및 패킹 중 변경에 덜 민감한 PE 실행 파일의 선택된 필드를 해시한다. ImpHash는 실행 파일의 import table을 해시한다. packed variant의 기능이 동일하기 때문에 imported function도 동일해야 한다. 불행히도 패커가 런타임에 original import table을 재구성하는 경우 동일한 패커로 패킹된 관련 없는 실행 파일에 대해 오탐을 제공한다. Authentihash는 Windows Authenticode 코드 서명 데이터를 무시하는 PE 실행 파일의 해시이다. 다른 publisher가 서명한 동일한 실행 파일을 식별할 수 있다. Authenticode 데이터, Authenticode 데이터에 대한 포인터 및 파일 체크섬의 세 부분을 제외한 전체 PE 실행 파일을 해시한다.
H. Supported Architectures
- Column: Cross-architecture
cross-architecture 접근 방식은 x86, ARM 및 MIPS와 같은 다양한 CPU 아키텍처에 대한 바이너리 코드 조각을 비교하는 것이다. 이는 서로 다른 아키텍처를 지원하지만 상호 비교할 수 없는 아키텍처 독립적인 접근 방식(예: F2004)과 다르다. 즉, 2개의 x86 입력과 2개의 MIPS 입력을 비교할 수 있지만 x86 입력을 MIPS 입력과 비교할 수는 없다. 크로스 아키텍처 접근 방식은 16가지이며 모두 2015년부터 제안되었다. 일반적인 응용 프로그램에는 버그가 포함될 수 있는 다른 아키텍처용으로 컴파일된 유사한 바이너리 코드 조각을 검색하기 위해 버그가 있는 바이너리 코드 조각이 제공된다. 예를 들어, Heartbleed에 취약한 OpenSSL 버전이 정적으로 컴파일된 펌웨어 이미지에서 프로그램을 검색한다.
서로 다른 아키텍처에 대한 코드 구문은 서로 다른 instruction mnemonic, register set, default calling convention이 있는 별도의 instruction set을 사용할 수 있으므로 크게 다를 수 있다. 따라서 아키텍처 간 접근 방식은 의미론적 유사성을 계산한다. 크로스 아키텍처 접근 방식은 두 가지 기술 중 하나를 사용한다. MULTI-MH, MOCKINGBIRD, BINGO, XMATCH, CACOMPARE, GITZ, FIRMUP과 같은 7가지 접근 방식은 바이너리 코드를 아키텍처 독립적인 중간 표현(IR)으로 격상한다. 그러면 원본 아키텍처에 관계없이 IR에 대해 동일한 분석을 수행할 수 있다. 장점은 분석이 IR에만 의존하고 IR 디자인을 별도의 그룹에 아웃소싱할 수 있다는 것이다. 섹션 VII에서는 각 접근 방식이 지원하는 특정 아키텍처와 사용하는 IR에 대해 자세히 설명한다. 9가지 접근 방식에서 사용하는 대안 접근 방식은 feature 기반 유사성을 사용하는 것이다(§VI-F에서 논의됨). 이러한 접근 방식은 바이너리 코드(DISCOVRE, BINDNN, GENIUS, GEMINI, αDIFF, VULSEEKER, RLZ2019, INNEREYE, SAFE)의 의미를 캡처하는 feature 벡터를 얻기 위해 각 아키텍처에 대해 별도의 모듈을 사용한다.
I. Type of Analysis
- Column: Static analysis; Dynamic analysis; Dataflow analysis
바이너리 코드 유사성 접근 방식은 정적 분석, 동적 분석 또는 둘 다를 사용할 수 있다. 정적 분석은 디스어셈블된 바이너리 코드를 실행하지 않고 조사한다. 반대로 동적 분석은 선택한 입력에서 코드를 실행하여 코드 실행을 조사한다. 동적 분석은 코드가 통제된 환경에서 실행될 때 온라인으로 수행되거나 실행 추적에서 오프라인으로 수행될 수 있다. 51개의 접근 방식은 정적 분석만 사용하고 4개는 동적 분석만 사용하며 6개는 둘을 결합한다. 바이너리 코드 유사성에서 모든 입력 코드를 비교해야 하는 대부분의 응용 프로그램 때문에 정적 분석이 우위를 점한다. 이는 complete code coverage를 제공하므로 정적 분석을 사용하면 더 쉽다. 동적 분석은 한 번에 하나의 실행을 검사하고 해당 실행에서 실행되는 코드의 유사성을 결정할 수 있다. 동적 분석의 적용 범위를 늘리기 위해 세 가지 접근 방식 IBINHUNT, BLEX, IMF-SIM은 서로 다른 실행 경로를 포함하는 여러 입력에서 코드를 실행하고 결과를 결합한다. 그러나 가능한 모든 실행 경로를 포함하는 입력에서 중요하지 않은 바이너리 코드를 실행하는 것은 불가능하다.
동적 분석의 장점은 메모리 주소, operand 값, 제어 흐름 대상이 런타임에 알려지기 때문에 메모리 aliasing이나 간접 점프와 같은 정적 분석 문제를 피할 수 있다는 것이다. 또 다른 장점은 일부 난독화를 처리할 수 있고 난독화 코드에서도 어려운 코드의 디스어셈블이 필요하지 않다는 것이다. 섹션 VIII에서는 난독화된 코드에 대한 robustness를 평가한 접근 방식에 대해 자세히 설명한다. 전반적으로 동적 분석은 malware unpacking(SMIT, BEAGLE, MUTANTX-S, CXZ2014, BINSIM), 추적 단위(BINSIM, KS2017) 및 의미론적 유사성에 대한 런타임 값 수집(BLEX, BINSIM, IMF-SIM)을 위해 사용되었다.
Dataflow analysis은 값이 코드를 통해 전파되는 방식을 조사하는 일반적인 유형의 분석이다. 추적할 데이터 소스(예: 특정 변수를 보유하는 레지스터 또는 메모리 위치), 다른 instruction 또는 IR 문에 의해 값이 전파되는 방식을 정의하는 propagation rule, 도달하는 값을 확인할 프로그램 포인트인 sink로 구성된다. 데이터 흐름 분석을 사용하는 19개 접근 방식 중 16개는 기호 실행을 사용하여 의미론적 유사도(§VI-D)를 계산하는 기호 수식 set을 추출한다. SPAIN은 taint 분석을 사용하여 취약점의 패턴과 보안 패치를 요약한다. 그리고 IBINHUNT는 taint 분석과 기호 실행을 모두 사용한다. 먼저 taint 분석을 필터로 사용하여 동일한 사용자 입력을 처리하는 바이너리 코드 조각을 찾고 값비싼 subgraph 동형 계산을 동일한 taint 레이블이 있는 항목으로 제한한다. 그리고 symbolic formula를 사용하여 basic block 유사도를 계산한다. IMF-SIM은 역참조 오류에서 함수의 포인터 인자를 유추하기 위해 backward taint analysis를 사용한다.
J. Normalization
- Column: Normalization
구문 유사성 접근 방식은 종종 instruction을 정규화하므로 동일한 형식으로 정규화된 두 명령어는 일부 구문 차이(예: 다른 레지스터가 사용됨)에도 불구하고 유사한 것으로 간주된다. 전반적으로 instruction 정규화를 사용하는 접근 방식은 33가지다. 다음 세 가지 유형의 instruction 정규화를 적용한다.
Operand removal
9가지 접근 방식에서 사용하는 정규화는 모든 operand를 mnemonic 또는 opcode만 instruction을 추상화하는 것이다. 예를 들어, %eax, %ebx를 추가하고 [%ecx]를 추가하면 %edx는 둘 다 다른 operand를 사용함에도 불구하고 add로 표시되고 유사한 것으로 간주된다.
Operand normalization
17가지 접근 방식에서 사용되는 정규화는 instruction operand를 레지스터의 경우 REG, 메모리의 경우 MEM, immediate value의 경우 IMM과 같은 피연산자 유형을 나타내는 심볼로 대체하는 것이다. 예를 들어, %eax, %ebx를 추가하고 %ecx를 추가하면 %edx는 모두 add REG, REG로 표시되며 컴파일러에서 사용하는 다른 레지스터 할당에도 불구하고 명령어와 매칭된다. operand 정규화는 operand 제거보다 덜 추상화된다. 예를 들어 [%ecx]를 추가하면 %edx는 addMEM,REG로 표시되므로 위와 다른 것으로 간주된다. 일부 접근 방식은 범용 레지스터 및 세그먼트 레지스터와 크기가 다른 operand(예: BINCLONE의 RegGen8 및 RegGen32)에 대해 서로 다른 심볼을 사용하기도 한다.
Mnemonic normalization
3가지 접근 방식(BMAT, EXPOSE, ILINE)에서 사용하는 정규화는 동일한 심볼로 여러 mnemonic을 나타내는 것이다. 예를 들어, BMAT와 ILINE은 컴파일러가 점프 조건을 수정하는 것을 설명하기 위해 동일한 심볼로 모든 조건부 점프(예: je, jne)를 표현한다.
정규화의 또 다른 유형은 semantics에 영향을 미치지 않아야 하는 코드를 무시하는 것이다. 예를 들어, 일부 instruction set에는 프로세스 상태를 변경하지 않는 no-op instruction이 포함되어 있다. 그리고 컴파일러는 레지스터를 자기 자신에게 이동시키는 명령어(예: mov %eax, %eax)와 같이 패딩에 대해 no-op equivalent instruction을 사용하는 경우가 많다. no-op equivalent instruction은 의미적 유사성 및 구조적 유사성 접근 방식에 중요하지 않지만 구문적 유사성 접근 방식에 영향을 미칠 수 있다. 세 가지 접근 방식은 no-op instruction을 제거한다(ILINE, MXW2015, QSM2015). BMM2006, FIRMUP은 난독화로 인해 발생할 수 있는 도달할 수 없는 dead code도 제거한다. EXPOSE는 관련 없는 작은 함수가 함수 에필로그 및 프롤로그 instruction으로 인해 유사하게 보일 수 있기 때문에 제거한다. BINGO, SIGMA는 소스 코드 없는 프로그램을 로드하기 위해 컴파일러에서 추가한 함수를 제거한다.
VII. IMPLEMENTATIONS
이 섹션에서는 61가지 접근 방식의 구현을 체계화한다. 각 접근 방식에 대해 Table III에는 기반이 되는 정적 및 동적 플랫폼, 접근 방식을 구현하는 데 사용되는 프로그래밍 언어, 구현이 분석 배포를 지원하는지 여부, 지원되는 대상 프로그램 아키텍처 및 운영 체제, 접근 방식이 출시되는 방식이 나와 있다. dash(-)는 정보를 찾을 수 없음(즉, 알 수 없음)을 나타내고 cross(X)는 지원되지 않음/사용되지 않음을 의미한다.
바이너리 코드 유사성 접근 방식을 처음부터 구축하려면 상당한 노력이 필요하다. 따라서 모든 접근 방식은 정적 분석을 위한 디스어셈블리 및 제어 흐름 그래프 또는 동적 분석을 위한 instruction-level 모니터링과 같은 기능을 제공하는 이전에 사용 가능한 바이너리 분석 플랫폼 또는 도구를 기반으로 한다. 그러나 구현은 기본 플랫폼에서 제공하는 기능의 subset만 사용할 수 있다. 가장 널리 사용되는 정적 플랫폼은 IDA(42개 접근 방식)이고 BAP(4개), DynInst(3개) 및 McSema(2개)가 그 뒤를 잇는다. IDA의 주요 기능은 디스어셈블 및 제어 흐름 그래프 구축이다. IDA는 많은 수의 아키텍처를 지원하기 때문에 인기가 많다. 일부 바이너리 분석 플랫폼은 이미 IDA를 디스어셈블러로 사용하는 것을 지원하므로 IDA와 다른 플랫폼(6가지 접근 방식)을 결합하는 것이 일반적이다. 동적 접근 방식 중 PIN이 5가지 접근 방식으로 가장 많이 사용되며 TEMU 및 ANUBIS가 각각 3가지 접근 방식으로 그 뒤를 잇는다. 이전 연구는 바이너리 코드 유형 추론 접근 방식에서 사용되는 바이너리 분석 플랫폼을 분석했다. 대부분의 플랫폼이 겹치기 때문에 독자에게 플랫폼 세부 사항에 대한 해당 작업을 참조하도록 하고 부록(Table V)에 6개의 추가 플랫폼이 있는 확장된 버전의 테이블을 제공한다.
몇 가지 접근 방식은 이전 바이너리 코드 유사성 접근 방식을 기반으로 한다. 두 접근 방식 모두 저자가 중복되는 경우도 한 가지 있다. 예를 들어 RMKNHLLP2014는 BINJUICE를 기반으로 하고 MXW2015는 이미 BINHUNT와 구성 요소를 공유한 IBINHUNT를 확장한다. 다른 경우는 이전에 릴리즈된 접근 방식을 사용한다. 예를 들어, BINSLAYER 및 SPAIN은 BINDIFF를 첫 번째 단계 필터로 사용하여 일치하는 함수를 찾는다.
가장 인기 있는 프로그래밍 언어는 Python(20개)이고 C++(14개)가 그 뒤를 잇는다. 그 이유 중 하나는 대부분의 접근 방식이 디스어셈블리에 IDA를 사용하고 IDA가 C++ 및 Python 플러그인을 모두 지원하기 때문이다. 또한 KAM1N0, BINSIGN은 분석을 분산하기 위해 Hadoop과 같은 분산 플랫폼을 사용했다.
바이너리 코드 분석은 특정 instruction set(예: x86, ARM)에서 직접 작동하거나 중간 표현(IR)으로 변환할 수 있다. IR을 사용하면 두 가지 주요 이점이 있다. 첫째, IR 위에 구축된 분석을 재사용하는 것이 더 쉽다. 예를 들어, 새로운 아키텍처를 지원하려면 IR로 변환할 새로운 프런트 엔드를 추가하기만 하면 되지만 분석 코드는 재사용할 수 있다. 둘째, 복잡한 instruction set(예: x86/x86-64)은 implicit operand나 conditional flag와 같은 side-effect를 명시적으로 만드는 더 작은 IR statement set과 expression set으로 변환할 수 있다. IR을 사용하는 15가지 접근 방식이 있으며 대부분 기본 플랫폼에서 제공하는 IR을 사용한다. 15개 접근 방식 중 5개는 BITBLAZE에서 제공하는 VINE(BINHUNT, IBINHUNT, COP, MXW2015, BINSIM)을 사용하고 다른 5개는 VALGRIND에서 제공하는 VEX(MULTI-MH, MOCKINGBIRD, CACOMPARE, GITZ, FIRMUP)를 사용하고 2개는 LLVM-IR을 사용한다(ESH, XMATCH). 나머지 세 가지 접근 방식은 각각 SWPQS2006는 SAGE III, TEDEM은 METASM, BINGO는 REIL를 사용한다. 16개의 크로스 아키텍처 접근 방식 중 6개만 IR(MULTI-MH, XMATCH, MOCKINGBIRD, CACOMPARE, GITZ, FIRMUP)을 사용하는 것은 놀라운 사실이다. 나머지 접근 방식은 일반적으로 common format의 feature vector를 출력하는 각 아키텍처에 대해 별도의 분석 모듈을 제공한다.
분석 대상 프로그램에 대해 가장 많이 지원되는 아키텍처는 x86/x86-64(59개 접근 방식), ARM(16개), MIPS(10개) 순이다. x86/x86-64를 지원하지 않는 두 가지 접근 방식은 Digital Alpha를 대상으로 하는 EXEDIFF와 ARM을 대상으로 하는 BINARM뿐이다. 16개의 크로스 아키텍처 접근 방식과 펌웨어를 지원하는 9개의 접근 방식이 있다. 첫 번째 크로스 아키텍처 접근 방식은 2015년에 ARM에 대한 지원을 추가한 MULTI-MH였다. 그 이후로 ARM 지원은 모바일 및 IoT 장치의 인기로 인해 매우 보편화되었다. 60개 이상의 프로세서 제품군을 지원하는 IDA를 사용하는 접근 방식이 42가지라도 IDA를 기반으로 구축된 대부분의 접근 방식은 x86/x86-64 프로그램만 분석한다. 가장 많이 지원되는 OS는 Linux(41개 접근 방식)이고 그 다음으로 Windows(35개 접근 방식)다. 4가지 접근 방식만 MacOS를 지원한다. x86/x86-64에 중점을 둔 초기 접근 방식은 종종 IDA를 사용하여 PE/Windows 및 ELF/Linux 실행 파일에 대한 지원을 확보했다. 가장 최근에 ARM을 활용하는 모든 접근 방식은 Android와 많은 IoT 장치에서 사용되는 Linux를 지원한다.
61개 접근 방식 중 12개만 오픈 소스다(BINSLAYER, TRACY, QSM2015, ESH, GENIUS, KAM1N0, GEMINI, ASM2VEC, VULSEEKER, RLZ2019, INNEREYE, SAFE). DR2005는 BINDIFF 상용 도구로 구현되었으며 현재 무료 바이너리로 제공된다. 나머지 접근 방식은 기반이 되는 플랫폼이 오픈 소스일 수 있지만 어떤 형태로든 출시되지 않았다. 또한 12개 오픈 소스 접근 방식 중 4개(ESH, GENIUS, RLZ2019, INNEREYE)는 소스 코드와 머신 러닝 모델을 부분적으로 공개했다.
VIII. EVALUATIONS
이 섹션에서는 61개의 바이너리 코드 유사성 접근 방식의 평가를 체계화한다. 각 접근 방식에 대해 Table IV는 사용된 data set(§VIII-A)과 평가 방법론(§VIII-B)을 요약한다.
A. Datasets
Table IV의 왼쪽은 각 접근 방식에서 사용하는 data set을 설명한다. 먼저 평가에 사용된 총 실행 파일 수와 benign 실행 파일과 malicious 실행 파일로 나누어 표시한다. 실행 파일은 다른 프로그램에서 가져오거나 다양한 컴파일러 및 컴파일 옵션을 사용하는 등의 방법으로 동일한 프로그램의 여러 버전일 수 있다. 그런 다음 함수 granularity가 있는 접근 방식의 경우 평가된 총 함수 수를 캡처하고 펌웨어를 분석하는 접근 방식의 경우 실행 파일을 가져온 이미지 수를 캡처한다. column의 dash(-)는 해당 논문에서 해당하는 개수를 찾을 수 없음을 의미한다. 예를 들어, SWPQS2006은 Windows XP의 시스템 라이브러리 파일을 평가하지만 총 실행 파일 수는 표시되지 않았다.
대부분의 접근 방식은 custom dataset을 사용하며, 인기 있는 벤치마크 중 하나는 18가지 접근 방식에서 사용하는 Coreutils다. 또한 펌웨어를 평가하는 접근 방식은 공개적으로 사용 가능한 두 개의 펌웨어(ReadyNAS와 DD-WRT)를 사용한다. 접근 방식의 절반 이상이 100개 미만의 실행 파일, 7개는 1K 미만, 8개는 10K 미만, 8개는 10K 이상에 대해 평가한다. 61개 접근 방식 중 37개는 benign 프로그램에 대해서만, 8개는 malware만, 16개는 둘 다에 대해서 평가했다. 이는 바이너리 코드 유사성이 악성 코드 분석에도 널리 사용됨을 나타낸다. 그러나 악성코드에 대해 평가된 24개 접근 방식 중 5개만이 패킹된 악성코드 샘플(SMIT, BEAGLE, MUTANTXS, CXZ2014, BINSIM)을 사용한다. 이러한 접근 방식은 먼저 custom unpacker(SMIT) 또는 generic(쓰기 및 실행) 언패커(BEAGLE, MUTANTX-S, CXZ2014, BINSIM)를 사용하여 malware의 압축을 풀고 바이너리 코드 유사성을 계산한다. 나머지는 malware의 소스 코드 또는 언패킹된 샘플을 사용한다.
함수 granularity를 사용하는 바이너리 코드 검색 접근 방식의 경우 repository의 함수 수가 dataset size를 더 잘 캡처한다. 가장 큰 dataset은 GENIUS에 의한 것으로 8,126개의 펌웨어에서 추출한 4억 2천만 개의 함수를 평가한다. 이전 접근 방식은 최대 0.5M 함수에 대해 평가했으며, 이는 임베딩 방식의 scalability의 장점을 보여준다. GENIUS와 동일한 dataset을 사용하는 FOSSIL(1.5M), BINSEQUENCE(3.2M), BINARM(3.2M), FIRMUP(40M) 및 GEMINI(420M)의 5가지 다른 접근 방식이 1M가지 이상의 함수에 대해 평가되었다. 또한 INNEREYE는 120만개의 basic block의 repository에 대해 평가했다.
B. Methodology
Table IV의 오른쪽은 각 접근 방식에서 사용되는 평가 방법론의 네 가지 측면인 robustness, accuracy, performance, 이전 접근 방식과의 비교를 설명한다.
Robustness
Table IV의 오른쪽에 있는 처음 8개 column은 접근 방식의 robustness를 평가하는 방법, 즉 입력 프로그램에 적용된 변환에도 불구하고 유사성을 포착하는 능력을 캡처한다. 먼저 dataset의 프로그램을 컴파일하는 데 각각 GCC, ICC, Visual Studio(MSVS), Clang 중 어느 컴파일러를 사용하는지 보여준다. 그런 다음 다른 컴파일 옵션으로 컴파일된 프로그램(cross-optimization), 다른 컴파일러로 컴파일된 프로그램(cross-compiler), 다른 아키텍처용으로 컴파일된 프로그램(cross-architecture) 간에 유사성을 평가하는지 여부를 캡처한다. 마지막으로 난독화 변환이 입력 프로그램에 적용될 때 유사성을 평가하는지 여부를 캡처한다.
robustness를 평가하는 접근법은 34개(마지막 4개 robustness column 중 적어도 1개 V)와 그렇지 않은 27개다. 많은 초기 연구는 robustness 평가하지 않았다. 이 평가는 접근 방식이 발전하면서 대중화되었다. 가장 인기 있는 robustness 평가는 cross-optimization(23개 접근 방식)이며, 그 다음이 cross-compiler(19개), cross-architecture(16개), 난독화(13개)이다. 크로스 최적화/컴파일러/아키텍쳐를 평가한 9가지 접근 방식이 있다. 크로스 컴파일러를 평가하는 것이 더 간단하므로 일반적으로 교차 최적화도 평가한다. 유사하게, 크로스 아키텍처를 평가하는 접근 방식은 일반적으로 크로스 컴파일러도 평가한다. 이는 크로스 아키텍처 프로그램이 다른 컴파일러를 사용하여 생성될 수 있기 때문이다. 여러 컴파일러로 프로그램을 컴파일하는 접근 방식이 가능하지만 크로스 컴파일러 평가를 수행할 수 없다. 즉, 다른 컴파일러로 컴파일된 프로그램 간의 유사성을 비교하지 않는다.
난독화된 프로그램에 대해 평가한 13가지 접근 방식이 있다. 그 중 2개는 소스 코드 변환만 사용(COP, ASM2VEC), 3개는 바이너리 코드 변환만 사용(KKMRV2005, TPM, BINSHAPE), 5개는 packed malware(SMIT, BEAGLE, MUUTANTX-S, CXZ2014, BINSIM)를 사용하고 3개는 소스 코드 및 바이너리 코드 변환(BINSIM, IMF-SIM, FOSSIL)을 평가한다.
Accuracy evaluation and comparison
여기에 일부 ground truth(V)를 사용하여 정확도의 정량적 평가를 수행하는 49개 접근 방식과 사례 연구(X)를 통해 정성적 정확도 평가를 수행하는 12개 접근 방식이 있다. true positives, false positives, precision, recall과 같은 표준 정확도 metric을 가장 자주 사용한다. 그러나 두 가지 접근 방식이 새로운 애플리케이션별 정확도 metric을 제안한다(ILINE, KS2017).
기존 접근 방식과 비교하여 33가지 접근 방식이 있다. 그들 모두는 정확도를 비교하고 6개는 런타임을 비교한다. 상위 비교 대상은 BINDIFF(13개 접근 방식 비교)이고 TRACY(5), DISCOVRE(4) 및 MULTI-MH(4)가 그 뒤를 잇는다. 바이너리 코드 유사성 접근 방식에서 정확도를 비교하는 것은 여러 가지 이유로 어렵다. 첫째, 제안된 접근 방식 중 극히 일부만이 코드를 공개적으로 발표했다(섹션 VII). 대부분의 접근 방식은 공개하지 않기 때문에 종종 이전 접근 방식을 다시 구현하여 수행되며 상당한 노력이 필요할 수 있다. 재구현의 한 가지 장점은 접근 방식을 새로운 dataset에서 비교할 수 있다는 것이다. 재구현에 대한 대안은 이전 접근 방식에서 사용된 동일한 dataset에 대한 새로운 접근 방식을 평가하고 보고된 결과와 비교하는 것이다. 이 방법은 6가지 접근 방식(GENIUS, BINGO, XMATCH, CACOMPARE, GEMINI 및 BINARM)에서만 사용된다. 대부분의 dataset이 custom이고 공개적으로 사용할 수 없기 때문일 수 있다. 다행히 최근에는 public code 릴리즈가 더 늘었다. 둘째, 입력 비교와 입력 granularity가 접근 방식마다 달라 공정한 비교가 거의 불가능할 수 있다. 예를 들어 호출 그래프를 사용하여 프로그램 유사성을 식별하는 접근 방식(예: SMIT)과 basic block을 비교하는 접근 방식(예: INNEREYE)을 공정하게 비교하는 것은 어렵다. 셋째, 입력 비교와 입력 granularity가가 같더라도 평가 지표와 방법론이 달라 측정 정확도에 큰 영향을 미칠 수 있다.
후자는 함수 granularity에서 작동하는 바이너리 코드 검색 접근 방식에서 가장 잘 설명된다. 이러한 접근 방식은 repository에서 주어진 함수와 가장 유사한 함수를 찾는다. 유사도 내림차순의 여러 항목을 반환하고 가장 유사한 상위 k개의 항목 중 하나가 일치하는 경우 true positive로 카운트한다. 불행히도 k 값은 접근 방식에 따라 다르며 정확도에 상당한 영향을 미친다. 예를 들어 상위 10위의 98% 정밀도는 상위 3위의 98% 정밀도보다 훨씬 더 나쁘다. 따라서 다른 k 값으로 얻은 정확도 수치를 비교하는 것이 어려워지고 충분히 높은 정확도 수치가 달성될 때까지 k를 높이고 싶은 유혹이 생긴다. 또한 많은 접근 방식이 repository에 유사한 항목이 존재하지 않는지 확인하는 데 사용되는 similarity threshold를 설명하지 않고 있다. 따라서 유사성이 낮더라도 repository에서 유사한 항목을 항상 찾아내게 된다.
Performance
일반적으로 런타임 성능을 측정한다(49/61). 런타임은 일반적으로 end-to-end로 측정되지만 일부 접근 방식에서는 각 접근 방식 구성 요소(예: BINSIM)에 대해 보고한다. 네 가지 접근 방식이 asymptotic complexity을 보고한다(BMM2006, SWPQS2006, ILINE, MOCKINGBIRD).
IX. DISCUSSION
이 섹션에서는 open challenge와 가능한 향후 연구 방향에 대해 설명한다.
Small pieces of binary code
많은 바이너리 코드 유사성 접근 방식은 작은 바이너리 코드 조각을 무시하고, 고려할 최소 instruction 수 또는 basic block 수에 대한 임계값을 설정한다. 종종 함수의 instruction 수가 5개 미만인 경우 등 소수의 instruction이 있는 바이너리 코드 조각만 무시되는데, 일부 접근 방식은 TRACY의 100개 basic block과 같은 큰 임계값을 사용한다. 바이너리 코드의 작은 조각은 공통적이고 구조 분석을 방해하는 단일 basic block으로 구성될 수 있으며 다른 semantics에도 불구하고 동일한 구문을 가질 수 있기 때문에 어렵다. 예를 들어, 객체의 필드 값을 업데이트하는 setter 함수는 매개변수 값으로 메모리 변수를 설정하기만 하면 거의 동일한 구문과 구조를 갖는다. 그러나 보안 수준을 설정하거나 performance counter를 업데이트하는 것과 같이 매우 다른 의미를 가질 수 있다. 또한 instruction classification, symbolic formulas, input-output pair들과 같은 semantic 유사성 기술은 차이점을 캡처하지 못할 수 있다(예를 들어 서로 다른 메모리 변수를 구분하기 않는 경우). 작은 바이너리 코드 조각의 유사성은 여전히 미해결 과제다. 한 가지 잠재적인 방법은 컨텍스트를 추가로 통합하는 것이다. 일부 구조적 접근 방식은 이미 함수와 일치하는 호출 그래프를 고려하지만(예: F2004), 항상 충분하지 않다. 우리는 locality(예: 바이너리 코드가 프로그램 구조에서 얼마나 가까운지) 또는 data reference(예: 동등한 변수를 사용하는지 여부)와 같은 다른 컨텍스트를 추가로 통합하는 것이 가능할 수 있다고 믿는다.
Source-to-binary similarity
표절 탐지와 같은 일부 응용 프로그램에서는 소스 코드를 바이너리 코드와 비교해야 할 수 있다. source-to-binary 유사성에 대한 초기 접근 방식은 소스 코드의 고유 함수를 캡처하는 소프트웨어 birthmark를 사용했다. 최근에는 오픈 소스 코드의 알려진 버그가 일부 대상 바이너리 코드에 존재하는지 검색하기 위해 source-to-binary 유사성이 적용되었다. 소스 코드의 가용성은 단순히 소스 코드를 컴파일하고 바이너리 코드 유사성을 수행하는 것에 비해 잠재적으로 정확도를 향상시키는 더 많은 semantics(예: 변수 및 함수 이름, 유형, 주석)를 제공한다. 우리는 바이너리 코드의 대상 조각이 일부 주어진 소스 코드에서 컴파일되었는지 또는 진화했는지 확인해야 하는 다른 응용 프로그램이 남아 있다고 믿는다. 예를 들어 소스 코드가 이전 버전에서만 사용할 수 있는 프로그램이 있을 수 있으며 최신 바이너리 버전이 원본 소스 코드에서 어떻게 발전했는지 이해할 필요가 있다.
Data similarity
이 survey는 바이너리 코드 유사성에 초점을 맞추었지만 프로그램은 코드와 데이터를 모두 포함한다. 코드에서 사용하는 데이터가 코드만큼 중요할 수도 있다. 예를 들어 machine learning classifier의 매개변수 변경과 같이 프로그램 버전 간의 유일한 변경 사항이 사용된 데이터인 경우가 그 예이다. 또한 데이터는 기능의 핵심이 될 수 있는 복잡한 데이터 구조에 저장될 수 있다. 바이너리 코드에 대한 타입 추론 기술의 오랜 역사가 존재한다. 바이너리 코드 유사성과 결합하여 서로 다른 바이너리 코드 조각에서 사용되는 데이터 구조를 비교하거나 두 개의 바이너리 코드가 동일한 데이터 구조를 사용하는 방식을 비교할 수 있다고 믿는다.
Semantic relationships
의미론적 유사성의 다른 측면은 관련 기능(예: 암호화 또는 네트워킹 함수)이 있는 바이너리 코드를 식별하는 것이다. 이는 기능과 관련된 코드가 동일한 의미를 갖지 않을 수 있기 때문에 어렵다. 예를 들어, 복호화 함수는 암호화 함수와 분명히 관련이 있지만 반대 작업을 수행한다. 지금까지 대부분의 작업은 암호화 함수 식별하는 것과 같은 도메인 특정 기술에 중점을 두었다. 그러나 최근에 일부 접근 방식이 domain-agnostic 기술을 탐구하기 시작했다. 우리는 이러한 의미론적 관계와 식별을 더 잘 정의하기 위해 추가 작업이 필요하다고 생각한다.
Scalability
지금까지 가장 큰 바이너리 코드 유사성 평가는 GENIUS와 GEMINI가 8,126개의 펌웨어 이미지(이미지당 500K 함수)의 420M 기능에 대해 수행한 것이다. 이는 이전 접근 방식에 비해 중요한 단계이지만 100K 개의 고유한 펌웨어를 고려하면 2020년까지 200억 개의 IoT 장치가 인터넷에 연결될 것으로 예상되기 때문에 보수적인 수치이다. 500억 개의 함수를 처리할 수 있는 바이너리 코드 유사성 접근 방식이 필요하다. 따라서 바이너리 코드 검색 엔진의 비전을 실현하려면 scalability에 대한 추가 개선이 필요하다.
Obfuscation
난독화된 코드의 바이너리 코드 유사성에 대한 많은 문제가 여전히 남아 있다. 예를 들어, 최근 연구에 따르면 최첨단 언패킹 기술은 불완전한 함수 탐지로 인해 원래 코드의 20~60%를 놓칠 수 있음을 보여준다. 그리고 현재 Themida나 VMProtect와 같은 가상화 기반 패커를 처리하는 바이너리 코드 유사성 접근 방식이 없다. 이들은 임의의 bytecode instruction set을 생성하고, 바이너리 코드의 입력 조각을 해당 bytecode instruction set로 변환하고, 생성된 바이트코드에서 네이티브 코드에 인터프리터(또는 가상 머신)를 연결 한다. 또한 난독화는 의미론적 유사성으로 가장 잘 해결되며, 코드의 원래 의미를 존중하지 않지만 여전히 주요 목표를 수행하는 난독화 변환에 challenge가 남아 있다.
Approach comparison
접근 방식을 평가하는 데 사용되는 다양한 dataset과 방법론(예: OM 접근 방식에 대한 상위 k개 평가)과 함께 이들 중 다수에 대한 소스 코드가 없기 때문에 이점과 한계를 이해하기 위한 공정한 비교를 수행하기 어렵다. 우리는 이 분야가 벤치마킹을 위한 public dataset과 동일한 실험 조건에서 독립적인 검증하는 것이 큰 이점을 가져다 줄 것이라고 믿는다. 또한 컴파일러 및 컴파일러 옵션의 변경을 넘어 난독화를 처리하는 접근 방식의 비교를 개선할 필요가 있다. 가능한 난독화 변환의 거대한 space와 각 접근 방식이 다른 subset을 지원한다는 점을 감안하면 real-world의 난독화를 다루는 dataset을 구축하는 것은 필수적이다.
X. CONCLUSION
지난 20년 동안 연구자들은 바이너리 코드 유사성을 수행하기 위해 많은 접근 방식을 제안했으며 패치 분석, 버그 검색, 악성 코드 탐지 및 분석과 같은 중요한 문제를 해결하기 위해 이를 적용했다. 이 분야는 다음과 같이 발전했다: 바이너리 코드 비교에서 바이너리 코드 검색으로; syntactic 유사성에서 structural 및 semantic 유사성을 통합하기 위해; 여러 code granularity를 다루기 위해 비교의 robustness를 강화하기 위해(cross-optimization, cross-compiler, cross-OS, cross-architecture, obfuscation) 비교되는 입력의 수를 조정하기 위해(예: 해싱, 임베딩, 인덱싱을 통해); similarity feature를 자동으로 학습하기 위해 발전했다.
이러한 인기에도 불구하고 아직 체계적으로 분석되지 않은 분야다. 본 논문은 바이너리 코드 유사성에 대한 첫 번째 survey를 제시한다. 본 논문의 핵심은 다음 4가지 차원에서 61개의 바이너리 코드 유사성 접근 방식을 체계화했다: 사용 가능한 애플리케이션, 접근 방식 특성, 접근 방식이 구현되는 방식, 이를 평가하는 데 사용되는 벤치마크 및 평가 방법론. 다양한 접근 방식의 장점과 한계, 구현 및 평가에 대해 논의했다. 초보자와 전문가 모두에게 유용한 접근하기 쉬운 표로 결과를 요약했다. 또한, 이 분야의 발전에 대해 논의하고 여전히 남아있는 open challenge를 설명하여 해당 분야의 미래가 밝음을 보여주었다.
Uploaded by Notion2Tistory v1.1.0