877 words - 4 pages

Abstract—This paper addresses the topic of methods for producing inter procedural static data flow graphs. The method used in this paper is a sort of progressive mining approach: A start location for the data flow edges is outlined, and through multiple iterations, the forward data flow step operation is taken on the universe, until no new paths have been found.

I.

INTRODUCTION

New tools often provide novel approaches to longstanding problems. In the next update of C-Atlas, Ensoft intends to update the capabilities of C-Atlas. These improvements are intended to provide a customizable approach to evaluating a program’s design, structure, and security. Such an update seeks to address ...view middle of the document...

The papers were “Precise Interprocedural Dataflow Analysis via Graph Reachability” by Thomas Reps, Susan Horwitz, and Mooly Sagiv of the University of Wisconsin, and “Program Slicing” by Mark Weiser. The existing solution was a Java method for the Atlas Interpreter designed by Ahmed Tamrawi of Iowa State University. Each of these offered its own specific insight into designing an effective solution to the inter procedural data flow graph creation problem. A. Graph Reachability Paper The paper by Thomas, Horowitz, Sagiv discusses a general method for producing inter procedural data flow graphs solvable in polynomial time. The generalization takes what it calls the IFDS problems (interprocedural, finite, distributive, subset problems) and maps it to “realizable-path” graph-reachability problems. The graph reachability problem is a term I had never heard characterized as such before, however, it seems like a fairly intuitive problem. Given a data flow graph universe, along all the realizable paths in a subset, what is the reachability of the subgraph? II.

This generalization relies on a method by the name of the “tabulation algorithm.” The tabulation algorithm is a dynamicprogramming work-list algorithm. This algorithm (being very complex and requiring a nutshell explanation) creates a tabulation of path and summary edges. A path edge is any edge along the realizable path. A summary edge is like a path edge, how ever it represents information on call site returns. This is important, because it describes a sensitive approach. While in static analysis, functions might have edges that loop back to some parent function, in this approach,...

Draw inspiration from millions of example essays and papers