Systems and methods for information flow analysis

• US 9,043,774 B2
• Filed: 02/12/2009
• Issued: 05/26/2015
• Est. Priority Date: 02/12/2008
• Status: Active Grant

• Current Assignee: David D. Duchesneau, William G. Bently
• Original Assignee: David D. Duchesneau
• Inventors: Bently, William G., Duchesneau, David D.
• Primary Examiner(s): Chen, Xi D
• Application Number:
  US12/370,554
• Publication Number:
  US 20090217248A1
• Time in Patent Office: 2,294 Days
• Field of Search: None
• US Class Current: 717/155
• CPC Class Codes: G06F 8/30 Creation or generation of source code
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis

Abstract

Computer-implemented methods for analyzing computer programs written in semi-structured languages are disclosed. The method is based on unification of the two classic forms of program flow analysis, control flow and data flow analysis. As such, it is capable of substantially increased precision, which increases the effectiveness of applications such as automated parallelization and software testing. Certain implementations of the method are based on a process of converting source code to a decision graph and transforming that into one or more alpha graphs which support various applications in software development. The method is designed for a wide variety of digital processing platforms, including highly parallel machines. The method may also be adapted to the analysis of (semi-structured) flows in other contexts including water systems and electrical grids.

Claims

1. A computer implemented method for analyzing computer programs based on a mathematical model of within the subroutine-level code of such programs, said method comprising:

a reduction process which transforms a representation of signal flows from an unreduced form to a reduced form, thereby removing unnecessary sequencing constraints;

said reduction process further comprising obtaining the unreduced form from said code, said unreduced form comprising a representation of control flow structure with associated data elements in said code, said data elements further comprising;

definition, use, predicate (vector of uses), intra-segment du-pair (definition-use pair), and intra-segment ud-pair (use-definition pair), performing a reduction process having the effect of removing unnecessary sequencing constraints (unnecessary flows), yielding said reduced form, said reduced form further comprising a representation which is convertible back to a parallelized form of the original subroutine-level code;

said unreduced form comprises a system of unreduced signal flow equations which, in conjunction with a signal flow algebra, describe the transmission of signals or state within said code, said signals further comprising control state and data state, with said signal flow algebra further comprising four operators for sequence, control, convergence and alternation and having algebraic rules that are non-commutative and non-associative; and

wherein said reduction process comprises the repeated application of the rules of said signal flow algebra, thereby transforming said unreduced signal flow equations into a reduced form comprising a system of reduced signal flow equations, said process having the effect of removing unnecessary sequencing constraints.

2. The computer implemented method of claim 1, wherein the unreduced form comprises a decision graph, which is an ordered tree representation of a system of unreduced signal flow equations which, in conjunction with said signal flow algebra, describe the transmission of signals or state within said code;

and wherein said reduction process comprises a fully automatable system of non-iterative graph transformations which natively support conventional structured constructs in said code, as well as the semi-structured constructs break, return, continue, and exceptions, and wherein said reduction process yields a reduced form further comprising one or more information flowgraphs at the subroutine level, each of which is a direct representation of the system of reduced signal flow equations as a graph having the same mathematical basis as the signal flow equations.

3. The computer implemented method of claim 2, wherein said information flowgraphs, which are direct representations of the systems of reduced signal flow equations as graphs having the same mathematical basis as the signal flow equations, and which are also inherently parallel representations of program flow, are utilized in a postprocessing step, said step converting said information flowgraphs into a desired output form further comprising independent or quasi-independent subsets of the original code of said program, such that said independent subsets may be utilized independently of each other as parallel codes or threads to implement automatic parallelization, or for use in efficient and parallelizable automated software testing approximating all-paths testing.