An optimal graph-construction approach to placing program signatures for signature monitoring

A new approach produces optimal signature placement for concurrent detection of processor and program-memory errors using signature monitoring. A program control-how graph, labeled with the overhead for placing a signature on each node and arc, is transformed into an undirected graph. For an order-independent signature function such as an XOR or arithmetic checksum, the undirected graph and a spanning tree algorithm are shown to produce an optimal placement in O(n log β(n, m)) time. Cyclic codes, which are order dependent, are shown to allow significantly lower overhead than order-independent functions. Prior work suggests overhead is unrelated to signature-function type. An O(n) graph-construction algorithm produces an optimal signature placement for cyclic codes. Experimental data show that using a cyclic code and horizontal reference signatures, the new approach can reduce average performance 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(n²) placement algorithm