AUTOMATED PARALLEL SOFTWARE CODE IMPACT ANALYSIS

• US 20120110557A1
• Filed: 10/28/2010
• Published: 05/03/2012
• Est. Priority Date: 10/28/2010
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: SINGH, Abhishek, VASUDEVA, Sachin
• Granted Patent: US 8,683,449 B2
• Time in Patent Office: Days
• US Class Current: 717/133
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589
• CPC Class Codes: G06F 11/3668 Software testing software testing in telephone exchanges H04M3/242, testing of hardware G06F11/22
• CPC Class Codes: G06F 11/368 for test version control, e.g. updating test cases to a new software version
• CPC Class Codes: G06F 8/75 Structural analysis for program understanding

Abstract

A server device is configured to receive a request to identify a manner in which changed code propagates within an application; generate a group of blocks that correspond to code associated with a parent function corresponding to the application and which includes the changed code; perform an intra-procedural analysis on the group of blocks to identify a block that is affected by the changed code included within an epicenter block; perform an inter-procedural analysis on functions associated with the block, where, when performing the inter-procedural analysis, the server device is to generate another group of blocks associated with the functions, and identify another block that is affected by the changed code included within the epicenter block; and present, for display, information associated with the block or the other block that enables the application to be tested based on the block or the other block.

Claims

1. A method comprising:

receiving, by a server device, a request to perform a parallel impact analysis on a changed line of code, of a plurality of lines of code, associated with a software application;

generating, by the server device and in response to the request, a control flow graph that corresponds to a function associated with one or more of the plurality of lines of code, the one or more of the plurality of lines of code including the changed line of code,

where the control flow graph includes one or more blocks that correspond to the one or more of the plurality of lines of code, the one or more blocks including an epicenter block associated with the changed line of code;

traversing, by the server device, the one or more blocks to determine whether any of the one or more blocks are affected by a set of variables within the epicenter block;

identifying, by the server device and based on the traversing, at least one impacted block, of the one or more blocks, that is affected by the set of variables and one or more statements, associated with the at least one impacted block, that call one or more other functions;

generating, by the server device, other control flow graphs for the one or more functions, where each of the other control flow graphs include a different one or more blocks that correspond to a respective, different one or more of the plurality of lines of code;

traversing, by the server device, the different one or more blocks associated with each of the other control flow graphs to identify at least one other impacted block that is affected by the set of variables; and

presenting, by the server device and to a display device, identifiers associated with the at least one impacted block and the at least one other impacted block for display, where the identifiers permit the software application to be tested based on the at least one impacted block and the at least one other impacted block.

2. The method of claim 1, where generating the control flow graph includes:

mapping different portions of the one or more of the plurality of lines of code to the one or more blocks; and

mapping a particular portion of the one or more of the plurality of lines of code to the epicenter block, where the particular portion of the one or more lines of code includes the changed line of code.

3. The method of claim 2, further comprising:

creating logical interconnections between the one or more blocks based on a manner in which data or logic flows within the function.

4. The method of claim 1, where traversing the one or more blocks further includes:

identifying one or more variables that are defined within the epicenter block based on the changed line of code; and

associating the one or more variables with an impacted set of variables associated with the epicenter block.

5. The method of claim 1, where traversing the one or more blocks further includes:

examining lines of code, associated with each of the one or more blocks, to determine whether variables, within the each of the one or more blocks, is associated with a defined set of variables or a used set of variables; and

associating the variables with the defined set of variables or the used set of variables, corresponding to each of the one or more blocks, based on the determination.

6. The method of claim 5, where identifying the at least one impacted block includes:

identifying that a block, of the one or more blocks, is the at least one impacted block, when a variable, included in the set of variables, is associated with the used set of variables that corresponds to the block; and

identifying that another block, of the one or more blocks, is not an impacted block, when another variable, included in the set of variables, is associated with the defined set of variables that corresponds to the other block.

7. The method of claim 5, where the set of variables is an impacted set of variables;

and

where identifying the at least one impacted block includes;

determining that a block, of the one or more blocks, is not affected by the epicenter block when;

the block defines a variable that is associated with the impacted set of variables,

or

the block does not use a variable that is associated with the impacted set of variables.

8. The method of claim 1, where identifying the at least one impacted block includes:

detecting, within the at least one impacted block, a call statement associated with a first function, where the call statement indicates that the first function is called by the function;

detecting, within the at least one impacted block, a return statement associated with a second function, where the return statement indicates that the second function calls the function; and

assigning a distance to the first function or the second function.

9. The method of claim 8, where traversing the different one or more blocks associated with the each of the other control flow graphs further includes:

performing an inter-procedural impact analysis by creating an analysis thread that corresponds to a first control flow graph associated with the first function and another analysis thread that corresponds to a second control flow graph associated with the second function; and

simultaneously executing a plurality of analysis threads, associated with the distance, to identify the at least one other impacted block, where the analysis thread and the other analysis thread are associated with the plurality of analysis threads.

10. The method of claim 9, further comprising:

identifying a third function based on another call statement or another return statement detected within the at least one other impacted block;

assigning another distance to the third function that permits the server device to create a further analysis thread associated with the third function; and

simultaneously executing another plurality of analysis threads, associated with the other distance, to identify at least one further impacted block, where the further analysis thread is associated with the other plurality of analysis threads.

11. A server device comprising:

a processor to;

receive a request to identify a manner in which a changed line of code affects a plurality of lines of code associated with a software application,

generate one or more blocks that correspond to one or more of the plurality of lines of code associated with a parent function, where the parent function is associated with an act or operation performed by the software application and which includes the changed line of code,

perform, in response to the request, an intra-procedural analysis on the one or more blocks to identify at least one block, of the one or more blocks, that is affected by the changed line of code included within an epicenter block, of the one or more blocks,

perform an inter-procedural analysis on one or more functions associated with the at least one block, where, when performing the inter-procedural analysis the processor is to;

generate another one or more blocks associated with each of the one or more functions, and

identify at least one other block, of the other one or more blocks, that is affected by the changed line of code included within the epicenter block, and

present, for display on a display device, information associated with the at least one block or the at least one other block that enables the software application to be tested based on the at least one block or the at least one other block.

12. The server device of claim 11, where, when performing the intra-procedural analysis, the processor is further to:

mark the at least one block as having been affected by the changed line of code, and

perform the inter-procedural analysis based on the marking of the at least one block; and

where, when performing the inter-procedural analysis, the processor is further to;

mark the at least one other block as having been affected by the changed line of code, and

generating the information based on the marking of the at least one block or the marking of the at least one other block.

13. The server device of claim 12, where the processor is further to:

perform another inter-procedural analysis on another one or more functions associated with the at least one other block based on the marking of the at least one other block and a logical interconnection between the at least one other block and the other one or more functions.

14. The server device of claim 11, where, when generating the one or more blocks, the processor is to:

map different portions of the one or more of the plurality of lines of code to the one or more blocks, where one of the different portions includes the changed line of code that is mapped to the epicenter block.

15. The server device of claim 11, where, when generating the one or more blocks, the processor is to:

associate one or more variables, associated with the epicenter block, with an impacted set of variables when the one or more variables are defined within the epicenter block,

associate a first variable, associated with a particular block of the one or more blocks, with a used set of variables, when the first variable is used, but not defined, within the particular block, and

associate a second variable, associated with the particular block, with a defined set of variables when the second variable is defined within the particular block.

16. The server device of claim 15, where, when performing the intra-procedural analysis, the processor is to:

identify the particular block as an impacted block when at least one of the used set of variables is included in the impacted set of variables, and

determine that the particular block is not an impacted block when none of the used set of variables are included in the impacted set of variables.

17. The server device of claim 15, where, when performing the intra-procedural analysis, the processor is to:

identify that a variable, associated with the particular block, is included in the impacted set of variables, and

determine that the particular block is not an impacted block when the variable is included in the defined set of variables associated with the particular block.

18. The server device of claim 11, where the processor is further to:

create one or more analysis threads, corresponding to one or more parent functions, that are associated with a first distance,

execute the one or more analysis threads associated with the first distance by performing one or more intra-procedural analyses on the one or more parent functions, where the one or more intra-procedural analyses are performed concurrently or simultaneously,

create one or more analysis threads, corresponding to one or more child functions, that are associated with a second distance, where the one or more child functions are associated with blocks, within the one or more parent functions, that are affected by the changed line of code associated with the software application, and

execute the one or more analysis threads, associated with the second distance by performing one or more inter-procedural analyses on the one or more child functions, where the one or more inter-procedural analyses are performed concurrently or simultaneously.

19. A non-transitory computer-readable medium comprising:

receiving a request to perform an impact analysis on a changed line of code, of a plurality of lines of code, associated with a software application;

associating, in response to the request, a parent function with one or more lines of code, of the plurality of lines of code, that include the changed line of code;

generating a control flow graph associated with the parent function, where the control flow graph includes one or more blocks that correspond to the one or more lines of code and an epicenter block that corresponds to the changed line of code,

where the epicenter block includes one or more variables that are defined within the epicenter block;

identifying one of the one or more blocks, as an impacted block, when the one of the one or more block uses any of the one or more variables;

generating a call graph that identifies one or more child functions associated with the impacted block based on statements, within the impacted block, that logically interconnect the one or more child functions with the impacted block;

identifying at least one other impacted block, of the blocks associated with the one or more child functions, based on a determination that the at least one other impacted block uses any of the one or more variables; and

presenting, for display, a notification that software testing is to be conducted on lines of code associated with the impacted block and the at least one other impacted block.

20. The non-transitory computer-readable medium of claim 19, where the parent function performs an act or operation associated with the software application;

and

where associating the parent function with the one or more lines of code includes;

identifying a first line of code, that occurs before the changed line of code, that corresponds to a beginning of the parent function;

identifying a second line of code, that occurs after the changed line of code, that corresponds to an end of the parent function; and

associating the parent function with the lines of code from the first line of code to the second line of code.

21. The non-transitory computer-readable medium of claim 19, where generating the control flow graph includes:

determining a data flow or a logic flow among the one or more blocks and between the epicenter block and the one or more blocks; and

creating logical interconnections among the one or more blocks and between the epicenter block and the one or more blocks based on the data flow or the logic flow.

22. The non-transitory computer-readable medium of claim 19, where generating the call graph further includes:

identifying the statements within the impacted block as one or more lines of code that call the one or more child functions or that return data to the one or more child functions.

23. The non-transitory computer-readable medium of claim 19, further comprising:

identifying a grandchild function based on a statement detected within the at least one other impacted block that logically interconnects the grandchild function with the at least one other impacted block;

identifying at least one further block associated with the grandchild function, based on a determination that the further block uses any of the one or more variables; and

presenting, for display, another notification that software testing is to be conducted on lines of code associated with the at least one further block.