Chương 1: Giới thiệu tổng quan đề tài và các hướng nghiên cứu liên quan 6 e Chương 2: Trình bày cơ sở lý thuyết các kiến thức liên quan đến đề tài e Chương 3: Trình bày mô hình fuzzing kết hợp hợp concolic execution và học tăng cường sâu e Chương 4: Trình bày kết quả thực nghiệm và các đánh giá liên quan e Chương 5: Kết luận và trình bày những hướng phát triển của đề tài CHƯƠNG 2. CƠ SỞ LÝ THUYET Ở chương này, chúng tôi trình bày cơ sở lý thuyết và những kiến thức liên quan của nghiên cứu, bao gồm Fuzzing, Concolic Execution và Phương pháp học máy tăng cường sâu. Khai niệm Fuzzing Fuzzing là một phương pháp tự động hóa kiểm thử thông qua việc đưa vào chương trình các bộ đầu vào ngẫu nhiên, không hợp lệ so với đầu vào mong muốn của chương trình nhằm kích hoạt được những dòng mã tiềm ẩn của chương trình từ đó tăng được độ bao phủ các nhánh mã cũng như khai thác các lỗ hồng của chương trình đang được kiểm thử, đặc biệt là các lỗ hong về bộ nhớ (memory corruption). Fuzzing được giới thiệu bởi Miller và cộng sự vào năm 1990 [14], đến nay đã phát triển và trở thành phương pháp đáng tin cậy để dò tìm lỗ hong phần mềm bởi mức độ hiệu quả mà nó mang lại.
Fuzzing hoạt động bằng cách cung cấp cho chương trình vô số các đầu vào với mục đích gây nên lỗi chương trình. Chính vì vậy, điểm cốt lõi của một trình fuzzing là phương thức sinh đầu vào có khả năng khiến chương trình mục tiêu thực thi nhiều đoạn mã và tạo ra các ngoại lệ trái với mục đích ban đầu của người lập trình. Độ phủ ma Khi kiểm thử chương trình, ngoài lỗ hổng tìm được, ta còn quan tâm đến lượng mã lệnh trong chương trình đã được thực thi. Đây được gọi là độ phủ 8 mã.
Độ phủ mã là yếu tố thường được sử dung để đánh giá hiệu năng của trình fuzzing sau số lượng lỗi phát hiện được với ý tưởng rằng độ phủ mã tỉ lệ thuận với số lỗi tìm được. Độ phủ mã thường được đo lường bằng cách chèn các đoạn mã đánh dấu trong chương trình nhằm xác định chương trình đã đi qua một đoạn lệnh nhất định hay chưa. Các trình fuzzing hiện nay còn dùng độ phủ mã để tạo ra các đầu vào hướng luồng thực thi chương trình đến một đoạn mã nhất định. Greuboz fuzzing (Coverage-guided fuzzing) Các phương pháp fuzzing có thể được phan loại theo nhiều cách: theo phương thức sinh đầu vào, theo mức độ nhận thức cấu trúc đầu vào hoặc theo mức độ nhận thức về cấu trúc của chương trình được kiểm thử.
Theo mức độ nhận thức về cấu trúc của chương trình mục tiêu, các phương pháp fuzzing được chia thành 3 nhóm: e Blackbox fuzzing: Nhóm phương pháp này được sử dụng khi ta không có nhiều thông tin về đối tượng kiểm thử. Các trình fuzzing thuộc nhóm này xem chương trình mục tiêu là một hộp đen (blackbox) và phụ thuộc vào việc quan sát hành vi của chương trình để tạo ra các bộ đầu vào mới. Blackbox fuzzing không tiêu tốn nhiều tài nguyên và có thé dé dàng được triển khai, nhưng phương pháp này khó có thể khai thác được các lỗ hổng phức tạp, cần sự hiểu biết sâu về chương trình mục tiêu. e Whitebox fuzzing: Nhóm phương pháp này được sử dụng khi ta có toàn quyền truy cập đến cau trúc thiết kế và mã nguồn của chương trình.
Điều này tạo điều kiện cho các phương pháp phân tích, đánh giá và xác định các vùng mã tiềm tàng lỗi để sinh các bộ đầu vào có khả năng hướng luồng thực thi đến các vùng mã này. Whitebox fuzzing có khả năng khai thác được các lỗ hổng phức tạp vốn không thể được khai thác bởi Blackbox fuzzing nhưng cần nhiều tài nguyên để phân tích chương trình đang được kiểm thử. Đại 9 diện cho nhóm phương pháp này gồm: SAGE [7], BuzzFuzz [6], KLUZZER [10],. e Greybox fuzzing: Nhóm phương pháp này kết hợp các đặc điểm của Blackbox và Whitebox fuzzing, thường được sử dụng khi ta có một phần thông tin về đối tượng kiểm thử đủ để cho phép một hướng tiếp cận nhắm đến mục tiêu kiểm thử hơn so với Blackbox fuzzing nhưng cũng không quá nặng về mặt phân tích chương trình như Whitebox fuzzing.
Greybox fuzzing có khả năng tạo ra các đầu vào nhắm đến một mục tiêu nhất định trong chương trình để cải thiện độ phủ mã cũng như số lượng lỗ hồng khai thác được mà không tiêu tốn quá nhiều tài nguyên tính toán. Tiêu biểu cho nhóm phương pháp này bao gồm: AFL [19], libFuzzer, Honggfuzz,. Greybox fuzzing không phụ thuộc vào các kỹ thuật phân tích chương trình như Symbolic Execution [9] hay Taint Analysis [15]. Thay vào đó, Greybox fuzzing thực hiện chèn các điểm đánh dẫu (instrumentation) vào các khối mã nhằm theo dõi quá trình thực thi của chương trình và đánh giá độ phủ mã (code coverage) của chương trình dưới một đầu vào nhất định.
Các đầu vào tao ra được trạng thái mới (ví dụ: thực thi được một đoạn mã mới, .) cho chương trình sẽ được lưu lại vào hàng đợi và được sử dụng trong các lượt fuzz sau. Các đầu vào không đem lại trạng thái mới sẽ được bỏ qua. Đây được gọi là Coverage-guided fuzzing. Khối cơ ban - Basic block Khối cơ ban (Basic block) định nghĩa một đoạn mã bao gồm một điểm bắt đầu (Entry point) và một điểm kết thúc (Exit point) trong đó không tồn tại bất kì lệnh rẽ nhánh nào khác ngoài điểm kết thúc và không tồn tại đích đến rẽ nhánh nào khác ngoài điểm bắt đầu.
Các trình greybox fuzzing chèn các điểm đánh dấu tại các lệnh rẽ nhánh hoặc đầu các khối cơ bản để theo vết luồng thực thi và xác định độ phủ mã của 10 chương trình khi nhận vào một đầu vào nhất định. Symbolic Execution Symbolic execution là một phương pháp thực thi chương trình sử dung các giá trị tượng trưng (symbolic value) thay cho các giá trị cụ thể (concrete value). Các giá trị đầu vào và các biến sẽ được thể hiện dưới dạng biểu thức đại diện cho các điều kiện ràng buộc nhánh của một đường thực thi trong chương trình (path constraints). Bằng cách giải các điều kiện ràng buộc này, symbolic execution có thể tạo ra các đầu vào hướng luồng thực thi đến một đoạn mã mục tiêu nhất định.
Xem xét đoạn mã nguồn bên dưới: BFoDWN&PO int x 0, y = 0; if (a < 5) { x II à } if (a && !b) yry- 2i assert(x + y == -1); Chon một đường thực thi của chương trình trên, ta sé theo dõi giá tri của các biến (có thể là cụ thể hoặc tượng trưng) cũng như các điều kiện ràng buộc để có thể thực thi được đường thực thi đã chọn. Với ø =a và b= Ø (a và Ø là giá trị tượng trưng), bảng 2.1 thống kê giá trị các biến và điều kiện ràng buộc để câu lệnh assert tại dòng 7 trả về true: Sau khi đã xác định được các ràng buộc của đường thực thi, một trình giải các giá trị ràng buộc này sẽ được sử dụng để tìm ra các giá trị cụ thể thỏa mãn được các điều kiện này nhằm hướng luồng thực thi của chương trình đến đoạn mã mục tiêu. 11 Dòng | Ràng buộc đường thực thi Giá trị của biến 0 | true ara, bw 8 1 | true ., FH0,yH0 2}a<5 2H 0,yH 0 5|œ<ð A œ#0 A ¬8 FH Ì, r>0 7|œ<5 A œZ0 A ABA 1+(-2)=-—l1|.1: Ví dụ vé symbolic execution 2. Concolic Execution Symbolic execution hiệu quả trong việc tìm các đầu vào thỏa mãn một đường thực thi nhất định.
Tuy nhiên phương pháp này có những hạn chế. Đối với các đường thực thi dài bao gồm nhiều câu lệnh điều kiện, bộ giải ràng buộc sẽ khó có thể giải các ràng buộc điều kiện và tìm ra giá trị thỏa mãn đường thực thi đang được xét. Diều này cũng xảy ra tương tự đối với các đường thực thi ngắn nhưng chứa các phép tính nằm ngoài khả năng tính toán của bộ giải ràng buộc như các hàm mật mã học hay các hàm toán học phi tuyến tính. Concolic execution có thể giải quyết những vấn đề này bằng cách kết hợp symbolic execution với concrete execution (thực thi sử dụng giá trị cụ thể).
Các giá tri cụ thể sẽ được sử dụng để thực thi chương trình. Tại các điểm rẽ nhánh, nếu giá trị cụ thể được sử dụng không thỏa mãn điều kiện rẽ nhánh dẫn đến đoạn mã cần thực thi, điều kiện của nhánh rẽ ngược lại sẽ được ghi nhận và symbolic execution sẽ được thực hiện theo nhánh rẽ này. Xem xét đoạn mã nguồn bên dưới: 1 weird_assert(int x, int y) { 2 if complex_func(x) == y { 3 ERROR ; 4 } else { 5 // OK 6 } 7 } 12 Xem hàm complex_ func là một hàm phức tap mà bộ giải ràng buộc không thể thỏa mãn. Thay vì tính toán giá trị x và y để thỏa mãn nhánh điều kiện dẫn đến ERROR, một giá trị cu thể sẽ được sử dụng cho x.
Lúc này Symbolic execution chỉ cần tìm giá trị y phù hợp để thỏa mãn nhánh điều kiện trên và dẫn chương trình đến dòng lệnh ERROR. Concolic execution giải quyết được van đề quá tai tính toán 6 symbolic exe- cution, giúp cho quá trình tìm đầu vào diễn ra nhanh hơn và hiệu quả hơn. Phương pháp học máy tăng cường sâu 2. Hoc may tăng cường - Reinforcement Learning 2.
Quy trinh quyét dinh Markov - Markov Decision Process Quy trình quyết định Markov (MDP) là một cấu trúc được sử dung để mô hình hóa bài toán lựa chọn quyết định trong các môi trường nhất định. Các kết quả nhận được từ môi trường có tính xác suất và phụ thuộc vào hành động đã được lựa chọn. Một MDP bao gồm các thành phần sau: e State S: Không gian các trạng thai của môi trường e Action A: Không gian các hành động có thể thực hiện trong môi trường e Transition probability P,(s;, 5:41): Ti lệ dé hanh động a tai trạng thai s¿ dan đến trang thái s;41 e Immediate reward R,(5;, 5:41): Phan thưởng nhận được khi môi trường chuyển từ trạng thái s; sang s;,, dưới hành động a 2. Khái niệm học máu tăng cường Học máy tăng cường (Reinforcement Learning) là một một nhánh của lĩnh vực may học.
Phương pháp học máy tăng cường dựa trên phương thức học thông 13 qua phan hồi, được mô hình hóa theo MDP, trong đó, một Tác tử (Agent) sẽ tương tác với Môi trường (Environment) bằng Hành động ø (Action) tại một Trạng thái s (State) và nhận lại phản hồi dưới hình thức là Phần thưởng r (Reward), từ đó học được hành động tối ưu nhất ở từng trạng thái.