Systems and methods for information 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.

1 . A digital processor-implemented method for analyzing a directed-flow network that is representable as directed or semi-structured flows, the method comprising:
 transforming an application-specific representation of the directed-flow network into decision graphs which represent the control flow structure of said flow network, with data flow elements attached to the graphs;   transforming said decision graphs into one or more information flowgraphs which represent the directed flows of said flow network in a unified manner, and which identify the independent and quasi-independent flows therein; and   transforming said information flowgraphs into application-specific artifacts for identifying independent and quasi-independent flows occurring in said flow network.   
     
     
         2 . A digital processor-implemented method for analyzing computer programs represented in semi-structured languages, the method comprising:
 transforming source code or object code of the computer program represented in a semi-structured language into decision graphs which represent the control flow structure of said program, with data flow elements attached to the graphs;   transforming said decision graphs into one or more information flowgraphs which represent control flow and data flow in a unified manner, and which identify the independent and quasi-independent flows therein; and   converting said information flowgraphs into the source code or object code in the original programming language for use in automatic parallelization or efficient automated software testing approximating all-paths testing.   
     
     
         3 . A digital processor-controlled apparatus comprising at least one digital processor and at least one machine-readable storage medium, the digital processor-controlled apparatus being capable of performing the method of  claim 1  or  claim 2 . 
     
     
         4 . A computer-readable storage medium having instructions encoded thereon which, when executed by a computer, cause the computer to perform the method of  claim 1  or  claims 2 .