# How Machine Learning Is Solving the Binary Function Similarity Problem ## I. Student Information |STT | MSSV | Họ và tên | Email | | --- | -------- | -------- | -------- | | 1 | 20120028 | Huỳnh Lê An | 20120028@student.hcmus.edu.vn | | 2 | 20120081 | Nguyễn Mậu Trọng Hiếu | 20120081@student.hcmus.edu.vn | | 3 | 20120599 | Phù Thị Kim Trang | 20120599@student.hcmus.edu.vn | ## II. The Binary Function Similarity Problem ### 1. Phát biểu bài toán Binary function similarity (tương đồng hàm nhị phân) là bài toán mà: + Input: Biểu diễn nhị phân của một cặp hàm. + Output: Một giá trị số để mô tả "sự tương đồng" giữa chúng. Giá trị similarity thường là số thực có giá trị trong đoạn [0, 1]. Nếu giá trị similarity càng gần 1 thì độ tương đồng giữa 2 đoạn mã càng lớn, và ngược lại. Similarity và Distance là hai khái niệm đối nghịch nhau, thường được sử dụng để đo lường mức độ tương đồng hoặc khác biệt giữa hai đối tượng. #### Ví dụ Dưới đây là một ví dụ đơn giản, cụ thể về Binary function similarity: Cho hai hàm nhị phân sau đây: Hàm f: 1010 1011 Hàm g: 1011 1010 Để xác định sự tương đồng giữa hai hàm này, chúng ta có thể sử dụng các phương pháp như khoảng cách Hamming (số bit khác nhau giữa 2 hàm). Ta thấy có bit thứ 4 và thứ 8 của 2 hàm là khác nhau, nên Hamming distance sẽ là 2. Vậy thì độ tương đồng giữa 2 hàm này là: $$1 - \frac{2}{8} = 1 - 0.25 = 0.75$$ Điều này có nghĩa là hai hàm có mức độ tương đồng khoảng 75%. #### Nhận xét về kết quả Kết quả đo lường tương đồng 0.75 cho thấy hai hàm có mức độ tương đồng lớn, nhưng không cung cấp thông tin chi tiết về sự khác biệt. Để có một cái nhìn đầy đủ hơn về tương đồng, ta có sử dụng các phương pháp và công cụ khác để phân tích và so sánh hai hàm nhị phân này. <!-- ## The Binary Function Similarity Problem Định nghĩa 'similarity' trong binary function similarity còn tùy thuộc vào hoàn cảnh như compiler, version, kiến trúc thực thi (ARM, x86,...). Đây là thách thức trong việc so sánh giữa các binary functions. --> ### 2. Measuring Function Similarity <!-- Giới thiệu các phương pháp đo lường sự tương đồng giữa hai hàm nhị phân. Trình bày các tiêu chí và phép đo tương đồng phổ biến, ví dụ: khoảng cách Hamming, tương đồng cosin, v.v. --> Các phương pháp đo lường sự tương đồng giữa các hàm nhị phân được chia làm 2 loại chính: + **So sánh trực tiếp:** So sánh dựa trên dữ liệu thô hoặc trích xuất đặc trưng của các hàm. Có nhiều phương pháp và mô hình máy học được sử dụng, bao gồm Bayesian networks, Convolutional Neural Networks (CNN), Graph Matching Networks (GMN), hay các mô hình kết hợp. + **So sánh gián tiếp:** Ánh xạ đặc trưng vào không gian chiều thấp để dễ dàng so sánh bằng các độ đo khoảng cách(Euclide hoặc cosine). Sử dụng fuzzy hashes và embeddings là hai phương pháp phổ biến. + **Fuzzy Hashes**: Khác với các băm mật mã truyền thống, fuzzy hashes được thiết kế một cách cố ý để ánh xạ các giá trị tương tự thành các giá trị băm tương tự. Fuzzy hashes thông thường không phù hợp để so sánh tính tương đồng của các hàm, tuy nhiên một số phương pháp (như FunctionSimSearch) đã đề xuất các kỹ thuật băm chuyên dụng để so sánh hai hàm. + **Embeddings**: Trong ngữ cảnh của tính tương đồng hàm, embeddings tạo ra một không gian chiều thấp, trong đó các giá trị đầu vào có ý nghĩa tương tự được ánh xạ gần nhau, bất kể sự khác biệt ban đầu giữa chúng. Mục tiêu của các mô hình học máy là học cách tạo ra embeddings tối đa hóa tính tương đồng giữa các hàm tương tự và giảm thiểu tính tương đồng với các hàm khác. + **Code embeddings**: Sử dụng kỹ thuật xử lý ngôn ngữ tự nhiên để xem mã lắp ráp như văn bản. Các phương pháp này xử lý chuỗi các "token" trong mã và tạo ra embeddings cho các khối mã hoặc lệnh. + Phương pháp Asm2Vec và word2vec được sử dụng để học cú pháp của các ngôn ngữ khác nhau hoặc ngôn ngữ trung gian. + Các mô hình seq2seq encoder-decoder hoặc BERT transformer được sử dụng để ánh xạ ý nghĩa từ các kiến trúc khác nhau vào cùng một không gian embeddings. + **Graph embeddings**: Được dùng để tính toán biểu diễn cho đồ thị điều khiển của các hàm. Các phương pháp bao gồm Graph Neural Network (GNN) và các biến thể như GMN. Các embeddings này mã hóa thông tin từ các khối cơ bản vào các nút trong đồ thị. ### 3. Function Representations **Binary functions (hàm nhị phân)** về cơ bản là các luồng byte tương ứng với dữ liệu và mã máy dành riêng cho một kiến trúc cụ thể nào đó. Bắt đầu từ raw input, có rất nhiều cách để trích xuất đặc trưng cấp cao để giúp ích cho việc phân biệt 2 hàm bất kì có đến từ cùng source code. Danh sách các phương pháp được trình bày dưới đây được sắp xếp theo chiều tăng dần của tính trừu tượng, tổng quát (abstraction): * **Raw bytes**: Trực tiếp sử dụng thông tin raw binary để đo đạc tính tương đồng hoặc kết hợp nó với thông tin khác từ đồ thị luồng điều khiển(CFG) hoặc call graph(CG). + **Assembly**: Các lệnh hợp ngữ thu được từ quá trình giải hợp ngữ có thể hữu ích khi các hoạt động có thể được mã hóa theo nhiều cách khác nhau tùy thuộc vào kích thước lệnh hoặc toán hạng. + **Normalized assembly**: đơn giản hóa và tiêu chuẩn hóa hợp ngữ bằng cách giảm biến thiên do các giá trị hằng số, từ đó tạo ra một biểu diễn duy nhất cho các hoạt động tương tự. + **Biểu diễn trung gian(IR)**: Các phương pháp sử dụng IR để đạt mức trừu tượng cao hơn, thống nhất biểu diễn và áp dụng kỹ thuật phân tích chương trình để đơn giản hóa mã. + **Structure**: Nhiều phương pháp tiếp cận cấu trúc nội bộ của một hàm (ví dụ như trích xuất Control-Flow Graph (CFG)) hoặc vai trò của một hàm trong toàn chương trình. + **Phân tích luồng dữ liệu**: Phương pháp để xem xét cách mà biểu thức số học được thực hiện trong hợp ngữ. + **Phân tích động**: Liên quan đến việc thực thi các hàm và phân tích mối quan hệ giữa đầu vào và đầu ra. + **Thực thi và phân tích tượng trưng**: Để hiểu rõ hành vi của hàm và quan hệ giữa đầu vào và đầu ra trên tất cả các đường đi có thể ## III. Selected Approaches <!-- Trình bày các phương pháp tiếp cận được lựa chọn để giải quyết vấn đề. Mô tả cách thức hoạt động và ưu điểm của mỗi phương pháp. Các phương pháp có thể bao gồm: bảng chân trị, thuật toán tối ưu hóa, phép đo tương tự dựa trên chuỗi bit, v.v. --> ### 1. Các tiêu chí lựa chọn phương pháp **Khả năng mở rộng và ứng dụng trong thế giới thực** + Lựa chọn phương pháp có khả năng xử lý trên lượng dữ liệu lớn trong thời gian cho phép, cho phép áp dụng phương pháp trong các bài toán thực tiễn. Do đó, không đánh giá cao cách tiếp cận dựa trên so sánh trực tiếp, hoặc quá chậm, quá phức tạp. **Tập trung vào các phương phát tổng quát** + Có nhiều bài báo chỉ tập trung giải quyết bài toán tổng quát trong một trường hợp cụ thể, điều này ảnh hưởng đến kết quả so sánh. **Tham khảo từ nhiều diễn đàn** + Thông thường, những nghiên cứu về binary similarity chỉ được so sánh với các phương pháp cải tiến đến từ cùng cộng đồng (học thuật hoặc công nghiệp), hoặc cùng tác giả. Do đó, để đảm bảo tính chính xác, chúng tôi sẽ so sánh từ tất cả các nguồn. **Ưu tiên những xu hướng mới nhất** + Việc áp dụng phương pháp học máy giúp tạo hiệu suất vượt trội so với các phương pháp trước đây. Do đó, chúng tôi ưu tiên những phương pháp hiện tại. ### 2. Các phương pháp **Bytes fuzzy hashing: Catalog1** <!-- ##### a. Cách thức hoạt động --> Giả sử $a$, $b$ là hai chuỗi cần so sánh. Gọi $S(a)$, $S(b)$ là chuỗi con tạo bởi 4 phần từ liên tiếp bởi $a$, $b$. VD: $a=123xy$ $S(a) = {123x, 23xy, 3xy1}$ Tương tự với $S(b)$. Giá trị tương đồng của $a$, $b$ được tính với công thức: $$similarity = \frac{S(a) \cap S(b)}{S(a) \cup S(b)}$$ Giá trị này được gọi là hệ số giống nhau Jaccard của hai tập $S(a)$ và $S(b)$. Nếu $similarity = 1$ thì $a$ và $b$ hoàn toàn giống nhau. Ngược lại, nếu $similarity = 0$ thì không có sự giống nhau giữa chúng. <!-- ##### b. Ưu điểm --> <!-- ##### c. Nhược điểm --> Vì chỉ xem xét các chuỗi con liên tiếp gồm 4 phần tử từ hai chuỗi đầu vào nên xảy ra tình trạng mất mát thông tin, ví dụ: các phần tử không liên tiếp, không tuân theo quy tắc chuỗi con 4 phần tử... **CFG fuzzy hashing: FunctionSimSearch** <!-- #### 1. Cách thức hoạt động --> Sử dụng SimHash để tính toán hàm fuzzy hash của những đồ thị được trích xuất từ CFG (Control FLow Graph). <!-- #### 2. Ưu điểm --> Phương pháp này có thể so sánh các hàm với các cấu trúc khác nhau dựa trên cấu trúc CFG. <!-- #### 3. Nhược điểm --> <!-- Độ phức tạp tính toán cao: Thuật toán yêu cầu tạo ra tất cả các chuỗi con liên tiếp và tính toán tương đồng. --> **Attributed CFG and GNN: Gemini** <!-- #### 1. Cách thức hoạt động --> Sử dụng GNN (Graph neural network) tính toán vector hàm dựa trên CFG (Control flow graph). <!-- #### 2. Ưu điểm --> Là phương pháp đầu tiên kết hợp GNN với kiến trúc Siamese trong học máy, cải tiến rất lớn so với ACFG (Attributed control flow graph) và tốt hơn so với các phương pháp sử dụng CFG như Bingo, Binsign, Kam1no, Tracy,... <!-- #### 3. Nhược điểm --> **Attributed CFG, GNN, and GMN: Li et al. 2019** <!-- #### 1. Cách thức hoạt động --> Sử dụng phương pháp mô hình khớp đồ thị trong học máy để tính toán sự giống nhau giữa các cặp đồ thị. <!-- #### 2. Ưu điểm --> Đề xuất mô hình mới tốt hơn so với mô hình nhúng đồ thị. Phương pháp thực hiện so sánh tất cả đồ thị ở mọi cấp thay vì nhúng từng đồ thị đồ lập. Tuy nhiên, điều này sẽ tăng chi phí tính toán. <!-- #### 3. Nhược điểm --> **IR, data flow analysis and neural network: Zeek** <!-- #### 1. Cách thức hoạt động --> Phương pháp này thực hiện theo các bước sau: + Chia hàm thành những blocks nhỏ. + Phân ra blocks thành các strands. + Chuyển mã thành các lệnh cụ thể + Sử dụng b-bit MD5 tính toán giá trị cụ thể của strands và xây dựng vector biểu diễn. ![](https://hackmd.io/_uploads/H1xJ0sFP2.png) <!-- #### 2. Ưu điểm --> Có độ chính xác cao và ứng dụng được trong các bài toán thực tế. <!-- #### 3. Nhược điểm --> **Assembly code embedding: Asm2Vec** <!-- #### 1. Cách thức hoạt động --> + Với tập các hàm hợp ngữ, xây dựng mạng nơ ron cho chúng. Chúng ta chỉ cần nội dung hàm mà không cần bất kỳ thông tin cho trước. + Sau khi huấn luyện mạng nơ ron, mô hình sẽ đưa ra tập hợp các vector tương ứng với từng hàm hợp ngữ. + Sau đó, thực hiện so sánh tập vector được tạo với tập vector của các hàm cần kiểm tra băng phương pháp cosine để lấy kết quả. ![](https://hackmd.io/_uploads/SJzIc-cPh.png) Mô hình mạng Asm2Vec cho hợp ngữ Asm2Vec chỉ được thiết kế cho hợp ngữ và chưa thể áp dụng trực tiếp trên nhiều kiến trúc. Hơn nữa, Asm2Vec chưa thể giải thích cho người dùng kết quả trả ra. <!-- #### 2. Ưu điểm --> <!-- #### 3. Nhược điểm --> **Assembly code embedding and self-attentive encoder: SAFE** <!-- #### 1. Cách thức hoạt động --> SAFE được thiết kế từ mạng Self-Attentive dựa trên các ưu điểm của ngành NLP (natural language processing). + Sử dụng i2V(là mô hình word2vec) để chuyển các hàm hợp ngữ thành tập vector. + Sử dụng mạng Self-Attentive để huấn luyện với đầu vào là tập vector. ![](https://hackmd.io/_uploads/B1JuxP5w3.png) SAFE có thể tính toán trên đa nền tảng. So với giải pháp trước đó, phương pháp không sử dụng CFG do đó tăng tốc độ tính toán. <!-- #### 2. Ưu điểm --> <!-- #### 3. Nhược điểm --> **Assembly code embedding, CFG and GNN: Massarelli et al. 2019** <!-- #### 1. Cách thức hoạt động --> Bao gồm 2 phần chính là: + Vertex Feature Extraction có nhiệm vụ nối những vector đặc trưng với những đỉnh g trong mạng CFG. + Structure2Vec có nhiệm vụ huấn luyện mạng với đầu vào là vector đặc trưng để tạo ra vector nhúng của g. ![](https://hackmd.io/_uploads/rJQ_yucwh.png) <!-- ##### 2. Ưu điểm --> <!-- ##### 3. Nhược điểm --> #### CodeCMR/BinaryAI <!-- ##### 1. Cách thức hoạt động --> Mã nguồn và mã nhị phân nhúng cần ba dữ liệu đầu vào: ngữ nghĩa, chuỗi và số nguyên. Sau đó, dùng kết quả từ mã nguồn và mã nhị phân để huấn luyện hệ số của mạng nơ ron, sử dụng hàm triple loss để tính toán kết quả. ![](https://hackmd.io/_uploads/HJvIMT5wn.png) Mô hình DPCNN ![](https://hackmd.io/_uploads/rJH6GGjv3.png) <!-- ##### 2. Ưu điểm --> <!-- ##### 3. Nhược điểm --> #### Trex <!-- ##### 1. Cách thức hoạt động --> + Đầu tiên, sử dụng mô hình masked LM với dữ liệu đầu vào assembly code và dynamic code bằng hàm micro-traces. + Sau đó, tinh chỉnh mô hình bằng cách xếp chồng những lớp mạng nơ ron mới. + Nối hai mô hình đã tạo với nhau, lúc này mô hình sẽ tính toán giá trị giống nhau của hàm. ![](https://hackmd.io/_uploads/HkU0j1sD3.png) <!-- ##### 2. Ưu điểm --> <!-- ##### 3. Nhược điểm --> ## IV. Evaluation ### Implementation - Phân tích nhị phân (binary analysis): IDA Pro 7.3. IDA Pro, hay Interactive Disassembler, là một trình dịch mã ngược (disassembler) dành cho phần mềm máy tính, nó chuyển đổi chương trình nhị phân thành hợp ngữ. - Để xây dựng mô hình deep learning: Tensorflow, PyTorch. - Gensim là một thư viện Python mã nguồn mở dành cho mô hình không gian vector. Tác giả dùng Gensim để cài đặt Asm2Vec - chuyển từ assembly code sang vector đặc trưng. - Cấu hình: Ubuntu 18.04, Intel Xeon Gold 6230 (80 virtual cores @2.10 GHz), 128GB DDR4 RAM, and one Nvidia RTX2080 Ti GPU (1350MHz, 11GB GDDR6, 13.45 TFLOPS FP32). ### Dataset Tác giả tạo ra 2 tập dataset: Dataset-1 and Dataset-2 để đánh giá các mô hình. Để có thể tạo ra tập dataset giống với phần mềm ngoài thực tế (real-world software), có đầy đủ các thử thách thì cần: - Multiple compiler families and versions. - Multiple compiler optimizations. - Multiple architectures and bitnesses. - Software of different nature (command line utilities vs. GUI applications) Tác giả dùng Dataset-1 để train machine-learning models và dùng cả 2 datasets để test các phương pháp. ### Result ![](https://hackmd.io/_uploads/rk76bgjwh.jpg) Ta có thể rút ra những nhận xét sau: - GMN, GNN outperform - đạt điểm số cao hơn các phương pháp còn lại. - Các embeddings-based models như [45, 49, 60, 76] thì có kết quả thấp hơn GMN, GNN và gần ngang nhau. - Asm2Vec không cho kết quả tốt hơn các phương pháp khác. - Những phương pháp fuzzy hashing không hiệu quả khi nhiều compilation variables (biến của trình biên dịch) cùng lúc thay đổi. #### ## V. Discussion ### Những đóng góp chính của các giải pháp học máy mới so với các phương pháp băm mờ đơn giản là gì? Các mô hình học sâu cung cấp một cách hiệu quả để học một biểu diễn hàm (embedding), tạo sự phân cách không gian giữa các lớp hàm khác nhau. Khác với các phương pháp băm mờ (fuzzy hashing), các mô hình học máy đạt được độ chính xác cao ngay cả khi nhiều biến dịch cùng lúc thay đổi và chúng được hưởng lợi từ ưu điểm của các bộ dữ liệu huấn luyện lớn được xây dựng trên cơ sở một sự thật đáng tin cậy được xác định bởi các tùy chọn biên dịch. Việc sử dụng kiến trúc Siamese [40, 45, 49, 76] kết hợp với margin based loss [40, 79] đã mang lại những cải tiến đáng kể trong kết quả. Hơn nữa, GNNs [40, 45, 76, 79] là một bộ mã hóa hàm hiệu quả có thể được sử dụng kết hợp với các bộ mã hóa cấp độ chỉ dẫn khác [45, 79]. ### Các phương pháp khác nhau có hoạt động tốt hơn với những công việc khác nhau không? Việc so sánh giữa các kiến trúc có khó khăn hơn việc làm việc với một kiến trúc duy nhất không? Tác giả bài báo cho rằng hầu hết các mô hình học máy hoạt động rất tương tự trên tất cả các task được đánh giá, kể cả dù giống hay khác kiến trúc. Hơn nữa, không cần thiết phải huấn luyện chúng cho một task cụ thể, vì việc sử dụng dữ liệu phổ quát nhất (XM) cho phép đạt được hiệu suất tổng thể gần nhất với mỗi task riêng biệt. Điều này không đúng với các phương pháp băm mờ. **XM**: tập data gồm các cặp hàm đến từ các kiến trúc, bitness (32-bit hay 64-bit), trình biên dịch, phiên bản trình biên dịch và tối ưu hóa tùy ý. ### Còn hướng nghiên cứu hứa hẹn nào để thiết kế các kỹ thuật, phương pháp mới không? Kết quả cho thấy các mô hình học sâu đáp ứng được yêu cầu về khả năng mở rộng và độ chính xác cho các nhiệm vụ function similarity khác nhau, đặc biệt là do khả năng học một biểu diễn hàm phù hợp cho nhiều nhiệm vụ. Mặc dù các mô hình GNN đã cung cấp kết quả tốt nhất, nhưng có hàng chục biến thể khác nhau cần được kiểm tra. Hơn nữa, tác giả đã quan sát thấy rằng việc lựa chọn các đặc trưng và mô hình học máy không phải là những khía cạnh duy nhất ảnh hưởng đến hiệu suất của một phương pháp. Một số khía cạnh như training strategy và loss function chỉ mới được quan tâm gần đây. ## VI. Conclusions Paper này là thực hiện nghiên cứu đo lường đầu tiên bao gồm hơn năm năm công trình nghiên cứu giải quyết vấn đề function similarity. Tác giả đã nêu ra các thách thức trong lĩnh vực nghiên cứu, các khó khăn giữa việc so sánh các phương pháp với nhau. Bài viết này chính là cầu nối giúp cộng đồng hiểu rõ hơn về lĩnh vực nghiên cứu này. Tác giả hi vọng với bài viết, các dataset, code được công bố sẽ giúp cho mọi người có một khởi đầu tốt khi bắt đầu nghiên cứu về bài toán function similarity. ## Reference Marcelli, Andrea, et al. "How machine learning is solving the binary function similarity problem." 31st USENIX Security Symposium (USENIX Security 22). 2022.