Static validation of machine code for security properties
Novel graph analytics herein detect security violations in machine code. Here is static validation of machine code for detecting policy violations in an accelerated way that analytically generates a control flow graph from misaligned sequences of instructions that may, for example, partially overlap (i.e. share some of the bytes) in a memory buffer. In a first analytic phase, entry points into machine code are discovered. The entry points are starting points of control flow analysis that generates a directed control flow graph (CFG) in a second analytic phase. In a third analytic phase, interchangeable and combinable security policies implement the graph analytics in a flexible way that can be customized for a processor and its instruction set architecture (ISA). This approach will quantifiably increase the reliability of a computer that executes untrusted code such as an open source library or tenant logic in a multitenant environment such as a public cloud.
1 . A method comprising:
detecting, in a sequence of bytes of executable code for an instruction set architecture (ISA), a first sequence of instructions that consists of a subsequence of the sequence of bytes of executable code that contains: a) two adjacent instructions and b) an occurrence of a multibyte constant that contains: i) a byte of a first instruction of the two adjacent instructions and ii) a byte of a second instruction of the two adjacent instructions;
detecting, based on the occurrence of the multibyte constant, a second sequence of instructions in the sequence of bytes of executable code;
generating, based on the first sequence of instructions and the second sequence of instructions, a control flow graph; and
detecting, based on the control flow graph, a security violation in the sequence of bytes of executable code;
wherein the method is performed by one or more computers without execution of the sequence of bytes of executable code.
2 . The method of claim 1 wherein the occurrence of the multibyte constant is a particular instruction.
3 . The method of claim 2 wherein the particular instruction is at least one jump target indicator selected from a group consisting of:
an instruction that consists of exactly four bytes,
an instruction that contains an operation code (opcode) that consists of exactly four bytes,
an instruction that does not contain an operand,
an instruction whose execution has no operation, and
a jump target indicator that consists solely of distinct byte values.
4 . The method of claim 1 wherein the second sequence of instructions is not a basic block.
5 . The method of claim 1 wherein:
the first sequence of instructions consists of a first subsequence of the sequence of bytes of executable code;
the second sequence of instructions consists of a second subsequence of the sequence of bytes of executable code;
the sequence of bytes of executable code contains, between the first subsequence of the sequence of bytes of executable code and the second subsequence of the sequence of bytes of executable code, a third subsequence of the sequence of bytes of executable code;
said generating the control flow graph is not based on the third subsequence of the sequence of bytes of executable code.
6 . The method of claim 1 wherein said detecting the security violation comprises during static analysis, performing at least one detection selected from a group consisting of:
a detection of a jump instruction that specifies a target that is not a jump target indicator instruction,
a detection of an instruction that has an operation code that is not in a whitelist, and
a detection that the second sequence of instructions does not contain a fence instruction.
7 . The method of claim 1 wherein each vertex in the control flow graph represents a distinct instruction.
8 . The method of claim 1 wherein the sequence of bytes of executable code is contained in
an executable file that lacks execute permission.
9 . One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors without execution of a sequence of bytes of executable code for an instruction set architecture (ISA), cause:
detecting, in the sequence of bytes of executable code, a first sequence of instructions that consists of a subsequence of the sequence of bytes of executable code that contains: a) two adjacent instructions and b) an occurrence of a multibyte constant that contains: i) a byte of a first instruction of the two adjacent instructions and ii) a byte of a second instruction of the two adjacent instructions;
detecting, based on the occurrence of the multibyte constant, a second sequence of instructions in the sequence of bytes of executable code;
generating, based on the first sequence of instructions and the second sequence of instructions, a control flow graph; and
detecting, based on the control flow graph, a security violation in the sequence of bytes of executable code.
10 . The one or more non-transitory computer-readable media of claim 9 . wherein the occurrence of the multibyte constant is a particular instruction.
11 . The one or more non-transitory computer-readable media of claim 10 wherein the particular instruction is at least one jump target indicator selected from a group consisting of:
an instruction that consists of exactly four bytes,
an instruction that contains an operation code (opcode) that consists of exactly four bytes,
an instruction that does not contain an operand,
an instruction whose execution has no operation, and
a jump target indicator that consists solely of distinct byte values.
12 . The one or more non-transitory computer-readable media of claim 9 wherein the second sequence of instructions is not a basic block.
13 . The one or more non-transitory computer-readable media of claim 9 wherein:
the first sequence of instructions consists of a first subsequence of the sequence of bytes of executable code;
the second sequence of instructions consists of a second subsequence of the sequence of bytes of executable code;
the sequence of bytes of executable code contains, between the first subsequence of the sequence of bytes of executable code and the second subsequence of the sequence of bytes of executable code, a third subsequence of the sequence of bytes of executable code;
said generating the control flow graph is not based on the third subsequence of the sequence of bytes of executable code.
14 . The one or more non-transitory computer-readable media of claim 9 wherein said detecting the security violation comprises during static analysis, performing at least one detection selected from a group consisting of:
a detection of a jump instruction that specifies a target that is not a jump target indicator instruction,
a detection of an instruction that has an operation code that is not in a whitelist, and
a detection that the second sequence of instructions does not contain a fence instruction.
15 . The one or more non-transitory computer-readable media of claim 9 wherein each vertex in the control flow graph represents a distinct instruction.
16 . The one or more non-transitory computer-readable media of claim 9 wherein the sequence of bytes of executable code is contained in
an executable file that lacks execute permission.