Autonomous reasoning system for vulnerability analysis

• US 9,767,290 B2
• Filed: 07/09/2015
• Issued: 09/19/2017
• Est. Priority Date: 03/05/2015
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Murthy, Praveen, Copos, Bogdan, Pham, Thuan
• Primary Examiner(s): Zand, Kambiz
• Assistant Examiner(s): LE, THANH H
• Application Number:
  US14/795,812
• Publication Number:
  US 20160259943A1
• Time in Patent Office: 803 Days
• CPC Class Codes: G06F 21/577 Assessing vulnerabilities and evaluating computer system security
• CPC Class Codes: G06F 2221/033 Test or assess software
• CPC Class Codes: G06F 8/65 Updates security arrangements therefor G06F21/57
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates

Abstract

A method of vulnerability analysis of a deployed program (program) includes inputting a binary program under analysis (BPUA) derived from the program. The method includes analyzing input/output (I/O) behavior of the program. The method includes discovering inputs to the program based on application of exploration techniques to the BPUA and analysis of the I/O behavior. The method includes determining which of the inputs are negative inputs. The negative inputs are inputs that trigger a response that includes a vulnerability of the program. Based on the negative inputs and triggered responses, the method includes developing a patch for the program that modifies the program to process at least some of the negative inputs without triggering a response that includes the vulnerability. The method includes automatically dispatching the patch.

Claims

1. A method of vulnerability analysis of a deployed program, the method comprising:

receiving a binary program under analysis (BPUA) derived from the deployed program;

analyzing input/output (I/O) behavior of the deployed program;

discovering inputs to the deployed program based on application of two or more exploration techniques to the BPUA and analysis of the I/O behavior, the inputs including a first set of inputs discovered during a symbolic execution process, a second set of inputs discovered during a side-channel input generation, and a third set of inputs from an I/O state machine module (stateful model) generation process;

determining which of the inputs are negative inputs, the negative inputs including a portion of the inputs that trigger a response that includes a vulnerability of the deployed program;

based on the negative inputs and triggered responses, developing a patch for the deployed program that modifies the deployed program to process at least some of the negative inputs without triggering a response that includes the vulnerability; and

automatically dispatching the patch to the deployed program.

2. The method of claim 1, further comprising:

determining which of the inputs are positive inputs, the positive inputs including a portion of the inputs that trigger responses that do not include a vulnerability of the deployed program;

associating each of the negative inputs and each of the positive inputs with the response that is triggered in the deployed program;

storing each of the negative inputs and associated response as negative test cases in a test database; and

storing each of the positive inputs and associated response as positive test cases in the test database.

3. The method of claim 2, further comprising generating an overall fitness function based on the positive test cases and negative test cases, wherein the patch includes a mutation to the deployed program based on the fitness function and genetic programming.

4. The method of claim 2, further comprising testing the patch using the positive test cases and negative test cases before automatically dispatching the patch to the deployed program.

5. The method of claim 1, further comprising:

further discovering additional inputs using one or more fuzzers; and

determining which of the additional inputs are negative inputs.

6. The method of claim 1, wherein the vulnerability includes a memory corruption error, a buffer overflow, a software crash, and an arithmetic error.

7. The method of claim 1, wherein:

the exploration techniques include symbolic execution of the BPUA and a side-channel input generation process for unknown program behavior; and

the I/O behavior includes console interactions of a user with the deployed program and captured network traffic communicated with the deployed program.

8. The method of claim 1, wherein the discovering inputs includes:

comparing the first set of inputs, the second set of inputs, and the third set of inputs to determine which of the inputs are not included in all of the first set of inputs, the second set of inputs, and the third set of inputs;

for one or more of the inputs omitted from the second set of inputs, generating a set of prefixes of omitted inputs and using the set of prefixes in the side-channel input generation as bases to discover one or more other inputs; and

for one or more of the inputs omitted from the first set of inputs, incorporating the omitted inputs in the stateful model.

9. The method of claim 1, further comprising developing the stateful model that represents, at an abstract level, the I/O behavior of the BPUA that has been learned to that point, wherein the stateful model is a basis of patch development using a genetic programming-based repair framework.

10. The method of claim 1, wherein the analyzing the I/O behavior, the discovering inputs, the determining, the developing the patch, and the dispatching occur while the deployed program is running.

11. One or more non-transitory computer-readable media having encoded therein programming code executable by one or more processors to perform operations, the operations comprising:

receiving a binary program under analysis (BPUA) derived from a deployed program;

analyzing input/output (I/O) behavior of the deployed program;

discovering inputs to the deployed program based on application of two or more exploration techniques to the BPUA and analysis of the I/O behavior, the inputs including a first set of inputs discovered during a symbolic execution process, a second set of inputs discovered during a side-channel input generation, and a third set of inputs from an I/O state machine module (stateful model) generation process;

determining which of the inputs are negative inputs, the negative inputs including a portion of the inputs that trigger a response that includes a vulnerability of the deployed program;

based on the negative inputs and triggered responses, developing a patch for the deployed program that modifies the deployed program to process at least some of the negative inputs without triggering a response that includes the vulnerability; and

automatically dispatching the patch to the deployed program.

12. The non-transitory computer-readable media of claim 11, wherein the operations further comprise:

determining which of the inputs are positive inputs, the positive inputs including a portion of the inputs that trigger responses that do not include a vulnerability of the deployed program;

associating each of the negative inputs and each of the positive inputs with the response that is triggered in the deployed program;

storing each of the negative inputs and associated response as negative test cases in a test database; and

storing each of the positive inputs and associated response as positive test cases in the test database.

13. The non-transitory computer-readable media of claim 12, wherein the operations further comprise generating an overall fitness function based on the positive test cases and negative test cases, wherein the patch includes a mutation to the deployed program based on the fitness function and genetic programming.

14. The non-transitory computer-readable media of claim 12, wherein the operations further comprise testing the patch using the positive test cases and negative test cases before automatically dispatching the patch to the deployed program.

15. The non-transitory computer-readable media of claim 11, wherein the operations further comprise:

further discovering additional inputs using one or more fuzzers; and

determining which of the additional inputs are negative inputs.

16. The non-transitory computer-readable media of claim 11, wherein the vulnerability includes a memory corruption error, a buffer overflow, a software crash, and an arithmetic error.

17. The non-transitory computer-readable media of claim 11, wherein:

the exploration techniques include symbolic execution of the BPUA and a side-channel input generation process for unknown program behavior; and

the I/O behavior includes console interactions of a user with the deployed program and captured network traffic communicated with the deployed program.

18. The non-transitory computer-readable media of claim 11, wherein the discovering inputs includes:

comparing the first set of inputs, the second set of inputs, and the third set of inputs to determine which of the inputs are not included in all of the first set of inputs, the second set of inputs, and the third set of inputs;

for one or more of the inputs omitted from the second set of inputs, generating a set of prefixes of omitted inputs and using the set of prefixes in the side-channel input generation as bases to discover one or more other inputs; and

for one or more of the inputs omitted from the first set of inputs, incorporating the omitted inputs in the stateful model.

19. The non-transitory computer-readable media of claim 11, wherein the operations further comprise developing the stateful model that represents, at an abstract level, the I/O behavior of the BPUA that has been learned to that point, wherein the stateful model is a basis of patch development using a genetic programming-based repair framework.

20. The non-transitory computer-readable media of claim 11, wherein the analyzing the I/O behavior, the discovering inputs, the determining, the developing the patch, and the dispatching occur while the deployed program is running.