bluuebunny/crossref_metadata_2025 huggingface dataset:
Matching execution histories of program versions
Authors: Zhang Xiangyu , Gupta Rajiv
Published: November 2005

We develop a method for matching dynamic histories of program executions of two program versions. The matches produced can be useful in many applications including software piracy detection and several debugging scenarios. Unlike some static approaches for matching program versions, our approach does not require access to source code of the two program versions because dynamic histories can be collected by running instrumented versions of program binaries. We base our matching algorithm on comparison of rich program execution histories which include: control flow taken, values produced, addresses referenced, as well as data dependences exercised. In developing a matching algorithm we had two goals: producing an
accurate match
and producing it
quickly
. By using rich execution history, we are able to compare the program versions across many behavioral dimensions. The result is a fast and highly precise matching algorithm. Our algorithm first uses individual histories of instructions to identify multiple potential matches and then it refines the set of matches by matching the data dependence structure established by the matching instructions. To test our algorithm we attempted matching of execution histories of unoptimized and optimized program versions. Our results show that our algorithm produces highly accurate matches which are highly effective when used in comparison checking approach to debugging optimized code.
Lightweight object specification with typestates
Authors: Bierhoff Kevin , Aldrich Jonathan
Published: November 2005

Previous work has proven typestates to be useful for modeling protocols in object-oriented languages. We build on this work by addressing substitutability of subtypes as well as improving precision and conciseness of specifications. We propose a specification technique for objects based on abstract states that incorporates state refinement, method refinement, and orthogonal state dimensions. Union and intersection types form the underlying semantics of method specifications. The approach guarantees substitutability and behavioral subtyping. We designed a dynamic analysis to check existing object-oriented software for protocol conformance and validated our approach by specifying two standard Java libraries. We provide preliminary evidence for the usefulness of our approach.
Joining dataflow with predicates
Authors: Fischer Jeffrey , Jhala Ranjit , Majumdar Rupak
Published: November 2005

Dataflow analyses sacrifice path-sensitivity for efficiency and lead to false positives when used for verification. Predicate refinement based model checking methods are path-sensitive but must perform many expensive iterations to find all the relevant facts about a program, not all of which are naturally expressed and analyzed using predicates. We show how to join these complementary techniques to obtain efficient and precise versions of any lattice-based dataflow analysis using
predicated lattices
. A predicated lattice partitions the program state according to a set of predicates and tracks a lattice element for each partition. The resulting dataflow analysis is more precise than the eager dataflow analysis without the predicates.In addition, we automatically infer predicates to rule out imprecisions. The result is a dataflow analysis that can adaptively refine its precision. We then instantiate this generic framework using a
symbolic execution lattice
, which tracks pointer and value information precisely. We give experimental evidence that our combined analysis is both more precise than the eager analysis in that it is sensitive enough to prove various properties, as well as much faster than the lazy analysis, as many relevant facts are eagerly computed, thus reducing the number of iterations.This results in an order of magnitude improvement in the running times from a purely lazy analysis.
Strathcona example recommendation tool
Authors: Holmes Reid , Walker Robert J. , Murphy Gail C.
Published: November 2005

Using the application programming interfaces (API) of large software systems requires developers to understand details about the interfaces that are often not explicitly defined. However, documentation about the API is often incomplete or out of date. Existing systems that make use of the API provide a form of implicit information on how to use that code. Manually searching through existing projects to find relevant source code is tedious and time consuming. We have created the Strathcona Example.Recommendation Tool to assist developers in finding relevant fragments of code, or examples, of an API's use. These examples can be used by developers to provide insight on how they are supposed to interact with the API.
Parameterized unit tests with unit meister
Authors: Tillmann Nikolai , Schulte Wolfram
Published: November 2005

Parameterized unit tests extend the current industry practice of using closed unit tests defined as parameterless methods. Traditional closed unit tests are re-obtained by instantiating the parameterized unit tests. We have developed the prototype tool
Unit Meister
, which uses symbolic execution and constraint solving to automatically compute a minimal set of inputs that exercise a parameterized unit test given certain coverage criteria. In addition, the parameterized unit tests can be used as symbolic summaries during symbolic execution, which allows our approach to scale for arbitrary abstraction levels. Unit Meister has a command-line interface, and is also integrated into Visual Studio 2005 Team System.
KenyaEclipse
Authors: Chatley Robert , Timbul Thomas
Published: November 2005

A fundamental part of a Computer Science degree is learning to program. Rather than starting students on a full commercial language, we favour using a dedicated "teaching language" to introduce programming concepts.At the same time, we want to introduce students to popular tools that assist in the software development process. However, up until now our teaching language, Kenya, has not been supported by professional IDEs. Therefore, we have been unable to progress smoothly from first principles to the state of the art within one environment.We present work that integrates the Kenya language into the Eclipse environment. Students can now become familiar with the major features of a professional IDE while learning to program, and experience a smooth transition to commercial languages within the same environment.One of the hardest things to teach students is good programming style. Compilers reveal syntactic and type errors, but do not analyse style. We have harnessed as-you-type code checking, as seen in Eclipse's Java development tools, to provide advice on program style as well as correctness.
Visual tool for generative programming
Authors: Grigorenko Pavel , Saabas Ando , Tyugu Enn
Published: November 2005

A way of combining object-oriented and structural paradigms of software composition is demonstrated in a tool for generative programming. Metaclasses are introduced that are components with specifications called metainterfaces. Automatic code generation is used that is based on structural synthesis of programs. This guarantees that problems of handling data dependencies, order of application of components, usage of higher-order control structures etc are handled automatically. Specifications can be written either in a specification language or given visually on an architectural level. The tool is Java-based and portable.
Online testing with model programs
Authors: Veanes Margus , Campbell Colin , Schulte Wolfram , Tillmann Nikolai
Published: November 2005

Online testing is a technique in which test derivation from a model program and test execution are combined into a single algorithm. We describe a practical online testing algorithm that is implemented in the model-based testing tool developed at Microsoft Research called Spec Explorer. Spec Explorer is being used daily by several Microsoft product groups. Model programs in Spec Explorer are written in the high level specification languages AsmL or Spec\#. We view model programs as implicit definitions of interface automata. The conformance relation between a model and an implementation under test is formalized in terms of refinement between interface automata. Testing then amounts to a game between the test tool and the implementation under test.
PR-Miner
Authors: Li Zhenmin , Zhou Yuanyuan
Published: November 2005

Programs usually follow many
implicit
programming rules, most of which are too tedious to be documented by programmers. When these rules are violated by programmers who are unaware of or forget about them, defects can be easily introduced. Therefore, it is highly desirable to have tools to automatically extract such rules and also to automatically detect violations. Previous work in this direction focuses on simple function-pair based programming rules and additionally requires programmers to provide rule templates.This paper proposes a
general
method called PR-Miner that uses a data mining technique called frequent itemset mining to efficiently extract implicit programming rules from large software code written in an industrial programming language such as C,
requiring little effort from programmers and no prior knowledge of the software
. Benefiting from frequent itemset mining, PR-Miner can extract programming rules in general forms (without being constrained by any fixed rule templates) that can contain multiple program elements of various types such as functions, variables and data types. In addition, we also propose an efficient algorithm to automatically detect violations to the extracted programming rules, which are strong indications of bugs.Our evaluation with large software code, including Linux, PostgreSQL Server and the Apache HTTP Server, with 84K--3M lines of code each, shows that PR-Miner can efficiently extract thousands of general programming rules and detect violations within 2 minutes. Moreover, PR-Miner has detected many violations to the extracted rules. Among the top 60 violations reported by PR-Miner, 16 have been confirmed as bugs in the
latest version
of Linux, 6 in PostgreSQL and 1 in Apache. Most of them violate complex programming rules that contain more than 2 elements and are thereby difficult for previous tools to detect. We reported these bugs and they are currently being fixed by developers.
Reuse and variability in large software applications
Authors: Estublier Jacky , Vega German
Published: November 2005

Reuse has always been a major goal in software engineering, since it promises large gains in productivity, quality and time to market reduction. Practical experience has shown that substantial reuse has only successfully happened in two cases: libraries, where many generic and small components can be found; and product lines, where domains-specific components can be assembled in different ways to produce variations of a given product.In this paper we examine how product lines have successfully achieved reuse of coarse-grained components, and the underlying factors limiting this approach to narrowly scoped domains. We then build on this insight to present an approach, called software federation, which proposes a mechanism to overcome the identified limitations, and therefore makes reuse of coarse-grained components possible over a larger range of applications. Our approach extends and generalizes the product line approach, extending the concepts and mechanisms available to manage variability. The system is in use in different companies, validating the claims made in this paper.
Industrial experience with building a web portal product line using a lightweight, reactive approach
Authors: Pettersson Ulf , Jarzabek Stan
Published: November 2005

Imprecise, frequently changing requirements and short time-to-market create challenges for application of conventional software methods in Web Portal engineering. To address these challenges, ST Electronics (Info-Software Systems) Pte. Ltd. applied a lightweight, reactive approach to support a Web Portal product line. Unique characteristics of the approach were fast, low-cost migration from a single conventional Web Portal towards a reusable "generic Web Portal" solution, effective handling of large number of functional variants and their dependencies, the ability to rapidly develop new Web Portals from the generic one, and to independently evolve multiple Web Portals without ever losing a connection between them and the "generic Web Portal". The initial Web Portal was built using state-of-the-art conventional methods. The Web Portal was not flexible enough to reap the benefits of new business opportunities that required the company to rapidly develop and further maintain many similar Web Portals. To overcome the limitations of the conventional solution, a reuse technique called XVCL was applied incrementally. Over a period of three weeks, the conventional solution was converted into a Web architecture capable of handling nine Web Portals from a base of code smaller than the original Web Portal. In the paper, we describe the process that led to building the above Web Portal product line. We explain the difficulties in building an effective generic Web solution using conventional techniques. We analyze our reuse-based solution in qualitative and quantitative ways.
Inconsistency detection and resolution for context-aware middleware support
Authors: Xu Chang , Cheung S. C.
Published: November 2005

Context-awareness is a key feature of pervasive computing whose environments keep evolving. The support of context-awareness requires comprehensive management including detection and resolution of context inconsistency, which occurs naturally in pervasive computing. In this paper we present a framework for realizing dynamic context consistency management. The framework supports inconsistency detection based on a semantic matching and inconsistency triggering model, and inconsistency resolution with proactive actions to context sources. We further present an implementation based on the
Cabot
middleware. The feasibility of the framework and its performance are evaluated through a case study and a simulated experiment, respectively.
Anchoring and adjustment in software estimation
Authors: Aranda Jorge , Easterbrook Steve
Published: November 2005

Anchoring and adjustment is a form of cognitive bias that affects judgments under uncertainty. If given an initial answer, the respondent seems to use this as an 'anchor', adjusting it to reach a more plausible answer, even if the anchor is obviously incorrect. The adjustment is frequently insufficient and so the final answer is biased. In this paper, we report a study to investigate the effects of this phenomenon on software estimation processes. The results show that anchoring and adjustment does occur in software estimation, and can significantly change the resulting estimates, no matter what estimation technique is used. The results also suggest that, considering the magnitude of this bias, software estimators tend to be too confident of their own estimations.
Combining self-reported and automatic data to improve programming effort measurement
Authors: Hochstein Lorin , Basili Victor R. , Zelkowitz Marvin V. , Hollingsworth Jeffrey K. , Carver Jeff
Published: November 2005

Measuring effort accurately and consistently across subjects in a programming experiment can be a surprisingly difficult task. In particular, measures based on self-reported data may differ significantly from measures based on data which is recorded automatically from a subject's computing environment. Since self-reports can be unreliable, and not all activities can be captured automatically, a complete measure of programming effort should incorporate both classes of data. In this paper, we show how self-reported and automatic effort can be combined to perform validation and to measure total programming effort.
Quantitative assessment of UML dynamic models
Authors: Baroni Aline Lúcia
Published: November 2005

In this work we plan to provide a suite of measures to address mainly two problem areas within contemporary object-oriented software measurement: (i) the lack of measures for the early stages of system development, like conceptual modeling and (ii) the lack of measures for dynamic models of an object-oriented system. Our suite of measures is going to be taken from UML 2.0 diagrams. OCL (Object-Constraint Language) and the UML 2.0 meta-model will be used to formalize and contextualize the definitions.
Reengineering towards components using "Reconn-exion"
Authors: Le Gear Andrew , Buckley Jim
Published: November 2005

Continuing to develop software from scratch will not be feasible indefinitely. Reusing existing software would seem to be a viable solution to this problem. The paradigm of component-based development (CBD) explicitly accounts for reuse in its process. Unfortunately the majority of existing software systems are not implemented using CBD, thus reusing portions of this software using CBD becomes difficult. Reengineering and maintenance research contains a plethora of software analysis and restructuring techniques that could be used to help us exploit legacy applications for reuse. This thesis focuses on two such techniques and combines variations of them for the purpose of component recovery: A feature location technique called Software Reconnaissance and a design recovery technique called Software Reflexion Modelling. Their combination is called "Component Reconn-exion." We describe the technique, highlight results and evaluation to date and finally discuss further work necessary to complete our contribution as a PhD. thesis.
Utilizing verification and validation certificates to estimate software defect density
Authors: Sherriff Mark
Published: November 2005

In industry, information on defect density of a product tends to become available too late in the software development process to affordably guide corrective actions. Our research objective is to build a parametric model which utilizes a persistent record of the validation and verification (V&V) practices used with a program to estimate the defect density of that program. The persistent record of the V&V practices are recorded as certificates which are automatically recorded and maintained with the code.PhD Advisor: Dr. Laurie Williams, williams@csc.ncsu.edu
Surveying the factors that influence maintainability
Authors: Hordijk Wiebe , Wieringa Roel
Published: November 2005

We want to explore and analyse design decisions that influence maintainability of software. Software maintainability is important because the effort expended on changes and fixes in software is a major cost driver. We take an empirical, qualitative approach, by investigating cases where a change has cost more or less than comparable changes, and analysing the causes for those differences. We will use this analysis of causes as input to following research in which the individual contributions of a selection of those causes will be quantitatively analysed.
Report on MSR 2005
Authors: Diehl Stephan , Hassan Ahmed E. , Holt Richard C.
Published: November 2005

A one-day workshop on the topic of Mining Software Repositories (MSR) was held at ICSE 2005 in St. Louis, Missouri. Researchers and practitioners in the MSR field try to transform static record keeping software repositories to active ones. These repositories permit researchers to gain empirically based understanding of software development, while software practitioners use these repositories to predict and plan various aspects of their project.Following the success of last year's workshop, MSR 2005 had a large number of high quality submissions and a great number of participants. 22 papers were accepted from 38 submissions - 11 papers were presented as Lightning talks (5 mins) and another 11 papers were presented as regular talks (15 mins). The Lighting talks were followed with a walk-around demo and discussion session.This report includes an overview of the presentations made during the day and a summary of the issues raised throughout the workshop.
Second international workshop on models and processes for the evaluation of off-the-shelf components (MPEC'05)
Authors: Chung Lawrence , Franch Xavier , Maiden Neil
Published: November 2005

Off-The-Shelf Software components (hereafter OTS) play an increasingly important role in software systems development. One of the central activities in a successful OTS-based system development is OTS evaluation, which is one of the cornerstones of OTS selection, OTS implementation and cost models for OTS. Achieving a better understanding of this activity is the objective of the
"International Workshop on Models and Processes for the Evaluation of OTS Components (MPEC)".
After the first edition collocated with ICSE'04, a second edition has taken place (May 21
th
, 2005, Saint Louis, Missouri, USA), again as a satellite event of ICSE.This paper reports on the structure of the workshop, presenting short summaries of the talks given and the research issues identified and heavily discussed during the workshop. More details are available at the workshop URL: http://www.lsi.upc.es/events/mpec.
Advances in model-based software testing (A-MOST)
Authors: Dalal Siddhartha R. , Jain Ashish , Poore Jesse
Published: November 2005

This is a summary of the Advances in Model-Based Software Testing (A-MOST) workshop held on May 15-16, 2005, in St. Louis, Missouri. The workshop had approximately 40 participants. The goals of this workshop were to offer a comprehensive overview of model-based testing to the ICSE community, and bring the researchers and practitioners together to discuss advances, applications, and the complex problems yet to be solved in model-based testing. The workshop was lively and maintained participant interest for the entire two-day program. A brief summary based upon agenda items is provided. Details on the workshops are archived at http://aetgweb.argreenhouse.com.
Scenarios and state machines
Authors: Bontemps Yves , Egyed Alexander
Published: November 2005

This report summarizes the Workshop on Scenarios and State Machines: Models, Algorithms, and Tools, held in St. Louis, Missouri, USA, on 21 May 2005, in conjunction with the International Conference on Software Engineering (ICSE 2005). The workshop consisted of a keynote and nine presentations. The workshop web page, which includes presented papers and the keynote presentation, can be found at http://www.info.fundp.ac.be/~ybo/scesm05/.
An expert committee model to estimate lines of code
Authors: Aggarwal K. K. , Singh Yogesh , Chandra Pravin , Puri Manimala
Published: November 2005

Resource Estimation is a challenging activity, in the early stages of project development. Once the functionality desired by the user is ascertained, function points can be calculated. This paper proposes to estimate Lines of Code once the Function Point count is known, using linear regression techniques and also a neural network model. These two are then combined to propose an expert committee model which gives better results. This is validated by empirical data available from ISBSG data set (release 9).
Universal software safety standard
Authors: Bhansali P. V.
Published: November 2005

This paper identifies the
minimum
subset required for a truly universal safety-critical software standard. This universal software standard could be used in but is not limited to the following application domains: commercial, military and space aviation; medical diagnostic and therapeutic instruments; automotive and transportation systems; industrial process control and robotics; nuclear power plants and weapons control; commercial appliances and ride electronics. The standard takes into account that safety is a system attribute but focuses on software as the critical component. Its roots are based in MoD 00-55, 56, DO-178B, ARP 4754 and 4761, Mil-Std-882 and Software Safety Handbook, IEC 61508, IEC 60880, ANSI/ISA-S84.01, ANSI/AAMI SW68:2001, NASA-STD-8719.13, UL 1998, EN 50128, MISRA Automotive Standard, and IEEE 1228.
This minimum subset uses existing system and software technology and can be adapted to future applications.
A universal software safety standard would benefit the entire safety-critical industry by lowering the cost and improving the quality of software by having common processes and tools. As an additional benefit, various application sectors could share data on the efficacy of each technique used in the development and verification of safety-critical software. This in turn could improve the overall safety of systems in the future.
Engineering on the surprise continuum
Authors: Riehle Richard
Published: November 2005

Speakers at conferences often mention the Principle of Least Surprise. This article explores the notion of surprise on a Surprise Tolerance Continuum. We also comment on how different disciplines benefit from managing surprise. Since this publication deals with software engineering, we focus on problems related to the creation, management, and maintenance of software.
The risks of large organizations in developing complex systems
Authors: Schaefer Robert
Published: November 2005

The risks to the large organization of being able to complete the development of large software intensive systems on time and in budget include not just the defining and maintaining of proper requirements and work processes, but also in the defining and maintaining of the proper organizational work structures. Bureaucratic structures prevalent in large organizations can be inefficient and irrational especially in regards to unplanned surprises, exigencies, contingencies, and the emergent properties that are the normal part of the development and integration of first-of and one-of-a-kind large systems. All large software intensive systems, at their true core, are experiments, and experimentation and bureaucracy have proved to be, over time, destructively antithetical in basic values. Conway's law, first stated in 1968, has by the lights of 2005 provided only a superficial explanation of the antipathy of bureaucracy towards the unknown and risk. The belief that "[o]rganizations which design systems...are constrained to produce designs which are copies of the communication structures of these organizations", can be easily refuted by noting that hierarchical organizations have been quite successful in designing and implementing networked systems subsequent to the invention of Ethernet and TCP/IP. The example provided by Conway was not sufficient by itself to draw the conclusion was made, a common fallacy of cause and effect, but he was certainly on an interesting path of investigation. Large system development failures cannot be prevented soley through improved planning, requirements, processes and software. Improvement must also come from the recognition of the limits of organization, planning and process; the recognition of the basic antipathy between bureaucracy and risk; the recognition of the need for organizational structures that scale yet remain responsive; the recognition of the need for better attitudes towards faults and failures, and the recognition that in order to reduce the risks that are inherent when the technical becomes political, that one must reduce the risks of speaking truth to power. The short article that follows is intended to raise more questions than provide answers, and the references are intended to provide a starting point for further research.
Software quality assurance through COSMIC FFP
Authors: Zayaraz G. , Thambidurai Dr. P. , Srinivasan Madhu , Rodrigues Dr. Paul
Published: November 2005

Success in software development depends on the satisfaction of the quality requirements stated by the stakeholders. Software architecture ensures development of quality software. Quality measurement at the software architecture level leads to risk mitigation, cost reduction and quality assurance. Existing software architectural measurement techniques are qualitative in nature. However, quantification of quality measures facilitates the process of effective quality assurance. In this paper, we propose a new quantitative measurement technique based on COSMIC Full Function Points (CFFP) and ISO 9126 quality standards. Though CFFP methodology was basically designed to measure the functional size of software at the requirements level, attempt has been made to apply COSMIC FFP principles at the architectural level to measure quality attributes based on ISO 9126 quality standards.
Surfing the net for software engineering notes
Authors: Doernhoefer Mark
Published: November 2005

Our last survey of Internet software security sites was about four years ago. I thought it was about time to take another look at the web to see what has been added in the last few years. Some of the sites we've visited before have added extensive new information and resources for developers working on secure software. And this time around, I'd like to focus on some open source software that can help you test and evaluate your applications.
Elaine Chew
Authors: Lee Newton
Published: November 2005

Elaine Chew, our distinguished editorial board advisor, is a recipient of the 2004 Presidential Early Career Award for Scientists and Engineers. She is Viterbi Early Career Chair Assistant Professor at the University of Southern California. She is also a Senior Investigator at the USC Integrated Media Systems Center. She was a Visiting Assistant Professor at Lehigh University's Department of Industrial and Manufacturing Systems Engineering and a freelance pianist for the music faculty chamber groups 2000-2001.
Visualization of tonal content with self-organizing maps and self-similarity matrices
Authors: Toiviainen Petri
Published: November 2005

This article presents a dynamic model of tonality perception based on a short-term memory model and a self-organizing map (SOM). The model can be used for dynamic visualization of perceived tonal content, making it possible to examine the clarity and locus of tonality at any given point of time. This article also presents a method for the visualization of tonal structure using self-similarity matrices. The methods are applied to compositions of J. S. Bach, S. Barber, and J. Pachelbel. Finally, a real-time application embracing the tonality perception model is presented.
Visual hierarchical key analysis
Authors: Sapp Craig Stuart
Published: November 2005

Tonal music is often conceived of as progressing through a sequence of key regions, usually starting and ending in the tonic key, with a journey away from the tonic key somewhere in the middle of the piece. This article presents a visual method of displaying the musical key structure of a composition in a single picture. The hierarchical plots can also show the relative strength of these key regions and how they develop out of the chordal substrate of the music.
Interactive multi-scale visualizations of tonal evolution in MuSA.RT Opus 2
Authors: Chew Elaine , Francois Alexandre R. J.
Published: November 2005

The purpose of this article is to describe MuSA.RT Opus 2, an interactive system for tonal visualization of music at multiple scales, and to present examples of the types of musical features and attributes that can be abstracted and visualized by the system. MuSA.RT aims to create an environment by which musical performances can be mapped in real-time to a concrete and visual metaphor for tonal space, wherein we can see the establishment and evolution of the tonal context. In this environment, expert musicians will be able to see the tonal structures of what they play, initiated listeners will be able to visually follow the structures that they hear, and novices can learn to hear the structures that they see. MuSA.RT is both an interactive art installation that can convert musical performances to mathematically elegant graphics and a scientific tool for visualizing the inner workings of tonal induction and tracking algorithms. In this article we describe the mapping strategies for transforming a MIDI stream into tonal structures in 3D space, and our solution for overcoming the challenge of real-time concurrent processing of data streams; we will also give examples and present case studies of visual mappings of music by Pachelbel, Bach, and Barber.
Children's music journey
Authors: McKinnon Ian
Published: November 2005

Music is recognized as a fundamental component in the education of the individual. Despite this fact, support and funding for music programs in public schools across North America continues to decline. This article discusses the benefits of music education on the development of the young mind and outlines the development of an interactive software program called "Children's Music Journey" to deliver affordable and pedagogically rigorous music education to children everywhere.
Labels and event processes in the asbestos operating system
Authors: Efstathopoulos Petros , Krohn Maxwell , VanDeBogart Steve , Frey Cliff , Ziegler David , Kohler Eddie , Mazières David , Kaashoek Frans , Morris Robert
Published: November 2005

Asbestos, a new prototype operating system, provides novel labeling and isolation mechanisms that help contain the effects of exploitable software flaws. Applications can express a wide range of policies with Asbestos's kernel-enforced label mechanism, including controls on inter-process communication and system-wide information flow. A new event process abstraction provides lightweight, isolated contexts within a single process, allowing the same process to act on behalf of multiple users while preventing it from leaking any single user's data to any other user. A Web server that uses Asbestos labels to isolate user data requires about 1.5 memory pages per user, demonstrating that additional security can come at an acceptable cost.
Mondrix
Authors: Witchel Emmett , Rhee Junghwan , Asanović Krste
Published: November 2005

This paper presents the design and an evaluation of Mondrix, a version of the Linux kernel with Mondriaan Memory Protection (MMP). MMP is a combination of hardware and software that provides efficient fine-grained memory protection between multiple protection domains sharing a linear address space. Mondrix uses MMP to enforce isolation between kernel modules which helps detect bugs, limits their damage, and improves kernel robustness and maintainability. During development, MMP exposed two kernel bugs in common, heavily-tested code, and during fault injection experiments, it prevented three of five file system corruptions.The Mondrix implementation demonstrates how MMP can bring memory isolation to modules that already exist in a large software application. It shows the benefit of isolation for robustness and error detection and prevention, while validating previous claims that the protection abstractions MMP offers are a good fit for software. This paper describes the design of the memory supervisor, the kernel module which implements permissions policy.We present an evaluation of Mondrix using full-system simulation of large kernel-intensive workloads. Experiments with several benchmarks where MMP was used extensively indicate the additional space taken by the MMP data structures reduce the kernel's free memory by less than 10%, and the kernel's runtime increases less than 15% relative to an unmodified kernel.
BAR fault tolerance for cooperative services
Authors: Aiyer Amitanand S. , Alvisi Lorenzo , Clement Allen , Dahlin Mike , Martin Jean-Philippe , Porth Carl
Published: November 2005

This paper describes a general approach to constructing cooperative services that span multiple administrative domains. In such environments, protocols must tolerate both
Byzantine behaviors
when broken, misconfigured, or malicious nodes arbitrarily deviate from their specification and
rational behaviors
when selfish nodes deviate from their specification to increase their local benefit. The paper makes three contributions: (1) It introduces the BAR (Byzantine, Altruistic, Rational) model as a foundation for reasoning about cooperative services; (2) It proposes a general three-level architecture to reduce the complexity of building services under the BAR model; and (3) It describes an implementation of BAR-B the first cooperative backup service to tolerate both Byzantine users and an unbounded number of rational users. At the core of BAR-B is an asynchronous replicated state machine that provides the customary safety and liveness guarantees despite nodes exhibiting both Byzantine and rational behaviors. Our prototype provides acceptable performance for our application: our BAR-tolerant state machine executes 15 requests per second, and our BAR-B backup service can back up 100MB of data in under 4 minutes.
Detecting past and present intrusions through vulnerability-specific predicates
Authors: Joshi Ashlesha , King Samuel T. , Dunlap George W. , Chen Peter M.
Published: November 2005

Most systems contain software with yet-to-be-discovered security vulnerabilities. When a vulnerability is disclosed, administrators face the grim reality that they have been running software which was open to attack. Sites that value availability may be forced to continue running this vulnerable software until the accompanying patch has been tested. Our goal is to improve security by detecting intrusions that occurred before the vulnerability was disclosed and by detecting and responding to intrusions that are attempted after the vulnerability is disclosed. We detect when a vulnerability is triggered by executing
vulnerability-specific predicates
as the system runs or replays. This paper describes the design, implementation and evaluation of a system that supports the construction and execution of these vulnerability-specific predicates. Our system, called IntroVirt, uses virtual-machine introspection to monitor the execution of application and operating system software. IntroVirt executes predicates over past execution periods by combining virtual-machine introspection with virtual-machine replay. IntroVirt eases the construction of powerful predicates by allowing predicates to run existing target code in the context of the target system, and it uses checkpoints so that predicates can execute target code without perturbing the state of the target system. IntroVirt allows predicates to refresh themselves automatically so they work in the presence of preemptions. We show that vulnerability-specific predicates can be written easily for a wide variety of real vulnerabilities, can detect and respond to intrusions over both the past and present time intervals, and add little overhead for most vulnerabilities.
Vigilante
Authors: Costa Manuel , Crowcroft Jon , Castro Miguel , Rowstron Antony , Zhou Lidong , Zhang Lintao , Barham Paul
Published: November 2005

Worm containment must be automatic because worms can spread too fast for humans to respond. Recent work has proposed network-level techniques to automate worm containment; these techniques have limitations because there is no information about the vulnerabilities exploited by worms at the network level. We propose Vigilante, a new end-to-end approach to contain worms automatically that addresses these limitations. Vigilante relies on collaborative worm detection at end hosts, but does not require hosts to trust each other. Hosts run instrumented software to detect worms and broadcast self-certifying alerts (SCAs) upon worm detection. SCAs are proofs of vulnerability that can be inexpensively verified by any vulnerable host. When hosts receive an SCA, they generate filters that block infection by analysing the SCA-guided execution of the vulnerable software. We show that Vigilante can automatically contain fast-spreading worms that exploit unknown vulnerabilities without blocking innocuous traffic.
The taser intrusion recovery system
Authors: Goel Ashvin , Po Kenneth , Farhadi Kamran , Li Zheng , de Lara Eyal
Published: November 2005

Recovery from intrusions is typically a very time-consuming operation in current systems. At a time when the cost of human resources dominates the cost of computing resources, we argue that next generation systems should be built with automated intrusion recovery as a primary goal. In this paper, we describe the design of Taser, a system that helps in selectively recovering legitimate file-system data after an attack or local damage occurs. Taser reverts tainted, i.e. attack-dependent, file-system operations but preserves legitimate operations. This process is difficult for two reasons. First, the set of tainted operations is not known precisely. Second, the recovery process can cause conflicts when legitimate operations depend on tainted operations. Taser provides several analysis policies that aid in determining the set of tainted operations. To handle conflicts, Taser uses automated resolution policies that isolate the tainted operations. Our evaluation shows that Taser is effective in recovering from a wide range of intrusions as well as damage caused by system management errors.
Hibernator
Authors: Zhu Qingbo , Chen Zhifeng , Tan Lin , Zhou Yuanyuan , Keeton Kimberly , Wilkes John
Published: November 2005

Energy consumption has become an important issue in high-end data centers, and disk arrays are one of the largest energy consumers within them. Although several attempts have been made to improve disk array energy management, the existing solutions either provide little energy savings or significantly degrade performance for data center workloads.Our solution, Hibernator, is a disk array energy management system that provides improved energy savings while meeting performance goals. Hibernator combines a number of techniques to achieve this: the use of disks that can spin at different speeds, a coarse-grained approach for dynamically deciding which disks should spin at which speeds, efficient ways to migrate the right data to an appropriate-speed disk automatically, and automatic performance boosts if there is a risk that performance goals might not be met due to disk energy management.In this paper, we describe the Hibernator design, and present evaluations of it using both trace-driven simulations and a hybrid system comprised of a real database server (IBM DB2) and an emulated storage server with multi-speed disks. Our file-system and on-line transaction processing (OLTP) simulation results show that Hibernator can provide up to 65% energy savings while continuing to satisfy performance goals (6.5--26 times better than previous solutions). Our OLTP emulated system results show that Hibernator can save more energy (29%) than previous solutions, while still providing an OLTP transaction rate comparable to a RAID5 array with no energy management.
Speculative execution in a distributed file system
Authors: Nightingale Edmund B. , Chen Peter M. , Flinn Jason
Published: November 2005

Speculator provides Linux kernel support for speculative execution. It allows multiple processes to share speculative state by tracking causal dependencies propagated through inter-process communication. It guarantees correct execution by preventing speculative processes from externalizing output, e.g., sending a network message or writing to the screen, until the speculations on which that output depends have proven to be correct. Speculator improves the performance of distributed file systems by masking I/O latency and increasing I/O throughput. Rather than block during a remote operation, a file system predicts the operation's result, then uses Speculator to checkpoint the state of the calling process and speculatively continue its execution based on the predicted result. If the prediction is correct, the checkpoint is discarded; if it is incorrect, the calling process is restored to the checkpoint, and the operation is retried. We have modified the client, server, and network protocol of two distributed file systems to use Speculator. For PostMark and Andrew-style benchmarks, speculative execution results in a factor of 2 performance improvement for NFS over local-area networks and an order of magnitude improvement over wide-area networks. For the same benchmarks, Speculator enables the Blue File System to provide the consistency of single-copy file semantics and the safety of synchronous I/O, yet still outperform current distributed file systems with weaker consistency and safety.
RaceTrack
Authors: Yu Yuan , Rodeheffer Tom , Chen Wei
Published: November 2005

Bugs due to data races in multithreaded programs often exhibit non-deterministic symptoms and are notoriously difficult to find. This paper describes RaceTrack, a dynamic race detection tool that tracks the actions of a program and reports a warning whenever a suspicious pattern of activity has been observed. RaceTrack uses a novel hybrid detection algorithm and employs an adaptive approach that automatically directs more effort to areas that are more suspicious, thus providing more accurate warnings for much less over-head. A post-processing step correlates warnings and ranks code segments based on how strongly they are implicated in potential data races. We implemented RaceTrack inside the virtual machine of Microsoft's Common Language Runtime (product version v1.1.4322) and monitored several major, real-world applications directly out-of-the-box,without any modification. Adaptive tracking resulted in a slowdown ratio of about 3x on memory-intensive programs and typically much less than 2x on other programs,and a memory ratio of typically less than 1.2x. Several serious data race bugs were revealed, some previously unknown.
Rx
Authors: Qin Feng , Tucek Joseph , Sundaresan Jagadeesan , Zhou Yuanyuan
Published: November 2005

Many applications demand availability. Unfortunately, software failures greatly reduce system availability. Prior work on surviving software failures suffers from one or more of the following limitations: Required application restructuring, inability to address deterministic software bugs, unsafe speculation on program execution, and long recovery time.This paper proposes an innovative
safe
technique, called Rx, which can quickly recover programs from many types of software bugs, both deterministic and non-deterministic. Our idea, inspired from allergy treatment in real life, is to rollback the program to a recent checkpoint upon a software failure, and then to re-execute the program in a
modified
environment. We base this idea on the observation that many bugs are correlated with the execution environment, and therefore can be avoided by removing the "allergen" from the environment. Rx requires few to no modifications to applications and provides programmers with additional feedback for bug diagnosis.We have implemented RX on Linux. Our experiments with four server applications that contain six bugs of various types show that RX can survive all the six software failures and provide transparent fast recovery within 0.017-0.16 seconds, 21-53 times faster than the whole program restart approach for all but one case (CVS). In contrast, the two tested alternatives, a whole program restart approach and a simple rollback and re-execution without environmental changes, cannot successfully recover the three servers (Squid, Apache, and CVS) that contain deterministic bugs, and have only a 40% recovery rate for the server (MySQL) that contains a non-deterministic concurrency bug. Additionally, RX's checkpointing system is lightweight, imposing small time and space overheads.