Search

Die Arbeit mit Zeigern auf dynamisch erzeugte Speicherbereiche ist oft fehleranfallig: Obwohl z.B. die beiden Funktionen.

We propose a novel notion of pointer race for concurrent programs manipulating a shared heap. A pointer race is an access to a memory address which was freed, and it is out of the accessor's control whether or not the cell has been re-allocated. We establish two results. 1 Under the assumption of pointer race freedom, it is sound to verify a program running under explicit memory management as if it was running with garbage collection. 2 Even the requirement of pointer race freedom itself can be verified under the garbage-collected semantics. We then prove analogues of the theorems for a stronger notion of pointer race needed to cope with performance-critical code purposely using racy comparisons and even racy dereferences of pointers. As a practical contribution, we apply our results to optimize a thread-modular analysis under explicit memory management. Our experiments confirm a speed-up of upi¾?to two orders of magnitude.

This chapter is the heart of the book. It explains algorithms, technical details and programming tricks of various approaches to implementation of persistent data—binary and ASCII serialization, memory paging, disk paging and smart pointers. The last section presents QSP (Quasi-Single-Page), a new design of persistent data which, besides other languages, also works in Objective-C and with iPhone applications.

Modern object-oriented programming languages such as C++ provide convenient abstractions and data encapsulation mechanisms for software developers. However, these features also complicate testing and static analysis of programs that utilize object-oriented programming concepts. In particular, the C++ language exhibits features such as multiple inheritance, static and dynamic typecasting that make static analyzers for C++ quite hard to implement. In this paper, we present an approach where static analysis is performed by lowering the original C++ program into a semantically equivalent C program. However, unlike existing translation mechanisms that utilize complex pointer arithmetic operations, virtual-base offsets, virtual-function pointer tables, and calls to run-time libraries to model C++ features, our translation is targeted towards making static program analyzers for C++ easier to write and provide more precise results. We have implemented our ideas in a framework for C++ called CILpp that is analogous to the popular C Intermediate Language (CIL) framework. We evaluate the effectiveness of our translation in a bug finding tool that uses abstract interpretation and model checking. The bug finding tool uncovered several previously unknown bugs in C++ open source projects.

The ability to perform strong updates is the main contributor to the precision of flow-sensitive pointer analysis algorithms. Traditional flow-sensitive pointer analyses cannot strongly update pointers residing in the heap. This is a severe restriction for Java programs. In this paper, we propose a new flow-sensitive pointer analysis algorithm for Java that can perform strong updates on heap-based pointers effectively. Instead of points-to graphs, we represent our points-to information as maps from access paths to sets of abstract objects. We have implemented our analysis and run it on several large Java benchmarks. The results show considerable improvement in precision over the points-to graph based flow-insensitive and flow-sensitive analyses, with reasonable running time.

Strings are commonly used in a large variety of software. And yet, they are a common source of bugs involving invalid memory accesses arising due to the misuse of the string manipulation API. Such bugs are often remotely exploitable, leading to severe consequences. Therefore, static detection of invalid memory accesses due to string operations has received much attention, especially for C programs that use the standard C library functions. More recently, software is increasingly being developed in object-oriented languages such as C++ and Java. However, the need to interact with legacy C code and C-based system-level APIs often necessitates the use of a mixed programming paradigm that combines features of high-level object-oriented constructs with calls to standard C library functions. While such programs are commonplace, there has been little research on static analysis of such programs. In this paper, we present memory models for C++ programs that are heap-aware, with an emphasis on modeling dynamically allocated memory, use of null-terminated string buffers, C++ Standard Template Library (STL) classes, and the interactions among these features. We use standard verification techinques such as abstract interpretation and model checking to verify properties over these models to find potential bugs. Our tool can find several previously unknown bugs in open-source projects. These bugs are primarily due to the subtle interactions of the intricate C++ programming model with legacy C string API.

The competency of pointer analysis is crucial for many compiler optimizations, transformations, and checks like memory safety. The potential interaction between threads in multithreaded programs complicates their pointer analysis and memory-safety check. The trade-off between accuracy and scalability remains a main issue when studying these analyses. In this work, we present novel approaches for the pointer analysis and memory safety of multithreaded programs as simply structured type systems. In order to balance accuracy and scalability, the type system proposed for pointer analysis of multithreaded programs is flow-sensitive and it invokes another flow-insensitive type system for parallel constructs. Therefore the proposed pointer analysis is described as flow sensitive-insensitive. The third type system presented in this paper takes care of memory safety of multithreaded programs and is an extension of the type system of pointer analysis. Programs having types in memory-safety type system, are guaranteed to be memory safe. Type derivations serve as proofs for correctness of the result of every pointer analysis and memory-safety check. Such proofs are required in the area of proof-carrying code.

Current (heterogeneous) multi-core environments such as gpGPU architectures are hard to program with normal imperative and object-oriented (OO) languages. There are two basic problems to tackle: (1) it is too easy to program race conditions and dead-locks with the available synchronization primitives, and (2) these environments do not support (or support inefficiently) the instructions required for efficient execution of OO programs, e.g., because function pointers and pointer arithmetic are lacking. We address both problems with a new language that comprises both Functional Programming (FP) and OO programming. We solve problem (1) by auto-parallelization in the functional core where all loops and non-dependent calls can be executed in parallel. FP is to be used to write computational intensive code with safe concurrent memory access. An alternative object model that does neither use pointer arithmetic nor function pointers but smart pointers/proxies (to implement polymorphism) as well as mixins and templates (to implement OO like code reuse) solves problem (2). To cleanly integrate the two language cores, we propose a new integration model that even grants some restricted ways to access state from within FP mode. With the new language and prototype compiler we can transparently parallelize code to target both Cuda and multi-core machines (without annotations from the programmer) and obtain good speedups.

Pointer analysis statically approximates the heap pointer structure during a program execution in order to track heap objects or to establish alias relations between references, and usually contributes to other analyses or code optimizations. In recent years, a number of algorithms have been presented that provide an efficient, scalable, and yet precise pointer analysis. However, it is unclear how the results of these algorithms compare to each other semantically. In this paper, we present a general region type system for a Java-like language and give a formal soundness proof. The system is subsequently specialized to obtain a platform for embedding the results of various existing context-sensitive pointer analysis algorithms, thereby equipping the computed relations with a common interpretation and verification. We illustrate our system by outlining an extension to a string value analysis that builds on pointer information.

Many logspace algorithms are naturally described as programs that operate on a structured input (e.g. a graph), that store in memory only a constant number of pointers (e.g. to graph nodes) and that do not use pointer arithmetic. Such "pure pointer algorithms" thus are a useful abstraction for studying the nature of logspace -computation. In this paper we introduce a formal class purple of pure pointer programs and study them on locally ordered graphs. Existing classes of pointer algorithms, such as Jumping Automata on Graphs ( jag s) or Deterministic Transitive Closure ( dtc ) logic, often exclude simple programs. purple subsumes these classes and allows for a natural representation of many graph algorithms that access the input graph by a constant number of pure pointers. It does so by providing a primitive for iterating an algorithm over all nodes of the input graph in an unspecified order. Since pointers are given as an abstract data type rather than as binary digits we expect that logarithmic-size worktapes cannot be encoded using pointers as is done, e.g. in totally-ordered dtc logic. We show that this is indeed the case by proving that the property "the number of nodes is a power of two," which is in logspace , is not representable in purple .

Pointer information is a prerequisite for most program analyses, and inclusion-based, i.e. Andersen-style, pointer analysis is widely used to compute such information. However, current inclusion-based analyses can have prohibitive costs in time and space, especially for programs with millions of lines of code. We present a suite of offline optimizations that exploit pointer and location equivalence to shrink the input to the subsequent pointer analysis without affecting precision, dramatically reducing both analysis time and memory consumption. Using a suite of six open-source C programs ranging in size from 169K to 2.17M LOC, we demonstrate that our techniques on average improve analysis time by 1.3-2.7× and reduce memory consumption by 3.2-6.9× over the best current techniques.

Implementing a new programming language by the means of a translator to an existing language is attractive as it provides portability over all platforms supported by the host language and reduces the development time as many low-level tasks can be delegated to the host compiler. The C and C++ programming languages are popular choices for many language implementations due to the availability of efficient compilers on many platforms, and good portability. For garbage-collected languages, however, they are not a perfect match as they provide no support for accurately discovering pointers to heap-allocated data. We evaluate the published techniques, and propose a new mechanism, lazy pointer stacks, for performing accurate garbage collection in such uncooperative environments. We implemented the new technique in the Ovm Java virtual machine with our own Java-to-C++ compiler and GCC as a back-end, and found that our technique outperforms existing approaches.

We present a method for proving data refinement in the presence of low-level pointer operations, such as memory allocation and deallocation, and pointer arithmetic. Surprisingly, none of the existing methods for data refinement, including those specifically designed for pointers, are sound in the presence of low-level pointer operations. The reason is that the low-level pointer operations allow an additional potential for obtaining the information about the implementation details of the module: using memory allocation and pointer comparison, a client of a module can find out which cells are internally used by the module, even without dereferencing any pointers. The unsoundness of the existing methods comes from the failure of handling this potential. In the paper, we propose a novel method for proving data refinement, called power simulation, and show that power simulation is sound even with low-level pointer operations.

Pointer analysis plays a critical role in modern C compilers because of the frequent appearances of pointer expressions. It is even more important for data dependence analysis, which is essential in exploiting parallelism, because complex data structures such as arrays are often accessed through pointers in C. One of the important aspects of pointer analysis methods is their granularity, the way in which the memory objects are named for analysis. The naming schemes used in a pointer analysis affect its effectiveness, especially for pointers pointing to heap memory blocks. In this paper, we present a new approach that applies the compiler analysis and profiling techniques together to study the impact of the granularity in pointer analyses. An instrumentation tool, based on the Intel's Open Resource Compiler (ORC), is devised to simulate different naming schemes and collect precise target sets for indirect references at runtime. The collected target sets are then fed back to the ORC compiler to evaluate the effectiveness of different granularity in pointer analyses. The change of the alias queries in the compiler analyses and the change of performance of the output code at different granularity levels are observed. With the experiments on the SPEC CPU2000 integer benchmarks, we found that 1) finer granularity of pointer analysis show great potential in optimizations, and may bring about up to 15% performance improvement, 2) the common naming scheme, which gives heap memory blocks names according to the line number of system memory allocation calls, is not powerful enough for some benchmarks. The wrapper functions for allocation or the user-defined memory management functions have to be recognized to produce better pointer analysis result, 3) pointer analysis of fine granularity requires inter-procedural analysis, and 4) it is also quite important that a naming scheme distinguish the fields of a structure in the targets.

Array-Range Analysis computes at compile time the range of possible index values for each array-index expression in a program. This information can be used to detect potential out-of-bounds array accesses and to identify non-aliasing array accesses. In a language like C, where arrays can be accessed indirectly via pointers, and where pointer arithmetic is allowed, range analysis must be extended to compute the range of possible values for each pointer dereference.

We present a new algorithm for checking the shape-safety of pointer manipulation programs. In our model, an abstract, data-less pointer structure is a graph. A shape is a language of graphs. A pointer manipulation program is modelled abstractly as a set of graph rewrite rules over such graphs where each rule corresponds to a pointer manipulation step. Each rule is annotated with the intended shape of its domain and range and our algorithm checks these annotations.

We are developing a distributed object oriented spatial database prototype. We are extending the GIDB prototype (developed at NRL for using and querying OVPF databases) to support distribution. GIDB is a Geographical Information System coupled with an object-oriented spatial database, which is implemented using the GemStone Object Database. We are currently exploring alternatives to add distribution to the prototype. We tried GemEnterprise as our distributed OODB, but needed to add a different model of distribution to it. In order to do so, we used a smart pointer technique, taking advantage of the dynamic capabilities of the SmallTalk language. Also, we did several experiments comparing performance of returning a smart pointer from a remote method, or returning a copy of the remote object. The smart pointer usually is smaller, so the transmission cost is smaller, but future messages have to be done remotely instead of locally.

Languages, such as C++, that combine static type checking with inheritance pose a challenge to the compiler writer: the flexibility of the type and scope system implies that a compiler must be able to cope with data structures of a complexity far exceeding what is needed for traditional languages. Fortunately, they also supply the means for coping with this complexity. This paper describes the strategies devised for representing and manipulating C++ scopes and the storage management techniques employed to make these representations efficient. The techniques have been used to implement a C++ compiler in C++.