Algebraic techniques for the optimization of control flow checking

Leveugle (1990) addressed the problem of reducing the overhead of online testing in dedicated controllers. He introduced a low-overhead technique that allows the detection of illegal paths in finite state machines. Based on Leveugle´s idea for detecting illegal paths, we introduce a new simple signature function. This signature function can be efficiently implemented in software. The assignment of values to the states is carried out algebraically by matrix inversion instead of using exhaustive search methods. We show that signatures computed using MISR or checksum are particular cases of our more general signature function. Thus, the state assignment problem can be solved more efficiently. Then, we address the problems of latency and checking from a formal perspective and show that finding the smallest set of checking states (i.e., states where the static signature as compared with the run-time signature) that induces a latency less than or equal to a given value L is NP-hard and there exists no polynomial time algorithm that solves this problem unless P=NP