AN OPTIMAL GRAPH-CONSTRUCTION APPROACH TO PLACING PROGRAM SIGNATURES FOR SIGNATURE MONITORING

A new approach produces optimal signature placement for concurrent det ection of processor and program-memory errors using signature monitori ng. A program control-flow graph, labeled with the overhead for placin g a signature on each node and arc, is transformed into an undirected graph. For an order-independent signature function such as an XOR or a rithmetic checksum, the undirected graph and a spanning tree algorithm are shown to produce an optimal placement in O(n log beta(n, m)) time . Cyclic codes, which are order dependent, are shown to allow signific antly lower overhead than order-independent functions. Prior work sugg ests overhead is unrelated to signature-function type. An O(n) graph-c onstruction algorithm produces an optimal signature placement for cycl ic codes. Experimental data show that using a cyclic code and horizont al reference signatures, the new approach can reduce average performan ce overhead to a fraction of a percent for the SPEC89 benchmark suite, more than 9 times lower than the performance overhead of an existing O(n2) placement algorithm.