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 any number of problems. Analyzing a C program’s memory management is one such problem. This project would seek to use C-Atlas to better analyze C memory management. In memory leak (memory management) analysis, the user must show that for every path forward from an variable’s allocation, there exists at least one deallocation site for that variable. This task is trivial, unless the variable’s allocation and deallocation(s) are separated by a vast field of possible control flow. C-Atlas offers a flexible interface for data flow graph generation as a solution to this problem. Through this interface, one may then produce connected data flow graphs, allowing a single variable’s path to be traced through multiple functions. This visual aide can greatly increase the time efficiency of performing memory leak analysis. The idea of this project was to write a script to produce meaningful data flow graphs for analyzing memory leaks. This script will seek to help confirm (or dispute) if some allocation site is dominated by some deallocation-site along every feasible data flow path. Finally, the script will be tested on a release of the XINU kernel. RESEARCH The research portion of this assignment consisted of reading two papers, a large set of Atlas documentation, and understanding an existing solution to this problem. 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, we can use a summary edge to describe that going forward. Looking at its source code, it makes a very similar attempt at proceeding through the graph as another implementation I researched, Ahmed Tamrawi’s approach. This algorithm seems to pulse through the graph, finding new work-list elements. B. Weiser Paper The paper by Weiser reiterated an idea we learned early on in this class: In static data flow analysis, given a directed graph G, we can be certain that a function f is always reached if g is an acyclic flow graph to node f. A “flow graph to f ” means that there exists no node v in the vertices V of G, such that there exists some path out of x that does not pass through f. Ergo, starting at the root of G, to reach the bottom tier of the graph you must eventually pass through node f. This is known as graph-domination. With this simplification, assuming G represents the forward data flow graph from a memory allocation site, we can determine that if f is a memory deallocation site in G, there can be no memory leak for the allocated memory being tracked in G. This fact forms the basis of connecting allocation to deallocation sites; If there exists some path (including considerations for invisible data flow) around a memory deallocation site in a allocated variable data flow graph, there must be a memory leak. C. Prior Implementation Ahmed Tamrawi’s implementation formed the basis for my implementation concept. His method relies on Ensoft’s new XCSG schema, as well as Atlas’ new C implementation. In general the algorithm is simple: For the universe, find all Memory Leak Analysis Algorithm 1:
[0] [1] [2] [3] [4] [5] ..] [6] [7] [8] E