Robust Patch Analysis using Efficient Features and an Attention-based Siamese Classification Neural Network in Binary Executables

Abstract

패치 분석은 이진 실행 파일에서 패치된 콘텐츠를 탐색하는 역엔지니어링 기법이며 전통적 으로 취약성 검색, 1-day 공격(1-day exploit) 등과 같은 응용 프로그램에 사용된다. 바이너리 상에서 패치 분석을 위해서는 두 가지 다른 버전의 바이너리 실행 파일을 비교하고 패치/수 정된 함수를 찾아야 하며, 패치가 되지 않은 함수를 필터링해야 한다. 리버스 엔지니어링에 서 바이너리 디핑(binary diffing)은 두 바이너리 프로그램 사이의 기능 차이와 유사성을 발 견하는 프로세스이며, 전통적으로 패치 분석을 위한 최선의 선택으로 간주된다. 바이너리 디핑에 대한 기존 연구는 함수 매칭 문제로 접근하여 함수 간의 초기 1:1 매핑을 공식화하고, 나중에 시퀀스 매칭 비율을 계산하여 두 함수를 정확한 일치(패치되지 않음), 부분 일치(패 치됨) 또는 일치 없음(오류/새로운 함수)으로 분류한다. 패치 분석을 위한 경험적인 분석에 서, 본 연구는 기존 기술의 정확도는 정확한 일치를 감지할 때만 가장 우수하며 부분적으로 변경된 기능, 특히 CWE478, CWE476 등과 같은 사소한 패치가 있는 기능을 탐지하는 데에 는 효율적이지 않다는 것을 발견했다. 기존 연구가 이런 단점을 보이는 데에는 두 가지 이유가 있다: (i) 1:1 매핑 단계에서 함수의 특징을 일치시키기 위해 엄격한 정책이 사용되었다. 기존 연구는 일련의 휴리스 틱(heuristic)을 정의하고 순차적 방식으로 함수를 일치시키는 데 사용했다. 일부 휴리스틱 이 지나치게 신뢰되었고, 휴리스틱의 우선순위를 미리 설정해 둠으로써 많은 잘못된 일치 결과가 발생하였다. (ii) 분류 단계에서 어셈블리 스니펫(assembly snippet)을 일반 텍스트로 간주하고 유사성 비교를 위해 시퀀스 일치 알고리즘을 사용한다. 명령어는 독특한 구조를 가지고 있다. 즉, 니모닉(mnemonic)과 레지스터는 명령어에서 특정한 위치를 가지며, 또한 의미적 관계(semantic relationship)를 가지고 있다는 점에서 어셈블리 코드를 일반 텍스트 와 다르게 만든다. 경험적 분석에서, 본 연구는 패치 또는 컴파일러가 도입한 무작위성에 의 해 야기되는 작은 수준의 명령어 변경은 시퀀스 일치 알고리즘의 관점으로는 거의 동일하게 취급되는 것을 발견했다. 시퀀스 일치는 일반 텍스트에서는 효과적이지만, 명령어 수준에서 는 구조적 및 의미적 변화를 감지하지 못하므로 분류에 그냥 사용할 경우 많은 잘못된 결과 의 원인이 된다. 본 논문에서는 두 가지 솔루션을 제안함으로써 앞서 언급한 근본적인 문제를 해결했다. 첫 째, 1:1 매핑 단계를 위해, 업계 표준 도구인 Diaphora에서 사용하는 각 휴리스틱의 단점을 분석하고, 계산적으로 저렴한 특징 벡터(feature vector) 세트를 제안했으며, Diaphora의 휴 리스틱을 본 논문에서 함수 매핑 과정과 필터링 과정을 위해 제안한 거리 기 반(distance-based) 선정 기준과 비교하였다. 둘째, 분류 단계를 위해, 우리는 각 분기가 어텐 션(attention) 기반 분산 학습 내장 신경망인 샴 이진 분류 신경망을 제안했다. 이 네트워크는 어셈블리 명령어 간의 의미 유사성을 학습하고, 명령어 수준에서 실제로 발생한 변화를 강 조하는 방법을 배우고, 최종 단계에서는 완전 연결 계층(fully connected layer)을 통해 일치 하거나 부분적으로 일치하는 두 개의 1:1 매핑된 함수를 분류하는 것을 배우게 된다. 제안된 신경망은 명령어 수준에서 컴파일러로 인한 변경과 패치 기반 변경을 구별할 수 있을 정도 로 정교하다. 마지막으로, 제안된 1:1 매핑 단계와 분류 단계를 통합하는 효율적인 신경망 지 원 바이너리 디핑 알고리즘을 제안했다. 제안된 바이너리 디핑 알고리즘은 두 바이너리 함 수를 정확히 일치, 부분 일치 또는 일치 없음 상태로 정확하게 분류한다. 본 논문은 제안된 특징 벡터, 다양한 디자인 및 신경망의 매개 변수를 철저히 평가했다. 신경 망을 훈련시키기 위해, x86 XNU 커널 바이너리가 사용되었으며 커널 바이너리와 CWE 데 이터 세트에 대해 제안된 신경망 지원 바이너리 디핑 알고리즘을 평가했다. 본 논문의 알고 리즘은 기존 바이너리 디핑 기법과 툴보다 높은 ∼99%의 분류 정확도를 달성했다.|Patch analysis is a reverse engineering technique to explore the patched content in binary executables and traditionally it is being used for applications like vulnerability discovery, 1-day exploit generation, etc. For patch analysis at the binary level, we need to compare two different versions of a binary executable and find the functions that were patched/modified; while filtering the unpatched functions. In reverse engineering, binary diffing is a process to discover the differences and similarities in functionality between two binary programs and is traditionally considered the best choice for patch analysis. Previous research on binary diffing approaches it as a function matching problem to formulate an initial 1:1 mapping between functions, and later a sequence matching ratio is computed to classify two functions being an exact match (unpatched), a partial match (patched) or no-match (error/new functions). In our empirical analysis for patch analysis, we have discovered that the accuracy of existing techniques is best only when detecting exact matches and they are not efficient in detecting partially changed functions; especially those with minor patches like CWE478, CWE476, etc.

The drawbacks in existing research are due to two major challenges (i) In the 1:1 mapping phase, using a strict policy to match function features. Existing research defines a set of heuristics and uses them to match functions in a sequential manner. They have overtrusted some heuristics and prioritizing them produces many false matching results. (ii) In the classification phase, consider an assembly snippet as a normal text, and use a sequence matching algorithm for similarity comparison. Instruction has a unique structure i.e. mnemonics and registers have a specific position in instruction and also have a semantic relationship, which makes assembly code different from general text. In our empirical analysis, we have discovered that the small instruction-level changes either caused by a patch or a compiler introduced randomness are pretty much the same for a sequence matching algorithm. Sequence matching performs best for general text but it fails to detect structural and semantic changes at an instruction level thus, its use for classification produces many false results.

In this dissertation, we have addressed the aforementioned underlying challenges by proposing a two-fold solution. First, for the 1:1 mapping phase, we have empirically analyzed heuristics in Diaphora – an industrystandard tool, discovered drawbacks of each heuristic and proposed a set of computationally inexpensive feature vectors, which are later comparedwith a distance-based selection criteria to map similar functions and filter unmatched functions. Second, for the classification phase, we have proposed a Siamese binary-classification neural network where each branch is an attention-based distributed learning embedding neural network — that learn the semantic similarity among assembly instructions, learn to highlight the actual changes at an instruction level and a final stage fully connected layer learn to accurately classify two 1:1 mapped function either an exact or a partial match. The proposed neural network is sophisticated enough to differentiate between the compiler-caused and patched-based changes at an instruction level. Finally, we have proposed an efficient neural network-assisted binary diffing algorithm that is an integration of our proposed 1:1 mapping phase and the classification phase. The proposed binary diffing algorithm accurately classifies the two binary functions being exact match, partial, or no-match.

We have thoroughly evaluated the proposed feature vectors, different design choices, and parameters of the neural network. For training the neural network, we have used x86 XNU kernel binaries and evaluated the proposed neural network-assisted binary diffing algorithm on kernel binaries (not included in training) and the CWE dataset. We have achieved ∼99% classification accuracy; which is higher than existing binary diffing techniques and tools.