The processors have long been treated as trusted black boxes for running software. However, processors may have undocumented instructions and instruction flaws, which increase the attack surface of the computing system. Hardware-related attack surfaces can bypass malware detection tools, resulting in undefined system behavior, instability, and insecurity. Unfortunately, the existing testing methods for undocumented instructions and instruction flaws have issues of insufficient test coverage and low test efficiency. We proposed an approach Skipscan to address these issues, which tests both the legal instructions and the reserved instructions. For the first time, to improve the test coverage, Skipscan leverages anoptimized combination algorithmto generate instruction prefix combinations, which covers the entire types of legal prefix combinations. To improve the test efficiency, Skipscan skips a considerable number of redundant legal instructions by leveraging theminimal test setof immediate and displacement operands. We evaluated Skipscan on eight x86 processors from Intel and AMD. The number of legal instructions and reserved instructions tested by Skipscan are 121.4 and 259.55 times that of Sandsifter on average, respectively. The test efficiency of Skipscan is on average 4 times that of Sandsifter. The ratio of legal instructions is reduced from 78.2% to 20.1% on average. Furthermore, we found more undocumented instructions on x86 processors and instruction flaws in x86 disassemblers.

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.

The instruction decoders are tools for software analysis, sandboxing, malware detection, and undocumented instructions detection. The decoders must be accurate and consistent with the instruction set architecture manuals. The existing testing methods for instruction decoders are based on random and instruction structure mutation. Moreover, the methods are mainly aimed at the legal instruction space. However, there is little research on whether the instructions in the reserved instruction space can be accurately identified as invalid instructions. We propose an instruction operand inferring algorithm, based on the depth-first search algorithm, to skip considerable redundant legal instruction space. The algorithm keeps the types of instructions in the legal instruction space unchanged and guarantees the traversal of the reserved instruction space. In addition, we propose a differential testing method that discovers decoding discrepancies between instruction decoders. We applied the method to XED and Capstone and found four million inconsistent instructions between them. Compared with the existing instruction generation method based on the depth-first search algorithm, the efficiency of our method is improved by about four times.