Determining valid inputs for an unknown binary program

• US 9,552,284 B2
• Filed: 05/15/2015
• Issued: 01/24/2017
• Est. Priority Date: 05/15/2015
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Copos, Bogdan, Murthy, Praveen
• Primary Examiner(s): Dao, Thuy
• Assistant Examiner(s): Chowdhury, Ziaul A
• Application Number:
  US14/714,072
• Publication Number:
  US 20160335175A1
• Time in Patent Office: 620 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/3636 by tracing the execution of the program
• CPC Class Codes: G06F 11/3684 for test design, e.g. generating new test cases
• CPC Class Codes: G06F 8/49 Partial evaluation
• CPC Class Codes: G06F 8/52 Binary to binary
• CPC Class Codes: G06F 8/71 Version control security arrangements therefor G06F21/57; Configuration management
• CPC Class Codes: G06F 8/73 Program documentation
• CPC Class Codes: G06F 8/74 Reverse engineering; Extracting design information from source code

Abstract

A method to determine valid input sequences for an unknown binary program is provided. The method includes obtaining multiple input sequences, which each include two or more different inputs, for an unknown binary program. The inputs for the input sequences may be valid inputs for the unknown binary program. The method may further include executing an instrumented version of the unknown binary program separately for each input sequence. For each execution of the instrumented version of the unknown binary program, a set of execution traces may be generated by recording execution traces generated by the execution of the instrumented version of the unknown binary program. The method may further include comparing the sets of execution traces and determining which of the input sequences the unknown binary program accepts as valid based on the comparison of the sets of execution traces.

Claims

1. A method to determine valid input sequences for an unknown binary program, the method comprising:

obtaining a plurality of input sequences of unknown validity for the unknown binary program, each of the input sequences including two or more different inputs, the inputs for the input sequences determined as valid inputs for the unknown binary program, the unknown binary program being unknown based on source code of the unknown binary program being unavailable;

executing an instrumented version of the unknown binary program separately for each input sequence, each execution of the instrumented version of the unknown binary program using one of the input sequences as inputs to the instrumented version of the unknown binary program;

for each execution of the instrumented version of the unknown binary program, generating a set of execution traces by recording execution traces generated by the execution of the instrumented version of the unknown binary program;

generating at least two control flow graphs for at least two execution traces;

comparing the sets of execution traces including comparing the at least two control flow graphs with each other; and

determining which of the plurality of input sequences the unknown binary program accepts as valid based on the comparison of the sets of execution traces, wherein a valid input sequence includes a first input that is a precondition for a subsequent second input in the valid input sequence.

2. The method of claim 1, wherein at least one of the inputs includes a command determined as valid for the unknown binary program and an argument associated with the command, the argument also determined as valid for the unknown binary program.

3. The method of claim 1, wherein generating the sets of execution traces includes selecting a portion of the execution traces for each execution of the instrumented version of the unknown binary program for inclusion in the sets of execution traces, the portion of the execution traces selected for the sets of execution traces being the execution traces generated after last inputs of the input sequences are provided to the unknown binary program.

4. The method of claim 3, wherein selecting the portion of the execution traces for inclusion in the sets of execution traces comprises:

executing the instrumented version of the unknown binary program without any inputs;

determining a plurality of the execution traces generated by the execution of the instrumented version of the unknown binary program at an end of the execution without any inputs;

setting the determined plurality of execution traces as partition execution traces; and

selecting the portion of the execution traces generated during execution of the instrumented version of the unknown binary program using the input sequences based on the portion of the execution traces occurring between a next to last occurrence and a last occurrence of the partition execution traces.

5. The method of claim 1, wherein comparing the at least two control flow graphs with each other comprises:

generating a string representation for each of the at least two control flow graphs; and

comparing the string representations.

6. The method of claim 5, wherein generating the string representation for each of the at least two control flow graphs includes implementing a depth-first search algorithm or breadth first search algorithm.

7. The method of claim 1, wherein an execution trace of one of the sets of execution traces represents a memory address associated with a straight-line block of instructions executed in the unknown binary program that is output by the instrumented version of the unknown binary program and not output by an un-instrumented version of the unknown binary program.

8. The method of claim 7, wherein a last input in each input sequence of the plurality of input sequences is the same and the plurality of input sequences is a set of input sequences, the method further comprising repeating the method of claim 1 for a plurality of other sets of input sequences, wherein a last input for each input sequence of each set of the other sets of input sequences is the same and the last input for each set of input sequences is different from the last input of the other sets of input sequences.

9. The method of claim 1, wherein when the comparison of the sets of execution traces indicates that the sets of execution traces are the same, none of the input sequences are determined to be accepted by the unknown binary program.

10. The method of claim 1, wherein when the comparison of the sets of execution traces indicates that one of the sets of execution traces is different than at least another two of the sets of execution traces that are the same, an input sequence corresponding to the one of the sets of execution traces is determined to be accepted by the unknown binary program.

11. One or more non-transitory computer readable media that include instructions that when executed by one or more processors perform operations to determine valid input sequences for an unknown binary program, the operations comprising:

obtaining a plurality of input sequences of unknown validity for the unknown binary program, each of the input sequences including two or more different inputs, the inputs for the input sequences determined as valid inputs by the unknown binary program, the unknown binary program being unknown based on source code of the unknown binary program being unavailable;

executing an instrumented version of the unknown binary program separately for each input sequence, each execution of the instrumented version of the unknown binary program using one of the input sequences as inputs to the instrumented version of the unknown binary program;

for each execution of the instrumented version of the unknown binary program, generating a set of execution traces by recording execution traces generated by the execution of the instrumented version of the unknown binary program;

generating at least two control flow graphs for at least two execution traces;

comparing the sets of execution traces including comparing the at least two control flow graphs with each other; and

determining which of the plurality of input sequences the unknown binary program accepts as valid based on the comparison of the sets of execution traces, wherein a valid input sequence includes a first input that is a precondition for a subsequent second input in the valid input sequence.

12. The one or more non-transitory computer readable media of claim 11, wherein the input includes a command determined as valid for the unknown binary program and an argument associated with the command, the argument also determined as valid for the unknown binary program.

13. The one or more non-transitory computer readable media of claim 11, wherein the operation of generating the sets of execution traces further comprises selecting a portion of the execution traces for each execution of the instrumented version of the unknown binary program for inclusion in the sets of execution traces, the portion of the execution traces selected for the sets of execution traces being the execution traces generated after last inputs of the input sequences are provided to the unknown binary program.

14. The one or more non-transitory computer readable media of claim 13, wherein the operation of selecting the portion of the execution traces for inclusion in the sets of execution traces, further comprises:

executing the instrumented version of the unknown binary program without any inputs;

determining a plurality of the execution traces generated by the execution of the instrumented version of the unknown binary program at an end of the execution without any inputs;

setting the determined plurality of execution traces as partition execution traces; and

selecting the portion of the execution traces generated during execution of the instrumented version of the unknown binary program using the input sequences based on the portion of the execution traces occurring between a next to last occurrence and a last occurrence of the partition execution traces.

15. The one or more non-transitory computer readable media of claim 11, wherein comparing the at least two control flow graphs with each other comprises:

generating a string representation for each of the at least two control flow graphs; and

comparing the string representations.

16. The one or more non-transitory computer readable media of claim 11, wherein an execution trace of one of the sets of execution traces represents a memory address associated with a straight-line block of instructions executed in the unknown binary program that is output by the instrumented version of the unknown binary program and not output by an un-instrumented version of the unknown binary program.

17. The one or more non-transitory computer readable media of claim 16, wherein a last input in each input sequence of the plurality of input sequences is the same and the plurality of input sequences is a set of input sequences, the operations further comprising repeating the operations of claim 11 for a plurality of other sets of input sequences, wherein a last input for each input sequence of each set of the other sets of input sequences is the same and the last input for each set of input sequences is different from the last input of the other sets of input sequences.

18. The one or more non-transitory computer readable media of claim 11, wherein when the comparison of the sets of execution traces indicates that the sets of execution traces are the same, none of the input sequences are determined to be accepted by the unknown binary program.

19. The one or more non-transitory computer readable media of claim 11, wherein when the comparison of the sets of execution traces indicates that one of the sets of execution traces is different than at least another two of the sets of execution traces that are the same, an input sequence corresponding to the one of the sets of execution traces is determined to be accepted by the unknown binary program.

20. A system to determine valid input sequences for an unknown binary program, the system comprising:

one or more processors;

one or more computer readable media configured to store instructions that when executed by the one or more processors perform operations, the operations comprising;

obtaining a plurality of input sequences of unknown validity for the unknown binary program, each of the input sequences including two or more different inputs, the inputs for the input sequences determined as valid inputs for the unknown binary program, the unknown binary program being unknown based on source code of the unknown binary program being unavailable;

executing an instrumented version of the unknown binary program separately for each input sequence, each execution of the instrumented version of the unknown binary program using one of the input sequences as inputs to the instrumented version of the unknown binary program;

for each execution of the instrumented version of the unknown binary program, generating a set of execution traces by recording execution traces generated by the execution of the instrumented version of the unknown binary program;

generating at least two control flow graphs for at least two execution traces;

comparing the sets of execution traces including comparing the at least two control flow graphs with each other; and

determining which of the plurality of input sequences the unknown binary program accepts as valid based on the comparison of the sets of execution traces, wherein a valid input sequence includes a first input that is a precondition for a subsequent second input in the valid input sequence.