JP2016181228A - Source code calculation device and source code calculation method - Google Patents

Abstract

[Problem] To provide a technology for more appropriately analyzing software programs. [Solution] A source code calculation device for analyzing source code of a software program, comprising: a control flow graph generation unit that analyzes the syntax of the source code and generates a control flow graph in which the software program is represented by basic blocks, which are sets of instructions with no internal branches or joins, and a directed graph showing the control structure between the basic blocks; and a resolution unit that searches for a predetermined solution target in the software program based on the control flow graph in which parts whose values are not determined by the analysis of the syntax of the software program are left undetermined, calculates a reaching definition of the solution target using the control flow graph, and reconstructs the control flow graph by reflecting a value obtained from the reaching definition in the control flow graph. [Selected Figure] Figure 1

Description

  The present invention relates to a technique for analyzing a source code of a software program for a microcontroller.

  In recent years, some microcontrollers (hereinafter referred to as “microcomputers”) have been discontinued. With the end of production of microcomputers, replacement of microcomputers that have been discontinued with other microcomputers is being promoted in industrial equipment with built-in microcomputers. Therefore, it is required to redesign embedded software designed for one microcomputer for another microcomputer.

  Some products that have microcomputers that are no longer in production have software programs written entirely or partially in assembly language. Since the specification of the assembly language varies depending on the microcomputer product, the source code written in the assembly language is different from the source code of the high-level language such as C language, and portability between microcomputers is low. In addition, since the architecture varies depending on the microcomputer product, the assembly language source code cannot be handled by simple conversion in units of instructions in redesigning the software program. For example, it is difficult to uniquely define the conversion procedure in units of instructions, and the set of instructions means that after analyzing the source code once, including microcomputer internal processing such as flags, memory map, peripheral circuit compatibility, etc. Conversion is performed in consideration of the processing contents to be performed.

  From the above background, static analysis of source code described in assembly language, especially analysis of data flow (data flow) is important. If the source code can be analyzed at the data flow level, it is possible to grasp the processing contents that the instruction set means. However, in order to modify the source code in consideration of the data flow in particular, it is essential to read the source code thoroughly. When working manually, a high skill and a large amount of man-hour are required. Therefore, if the analysis of the software program at the data flow level can be automated, a great reduction in man-hours can be expected.

  Patent Document 1 describes a program parallelization support apparatus that determines whether processing can be parallelized in the process of converting source code to machine code, and generates parallelized machine code if possible. Has been. In Patent Literature 1, source code is analyzed at the data flow level to determine whether or not a program can be parallelized, and factors that inhibit parallelization are extracted.

JP 2009-129179 A

  As described above, in order to correct a source code written for one microcomputer for another microcomputer, it is necessary to analyze the source code at the data flow level. CFG (control flow graph) is used for the analysis of the software program at the data flow level. The CFG represents a software program by a basic block that does not have branching and merging therein and a directed graph that indicates a control structure such as branching or merging between the basic blocks. The CFG can be obtained by parsing the source code.

  Analysis of the software program at the data flow level is realized by calculating the arrival definition using CFG. The arrival definition is a set of data definition instructions that reach the entry of each basic block. From the arrival definition, it is possible to know a dependency relationship between instructions and possible values of a variable such as a register. By utilizing such information for source code analysis, it becomes possible to analyze the program at the data flow level. Also, the CFG must be complete to allow such software programs to be analyzed at the data flow level.

  As described above, CFG is obtained by parsing source code. However, in some cases, a complete CFG cannot be obtained just by analyzing the syntax of the source code. For example, when a branch instruction in the indirect addressing mode is included in the source code, a complete CFG cannot be obtained only by parsing the source code. This is because in the indirect addressing mode, even if the source code is parsed, the actual address address cannot be obtained directly. If the actual address is not known, it is difficult to determine the branch destination of the branch instruction. The CFG cannot be completed unless the branch destination of the branch instruction is known.

  Patent Document 1 describes a method for determining the possibility of parallelization of a program. The method is to analyze CFG to obtain C language pointer information and use the obtained pointer information as an index for determining whether or not parallelization is possible. This pointer realizes processing similar to an instruction in the indirect addressing mode. That is, a process is realized in which the content of the variable indicated by the pointer is set as an address value, and data at the address on the memory indicated by the address value is referred to or updated. At that time, in the technique described in Patent Document 1, the pointer is analyzed using only the CFG obtained directly from the source code, and it is determined whether the pointer has a dependency. However, since the technique of Patent Document 1 is intended to determine the possibility of parallelization, it is not necessary to consider the address value indicated by the pointer when a specific instruction is executed.

  On the other hand, when modifying the embedded software of one microcomputer for another microcomputer, the source code is analyzed at the data flow level, the address value of the data to be referenced or updated is obtained, and the data at that address is also referenced in the new microcomputer. Or the software program needs to be modified to update. In addition, since the address value is unique to each microcomputer, it may inevitably be replaced. For this reason, it is indispensable to calculate an address value to replace a new instruction by redesigning the software program.

  However, since the specific address value is not derived in the process disclosed in Patent Document 1, a complete CFG cannot be obtained when the address value indicated by the pointer affects the CFG.

  As described above, the technique of Patent Document 1 is insufficient to rewrite a software program of a microcomputer for another microcomputer having a different architecture, and there is a technique for analyzing a software program more appropriately including an indirect addressing mode. is necessary.

  An object of the present invention is to provide a technique for more appropriately analyzing a software program.

  A source code arithmetic device according to an aspect of the present invention is a source code arithmetic device for analyzing a source code of a software program, analyzing the syntax of the source code, and branching and merging the software program internally. A control flow graph generation unit that generates a control flow graph represented by a basic block that is a set of instructions that do not have and a directed graph that indicates a control structure between the basic blocks, and a portion whose value is not determined by analyzing the syntax of the software program A predetermined solution object in the software program is searched based on the control flow graph in which undetermined is determined, the arrival definition of the solution object is calculated using the control flow graph, and the value obtained from the arrival definition is Reconstruct the control flow graph by reflecting it in the control flow graph Has a that solves part.

  According to the present invention, the control flow graph obtained by parsing the software program is searched for a solution target causing an undetermined value, and the solution target is solved using the control flow graph, and obtained by the analysis. By reflecting the value in the control flow graph, the portion that is undetermined is determined. Since the part that is not clarified by the syntax analysis is solved using the control flow graph, the software program can be analyzed more appropriately.

It is a block diagram which shows the basic composition of the source code analysis apparatus 100 by this embodiment. It is a figure which shows an example of CFG produced | generated based on the source code and it. It is a figure which shows an example of CFG produced | generated based on the source code and it. It is a block diagram of address value resolution part BL102. It is a flowchart which shows the process of the source code analyzer by this embodiment. It is a figure which shows the image of CFG management table OB103. It is the flowchart which detailed the series of processes from step S404 of FIG. 4 to S410. It is a figure which shows the image of the search in a branch. It is a figure which illustrates a mode that a CFG object is converted. It is a flowchart of the analysis process by program analysis process part BL103. It is a figure which shows a mode that the analysis result used as the format which a human being can decipher easily is displayed on the screen. It is a figure which shows the analysis result of the format which a computer can batch-process. It is a block diagram which shows a part of source code analysis apparatus by other embodiment. It is a flowchart of the analysis process of the source code analyzer by other embodiment.

  Hereinafter, the source code analysis apparatus according to the present embodiment will be described with reference to the drawings. The source code analysis apparatus is an apparatus that realizes a predetermined source code analysis method, and can be used, for example, to redesign a software program for a certain microcomputer for another microcomputer.

  FIG. 1 is a block diagram showing a basic configuration of a source code analysis apparatus 100 according to the present embodiment. Referring to FIG. 1, the source code analysis apparatus 100 includes a CFG generation unit BL101, an address value resolution unit BL102, a CFG management table OB103, a program analysis processing unit BL103, and a program optimization processing unit BL104. .

  The CFG generation unit BL101 receives a source code OB101 described in an assembly language or the like, analyzes the syntax of the source code OB101, and generates a control flow graph (CFG). The generated CFG becomes the CFG object OB102. The CFG is graph data generated by analyzing the syntax of the source code OB101, and the data structure thereof includes a basic block that does not have branching and merging therein, a directed graph that indicates the flow of data between the basic blocks, It is expressed by

  The address value resolution unit BL102 performs data flow analysis of the source code OB101 based on the CFG object OB102. At that time, the address value resolution unit BL102 searches for an indirect addressing mode instruction in the CFG object OB102, and acquires address information indicating an effective address referred to by the instruction.

  Further, the address value resolution unit BL102 reflects the acquired address information on the CFG object OB102 used for the data flow analysis, adds predetermined management information to the reconfigured CFG object OB102, and generates a CFG management table OB103 as an analysis result. To record. The management information includes identification information of the CFG object OB102 and path trace information indicating a program path from the start position to the indirect addressing mode instruction targeted for address resolution.

  The CFG management table OB103 holds, in a database, an analysis result including address information indicating an effective address referred to by the indirect addressing mode instruction acquired by the address value resolution unit BL102 and management information.

  The program analysis processing unit BL103 generates a CFG object in which the CFG generation unit BL101 generates the source code OB101 and the address value resolution unit BL102 reflects the result of the address resolution of the instruction in the indirect addressing mode. A predetermined analysis process for analyzing a predetermined analysis target instruction is executed, and the analysis result is output as a program analysis result OB105. For example, the predetermined analysis process is a process for calculating the arrival definition of the instruction to be analyzed by data flow analysis. In that case, the calculated arrival definition becomes the analysis result. Based on the CFG object OB102 registered in the CFG management table OB103, the program analysis result OB105 is converted into the source code OB106 in a format that can be processed by a new microcomputer after replacement of the source code OB101 for the microcomputer before replacement. Information that is referred to by the machine or human that performs the conversion.

  The program optimization processing unit BL104 optimizes the input source code OB101 based on the program analysis result OB105. In this optimization, the source code OB101 is made into a format that can be easily processed by the new microcomputer after replacement, can be efficiently processed by the new microcomputer, or human work can be facilitated or reduced. It is to be. Specifically, it is preferable to convert the program analysis result OB105 into a format that can be automatically processed by the new microcomputer after replacement, or a format that is highly readable for humans.

  2A to 2B are diagrams illustrating an example of a source code and a CFG generated based on the source code. FIG. 2A shows an example of source code, and FIG. 2B shows a CFG object generated from the source code of FIG. 2A.

  Looking at the CFG object OB102 in FIG. 2B, the source code 200 shown in FIG. 2A is divided into basic blocks B202, B203, and B204 that do not include branching and merging. Further, five blocks B201 to 205 including a start (START) block B201 and an end (END) block B205 are connected by a directed graph whose connection state is indicated by an arrow.

  FIG. 3 is a block diagram of the address value resolution unit BL102. Referring to FIG. 3, the address value resolution unit BL102 includes a program path search unit BL301, a data flow analysis unit BL302, a CFG reconstruction unit BL303, and a CFG verification unit BL304.

  The program path search unit BL301 searches for the START block B201 from the input CFG object OB102, traces the instruction of each basic block from the START block 201, and searches for the analysis target instruction. The analysis target instruction is an indirect addressing mode instruction as a specific example. When the program path search unit BL301 finds an instruction to be analyzed, it outputs program path information indicating a program path from the start position to the instruction.

  The data flow analysis unit BL302 executes a data flow analysis process based on the CFG object OB102 based on the program path information from the program path search unit BL301, thereby providing a value (address candidate) that is a candidate for the effective address of the instruction to be analyzed. Value).

  The CFG reconstruction unit BL303 reconstructs the CFG object OB102 based on the address candidate value generated by the data flow analysis unit BL302.

  The CFG verification unit BL304 verifies the reconfigured CFG object (reconfigured CFG object OB301) and stores it in the CFG management table OB103 together with the management information. Further, when there is a possibility that a CFG having another configuration may be obtained, the CFG verification unit BL304 returns the reconfigured CFG object OB301 to the program path search unit BL301 again. As the verification of the CFG object OB301, for example, it may be verified that the program path from the start position to the analysis target instruction can be normally traced.

  Returning to FIG. 1, the CFG management table OB103 includes a CFG object generated by the CFG generation unit BL101 or a reconfigured CFG object reconstructed from the CFG object (hereinafter collectively referred to as “CFG object OB102”), its management information, Is a table that stores them in a state where they are linked to each other. The management information includes identification information of the CFG object OB102 and program path information from the CFG object OB102 to the indirect addressing mode instruction that is an analysis target instruction that contributes to generation.

  The program analysis processing unit BL103 generates information necessary for porting the source code by analyzing the CFG object OB102 registered in the CFG management table OB103, and outputs the generated program analysis result OB105.

  Further, the program optimization processing unit BL104 performs program optimization processing on the source code OB101 based on the program analysis result OB105 generated by the program analysis processing unit BL103, and outputs the processing result. The optimization process here is a process of converting the source code OB101 into a format that can be processed by the porting-destination microcomputer, or a process of generating information useful for the conversion. For example, the program optimization processing unit BL104 outputs the optimized source code OB106.

  FIG. 4 is a flowchart showing processing of the source code analysis apparatus according to the present embodiment.

  First, the source code analysis apparatus 100 performs lexical analysis and syntax analysis of the input source code OB101, and checks whether there is an error in the programming language in the source code OB101 (step S400).

  If there is a grammatical error in the source code OB101, the source code analyzing apparatus 100 notifies the error and ends the process (step S401). If no grammatical error is found in the source code OB101, the source code analysis apparatus 100 generates a CFG object OB102 as shown in FIG. 2B (step S401). In the process of step S401, the program may include an indirect addressing mode (IDA) instruction. However, since a specific value of the address cannot be estimated at this time, it is set as an undetermined value.

  Next, the source code analyzing apparatus 100 traces the program path of the source code OB101 and determines whether there is an instruction in the indirect addressing mode (step S402). When the indirect addressing mode instruction is not found in the source code OB101, the source code analyzing apparatus 100 outputs the CFG object OB102 obtained by the process of step S401, and ends the process. That is, when the end point of the program is reached without finding the indirect addressing mode instruction, the process is terminated.

  When the instruction of the indirect addressing mode is included in the source code OB101, the source code analysis apparatus 100 registers the CFG object OB102 including the instruction obtained in the process of step S401 as the search target CFG (step S403). Then, the program path search process is started (step S404).

  When an instruction in the indirect addressing mode is found in the program path search process, the source code analysis apparatus 100 performs data flow analysis using the CFG object OB 102 currently being searched for, and calculates the arrival definition, thereby performing indirect addressing. A candidate value for the address of the mode instruction is calculated (step S405). The arrival definition can be obtained by calculating the data flow equation of Expression (1).

  In Expression (1), IN (B) represents a set of definition instructions that reach the basic block B of the CFG object OB102. OUT (B) is a set of definition instructions effective at the exit of the basic block B. Pred (B) is a set of preceding blocks of the basic block B. P is an element of Pred (B).

  DEF (B) is a set of definition instructions defined in the basic block B. KILL (B) is a set of definition instructions that disappear in the basic block B due to redefinition or the like. This data flow equation is calculated in the basic block to which the indirect addressing mode instruction found in the process of step S404 belongs, and an effective definition set (arrival definition) of the register or memory holding the address information in the instruction is calculated. The address value can be obtained by interpreting this arrival definition by an instruction set simulator or the like.

  Next, the source code analyzing apparatus 100 confirms whether the address value is valid (step S406). If the obtained address value is not a valid address value, an error is output and the process is terminated (step S411).

  If the obtained address value is valid, the source code analyzing apparatus 100 duplicates the CFG object OB102 serving as the search target CFG, and reconfigures the CFG indicated by the CFG object OB based on the address candidate value ( Step S407). When reconfiguring the CFG, information indicating that the instruction is in the indirect addressing mode is left. Depending on the source code OB101, a plurality of address values may be obtained. For each address value, a copy of the CFG object OB102 is duplicated and reconfigured using the address value.

  Next, the source code analyzing apparatus 100 verifies whether or not the analysis end condition is satisfied (step S408). The analysis end condition in step S408 is a condition that the structure of the reconstructed CFG object OB301 circulates. For example, when the structure of the reconfigured CFG object OB301, which is a reconfigured CFG, has already been registered in the CFG management table OB103, there is a high possibility that the CFG having the same structure repeatedly makes a statement. When the CFG having the same structure is repeated, that is, when the CFG structure circulates, there is no more CFG obtained newly. In that case, it can be said that no further search is necessary, and the analysis end condition is satisfied. If the analysis end condition is satisfied, the source code analyzing apparatus 100 ends the process (Yes in step S408).

  On the other hand, if the analysis end condition is not satisfied, the source code analysis apparatus 100 registers the reconstructed CFG object OB301 together with the management information in the CFG management table OB103 (step S409).

  FIG. 5 is a diagram showing an image of the CFG management table OB103. “CFG” in FIG. 5 is the reconstructed CFG object OB301. “NO.X” is an identification number of the reconstructed CFG object OB301, and “PATH” is program path information. “NO.X” and “PATH” correspond to management information.

  After that, the source code analysis apparatus 100 registers the reconstructed CFG object OB301 as a search target CFG, and executes the search process of step S404 with the indirect addressing mode instruction that executed the address resolution process as the starting point (step S410).

  If a grammatical error is found in the source code OB101 in step S400, or if the address is not a valid value in step S406, error information is generated in step S411 and the process ends. When this error information is generated, an operation of manually analyzing and reworking the program is always generated in the process of porting the source code OB101. Therefore, it is preferable to output detailed information so that error information can be easily understood by humans. For example, the error information includes a specific address value, an arrival definition that contributes to the determination of the address value, and related instruction group information.

  FIG. 6 is a flowchart detailing a series of processing from steps S404 to S410 in FIG.

  The source code analyzing apparatus 100 searches for a program head instruction from the START block B201 (step S700). The head instruction of the program (hereinafter referred to as “program head instruction”) can be found by referring to the subsequent block following the START block in the CFG object OB102 generated from the source code OB101.

  Next, the source code analyzing apparatus 100 initializes the path trace information in which the trace of the previous path is recorded, and sets the program head instruction as a search point (step S701). The search point refers to the current position (command) in searching for a command that follows the program path. Next, the source code analyzing apparatus 100 adds a search point instruction to the path trace information (step S702), and sets the next instruction as a search point (step S703).

  There may be branches in the program. When the source code analyzing apparatus 100 finds a branch in the program, the source code analyzing apparatus 100 performs a nondeterministic search for each branch. FIG. 7 is a diagram showing an image of searching at a branch.

  Referring to FIG. 7, an example in which the basic block B800 branches to the basic block B801 or B802 by an instruction (branch instruction) 104 is shown. In that case, the next search point of the instruction 104 is either the instruction 105 or the instruction 115. At this time, the path trace information P803 is duplicated to generate path trace information P804 when searching for the basic block B801 and path trace information P805 when searching for the basic block B802. They are used when following the program path.

  When the search point is the program end point, the source code analyzing apparatus 100 ends the analysis process in the program path being searched (step S704). Only when all the program paths are searched and the analysis process is completed, the source code analysis apparatus 100 determines that the complete termination condition is satisfied.

  However, if there is a loop in the program, the program path may be infinite and the analysis process may not be completed. In this case, by limiting the program path search condition when searching for a loop path, the search for an instruction that follows the program path can be terminated. For example, the number of times of passing through the same loop is counted, and when the count value (the number of loops) reaches a predetermined value which is a threshold value, it is determined that the loop end condition is satisfied and the search for the program path is ended. Also good. In that case, the threshold value may be manually set by the user. Further, the loop end condition may be determined by data flow analysis.

  Usually, since the address value specified by the instruction in the indirect addressing mode is often only an address in an area limited in the address space, the number of loops is usually limited. In particular, in the case of an old designed microcomputer program that is to be discontinued, the size of the memory space is small, and the memory area that can be taken by the address specified by the instruction in the indirect addressing mode is often extremely limited. Therefore, for the purpose of analyzing the source code in order to port the software program of the microcomputer that has been discontinued, it is a useful and realistic technique to determine the loop end condition by the number of loops.

  Next, the source code analyzing apparatus 100 determines whether or not the search point is an indirect addressing mode instruction (step S705). Otherwise, the source code analysis apparatus 100 adds to the path trace information and advances the search point to the next command and continues the search process (steps S705, S702, and S703). On the other hand, if the search point is an instruction in the indirect addressing mode in the determination in step S705, the source code analysis device 100 performs data flow analysis using the CFG object OB102 used in the search process, and The arrival definition is calculated, and the address value of the instruction is acquired (steps S706 and S707).

  For the calculation of the data flow equation described above in Equation (1), a method of repeating the calculation until the data flow reaches the fixed point as a whole is often used. In that case, an instruction not included in the path trace information may be included in the arrival definition. Therefore, it is preferable to remove instructions that are not included in the path trace information from the arrival definition obtained by the data flow analysis using Expression (1). By calculating the candidate value of the address based on the arrival definition from which the instruction not included in the path trace information is removed, an address value that can be reliably accessed by the software program can be obtained.

  Next, the source code analyzing apparatus 100 determines whether or not the address value obtained in the above process is valid (step S708). If the address value is valid, the source code analysis apparatus 100 duplicates the CFG object OB102 used in the search process, reconfigures it based on the address value, and generates a reconfigured CFG object OB102 (step S709). ).

  Indirect addressing mode instructions include jump instructions and non-jump instructions. When the instruction in the indirect addressing mode is a jump instruction, the source code analysis apparatus 100 reconfigures the CFG object OB102 including the connection relationship between basic blocks. On the other hand, when the instruction in the indirect addressing mode is a non-jump instruction, the source code analysis apparatus 100 only needs to convert the instruction into an absolute value notation.

  Even when the CFG object OB102 is reconfigured based on the address resolution of the instruction in the indirect addressing mode, information (flag or the like) that can identify that the instruction was originally an instruction in the indirect addressing mode is given. This information is used as an index when resolving the address value of the instruction during re-search. At this time, information of a register or memory that holds an address value may also be held.

  FIG. 8 is a diagram illustrating a state in which a CFG object is converted.

  Here, the CFG 900 is a CFG object being used for program path search. CFG 901 and CFG 902 are CFG objects after being reconstructed. For example, in the jump instruction in the indirect addressing mode in the instruction 103, consider a case where the register R0 for storing an address value has a value of 0xXXXX or 0xYYYY, as illustrated by a dashed arrow. In this case, two copies of CFG900 are copied, and one of them obtains CFG901 by reconfiguring CFG900 based on register address R0 = 0xXXXX. The other obtains CFG 902 by reconfiguring CFG 900 based on register address R0 = 0xYYYY.

  The CFG object reconstructed in step S709 is registered in the CFG management table OB103 together with the management information (step S710). The image of the state in which the CFG object is stored is as shown in FIG. 5, and includes management information including identification information of the CFG object OB102 and path trace information from the start position to the instruction to be resolved.

  Next, the source code analyzing apparatus 100 sets the reconstructed CFG object OB301 as a CFG object to be searched for a program path, and repeats the search process until the analysis end condition is satisfied (step S711).

  If there are a plurality of address value candidates in step S709, the source code analysis apparatus 100 performs a search process along the program path for each reconstructed CFG object OB301 reconstructed based on each address value. Run. At this time, the source code analyzing apparatus 100 also duplicates the path trace information and executes the process nondeterministically as in the case where the branch instruction is found in the program path search. If a candidate value for a valid address cannot be obtained in step S708, the source code analyzing apparatus 100 generates an error as described above and ends the process (step S712).

  As a result of the above processing, the CFG management table OB103 can hold patterns of all CFG objects OB102 that can be taken by the program, and these CFG objects OB102 have already taken into account the influence of instructions in the indirect addressing mode. .

  FIG. 9 is a flowchart of analysis processing by the program analysis processing unit BL103. The analysis process is executed using the CFG object OB102 registered in the CFG management table OB103.

  First, the program analysis processing unit BL103 identifies an instruction to be analyzed (step S1000). The analysis target instruction includes a method of manually specifying by the user, a method of automatically specifying mechanically according to a predetermined condition, and the like.

  When the analysis target instruction is specified, the program analysis processing unit BL103 accesses the CFG management table OB103 and acquires the first CFG object OB102 (step S1001). In the CFG management table OB103, the data of the CFG object OB102 can be managed by various management methods. The simplest method is to record and manage in a list format. When managing the CFG object OB102 as a list, the CFG object OB102 at the top of the list corresponds to the first CFG object OB102 described above.

  Next, the program analysis processing unit BL103 refers to the path trace information included in the management information associated with the first CFG object OB102 acquired from the CFG management table OB103, and sets the program path indicated by the path trace information. It is verified whether or not an instruction to be analyzed is included (step S1002).

  When the analysis target instruction is not included in the path trace information, it means that the CFG object OB102 is a CFG object OB102 that does not pass when the analysis target instruction is executed. Next, it is determined whether or not all CFG objects OB102 have been verified (step S1003). If all the CFG objects OB102 have been verified, the program analysis processing unit BL103 ends the process. If there is a CFG object OB102 that has not been verified yet, the program analysis processing unit BL103 acquires the next CFG object OB102 (step S1004), and the process returns to step S1002.

  If an analysis target instruction is included in the program path indicated by the path trace information in step S1002, the program analysis processing unit BL103 executes predetermined processing for analyzing the software program using the CFG object OB102 (step S1002). S1005). Various processes can be applied as the analysis process. As an example, there is a process of calculating the arrival definition of the instruction to be analyzed by data flow analysis.

  Next, the program analysis processing unit BL103 generates an analysis result including an instruction not included in the path trace information in the analysis processing in step S1005. It is removed (step S1006). This is because such an analysis result is invalid. For example, when analyzing a software program based on a data flow equation using a CFG object OB102 such as forward analysis or backward analysis, there may be a process of repeatedly solving the data flow equation until the arrival definition reaches a fixed point. . In such a case, an instruction that is executed after the analysis target instruction is executed may be included in the analysis result of the analysis target instruction. An analysis result based on information on a state in which an instruction to be executed later is not executed is invalid. In that case, since it is necessary to obtain the analysis result of the instruction based on the path trace information associated with the CFG object OB102, the program analysis processing unit BL103 removes the invalid analysis result in step S1006. .

  Next, the program analysis processing unit BL103 outputs the obtained analysis result (step S1007). Information related to the CFG object OB102 used for analyzing the instruction is added to the analysis result of the instruction to be analyzed. The information added to the CFG object OB102 added at this time may be identification information included in the management information linked to the CFG object OB102, or may be the CFG object OB102 itself including path trace information. Good.

  The program analysis processing unit BL103 may output the analysis result in a format that can be easily read by humans or a format that can be batch processed by a computer.

  FIG. 10 is a diagram illustrating a state in which an analysis result in a format that can be easily deciphered by a human being is displayed on the screen. In the example of FIG. 10, the image data including the image data indicating the data flow is in a format that can be browsed by the Web browser. FIG. 11 is a diagram illustrating an analysis result in a format that can be batch processed by a computer. In the example of FIG. 11, an analysis result (OB1200) described in an XML-based language, CSV (OB1201), binary data, and the like are output in a machine-processable format. Based on these processing results, the program optimization processing unit BL104 performs processing for optimizing the source code OB101 of the software program.

  As mentioned above, there are various possible optimization processes. For example, the process of converting the code to analyze the meaning of a plurality of instructions and efficiently realizing a process including the plurality of instructions, an internal register Delete unnecessary instructions including the process of automatically updating the process, process for optimizing the control structure, conversion of different memory space, extraction of instructions depending on IO, and process of generating highly readable code.

  As described above, according to the present embodiment, the CFG object OB102 can be generated while taking into consideration the influence of the instruction in the indirect addressing mode, and the analysis of the source code OB101 is executed by the systematic analysis based on the CFG object OB102. Can do. The analysis results can be viewed in a way that is highly readable by a browser, etc., or converted into a computer-recognizable format, reducing man-hours related to source code migration and optimized converted code Can be generated.

  Further, in the present embodiment, since the analysis is based on a program whose operation is guaranteed without aiming at defect verification represented by format verification or the like, the analysis can often be performed within a finite time, and the source code OB101 between different microcomputers. Useful when transplanting.

  In the present embodiment, the control flow graph generation unit (CFG generation unit BL101) analyzes the syntax of the source code OB101, and converts the software program into a basic block that is a set of instructions that do not have branching and merging therein, and A control flow graph (CFG) represented by a directed graph indicating a control structure between basic blocks is generated. The resolution unit (address value resolution unit BL102) searches for a predetermined resolution target in the software program based on a control flow graph in which a portion whose value is not determined by analysis of the syntax of the software program is undetermined, and uses the control flow graph Then, the arrival definition to be solved is calculated, and the control flow graph is reconstructed by reflecting the value obtained from the arrival definition in the control flow graph.

  According to this, a search target that causes an undetermined value is searched for in the control flow graph obtained by parsing the software program, the solution target is solved using the control flow graph, and the value obtained by the analysis Is reflected in the control flow graph to determine the portion that is an undetermined value. Since the part that is not clarified by the syntax analysis is solved using the control flow graph, the software program can be analyzed more appropriately.

  In the present embodiment, when the resolving unit (address value resolving unit BL102) reconstructs the control flow graph, the resolving target is searched for the next resolving target starting from the resolving target, and the resolving target is determined. The process of resolving and reconfiguring the control flow graph is repeated until all resolution targets in the software program are resolved.

  According to this, since the process of searching for and solving a solution target is repeated until all the solution targets are solved, the software program can be analyzed more appropriately.

  In the present embodiment, the program analysis processing unit BL103 analyzes the source code based on the reconfigured control flow graph. Since the source code can be analyzed using the reconfigured control flow graph, the software program can be analyzed more appropriately.

  In addition, according to the present embodiment, the program analysis processing unit BL103 analyzes the source code by data flow analysis based on the control flow graph. According to this, since the source code is analyzed by the data flow analysis, it is possible to determine a portion that becomes an undetermined value by the syntax analysis.

  In this embodiment, the program analysis processing unit BL103 outputs information obtained by analyzing the source code and the control flow graph used for the data flow analysis as analysis results. According to this, since the control flow graph is output together with the analysis result of the source code, it is possible to know the status of the data flow analysis performed in the source code analysis process.

Further, according to the present embodiment, when resolving the control flow graph, the resolving unit (address value resolving unit BL102) controls the path trace information indicating the program path from the start position of the software program to the control flow graph. Record along with the graph and refer to the path trace information for static analysis of the source code. According to this, since the path trace information is recorded and the static analysis of the software program is executed by referring to the recorded information, the software static analysis can be advanced along the program path indicated by the path trace information.
(Other embodiments)

  In the above-described embodiment, the analysis of the source code OB101 including the instruction in the indirect addressing mode is illustrated, but here, the analysis of the source code including the self-rewriting code is illustrated as another embodiment.

  The self-rewriting code is an instruction that uses a data copy instruction such as an MOV instruction to update the processing content of the program by rewriting data in the program code storage area of the program being executed. The self-modifying code can be easily described in an assembly language and used for various purposes. In the above-described embodiment, the instruction in the indirect addressing mode is supported. In the other embodiments, the instruction in the self-rewriting code is supported.

  FIG. 12 is a block diagram showing a part of a source code analyzing apparatus according to another embodiment. 12 is different from the source code analysis device 100 shown in FIG. 1 in that the address value resolution unit BL102 is replaced with a self-rewrite code resolution unit BL1300. It is shown.

  The self-rewriting code resolution unit BL1300 includes a self-rewriting code determination unit BL1301 and a self-rewriting code identification unit BL1302.

  When the instruction in the CFG object OB102 is an instruction to write data in the memory area, the self-rewriting code determination unit BL1301 determines whether the memory area is a program area. If the instruction is to rewrite the program area with an instruction to write data, the instruction is a self-rewriting code.

  If the instruction is a self-rewriting code, the self-rewriting code identifying unit BL1302 acquires a value written by the instruction and identifies specific memory contents from the value. If the contents of the memory rewritten by the self-rewriting code are known, the source code OB101 can be analyzed.

  The self-rewriting code determination unit BL1301 holds a program area definition list OB1301 that defines address information of a program area in the memory as an index for determining whether or not the instruction is a self-rewriting code.

  As a method of knowing the program area of the memory, for example, there are the following three methods. The first is a method of judging from source code. The second is a method of judging from the manual of the microcomputer. The third method is a method of analyzing the data flow of the source code OB101 and determining from a memory area referred to as an execution code based on information of the program counter.

  The self-rewriting code identification unit BL1302 holds an instruction code table OB1302 that holds information indicating a correspondence relationship between a value (binary value) written in the program area of the memory and information (instruction information) about an instruction indicated by the value. have. Information stored in the instruction code table OB1302 can be obtained mainly from the specifications of the microcomputer.

  FIG. 13 is a flowchart of analysis processing of a source code analysis apparatus according to another embodiment.

  First, the source code analyzing apparatus 100 generates a CFG from the source code OB101 and checks whether or not a self-rewriting code exists in the source code OB101, as in the case of analyzing the indirect addressing mode instruction of FIG. (Step S1400). Whether or not an instruction is a self-rewriting code is determined based on the program area definition list OB1301 whether or not the memory address to which data is written by the instruction is a program area. The memory address to which data is written is the program area. If there is, it is determined that the instruction is a self-rewriting code.

  When the existence of the self-rewriting code is confirmed in the source code OB101, the source code analyzing apparatus 100 sets the CFG object OB102 designated by the input as a search target (step S1401).

  Next, the source code analyzing apparatus 100 traces the program path of the CFG object OB102 to be searched from the top, and searches for a self-rewriting code (step S1402).

  When the program path is traced and the end position of the software program is reached, the source code analyzing apparatus 100 outputs an error indicating that the source code OB101 cannot be analyzed (step S1409), and the process ends.

  If a branch is found while following the program path, the source code analyzing apparatus 100 performs a nondeterministic search for each branch destination as in the case of finding an instruction in the indirect addressing mode. The source code analyzing apparatus 100 calculates the arrival definition for the self-rewritten code based on the CFG object OB102 used in the search, and identifies the value to be written (step S1403). This written value is used to identify the contents of the instruction.

  Next, the source code analyzing apparatus 100 obtains the contents of the newly rewritten instruction with reference to the instruction code table OB1302 from the value obtained in the process of step S1403, and the code representing the instruction is valid. It is verified whether or not there is (step S1404). If the instruction is not valid, the source code analyzing apparatus 100 outputs an error indicating that the source code 20 cannot be analyzed and ends the processing (step S1409).

  If the instruction is valid, the source code analyzing apparatus 100 duplicates the CFG object OB102 to be searched, and reconfigures the CFG object OB102 based on the information of the instruction to be rewritten (step S1305).

  Further, the source code analyzing apparatus 100 checks whether or not the analysis end condition is satisfied, as in the case of the indirect addressing mode instruction (step S1406). If the analysis end condition is satisfied, the source code analyzing apparatus 100 ends the process. If the analysis end condition is not satisfied, the source code analysis apparatus 100 registers the reconfigured CFG object OB102 (reconstructed CFG object OB301) in the CFG management table OB103 (step S1407). Further, the source code analysis apparatus 100 sets the reconstructed CFG object OB301 as a search target (step S1408), returns to step S1402, and repeats the processing until the analysis end condition is satisfied.

  Through the above processing, the source code analyzing apparatus 100 can acquire the CFG object OB102 of the source code OB101 including the self-rewriting code. Further, the source code analyzing apparatus 100 can realize static analysis of the source code OB101 by using the CFG object OB102. As in the indirect addressing mode, the analysis result obtained from the obtained CFG can be converted into various formats to reduce the man-hours related to the porting of the source code OB101 or the optimized converted result. It is also possible to automatically generate source code.

  Each of the embodiments of the present invention described above is an example for explaining the present invention, and is not intended to limit the scope of the present invention only to those embodiments. Those skilled in the art can implement the present invention in various other modes without departing from the gist of the present invention.

DESCRIPTION OF SYMBOLS 100 ... Source code analyzer, BL101 ... CFG generation part, BL102 ... Address value resolution part, BL103 ... Program analysis process part, BL104 ... Program optimization process part, BL1300 ... Code resolution part, BL1301 ... Code determination part, BL1302 ... Code Identification unit, BL301 ... Program path search unit, BL302 ... Data flow analysis unit, BL303 ... CFG reconstruction unit, BL304 ... CFG verification unit, OB101 ... Source code, OB102 ... CFG object, OB103 ... CFG management table, OB105 ... Program analysis Result, OB106 ... source code, OB1301 ... program area definition list, OB1302 ... instruction code table, OB301 ... reconstructed CFG object

Claims (10)

A source code arithmetic device for analyzing a source code of a software program,
Analyzing the syntax of the source code and generating a control flow graph representing the software program as a basic block that is a set of instructions that do not have branches and merges therein and a directed graph that indicates a control structure between the basic blocks A control flow graph generation unit;
Based on the control flow graph in which a portion whose value is not determined in the analysis of the syntax of the software program is undetermined, a predetermined resolution target in the software program is searched, and the resolution definition of the resolution target is determined using the control flow graph And resolving the control flow graph by reflecting the value obtained from the arrival definition in the control flow graph, and
A source code arithmetic unit having When the resolving unit reconstructs the control flow graph, it searches the next resolving target by tracing the program path starting from the resolved resolving target, resolves the resolving target, and reconstructs the control flow graph. Repeat the process until all resolution targets in the software program are resolved,
The source code arithmetic device according to claim 1.   The source code arithmetic device according to claim 1, further comprising a program analysis processing unit that analyzes the source code based on the reconfigured control flow graph.   4. The source code arithmetic device according to claim 3, wherein the program analysis processing unit analyzes the source code by data flow analysis based on the control flow graph.   5. The source code arithmetic device according to claim 4, wherein the program analysis processing unit outputs information obtained by analyzing the source code and the control flow graph used for the data flow analysis as an analysis result.   The resolving unit, when reconfiguring the control flow graph, records path trace information indicating a program path from the start position of the software program to the control flow graph together with the control flow graph, and refers to the path trace information The source code arithmetic device according to claim 1, wherein static analysis of the source code is performed.   The source code arithmetic device according to claim 1, wherein the solution target is an instruction in an indirect addressing mode.   The source code arithmetic device according to claim 1, wherein the solution target is an instruction to rewrite a program area during execution. A source code calculation method for analyzing a source code of a software program,
Control flow graph generation means analyzes the syntax of the source code, and represents the software program as a basic block that is a set of instructions that do not have branches and merges therein and a directed graph that indicates a control structure between the basic blocks. Generated control flow graph,
A solving means searches for a predetermined solution target in the software program based on the control flow graph in which a portion whose value is not determined in the analysis of the syntax of the software program is undetermined, and uses the control flow graph to solve the solution Reconstructing the control flow graph by calculating the target arrival definition and reflecting the value obtained from the arrival definition in the control flow graph;
Source code calculation method. When resolving the control flow graph, the solving means searches for a next resolution target by tracing the program path starting from the resolved resolution target, resolves the resolution target, and reconfigures the control flow graph. Repeat the process until all resolution targets in the software program are resolved,
The source code calculation method according to claim 9.