A software based approach to achieving optimal performance for signature control flow checking

The authors present a software-based approach that uses run-time program behavior to minimize the performance overhead in signature control flow checking. In general, for both RISC (reduced-instruction-set-computer) and CISC (complex-instruction-set-computer) architectures, it is found that using run-time information can reduce the performance overhead by 50%. For the MC68000, the performance overhead for adding justifying and reference signatures to the program code is approximately 2.8%. In addition to optimizing the performance, the authors' approach does not increase the hardware complexity of the monitor. Furthermore, an O(N²) algorithm which inserts justifying signatures on the arcs of the program control flow graph with N nodes is presented. It is shown that the algorithm complexity of previous schemes which insert justifying signatures in the program nodes is exponential.