Method of performing a reverse analysis of a program and its apparatus

A method of performing a reverse analysis of a program, analyzing contents of a program and extracting a specification of a program, comprising the steps of:

• preparing a first control flow comprising a syntax tree obtained by performing a syntax analysis of a program and connecting blocks in the order of an execution, each respective block comprises a series of statements which are executed in a predetermined order and do not include a branch;
• preparing a second control flow by finding a portion of a loop in said prepared first control flow, cutting the loop at a point of the loop, connecting said blocks designating contents of a process of said loop in a predetermined order corresponding to said cut point and connecting said connected plurality of blocks to a symbol designating the loop;
• finding the portion of said second control flow which corresponds to the loop and expressing the portion corresponding to the loop in a hierarchical manner in accordance with contents of said loop;
• finding a branching point and a merging point of the second control flow which are not included in said loop, and expressing said branching or merging point in a hierarchical manner in accordance with a structure of said portions not included in the loop by using a symbol of said branching merging point;
• preparing a third control flow by finding a portion of said control flow which is other than said loop portion and said branching or merging portions and can be executed sequentially, and expressing said portion to be sequentially executed by using a symbol designating a sequential execution in a hierarchical manner with the hierarchical expression of said loop and the hierarchical expression of said branching or merging portions;
• and
• obtaining a conditional expression for executing a particular statement in the program by using the third control flow.

An apparatus for performing a reverse analysis of a program, analyzing contents of a program to be executed and extracting a specification of a program, comprising:

• means for preparing a first control flow comprising a syntax tree obtained by performing a syntax analysis of a program and connecting blocks of an order of an execution, each respective block comprises a series of statements which are executed in a predetermined order and do not include a branch;
• means for preparing a second control flow by finding a portion of a loop in said prepared first control flow, cutting the loop at a point of the loop, connecting said blocks designating contents of a process of said loop in a predetermined order corresponding to said cut point and connecting said connected plurality of blocks to a symbol designating the loop, thereby extracting a specification of the program by using said second control flow;
• means for finding said second control flow which corresponds to the loop and expressing the portion corresponding to the loop in accordance with contents of said loop,
• in a hierarchical manner, finding a branching point and a merging point of the second control flow which are not included in said loop, and expressing said branching or said merging point in a hierarchical manner in accordance with a structure of said portions not included in the loop by using a symbol of said merging point;
• preparing a third control flow by finding a portion of said control flow which is other than said loop portion and said branching or merging portions and can be executed sequentially, and expressing said portion to be sequentially executed by using a symbol designating a sequential execution in a hierarchical manner with the hierarchical expression of said loop and the hierarchical expression of said branching or merging portions;
• and
• extracting a specification of a program by using said third control flow.