Discovering Instructions for Robust Binary-level Coverage Criteria

Abstract

Object-Branch Coverage (OBC) is often used to measure e ective- ness of test suites, when source code is unavailable. The traditional OBC de nition can be made more resilient to variations in compil- ers and the structure of generated code by creating more robust de nitions. However nding which instructions should be included in each new de nition is laborious, error-prone, and architecture- dependent. We automate the discovery of instructions to be in- cluded for an improved OBC de nition on the X86 and ARM archi- tectures. We discover all possible valid instructions by symbolically executing instruction decoders for X86 and ARM instructions. For each discovered instruction, we translate it to Vine IR, and check if the Vine IR translation satis es the OBC de nition. We verify the correctness of our tool by comparing its output with the X86 and ARM architecture manuals. Our automated instruction clas- si cation facilitates development of more robust OBC de nitions with better bug- nding ability and lesser sensitivity to compiler variations.