Verifying Software Emulation of an Unsupported Hardware Instruction

Samuel Gruetter, Thomas Bourgeat, Adam Chlipala. Verifying Software Emulation of an Unsupported Hardware Instruction. Proceedings of the Interactive Theorem Proving - Fifteenth International Conference (ITP'24). September 2024.

Paper as PDF


Some processors, especially embedded ones, do not implement all instructions in hardware. Instead, if the processor encounters an unimplemented instruction, an unsupported-instruction exception is raised, and an exception handler is run which implements the missing instruction in software. Getting such a system to work correctly is tricky: The exception handler code must not destroy any state of the user program and must use the control and status registers (CSRs) of the processor correctly. Moreover, parts of the handler are typically implemented in assembly, while other parts are implemented in a language like C, and one must make sure that when jumping from the user program into the handler assembly, from the handler assembly into C, back to assembly and finally back to the user program, all the assumptions made by the different pieces of code, hardware, and the compiler are satisfied.

Despite all these tricky details, there is a concise and intuitive way of stating the correctness of such a system: User programs running on a system where some instructions are implemented in software behave the same as if they were running on a system where all instructions are implemented in hardware.

We formalize and prove such a statement in the Coq proof assistant, for the case of a simple exception handler implementing the multiplication instruction on a RISC-V processor.

GitHub repository