Distributed static analysis of computer software applications

• US 8,856,764 B2
• Filed: 01/25/2011
• Issued: 10/07/2014
• Est. Priority Date: 01/25/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Pistoia, Marco, Tripp, Omer, Weisman, Omri
• Primary Examiner(s): Chen, Xi D
• Application Number:
  US13/012,804
• Publication Number:
  US 20120192161A1
• Time in Patent Office: 1,351 Days
• Field of Search: None
• US Class Current: 717/154
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589
• CPC Class Codes: G06F 8/75 Structural analysis for program understanding

Abstract

A method for distributed static analysis of computer software applications, includes: statically analyzing instructions of a computer software application; identifying at least one entry point in the computer software application; assigning a primary agent to statically analyze the computer software application from the entry point; assigning a secondary agent to statically analyze a call site encountered by the primary agent and produce a static analysis summary of the call site; and presenting results of any of the static analyses via a computer-controlled output device.

Claims

1. A computer program product for distributed static analysis of computer software applications, the computer program product comprising:

a computer-readable storage medium not including signals per se; and

computer-readable program code embodied in the computer-readable storage medium, wherein the computer-readable program code is configured to;

statically analyze instructions of a computer software application,

identify at least one entry point in the computer software application,

assign, by a primary agent manager, a primary agent to statically analyze the computer software application from the entry point,

assign, by a secondary agent manager, a secondary agent to statically analyze a call site encountered by the primary agent and produce a static analysis summary of the call site, wherein the call site comprises an external reference, and wherein the secondary agent is tasked with analyzing the external reference to produce the static analysis summary of the call site, wherein analysis of the external reference by the secondary agent is triggered by the static analysis performed by the primary agent when

i) the primary agent encounters the call site requiring static analysis,

ii) the primary agent issues a request to a summaries data store for the static analysis summary of the call site and the static analysis summary of the call site does not exist in the summaries data store, and

iii) the primary agent places a request for the static analysis summary of the call site on a queue of requests for static analysis summaries,

resume the primary agent'"'"'s static analysis of the computer software application using the static analysis summary of the call site after the static analysis summary of the call site is produced,

present results of any of the static analyses via a computer-controlled output device, and wherein the assigning the primary agent and the assigning the secondary agent produce static analysis that is scalable and precise for the computer software application.

2. The computer program product of claim 1, wherein the computer-readable program code configured to assign the primary agent to statically analyze the computer software application form the entry point is further configured to:

check whether the static analysis summary of the call site exists in the summaries data store;

statically analyze the computer software application from the entry point using the static analysis summary of the call site if the static analysis summary of the call site exists; and

if the static analysis summary of the call site does not exist,

suspend the primary agent'"'"'s static analysis of the computer software application,

issue the request for the static analysis summary of the call site, and

store the static analysis summary of the call site in the summaries data store.

3. The computer program product of claim 1, wherein the primary agent is a computer process that is executed by either a single computer processor or a single core of a multi-core computer processor.

4. The computer program product of claim 1, wherein the computer-readable program code configured to assign the primary agent to statically analyze the computer software application from the entry point is further configured to:

assign a plurality of primary agents to statically analyze the computer software application from a plurality of entry points of the computer software application,

wherein each of the plurality of primary agents statically analyzes a different one of the plurality of entry points, and

wherein the plurality of primary agents operate concurrently.

5. The computer program product of claim 1, wherein the computer-readable program code configured to assign the primary agent to statically analyze the computer software application from the entry point is further configured to:

assign the primary agent from a pool and returning the primary agent to the pool once the primary agent completes the primary agent'"'"'s static analysis of the primary agent'"'"'s assigned entry point.

6. The computer program product of claim 1, wherein the secondary agent is a computer process that is executed by either a single computer processor or a single core of a multi-core computer processor.

7. The computer program product of claim 1, wherein the computer-readable program code configured to assign the secondary agent to statically analyze the call site encountered by the primary agent and produce the static analysis summary of the call site is further configured to:

assign a plurality of secondary agents to statically analyze a plurality of call sites and produce a corresponding plurality of static analysis summaries,

wherein each of the plurality of secondary agents statically analyzes a different one of the plurality of call sites, and

wherein the plurality of secondary agents operate concurrently.

8. The computer program product of claim 1, wherein the computer-readable program code configured to assign the secondary agent to statically analyze the call site encountered by the primary agent and produce the static analysis summary of the call site is further configured to:

assign the secondary agent from a pool and returning the secondary agent to the pool once the secondary agent completes the secondary agent'"'"'s static analysis of the secondary agent'"'"'s assigned call site.

9. The computer program product of claim 1, wherein the computer-readable program code configured to assign the primary agent to statically analyze the computer software application from the entry point is further configured to assign a plurality of primary agents to statically analyze the computer software application from a plurality of entry points of the computer software application,

wherein the computer-readable program code configured to assign the secondary agent to statically analyze the call site encountered by the primary agent and produce the static analysis summary of the call site is further configured to assign a plurality of secondary agents to statically analyze a plurality of call sites and produce a corresponding plurality of static analysis summaries,

wherein each of the plurality of primary agents statically analyzes a different one of the plurality of entry points,

wherein each of the plurality of secondary agents statically analyzes a different one of the plurality of call sites, and

wherein the plurality of primary agents and secondary agents operate concurrently.

10. The computer program product of claim 2 wherein when the computer-readable program code is configured to assign a primary agent to statically analyze the computer software application, the computer-readable program code is further configured to:

specify an abstraction for each argument required by the call site, wherein the abstraction is specified by the primary agent when the primary agent;

i) checks whether the static analysis summary of the call site exists, and

ii) issues the request for the static analysis summary of the call site, and

produce the static analysis summary of the call site with respect to the each specified abstraction.

11. A system for distributed static analysis of computer software applications, the system comprising:

one or more processors; and

a computer-readable storage medium comprising computer-readable program code embodied in the computer-readable storage medium, wherein the computer-readable program code is configured to;

statically analyze instructions of a computer software application;

identify at least one entry point in the computer software application;

assign, by a primary agent manager, a primary agent to statically analyze the computer software application from the entry point;

assign, by a secondary agent manager, a secondary agent to statically analyze a call site encountered by the primary agent and produce a static analysis summary of the call site, wherein the call site comprises an external reference, and wherein the secondary agent is tasked with analyzing the external reference to produce the static analysis summary of the call site, wherein analysis of the external reference by the secondary agent is triggered by the static analysis performed by the primary agent when

i) the primary agent encounters the call site requiring static analysis,

ii) the primary agent issues a request to a summaries data store for the static analysis summary of the call site and the static analysis summary of the call site does not exist in the summaries data store, and

iii) the primary agent places a request for the static analysis summary of the call site on a queue of requests for static analysis summaries,

resume the primary agent'"'"'s static analysis of the computer software application using the static analysis summary of the call site after the static analysis summary of the call site is produced;

present results of any of the static analyses via a computer-controlled output device, and

wherein the assigning the primary agent and the assigning the secondary agent produce static analysis that is scalable and precise for the computer software application.

12. The system of claim 11, wherein the computer-readable program code configured to assign a primary agent to statically analyze the computer software application from the entry point is further configured to:

check whether the static analysis summary exists of the call site in the summaries data store;

statically analyze the computer software application from the entry point using the static analysis summary of the call site if the static analysis summary of the call site exists; and

if the static analysis summary of the call site does not exist,

suspend the primary agent'"'"'s static analysis of the computer software application,

issue the request for a static analysis summary of the call site, and

store the static analysis summaries of the call site in the summaries data store.

13. The system of claim 11, wherein the entry point is an interaction interface exposed by the computer software application to a source of interaction that is external to the computer software application.

14. The system of claim 11, wherein the computer-readable program code configured to assign the primary agent to statically analyze the computer software application from the entry point is further configured to:

assign a plurality of primary agents to statically analyze the computer software application from a plurality of entry points of the computer software application,

wherein each of the plurality of primary agents statically analyzes a different one of the plurality of entry points,

wherein the plurality of primary agents operate concurrently, and

wherein each of the primary agents are executed by a different computer processor or computer processor core.

15. The system of claim 11, wherein the call site is a reference to any of a method, a procedure, and a function that is external to a method, procedure, or function where the call site is found within the computer software application.

16. The system of claim 11, wherein the computer-readable program code configured to assign the secondary agent to statically analyze the call site encountered by the primary agent and produce the static analysis summary of the call site assign is further configured to:

assign a plurality of secondary agents to statically analyze a plurality of call sites and produce a corresponding plurality of static analysis summaries,

wherein each of the plurality of secondary agents statically analyzes a different one of the plurality of call sites,

wherein the plurality of secondary agents operate concurrently, and

wherein each of the secondary agents are executed by a different computer processor or computer processor core.

17. The system of claim 11, wherein the computer-readable program code configured to assign the primary agent to statically analyze the computer software application from the entry point is further configured to assign a plurality of primary agents to statically analyze the computer software application from a plurality of entry points of the computer software application,

wherein the computer-readable program code configured to assign the secondary agent to statically analyze the call site encountered by the primary agent and produce the static analysis summary of the call site assign is further configured to assign a plurality of secondary agents to statically analyze a plurality of call sites and produce a corresponding plurality of static analysis summaries,

wherein each of the plurality of primary agents statically analyzes a different one of the plurality of entry points,

wherein each of the plurality of secondary agents statically analyzes a different one of the plurality of call sites,

wherein the plurality of primary agents and secondary agents operate concurrently, and

wherein each of the primary agents and secondary agents are executed by a different computer processor or computer processor core.