Xu et al. Neural Network-based Graph Embedding for Cross-Platform Binary Code Similarity Detection. (CCS 2017) 요약

ABSTRACT

• cross-platfrom 바이너리 코드 유사성 탐지는 approximate graphmatching algorithms에 의존한다.
  • 이 방식은 느리고 정확하지않음
• 이에 신경망을 기반으로 바이너리 코드 유사성을 탐지하는 방법을 제안한다.
• 이를통해 취약한 펌웨어를 잘 식별하고 Deep learning for Security의 성공사례를 제시

INTRODUCTION

• 바이너리 코드 유사성 감지는 표절 감지, 악성 코드 감지, 취약점 검색 등 다양한 보안 응용 분야에서 활용되며 점점 바이너리 코드 유사성 감지가 주목받고 있음
  • 특히 IOT 펌웨어 이미지에서 취약점 검색은 매우 중요함
  • 단일 소스 코드 수준의 버그가 다양한 하드웨어 아키텍처와 소프트웨어 플랫폼을 가진 수백 개 이상의 기기에 퍼질 수 있기때문
  • 보안 전문가들은 여러 플랫폼(x86, ARM, MIPS 등)에서 이진 파일 내에서 빠르게 유사한 함수를 감지해야 하는 증가하는 필요성에 직면하고 있음
• 기존의 방식은 다음과 같음
  • 기존 : 플랫폼 독립적 특징 추출 → 제어흐름 그래프 표현 → 유사도 검출
  • Genius : 제어 흐름그래프에서 고수준 특징표현학습 → 임베딩으로 인코딩 (그래프 일치알고리즘에 의존)
• 기존의 방식(그래프 매칭 기반 접근방식)의 문제점
  • 고정된 그래프 매칭 알고리즘에 의해 근사된 유사성 함수는 다양한 응용 프로그램에 적응하기 어려움 (표절탐지 - 유사 / 취약점 탐지 - 다름) 수동으로 디자인된 유사성함수가 모두의 시나리오에 적합하지 X
  • 매우 느림 (super-linear runtime)
• 기여도는 아래와 같음
  • 바이너리 함수에 대한 embeddings(embeddings이란? 텍스트를 실수 벡터 형태(i.e. floating point 숫자들로 구성된 고정된 크기의 배열)로 표현한 결과물) 생성에 대한 최초의 신경망 기반 접근방식을 제안 ⇒ 빠르게 모델 재훈련가능
  • pre-trained model이 유사성 탐지에 사용할 임베딩을 생성할 수 있도록 Siamese 네트워크를 사용하여 임베딩 네트워크 훈련
  • Gemini(딥러닝기반) 프로토타입을 개발하여 Genius(그래프일치알고리즘) 보다 성능이 좋음을 보임

BINARY CODE SIMILARITY DETECTION

• cross-platform 간의 이진코드 탐색 문제에 대해
  • Binary only: 소스 코드에 대한 접근이 제한되는 경우가 많으므로 효과적인 유사성 감지 및 코드 검색 기술은 직접적으로 바이너리 코드에서 작동해야함
  • Cross-platform support: 다양한 하드웨어 아키텍처 및 소프트웨어 플랫폼에서 나올 수 있기 때문에 효과적인 바이너리 검색 기술은 다양한 플랫폼에서 도입된 문법적 변화를 허용하고 해당 바이너리 함수들의 본질적 특성을 포착
  • High precision & efficiency : 효과적인 바이너리 코드 유사성 검출기는 유사한 함수 쌍에 높은 점수를 할당하고 관련 없는 함수 쌍에는 낮은 점수를 할당해야 하고 대규모로 확장가능해야함
  • Adaptive : 도메인 전문가가 유사하거나 비슷하지 않은 예를 제공할 때 유사성 함수는 빠르게 이러한 예에 적응하여 도메인 특정 응용에 대응
• 기존의 바이너리 코드 매칭 및 검색
  • Pairwise Graph Matching ⇒ 대부분 단일 플랫폼
    • 각 기본 블록에 대한 입력-출력 쌍을 기능의 제어 흐름 그래프에서 추출하고 그래프 매칭을 수행 (비용이 매우 많이듬)
  • Graph Embedding ⇒ 시간이 오래걸림
    • 그래프 표현을 임베딩, 즉 숫자 특징 벡터로 변환 ⇒ 유사성 함수를 두 벡터 간의 쉬운 거리 함수로 계산
    • 특징 벡터는 지역 민감 해싱(LSH) 기반 데이터베이스를 사용하여 인덱싱될 수 있으므로 검색 쿼리를 O(1) 시간에 실행가능
    • 바이너리 함수(펌웨어 이미지 또는 알려진 취약점에서 나온)가 주어지면 먼저 속성화된 제어 흐름 그래프(ACFG) 형식의 원시 기능을 추출
    • a codebook and graph matching 에 시간이 매우 오래듬
      • 코드북 생성 : 각 컨트롤 흐름 패어그래프를 spectral clustering 해야함
      • 그래프 임베딩 : 그래프 임베딩의 속도는 코드북에 선형적으로 증가
• Neural Network-based Embedding Generation
  • ACFG를 임베딩하는 데 신경망 기반 접근 방식을 제안
  • 더 나은 정확도 : 신경망 기반 임베딩은 양분 그래프 매칭 및 Genius보다 훨씬 더 높은 정확도를 달성가능
    1. bipartite graph matching에 의존X : iteratively propagating embedding throughout the control flow graph
    2. 신경망의 매개변수는 자동으로 학습 : ACFG 임베딩 간의 거리를 유사하면 최소화 다르면 최대화. 딥러닝 → 재학습가능
  • 더 빠른 속도 :
    • Genius의 그래프 임베딩은 양분 그래프 매칭을 수행 → 우린 아님
      • 신경망 → 병렬화가능(다중코어 CPU & GPU)
    • 블록간 속성 필요 x - 이미 임베딩에 블록간 관계 정보 통합
  • 더 빠른 오프라인 : 재훈련가능

NEURAL NETWORK-BASED MODEL FOR

EMBEDDING GENERATION

• 임베딩을 이용하면 그래프 매칭 알고리즘을 사용하지않아 효율적으로 계산할 수 있음
  • embedding (i.e., the mapping ϕ)은 함수의 특징을 적절히 벡터로 표현한 것
  • 벡터로 표현하면 단순 숫자계산 문제가 되며 계산속도가 매우 빨라짐
• 사실 임베딩은 라벨정보가 필요한 분류 문제를 위해 설계됨 → 우리의 코드 유사성 임베딩은 분류문제가 아님
  • 따라서 예측(기존 접근방식)에 집중하는 것이 아닌 두 입력 attributed control flow graph(ACFG) 간의 유사성을 잘 구분할 수 있도록 집중하여 훈련
• 훈련방식 : 래프 쌍 д1,д2와 출력으로 ground truth π(f1, f2)만 감독을 받아 임베딩이 어떻게 생성되어야 하는지에 대한 추가 수작업 휴리스틱 없이 end-to-end로 훈련
  • Siamese 아키텍처 [7]를 설계하고 그래프 임베딩 네트워크 Structure2vec [13]를 내장
    • Siamese 아키텍처는 두 함수를 입력으로 받아 유사성 점수를 출력
    • 이로써 모델은 입력으로 그

EVALUATION

• 바이너리 함수의 임베딩 계산 → t-SNE로 2차원 평면에 투영
  • 동일한 소스 함수에서 컴파일된 바이너리 함수는 서로 가깝게 나타남
  • 서로다른 소스 함수에서 컴파일된 바이너리 함수는 서로 멀리 떨어져있음
  ⇒ 사전 훈련된 임베딩 함수가 대상 아키텍처, 사용되는 컴파일러 및 최적화 수준과 관계없이 임베딩에서 소스 함수의 정보를 보존할 수 있다는 것을 보여줌
• Gemini가 BGM 및 Genius 보다 ROC AUC 시간관점에서 더 좋음

RELATED WORK

• Raw feature based bug search → 크로스 아키텍처에서 사용불가
  • N-grams 또는 N-perms은 버그 검색을 위한 raw feature 초기의 두 접근 방식
    • 코드의 의미를 이해하지 않고 바이너리 시퀀스나 니모닉 코드 매칭을 채택하기 때문에 서로 다른 컴파일에 의한 opcode 재배열 문제를 감내할 수 없음
  • tracelet 기반 접근방식
    • 실행 순서 캡처 → opcode 변경문제 해결
  • TEDEM 블록에 대한 표현 트리 사용
  ⇒ but, opcode 및 레지스터 이름 기반은 아키텍처간 버그찾기에 적합하지X
• Graph embedding → 크로스 아키텍처에서 사용가능
  • Zynamics BinDiff[15]와 BinSlayer [6]는 코드 검색을 위해 제어 흐름 그래프 간 유사성을 측정하기 위해 비용이 많이 드는 그래프 동형성 알고리즘을 채택
  • BinHunt[20] 및 iBinHunt [29]에서 사용된 상징 실행 및 정리증명기는 방정식을 추출하고 동등성 검사를 수행해야 하므로 고의로 비용이 많이 듬
  • 이외에도 그래프 임베딩기반 접그닝 많이 있지만 비용을 줄이는 것이 매인이고 너무 오래걸리는 시간 극복이 어려움
• Deep learning-based graph embedding approaches
  • 그래프 임베딩?
    • 그래프의 노드를 임베딩 : 노드에서 벡터 공간으로의 맵을 찾아 그래프의 구조 정보를 보존
    • 전체 그래프를 나타내는 임베딩 벡터 찾기 : 해당 벡터에 대한 기계 학습 방법을 수행하여 단백질 설계 및 유전자 분석과 같은 작업을 처리가능

결론

• 바이너리 함수에 대한 임베딩 생성 → 딥러닝 적용
  • 유사성 탐지 정확도 증가
  • 임베딩 생성시간 단축
  • 전체 학습시간 단축