Anomaly Detection System for Hard Real-Time Embedded Systems

A computer-implemented method to generate a security automaton for detecting anomalous software behavior, the method comprising:

• partitioning assembly code of a target program into a plurality of code blocks, wherein each respective one of the code blocks represents a sequence of instructions that begins on a function entry or a next sequential instruction after a prior branch instruction and ends on a closing branch instruction;
• creating a plurality of edges in a control-flow graph by creating, for each respective one of the code blocks, a corresponding edge between a respective initial code block, which is the respective one of the code blocks, and each respective target code block of all branch targets of the respective initial code block, wherein the control-flow graph is a memory structure in a computer readable memory;
• setting a label for each respective one of the edges in the control-flow graph indicative of a branch type of the respective one of the edges;
• and
• creating the security automaton in the computer readable memory based on the control-flow graph, wherein creating the security automaton includes:
• creating a plurality of transitions, each of the transitions representing a valid transition between two respective ones of a plurality of states, the transitions corresponding to the edges in the control-flow graph, the states corresponding to the code blocks in the control-flow graph, and
• setting one or more of a plurality of security policies on the transitions based on the label for the edges corresponding to the transitions.

A non-transitory computer readable storage medium comprising a plurality of computer executable instructions, the computer executable instructions executable by a processor, the computer executable instructions comprising:

• instructions executable to partition assembly code of a target program into a plurality of code blocks, wherein each respective one of the code blocks represents a sequence of instructions that begins on a function entry or a next sequential instruction after a prior branch instruction and ends on a closing branch instruction;
• instructions executable to create a plurality of edges in a control-flow graph by creating, for each respective one of the code blocks, a corresponding edge between a respective initial code block, which is the respective one of the code blocks, and each respective target code block of all branch targets of the respective initial code block, the control-flow graph being a memory structure in a computer readable memory;
• instructions executable to set a label for each respective one of the edges in the control-flow graph indicative of a branch type of the respective one of the edges;
• and
• instructions executable to create a security automaton in the computer readable memory based on the control-flow graph, wherein the instructions executable to create the security automaton include:
• instructions executable to create a plurality of transitions, each of the transitions representing a valid transition between two respective ones of a plurality of states, the transitions corresponding to the edges in the control-flow graph, the states corresponding to the code blocks in the control-flow graph, and
• instructions executable to set one or more of a plurality of security policies on the transitions based on the label for the edges corresponding to the transitions.