| Title | In-depth Testing of x86 Instruction Disassemblers with Feedback Controlled DFS Algorithm |
| Authors | Wang, Guang Zhu, Ziyuan Cheng, Xu Meng, Dan |
| Affiliation | Chinese Acad Sci, Inst Informat Engn, Beijing, Peoples R China Univ Chinese Acad Sci, Sch Cyber Secur, Beijing, Peoples R China Peking Univ, Dept Mech Engn, Beijing, Peoples R China |
| Issue Date | 2022 |
| Publisher | 2022 IEEE 40TH INTERNATIONAL CONFERENCE ON COMPUTER DESIGN (ICCD 2022) |
| Abstract | Instruction disassemblers can be used for software reverse engineering, malware analysis, and undocumented instructions detection. However, flaws in the disassemblers directly affect the accuracy of its related applications. For example, if the disassembler fails to decode or misdecodes the binary code of malware, the reverse engineers may misinterpret the functionality of the malware. Therefore, it is necessary to systematically test the disassemblers. Existing works leverage the depth-first search (DFS) algorithm to search the x86 instruction space. However, they cannot cover all x86 instruction opcodes and register operands. The root cause is that existing DFS algorithms cannot guarantee the search depth for some instruction space. We proposed an approach, named FedDFS, to improve the search depth of DFS algorithm. We analyzed the x86 instruction formats and summarized the essential search depth for each instruction format. We leveraged a feedback controlled DFS algorithm, which is controlled by comparing its search depth with essential search depth. If FedDFS detects that search depth is smaller than essential search depth, the feedback mechanism promptly increases the search depth until it reaches the proper search depth. We evaluated FedDFS on disassembler Capstone and processors from Intel and AMD. The experimental results proved that, after increasing the search depth, FedDFS does improve the coverage of x86 instruction opcodes and register operands. FedDFS tested trillions of instructions and found more instruction flaws in Capstone, which of them can only be found by FedDFS. |
| URI | http://hdl.handle.net/20.500.11897/671944 |
| ISBN | 978-1-6654-6186-3 |
| ISSN | 1063-6404 |
| DOI | 10.1109/ICCD56317.2022.00075 |
| Indexed | CPCI-S(ISTP) |
| Appears in Collections: | 工学院 |
