bluuebunny/crossref_metadata_2025 huggingface dataset:
Protecting cryptographic keys and computations via virtual secure coprocessing
Authors: McGregor John P. , Lee Ruby B.
Published: November 2005

Cryptographic processing is a critical component of secure networked computing systems. The protection offered by cryptographic processing, however, greatly depends on the methods employed to manage, store, and exercise a user's cryptographic keys. In general, software-only key management schemes contain numerous security weaknesses. Thus, many systems protect keys with distributed protocols or supplementary hardware devices, such as smart cards and cryptographic coprocessors. However, these key protection mechanisms suffer from combinations of user inconvenience, inflexibility, performance penalties, and high cost.In this paper, we propose architectural enhancements for general-purpose processors that protect core secrets by facilitating virtual secure coprocessing (VSCoP). We describe modest hardware modifications and a trusted software library that allow common computing devices to perform flexible, high-performance, and protected cryptographic computation. The hardware additions include a small key store in the processor, encryption engines at the cache-memory interface, a few new instructions, and minor hardware platform modifications. With these enhancements, users can store, transport, and employ their secret keys to safely complete cryptographic operations in the presence of insecure software. In addition, we provide a foundation with which users can more securely access their secret keys on any Internet-connected computing device (that supports VSCoP) without requiring auxiliary hardware such as smart cards.
An architecture a day keeps the hacker away
Authors: Holland David A. , Lim Ada T. , Seltzer Margo I.
Published: November 2005

System security as it is practiced today is a losing battle. In this paper, we outline a possible comprehensive solution for binary-based attacks, using virtual machines, machine descriptions, and randomization to achieve broad heterogeneity at the machine level. This heterogeneity increases the "cost" of broad-based binary attacks to a sufficiently high level that they cease to become feasible. The convergence of several recent technologies appears to make our approach achievable at a reasonable cost, with only moderate run-time overhead.
Hardware support for self-healing software services
Authors: Sidiroglou Stelios , Locasto Michael E. , Keromytis Angelos D.
Published: November 2005

We propose a new approach for
reacting
to a wide variety of software failures, ranging from remotely exploitable vulnerabilities to more mundane bugs that cause abnormal program termination (
e.g.
, illegal memory dereference). Our emphasis is in creating "self-healing" software that can protect itself against a recurring fault until a more comprehensive fix is applied. Our system consists of a set of sensors that monitor applications for various types of failure and an instruction-level emulator that is invoked for selected parts of a program's code. This emulator allows us to predict recurrences of faults and recover execution to a safe control flow. Using the emulator for small pieces of code, as directed by the sensors, allows us to minimize the performance impact on the immunized application. We describe the overall system architecture, highlighting a prototype implementation for the
x86
platform. We discuss a
virtual emulator
, which uses existing and new processor features to improve performance.
A security assessment of the minos architecture
Authors: Crandall Jedidiah R. , Chong Frederic T.
Published: November 2005

Minos is a microarchitecture that implements Biba's low-water-mark integrity policy on individual words of data. Months of testing have revealed a robust system that stops attacks which corrupt control data to hijack program control flow. The low-water-mark policy is orthogonal to the memory model so that it works with existing software and middleware. The key is that Minos tracks the integrity of all data, but protects control flow by checking this integrity when a program uses the data for control transfer. Existing policies, in contrast, need to differentiate between control and non-control data
a priori.
Our implementation of Minos for Red Hat Linux 6.2 on a Pentium-based emulator is a usable Linux system on the network. We have demonstrated that Minos protects against a menagerie of real control data attacks, not just buffer overflows. This paper will detail our security assessments of Minos and other hardware and software mechanisms designed to stop the same class of attacks. We conclude that while Minos is substantially more secure than other approaches, existing C programs lack the semantic information necessary to totally secure their control flow. More details about the implementation of Minos are available in [1].
Energy-security tradeoff in a secure cache architecture against buffer overflow attacks
Authors: Inoue Koji
Published: November 2005

In this paper, we propose a cache architecture, called
SCache
, to detect buffer-overflow attacks at run time. Furthermore, the energy-security efficiency of SCache is discussed. SCache generates replica cache lines on each return-address store, and compares the original value loaded from the memory stack to the replica one on the corresponding return-address load. The number and the placement policy of the replica line strongly affect both energy and vulnerability. In our evaluation, it is observed that SCache can protect more than 99.3% of return-address loads from buffer-overflow attacks, while it increases total cache energy consumption by about 23%, compared to a well-known low-power cache.
Using instruction block signatures to counter code injection attacks
Authors: Milenković Milena , Milenković Aleksandar , Jovanov Emil
Published: November 2005

With more computing platforms connected to the Internet each day, computer system security has become a critical issue. One of the major security problems is execution of malicious injected code. In this paper we propose new processor extensions that allow execution of trusted instructions only. The proposed extensions verify instruction block signatures in run-time. Signatures are generated during a trusted installation process, using a multiple input signature register (MISR), and stored in an encrypted form. The coefficients of the MISR and the key used for signature encryption are based on a hidden processor key. Signature verification is done in the background, concurrently with program execution, thus reducing negative impact on performance. The preliminary results indicate that the proposed processor extensions will prevent execution of any unauthorized code at a relatively small increase in system complexity and execution time.
ChipLock
Authors: Kgil Taeho , Falk Laura , Mudge Trevor
Published: November 2005

The increasing need for security has caused system designers to consider placing some security support directly at the hardware level. In fact, this is starting to emerge as an important consideration in processor design, because the performance overhead of supporting security in hardware is usually significantly lower than a complete software solution. In this paper, we investigate integrating some security support into hardware. We show that security support can be added at some acceptable cost in area and performance. We propose a processor extension called ChipLock. It provides hardware security support for a mostly untrusted operating system to ensure the integrity and confidentiality of all computational results. ChipLock's modular design can be easily integrated into existing hardware platforms with only slight modification to the operating system. ChipLock includes a built-in hardware Key Manager that supports symmetric key assignment, and a read-only-memory, TrustROM, that executes secure hardware routines. The software required is a small trusted portion of the operating system called Trust-Code. We modeled ChipLock's architecture on a full system simulator and showed that, for SPEC2000 benchmarks, it adds about an average of 20% to the execution time, primarily from cryptographic and verification latencies. In addition, layout studies show an area cost of about 8 mm
2
in 180 nm technology. This translates to an area overhead of 5% ~ 15% depending on the processor type.
An in-depth look at computer performance growth
Authors: Ekman Magnus , Warg Fredrik , Nilsson Jim
Published: November 2005

It is a common belief that computer performance growth is over 50% annually, or that performance doubles every 18-20 months. By analyzing publicly available results from the SPEC integer (CINT) benchmark suites, we conclude that this was true between 1985 and 1996 -- the early years of the RISC paradigm.During the last 7.5 years (1996-2004), however, performance growth has slowed down to 41%, with signs of a continuing decline. Meanwhile, clock frequency has improved with about 29% annually. The improvement in clock frequency was enabled both by an annual device speed scaling of 20% as well as by longer pipelines with a lower gate-depth in each stage. This paper takes a fresh look at -- and tries to remove the confusion about -- performance scaling that exists in the computer architecture community.
Internet nuggets
Authors: Thorson Mark
Published: November 2005

This column consists of selected traffic from the
comp.arch
newsgroup, a forum for discussion of computer architecture on the Internet---an international computer network.
Risks to the public
Authors: Neumann Peter G.
Published: November 2005

Edited by Peter G. Neumann (Risks Forum Moderator and Chairman of the ACM Committee on Computers and Public Policy), plus personal contributions by others, as indicated. Opinions expressed are individual rather than organizational, and all of the usual disclaimers apply. We address problems relating to software, hardware, people, and other circumstances relating to computer systems. To economize on space, we include pointers to items in the online Risks Forum: (R i j) denotes RISKS vol i number j. Cited RISKS items generally identify contributors and sources, together with URLs. Official RISKS archives are available at www.risks.org (which redirects to Newcastle and gets you nice html formatting and a search engine courtesy of Lindsay Marshall; http://catless.ncl.ac.uk/Risks/i.j.html gets you (R i j)) and at ftp://www.sri.com/risks. This issue spans (R 23 67) to (R 23 83).
BatchFlow
Authors: Kendapadi Ananth , Gandolfo Matt , Shukla Amitosh
Published: November 2005

In a typical IT division of a large enterprise, there are a significant number of batch jobs that process data in relational database systems and flat files. These jobs may range from those that are run once in a year to those that are run every hour or every few minutes. While there are many notations available to represent a relational database schema including the ER model [1], it appears that there is no good visual notation to represent the jobs themselves. To some extent, this problem can be addressed by using flowcharts, UML sequence diagrams, and operations summary matrix. However, these notations and representations do not leverage the fact that most of the operations in a batch job are usually a relational select/insert/update/delete operation on a relational table, or a read/write operation on a file. In this paper, we introduce a method and notation that we call BatchFlow. This notation can help organizations in visualizing and communicating the batch job designs at a high level.
Review of "Return on Software by Steve Tockey"; Addison Wesley, 2005
Authors: Ben-Menachem Mordechai
Published: November 2005

This book examines the issues concerning our investments in software systems and software-rich, embedded systems. As far as I can tell, every aspect of this difficult subject seems to have been covered. It is, I believe, the first time that such a book has appeared. Prof. Boehm's book is not only quite old by now; it examined economic aspects of systems from a totally different viewpoint and with different aims. A book on the economics of software has been needed for quite a long time. All analysts look at the economic aspects of what they propose to do -- if they don't they are certainly not professional; they are wasteful amateurs. However, it is unfortunately rare for this to be done well as very few technical analysts have the basic economic training to do so.
Tasking deadlocks in programs with the full Ada 95
Authors: Tojo Yasushi , Nara Sinsuke , Goto Yuichi , Cheng Jingde
Published: November 2005

This article presents some examples of tasking deadlocks concerning tasking synchronization waiting relations defined in Ada 95's Real-Time Systems Annex.
Stability of end-to-end algorithms for joint routing and rate control
Authors: Kelly Frank , Voice Thomas
Published: November 2005

Dynamic multi-path routing has the potential to improve the reliability and performance of a communication network, but carries a risk. Routing needs to respond quickly to achieve the potential benefits, but not so quickly that the network is destabilized. This paper studies how rapidly routing can respond, without compromising stability.We present a sufficient condition for the local stability of end-to-end algorithms for joint routing and rate control. The network model considered allows an arbitrary interconnection of sources and resources, and heterogeneous propagation delays. The sufficient condition we present is decentralized: the responsiveness of each route is restricted by the round-trip time of that route alone, and not by the round-trip times of other routes. Our results suggest that stable, scalable load-sharing across paths, based on end-to-end measurements, can be achieved on the same rapid time-scale as rate control, namely the time-scale of round-trip times.
A methodology for studying persistency aspects of internet flows
Authors: Wallerich Jörg , Dreger Holger , Feldmann Anja , Krishnamurthy Balachander , Willinger Walter
Published: November 2005

We focus in this paper on Internet flows, consider their contributions to the overall traffic per time unit or bin, and perform a multi-scale and multi-protocol analysis to explore the persistency properties of those flows that contribute the most (also known as "heavy hitters" or "elephants"). Knowing the persistency features (or a lack thereof) of the heavy hitters and understanding their underlying causes is crucial when developing traffic engineering tools that focus primarily on optimizing system performance for elephant flows.The main difficulty when studying the persistency properties of flows is that the available measurements are either too fine-grained to perform large-scale studies (i.e., packet-level traces) or too coarse-grained to extract the detailed information necessary for the purpose at hand (i.e., Netflow traces, SNMP). We deal with this problem by assuming that flows have constant throughput through their lifetime. We then check the validity of this assumption by comparing our Netflow-derived findings against those obtained from directly studying the corresponding detailed packet-level traces. By considering different time aggregations (e.g., bin sizes between 1--10 minutes) and flow abstractions (e.g., raw IP flows, pre-fix flows), varying the definition of what constitutes an "elephant", and slicing by different protocols and applications, we present a methodology for studying persistency aspects exhibited by Internet flows. For example, we find that raw IP flows that are elephant flows for at least once (i.e., one bin or time unit) in their lifetimes tend to show a remarkable persistence to be elephants for much of their lifetimes, but certain aggregate flows exhibit more intricate persistency properties.
From the chair
Authors: Sipior Janice C. , Schatzberg Laurie , Leidner Dorothy , Lending Diane , Vowels Susan
Published: November 2005

The ACM-SIGMIS CPR (Computer Personnel Research) 2005 Conference was a great success! This year's conference was held at the Atlanta Doubletree/Buckhead in Atlanta, Georgia USA from April 14-16, 2005, http://www.acm.org/sigmis/CPR_2005_Home_Page.htm.Look for the SIGMIS CPR 2005 Conference Proceedings in the ACM Digital Library at: http://portal.acm.org/dl.cfm.Our sincere appreciation is extended to the members of the 2005 Conference Committee for all their hard work in making this conference a success:
Conference Chair:
Mike Gallivan, Georgia State University, mgallivan@gsu.edu
Program Co-Chairs:
Jo Ellen Moore, Southern Illinois University Edwardsville, joemoor@siue.edu Susan E. Yager, Southern Illinois University Edwardsville, syager@siue.edu
Local Arrangements:
Ephraim McLean, Georgia State University, emclean@gsu.edu
Treasurer:
Laurie Schatzberg, University of New Mexico, laurie@mgt.unm.edu
Publicity:
Manju Ahuja, Indiana University Bloomington, mahuja@indiana.eduThe second annual "Magid Igbaria Outstanding Conference Paper of the Year Award" was awarded to Kelly J. Fadel and Mohan Tanniru, both of the University of Arizona, for their paper, "A Knowledge-Centric Framework for Process Redesign." Congratulations to you both!At the close of the conference, Diane Lending, CPR Committee Chair, held the third annual SIGMIS Business Meeting. Mike Gallivan, CPR 2005 Conference Chair, presented a Preliminary Outcome Report for the CPR 2005 Conference. Conrad Shayo, California State University, who is the CPR 2006 Conference Chair, provided a Progress Report for the CPR 2006 Conference. Next year's CPR 2006 Conference will be held April 13-15, 2006 in Claremont, California, USA. Please visit http://www.acm.org/sigmis/2006_CPR_Call_for_Papers.pdf or contact any member of the 2006 Conference Committee for more information:
Conference Chair:
Conrad Shayo, California State University San Bernardino, cshayo@csusb.edu
Program Co-Chairs:
Kate M. Kaiser, Marquette University, kate.kaiser@mu.edu Terry Ryan, Claremont Graduate School, terry.ryan@cgu.edu
Local Arrangements:
Seta Whitby, University of La Verne, whitbys@ulv.edu
Treasurer:
Laurie Schatzberg, University of New Mexico, laurie@mgt.unm.edu
Publicity:
Tony Coulson, California State University, San Bernardino, tcoulson@csusb.eduEveryone is welcome! Please continue to consider the ACM-SIGMIS CPR Conference and Data Base as outlets for your research and sources of information.Thank you for your continued support of SIGMIS. Please feel free to contact any one of us with suggestions or ideas to improve SIGMIS. Have a nice summer!
An empirical test of the DeLone-McLean model of information system success
Authors: Iivari Juhani
Published: November 2005

This paper tests the model of information system success proposed by DeLone and McLean using a field study of a mandatory information system. The results show that perceived system quality and perceived information quality are significant predictors of user satisfaction with the system, but not of system use. Perceived system quality was also a significant predictor of system use. User satisfaction was found to be a strong predictor of individual impact, whereas the influence of system use on individual impact was insignificant.
Individual differences and usage behavior
Authors: Burton-Jones Andrew , Hubona Geoffrey S.
Published: November 2005

A critical assumption of the Technology Acceptance Model (TAM) is that its belief constructs - perceived ease of use (PEOU) and perceived usefulness (PU) - fully mediate the influence of external variables on IT usage behavior. If this assumption is true, researchers can effectively "assume away" the effects of broad categories of external variables, those relating to the specific task, the technology, and user differences. One recent study did indeed find that belief constructs fully mediated individual differences, and its authors suggest that further studies with similar results could pave the way for simpler acceptance models that ignore such differences. To test the validity of these authors' results, we conducted a similar study to determine the effect of staff seniority, age, and education level on usage behavior. Our study involved 106 professional and administrative staff in the IT division of a large manufacturing company who voluntarily use email and word processing. We found that these individual user differences have significant direct effects on both the frequency and volume of usage. These effects are beyond the indirect effects as mediated through the TAM belief constructs. Thus, rather than corroborating the recent study, our findings underscore the importance of users' individual differences and suggest that TAM's belief constructs are accurate but incomplete predictors of usage behavior.
An architectural framework for supporting distributed object based routing
Authors: Gantsou Dhavy
Published: November 2005

TCP/IP routing protocols essentially implement distributed algorithms. Traditionally, the C and C++ programming languages have been used for implementing software supporting these protocols. Since the semantics of these languages do not provide adequate supports to cover concurrency, real-time and intrinsic properties of networking systems, protocols software are designed according to classical schemes where operating system features are extensively used to overcome C or C++ limitations. These models have served the Internet extremely well .nowadays However, as the current Internet routing system is evolving to address new requirements, so many software design methodologies. This paper shows an Ada95 technology based approach. It describes a distributed object based prototype of routing protocols.
The sets of real and complex numbers are denumerable
Authors: Ferreira Ulisses
Published: November 2005

This short article demonstrates that both the sets of real and complex numbers are actually denumerable, which means that those numeric sets, as well as the set of natural numbers, actually have the same cardinality, hence there exists a unique transfinite number.
Review of "Data Privacy and Security by David Salomon"; Spring-Verlag, 2003, $51.48, Hardcover.
Authors: Papanikolaou Nick
Published: November 2005

The field of cryptology and data security hardly needs any introduction; numerous popular accounts of the subject have appeared over the years, and it is already a core topic in undergraduate computer science. The very term "cryptology" is testimony to the long history of the field; the term is derived from the words κσνπτós (meaning hidden), and λóγos (meaning speech), which have retained their meaning in the Greek language for many centuries.
Guest column: inapproximability results via Long Code based PCPs
Authors: Khot Subhash
Published: November 2005

Summer has come again. And what better way is there to spend a summer than to relax on a sandy beach, on a mountain top, or at a park's picnic tables, and...
think theory
! Summer is a particularly good time to attack the big questions whose openness just plain annoys you. In light of Reingold's L = SL result, does L-vs.-RL tempt you? If so, take it on! (But perhaps peek first at Reingold--Trevisan--Vadhan's ECCC TR05-022.) Are you convinced that UP = NP should imply the collapse of the polynomial hierarchy? Make it so! (But if you hope to do so via showing that UP is contained in the low hierarchy, peek first at Long--Sheu's 1996 MST article.) You know that S
2
⊆ S
NP∩coNP
2
⊆ ZPP
NP
and S
NP
2
⊆ ZPP

NP
NP

, but believe that some of those "⊆"s are "=" s or are (gasp!) provably strict containments (thus giving some insight into whether recent improvements (Cai in FOCS 2001; Cai et al. in Information and Computation 2005) in the collapses of the polynomial hierarchy from assumptions that NP is in P/poly, (NP ∩ coNP)/poly, or coNP/poly are strict improvements)? Well, prove an "=" or find evidence for a strict containment... or to really make this a summer for us all to remember, prove a strict containment! Wishing you happy theorems.This article gives an overview of recent PCP constructions based on the Long Code and the inapproximability results implied by these constructions. We cover the inapproximability results for (1) MAX-3SAT and CLIQUE (2) Results for SPARSEST CUT, VERTEX COVER and MAX-CUT implied by the
Unique Games Conjecture
and (3) HYPERGRAPH VERTEX COVER and coloring problems on hypergraphs. The article aims at explaining the general framework that, loosely speaking, incorporates all the above results.
Four colors suffice!
Authors: Khuller Samir
Published: November 2005

This column is a review of the recent book "Four colors suffice" by Robin Wilson (used copies available on Amazon for $11.50) that might interest the readers of this column since its almost three decades since the result was proven by Appel and Haken.
Algorithmic problems in power management
Authors: Irani Sandy , Pruhs Kirk R.
Published: November 2005

We survey recent research that has appeared in the theoretical computer science literature on algorithmic problems related to power management. We will try to highlight some open problem that we feel are interesting. This survey places more concentration on lines of research of the authors: managing power using the techniques of speed scaling and power-down which are also currently the dominant techniques in practice.
Logical verification and equational verification
Authors: Pucella Riccardo
Published: November 2005

There were some errors in the last article of the Logic Column. Thanks to Claudia Zepeda for spotting them. They have been corrected in the online version of the article, available from the CORR archive at http://arxiv.org/abs/cs.LO/0502031. All articles published in this column are archived at CORR; the following URL will return them all: http://arxiv.org/find/grp_cs/1/ti:+AND+logic+column.
The Cambridge CAP computer and its protection system
Authors: Needham R. M. , Walker R. D.H.
Published: November 2005

This paper gives an outline of the architecture of the CAP computer as it concerns capability-based protection and then gives an account of how protected procedures are used in the construction of an operating system.
The Multics kernel design project
Authors: Schroeder Michael D. , Clark David D. , Saltzer Jerome H.
Published: November 2005

We describe a plan to create an auditable version of Multics. The engineering experiments of that plan are now complete. Type extension as a design discipline has been demonstrated feasible, even for the internal workings of an operating system, where many subtle intermodule dependencies were discovered and controlled. Insight was gained into several tradeoffs between kernel complexity and user semantics. The performance and size effects of this work are encouraging. We conclude that verifiable operating system kernels may someday be feasible.
Consistency and correctness of duplicate database systems
Authors: Ellis Clarence A.
Published: November 2005

Solutions to the duplicate database update problem are considered, and a formal validation technique using the theory of L systems is developed and applied to the problem. The paper shows some particular solutions but is primarily concerned with general properties of the problem, convenient representational techniques, and formal proof procedures which are general enough to apply to this and to a number of other problems in parallel processing and synchronization.
Synchronization with eventcounts and sequencers (Extended Abstract)
Authors: Reed David P. , Kanodia Rajendra K.
Published: November 2005

The design of computer systems to be concurrently used by multiple, independent users requires a mechanism that allows programs to synchronize their use of shared resources. Many such mechanisms have been developed and used in practical applications. Most of the currently favored mechanisms, such as semaphores and monitors are based on the concept of
mutual exclusion
.

In this paper, we describe an alternative synchronization mechanism that is not based on the concept of mutual exclusion, but rather on observing the sequencing of significant events in the course of an asynchronous computation. Two kinds of objects are described, an eventcount, which is a communication path for signalling and observing the progress of concurrent computations, and a sequencer, which assigns an order to events occurring in the system.
Automatic and general solution to the adaptation of programs in a paging environment
Authors: Babonneau J. Y. , Achard M. S. , Morisset G. , Mounajjed M. B.
Published: November 2005

The efficiency of replacement algorithms in paged virtual-storage systems depends on the locality of memory references. The restructuring of the blocks which compose the program may improve this locality. [HATFIELD and GERALD 71] [MASUDA SHIOTA NOGUCHI and OHKI 74] [FERRARI 76].

In confining this restructuring to the link-editing operation, a general and completely automatic solution has been implemented, in the form of a self-adaptative system, on the SIRIS 8 operating system. A reduction of 40 to 70% in the page fault rate has been obtained.
Effect of program localities on memory management strategies
Authors: Masuda Takashi
Published: November 2005

Programs tend to reference pages unequally and cluster references to certain pages in short time intervals. These properties depend on the tendency of program locality references and program phase transitions. The significant effects on system performances arise from the phase transition behavior. However, the phase transition behavior of programs has been rarely taken into account in the analysis of memory management strategies. This paper investigates the effect of the phase transition behavior on the total system performance. For this purpose, an elaborate simulation model of the multiprogrammed memory management has been developed for a time-sharing environment. The working set strategy and the local LRU strategy are modeled in the simulation system. A simple phase transition model and the simple LRU stack model are used as a program paging behavior model. Both cases are analyzed where (1) locality variations exist and phase transitions occur, and (2) only locality variations exist and phase transitions do not occur. The relations between the phase transition rate and the system performance are found in the above memory management strategies.
Information transmission in computational systems
Authors: Cohen Ellis
Published: November 2005

This paper presents Strong Dependency, a formalism based on an information theoretic approach to information transmission in computational systems. Using the formalism, we show how the imposition of initial constraints reduces variety in a system, eliminating undesirable information paths. In this way, protection problems, such as the Confinement Problem, may be solved. A variety of inductive techniques are developed useful for proving that such solutions are correct.
Process backup in producer-consumer systems
Authors: Russell David L.
Published: November 2005

System state restoration after detection of an error is discussed for producer-consumer systems, with emphasis on the control of the domino effect. Recovery primitives MARK, RESTORE, and PURGE are proposed that, in conjunction with the use of SEND-RECEIVE interprocess communication primitives, allow bounds to be placed on the amount of unnecessary restoration that can occur as a result of system state restoration.
Beyond concurrent Pascal
Authors: Löhr Klaus-Peter
Published: November 2005

We take the view that operating systems should not be written in assembly language. Alternatives are machine oriented high-level languages and “safe” languages in the style of Concurrent Pascal and MODULA. A serious drawback of the Concurrent Pascal approach is the fact that those very language features that pertain to operating systems must be implemented separately, using some other language. A technique is presented which solves this problem. This technique is based on user-defined trap handling. It is exhibited by demonstrating how virtual memory systems can be constructed using Concurrent Pascal and how process management can be moved from the kernel to the Concurrent Pascal program. We demonstrate that a fundamental solution of the difficulties with Concurrent Pascal, MODULA, and similar languages cannot be found in going back to classical implementation languages, but in designing languages that are not rich with special features, but powerful with respect to extension and shrinkage.
A NonStop kernel
Authors: Bartlett Joel F.
Published: November 2005

The Tandem NonStop System is a fault-tolerant [1], expandable, and distributed computer system designed expressly for online transaction processing. This paper describes the key primitives of the kernel of the operating system. The first section describes the basic hardware building blocks and introduces their software analogs: processes and messages. Using these primitives, a mechanism that allows fault-tolerant resource access, the process-pair, is described. The paper concludes with some observations on this type of system structure and on actual use of the system.
Accent
Authors: Rashid Richard F. , Robertson George G.
Published: November 2005

Accent is a communication oriented operating system kernel being built at Carnegie-Mellon University to support the distributed personal computing project, Spice, and the development of a fault-tolerant distributed sensor network (DSN). Accent is built around a single, powerful abstraction of communication between processes, with all kernel functions, such as device access and virtual memory management accessible through messages and distributable throughout a network. In this paper, specific attention is given to system supplied facilities which support transparent network access and fault-tolerant behavior. Many of these facilities are already being provided under a modified version of VAX/UNIX. The Accent system itself is currently being implemented on the Three Rivers Corp. PERQ.
Cryptographic sealing for information secrecy and authentication
Authors: Gifford David K.
Published: November 2005

The problem of computer security can be considered to consist of four distinct components:
secrecy
(ensuring that information is only disclosed to authorized users),
authentication
(ensuring that information is not forged),
integrity
(ensuring that information is not destroyed), and
availability
(ensuring that access to information can not be maliciously interrupted).

The paper describes a new protection mechanism called
cryptographic sealing
that provides primitives for secrecy and authentication. The mechanism is enforced with a synthesis of classical cryptography, public-key cryptography, and a threshold scheme.
iMAX
Authors: Kahn Kevin C. , Corwin William M. , Dennis T. Don , D'Hooge Herman , Hubka David E. , Hutchins Linda A. , Montague John T. , Pollack Fred J.
Published: November 2005

The Intel iAPX 432 is an object-based microcomputer which, together with its operating system iMAX, provides a multiprocessor computer system designed around the ideas of data abstraction. iMAX is implemented in Ada and provides, through its interface and facilities, an Ada view of the 432 system. Of paramount concern in this system is the uniformity of approach among the architecture, the operating system, and the language. Some interesting aspects of both the external and internal views of iMAX are discussed to illustrate this uniform approach.
The iMAX-432 object filing system
Authors: Pollack Fred J. , Kahn Kevin C. , Wilkinson Roy M.
Published: November 2005

iMAX is the operating system for Intel's iAPX-432 computer system. The iAPX-432
1
is an object-oriented multiprocessor architecture that supports capability-based addressing. The object filing system is that part of iMAX that implements a permanent reliable object store.

In this paper we describe the key elements of the iMAX object filing system design. We first contrast the concept of an object filing system with that of a conventional file system. We then describe the iMAX design paying particular attention to five problems that other object filing designs have either solved inadequately or failed to address. Finally, we discuss an effect of object filing on the programming semantics of Ada.
The architecture of the Eden system
Authors: Lazowska Edward D. , Levy Henry M. , Almes Guy T. , Fischer Michael J. , Fowler Robert J. , Vestal Stephen C.
Published: November 2005

The University of Washington's Eden project is a five-year research effort to design, build and use an “integrated distributed” computing environment. The underlying philosophy of Eden involves a fresh approach to the tension between these two adjectives. In briefest form, Eden attempts to support both good personal computing and good multi-user integration by combining a node machine / local network hardware base with a software environment that encourages a high degree of sharing and cooperation among its users.

The hardware architecture of Eden involves an Ethernet local area network interconnecting a number of node machines with bit-map displays, based upon the Intel iAPX 432 processor. The software architecture is object-based, allowing each user access to the information and resources of the entire system through a simple interface.

This paper states the philosophy and goals of Eden, describes the programming methodology that we have chosen to support, and discusses the hardware and kernel architecture of the system.
Grapevine
Authors: Birrell Andrew D. , Levin Roy , Needham Roger M. , Schroeder Michael D.
Published: November 2005

Grapevine is a distributed, replicated system running on a large internet within the Xerox research and development community. The internet extends from coast to coast in the USA, to Canada and to Europe, and contains more than 50 Ethernet local networks linked by leased telephone lines. Over 1500 computers are attached to the internet. Most computers are used an personal workstations, but some are used as
servers
providing access to shared facilities such as printers, large-scale secondary storage, or data bases. Computers on the internet are uniformly addressable using the
PUP
family of protocols.
How to evaluate page replacement algorithms
Authors: Kain Richard Y.
Published: November 2005

The designer of a virtual memory system can obtain accurate estimates of the average memory requirements of programs running in the system by weighting the average allocation during execution intervals with the average allocation during page waiting intervals. We show how to combine the averages, how to use the measure to determine the size of primary memory while achieving system balance between memory and processor demands, and how to partially order the performance of paging algorithms.
On protection in operating systems
Authors: Harrison Michael A. , Ruzzo Walter L. , Ullman Jeffrey D.
Published: November 2005

A model of protection mechanisms in computing systems is presented and its appropriateness is demonstrated. The “safety” problem for protection systems under our model is to determine in a given situation whether a subject can acquire a particular right to an object. In restricted cases, one can show that this problem is decidable, i.e., there is an algorithm to determine whether a system in a particular configuration is safe. In general, and under surprisingly weak assumptions, one cannot decide if a situation is safe. Various implications of this fact are discussed.
Dynamic linking and environment initialization in a multi-domain process.
Authors: Janson Philippe A.
Published: November 2005

As part of an effort to engineer a security kernel for Multics, the dynamic linker has been removed from the domain of the security kernel. The resulting implementation of the dynamic linking function requires minimal security kernel support and is consistent with the principle of least privilege. In the course of the project, the dynamic linker was found to implement not only a linking function, but also an environment initialization function for executing procedures. This report presents an analysis of dynamic linking and environment initialization in a multi-domain process, isolating three sets of functions requiring different sets of access privileges. A design based on this decomposition of the dynamic linking and environment initialization functions is presented.
The network Unix system
Authors: Chesson Gregory L.
Published: November 2005

A Network Interface Program (NIP) is that part of an operating system which interfaces with similar entities in a network. Normally, the NIP is a collection of software routines which implement interprocess communication, interhost protocols, data flow controls, and other necessary executive functions. This paper discusses the organization of the NIP currently being used with the Unix operating system on the ARPA network. The Network Unix system is noteworthy because of the natural way that network and local functions are merged. As a result the network appears as a logical extension to the local system - from the point of view of both the interactive terminal and user program.
Some constraints and tradeoffs in the design of network communications
Authors: Akkoyunlu E. A. , Ekanadham K. , Huber R. V.
Published: November 2005

A number of properties and features of interprocess communication systems are presented, with emphasis on those necessary or desirable in a network environment. The interactions between these features are examined, and the consequences of their inclusion in a system are explored. Of special interest are the time-out feature which forces all system table entries to “die of old age” after they have remained unused for some period of time, and the insertion property which states that it is always possible to design a process which may be invisibly inserted into the communication path between any two processes. Though not tied to any particular system, the discussion concentrates on distributed systems of sequential processes (no interrupts) with no system buffering.
Overview of the Hydra Operating System development
Authors: Wulf W. , Levin R. , Pierson C.
Published: November 2005

An overview of the hardware and philosophic context in which the Hydra design was done is discussed. The construction methodology is discussed together with some data which suggests the success of this methodological approach.
Scheduling partially ordered tasks with probabilistic execution times
Authors: Chandy K. M. , Reynolds P. F.
Published: November 2005

The objective of this paper is to relate models of multi-tasking in which task times are known or known to be equal to models in which task times are unknown. We study bounds on completion times and the applicability of optimal deterministic schedules to probabilistic models. Level algorithms are shown to be optimal for forest precedence graphs in which task times are independent and identically distributed exponential or Erlang random variables. A time sharing system simulation shows that multi-tasking could reduce response times and that response time is insensitive to multi-tasking scheduling disciplines.
Analysis of a level algorithm for preemptive scheduling
Authors: Lam Shui , Sethi Ravi
Published: November 2005

Muntz and Coffman give a level algorithm that constructs optimal preemptive schedules on identical processors when the task system is a tree or when there are only two processors. A variation of their algorithm is adapted for processors of different speeds. The algorithm is shown to be optimal on two processors for arbitrary task systems, but not on three or more processors even for trees. Taking the algorithm as a heuristic on m processors and using the ratio of the lengths of the constructed and optimal schedules as a measure, we show that, on identical processors, its performance is bounded by 2 - 2/m. Moreover 2 - 2/m is a best bound in that there exist task systems for which this ratio is approached arbitrarily closely. On processors of different speeds, we derive an upper bound of its performance in terms of the speeds of the given processor system and show that @@@@1.5m is an upper bound over all processor systems. We also give an example of a system for which the bound @@@@m/2 @@@@2 can be approached asymptotically, thus establishing that the @@@@1.5m bound can at most be improved by a constant factor.
Selecting a scheduling rule that meets pre-specified response time demands
Authors: Coffman E. G. , Mitrani I.
Published: November 2005

In this paper we study the problem of designing scheduling strategies when the demand on the system is known and waiting time requirements are pre-specified. This important synthesis problem has received little attention in the literature, and contrasts with the common analytical approach to the study of computer service systems. This latter approach contributes only in-directly to the problem of finding satisfactory scheduling rules when the desired (or required) response-time performance is specifiable in advance.
A comment on the confinement problem
Authors: Lipner Steven B.
Published: November 2005

The confinement problem, as identified by Lampson, is the problem of assuring that a borrowed program does not steal for its author information that it processes for a borrower. An approach to proving that an operating system enforces confinement, by preventing borrowed programs from writing information in storage in violation of a formally stated security policy, is presented. The confinement problem presented by the possibility that a borrowed program will modulate its resource usage to transmit information to its author is also considered. This problem is manifest by covert channels associated with the perception of time by the program and its author; a scheme for closing such channels is suggested. The practical implications of the scheme are discussed.
A study of program locality and lifetime functions
Authors: Denning Peter J. , Kahn Kevin C.
Published: November 2005

A program model can be regarded as decomposible into two main parts. The macromodel captures the phase-transition behavior by specifying locality sets and their associated reference intervals (phases). The micromodel captures the reference patterns within phases. A semi-Markov model can be used at the macro level, while one of the simple early models (such as the random-reference or LRU stack) can be used at the micro level. This paper shows that, even in simplest form, this type of model is capable of reproducing known properties of empirical lifetime functions. A micromodel, alone without a macromodel, is incapable of doing so.
Measurement and analysis of instruction use in the VAX-11/780
Authors: Clark Douglas W. , Levy Henry M.
Published: November 2005

This paper reports measurements of instruction set use on the VAX-11/780 computer. A hardware monitor was used to measure the frequency and time taken by each VAX instruction. Data from benchmark programs, a compiler, a linker, and a synthetic timesharing workload are reported. Results show that although some programs rely on a small set of instructions, different applications use the instruction set in different ways.
VLSI architectures for high speed recognition of context-free languages and finite-state languages
Authors: Chu King-Hang , Fu King-Sun
Published: November 2005

This paper presents two VLSI architectures for the recognition of context-free languages and finite-state languages. The architecture for context-free languages consists of n(n+1)/2 identical cells and it is capable of recognizing an input string of length n in 2n time units. The architecture for finite-state languages consists of n cells and it can recognize a string of length n in constant time. Since both architectures have characteristics such as modular layout, simple constrol and dataflow pattern, high degree of multiprocessing and/or pipelining, etc., they are very suitable for VLSI implementation.