bluuebunny/crossref_metadata_2025 huggingface dataset:
Adaptive functional programming
Authors: Acar Umut A. , Blelloch Guy E. , Harper Robert
Published: November 2005

An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain limited in their scope of applicability. We propose a general mechanism for adaptive computing that enables one to make any purely-functional program adaptive.We show that the mechanism is practical by giving an efficient implementation as a small ML library. The library consists of three operations for making a program adaptive, plus two operations for making changes to the input and adapting the output to these changes. We give a general bound on the time it takes to adapt the output, and based on this, show that an adaptive Quicksort adapts its output in logarithmic time when its input is extended by one key.To show the safety and correctness of the mechanism we give a formal definition of
AFL
, a call-by-value functional language extended with adaptivity primitives. The modal type system of
AFL
enforces correct usage of the adaptivity mechanism, which can only be checked at run time in the ML library. Based on the
AFL
dynamic semantics, we formalize the change-propagation algorithm and prove its correctness.
The strength of non-size increasing computation
Authors: Hofmann Martin
Published: November 2005

We study the expressive power of non-size increasing recursive definitions over lists. This notion of computation is such that the size of all intermediate results will automatically be bounded by the size of the input so that the interpretation in a finite model is sound with respect to the standard semantics. Many well-known algorithms with this property such as the usual sorting algorithms are definable in the system in the natural way. The main result is that a characteristic function is definable if and only if it is computable in time
O
(2
p(n)
) for some polynomial
p
.The method used to establish the lower bound on the expressive power also shows that the complexity becomes polynomial time if we allow primitive recursion only. This settles an open question posed in [1, 7].The key tool for establishing upper bounds on the complexity of derivable functions is an interpretation in a finite relational model whose correctness with respect to the standard interpretation is shown using a semantic technique.
Stack inspection
Authors: Fournet Cédric , Gordon Andrew D.
Published: November 2005

Stack inspection is a security mechanism implemented in runtimes such as the JVM and the CLR to accommodate components with diverse levels of trust. Although stack inspection enables the fine-grained expression of access control policies, it has rather a complex and subtle semantics. We present a formal semantics and an equational theory to explain how stack inspection affects program behaviour and code optimisations. We discuss the security properties enforced by stack inspection, and also consider variants with stronger, simpler properties.
Resource usage analysis
Authors: Igarashi Atsushi , Kobayashi Naoki
Published: November 2005

It is an important criterion of program correctness that a program accesses resources in a valid manner. For example, a memory region that has been allocated should be eventually deallocated, and after the deallocation, the region should no longer be accessed. A file that has been opened should be eventually closed. So far, most of the methods to analyze this kind of property have been proposed in rather specific contexts (like studies of memory management and verification of usage of lock primitives), and it was not so clear what is the essence of those methods or how methods proposed for individual problems are related. To remedy this situation, we formalize a general problem of analyzing resource usage as a
resource usage analysis problem
, and propose a type-based method as a solution to the problem.
Systems-on-chip needs for embedded software development
Authors: Magarshack Philippe
Published: November 2005

Increasingly, today's system-level chips include heterogeneous computing cores which can be general-purpose, signal or network processors. The function of the chip heavily depends on the software created for these processor cores. Therefore, all the concerns of traditional hardware architects or designers will fall into the responsibility of embedded software developers: real-time constraints, low-power requirements, and how to split a series of tasks into various widely different processors.Just as the processor core is integrated into the chip, software development must be integrated into the chip development flow. The implications in terms of design flow and embedded software development tools will be examined based on some actual SoC examples. The trends in the responsibilities and skills of the hardware and software developers will be analyzed and some general directions will be proposed.
Energy-conscious compilation based on voltage scaling
Authors: Saputra H. , Kandemir M. , Vijaykrishnan N. , Irwin M. J. , Hu J. S. , Hsu C-H. , Kremer U.
Published: November 2005

As energy consumption has become a majorconstraint in current system design, it is essential to look beyond the traditional low-power circuit and architectural optimizations. Further, software is becoming an increasing portion of embedded/portable systems. Consequently, optimizing the software in conjunction with the underlying low-power hardware features such as voltage scaling is vital.In this paper, we present two compiler-directed energy optimization strategies based on voltage scaling: static voltage scaling and dynamic voltage scaling. In static voltage scaling, the compiler determines a single supply voltage level for the entire input program. We primarily aim at improving the energy consumption of a given code without increasing its execution time. To accomplish this, we employ classical loop-level compiler optimizations. However, we use these optimizations to create opportunities for voltage scaling to save energy, rather than increase program performance.In dynamic voltage scaling, the compiler can select different supply voltage levels for different parts of the code. Our compilation strategy is based on integer linear programming and can accommodate energy/performance constraints. For a benchmark suite of array-based scientific codes and embedded video/image applications, our experiments show average energy savings of 31.8% when static voltage scaling is used. Our dynamic voltage scaling strategy saves 15.3% more energy than static voltage scaling when invoked under the same performance constraints.
Generic control flow reconstruction from assembly code
Authors: Kästner Daniel , Wilhelm Stephan
Published: November 2005

Processors used in embedded systems are usually characterized by specialized irregular hardware architectures for which traditional code generation and optimization techniques fail. Especially for these types of processors the
Propan
system has been developed that enables high-quality machine-dependent postpass optimizers to be generated from a concise hardware specification. Optimizing code transformations as featured by
Propan
require the control flow graph of the input program to be known. The control flow reconstruction algorithm is generic, i.e. machine-independent, and automatically derives the required hardware-specific knowledge from the machine specification. The reconstruction is based on an extended program slicing mechanism and is tailored to assembly programs. It has been retargeted to assembly programs of two contemporary microprocessors, the Analog Devices SHARC and the Philips TriMedia TM1000. Experimental results show that the assembly-based slicing enables the control flow graph of large assembly programs to be constructed in short time. Our experiments also demonstrate that the hardware design significantly influences the precision of the control flow reconstruction and the required computation time.
Efficient register and memory assignment for non-orthogonal architectures via graph coloring and MST algorithms
Authors: Cho Jeonghun , Paek Yunheung , Whalley David
Published: November 2005

Finding an optimal assignment of program variables into registers and memory is prohibitively difficult in code generation for
application specific instruction-set processors
(ASIPs). This is mainly because, in order to meet stringent speed and power requirements for embedded applications, ASIPs commonly employ
non-orthogonal
architectures which are typically characterized by irregular data paths, heterogeneous registers and multiple memory banks. As a result, existing techniques mainly developed for relatively regular, orthogonal
general-purpose processors
(GPPs) are obsolete for these recently emerging ASIP architectures. In this paper, we attempt to tackle this issue by exploiting conventional
graph coloring
and
maximum spanning tree
(MST) algorithms with special constraints added to handle the non-orthogonality of ASIP architectures. The results in our study indicate that our algorithm finds a fairly good assignment of variables into heterogeneous registers and multi-memories while it runs extremely faster than previous work that employed exceedingly expensive algorithms to address this issue.
Proxy compilation of dynamically loaded Java classes with MoJo
Authors: Newsome Matt , Watson Des
Published: November 2005

Interest in Java implementations for resource-constrained environments such as embedded systems has been tempered by concerns regarding its efficiency. Current native compilers for Java offer dramatic increases in efficiency, but have poor support for dynamically-loaded classes, which are typically served by slow interpreters or JIT compilers, the code-size of this latter utterly mismatching the resource constraints of the system.After a brief survey of Ahead-of-Time compilers for Java, we present MoJo --- a new native compiler and the testbed for our proxy compilation scheme, which allows embedded clients to connect to servers and delegate compilation of Java class packages to native code libraries.We also present initial results from experimental testing using MoJo in a resource-constrained, mobile computing environment. We show that MoJo is faster than all surveyed Java implementations for the test platform executing our initial test application. Our proxy compilation scheme results in a 94% speed increase over the fastest tested interpreter system and a 20% speed increase over the fastest tested JIT system.The MoJo-generated binaries for the application are also shown to be 45 times smaller than those required by its nearest iPAQ JRE competitor and 275 times smaller than the Sun JRE v1.3.1 for iPAQ as a direct result of our incremental, on-demand transfer of API classes to the client.
Perfecting preemption threshold scheduling for object-oriented real-time system design
Authors: Kim Saehwa , Hong Seongsoo , Kim Tae-Hyung
Published: November 2005

In spite of the proliferation of object-oriented design methodologies in contemporary software development, their application to real-time embedded systems has been limited because of the practitioner's conservative attitude toward handling timing constraints. In fact, this conservative attitude is well-grounded because traditional priority-based scheduling techniques cannot be straightforwardly integrated into them. The automated implementation from the object-oriented real-time designs usually incurs a large number of tasks which, under traditional priority-based scheduling techniques, does not scale well due to excessive preemption overheads. Recently, preemption threshold scheduling was introduced to reduce run-time multi-tasking overhead while improving schedulability by exploiting non-preemptibility as much as possible. Unfortunately, the preemption threshold scheduling cannot be directly adopted into the object-oriented design methods due to the lack of real-time synchronization.In this paper, we present the essential basis of real-time synchronization for preemption threshold scheduling. Specifically, we integrate the priority inheritance protocol, the priority ceiling protocol, and the immediate inheritance protocol into preemption threshold scheduling. We also provide their schedulability analyses. Consequently, the integrated scheme, which minimizes worst-case context switches, is appropriate for the automated implementation of real-time object-oriented design models.
Reference idempotency analysis
Authors: Kim Seon Wook , Ooi Chong-liang , Eigenmann Rudolf , Falsafi Babak , Vijaykumar T. N.
Published: November 2005

Recent proposals for multithreaded architectures allow threads with unknown dependences to execute speculatively in parallel. These architectures use hardware
speculative storage
to buffer uncertain data, track data dependences and roll back incorrect executions. Because
all
memory references access the speculative storage, current proposals implement this storage using small memory structures for fast access. The limited capacity of the speculative storage causes considerable performance loss due to
speculative storage overflow
whenever a thread's speculative state exceeds the storage capacity. Larger threads exacerbate the overflow problem but are preferable to smaller threads, as larger threads uncover more parallelism.

In this paper, we discover a new program property called memory
reference idempotency
. Idempotent references need not be tracked in the speculative storage, and instead can directly access non-speculative storage (i.e., the conventional memory hierarchy). Thus, we reduce the demand for speculative storage space. We define a formal framework for reference idempotency and present a novel compiler-assisted speculative execution model. We prove the necessary and sufficient conditions for reference idempotency using our model. We present a compiler algorithm to label idempotent memory references for the hardware. Experimental results show that for our benchmarks, over 60% of the references in non-parallelizable program sections are idempotent.
Efficient load balancing for wide-area divide-and-conquer applications
Authors: van Nieuwpoort Rob V. , Kielmann Thilo , Bal Henri E.
Published: November 2005

Divide-and-conquer programs are easily parallelized by letting the programmer annotate potential parallelism in the form of
spawn
and
sync
constructs. To achieve efficient program execution, the generated work load has to be balanced evenly among the available CPUs. For single cluster systems,
Random Stealing
(RS) is known to achieve optimal load balancing. However, RS is inefficient when applied to hierarchical wide-area systems where multiple clusters are connected via wide-area networks (WANs) with high latency and low bandwidth.

In this paper, we experimentally compare RS with existing load-balancing strategies that are believed to be efficient for multi-cluster systems,
Random Pushing
and two variants of
Hierarchical Stealing
. We demonstrate that, in practice, they obtain less than optimal results. We introduce a novel load-balancing algorithm,
Cluster-aware Random Stealing
(CRS) which is highly efficient and easy to implement. CRS adapts itself to network conditions and job granularities, and does not require manually-tuned parameters. Although CRS sends more data across the WANs, it is faster than its competitors for 11 out of 12 test applications with various WAN configurations. It has at most 4% overhead in run time compared to RS on a single, large cluster, even with high wide-area latencies and low wide-area bandwidths. These strong results suggest that divide-and-conquer parallelism is a useful model for writing distributed supercomputing applications on hierarchical wide-area systems.
Scalable queue-based spin locks with timeout
Authors: Scott Michael L. , Scherer William N.
Published: November 2005

Queue-based spin locks allow programs with busy-wait synchronization to scale to very large multiprocessors, without fear of starvation or performance-destroying contention. So-called
try locks
, traditionally based on non-scalable test-and-set locks, allow a process to abandon its attempt to acquire a lock after a given amount of time. The process can then pursue an alternative code path, or yield the processor to some other process.

We demonstrate that it is possible to obtain both scalability and bounded waiting, using variants of the queue-based locks of Craig, Landin, and Hagersten, and of Mellor-Crummey and Scott. A process that decides to stop waiting for one of these new locks can ``link itself out of line'' atomically. Single-processor experiments reveal performance penalties of 50--100\% for the CLH and MCS try locks in comparison to their standard versions; this marginal cost decreases with larger numbers of processors.

We have also compared our queue-based locks to a traditional \tatas\ lock with exponential backoff and timeout. At modest (non-zero) levels of contention, the queued locks sacrifice cache locality for fairness, resulting in a worst-case 3X performance penalty. At high levels of contention, however, they display a 1.5--2X performance
advantage
, with significantly more regular timings and significantly higher rates of acquisition prior to timeout.
High-level adaptive program optimization with ADAPT
Authors: Voss Michael J. , Eigemann Rudolf
Published: November 2005

Compile-time optimization is often limited by a lack of target machine and input data set knowledge. Without this information, compilers may be forced to make conservative assumptions to preserve correctness and to avoid performance degradation. In order to cope with this lack of information at compile-time, adaptive and dynamic systems can be used to perform optimization at runtime when complete knowledge of input and machine parameters is available. This paper presents a compiler-supported high-level adaptive optimization system. Users describe, in a domain specific language, optimizations performed by stand-alone optimization tools and backend compiler flags, as well as heuristics for applying these optimizations dynamically at runtime. The ADAPT compiler reads these descriptions and generates application-specific runtime systems to apply the heuristics. To facilitate the usage of existing tools and compilers, overheads are minimized by decoupling optimization from execution. Our system, ADAPT, supports a range of paradigms proposed recently, including dynamic compilation, parameterization and runtime sampling. We demonstrate our system by applying several optimization techniques to a suite of benchmarks on two target machines. ADAPT is shown to consistently outperform statically generated executables, improving performance by as much as 70%.
LogGPS
Authors: Ino Fumihiko , Fujimoto Noriyuki , Hagihara Kenichi
Published: November 2005

We present a new parallel computational model, named LogGPS, which captures synchronization.

The LogGPS model is an extension of the LogGP model, which abstracts communication on parallel platforms. Although the LogGP model captures long messages with one bandwidth parameter (
G
), it does not capture synchronization that is needed before sending a long message by high-level communication libraries. Our model has one additional parameter,
S
, defined as the threshold for message length, above which synchronous messages are sent.

We also present some experimental results using both models. The results include (1) a verification of the LogGPS model, (2) an example of synchronization analysis using an MPI program and (3) a comparison of the models. The results indicate that the LogGPS model is more accurate than the LogGP model, and analyzing synchronization costs is important when improving parallel program performance.
Comments on “the law of demeter” and C++
Authors: Sakkinen M.
Published: November 2005

A rule of good style for object-oriented programming has recently been put forward, actually in several flavours (class vs. object, weak vs. strong). Some possible problems in the original rule are discussed, and a modified formulation is proposed to overcome at least part of the them. Doubts still remain about how useful the rule is with Smalltalk and other
untyped
languages. Then the application of the rule to the C++ language is studied and shown not to be as straightforward as has been suggested. This is largely a consequence of the intertwining of the conventional and the object-oriented component in C++. On the other hand, being typed, it is a promising language for enforcing rules of this kind at compile time. A new language-specific formulation is finally presented, argumenting that it is better in class than object flavour.
Monads for incremental computing
Authors: Carlsson Magnus
Published: November 2005

This paper presents a monadic approach to incremental computation, suitable for purely functional languages such as Haskell. A program that uses incremental computation is able to perform an incremental amount of computation to accommodate for changes in input data. Recently, Acar, Blelloch and Harper presented a small Standard ML library that supports efficient, high-level incremental computations [1]. Here, we present a monadic variant of that library, written in Haskell extended with first-class references. By using monads, not only are we able to provide a purely functional interface to the library, the types also enforce "correct usage" without having to resort to any type-system extension. We also find optimization opportunities based on standard monadic combinators.This is an exercise in putting to work monad transformers with environments, references, and continuations.
Contracts for higher-order functions
Authors: Findler Robert Bruce , Felleisen Matthias
Published: November 2005

Assertions play an important role in the construction of robust software. Their use in programming languages dates back to the 1970s. Eiffel, an object-oriented programming language, wholeheartedly adopted assertions and developed the "Design by Contract" philosophy. Indeed, the entire object-oriented community recognizes the value of assertion-based contracts on methods.In contrast, languages with higher-order functions do not support assertion-based contracts. Because predicates on functions are, in general, undecidable, specifying such predicates appears to be meaningless. Instead, the functional languages community developed type systems that statically approximate interesting predicates.In this paper, we show how to support higher-order function contracts in a theoretically well-founded and practically viable manner. Specifically, we introduce λ

con

, a typed lambda calculus with assertions for higher-order functions. The calculus models the assertion monitoring system that we employ in DrScheme. We establish basic properties of the model (type soundness, etc.) and illustrate the usefulness of contract checking with examples from DrScheme's code base.We believe that the development of an assertion system for higher-order functions serves two purposes. On one hand, the system has strong practical potential because existing type systems simply cannot express many assertions that programmers would like to state. On the other hand, an inspection of a large base of invariants may provide inspiration for the direction of practical future type system research.
An interoperable calculus for external object access
Authors: Ohori Atsushi , Yamatodani Kiyoshi
Published: November 2005

By extending an ML-style type system with record polymorphism, recursive type definition, and an ordering relation induced by field inclusion, it is possible to achieve seamless and type safe interoperability with an object-oriented language. Based on this observation, we define a polymorphic language that can directly access external objects and methods, and develop a type inference algorithm. This calculus enjoys the features of both higher-order programming with ML polymorphism and class-based object-oriented programming with dynamic method dispatch. To establish type safety, we define a sample object-oriented language with multiple inheritance as the target for interoperability, define an operational semantics of the calculus, and show that the type system is sound with respect to the operational semantics. These results have been implemented in our prototype interpretable language, which can access Java class files and other external resources.
A demand-driven adaptive type analysis
Authors: Dubé Danny , Feeley Marc
Published: November 2005

Compilers for dynamically and statically typed languages ensure safe execution by verifying that all operations are performed on appropriate values. An operation as simple as
car
in Scheme and
hd
in SML will include a run time check unless the compiler can prove that the argument is always a non-empty list using some type analysis. We present a demand-driven type analysis that can adapt the precision of the analysis to various parts of the program being compiled. This approach has the advantage that the analysis effort can be spent where it is justified by the possibility of removing a run time check, and where added precision is needed to accurately analyze complex parts of the program. Like the
k
-cfa our approach is based on abstract interpretation but it can analyze some important programs more accurately than the
k
-cfa for any value of
k
. We have built a prototype of our type analysis and tested it on various programs with higher order functions. It can remove all run time type checks in some nontrivial programs which use
map
and the Y combinator.
Exception analysis for non-strict languages
Authors: Glynn Kevin , Stuckey Peter J. , Sulzmann Martin , Søndergaard Harald
Published: November 2005

In this paper we present the first exception analysis for a non-strict language. We augment a simply-typed functional language with exceptions, and show that we can define a type-based inference system to detect uncaught exceptions. We have implemented this exception analysis in the GHC compiler for Haskell, which has been recently extended with exceptions. We give empirical evidence that the analysis is practical.
Interactive visual functional programming
Authors: Hanna Keith
Published: November 2005

An interactive graphical environment for supporting the development and use of Haskell applications programs is described. The environment, named Vital, is particularly intended for supporting the open-ended, incremental development style often preferred by non-specialist users in which successive steps of program development are motivated and informed by results so far obtained.Significant features of Vital include: the graphical display of data structures in a format defined by a datatype-indexed stylesheet, the way that evaluation of (possibly infinite) values is demand-driven by the action of the user scrolling around an unbounded workspace, and support for copy-and-paste graphical editing of data structures. This latter allows, for example, the user to modify a complex data structure by point-and-click operations, or to create (by functional evaluation) a regular data structure and then edit values or expressions into it. The effect of each editing operation is immediately reflected in the Haskell program source code.
Tagless staged interpreters for typed languages
Authors: PašaliΕ Emir , Taha Walid , Sheard Tim
Published: November 2005

Multi-stage programming languages provide a convenient notation for explicitly staging programs. Staging a definitional interpreter for a domain specific language is one way of deriving an implementation that is both readable and efficient. In an untyped setting, staging an interpreter "removes a complete layer of interpretive overhead", just like partial evaluation. In a typed setting however, Hindley-Milner type systems do not allow us to exploit typing information in
the language being interpreted
. In practice, this can mean a slowdown cost by a factor of three or mor.Previously, both type specialization and tag elimination were applied to this problem. In this paper we propose an alternative approach, namely, expressing the definitional interpreter in a dependently typed programming language. We report on our experience with the issues that arise in writing such an interpreter and in designing such a language. .To demonstrate the soundness of combining staging and dependent types in a general sense, we formalize our language (called Meta-D) and prove its type safety. To formalize Meta-D, we extend Shao, Saha, Trifonov and Papaspyrou's λH language to a multi-level setting. Building on λH allows us to demonstrate type safety in a setting where the type language contains all the calculus of inductive constructions, but without having to repeat the work needed for establishing the soundness of that system.
There and back again
Authors: Danvy Olivier , Goldberg Mayer
Published: November 2005

We present a programming pattern where a recursive function traverses a data structure---typically a list---at return time. The idea is that the recursive calls get us there (typically to a base case) and the returns get us back again
while traversing the data structure
. We name this programming pattern of traversing a data structure at return time "There And Back Again" (TABA).The TABA pattern directly applies to computing a symbolic convolution. It also synergizes well with other programming patterns, e.g., dynamic programming and traversing a list at double speed. We illustrate TABA and dynamic programming with Catalan numbers. We illustrate TABA and traversing a list at double speed with palindromes and we obtain a novel solution to this traditional exercise.A TABA-based function written in direct style makes full use of an Algol-like control stack and needs no heap allocation. Conversely, in a TABA-based function written in continuation-passing style, the continuation acts as a list iterator. In general, the TABA pattern saves one from constructing intermediate lists in reverse order.
An experimental study of renewal-older-first garbage collection
Authors: Hansen Lars T. , Clinger William D.
Published: November 2005

Generational collection has improved the efficiency of garbage collection in fast-allocating programs by focusing on collecting young garbage, but has done little to reduce the cost of collecting a heap containing large amounts of older data. A new generational technique, older-first collection, shows promise in its ability to manage older data.This paper reports on an implementation study that compared two older-first collectors to traditional (younger-first) generational collectors. One of the older-first collectors performed well and was often effective at reducing the first-order cost of collection relative to younger-first collectors. Older-first collectors perform especially well when objects have queue-like or random lifetimes.
Final shift for call/cc:
Authors: Gasbichler Martin , Sperber Michael
Published: November 2005

We present a direct implementation of the
shift
and
reset
control operators in the
SFE
system. The new implementation improves upon the traditional technique of simulating
shift
and
reset
via
callcc
. Typical applications of these operators exhibit space savings and a significant overall performance gain. Our technique is based upon the popular incremental stack/heap strategy for representing continuations. We present implementation details as well as some benchmark measurements for typical applications.
BuddyCache
Authors: Bjornsson Magnus E. , Shrira Liuba
Published: November 2005

Collaborative applications provide a shared work environment for groups of networked clients collaborating on a common task. They require strong consistency for shared persistent data and efficient access to fine-grained objects. These properties are difficult to provide in wide area networks because of high network latency.
BuddyCache
is a new transactional caching approach that improves the latency of access to shared persistent objects for collaborative strong-consistency applications in high-latency network environments. The challenge is to improve performance while providing the correctness and availability properties of a transactional caching protocol in the presence of node failures and slow peers.We have implemented a BuddyCache prototype and evaluated its performance. Analytical results, confirmed by measurements of the BuddyCache prototype using the multi-user 007 benchmark indicate that for typical Internet latencies, e.g. ranging from 40 to 80 milliseconds round trip time to the storage server, peers using BuddyCache can reduce by up to 50% the latency of access to shared objects compared to accessing the remote servers directly.
Workflow enactment with continuation and future objects
Authors: Manolescu Dragos A.
Published: November 2005

An increasing number of software developers are turning to workflow to separate the logic and the control aspects in their applications, thus making them more amenable to change. However, in spite of recent efforts to standardize and provide reusable workflow components, many developers build their own. This is a challenging endeavor and involves solving problems which seem incompatible with the object paradigm and current object-oriented programming languages. In the context of an object-oriented workflow framework, this paper demonstrates a novel approach that resolves this impedance mismatch with techniques drawn from programming language theory. This successful cross-pollination narrows the gap between the results of decades of research in programming languages and developers working hard to cope with change.
Portable serialization of CORBA objects
Authors: Killijian Marc-Olivier , Ruiz Juan-Carlos , Fabre Jean-Charles
Published: November 2005

The objective of this work is to define, implement and illustrate a portable serialization technique for CORBA objects. We propose an approach based on reflection: through open compilers facilities the internal state of CORBA objects is obtained and transformed into a language independent format using CORBA mechanisms. This state can be restored and used by objects developed using different languages and running on different software platforms. A tool was developed and applied to a Chat application as a case study. The proposed technique is used to exchange state information between a C++ and a Java incarnation of this CORBA service. An observer tool enables the object state to be displayed and analyzed by the user. The applicability of this technique to various domains is discussed. Beyond the interest of language reflection, we finally advocate that operating system and middleware reflection would also be powerful concepts to extend the work presented in this paper.
Online feedback-directed optimization of Java
Authors: Arnold Matthew , Hind Michael , Ryder Barbara G.
Published: November 2005

This paper describes the implementation of an online feedback-directed optimization system. The system is fully automatic; it requires no prior (offline) profiling run. It uses a previously developed low-overhead instrumentation sampling framework to collect control flow graph edge profiles. This profile information is used to drive several traditional optimizations, as well as a novel algorithm for performing feedback-directed control flow graph node splitting. We empirically evaluate this system and demonstrate improvements in peak performance of up to 17% while keeping overhead low, with no individual execution being degraded by more than 2% because of instrumentation.
An analyzable annotation language
Authors: Khurshid Sarfraz , Marinov Darko , Jackson Daniel
Published: November 2005

The Alloy Annotation Language (AAL) is a language (under development) for annotating Java code based on the Alloy modeling language. It offers a syntax similar to the Java Modeling Language (JML), and the same opportunities for generation of run-time assertions. In addition, however, AAL offers the possibility of fully automatic compile-time analysis. Several kinds of analysis are supported, including: checking the code of a method against its specification; checking that the specification of a method in a subclass is compatible with the specification in the superclass; and checking properties relating method calls on different objects, such as that the equals methods of a class (and its overridings) induce an equivalence. Using partial models in place of code, it is also possible to analyze object-oriented designs in the abstract: investigating, for example, a view relationship amongst objects.The paper gives examples of annotations and such analyses. It presents (informally) a systematic translation of annotations into Alloy, a simple first-order logic with relational operators. By doing so, it makes Alloy's automatic analysis, which is based on state-of-the-art SAT solvers, applicable to the analysis of object-oriented programs, and demonstrates the power of a simple logic as the basis for an annotation language.
Ownership, encapsulation and the disjointness of type and effect
Authors: Clarke Dave , Drossopoulou Sophia
Published: November 2005

Ownership types provide a statically enforceable notion of object-level encapsulation. We extend ownership types with computational effects to support reasoning about object-oriented programs. The ensuing system provides both access control and effects reporting. Based on this type system, we codify two formal systems for reasoning about aliasing and the disjointness of computational effects. The first can be used to prove that evaluation of two expressions will never lead to aliases, while the latter can be used to show the non-interference of two expressions.
Alias annotations for program understanding
Authors: Aldrich Jonathan , Kostadinov Valentin , Chambers Craig
Published: November 2005

One of the primary challenges in building and evolving large object-oriented systems is understanding aliasing between objects. Unexpected aliasing can lead to broken invariants, mistaken assumptions, security holes, and surprising side effects, all of which may lead to software defects and complicate software evolution.This paper presents AliasJava, a capability-based alias annotation system for Java that makes alias patterns explicit in the source code, enabling developers to reason more effectively about the interactions in a complex system. We describe our implementation, prove the soundness of the annotation system, and give an algorithm for automatically inferring alias annotations. Our experience suggests that the annotation system is practical, that annotation inference is efficient and yields appropriate annotations, and that the annotations can express important invariants of data structures and of software architectures.
Access rights analysis for Java
Authors: Koved Larry , Pistoia Marco , Kershenbaum Aaron
Published: November 2005

Java 2 has a security architecture that protects systems from unauthorized access by mobile or statically configured code. The problem is in manually determining the set of security access rights required to execute a library or application. The commonly used strategy is to execute the code, note authorization failures, allocate additional access rights, and test again. This process iterates until the code successfully runs for the test cases in hand. Test cases usually do not cover all paths through the code, so failures can occur in deployed systems. Conversely, a broad set of access rights is allocated to the code to prevent authorization failures from occurring. However, this often leads to a violation of the "Principle of Least Privilege"This paper presents a technique for computing the access rights requirements by using a context sensitive, flow sensitive, interprocedural data flow analysis. By using this analysis, we compute at each program point the set of access rights required by the code. We model features such as multi-threading, implicitly defined security policies, the semantics of the Permission.implies method and generation of a security policy description. We implemented the algorithms and present the results of our analysis on a set of programs. While the analysis techniques described in this paper are in the context of Java code, the basic techniques are applicable to access rights analysis issues in non-Java-based systems.
Language-specific make technology for the Java programming language
Authors: Dmitriev Mikhail
Published: November 2005

Keeping the code of a Java application consistent (code is consistent if all of the project classes can be recompiled together without errors) prevents late linking errors, and thus may significantly improve development turnaround time. In this paper we describe a make technology for the Java programming language, that is based on smart dependency checking, guarantees consistency of the project code, and at the same time reduces the number of source code recompilations to the minimum. After project code consistency is initially assured by complete recompilation, the information extracted from the binary classes is stored in a so-called project database. Whenever the source code for some class C is changed, its recompiled binary is compared to the old version of C preserved in the project database. As a result, we find a minimum subset of classes that depend on C and may be affected by the particular change made to it. These are recompiled in turn, and absence of compilation errors at this phase guarantees the consistency of the new project code. To determine which dependent classes to recompile, we categorize all source incompatible changes, and for each category establish a criterion for finding the smallest possible subset of dependent classes.
Architecture and design of adaptive object-models
Authors: Yoder Joseph W. , Balaguer Federico , Johnson Ralph
Published: November 2005

Many object-oriented information systems share an architectural style that emphasizes flexibility and run-time adaptability. Business rules are stored externally to the program such as in a database or XML files instead of in code. The object model that the user cares about is part of the database, and the object model of the code is just an interpreter of the users' object model. We call these systems "Adaptive Object-Models", because the users' object model is interpreted at runtime and can be changed with immediate (but controlled) effects on the system interpreting it. The real power in Adaptive Object-Models is that they have a definition of a domain model and rules for its integrity and can be configured by domain experts external to the execution of the program. This paper describes the Adaptive Object-Model architecture along with its strengths and weaknesses. It illustrates the Adaptive Object-Model architectural style by describing a framework for Medical Observations (following Fowler's Analysis Patterns) that we built.
An overview of methods for dependence analysis of concurrent programs
Authors: Chen Zhenqiang , Xu Baowen , Zhao Jianjun
Published: November 2005

Program dependence analysis is an analysis technique to identify and determine various program dependencies in source codes, which has been widely used in program understanding, debugging, testing, reverse engineering, and maintenance. However, there are still many difficulties to be solved when carrying out dependence analysis for concurrent programs because the execution of statements is unpredictable. This survey describes methods and research directions for dependence analysis of concurrent programs, especially about how to obtain the dependencies between concurrently executed statements, the factors leading to intransitivity among dependencies, and how to deal with the intransitivity problem. By careful comparisons, users can select a proper algorithm for their requirements.
Temporally silent stores
Authors: Lepak Kevin M. , Lipasti Mikko H.
Published: November 2005

Recent work has shown that silent stores--stores which write a value matching the one already stored at the memory location--occur quite frequently and can be exploited to reduce memory traffic and improve performance. This paper extends the definition of silent stores to encompass sets of stores that change the value stored at a memory location, but only temporarily, and subsequently return a previous value of interest to the memory location. The stores that cause the value to revert are called temporally silent stores. We redefine multiprocessor sharing to account for temporal silence and show that in the limit, up to 45% of communication misses in scientific and commercial applications can be eliminated by exploiting values that change only temporarily. We describe a practical mechanism that detects temporally silent stores and removes the coherence traffic they cause in conventional multiprocessors. We find that up to 42% of communication misses can be eliminated with a simple extension to the MESI protocol. Further, we examine application and operating system code to provide insight into the temporal silence phenomenon and characterize temporal silence by examining value frequencies and dynamic instruction distances between temporally silent pairs. These studies indicate that the operating system is involved heavily in temporal silence, in both commercial and scientific workloads, and that while detectable synchronization primitives provide substantial contributions, significant opportunity exists outside these references.
Maté
Authors: Levis Philip , Culler David
Published: November 2005

Composed of tens of thousands of tiny devices with very limited resources ("motes"), sensor networks are subject to novel systems problems and constraints. The large number of motes in a sensor network means that there will often be some failing nodes; networks must be easy to repopulate. Often there is no feasible method to recharge motes, so energy is a precious resource. Once deployed, a network must be reprogrammable although physically unreachable, and this reprogramming can be a significant energy cost.We present Maté, a tiny communication-centric virtual machine designed for sensor networks. Maté's high-level interface allows complex programs to be very short (under 100 bytes), reducing the energy cost of transmitting new programs. Code is broken up into small capsules of 24 instructions, which can self-replicate through the network. Packet sending and reception capsules enable the deployment of ad-hoc routing and data aggregation algorithms. Maté's concise, high-level program representation simplifies programming and allows large networks to be frequently reprogrammed in an energy-efficient manner; in addition, its safe execution environment suggests a use of virtual machines to provide the user/kernel boundary on motes that have no hardware protection mechanisms.
Enabling trusted software integrity
Authors: Kirovski Darko , Drinić Milenko , Potkonjak Miodrag
Published: November 2005

Preventing execution of unauthorized software on a given computer plays a pivotal role in system security. The key problem is that although a program at the beginning of its execution can be verified as authentic, while running, its execution flow can be redirected to externally injected malicious code using, for example, a buffer overflow exploit. Existing techniques address this problem by trying to detect the intrusion at run-time or by formally verifying that the software is not prone to a particular attack.We take a radically different approach to this problem. We aim at intrusion prevention as the core technology for enabling secure computing systems. Intrusion prevention systems force an adversary to solve a computationally hard task in order to create a binary that can be executed on a given machine. In this paper, we present an exemplary system--SPEF--a combination of architectural and compilation techniques that ensure software integrity at run-time. SPEF embeds encrypted, processor-specific constraints into each block of instructions at software installation time and then verifies their existence at run-time. Thus, the processor can execute only properly installed programs, which makes installation the only system gate that needs to be protected. We have designed a SPEF prototype based on the ARM instruction set and validated its impact on security and performance using the MediaBench suite of applications.