Müller, Patrick · Publikationsdatenbank der Fraunhofer-Gesellschaft (Fraunhofer-Gesellschaft) · 2015
Information flow analysis is an approach to check whether there is no propagation of information that violates a certain policy in a given program. Flow sensitive analyses, of which implementations for Java already exist, can be very precise in finding malicious flows, but require a lot of resources in terms of computation time and memory consumption. Therefore there is need for a flow-insensitive analysis which can be run faster, yielding results with lesser precision while retaining a high recall. Such an analysis would have several possible applications, e.g. it could be used to analyze a high number of programs to determine which of these contain violations, in order to use flow sensitive analyses on those. This Bachelors thesis provides an implementation of such an analysis based on an already existing pointer analysis. The performance will be compared to an already existing flow sensitive analysis, as well.
Cited by 0
Jeffrey S. Foster, Manuel Fähndrich, Alex Aiken · UC Berkeley · 1997
We describe new type systems for two kinds of flow-insensitive points-to analyses, one based on Andersen's algorithm and one based on Steensgaard's. The type systems are formulated using a mixed constraint framework. These systems can be seen as a straightforward axiomatization of an informal description of the algorithms, and we show this formally by proving soundness with respect to an operational semantics. Further, we show that these two systems are nearly identical, except that one uses subset constraints and one uses unification. We discuss an implementation of these systems and describe experiments that demonstrate that our general framework achieves running times within a small constant factor of a hand-coded solution. We conclude that a mixed constraint system provides a useful, practical framework for static semantic analyses.
Cited by 22
Sam Blackshear, Bor-yuh Evan Chang, Sriram Sankaranarayanan et al. · 2011
Abstract. We present techniques for determining the precision gap between Andersen’s points-to analysis and precise flow-insensitive points-to analysis in practice. While previous work has shown that such a gap may exist, no efficient algorithm for precise flow-insensitive analysis is known, making measurement of the gap on real-world programs difficult. We give an algorithm for precise flow-insensitive analysis of programs with finite memory, based on a novel technique for refining any points-to analysis with a search for flow-insensitive witnesses. We give a compact symbolic encoding of the technique that enables computing the search using a tuned SAT solver. We also present extensions of the algorithm that enable computing lower and upper bounds on the precision gap in the presence of dynamic memory allocation. In our experimental evaluation over a suite of small- to medium-sized C programs, we never observed a precision gap between Andersen’s analysis and the precise analysis. In other words, Andersen’s analysis computed a precise flow-insensitive result for all of our benchmarks. Hence, we conclude that while better algorithms for the precise flow-insensitive analysis are still of theoretical interest, their practical impact for C programs is likely to be negligible. 1
Cited by 0
Michael Burke, Paul R. Carini, Jong-deok Choi et al. · 1994
Data-flow analysis computes information about the potential behavior of a program in terms of the definitions and uses of data objects. Data-flow analysis for programs written in languages such as FORTRAN has been well developed. However, due to the presence of pointers, data-flow analysis has been less successful for languages such as C, C++, LISP, and Fortran 90. Data-flow analysis algorithms can be classified into two categories: flow-sensitive and flowinsensitive. To improve efficiency, flow-insensitive interprocedural analyses do not make use of the intraprocedural control flow information associated with individual procedures. Since pointer-induced aliases can change within a procedure, applying known flow-insensitive analyses can result in either incorrect or overly conservative solutions. In this paper, we present a flowinsensitive data-flow analysis algorithm that computes interprocedural pointer-induced aliases. We improve the precision of our analysis by (1) making use of c...
Cited by 0
Rebecca Hasti, Susan Horwitz · 1998
A pointer-analysis algorithm can be either flow-sensitive or flow-insensitive. While flow-sensitive analysis usually provides more precise information, it is also usually considerably more costly in terms of time and space. The main contribution of this paper is the presentation of another option in the form of an algorithm that can be 'tuned' to provide a range of results that fall between the results of flow-insensitive and flow-sensitive analysis. The algorithm combines a flow-insensitive pointer analysis with static single assignment (SSA) form and uses an iterative process to obtain progressively better results.
Cited by 86
Sam Blackshear, Bor-yuh Evan Chang, Sriram Sankaranarayanan et al. · 2011
We present techniques for determining the precision gap between Andersen’s points-to analysis and precise flow-insensitive points-to analysis in practice. While previous work has shown that such a gap may exist, no efficient algorithm for precise flow-insensitive analysis is known, making measurement of the gap on real-world programs difficult. We give an algorithm for precise flow-insensitive analysis of programs with finite memory, based on a novel technique for refining any points-to analysis with a search for flow-insensitive witnesses. We give a compact symbolic encoding of the technique that enables computing the search using a tuned SAT solver. We also present extensions of the algorithm that enable computing lower and upper bounds on the precision gap in the presence of dynamic memory allocation. In our experimental evaluation over a suite of small- to medium-sized C programs, we never observed a precision gap between Andersen’s analysis and the precise analysis. In other words, Andersen’s analysis computed a precise flow-insensitive result for all of our benchmarks. Hence, we conclude that while better algorithms for the precise flow-insensitive analysis are still of theoretical interest, their practical impact for C programs is likely to be negligible.
Cited by 0
Foster, Jeffrey S, Author, Fahndrich, Manuel, Author, Aiken, Alexander, Author · UC Berkeley
We carry out an experimental analysis for two of the design dimensions of flow-insensitive points-to analysis for C: polymorphic versus monomorphic and equality-based versus inclusion-based. Holding other analysis parameters fixed, we measure the precision of the four design points on a suite of benchmarks of up to 90,000 abstract syntax tree nodes. Our experiments show that the benefit of polymorphism varies significantly with the underlying monomorphic analysis. For our equality-based analysis, adding polymorphism greatly increases precision, while for our inclusion-based analysis, adding polymorphism hardly makes any difference. We also gain some insight into the nature of polymorphism in points-to analysis of C. In particular, we find considerable polymorphism available in function parameters, but little or no polymorphism in function results, and we show how this observation explains our results
Cited by 0
Er Aiken, Manuel Fähndrich, Jeffrey S. Foster et al. · 2000
We carry out an experimental analysis for two of the design dimensions of flow-insensitive points-to analysis for C: polymorphic versus monomorphic and equality-based versus inclusion-based. Holding other analysis parameters fixed, we measure the precision of the four design points on a suite of benchmarks of up to 90,000 abstract syntax tree nodes. Our experiments show that the benefit of polymorphism varies significantly with the underlying monomorphic analysis. For our equality-based analysis, adding polymorphism greatly increases precision, while for our inclusion-based analysis, adding polymorphism hardly makes any difference. We also gain some insight into the nature of polymorphism in points-to analysis of C. In particular, we find considerable polymorphism available in function parameters, but little or no polymorphism in function results, and we show how this observation explains our results.
Cited by 0
Sridharan, Manu, Chang, Bor-Yuh Evan, Blackshear, Sam et al. · CU Scholar (University of Colorado Boulder) · 2011
Cited by 0Open access
Roy Shea · 2007
1 Introduction to Related Work This paper examines the relationship between Lighthouse and current verification and analysis work within the system community. Recent work on ownership often describes ownership using flow insensitive or flow sensitive types. At times this boundary is not perfectly clear. Flow insensitive ownership analysis tends to use
Cited by 0
Alejandro Russo, Andrei Sabelfeld · 2010
Abstract—This paper seeks to answer fundamental questions about trade-offs between static and dynamic security analysis. It has been previously shown that flow-sensitive static informationflow analysis is a natural generalization of flow-insensitive static analysis, which allows accepting more secure programs. It has been also shown that sound purely dynamic information-flow enforcement is more permissive than static analysis in the flowinsensitive case. We argue that the step from flow-insensitive to flow-sensitive is fundamentally limited for purely dynamic information-flow controls. We prove impossibility of a sound purely dynamic information-flow monitor that accepts programs certified by a classical flow-sensitive static analysis. A side implication is impossibility of permissive dynamic instrumented security semantics for information flow, which guides us to uncover an unsound semantics from the literature. We present a general framework for hybrid mechanisms that is parameterized in the static part and in the reaction method of the enforcement (stop, suppress, or rewrite) and give security guarantees with respect to termination-insensitive noninterference for a simple language with output. I.
Cited by 0
Barbara G. Ryder, William A. Landi, Philip A. Stocks et al. · 2001
The first interprocedural modification side-effects analysis for C (MODC) that obtains better than worst-case precision on programs with general-purpose pointer usage is presented with empirical results. The analysis consists of an algorithm schema corresponding to a family of MODC algorithms with two independent phases: one for determining pointer-induced aliases and a subsequent one for propagating interprocedural side effects. These MODC algorithms are parameterized by the aliasing method used. The empirical results compare the performance of two dissimilar MODC algorithms: MODC(FSAlias) uses a flow-sensitive, calling-context-sensitive interprocedural alias analysis; MODC(FIAlias) uses a flow-insensitive, calling-context-insensitive alias analysis which is much faster, but less accurate. These two algorithms were profiled on 45 programs ranging in size from 250 to 30,000 lines of C code, and the results demonstrate dramatically the possible costprecision trade-offs. This first comparative implementation of MODC analyses offers insight into the differences between flow-/context-sensitive and flow-/context-insensitive analyses. The analysis cost versus precision trade-offs in side-effect information obtained are reported. The results show surprisingly that the precision of flow-sensitive side-effect analysis is not always prohibitive in cost, and that the precision of flow-insensitive analysis is substantially better than worst-case estimates
Cited by 0
Bohn, M.A. · Publikationsdatenbank der Fraunhofer-Gesellschaft (Fraunhofer-Gesellschaft) · 2009
S.7.1-7.16
Cited by 0
Barbara G. Ryder, William Landi, P. Stocks et al. · ACM Transactions on Programming Languages and Systems · 2001
The first interprocedural modification side-effects analysis for C (MOD C ) that obtains better than worst-case precision on programs with general-purpose pointer usage is presented with empirical results. The analysis consists of an algorithm schema corresponding to a family of MOD C algorithms with two independent phases: one for determining pointer-induced aliases and a subsequent one for propagating interprocedural side effects. These MOD C algorithms are parameterized by the aliasing method used. The empirical results compare the performance of two dissimilar MOD C algorithms: MOD C ( FSAlias ) uses a flow-sensitive, calling-context-sensitive interprocedural alias analysis; MOD C ( FIAlias uses a flow-insensitive, calling-context-insensitive alias analysis which is much faster, but less accurate. These two algorithms were profiled on 45 programs ranging in size from 250 to 30,000 lines of C code, and the results demonstrate dramatically the possible cost-precision trade-offs. This first comparative implementation of MOD C analyses offers insight into the differences between flow-/context-sensitive and flow-/context-insensitive analyses. The analysis cost versus precision trade-offs in side-effect information obtained are reported. The results show surprisingly that the precision of flow-sensitive side-effect analysis is not always prohibitive in cost, and that the precision of flow-insensitive analysis is substantially better than worst-case estimates and seems sufficient for certain applications. On average MOD C ( FSAlias ) for procedures and calls is in the range of 20% more precise than MOD C ( FIAlias ); however, the performance was found to be at least an order of magnitude slower than MOD C ( FIAlias ).
Cited by 96Open access
Prakash Prabhu, Priti Shankar · 2006
Abstract. Context sensitive pointer analyses based on the bddbddb [1] system have been shown to scale to large Java programs. We provide a technique to incorporate flow sensitivity for Java fields into one such analysis and obtain an escape analysis based on it. First, we express an intraprocedural field flow sensitive analysis, using the Heap Array SSA form [2] in Datalog. We then extend this analysis interprocedurally by introducing two new φ functions for Heap Array SSA Form and adding deduction rules corresponding to them. Adding a few more rules gives us an escape analysis. We describe two types of field flow sensitivity: partial(PFFS) and full(FFFS), the former without strong updates to fields and the latter with strong updates. We compare these analyses with two different (field flow insensitive) versions of Whaley-Lam analysis[1]: one of which is flow sensitive for locals(FS) and the other, flow insensitive for locals(FIS). We have implemented this analysis on the bddbddb system while using the SOOT open source framework[3] as a front end to it. We have run our analysis on a set of 15 Java programs. Our experimental results show that the time taken by our field flow sensitive analyses is comparable to that of the field flow insensitive versions while doing much better in some cases. Our PFFS analysis achieves average reductions of about 23 % and 30 % in the size of the points-to sets at load and store statements respectively and discovers 71 % more “caller-captured ” objects than FIS. 1
Cited by 0
Michael Burke · ACM Transactions on Programming Languages and Systems · 1990
We reformulate interval analysis so that it can he applied to any monotone data-flow problem, including the nonfast problems of flow-insensitive interprocedural analysis. We then develop an incremental interval analysis technique that can be applied to the same class of problems. When applied to flow-insensitive interprocedural data-flow problems, the resulting algorithms are simple, practical, and efficient. With a single update, the incremental algorithm can accommodate any sequence of program changes that does not alter the structure of the program call graph. It can also accommodate a large class of structural changes. For alias analysis, we develop an incremental algorithm that obtains the exact solution as computed by an exhaustive algorithm. Finally, we develop a transitive closure algorithm that is particularly well suited to the very sparse matrices associated with the problems we address.
Cited by 129Open access
Fabian Stemmler, Michael Schwarz, Julian Erhard et al. · ArXiv.org · 2025
Static analysis of real-world programs combines flow- and context-sensitive analyses of local program states with computation of flow- and context-insensitive invariants at globals, that, e.g., abstract data shared by multiple threads. The values of locals and globals may mutually depend on each other, with the analysis of local program states both making contributions to globals and querying their values. Usually, all contributions to globals are accumulated during fixpoint iteration, with widening applied to enforce termination. Such flow-insensitive information often becomes unnecessarily imprecise and can include superfluous contributions -- trash -- which, in turn, may be toxic to the precision of the overall analysis. To recover precision of globals, we propose techniques complementing each other: Narrowing on globals differentiates contributions by origin; reluctant widening limits the amount of widening applied at globals; and finally, abstract garbage collection undoes contributions to globals and propagates their withdrawal. The experimental evaluation shows that these techniques increase the precision of mixed flow-sensitive analyses at a reasonable cost.
Cited by 0Open access
Saumya Debray · 2007
Interprocedural analyses can be classified as either context-insensitive, which tend to sacrifice precision to gain efficiency, or context-sensitive, which are more precise but also more expensive. This paper discusses a profile-guided approach to interprocedural analysis that is context-sensitive, and hence more precise, for the "important" call sites for a function, and context-insensitive, and hence more efficient, for the "unimportant" call sites. Experiments indicate that this approach can be significantly more efficient than a traditional context-sensitive analysis without sacrificing much of the pragmatic value of the dataflow information gathered. 1 Introduction For code analysis and optimization purposes, compilers typically construct a control flow graph for each function in a program [1]. Control flow across function boundaries is often represented using an interprocedural control flow graph (e.g., see [15]), which consists of the control flow graphs of all the functions i...
Cited by 0
Lian Li, Cristina Cifuentes, Nathan Keynes · 2011
Points-to analysis is a fundamental static analysis technique which computes the set of memory objects that a pointer may point to. Many different applications, such as security-related program analyses, bug checking, and analyses of multi-threaded programs, require precise points-to information to be effective. Recent work has focused on improving the precision of points-to analysis through flow-sensitivity and great progress has been made. However, even with all recent progress, flow-sensitive points-to analysis can still be much slower than a flow-insensitive analysis.
Cited by 97
Sundaresan, Vijay. · eScholarship@McGill (McGill) · 1999
Virtual method calls are a fundamental feature offered by Java, an object-oriented programming language. However, they are also a source of degradation of performance at run time and imprecision in interprocedural analyses. There are several well known, inexpensive analyses that have been developed for virtual call resolution. However, they have been observed to be effective in resolving method calls in library code, while not being very effective in the benchmark code excluding libraries. We present a new flow insensitive and context insensitive analysis called reaching type analysis in this thesis. We present the analysis rules for two variations of this analysis, variable type analysis and a coarser grained version declared type analysis. Reaching type analysis is based on an analysis that builds a type propagation graph where nodes represent variables and edges represent the flow of types due to assignments. We have implemented variable type analysis and declared type analysis, and tw...
Cited by 1Open access