Method of checking the execution of microcode sequences

Claim 1

A method for detecting impermissible traversals in a system in which selective traversals (jumps or branches) along extents of the symbol string are dictated by embedded pointers, and further in which the symbol string includes single entrance, single exit (SESE) substrings, comprising the steps of: (a) processing the symbol string by: (1) deriving the labeling ones of a set of permissible traversals from the SESE substrings; (2) generating a global label indicative of one permissible traversal through the symbol string of the set of permissible traversals and then scaling the labels obtained in step (a1) of remaining ones of the set of permissible traversals such that transitioning along a permissible traversal always yields the same global label; (3) embedding the labels within SESE substrings; (b) executing the processed symbol string by: (4) reading the SESE substrings from a boundary (entrance/exit) of an arbitrary substring to a boundary of another arbitrary substring and computing from each read substring at least one label indicative of the traversal; and (5) comprising the embedded label with computed label such that a mismatch is indicative of error.

Claim 2

A method for detecting impermissible traversals in a system in which selective traversals (jumps or branches) along extents of the symbol string are dictated by embedded pointers, and further in which the symbol string includes single entrance, single exit (SESE) substrings, comprising the steps of: (a) processing the symbol string by: (1) deriving the labeling ones of a set of permissible traversals from the SESE substrings; (2) generating a global label indicative of one permissible traversal through the symbol string of the set of permissible traversals and then scaling the labels obtained in step (a1) of remaining ones of the set of permissible traversals such that transitioning along a permissible traversal always yields the same global label; (3) embedding the labels within SESE substrings; (b) executing the processed symbol string by: (4) reading the SESE substrings from a boundary (entrance/exit) of an arbitrary substring to a boundary of another arbitrary substring and computing from each read substring at least one label indicative of the traversal; and (5) comprising the embedded label with computed label such that a mismatch is indicative of error.

Claim 4

A method of verifying correct execution of a string of sequential microinstructions, comprising the steps of: (a) deriving a numerical representation (label) for each microinstruction in one selected permissible traversal in the microinstruction string; (b) operating on said derived numerical representations (labels) through a predetermined function to obtain a predetermined global label; (c) storing said predetermined global label at the entry point of said microinstruction string to signify the beginning of a microprogram segment; (d) at runtime, regenerating said global label concurrently with execution of the string of microinstructions; (e) at runtime, comparing said regenerated global label with said predetermined global label at the conclusion of execution of said microinstruction string.

Claim 5

A method of verifying correct execution of a string of sequential microinstructions, comprising the steps of: (a) deriving a numerical representation (label) for each microinstruction in one selected permissible traversal in the microinstruction string; (b) operating on said derived numerical representations (labels) through a predetermined function to obtain a predetermined global label; (c) storing said predetermined global label at the entry point of said microinstruction string to signify the beginning of a microprogram segment; (d) at runtime, regenerating said global label concurrently with execution of the string of microinstructions; (e) at runtime, comparing said regenerated global label with said predetermined global label at the conclusion of execution of said microinstruction string.