Source author record

Uday P. Khedker

Uday P. Khedker appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Programming Languages Logic in Computer Science

Catalog footprint

What is connected

8works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Flow- and Context-Sensitive Points-to Analysis using Generalized Points-to Graphs

Computing precise (fully flow-sensitive and context-sensitive) and exhaustive points-to information is computationally expensive. Many practical tools approximate the points-to information trading precision for efficiency. This has adverse impact on computationally intensive analyses such as model checking. Past explorations in top-down approaches of fully flow- and context-sensitive points-to analysis (FCPA) have not scaled. We explore the alternative of bottom-up interprocedural approach which constructs summary flow functions for procedures to represent the effect of their calls. This approach has been effectively used for many analyses. However, it is computationally expensive for FCPA which requires modelling unknown locations accessed indirectly through pointers. Such accesses are commonly handled by using placeholders to explicate unknown locations or by using multiple call-specific summary flow functions. We generalize the concept of points-to relations by using the counts of indirection levels leaving the unknown locations implicit. This allows us to create summary flow functions in the form of generalized points-to graphs (GPGs) without the need of placeholders. By design, GPGs represent both memory (in terms of classical points-to facts) and memory transformers (in terms of generalized points-to facts). We perform FCPA by progressively reducing generalized points-to facts to classical points-to facts. GPGs distinguish between may and must pointer updates thereby facilitating strong updates within calling contexts. The size of GPG is linearly bounded by the number of variables and is independent of the number of statements in the procedure. Empirical measurements on SPEC benchmarks show that GPGs are indeed compact in spite of large procedure sizes. This allows us to scale FCPA to 158 kLoC using GPGs (compared to 35 kLoC reported by liveness-based FCPA).

preprint2016arXiv

Scaling Bounded Model Checking By Transforming Programs With Arrays

Bounded Model Checking is one the most successful techniques for finding bugs in program. However, for programs with loops iterating over large-sized arrays, bounded model checkers often exceed the limit of resources available to them. We present a transformation that enables bounded model checkers to verify a certain class of array properties. Our technique transforms an array-manipulating program in ANSI-C to an array-free and loop-free program. The transformed program can efficiently be verified by an off-the-shelf bounded model checker. Though the transformed program is, in general, an abstraction of the original program, we formally characterize the properties for which the transformation is precise. We demonstrate the applicability and usefulness of our technique on both industry code as well as academic benchmarks.

preprint2015arXiv

Heap Abstractions for Static Analysis

Heap data is potentially unbounded and seemingly arbitrary. As a consequence, unlike stack and static memory, heap memory cannot be abstracted directly in terms of a fixed set of source variable names appearing in the program being analysed. This makes it an interesting topic of study and there is an abundance of literature employing heap abstractions. Although most studies have addressed similar concerns, their formulations and formalisms often seem dissimilar and some times even unrelated. Thus, the insights gained in one description of heap abstraction may not directly carry over to some other description. This survey is a result of our quest for a unifying theme in the existing descriptions of heap abstractions. In particular, our interest lies in the abstractions and not in the algorithms that construct them. In our search of a unified theme, we view a heap abstraction as consisting of two features: a heap model to represent the heap memory and a summarization technique for bounding the heap representation. We classify the models as storeless, store based, and hybrid. We describe various summarization techniques based on k-limiting, allocation sites, patterns, variables, other generic instrumentation predicates, and higher-order logics. This approach allows us to compare the insights of a large number of seemingly dissimilar heap abstractions and also paves way for creating new abstractions by mix-and-match of models and summarization techniques.

preprint2014arXiv

Buffer Overflow Analysis for C

Buffer overflow detection and mitigation for C programs has been an important concern for a long time. This paper defines a string buffer overflow analysis for C programs. The key ideas of our formulation are (a) separating buffers from the pointers that point to them, (b) modelling buffers in terms of sizes and sets of positions of null characters, and (c) defining stateless functions to compute the sets of null positions and mappings between buffers and pointers. This exercise has been carried out to test the feasibility of describing such an analysis in terms of lattice valued functions and relations to facilitate automatic construction of an analyser without the user having to write C/C++/Java code. This is facilitated by devising stateless formulations because stateful formulations combine features through side effects in states raising a natural requirement of C/C++/Java code to be written to describe them. Given the above motivation, the focus of this paper is not to build good static approximations for buffer overflow analysis but to show how given static approximations could be formalized in terms of stateless formulations so that they become amenable to automatic construction of analysers.

preprint2014arXiv

Generalizing the Liveness Based Points-to Analysis

The original liveness based flow and context sensitive points-to analysis (LFCPA) is restricted to scalar pointer variables and scalar pointees on stack and static memory. In this paper, we extend it to support heap memory and pointer expressions involving structures, unions, arrays, and pointer arithmetic. The key idea behind these extensions involves constructing bounded names for locations in terms of compile time constants (names and fixed offsets), and introducing sound approximations when it is not possible to do so. We achieve this by defining a grammar for pointer expressions, suitable memory models and location naming conventions, and some key evaluations of pointer expressions that compute the named locations. These extensions preserve the spirit of the original LFCPA which is evidenced by the fact that although the lattices and flow functions change, the overall data flow equations remain unchanged.

preprint2013arXiv

Interprocedural Data Flow Analysis in Soot using Value Contexts

An interprocedural analysis is precise if it is flow sensitive and fully context-sensitive even in the presence of recursion. Many methods of interprocedural analysis sacrifice precision for scalability while some are precise but limited to only a certain class of problems. Soot currently supports interprocedural analysis of Java programs using graph reachability. However, this approach is restricted to IFDS/IDE problems, and is not suitable for general data flow frameworks such as heap reference analysis and points-to analysis which have non-distributive flow functions. We describe a general-purpose interprocedural analysis framework for Soot using data flow values for context-sensitivity. This framework is not restricted to problems with distributive flow functions, although the lattice must be finite. It combines the key ideas of the tabulation method of the functional approach and the technique of value-based termination of call string construction. The efficiency and precision of interprocedural analyses is heavily affected by the precision of the underlying call graph. This is especially important for object-oriented languages like Java where virtual method invocations cause an explosion of spurious call edges if the call graph is constructed naively. We have instantiated our framework with a flow and context-sensitive points-to analysis in Soot, which enables the construction of call graphs that are far more precise than those constructed by Soot's SPARK engine.

preprint2012arXiv

A Logic for Correlating Temporal Properties across Program Transformations

Program transformations are widely used in synthesis, optimization, and maintenance of software. Correctness of program transformations depends on preservation of some important properties of the input program. By regarding programs as Kripke structures, many interesting properties of programs can be expressed in temporal logics. In temporal logic, a formula is interpreted on a single program. However, to prove correctness of transformations, we encounter formulae which contain some subformulae interpreted on the input program and some on the transformed program. An example where such a situation arises is verification of optimizing program transformations applied by compilers. In this paper, we present a logic called Temporal Transformation Logic (TTL) to reason about such formulae. We consider different types of primitive transformations and present TTL inference rules for them. Our definitions of program transformations and temporal logic operators are novel in their use of the boolean matrix algebra. This results in specifications that are succinct and constructive. Further, we use the boolean matrix algebra in a uniform manner to prove soundness of the TTL inference rules.

preprint2011arXiv

Lazy Pointer Analysis

Flow- and context-sensitive pointer analysis is generally considered too expensive for large programs; most tools relax one or both of the requirements for scalability. We formulate a flow- and context-sensitive points-to analysis that is lazy in the following sense: points-to information is computed only for live pointers and its propagation is sparse (restricted to live ranges of respective pointers). Further, our analysis (a) uses strong liveness, effectively including dead code elimination; (b) afterwards calculates must-points-to information from may-points-to information instead of using a mutual fixed-point; and (c) uses value-based termination of call strings during interprocedural analysis (which reduces the number of call strings significantly). A naive implementation of our analysis within GCC-4.6.0 gave analysis time and size of points-to measurements for SPEC2006. Using liveness reduced the amount of points-to information by an order of magnitude with no loss of precision. For all programs under 30kLoC we found that the results were much more precise than gcc's analysis. What comes as a pleasant surprise however, is the fact that below this cross-over point, our naive linked-list implementation is faster than a flow- and context-insensitive analysis which is primarily used for efficiency. We speculate that lazy flow- and context-sensitive analyses may be not only more precise, but also more efficient, than current approaches.