An optimal graph-construction approach to placing program signatures for signature monitoring
- 1 January 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 42 (11) , 1372-1381
- https://doi.org/10.1109/12.247847
Abstract
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 beta (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/sup 2/) placement algorithm.Keywords
This publication has 18 references indexed in Scilit:
- An empirical analysis of algorithms for constructing a minimum spanning treePublished by Springer Nature ,2005
- Control-flow checking using watchdog assists and extended-precision checksumsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A new approach to control flow checking without program modificationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1991
- Continuous signature monitoring: low-cost concurrent detection of processor control errorsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1990
- Control-flow checking using watchdog assists and extended-precision checksumsIEEE Transactions on Computers, 1990
- A linear-time algorithm for finding a minimum spanning pseudoforestInformation Processing Letters, 1988
- Concurrent error detection using watchdog processors-a surveyIEEE Transactions on Computers, 1988
- A roving monitoring processor for detection of control flow errors in multiple processor systemsMicroprocessing and Microprogramming, 1987
- Processor Control Flow Monitoring Using Signatured Instruction StreamsIEEE Transactions on Computers, 1987
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphsCombinatorica, 1986