The Experts below are selected from a list of 285 Experts worldwide ranked by ideXlab platform
Mary Lou Soffa - One of the best experts on this subject based on the ideXlab platform.
-
SAS - Tutorial: Techniques to Improve the Scalability and Precision of Data Flow Analysis
Static Analysis, 1999Co-Authors: Mary Lou SoffaAbstract:Since the introduction of data flow Analysis more than 20 years ago, the applications of data flow Analysis have expanded considerably with the recognition of its practical benefits. The current use of data flow Analysis goes well beyond its initial application of register allocation and machine independent optimizations. Compilers today rely heavily on data flow analyses for sophisticated optimizations and to guide the exploitation of architectural features, such as the numbers of processors and their functional units and the memory hierarchy. Besides compilers, data flow Analysis is also used in software engineering. Applications include program verification, debugging (especially of optimized and parallelized code), program test case generation and coverage Analysis, regression testing, program integration and program understanding.
-
LCR - Data Flow Analysis Driven Dynamic Data Partitioning
Languages Compilers and Run-Time Systems for Scalable Computers, 1998Co-Authors: Jodi Lynn Tims, Rajiv Gupta, Mary Lou SoffaAbstract:The use of distributed memory architectures as an effective approach to parallel computing brings with it a more complex program development process. Finding a partitioning of program code and data that supports sufficient parallelism without incurring prohibitive communication costs is a challenging and critical step in the development of programs for distributed memory systems. Automatic data distribution techniques have the goal of placing the responsibility of determining a suitable data partitioning into the domain of the compiler. Static program Analysis techniques that expose data interrelationships and derive performance estimates are central to the development of automatic data distribution heuristics. In this paper we present a data partitioning heuristic that makes use of array data flow Analysis information in the modeling of data interrelationships and the estimation of costs associated with resolving interrelationships via communication. The global view provided by data flow Analysis permits consideration of potential communication optimizations before data partitioning decisions are made. Our heuristic uses tiling techniques to determine data partitionings. The resulting data distributions, while still regular, are not limited to the standard BLOCK, CYCLIC and BLOCK-CYCLIC varieties. Preliminary results indicate an overall reduction in communication cost with our technique.
-
CC - Reducing the Cost of Data Flow Analysis By Congruence Partitioning
Lecture Notes in Computer Science, 1994Co-Authors: Evelyn Duesterwald, Rajiv Gupta, Mary Lou SoffaAbstract:Data flow Analysis expresses the solution of an information gathering problem as the fixed point of a system of monotone equations. This paper presents a technique to improve the performance of data flow Analysis by systematically reducing the size of the equation system in any monotone data flow problem. Reductions result from partitioning the equations in the system according to congruence relations. We present a fast O(n log n) partitioning algorithm, where n is the size of the program, that exploits known algebraic properties in equation systems. From the resulting partition a reduced equation system is constructed that is minimized with respect to the computed congruence relation while still providing the data flow solution at all program points.
-
IPPS - The combining DAG: a technique for parallel data flow Analysis
Proceedings Sixth International Parallel Processing Symposium, 1Co-Authors: R. Kramer, Rajiv Gupta, Mary Lou SoffaAbstract:The availability of multiprocessor systems has recently generated an increased interest in the design and implementation of parallel compilers. The authors present a parallel algorithm for performing data flow Analysis which is an important component of any compiler. Data flow information is used in various phases of compilation including code generation, code scheduling, traditional optimizing transformations and parallelizing transformations. A single program compilation may involve the computation of the solution to several data flow problems and possibly solutions to the same problem multiple times at different points in the language translation process. Thus, for large programs the data flow Analysis performed during compilation can be time-consuming. Data flow Analysis is also used in other program tools such as editors, testers, and debuggers. >
Uday P. Khedker - One of the best experts on this subject based on the ideXlab platform.
-
Complexity of Data Flow Analysis for Non-Separable Frameworks
arXiv: Programming Languages, 2006Co-Authors: Bageshri Karkare, Uday P. KhedkerAbstract:The complexity of round robin method of intraprocedural data flow Analysis is measured in number of iterations over the control flow graph. Existing complexity bounds realistically explain the complexity of only Bit-vector frameworks which are separable. In this paper we define the complexity bounds for non-separable frameworks by quantifying the interdependences among the data flow information of program entities using an Entity Dependence Graph.
-
Bidirectional data flow Analysis for type inferencing
Computer Languages Systems & Structures, 2003Co-Authors: Uday P. Khedker, Dhananjay M. Dhamdhere, Alan MycroftAbstract:Tennenbaum's data flow Analysis based formulation of type inferencing is termed bidirectional in the ''Dragon Book''; however, it fails to qualify as a formal data flow framework and is not amenable to complexity Analysis. Further, the types discovered are imprecise. Here, we define a formal data flow framework (based on bidirectional data flow Analysis) which discovers more precise type information and is amenable to complexity Analysis. We compare data flow analyses with the more general constraint-based analyses and observe that data flow analyses represent program analyses without unbounded auxiliary store. We show that if unlimited auxiliary store is allowed then no data flow Analysis would need more than two passes; if auxiliary store is disallowed then type inferencing requires bidirectional data flow Analysis.
-
Bidirectional data flow Analysis for type inferencing
Computer Languages Systems & Structures, 2003Co-Authors: Uday P. Khedker, Dhananjay M. Dhamdhere, Alan MycroftAbstract:Tennenbaum's data flow Analysis based formulation of type inferencing is termed bidirectional in the “Dragon Book”; however, it fails to qualify as a formal data flow framework and is not amenable to complexity Analysis. Further, the types discovered are imprecise. Here, we define a formal data flow framework (based on bidirectional data flow Analysis) which discovers more precise type information and is amenable to complexity Analysis. We compare data flow analyses with the more general constraint-based analyses and observe that data flow analyses represent program analyses without unbounded auxiliary store. We show that if unlimited auxiliary store is allowed then no data flow Analysis would need more than two passes; if auxiliary store is disallowed then type inferencing requires bidirectional data flow Analysis.© Elsevie
-
Bidirectional data flow Analysis: myths and reality
ACM SIGPLAN Notices, 1999Co-Authors: Uday P. Khedker, Dhananjay M. DhamdhereAbstract:Research in bidirectional data flow Analysis seems to have come to a halt due to an impression that the case for bidirectional data flow Analysis has been considerably weakened by a plethora of investigations based on decomposability of known bidirectional placement algorithms into a sequence of purely unidirectional components. This paper shows that the approach of decomposability is not general enough in that it derives its power from the simplifying graph transformation of edge-splitting and the favourable nature of flows in partial redundancy elimination (PRE). This follows from the fact that in the absence of edge-splitting, PRE cannot be performed using a sequence of cascaded unidirectional flows. Further, edge-splitting inherently converts data flows involved in PRE into unidirectional flows. In our opinion, this obviates the need of an alternative formulation. We also show that edge-splitting cannot convert data flows involved in "truly" bidirectional data flow problems into unidirectional flows. Thus not every bidirectional data flow problem can be converted into unidirectional flows. Besides, we argue that the premise that bidirectional Analysis is more complex than unidirectional Analysis, is invalid. We also mention some issues in bidirectional data flow Analysis which need to be investigated
-
A generalized theory of bit vector data flow Analysis
ACM Transactions on Programming Languages and Systems, 1994Co-Authors: Uday P. Khedker, Dhananjay M. DhamdhereAbstract:The classical theory of data flow Analysis, which has its roots in unidirectional flows, is inadequate to characterize bidirectional data flow problems. We present a generalized theory of bit vector data flow Analysis which explains the known results in unidirectional and bidirectional data flows and provides a deeper insight into the process of data flow Analysis. Based on the theory, we develop a worklist-based generic algorithm which is uniformly applicable to unidirectional and bidirectional data flow problems. It is simple, versatile, and easy to adapt for a specific problem. We show that the theory and the algorithm are applicable to all bounded monotone data flow problems which possess the property of the separability of solution. The theory yields valuable information about the complexity of data flow Analysis. We show that the complexity of worklist-based iterative Analysis is the same for unidirectional and bidirectional problems. We also define a measure of the complexity of round-robin iterative Analysis. This measure, called width , is uniformly applicable to unidirectional and bidirectional problems and provides a tighter bound for unidirectional problems than the traditional measure of depth . Other applications include explanation of isolated results in efficient solution techniques and motivation of new techniques for bidirectional flows. In particular, we discuss edge splitting and edge placement and develop a feasibility criterion for decomposition of a bidirectional flow into a sequence of unidirectional flows.
Seyed M. Buhari - One of the best experts on this subject based on the ideXlab platform.
-
DroidRista: a highly precise static data flow Analysis framework for android applications
International Journal of Information Security, 2019Co-Authors: Areej Alzaidi, Suhair Alshehri, Seyed M. BuhariAbstract:The Android operating system dominates the smartphone market. Thus, to service the market, the number of Android applications has risen dramatically. These applications are processing a great amount of sensitive data, which could result in various concerns including data leakage and privacy violations. For example, applications may misuse the sensitive data stored on Android devices and violate the privacy of the user. Therefore, it is essential to maintain user privacy and protect sensitive data from leakage. Static data flow Analysis approaches are used for analyzing Android applications to uncover security and privacy issues. However, these approaches frequently generate false alarms, given the different challenges created by Android applications, such as inter-component communication (ICC), reflection, and implicit flow. This work presents the DroidRista approach for conducting static data flow Analysis on Android applications to detect sensitive data leakage. DroidRista analyzes ICC, reflection, and implicit flow in Android applications. To evaluate the performance of DroidRista, it was tested on three data sets. The results demonstrate improved performance in terms of detecting data leakage compared to existing static data flow Analysis approaches.
Dhananjay M. Dhamdhere - One of the best experts on this subject based on the ideXlab platform.
-
Bidirectional data flow Analysis for type inferencing
Computer Languages Systems & Structures, 2003Co-Authors: Uday P. Khedker, Dhananjay M. Dhamdhere, Alan MycroftAbstract:Tennenbaum's data flow Analysis based formulation of type inferencing is termed bidirectional in the ''Dragon Book''; however, it fails to qualify as a formal data flow framework and is not amenable to complexity Analysis. Further, the types discovered are imprecise. Here, we define a formal data flow framework (based on bidirectional data flow Analysis) which discovers more precise type information and is amenable to complexity Analysis. We compare data flow analyses with the more general constraint-based analyses and observe that data flow analyses represent program analyses without unbounded auxiliary store. We show that if unlimited auxiliary store is allowed then no data flow Analysis would need more than two passes; if auxiliary store is disallowed then type inferencing requires bidirectional data flow Analysis.
-
Bidirectional data flow Analysis for type inferencing
Computer Languages Systems & Structures, 2003Co-Authors: Uday P. Khedker, Dhananjay M. Dhamdhere, Alan MycroftAbstract:Tennenbaum's data flow Analysis based formulation of type inferencing is termed bidirectional in the “Dragon Book”; however, it fails to qualify as a formal data flow framework and is not amenable to complexity Analysis. Further, the types discovered are imprecise. Here, we define a formal data flow framework (based on bidirectional data flow Analysis) which discovers more precise type information and is amenable to complexity Analysis. We compare data flow analyses with the more general constraint-based analyses and observe that data flow analyses represent program analyses without unbounded auxiliary store. We show that if unlimited auxiliary store is allowed then no data flow Analysis would need more than two passes; if auxiliary store is disallowed then type inferencing requires bidirectional data flow Analysis.© Elsevie
-
Bidirectional data flow Analysis: myths and reality
ACM SIGPLAN Notices, 1999Co-Authors: Uday P. Khedker, Dhananjay M. DhamdhereAbstract:Research in bidirectional data flow Analysis seems to have come to a halt due to an impression that the case for bidirectional data flow Analysis has been considerably weakened by a plethora of investigations based on decomposability of known bidirectional placement algorithms into a sequence of purely unidirectional components. This paper shows that the approach of decomposability is not general enough in that it derives its power from the simplifying graph transformation of edge-splitting and the favourable nature of flows in partial redundancy elimination (PRE). This follows from the fact that in the absence of edge-splitting, PRE cannot be performed using a sequence of cascaded unidirectional flows. Further, edge-splitting inherently converts data flows involved in PRE into unidirectional flows. In our opinion, this obviates the need of an alternative formulation. We also show that edge-splitting cannot convert data flows involved in "truly" bidirectional data flow problems into unidirectional flows. Thus not every bidirectional data flow problem can be converted into unidirectional flows. Besides, we argue that the premise that bidirectional Analysis is more complex than unidirectional Analysis, is invalid. We also mention some issues in bidirectional data flow Analysis which need to be investigated
-
A generalized theory of bit vector data flow Analysis
ACM Transactions on Programming Languages and Systems, 1994Co-Authors: Uday P. Khedker, Dhananjay M. DhamdhereAbstract:The classical theory of data flow Analysis, which has its roots in unidirectional flows, is inadequate to characterize bidirectional data flow problems. We present a generalized theory of bit vector data flow Analysis which explains the known results in unidirectional and bidirectional data flows and provides a deeper insight into the process of data flow Analysis. Based on the theory, we develop a worklist-based generic algorithm which is uniformly applicable to unidirectional and bidirectional data flow problems. It is simple, versatile, and easy to adapt for a specific problem. We show that the theory and the algorithm are applicable to all bounded monotone data flow problems which possess the property of the separability of solution. The theory yields valuable information about the complexity of data flow Analysis. We show that the complexity of worklist-based iterative Analysis is the same for unidirectional and bidirectional problems. We also define a measure of the complexity of round-robin iterative Analysis. This measure, called width , is uniformly applicable to unidirectional and bidirectional problems and provides a tighter bound for unidirectional problems than the traditional measure of depth . Other applications include explanation of isolated results in efficient solution techniques and motivation of new techniques for bidirectional flows. In particular, we discuss edge splitting and edge placement and develop a feasibility criterion for decomposition of a bidirectional flow into a sequence of unidirectional flows.
-
Complexity of bi-directional data flow Analysis
Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '93, 1993Co-Authors: Dhananjay M. Dhamdhere, Uday P. KhedkerAbstract:The concept of an information flow path arising from the generalized theory of data flow Analysis [21] is used to analyze the complexity of data flow Analysis. The width (w) of a program flow graph with respect to a class of data flow problems is introduced as a measure of the complexity of round-robin iterative Analysis. This provides the first known complexity result for round robin iterative Analysis of bidirectional data flows commonly used in algorithms based on the suppression of partial redundancies [6, 7, 8, 9, 17, 18, 25]. We also show that width provides a better bound on the complexity of unidirectional data flows than the classical notion of depth . The paper presents ways to reduce the width, and thereby the complexity of flow Analysis, for several interesting problems. Complexity Analysis using the notion of width is also shown to motivate efficient solution methods for various bidirectional problems, viz . The alternating iterations method, and an interval Analysis based elimination method for the partial redundancy elimination problems. The paper also presents a condition for the decomposability of a bidirectional problem into a sequence of unidirectional problems.
Bernhard Steffen - One of the best experts on this subject based on the ideXlab platform.
-
CC - Data-Flow Analysis as model checking within the jABC
Lecture Notes in Computer Science, 2006Co-Authors: Anna-lena Lamprecht, Tiziana Margaria, Bernhard SteffenAbstract:This paper describes how the jABC, a generic framework for library-based program development, and two of its plugins - the Model Checker and a flow graph converter – form a framework for intraprocedural Data-Flow Analysis via model checking. Based on functionalities provided by the Soot program Analysis platform, the converter generates graph structures from Java classes. Data flow analyses are then expressed as formulas in the modal μ-calculus. Executing the Analysis is carried out by checking the validity of the formulas on the flow graph. The tool demonstration will illustrate the interplay of the involved components, which elegantly provides a fully integrated implementation of Data-Flow Analysis as Model Checking in a software development environment.
-
Generating data flow Analysis algorithms from modal specifications
Science of Computer Programming, 1993Co-Authors: Bernhard SteffenAbstract:Abstract The paper develops a framework that is based on the idea that modal logic provides an appropriate framework for the specification of data flow Analysis (DFA) algorithms as soon as programs are represented as models of the logic. This can be exploited to construct a DFA-generator that generates efficient implementations of DFA-algorithms from modal specifications by partially evaluating a specific model checker with respect to the specifying modal formula. Moreover, the use of a modal logic as specification language for DFA-algorithms supports the compositional development of specifications and structured proofs of properties of DFA-algorithms. The framework is illustrated by means of a real-life example: the problem of determining optimal computation points within flow graphs.
