# US 11,307,962 B2 · Method for semantic preserving transform mutation discovery and vetting > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,307,962 B2 - Document ID: US11307962B2 - Status: Granted - Kind: B2 - Application number: 16/030,549 - Filed: 2018-07-09 - Published: 2020-01-09 - Granted: 2022-04-19 - Earliest claimed: 2018-07-09 - Assignees: The United States of America as represented by the Secretary of the Navy - Applicants: The United States of America as represented by the Secretary of the Navy - Inventors: Jason A. Landsborough; Sunny J. Fugate; Stephen T. Harding - Web page: https://patentgrep.com/patent/US11307962B2 ## CPC - G06F 11/3608: {using formal methods, e.g. model checking, abstract interpretation (theorem proving G06N5/013)} - G06F 11/3688: {for test execution, e.g. scheduling of test suites} - G06F 11/3692: {for test results analysis} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method for validating software transforms. A target program binary is mutated, producing a plurality of variants. It is determined whether each variant passes a test suite. Upon determining the variant does not pass the test suite, the variant is discarded. Upon determining the variant passes the test suite, the variant is compared to the target program binary. A candidate transform is extracted which meets scope criteria. The candidate transform is applied to each of a plurality of test programs. It is determined whether the candidate transform is safe. Upon determining that the candidate transform is not safe, the candidate transform is discarded. Upon determining that the candidate transform is safe, the candidate transform is collected. ## Claims ### Claim 1 A computer system with at least one processor for executing instructions for generating validated software transforms, the instructions from a non-transitory storage media causing the at least one processor to perform steps comprising: mutating a target program binary, producing a plurality of variants; determining whether each variant of the variants passes a test suite; upon determining the variant does not pass the test suite, discarding the variant; upon determining the variant passes the test suite: extracting a candidate transform that describes a difference between the target program binary and the variant; applying the candidate transform to each of a plurality of test programs; determining whether the candidate transform is safe; upon determining the candidate transform is not safe, discarding the candidate transform; and upon determining the candidate transform is safe, collecting the candidate transform as one of the validated software transforms. ### Claim 2 (depends on 1) The computer system of claim 1, wherein the target program binary is mutated using genetic mutation. ### Claim 3 (depends on 1) The computer system of claim 1, wherein the mutation step comprises a swapping code step. ### Claim 4 (depends on 1) The computer system of claim 1, wherein the mutation step comprises an inserting code step. ### Claim 5 (depends on 1) The computer system of claim 1, wherein the mutation step comprises a deleting code step. ### Claim 6 (depends on 1) The computer system of claim 1, wherein the variants are produced using a crossover combination technique. ### Claim 7 (depends on 6) The computer system of claim 6, wherein the crossover combination technique is a two-point technique. ### Claim 8 (depends on 1) The computer system of claim 1, wherein the variants are produced using tournament selection. ### Claim 9 (depends on 1) The computer system of claim 1, wherein the candidate transform is extracted by comparing a disassembled output of the target program binary with a disassembled output of the variant, and the candidate transform describes the difference between the disassembled outputs of the target program binary and the variant. ### Claim 10 (depends on 1) The computer system of claim 1, wherein at the applying the candidate transform to each of the plurality of test programs step, the candidate transform is applied to an executable section of the test program. ### Claim 11 (depends on 1) The computer system of claim 1, wherein at the applying the candidate transform to each of the plurality of test programs step, the test programs are a plurality of test programs other than the target program binary and the variants. ### Claim 12 (depends on 1) The method computer system of claim 1, wherein at the determining whether the candidate transform is safe step, the candidate transform T is considered safe if, for each test program F of the test programs, the test program P and a variant P′=T(P) produced during the applying are functionally equivalent because both P and P′ pass a respective test suite for the test program P. ### Claim 13 A computer system with at least one processor for executing instructions for generating validated software transforms, the instructions from a non-transitory storage media causing the at least one processor to perform steps comprising: mutating a target program binary, producing a plurality of variants of the target program binary; determining whether each variant of the variants passes a test suite for the target program binary; upon determining the variant does not pass the test suite, discarding the variant; upon determining the variant passes the test suite: extracting a candidate transform that describes a difference between a disassembled output of the target program binary and a disassembled output of the variant; applying the candidate transform to each test program binary of a plurality of additional program binaries, producing a variant of the test program binary; determining whether the candidate transform is safe, wherein the candidate transform is considered safe if, for each test program binary of the additional program binaries, the variant of the test program binary passes a respective test suite for the test program binary; upon determining the candidate transform is not safe, discarding the candidate transform; and upon determining the candidate transform is safe, collecting the candidate transform as one of the validated software transforms. ### Claim 14 (depends on 13) The computer system of claim 13, wherein the mutation step comprises a code swapping step. ### Claim 15 (depends on 13) The computer system of claim 13, wherein the mutation step comprises an inserting code step. ### Claim 16 (depends on 13) The computer system of claim 13, wherein the mutation step comprises a deleting code step. ### Claim 17 (depends on 13) The computer system of claim 13, wherein the variants are produced using a crossover combination technique. ### Claim 18 (depends on 13) The computer system of claim 13, wherein the variants are produced using tournament selection. ### Claim 19 (depends on 13) The computer system of claim 13, wherein at the applying the candidate transform to each test program binary of a plurality of additional program binaries step, the candidate transform is applied to a .text section of the test program binary. ### Claim 20 A computer system with at least one processor for executing instructions for generating validated software transforms, the instructions from a non-transitory storage media causing the at least one processor to perform steps comprising: mutating a target program binary using genetic mutation, producing a plurality of variants of the target program binary using a crossover combination technique and tournament selection, wherein the crossover combination technique is a two-point technique; determining whether each variant of the variants passes a test suite for the target program binary; upon determining the variant does not pass the test suite, discarding the variant; upon determining the variant passes the test suite: extracting a candidate transform by comparing a disassembled output of the target program binary with a disassembled output of the variant, the candidate transform describing a difference between the disassembled outputs of the target program binary and the variant within a window scope criteria; applying the candidate transform to each test program binary of a plurality of additional program binaries, producing a variant of the test program binary, wherein the candidate transform is applied to a .text section of the test program binary; determining whether the candidate transform is safe, wherein the candidate transform is considered safe if, for each test program binary of the additional program binaries, the variant of the test program binary passes a respective test suite for the test program binary; upon determining the candidate transform is not safe, discarding the candidate transform; and upon determining the candidate transform is safe, collecting the candidate transform as one of the validated software transforms.