Automated software generation through mutation and artificial selection

Patent metadata

Field	Value
Publication number	US-2021096831-A1
Application number	US-201916589029-A
Country	US
Kind code	A1
Filing date	Sep 30, 2019
Priority date	Sep 30, 2019
Publication date	Apr 1, 2021
Grant date	—

Abstract

Techniques for automatically generating a target software object herein include accessing an initial version of a candidate software object that does not satisfy one or more functional requirements; mutating executable binary object code of the initial version of the candidate software object to generate a first intermediate version; testing the first intermediate version to determine whether the first intermediate version satisfies at least one of the one or more functional requirements by executing the first intermediate version and a set of automated tests; and continuing to mutate and test the candidate software object through successive intermediate versions of the candidate software object until a version of the candidate software object satisfies all of the one or more functional requirements, wherein each successive intermediate version of the candidate software satisfies at least one functional requirement not satisfied by preceding versions of the candidate software object.

First claim

What is claimed is:

1 . A computing device comprising:
a processor; and a computer-readable medium storing executable instructions for causing the processor to perform operations comprising:
accessing an initial version of a candidate software object that does not satisfy one or more functional requirements of the target software object;
mutating executable binary object code of the initial version of the candidate software object to generate a first intermediate version of the candidate software object;
testing the first intermediate version of the candidate software object to determine whether the first intermediate version of the candidate software object satisfies at least one of the one or more functional requirements by executing the first intermediate version of the candidate software object and a set of automated tests that provide the first intermediate version of the candidate software object with a predetermined set of inputs and determine whether outputs of the first intermediate version of the candidate software output correspond to a predetermined set of outputs; and
continuing to mutate and test the candidate software object through successive intermediate versions of the candidate software object until a version of the candidate software object satisfies all of the one or more functional requirements, wherein each successive intermediate version of the candidate software satisfies at least one functional requirement not satisfied by preceding versions of the candidate software object.

2 . The computing device of claim 1 , responsive to the first intermediate version of the candidate software object not satisfying the at least one of the one or more functional requirements, iteratively mutating and testing the first candidate software object by:
further mutating the first intermediate version of the candidate software object; and testing the further mutated first intermediate version of the candidate software object to determine whether the further mutated candidate software object satisfies at least one of the one or more functional requirements.

3 . The computing device of claim 1 , wherein mutating the first version of the candidate software object includes adding at least one bit to the candidate software object.

4 . The computing device of claim 3 , wherein adding the at least one bit to the candidate software object comprises adding the at least one bit to a code section of the candidate software object.

5 . The computing device of claim 3 , wherein the computer-readable medium further includes instructions for causing the processor to perform operations comprising:
maintaining a state of a first portion of the code section that satisfies the at least one or more functional requirements.

6 . The computing device of claim 5 , wherein continuing to mutate the first intermediate version of the candidate software further comprises:
generating the second intermediate version of the candidate software object by adding one or more bits to a second portion of the code section of the first intermediate version of the candidate software object.

7 . The computing device of claim 1 , wherein testing the first intermediate version of the candidate software object includes:
executing one or more tests associated with a first functional requirement of the one or more functional requirements; and determining that the candidate software object satisfies the first functional requirement responsive to the candidate software object passing all of the one or more tests associated with the first functional requirement.

8 . A method performed by a data processing system for automatically generating a target software object comprising:
accessing via a processor an initial version of a candidate software object that does not satisfy one or more functional requirements of the target software object; mutating via the processor executable binary object code of the initial version of the candidate software object to generate a first intermediate version of the candidate software object; testing via the processor the first intermediate version of the candidate software object to determine whether the first intermediate version of the candidate software object satisfies at least one of the one or more functional requirements by executing the first intermediate version of the candidate software object and a set of automated tests that provide the first intermediate version of the candidate software object with a predetermined set of inputs and determine whether outputs of the first intermediate version of the candidate software output correspond to a predetermined set of outputs; and continuing to mutate and test the candidate software object through successive intermediate versions of the candidate software object until a version of the candidate software object satisfies all of the one or more functional requirements, wherein each successive intermediate version of the candidate software satisfies at least one functional requirement not satisfied by preceding versions of the candidate software object.

9 . The method of claim 8 , responsive to the first intermediate version of the candidate software object not satisfying the at least one of the one or more functional requirements, iteratively mutating and testing the first candidate software object by:
further mutating the first intermediate version of the candidate software object; and testing the further mutated first intermediate version of the candidate software object to determine whether the further mutated candidate software object satisfies at least one of the one or more functional requirements.

10 . The method of claim 8 , wherein mutating the first version of the candidate software object includes adding at least one bit to the candidate software object.

11 . The method of claim 10 , wherein adding the at least one bit to the candidate software object comprises adding the at least one bit to a code section of the candidate software object.

12 . The method of claim 10 , further comprising:
maintaining a state of a first portion of the code section that satisfies the at least one or more functional requirements.

13 . The method of claim 12 , wherein continuing to mutate the first intermediate version of the candidate software further comprises:
generating the second intermediate version of the candidate software object by adding one or more bits to a second portion of the code section of the first intermediate version of the candidate software object.

14 . The method of claim 8 , wherein testing the first intermediate version of the candidate software object includes:
executing via the processor one or more tests to determine whether the candidate software object satisfies a respective software requirement of the one or more functional requirements; and determining via the processor that the respective software requirement has been satisfied responsive to the candidate software object passing the one or more tests.

15 . A memory device storing instructions that, when executed on a processor of a computing device, cause the computing device to automatically generate a target software object, by:
accessing an initial version of a candidate software object that does not satisfy one or more functional requirements of the target software object; mutating executable binary object code of the initial version of the candidate software object to generate a first intermediate version of the candidate software object; testing the first intermediate version of the candidate software object to determine whether the first in

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Satyarth Arun S

Classifications

• G06F11/3688 Primary

  for test execution, e.g. scheduling of test suites · CPC title

• G06F8/30 Primary

  Creation or generation of source code · CPC title

• G06N3/126

  Evolutionary algorithms, e.g. genetic algorithms or genetic programming · CPC title

• G06F8/71

  Version control (security arrangements therefor G06F21/57); Configuration management · CPC title

• G06F11/3692

  for test results analysis · CPC title