An equivalence checker for hardware-dependent embedded system software
Carlos Villarraga, Bernard Schmidt, Jörg Bormann, Christian Hippolyt Bartsch, Dominik Stoffel, Wolfgang Kunz · Formal Methods · 2013
This paper presents a novel approach to formally prove the equivalence of low-level hardware-dependent programs. Inspired by hardware verification techniques, a software miter is created that compares the behaviors of two programs, taking into account the interfaces between the software and the hardware environments. Two programs are considered equivalent if they produce the same outputs for the same input assignments and also exhibit the same sequences of interactions with the relevant hardware peripherals. This motivates a hardware-dependent computational model combining a path-oriented program view, as is common in hardware-independent software verification, with a structural hardware representation of the program's computation. Experimental results show the effectiveness of the proposed technique for industrial low-level software in important equivalence checking scenarios such as code porting and automated/manual code transformations.