Method for swapping adjacent instructions midstream in software executables in order to hide information therein

Patent metadata

Field	Value
Publication number	US-11520865-B2
Application number	US-202117165660-A
Country	US
Kind code	B2
Filing date	Feb 2, 2021
Priority date	Feb 2, 2021
Publication date	Dec 6, 2022
Grant date	Dec 6, 2022

Abstract

A method for hiding information in executable code comprising: identifying a set of pairs of interchangeable instructions, wherein each pair has an instruction order of execution that is reversible without changing a functionality of the executable code; organizing the pairs into a plurality of matrices based on a set of random seeds; for each matrix, inverting a submatrix consisting of a subset of columns from each matrix to identify a subset of pairs; identifying a matrix that has full column rank on a subset of columns that is a function of the pairs' location; storing an index of the identified matrix's associated seed in a secure data storage location; and encoding data into the executable code by reversing the order of execution of the subset of pairs and treating each pair having reversed instructions as a “1” and each pair of non-reversed instructions as a “0” or vice versa.

First claim

We claim:

1. A method for using a computer to hide information in executable code comprising:
identifying in the executable code a set of pairs of interchangeable assembly-level instructions, wherein each pair has a characteristic that an order of execution of its constituent instructions may be reversed without changing a functionality or performance of the executable code;
organizing the pairs of interchangeable assembly-level instructions into a plurality of random matrices based on a set of random seeds such that each seed maps to exactly one matrix;
for each random matrix, inverting a submatrix consisting of a subset of columns from each matrix to identify a subset of pairs of interchangeable instructions;
identifying a matrix from the plurality of matrices that has full column rank on a subset of columns that is a function of a location of each of the pairs of interchangeable instructions;
storing an index of the identified matrix's associated seed in a secure data storage location; and
encoding binary information into the executable code by reversing the order of execution of the subset of pairs of interchangeable instructions and treating each pair having reversed instructions as a “1” and each pair of interchangeable instructions having an original order of execution as a “0” or vice versa.

2. The method of claim 1 , further comprising:
recovering the index of the identified matrix's associated seed from the secure data storage location; and
reconstructing the identified matrix and its corresponding submatrix based on the associated seed in order to identify which pairs of instructions have been reversed and thus retrieve the encoded binary information.

3. The method of claim 2 , wherein the steps of claim 2 are performed by a second, separate computer from the computer identified in claim 1 .

4. A method for using a computer to hide information in executable code comprising:
a. identifying in the executable code a set J of pairs of interchangeable assembly-level instructions, wherein each pair has an order of execution of its constituent instructions that may be reversed without changing a functionality or performance of the executable code;
b. generating a |J|×n matrix M over a finite field of size two based on one of a set S of random seeds, wherein n is a total number of interchangeable assembly-level instructions;
c. creating a sub-matrix M J composed of a subset of columns of the matrix M indexed by the set J to identify a subset of pairs of interchangeable instructions;
d. repeating steps (b)-(c) with different seeds until the sub-matrix M J has full rank;
e. encoding hidden binary information into the executable code by reversing the order of execution of the subset of the pairs of interchangeable assembly-level instructions whereby each of the subset of pairs with a reversed order of execution is deemed a “1” and each pair of assembly-level instructions that maintains an original order of execution is deemed a “0” such that the functionality of the executable code is not altered;
f. storing in a secure location an index of a seed associated with the full-rank sub-matrix M j ; and
g. retrieving the hidden binary information by recovering the index of the seed associated with the full-rank sub-matrix M J from the secure location and regenerating the matrix M based on the seed associated with the full-rank sub-matrix M J .

5. The method of claim 4 , further comprising using a new seed s′ to randomly generate the matrix M if all the seeds in set S have been used to create matrices and none of the associated submatrices M J are full rank.

6. The method of claim 5 , further comprising adding s′ to S if s′<S and the matrix M was generated using s′.

7. The method of claim 6 , wherein the set S is the set of random seeds after the algorithm has been executed.

8. The method of claim 4 , where step (g) is performed without a foreknowledge of which subset of pairs have a reversed order of execution.

9. The method of claim 4 , wherein each of the pairs of interchangeable assembly-level instructions consist of two adjacent instructions in the executable code.

10. The method of claim 4 , wherein the hidden binary information is a digital signature such that retrieval of the digital signature would serve as both a validation that the executable code is authentic and also that the executable code has not been tampered with.

11. The method of claim 4 , wherein the set of random seeds is generated through an encryption library.

12. The method of claim 4 , wherein the set of random seeds is stored in a memory store.

13. The method of claim 4 , wherein the subset of instructions with reversed order of execution is not pre-determined before the encoding steps.

14. The method of claim 4 , wherein the method does not include introduction of new instructions in the executable code.

Assignees

• Us Gov As Represented By The Secretary Of The Navy
• Us Navy

Inventors

• Gabrys Ryan C
• Martinez Luis M
• Fugate Sunny James

Classifications

• G06F21/12 Primary

  Protecting executable software · CPC title

• G06F21/44 Primary

  Program or device authentication · CPC title

• H04L9/0869

  involving random numbers or seeds · CPC title

• G09C5/00

  Ciphering apparatus or methods not provided for in the preceding groups, e.g. involving the concealment or deformation of graphic data such as designs, written or printed messages · CPC title

• H04L9/3247

  involving digital signatures · CPC title