Automatic generation of assertions to detect potential security vulnerabilities in C programs that use union and pointer types

Type unions, pointer variables and function pointers are a long standing source of subtle security bugs in C program code. Their use can lead to hard-to-diagnose crashes or exploitable vulnerabilities that allow an attacker to attain privileged access over classified data. This paper describes an automatable framework for detecting such weaknesses in C programs statically, where possible, and for generating assertions that will detect them dynamically, in other cases. Exclusively based on analysis of the source code, it identifies required assertions using a type inference system supported by a custom made symbol table. In our preliminary findings, our type system was able to infer the correct type of unions in different scopes, without manual code annotations or rewriting. Whenever an evaluation is not possible or is difficult to resolve, appropriate runtime assertions are formed and inserted into the source code. The approach is demonstrated via a prototype C analysis tool.

Field Flow Sensitive Pointer and Escape Analysis for Java Using Heap Array SSA

Context sensitive pointer analyses based on Whaley and Lam’s bddbddb 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 Fink et al.’s Heap Array SSA form 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: 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 as a front end. 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.

Scalable flow-sensitive pointer analysis for fava with strong updates

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.

Parallel Flow-Sensitive Pointer Analysis by Graph-Rewriting

Precise pointer analysis is a problem of interest to both the compiler and the program verification community. Flow-sensitivity is an important dimension of pointer analysis that affects the precision of the final result computed. Scaling flow-sensitive pointer analysis to millions of lines of code is a major challenge. Recently, staged flow-sensitive pointer analysis has been proposed, which exploits a sparse representation of program code created by staged analysis. In this paper we formulate the staged flow-sensitive pointer analysis as a graph-rewriting problem. Graph-rewriting has already been used for flow-insensitive analysis. However, formulating flow-sensitive pointer analysis as a graph-rewriting problem adds additional challenges due to the nature of flow-sensitivity. We implement our parallel algorithm using Intel Threading Building Blocks and demonstrate considerable scaling (upto 2.6x) for 8 threads on a set of 10 benchmarks. Compared to the sequential implementation of staged flow-sensitive analysis, a single threaded execution of our implementation performs better in 8 of the benchmarks.

SymbolDesign: A User-centered Method to Design Pen-based Interfaces and Extend the Functionality of Pointer Input Devices

A method called "SymbolDesign" is proposed that can be used to design user-centered interfaces for pen-based input devices. It can also extend the functionality of pointer input devices such as the traditional computer mouse or the Camera Mouse, a camera-based computer interface. Users can create their own interfaces by choosing single-stroke movement patterns that are convenient to draw with the selected input device and by mapping them to a desired set of commands. A pattern could be the trace of a moving finger detected with the Camera Mouse or a symbol drawn with an optical pen. The core of the SymbolDesign system is a dynamically created classifier, in the current implementation an artificial neural network. The architecture of the neural network automatically adjusts according to the complexity of the classification task. In experiments, subjects used the SymbolDesign method to design and test the interfaces they created, for example, to browse the web. The experiments demonstrated good recognition accuracy and responsiveness of the user interfaces. The method provided an easily-designed and easily-used computer input mechanism for people without physical limitations, and, with some modifications, has the potential to become a computer access tool for people with severe paralysis.

Pointer Swizzling: Unterbrechung erwünscht!

Vortragsfolien eines auf dem SAP ABAP-Jahrestreffen 20.-22.9.1995 in Ottrott/Elsaß gehaltenen Vortrags. - Zusammenfassung: Unter Pointer Swizzling versteht man eine Technik, persistente Zeiger in Datenbeständen zur Laufzeit so geschickt durch Hauptspeicherzeiger zu ersetzen, dass schnelles Durchlaufen komplexer Objektstrukturen möglich wird. Den Begriff umgibt ein Hauch von „Magie“, vielleicht auch wegen der Geheimniskrämerei, mit der eine Firma diese Technik in ihrem Datenbankprodukt umgibt. Der Vortrag soll zeigen, dass die Grundprinzipien des Pointer Swizzling eigentlich sehr einfach sind. Andererseits gibt es eine erstaunliche Vielfalt von recht unterschiedlichen Spielarten, was eine sachliche Diskussion über das Konzept und die Vor- und Nachteile erschwert. An einem durchgängigen Beispiel wird die Umsetzung in eine eigene Anwendung veranschaulicht, wobei - wie im Softwaregeschäft üblich - einige gut getarnte Fallgruben auf den Implementierer warten.

Emergence of the Pointer Basis through the Dynamics of Correlations

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

[A-mode ultrasonic pointer for navigated pelvic surgery]

Surgical navigation has proven to be a minimally invasive procedure that enables precise surgical interventions with reduced exposure to irradiation for patient and personnel. Fluoroscopy-based modules have prevailed on the market. For certain operations of the pelvis computed tomography is necessary with its high imaging quality and considerably larger scan volume. To enable navigation in these cases, matching of the CT data set and the patient's real pelvic bone is essential. The common pair point-matching algorithm is complemented by the surface-matching algorithm to achieve an even higher overall precision of the system. For conventional surface matching with a solid pointer, the bone has to be exposed from soft tissue quite extensively, using a solid pointer. This conflicts with the claim of computer-assisted surgery to be minimally invasive. We integrated an A-mode ultrasonic pointer with the intention to perform extended surface matching on the pelvic bone noninvasively. Related to the conventional method, comparable and to some extent even improved precision conditions could be established.

Augmenting a Laser Pointer with a Diffraction Grating for Monoscopic 6DOF Detection

This article illustrates the detection of 6 degrees of freedom (DOF) for Virtual Environment interactions using a modified simple laser pointer device and a camera. The laser pointer is combined with a diffraction rating to project a unique laser grid onto the projection planes used in projection-based immersive VR setups. The distortion of the projected grid is used to calculate the translational and rotational degrees of freedom required for human-computer interaction purposes.

Parallelizing irregular and pointer-based computations automatically: perspectives from logic and constraint programming

Irregular computations pose sorne of the most interesting and challenging problems in automatic parallelization. Irregularity appears in certain kinds of numerical problems and is pervasive in symbolic applications. Such computations often use dynamic data structures, which make heavy use of pointers. This complicates all the steps of a parallelizing compiler, from independence detection to task partitioning and placement. Starting in the mid 80s there has been significant progress in the development of parallelizing compilers for logic pro­gramming (and more recently, constraint programming) resulting in quite capable paralle­lizers. The typical applications of these paradigms frequently involve irregular computations, and make heavy use of dynamic data structures with pointers, since logical variables represent in practice a well-behaved form of pointers. This arguably makes the techniques used in these compilers potentially interesting. In this paper, we introduce in a tutoríal way, sorne of the problems faced by parallelizing compilers for logic and constraint programs and provide pointers to sorne of the significant progress made in the area. In particular, this work has resulted in a series of achievements in the areas of inter-procedural pointer aliasing analysis for independence detection, cost models and cost analysis, cactus-stack memory management, techniques for managing speculative and irregular computations through task granularity control and dynamic task allocation such as work-stealing schedulers), etc.

Automatic parallelization of irregular and pointer-based computations: perspectives from logic and constraint programming

Irregular computations pose some of the most interesting and challenging problems in automatic parallelization. Irregularity appears in certain kinds of numerical problems and is pervasive in symbolic applications. Such computations often use dynamic data structures which make heavy use of pointers. This complicates all the steps of a parallelizing compiler, from independence detection to task partitioning and placement. In the past decade there has been significant progress in the development of parallelizing compilers for logic programming and, more recently, constraint programming. The typical applications of these paradigms frequently involve irregular computations, which arguably makes the techniques used in these compilers potentially interesting. In this paper we introduce in a tutorial way some of the problems faced by parallelizing compilers for logic and constraint programs. These include the need for inter-procedural pointer aliasing analysis for independence detection and having to manage speculative and irregular computations through task granularity control and dynamic task allocation. We also provide pointers to some of the progress made in these áreas. In the associated talk we demónstrate representatives of several generations of these parallelizing compilers.

Extreme pointer years in tree-ring records of central Spain as evidence of climatic events and the eruption of the Huaynaputina Volcano (Peru, 1600 AD)

The study of pointer years of numerous tree-ring chronologies of the central Iberian Peninsula (Sierra de Guadarrama) could provide complementary information about climate variability over the last 405 yr. In total, 64 pointer years have been identified: 30 negative (representing minimum growths) and 34 positive (representing maximum growths), the most significant of these being 1601, 1963 and 1996 for the negative ones, and 1734 and 1737 for the positive ones. Given that summer precipitation was found to be the most limiting factor for the growth of Pinus in the Sierra de Guadarrama in the second half of the 20th century, it is also an explanatory factor in almost 50% of the extreme growths. Furthermore, these pointer years and intervals are not evenly distributed throughout time. Both in the first half of the 17th and in the second half of 20th, they were more frequent and more extreme and these periods are the most notable for the frequency of negative pointer years in Central Spain. The interval 1600–1602 is of special significance, being one of the most unfavourable for tree growth in the centre of Spain, with 1601 representing the minimum index in the regional chronology. We infer that this special minimum annual increase was the effect of the eruption of Huaynaputina, which occurred in Peru at the beginning of 1600 AD. This is the first time that the effects of this eruption in the tree-ring records of Southern Europe have been demonstrated.