Distributed static analysis of computer software applications

• US 8,984,493 B2
• Filed: 04/23/2013
• Issued: 03/17/2015
• Est. Priority Date: 01/25/2011
• Status: Active Grant

• 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/868,189
• Publication Number:
  US 20130239097A1
• Time in Patent Office: 693 Days
• Field of Search: None
• US Class Current: 717/131
• 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 analyzes via a computer-controlled output device.

Claims

1. A computer-implemented method for distributed static analysis of computer software applications, the method comprising:

statically analyzing instructions of a computer software application;

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

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

assigning, 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;

resuming 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;

presenting 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 method of claim 1, wherein the assigning the primary agent to statically analyze the computer software application from the entry point comprises:

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

statically analyzing 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,

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

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

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

3. The method of claim 1, wherein the assigning the primary agent to statically analyze the computer software application from the entry point comprises:

assigning 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.

4. The method of claim 1, wherein the assigning the primary agent to statically analyze the computer software application from the entry point comprises:

assigning 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.

5. The method of claim 1, wherein the assigning the secondary agent to statically analyze the call site encountered by the primary agent and produce the static analysis summary of the call site comprises:

assigning 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.

6. The method of claim 1, wherein the assigning the secondary agent to statically analyze the call site encountered by the primary agent and produce the static analysis summary of the call site comprises:

assigning 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.

7. The method of claim 1, wherein the assigning the primary agent to statically analyze the computer software application from the entry point comprises assigning 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 assigning the secondary agent to statically analyze the call site encountered by the primary agent and produce the static analysis summary of the call site comprises assigning 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.

8. The method of claim 1, wherein assigning the primary agent to statically analyze the computer software application comprises:

specifying 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

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