bluuebunny/crossref_metadata_2025 huggingface dataset:
Evaluating and tuning a static analysis to find null pointer bugs
Authors: Hovemeyer David , Spacco Jaime , Pugh William
Published: February 2006

Using static analysis to detect memory access errors, such as null pointer dereferences, is not a new problem. However, much of the previous work has used rather sophisticated analysis techniques in order to detect such errors.In this paper we show that simple analysis techniques can be used to identify many such software defects, both in production code and in student code. In order to make our analysis both simple and effective, we use a non-standard analysis which is neither complete nor sound. However, we find that it is effective at finding an interesting class of software defects.We describe the basic analysis we perform, as well as the additional errors we can detect using techniques such as annotations and inter-procedural analysis.In studies of both production software and student projects, we find false positive rates of around 20% or less. In the student code base, we find that our static analysis techniques are able to pinpoint 50% to 80% of the defects leading to a null pointer exception at runtime.
Making distributed systems secure with program analysis and transformation
Authors: Myers Andrew
Published: February 2006

Building secure distributed systems is difficult, and making sure they are secure is even harder. For strong security, a variety of different mechanisms are used, such as encryption, digital signatures, access control, and replication. But once the system is built, it is difficult to know that system-level security objectives have been achieved.
Weakest-precondition of unstructured programs
Authors: Barnett Mike , Leino K. Rustan M.
Published: February 2006

Program verification systems typically transform a program into a logical expression which is then fed to a theorem prover. The logical expression represents the weakest precondition of the program relative to its specification; when (and if!) the theorem prover is able to prove the expression, then the program is considered correct. Computing such a logical expression for an imperative, structured program is straightforward, although there are issues having to do with loops and the efficiency both of the computation and of the complexity of the formula with respect to the theorem prover. This paper presents a novel approach for computing the weakest precondition of an
unstructured
program that is sound even in the presence of loops. The computation is efficient and the resulting logical expression provides more leeway for the theorem prover efficiently to attack the proof.
String analysis for x86 binaries
Authors: Christodorescu Mihai , Kidd Nicholas , Goh Wen-Han
Published: February 2006

Information about string values at key points in a program can help program understanding, reverse engineering, and forensics. We present a static-analysis technique for recovering possible string values in an executable program, when no debug information or source code is available. The result of our analysis is a regular language that describes a superset of the string values possible at a given program point. We also impart some of the lessons learned in the process of implementing our analysis as a tool for recovering C-style strings in x86 executables.
Static control-flow analysis for reverse engineering of UML sequence diagrams
Authors: Rountev Atanas , Volgin Olga , Reddoch Miriam
Published: February 2006

UML sequence diagrams are commonly used to represent the interactions among collaborating objects. Reverse-engineered sequence diagrams are constructed from existing code, and have a variety of uses in software development, maintenance, and testing. In static analysis for such reverse engineering, an open question is how to represent the intraprocedural flow of control from the code using the control-flow primitives of UML 2.0. We propose simple UML extensions that are necessary to capture general flow of control. The paper describes an algorithm for mapping a reducible exception-free intraprocedural control-flow graph to UML, using the proposed extensions. We also investigate the inherent tradeoffs of different problem solutions, and discuss their implications for reverse-engineering tools. This work is a substantial step towards providing high-quality tool support for effective and efficient reverse engineering of UML sequence diagrams.
X-gtrbac admin
Authors: Bhatti Rafae , Shafiq Basit , Bertino Elisa , Ghafoor Arif , Joshi James B. D.
Published: February 2006

The modern enterprise spans several functional units or administrative domains with diverse authorization requirements. Access control policies in an enterprise environment typically express these requirements as authorization constraints. While desirable for access control, constraints can lead to conflicts in the overall policy in a multidomain environment. The administration problem for enterprise-wide access control, therefore, not only includes authorization management for users and resources within a single domain but also conflict resolution among heterogeneous access control policies of multiple domains to allow secure interoperation within the enterprise. This work presents design and implementation of X-GTRBAC Admin, an administration model that aims at enabling administration of role-based access control (RBAC) policies in the presence of constraints with support for conflict resolution in a multidomain environment. A key feature of the model is that it allows decentralization of policy administration tasks through the abstraction of administrative domains, which not only simplifies authorization management, but is also fundamental to the concept of decentralized conflict resolution presented. The paper also illustrates the applicability of the outlined administrative concepts in a realistic enterprise environment using an implementation prototype that facilitates policy administration in large enterprises.
Access control to people location information
Authors: Hengartner Urs , Steenkiste Peter
Published: February 2006

Ubiquitous computing uses a variety of information for which access needs to be controlled. For instance, a person's current location is a sensitive piece of information that only authorized entities should be able to learn. Several challenges arise in the specification and implementation of policies controlling access to location information. For example, there can be multiple sources of location information. The sources can be within different administrative domains, which might allow different entities to specify policies, and policies need to be flexible. We address these issues in our design of a distributed access control mechanism for a people location system. Our design encodes policies as digital certificates, which enables decentralized storage of policies. We also present an algorithm for the discovery of distributed certificates. Furthermore, we discuss several privacy issues and show how our design addresses them. To show feasibility of our design, we built an example implementation based on SPKI/SDSI certificates. Using measurements, we quantify the influence of access control on query processing time. We also discuss trade-offs between RSA-based and DSA-based signature schemes for digital certificates.
Survey and taxonomy of packet classification techniques
Authors: Taylor David E.
Published: February 2006

Packet classification is an enabling function for a variety of Internet applications including quality of service, security, monitoring, and multimedia communications. In order to classify a packet as belonging to a particular flow or set of flows, network nodes must perform a search over a set of filters using multiple fields of the packet as the search key. In general, there have been two major threads of research addressing packet classification, algorithmic and architectural. A few pioneering groups of researchers posed the problem, provided complexity bounds, and offered a collection of algorithmic solutions. Subsequently, the design space has been vigorously explored by many offering new algorithms and improvements on existing algorithms. Given the inability of early algorithms to meet performance constraints imposed by high speed links, researchers in industry and academia devised architectural solutions to the problem. This thread of research produced the most widely-used packet classification device technology, Ternary Content Addressable Memory (TCAM). New architectural research combines intelligent algorithms and novel architectures to eliminate many of the unfavorable characteristics of current TCAMs. We observe that the community appears to be converging on a combined algorithmic and architectural approach to the problem. Using a taxonomy based on the high-level approach to the problem and a minimal set of running examples, we provide a survey of the seminal and recent solutions to the problem. It is our hope to foster a deeper understanding of the various packet classification techniques while providing a useful framework for discerning relationships and distinctions.
Dynamic software updating
Authors: Hicks Michael , Nettles Scott
Published: February 2006

Many important applications must run continuously and without interruption, and yet also must be changed to fix bugs or upgrade functionality. No prior general-purpose methodology for dynamic updating achieves a practical balance between flexibility, robustness, low overhead, ease of use, and low cost.We present an approach for C-like languages that provides type-safe dynamic updating of native code in an extremely flexible manner---code, data, and types may be updated, at programmer-determined times---and permits the use of automated tools to aid the programmer in the updating process. Our system is based on
dynamic patches
that contain both the updated code and the code needed to transition from the old version to the new. A novel aspect of our patches is that they consist of
verifiable native code
(e.g. Proof-Carrying Code or Typed Assembly Language), which is native code accompanied by annotations that allow online verification of the code's safety. We discuss how patches are generated mostly automatically, how they are applied using dynamic-linking technology, and how code is compiled to make it updateable.To concretely illustrate our system, we have implemented a dynamically updateable web server, FlashEd. We discuss our experience building and maintaining FlashEd, and generalize to present observations about updateable software development. Performance experiments show that for FlashEd, the overhead due to updating is low: typically less than 1 percent.
Pack wisely and remember the local voltage
Authors: Erickson Laura
Published: February 2006

In today's connected world, the wide dimensions of culture are a rich source for insights. In this Connections column, Laura Erickson gives us her viewpoints about the power of looking into cultures.---Manfred Tscheligi
To consolidate or distribute?
Authors: Johnk Linn , Manahan Meera , Graefe Tom
Published: February 2006

In large companies, the processes of user-centered design (UCD)---or as these authors say, "customer-centered design (CCD)"---may be similar across business units, but the content of the work may differ dramatically from one unit to another. Thus, like many other "minority" professions, User Experience and UCD communities struggle with how to balance full involvement in and service to their business units with coordination, professional cohesion, and leadership across business units. In this month's column, our authors discuss how they and their colleagues at Hewlett Packard have been working to strengthen their professional community across the company, while preserving the ties linking practitioners and their business units.

---Susan Dray and David Siegel
Dashboards in your future
Authors: Marcus Aaron
Published: February 2006

What's happening? What's happened? What's going to happen? Check the dashboard.
Simplifying the design and automating the verification of pipelines with structural hazards
Authors: Higgins Jason T. , Aagaard Mark D.
Published: February 2006

This article describes a technique that simplifies the design of pipelined circuits automates the specification and verification of structural-hazard and datapath correctness properties for pipelined circuits. The technique is based upon a template for pipeline stages, a control-circuit cell library, a decomposition of structural hazard and datapath correctness into a collection of simple properties, and a prototype design tool that generates verification scripts for use by external tools. Our case studies include scalar and superscalar implementations of a 32-bit OpenRISC integer microprocessor.
Instruction-level test methodology for CPU core self-testing
Authors: Shamshiri Saeed , Esmaeilzadeh Hadi , Navabi Zainalabdein
Published: February 2006

TIS is an instruction-level methodology for processor core self-testing that enhances instruction set of a CPU with test instructions. Since the functionality of test instructions is the same as the NOP instruction, NOP instructions can be replaced with test instructions. Online testing can be accomplished without any performance penalty. TIS tests different parts of the processor and detects stuck-at faults. This method can be employed in offline and online testing of single-cycle, multicycle and pipelined processors. But, TIS is more appropriate for online testing of pipelined architectures in which NOP instructions are frequently executed because of data, control and structural hazards. Running test instructions instead of these NOP instructions, TIS utilizes the time that is otherwise wasted by NOPs. In this article, two different implementations of TIS are presented. One implementation employs a dedicated hardware modules for test vector generation, while the other is a software-based approach that reads test vectors from memory. These two approaches are implemented on a pipelined processor core and their area overheads are compared. To demonstrate the appropriateness of the TIS test technique, several programs are executed and fault coverage results are presented.
Review of "DECset-8000 System User's Guide, Vol #1, #2, by Vincent Manis, Peter van den Bosch"
Authors: Abbott Russ
Published: February 2006

When it comes to designing software for people not used to dealing with computers, manufacturers of hardware are frequently the worst offenders in producing complex, inconsistent and frustrating systems. The problem is that they tend to think of all people as potential programmers. Now, a programmer, though he may grumble, will put up with almost any inconvenience thrown in his way, but a typist is not a programmer, nor is a bank clerk, nor is a journalist. Yet these people, and others in every aspect of business and industry, are expected to deal, in increasing numbers, with software designed for programmers and other members of the computer culture. They too will adjust themselves, since it is their livelihood, but they will not grumble, because they too often do not realize that matters could be better. When "the computer" makes a mistake it will afford them a moment of bitter pleasure during coffee-breaks, but in general they will feel frustrated, inadequate and oppressed, and their working lives will be made just a little more unpleasant because of it.
A statistical approach to errors in bibliographic data bases
Authors: Kuch T. D. C.
Published: February 2006

Virtually all large bibliographic data base (BDB) systems use inverted files for efficient retrieval. These files contain unique character strings found in the BDB, with the exception of stopwords such as A, AN, THE, etc. For each unique string, the number of records in which it occurs is also given.
Experimental approaches to the study of systems documentation
Authors: Kuch T. D. C.
Published: February 2006

In addition to reporting on various documentation methods and proposing new ones, I suggest that there is a need for an experimental approach to the measurement of documentation. It may be appropriate for SIGDOC, or a SIGDOC member at a university, to apply for a grant to evaluate HIPO, Autoflow, and other techniques, including combinations of techniques. In general, the experiment might take this form:1. Select a fairly small system which performs fairly simple functions, say, calculates a non-complex payroll. The system should comprise fewer than eight (or so) programs, including calls to sorts or other utility programs. The system should have been in operation long enough so that virtually all its quirks are known.2. Prepare a number of different documentation packages for the system, and present copies to test subjects, one subject per package.3. Measure: a. Time required by the subject until he claims "understanding" of the documentation; b. Number of questions the subject has about the system that were not answered by the documentation.4. Then, present the test subject with a series of problems, such as "Increase Federal tax withheld by 0.5% for each employee", or "Print the names of all employees earning less than $4 an hour".
Notes for a survey of text editors and formatters
Authors: Sachs Jonathan
Published: February 2006

I've had experience with only two formatters: FORMAT and FMT. I can't think of anything worth doing that FORMAT does better than FMT, so I'll largely ignore the former. I'll mainly be reacting to FMT: the things it does that I like, and the things it lacks that I want.
HODI
Authors: Mengarini William
Published: February 2006

HIPO iz u teknyk faar dayugraming dhu fungkshunl atribywts uv prosesz in u sistm. Dhu mowst distingktv port uv HIPO iz dhy inpoot-proses-awtpoot chort. Dhis tryts u proses az u fungkshn, with thingz gowing in and thingz kuming awt. Arowz or ywzd tw repryzent deytu flow. Hyr iz an egzampl:Dhis showz 3 prosesz, whic probbly or not sykwenshl, teking inpoot frum 3 faylz and prudwsing 2 awtpoot faylz. Dhy advantej uv u dayugram lavk dhis iz dhat it konsetreyts on dhy esns uv fungkshn: whut gowz in and whut kumz awt.
Identifying project scope
Authors: Lelle Philip
Published: February 2006

After the initial two months of gathering documents and identifying sources, determination of the scope of the project was begun. The BLS/OWS (Bureau of Labor Statistics, Occupational Wage Survey) System involves several hundred people, distributed in Washington and eight Regional Offices. However, only a few dozen people are totally involved with the OWS System. There are many other Surveys conducted by BLS and the greater portion of time of those peripherally involved in OWS is spent on non-OWS matters. In terms or information flow, between the authors/producers of the OWS System and the users, the direction had been a "pull" by the user's from the Systems group. One of the volumes to be developed had to change this situation, turn it around to "push" the information out to the user. Another volume was defined to be directed towards people in management positions both in BLS and other agencies, and would contain general information about the OWS System. Finally, the System's documentation required for maintenance and running production would be a volume each.
Automated court case management in the prosecutor's office
Authors: Byrne Garrett H.
Published: February 2006

During the early fall of 1977 the National District Attorneys Association and the Suffolk County District Attorney's Office, located in Boston, Massachusetts, completed a two-year cooperative project to design, implement and install a prototype, low cost, computer based prosecutor's case management system in the Suffolk office. The completed system, and the lessons which were learned during the development of this system represent a significant advance in functional design for automated case management for prosecutors.
The Road to Disaster?
Authors: Dorn Philip H.
Published: February 2006

The craftsmen and cottage industries of the 18th century evolved to the now familiar industrial society. After just over 1DO years, the world faces another iteration in an endless social transformation process. Will a post-industrial society, an information age, replace the product-based economic system? If the transition is to occur, when will it happen? What will be the effect on working populations when, inevitably, the mills stop and the furnaces cool? What are the consequences for individuals, nations, and societies of a system where fewer and fewer people produce more and more goods and services?
The documentation delivery problem
Authors: Kuch T. D. C.
Published: February 2006

Suppose you have written the perfect documentation package for a system. Further, suppose you update the documentation instantaneously every time the system changes (Suppose we conquer cancer; suppose we travel faster than light). But, even if this impossible goal is realized, what then?
A formatter generator or programming a formatter machine
Authors: Abbott Russell
Published: February 2006

It happened with compilers, and I guess it had to happen eventually with text formatters. But the source for this development in formatters is surprising--at least to someone who has spent so much time in an academic environment. After having written enough compilers, we, the computer industry, abstracted ourselves to the stage of producing compiler generators. We have, by now, been writing text formatters for quite some time, and yet no one has produced a "theory of text formatting" enabling him to write a formatter generator. Yet Autologic', a leading manufacturer of computer controlled typesetters, needed a formatting facility more sophisticated than those generally available on the standard time sharing system. Serving printers is far different from serving terminal-bound authors.
Texture
Authors: Sachs Jon
Published: February 2006

TEXTURE is a text composer developed by the University of British Columbia (UBC). It runs on IBM System/360 and 370 computers under the Michigan Terminal System. Its designers' objective was to match or exceed the capabilities of IBM's FORMAT text composer by using a more orderly and elegant design.
Acting as an archivist
Authors: Lelle Philip
Published: February 2006

The Bureau of Labor Statistics' Occupational Wage Survey (BLS/OWS) System has a long history of how it grew from manual to nearly automatic processing procedures. The current version of the Survey collection-to-bulletin publication application is written in COBOL and runs as a batch job in the Departmental Computer Center's (DCC) IBM 360-68. Previous versions had made use of 7074's, 1401's, 650's, et al.. During all of these generations, there were many studies such as Task Force group reports on defining functions and their implementation, given the set of hardware capabilities they had to work with. These reports, memos of Regional Office and Washington discussions of realities and hopes, the ad hoc and preemptory user's broadsides, written up in haste for fielding the software, and the technicalities of Wage Survey operation as defined by BLS, made up the inputs that had to be arranged in the, as-yet, undefined structure.
What is text processing?
Authors: Abbott Russ
Published: February 2006

In this article, I begin to set out what I find appealing about text processing. In the process, I hope to define the field of text processing more precisely.
Standardized flowcharts
Authors: LeBlanc Wayne
Published: February 2006

A set of guidelines are detailed in this paper for developing flowcharts which are very useful for writing or documenting structured programs. These guidelines produce flowcharts which allow easy identification of logic paths, allow simple recognition of the depth of decision levels, and compel the same sequence of logic to appear pictorially identical, regardless of the flowchart author.
On teaching the art of compromising in the development of external specifications
Authors: Kimura Izumi
Published: February 2006

Programming in the broader sense includes the development of an external specification. However, no systematic method has been known for training programmers in this side of programming.This paper presents a sample problem which, it is hoped, will be useful for improving the state of the art. The problem concerns the formatting of a letter. It is designed to require compromises between the implementor's and the user's convenience.The paper outlines a possible solution. It includes a coding example that uses a state diagram as a vehicle for pseudo-coding. It also describes a table driven technique and experiences with using the problem in a classroom and other environments.
Trucking right
Authors: Rigo Joe
Published: February 2006

Computers really may help people write better. They provide motivation, and they make the whole job easier.
Automated publications production system
Authors: Bergeron Tom
Published: February 2006

Ever since the Wang Word Processing link to IBM for review on TSO and/or printing by 3800 TILT came to be, people have been clamoring for more. They can see that with just a few minor changes, the two week average time for a master copy to go through Print Services can be cut down to about 20 minutes of 3800 printing time. Let's make those changes.
Ease of use and the richness of documentation adequacy
Authors: Girill T. R.
Published: February 2006

Behind the many staff-training, user-feedback, and design-review proposals described in "Improving the usability of programming publications" (Bethke, 1981), lies a basic commitment to perceived ease of use. In this commentary I argue that this ease-of-use approach to documentation adequacy is valuable because it is intrinsically more sophisticated than its alternatives.
Usability revisited
Authors: Bethke Frederick J.
Published: February 2006

It can be a peculiar experience to revisit something one wrote (or co-wrote) a long time ago. Reading the
Systems Journal
article again after the passage of more than a decade aroused a jumble of thoughts and memories. Along with other things, the titles of Dumas' sequels
Ten Years Later
and
Twenty Years After
floated up into my consciousness. Not that there's much parallel between the romantic world of Dumas and our all-too-realistic and decidedly non-swashbuckling profession; but the echoes rang faintly, nonetheless.
A method to simplify filling data entry forms
Authors: Sankar C. S.
Published: February 2006

Data entry forms are a vital part of information systems in a company or in the federal government. International Data Corporation [1] has projected that, while 44% of today's clerical force has some kind of computer terminal, electronic typewriter, or word processor, by 1986 the ratio of these devices to clerical personnel will exceed 1:1. Most of the clerical personnel will be filling data entry forms, and these data will appear on video screens.
Part three
Authors: Brockmann R. John
Published: February 2006

When I began teaching computer user documentation, there were very few books on the subject...and the few that existed weren't very good (John O'Rourke's Writing for the Reader (1976) excepted). Much has changed since--most notably the increasing interest and market for books on computer user documentation. In fact, so many books have been published in the last three years that this is the third in a series of reviews of ten such books.
A word from the editor
Authors: Lee Newton
Published: February 2006

Welcome to ACM Computers in Entertainment, a premier online magazine featuring video interviews with leading professionals and interesting articles on entertainment technology and its applications.
Interview with Dana Plautz
Authors: Lee Newton , Plautz Dana
Published: February 2006

In our first issue of 2006, the Interviews column features video
interviews with two of our distinguished advisory board members,
Dr. Nicholas Negroponte and Ms. Dana Plautz. Ms. Dana Plautz,
formerly at Intel Research, is the Studio Director at Second Story
Interactive. I conducted a video interview with Dana on November
24, 2005, at the Digital Hollywood conference in Los Angeles,
California. In the video interview, you will hear Dana's answers to
the following questions: 1. You are the chairperson of the Art and
Entertainment Research Council at the Intel Corporation. How has
Intel been promoting art and entertainment research? 2. Can you
give us some examples of art research versus entertainment
research? 3. What are the most effective ways to bridge the gap
between academic research and industrial product development? 4.
Can you share with us some of the exciting projects at the Intel
Multimedia Lab? 5. As a result of the R&D spending by Intel and
other technology companies, how do you see the future of
entertainment?
Computer game-flow design
Authors: Taylor M. J. , Gresty D. , Baskett M.
Published: February 2006

Computer games are a rapidly growing segment of the entertainment industry. Design and development of modern computer games can be a complex activity involving many participants from a variety of disciplines. However, computer game design approaches typically appear to be less formalised than those used for other types of software systems. In this article we describe an approach to computer game-flow design intended for the design of individual game levels within a computer game and demonstrate its application in practice.
Extending cyberspace
Authors: Rashid Omer , Mullins Ian , Coulton Paul , Edwards Reuben
Published: February 2006

In the current market many game developers and publishers treat the cellular phone as just another platform to which they can port a console game; they ignore the exciting new possibilities cellular phones provide via their inherent ability to maintain connectivity while on the move. One possibility is to extend the virtual world of traditional video games through location-based information, which allows users to play games that incorporate knowledge of their physical location and landscape, and then provides them with the ability to interact with both real and virtual objects within that space. However, if such games are to become pervasive and if developers want their efforts to escape the bounds of the research laboratory, they must address the nature of the cellular environment, the precision of the location-based technologies in their region, and the present and likely future capabilities of cellular handsets. To aid innovative game development we draw together many fragmented sources of information for an assessment of technologies, and implementations of cellular location-based games. Further, we discuss practical mechanisms for producing a finer degree of location granularity, both through future technology and our novel implementations of systems that augment location-sensing. The first mechanism uses Bluetooth, which is already a pervasive component of mobile phones feature sets, and can be implemented without the need for client side software. The second implements the use of a future pervasive technology, RFID tags, now that commercial cellular handsets that incorporate RFID readers have emerged.
NTT's technologies for next-generation video services
Authors: Tashiro Yutaka , Yashima Yoshiyuki , Fuju Hiroshi
Published: February 2006

This article presents some examples of video content delivery and two-way video communication services and describes current trends in the digital media technology supporting these services. It also describes NTT's research efforts in subjects such as video coding and introduces our vision of business services that combine high-quality secure video delivery with high added-value processing.
ACM SIGCHI ACE 2006 Hollywood - International Conference on Advances in Computer Entertainment Technology
Authors: Lee Newton
Published: February 2006

Following the great success of ACE 2004 in Singapore and ACE 2005 in Valencia, we have great pleasure in announcing ACM SIGCHI ACE 2006 to be held in the capital of entertainment: Hollywood, USA on 14th - 16th June 2006 www.ace2006.orgSimilarly to ACE in 2004/5, ACM, the world's leading computer science society will be publishing all accepted papers, in both the proceedings and the ACM Digital Library and the conference is fully in technical association with the prestigious ACM SIGCHI.Furthermore, the Best Demo (Gold Medal), Best Paper (Gold Medal), and Excellent Paper prizes will again be awarded. Furthermore the Best papers will be published in the leading ACM publication: ACM Computers in Entertainment as well as the Journal of Virtual Reality and Broadcasting.This year we have very exciting new developments such as new call for art works and the Exhibition: Leonardo II where we call for exhibitions in Interactive Art and Digital Cinema. Furthermore prizes will be given for the best art works.Also we have an exciting line-up of Keynote Speakers which will be announced soon.
Polymorphic regular tree types and patterns
Authors: Vouillon Jérôme
Published: February 2006

We propose a type system based on regular tree grammars, where algebraic datatypes are interpreted in a structural way. Thus, the same constructors can be reused for different types and a flexible subtyping relation can be defined between types, corresponding to the inclusion of their semantics. For instance, one can define a type for lists and a subtype of this type corresponding to lists of even length. Patterns are simply types annotated with binders. This provides a generalization of algebraic patterns with the ability of matching arbitrarily deep in a value. Our main contribution, compared to languages such as XDuce and CDuce, is that we are able to deal with both polymorphism and function types.
Small bisimulations for reasoning about higher-order imperative programs
Authors: Koutavas Vasileios , Wand Mitchell
Published: February 2006

We introduce a new notion of bisimulation for showing contextual equivalence of expressions in an untyped lambda-calculus with an explicit store, and in which all expressed values, including higher-order values, are storable. Our notion of bisimulation leads to smaller and more tractable relations than does the method of Sumii and Pierce [31]. In particular, our method allows one to write down a bisimulation relation directly in cases where [31] requires an inductive specification, and where the principle of local invariants [22] is inapplicable. Our method can also express examples with higher-order functions, in contrast with the most widely known previous methods [4, 22, 32] which are limited in their ability to deal with such examples. The bisimulation conditions are derived by manually extracting proof obligations from a hypothetical direct proof of contextual equivalence.
Fast and loose reasoning is morally correct
Authors: Danielsson Nils Anders , Hughes John , Jansson Patrik , Gibbons Jeremy
Published: February 2006

Functional programmers often reason about programs as if they were written in a total language, expecting the results to carry over to non-total (partial) languages. We justify such reasoning.Two languages are defined, one total and one partial, with identical syntax. The semantics of the partial language includes partial and infinite values, and all types are lifted, including the function spaces. A partial equivalence relation (PER) is then defined, the domain of which is the total subset of the partial language. For types not containing function spaces the PER relates equal values, and functions are related if they map related values to related values.It is proved that if two closed terms have the same semantics in the total language, then they have related semantics in the partial language. It is also shown that the PER gives rise to a bicartesian closed category which can be used to reason about values in the domain of the relation.
Stratified type inference for generalized algebraic data types
Authors: Pottier François , Régis-Gianas Yann
Published: February 2006

Stratified type inference for generalized algebraic data types.
Hybrid type checking
Authors: Flanagan Cormac
Published: February 2006

Traditional static type systems are very effective for verifying basic interface specifications, but are somewhat limited in the kinds specifications they support. Dynamically-checked contracts can enforce more precise specifications, but these are not checked until run time, resulting in incomplete detection of defects.
Hybrid type checking
is a synthesis of these two approaches that enforces precise interface specifications, via static analysis where possible, but also via dynamic checks where necessary. This paper explores the key ideas and implications of hybrid type checking, in the context of the simply-typed λ-calculus with arbitrary refinements of base types.
A polymorphic modal type system for lisp-like multi-staged languages
Authors: Kim Ik-Soon , Yi Kwangkeun , Calcagno Cristiano
Published: February 2006

This article presents a polymorphic modal type system and its principal type inference algorithm that conservatively extend ML by all of Lisp's staging constructs (the quasi-quotation system). The combination is meaningful because ML is a practical higher-order, impure, and typed language, while Lisp's quasi-quotation system has long evolved complying with the demands from multi-staged programming practices. Our type system supports open code, unrestricted operations on references, intentional variable-capturing substitution as well as capture-avoiding substitution, and lifting values into code, whose combination escaped all the previous systems.
A virtual class calculus
Authors: Ernst Erik , Ostermann Klaus , Cook William R.
Published: February 2006

Virtual classes
are class-valued attributes of objects. Like virtual methods, virtual classes are defined in an object's class and may be redefined within subclasses. They resemble inner classes, which are also defined within a class, but virtual classes are accessed through object
instances
, not as static components of a class. When used as types, virtual classes depend upon object identity -- each object instance introduces a new family of virtual class types. Virtual classes support large-scale program composition techniques, including higher-order hierarchies and family polymorphism. The original definition of virtual classes in
BETA
left open the question of static type safety, since some type errors were not caught until runtime. Later the languages Caesar and gbeta have used a more strict static analysis in order to ensure static type safety. However, the existence of a sound, statically typed model for virtual classes has been a long-standing open question. This paper presents a virtual class calculus,
VC
, that captures the essence of virtual classes in these full-fledged programming languages. The key contributions of the paper are a formalization of the dynamic and static semantics of
VC
and a proof of the soundness of
VC
.
Interruptible iterators
Authors: Liu Jed , Kimball Aaron , Myers Andrew C.
Published: February 2006

This paper introduces interruptible iterators, a language feature that makes expressive iteration abstractions much easier to implement. Iteration abstractions are valuable for software design, as shown by their frequent use in well-designed data structure libraries such as the Java Collections Framework. While Java iterators support iteration abstraction well from the standpoint of client code, they are awkward to implement correctly and efficiently, especially if the iterator needs to support imperative update of the underlying collection, such as removing the current element. Some languages, such as CLU and C# 2.0, support iteration through a limited coroutine mechanism, but these mechanisms do not support imperative updates. Interruptible iterators are more powerful coroutines in which the loop body is able to interrupt the iterator with requests to perform updates. Interrupts are similar to exceptions, but propagate differently and have resumption semantics. Interruptible iterators have been implemented as part of the JMatch programming language, an extended version of Java. A JMatch reimplementation of the Java Collections Framework shows that implementations can be made substantially shorter and simpler; performance results show that this language mechanism can also be implemented efficiently.
Specifying C++ concepts
Authors: Dos Reis Gabriel , Stroustrup Bjarne
Published: February 2006

C++ templates are key to the design of current successful mainstream libraries and systems. They are the basis of programming techniques in diverse areas ranging from conventional general-purpose programming to software for safety-critical embedded systems. Current work on improving templates focuses on the notion of concepts (a type system for templates), which promises significantly improved error diagnostics and increased expressive power such as concept-based overloading and function template partial specialization. This paper presents C++ templates with an emphasis on problems related to separate compilation. We consider the problem of how to express concepts in a precise way that is simple enough to be usable by ordinary programmers. In doing so, we expose a few weakness of the current specification of the C++ standard library and suggest a far more precise and complete specification. We also present a systematic way of translating our proposed concept definitions, based on use-patterns rather than function signatures, into constraint sets that can serve as convenient basis for concept checking in a compiler.
Frame rules from answer types for code pointers
Authors: Thielecke Hayo
Published: February 2006

We define a type system, which may also be considered as a simple Hoare logic, for a fragment of an assembly language that deals with code pointers and jumps. The typing is aimed at local reasoning in the sense that only the type of a code pointer is needed, and there is no need to know the whole code itself. The main features of the type system are separation logic connectives for describing the heap, and polymorphic answer types of continuations for keeping track of jumps. Specifically, we address an interaction between separation and answer types: frame rules for local reasoning in the presence of jumps are recovered by instantiating the answer type. However, the instantiation of answer types is not sound for all types. To guarantee soundness, we restrict instantiation to closed types, where the notion of closedness arises from biorthogonality (in a sense inspired by Krivine and Pitts). A machine state is orthogonal to a disjoint heap if their combination does not lead to a fault. Closed types are sets of machine states that are orthogonal to a set of heaps. We use closed types as well-behaved answer types.
A verifiable SSA program representation for aggressive compiler optimization
Authors: Menon Vijay S. , Glew Neal , Murphy Brian R. , McCreight Andrew , Shpeisman Tatiana , Adl-Tabatabai Ali-Reza , Petersen Leaf
Published: February 2006

We present a verifiable low-level program representation to embed, propagate, and preserve safety information in high perfor-mance compilers for safe languages such as Java and C#. Our representation precisely encodes safety information via static single-assignment (SSA) [11, 3] proof variables that are first-class constructs in the program.We argue that our representation allows a compiler to both (1) express aggressively optimized machine-independent code and (2) leverage existing compiler infrastructure to preserve safety information during optimization. We demonstrate that this approach supports standard compiler optimizations, requires minimal changes to the implementation of those optimizations, and does not artificially impede those optimizations to preserve safety. We also describe a simple type system that formalizes type safety in an SSA-style control-flow graph program representation. Through the types of proof variables, our system enables compositional verification of memory safety in optimized code. Finally, we discuss experiences integrating this representation into the machine-independent global optimizer of STARJIT, a high-performance just-in-time compiler that performs aggressive control-flow, data-flow, and algebraic optimizations and is competitive with top production systems.
Editor's message
Authors: Diot Christophe
Published: February 2006

With this first 2006 issue, we are closing one year of the "new CCR formula." This aniversary makes me realize that we have not received many comments about CCR--just a couple of encouragement emails and one strong criticism. The authors of the criticism were mostly unhappy with the fact that we have made changes to the criteria to accept papers, and that these changes are not clearly described on the CCR web site. This is probably (at least partially) true, and we need your feedback to improve CCR. Please send us more feedback, positive or negative. You can send me or any of the area editors direct feedback. Alternatively, you can use the sigcomm mailing list sigcomm@postel.orgTo clarify, papers published in CCR should be of interest to our community. They should be mostly original (please do not send a paper based on material already published--the purpose of CCR is not to archive), with some evidence that it works or that the idea is worth being investigated. Novelty is certainly the heaviest acceptance criteria. So far, we have received around 15 to 20 submissions per issue and accepted 4 or 5 each time. This might be low as an acceptance rate for CCR, and we would love to publish more.Editorials seem to gain popularity. We are publishing 12 of them in this issue with some noticeable ones. Michalis Faloutsos accepted to run a new column on community news to appear in every issue. This editorial will provide news, gossips, practical information, etc. from our community in a humorous way. Michalis needs your input. Note that every gossip will be peer reviewed. Also in this issue Jim Kurose inaugurates a column entitled "10 recommended readings." Please send us the list of your 10 favority papers as well. Finally, we have a new episode of the CCR sitcom "buffers: size does matter!" This series has generated a lot of controversy (under the author's responsability). I believe this kind of argument is useful and I would like to encourage many more of such discussions. What about a new saga on QoS, on overlays, or on clean-slate design of communication architectures? And please keep sending us two-page papers on other topics. We will make our best to publish them as soon as possibleLast, in the previous issue I told you about a new junior reviewing program that I intended to deploy early 2006 (see the October issue for details). Unfortunately, I have received very little feedback on this project. In particular, nobody volunteered to help design the web interface for this service. If you really think such a service can help the community, please drop me a note and (a) volunteer!
Secure distributed data-mining and its application to large-scale network measurements
Authors: Roughan Matthew , Zhang Yin
Published: February 2006

The rapid growth of the Internet over the last decade has been startling. However, efforts to track its growth have often fallen afoul of bad data --- for instance, how much traffic does the Internet now carry? The problem is not that the data is technically hard to obtain, or that it does not exist, but rather that the data is not shared. Obtaining an overall picture requires data from multiple sources, few of whom are open to sharing such data, either because it violates privacy legislation, or exposes business secrets. Likewise, detection of global Internet health problems is hampered by a lack of data sharing. The approaches used so far in the Internet,
e.g.
trusted third parties, or data anonymization, have been only partially successful, and are not widely adopted.The paper presents a method for performing computations on shared data
without any participants revealing their secret data
. For example, one can compute the sum of traffic over a set of service providers without any service provider learning the traffic of another. The method is simple, scalable, and flexible enough to perform a wide range of valuable operations on Internet data.