21985459
Safety and Security Analysis of Object-Oriented Models
In this paper we review existing approaches for the safety and security analysis of object-oriented software designs, and identify ways in which these approaches can be improved and made more rigorous.
12745557
Safety of Strictness Analysis via Term Graph Rewriting
A safe abstraction is presented for a restricted form of term graph rewriting. This abstraction can be seen as a formalisation of the rewrite system employed by the strictness analyser in the Concurrent Clean compiler. Programs written in a core functional language are interpreted as graph rewriting systems using a form of equational term graph rewriting due to Ariola and Arvind. Abstract graphs are defined by extending the signature of ordinary graphs and it is shown how to extend a rewriting system on ordinary graphs to one on abstract graphs. An abstraction relation between abstract graphs is used to define a notion of safety with respect to a variant of Ariola and Arvind’s direct approximation semantics, and this notion of safety is shown to be adequate for strictness analysis. Abstract reduction is defined as the union of the extended rewrite system with additional ‘heuristic’ reductions and shown to be safe.
36796993
From Implicit Specifications to Explicit Designs in Reactive System Development
In this paper we describe how the RSDS method can be used as a bridge between implicit Z-style specifications of reactive systems, and explicit B AMN designs of these systems. We define the translation from RSDS to B and verify its correctness. We also define controller decomposition techniques, and a translation to SMV.
2534703
Event Structures and Non-Orthogonal Term Graph Rewriting
Received 1. Abstract We show that for every term graph in a left-linear but non-orthogonal term graph rewrite system, one can construct an event structure which represents all the possible reductions which can occur in reduction sequences starting from that term graph. Every nite reduction sequence from that graph corresponds to a connguration of the event structure, and L evy-equivalent sequences correspond to the same connguration. Garbage collection is modelled in the event structure by an \erases" relation. The asymmetric connicts which arise in non-orthogonal rewrite systems are modelled by introducing a \prevents" relation. The conngurations of the event structure then form the state space of an event automaton. Taking the directed completion of this space yields a prime algebraic domain. 2. Introduction By term graph rewriting we have in mind the operational style of rewriting described in (BvEG + 87). A more elegant, algebraic approach to the semantics may be found in (Ken91). Since the arguments in the proofs in this paper are almost exclusively operational in nature we have assumed the semantics in the former. We will occasionally use notation that assumes redexes and sequences are morphisms in the category described in (KKSdV93) (as they are). This done as anotational convenience and does not assume any category theory on the part of the reader. Following the approach of the work on event structures for orthogonal term graph rewriting systems in (KKSdV93) we assume that garbage collection is not delayed and is implicit in a rewrite step. We require the left-hand sides of rules in the rewriting systems to be representations of left-linear terms and do not allow them to contain cycles; crucially we allow non-orthogonal rules. This class of term graph rewriting systems is quite general, suuciently general to be able to describe not only the functional language Clean but also languages without a functional strategy, including the abstract reduction used to do strictness analysis in Clean (see (ENP91), (Noc94)), and non-deterministic term graph rewriting. In point of fact the class we consider is more general than necessary to describe any of these since none of
2128670
Information flow for Algol-like languages
In this paper we present an approach to information flow analysis for a family of languages. We start with a simple imperative language. We present an information flow analysis using a flow logic. The paper contains detailed correctness proofs for this analysis. We next extend the analysis to a restricted form of Idealised Algol, a call-by-value higher-order extension of the simple imperative language (the key restriction being the lack of recursion). The paper concludes with a discussion of further extensions, including a probabilistic extension of Idealised Algol.
32997227
Static Analysis of Value-Passing Process Calculi
5895699
Addressing reality: an architectural response to real-world demands on the evolving Internet
A system as complex as the Internet can only be designed effectively if it is based on a core set of design principles, or tenets, that identify points in the architecture where there must be common understanding and agreement. The tenets of the original Internet architecture [6] arose as a response to the technical, governmental, and societal environment of internetworking's earliest days, but have remained central to the Internet as it has evolved. In light of the increasing integration of the Internet into the social, economic, and political aspects of our lives, it is worth revisiting the underlying tenets of what is becoming a central element of the world's infrastructure.This paper examines three key tenets that we believe should guide the evolution of the Internet in its next generation and beyond. They are: design for change, controlled transparency, and the centrality of the tussle space. [8] Our purpose is not to present these ideas as new, but rather to propose that they should be elevated to central tenets of the evolving architecture of the Internet, and explore the ramifications of doing so. The paper first examines the tenets somewhat abstractly, and then in more detail by studying their relation to several design choices needed for a complete architecture. We conclude with a discussion of the relationship between the network architecture and the applications it serves.
7136114
Multipath execution: opportunities and limits
Even sophisticated branch-prediction techniques necessarily suffer some mispredictions, and even relatively small mispredict rates hurt performance substantially in current-generation processors. In this paper, we investigate schemes for improving performance in the face of imperfect branch predictors by having the processor simultaneously execute code from both the taken and not-taken outcomes of a branch. This paper presents data regarding the limits of multipath execution, considers fetch-bandwidth needs for multipath execution, and discusses various dynamic confidence-prediction schemes that gauge the likelihood of branch mispredictions. Our evaluations consider executing along several (Z-8) paths at once. Using 4 paths and a relatively simple confidence predictor, multipath execution garners speedups of up to 30% compared to the single-path case, with an average speedup of 14.4% for the SPECint suite. While associated increases in instruction-fetch-bandwidth requirements are not too surprising, a less expected result is the significance of having a separate return-address stack for each forked path. Overall, our results indicate that multipath execution offers significant improvements over single-path performance, and could be especially useful when combined with multithreading so that hardware costs can be amortized over both approaches.
14927180
Improving prediction for procedure returns with return-address-stack repair mechanisms
This paper evaluates several mechanisms for repairing the return-address stack after branch mispredictions. The return-address stack is a small but important structure for achieving better control-flow prediction accuracy and therefore better performance. But wrong-path execution after mispredictions frequently corrupts the return-address stack, making repair mechanisms necessary. If the processor implements multipath execution-simultaneously executing both sides of a branch-the contention among different paths makes the problem more severe. For conventional, single-path processors, this paper proposes saving both the top-of-stack pointer and the top-of-stack contents for later restoration in case of a misprediction. This simple technique achieves nearly 100% hit rates and improves performance by up to 8.7% compared to a stack with no repair mechanism. For multipath processors, providing each path with its own return-address stack completely eliminates contention, improving performance by over 25%.
5170042
Building and Using A Scalable Display Wall System
Princeton's scalable display wall project explores building and using a large-format display with commodity components. The prototype system has been operational since March 1998. Our goal is to construct a collaborative space that fully exploits a large-format display system with immersive sound and natural user interfaces. Our prototype system is built with low-cost commodity components: a cluster of PCs, PC graphics accelerators, consumer video and sound equipment, and portable presentation projectors. This approach has the advantages of low cost and of tracking technology well, as high-volume commodity components typically have better price-performance ratios and improve at faster rates than special-purpose hardware. We report our early experiences in building and using the display wall system. In particular, we describe our approach to research challenges in several specific research areas, including seamless tiling, parallel rendering, parallel data visualization, parallel MPEG decoding, layered multiresolution video input, multichannel immersive sound, user interfaces, application tools, and content creation.
9494191
Visualization of height field data with physical models and texture photomapping
The paper discusses a unique way to visualize height field data-the use of solid fabricated parts with a photomapped texture to display scalar information. In this process, the data in a height field are turned into a 3D solid representation through solid freeform fabrication techniques, in this case laminated object manufacturing. Next, that object is used as a 3D "photographic plate" to allow a texture image representing scalar data to be permanently mapped onto it. The paper discusses this process and how it can be used in different visualization situations.