bluuebunny/crossref_metadata_2025 huggingface dataset:
LOCAL ORDER AT THE SURFACE OF BINARY ALLOYS IN RELATION TO THEIR CHEMICAL REACTIVITY
Authors: BERTOLINI J. C.
Published: October 2004

The behavior of binary alloys with respect to catalysis can be understood in terms of the geometric “ensemble effect” and/or the electronic “ligand effect.” For understanding, one has consequently to know precisely the local concentration and arrangement of both components at the very surface (in contact with the reactants), and also in the sublayers which influence electronically the outer atoms. Two kinds of well-defined surface are considered: binary alloys and well-controlled deposits of a given metal on a foreign metallic substrate. After a brief description of the driving forces for surface segregation and of metal-on-metal growth modes, the relations between surface composition/structure and reactivity of binary alloys are illustrated by some striking examples. In order to limit the discussion, the presentation is focused on platinum-based and palladium-based alloys. The ensemble effect is discussed first on the basis of the influence of inactive Bi, Pb or Sn deposits on Pt single crystal surfaces. For alloys, the PtCu3 (111), which exhibits a p (2×2) ordered surface structure in which the Pt surface atoms are all isolated by Cu atoms, offers a unique model sample for studying the dilution (of Pt by Cu) influence. The electronic influence of elements present in the sublayers is illustrated on PtNi (111) and Pt 3 Fe (111) samples, which present a quasicomplete Pt surface layer (with more or less Ni or Fe in the sublayers) and strong modifications of their chemisorptive properties and catalytic performances for some simple reactions. The properties of surfaces largely concentrated into Pd (either by large surface segregation in alloys containing low bulk Pd content, or by Pd deposition on various single crystal metal substrates) are discussed in the light of electronic modifications induced by the substrate atoms, with consequences on their chemical reactivity.
CHEMISTRY ON SINGLE CRYSTAL SURFACES OF Pt AND Pd ALLOYS
Authors: NIEUWENHUYS B. E.
Published: October 2004

During the past decade, alloy surfaces have been increasingly studied on the atomic level. As a result, their atomic structure, composition and the adsorbate-surface interactions are much better understood. The purpose of this paper is to review the status of our present knowledge of the chemical properties of single crystal surfaces of Pd and Pt alloys. In particular, the adsorption of H 2, 0 2, CO, NO and the catalytic reactions involving these molecules on single crystal surfaces of Pd-Cu , Pd-Ag , Pd-Au , Pt-Cu , Pt-Rh , Pt-Fe , Pt-Co , Pt-Ni and Pt-Ti are discussed and compared with the processes on the corresponding single crystal surfaces of the pure metals.
First-class monadic schedules
Authors: Mirani Rajiv , Hudak Paul
Published: October 2004

Parallel functional languages often use meta-linguistic annotations to provide control over parallel evaluation. In this paper we explore a flexible mechanism to control when an expression is evaluated:
first-class monadic schedules
. We discuss the advantages of using such first-class values over traditional annotation-based systems. In particular, it is often desirable to make decisions about the operational behavior of parallel programs depending on the dynamic state of the system. For example, we may want to measure the system load before deciding to evaluate expressions in parallel. For this purpose, we show how
monads
can be used to access dynamic system parameters in a referentially transparent manner (up to termination).As a mechanism to reason about schedules, we present a set of
algebraic properties
that any implementation of schedules must satisfy. We also describe an implementation that translates schedules into a dialect of Scheme extended with
futures
. We prove that this implementation satisfies the given set of algebraic properties, and give performance results for a parallel solution to the
n
-body problem using the Barnes--Hut method.Although our ideas were developed specifically for nonstrict functional languages such as Haskell, we briefly discuss how they can be used with strict functional languages and imperative languages as well.
Optimistic register coalescing
Authors: Park Jinpyo , Moon Soo-Mook
Published: October 2004

Graph-coloring register allocators eliminate copies by coalescing the source and target nodes of a copy if they do not interfere in the interference graph. Coalescing, however, can be harmful to the colorability of the graph because it tends to yield a graph with nodes of higher degrees. Unlike
aggressive coalescing
, which coalesces any pair of noninterfering copy-related nodes,
conservative coalescing
or
iterated coalescing
perform safe coalescing that preserves the colorability. Unfortunately, these heuristics give up coalescing too early, losing many opportunities for coalescing that would turn out to be safe. Moreover, they ignore the fact that coalescing may even improve the colorability of the graph by reducing the degree of neighbor nodes that are interfering with both the source and target nodes being coalesced. This article proposes a new heuristic called
optimistic coalescing
which optimistically performs aggressive coalescing, thus exploiting the positive impact of coalescing aggressively, but when a coalesced node is to be spilled, it is split back into separate nodes. Since there is a better chance of coloring one of those splits, we can reduce the overall spill amount.
Is hierarchical public-key certification the next target for hackers?
Authors: Burmester Mike , Desmedt Yvo G.
Published: October 2004

Considering alternatives to hierarchical authentication structures that are not sufficiently secure for communication on open networks such as the Internet.
Certified mail
Authors: Oppliger Rolf
Published: October 2004

The lack of evidence for message receipt is a missing piece of the infrastructure required for the more professional use of email.
Electronic frontiers in foreign exchange trading
Authors: Gallaugher John , Melville Nigel
Published: October 2004

In pursuit of the $1.2-trillion-a-day opportunity.
2004 ACM awards banquet
Authors: CACM Staff
Published: October 2004

ACM played host to over 200 industry luminaries at its 2004 Awards Banquet held June 5 at the Plaza Hotel in New York City. The event recognizes technical excellence and outstanding service to the computing field. The 2003 award winners and newly inducted ACM Fellows represent a diverse group of leaders in the computing field and the IT community. The following images capture those honored:
Does telecommuting really increase productivity?
Authors: Westfall Ralph D.
Published: October 2004

As many companies have learned in the last decade, the reality of telecommuting does not reflect the hype, the expected potential, or the existing literature.
Negotiating in service-oriented environments
Authors: Elfatatry Ahmed , Layzell Paul
Published: October 2004

Buy or rent? This question applies not only to houses and cars, but now to software.
The mystery of formal methods disuse
Authors: Glass Robert L.
Published: October 2004

A story of zealotry and chicanery.
Computer science education in Japan
Authors: Bush Martin E.
Published: October 2004

Firsthand observations trace the current state, future potential, and obstacles ahead for Japanese academia.
Introduction
Authors: Rosenbloom Andrew
Published: October 2004

Complex 3D worlds built from scientific data or transformed into multiplayer games can be experienced naturally, not just viewed through flat 2D windows.
Designing cranial implants in a haptic augmented reality environment
Authors: Scharver Chris , Evenhouse Ray , Johnson Andrew , Leigh Jason
Published: October 2004

Medical sculptors and neurosurgeons create virtual 3D cranial models based on patient CT data superimposed over their hands as if they were sculpting physical models.
Toward the merging of real and virtual spaces
Authors: Lok Benjamin C.
Published: October 2004

In hybrid environments, where real and virtual overlap, participants naturally see, touch, and manipulate the object at hand.
Visualizing dynamic architectural environments
Authors: Houston Mike , Niederauer Chris , Agrawala Maneesh , Humphreys Greg
Published: October 2004

How to expose the internal 3D structures of multiplayer games and architectural models by automatically generating interactive exploded views.
A study of source-level compiler algorithms for automatic construction of pre-execution code
Authors: Kim Dongkeun , Yeung Donald
Published: October 2004

Pre-execution is a promising latency tolerance technique that uses one or more helper threads running in spare hardware contexts ahead of the main computation to trigger long-latency memory operations early, hence absorbing their latency on behalf of the main computation. This article investigates several source-to-source C compilers for extracting pre-execution thread code automatically, thus relieving the programmer or hardware from this onerous task. We present an aggressive profile-driven compiler that employs three powerful algorithms for code extraction. First,
program slicing
removes non-critical code for computing cache-missing memory references. Second,
prefetch conversion
replaces blocking memory references with non-blocking prefetch instructions to minimize pre-execution thread stalls. Finally,
speculative loop parallelization
generates thread-level parallelism to tolerate the latency of blocking loads. In addition, we present four "reduced" compilers that employ less aggressive algorithms to simplify compiler implementation. Our reduced compilers rely on back-end code optimizations rather than program slicing to remove non-critical code, and use compile-time heuristics rather than profiling to approximate runtime information (e.g., cache-miss and loop-trip counts).We prototype our algorithms on the Stanford University Intermediate Format (SUIF) framework and a publicly available program slicer, called
Unravel
[Lyle and Wallace 1997]. Using our prototype, we undertake a performance evaluation of our compilers on a detailed architectural simulator of an 8-way out-of-order SMT processor with 4 hardware contexts, and 13 applications selected from the SPEC and Olden benchmark suites. Our most aggressive compiler improves the performance of 10 out of 13 applications, reducing execution time by 20.9%. Across all 13 applications, our aggressive compiler achieves a harmonic average speedup of 17.6%. For our reduced compilers, eliminating program slicing and relying on back-end optimizations degrades performance minimally, suggesting that effective pre-execution compilers can be built without program slicing. Furthermore, without cache-miss profiles, we still achieve good speedup, 15.5%, but without loop-trip count profiles, we achieve a speedup of only 7.7%. Finally, our results show compiler-based pre-execution can benefit multiprogrammed workloads. Simultaneously executing applications achieve higher throughput with pre-execution compared to no pre-execution. Due to contention for hardware contexts, however, time-slicing outperforms simultaneous execution in some cases where individual applications make heavy use of pre-execution threads.
An overview of the PAISLey project-1984
Authors: Zave Pamela
Published: October 2004

PAISLey is an executable specification language that is especially well suited to real-time and distributed systems. It is motivated by an approach to software development based on the separation of problem-oriented from implementation-oriented concerns, and promising several substantial benefits over conventional development cycles. The language is executed by an interpreter that provides capabilities for debugging specifications, giving demonstrations to customers, early performance simulation, and (eventually) rapid prototyping. The language has been the vehicle for major example specifications in four problem domains, and for two methods for reducing whole classes, of problems to appropriate specifications. In June 1984 the emphasis of the PAISLey project will shift to practical use and evaluation, starting with PAISLey workshops and consulting services offered to potential user organizations by a technology-transfer program within AT&T Bell Laboratories. This paper is intended to summarize what has been achieved so far and to serve as a guide for further reading.
My accordian's stuffed full of paper
Authors: Brown Dave
Published: October 2004

Once upon a time I thought there was a fixed amount of energy that a development team could put on a project in any given period of time, and I simply had to allocate that to productive and non-productive tasks. Woe and behold, Dick Orgass corrected me. He noted that projects which write large papers about their design get far less done than ones which keep their non-productive tasks under stricter control, even with the same amount of resources.This is a paper about
why
.
Understanding the software paradox
Authors: Blum Bruce
Published: October 2004

This paper considers why the software community has not yet automated the process of developing software. It identifies some of the major factors which inhibit the establishment of a unifying view. The paper considers alternate views of the development process and discusses implications of each. Finally, it reviews some of the non-technical issues related to software development. This is a paper of ideas; no solutions are offered.
Towards more intelligent programming environments
Authors: Parker Jeff
Published: October 2004

This paper reports on research into the investigation and development of facilities for intelligent program development aids. Such facilities for example a structured editor, provide a superior environment for the development of programs in existing languages such as Pascal. They also present the opportunity for the development of interactive programming languages which are no longer subject to the constraints imposed by traditional software development tools.
Evolutionary Delivery versus the "waterfall model"
Authors: Gilb Tom
Published: October 2004

The conventional wisdom of planning software engineering projects, using the widely cited "waterfall model" is not the only useful software development process model. In fact, the "waterfall model" may be unrealistic, and dangerous to the primary objectives of any software project.The alternative model, which I choose to call "evolutionary delivery" is not widely taught or practiced yet. But there is already more than a decade of practical experience in using it. In various forms. It is quite clear from these experiences that evolutionary delivery is a powerful general tool for both software development and associated systems development.Almost all experienced software developers do make use of some of the ideas in evolutionary development at one time or another. But, this is often unplanned, informal and it is an incomplete exploitation of this powerful method. This paper will try to expose the theoretical and practical aspects of the method in a fuller perspective. We need to learn the theory fully, so that we can apply and learn it completely.
Productivity
Authors: Bazelmans Rudy
Published: October 2004

This paper addresses the issue of productivity in the software industry. It discusses the expected benefits of software tools and techniques. It describes the role of the tools group in this regard and, finally, discusses the characteristics of members of a tools group.
PARTIAL
Authors: Reynolds Robert G.
Published: October 2004

This paper describes a software tool, PARTIAL, that monitors a sequence of stepwise refinements. This tool is designed to collect information about properties of the stepwise refinement of pseudocode, where the pseudocode can be based upon any target language. The particular language selected to illustrate the system here is Ada.The system is used to analyze a stepwise refinement sequence from Myers (7). While few patterns appear evident when looking at this sequence of stepwise refinements, use of the partial metrics system illuminates a set of distinctly linear trends in the development process. These trends suggest questions that can be investigated in the future using the partial metrics approach.
UNIX as an environment for non-UNIX software development
Authors: Ward Jean Renard
Published: October 2004

Many of the back issues of SEN contain articles about software development environments and software tools. UNIX has historically been cited as an example of a good software development environment. For many developers still struggling with the offspring of MS-DOS, RSX-11M, OS-370 and the like, UNIX still represents a dreamed-of state-of-the-art. Many of the more enhanced environments actually sit on top of UNIX or a UNIX-like system, especially for graphics-based environments like those offered by Sun Microsystems, Apollo, and Masscomp.Pencept's business is real-time character recognition for hand-"scribbled" text. Our products run in a completely non-UNIX environment, but all of our development is done on UNIX. This presented a unique opportunity to find out how good "standard" UNIX is for developing non-UNIX products.Based on our experience, we have come to the conclusion that UNIX is a good software development environment for the kinds of applications that are traditionally run on UNIX, if UNIX is the target environment. UNIX (and most of its derivatives) do NOT address many of the more general needs of non-UNIX software engineering projects.UNIX is a powerful system, partly because it comes with a large assortment of software development tools. Some of the deficiencies and problems we had to resolve were:+ Certain UNIX and vendor software had to be modified, because it did not have all the functions we absolutely needed.+ Several UNIX utilities did poorly for this big a project.+ Some UNIX features were poorly designed for non-UNIX development.+ Some tools for our particular project are not part of UNIX.Our particular vendor is Masscomp, which competes in the high-performance graphics workstation market with companies such as Apollo, Sun Microsystems, and Digital Equipment Corporation. We believe that our experience is generally applicable to UNIX systems, regardless of vendor, and across a variety of UNIX versions (System III, System V, Berkeley 4.2, etc.)
An Ina Jo® proof manager for the formal development method
Authors: Berry Daniel M.
Published: October 2004

This paper describes methods for decomposing large conjectures into smaller ones in order to make their proof easier and for limiting the amount of reproving that occurs when a specification is modified. It proposes a tool, based on these methods, for managing the proofs of conjectures about an evolving specification.
Prolog technology as a basis for verification systems
Authors: Gerhart Susan L.
Published: October 2004

Prolog presents an interesting alternative technology to Lisp and Pascal-like languages for implementing verification systems. The AFFIRM Specification and Verification System has been partially re-implemented successfully in Prolog. Experiences and conjectures about the future role of Prolog are discussed.
LUCID
Authors: Glasgow Jexice I. , MacEwe Glena H.
Published: October 2004

This paper proposes the use of the specification/programming language Lucid to specify secure distributed systems. It reports on the status of work to develop a formal model of security for the SNet multi-level secure distributed system, and to specify it in Lucid.
The emerging social significance of the magnetic-tape write-enable ring
Authors: Dunn Dick
Published: October 2004

Magnetic tape write-enable rings are found, by virtue of physical characteristics and wide general availability, to be of considerable use outside their designed application area. Their serendipitous significance is conceptually analogous to that of the paper clip.
Defending against an Internet-based attack on the physical world
Authors: Byers Simon , Rubin Aviel D. , Kormann David
Published: October 2004

We discuss the dangers that scalable Internet functionality may present to the real world, focusing upon an attack that is simple, yet can have great impact, which we believe may occur quite soon. We offer and critique various solutions to this class of attack and hope to provide a warning to the Internet community of what is currently possible. The attack is, to some degree, a consequence of the availability of private information on the Web, and the increase in the amount of personal information that users must reveal to obtain Web services.
Answering queries using views
Authors: Goasdoué François , Rousset Marie-Christine
Published: October 2004

In this article, we investigate a first step towards the long-term vision of the Semantic Web by studying the problem of answering queries posed through a mediated ontology to multiple information sources whose content is described as
views
over the ontology relations. The contributions of this paper are twofold. We first offer a uniform logical setting which allows us to encompass and to relate the existing work on answering and rewriting queries using views. In particular, we make clearer the connection between the problem of rewriting queries using views and the problem of answering queries using extensions of views. Then we focus on an instance of the problem of rewriting
conjunctive queries
using views through an ontology expressed in a description logic, for which we exhibit a complete algorithm.
Recovery guarantees for Internet applications
Authors: Barga Roger , Lomet David , Shegalov German , Weikum Gerhard
Published: October 2004

Internet-based e-services require application developers to deal explicitly with failures of the underlying software components, for example web servers, servlets, browser sessions, and so forth. This complicates application programming, and may expose failures to end users. This paper presents a framework for an application-independent infrastructure that provides recovery guarantees and masks almost all system failures, thus relieving the application programmer from having to deal with these failures---by making applications "stateless." The main concept is an interaction contract between two components regarding message and state preservation. The framework provides comprehensive recovery encompassing data, messages, and the states of application components. We describe techniques to reduce logging cost, allow effective log truncation, and permit independent recovery for critical components. We illustrate the framework's utility via web-based e-services scenarios. Its feasibility is demonstrated by our prototype implementation of interaction contracts based on the Apache web server and the PHP servlet engine. Finally, we discuss industrial relevance for middleware architectures such as. Net or J2EE.
Advances in dataflow programming languages
Authors: Johnston Wesley M. , Hanna J. R. Paul , Millar Richard J.
Published: October 2004

Many developments have taken place within dataflow programming languages in the past decade. In particular, there has been a great deal of activity and advancement in the field of dataflow visual programming languages. The motivation for this article is to review the content of these recent developments and how they came about. It is supported by an initial review of dataflow programming in the 1970s and 1980s that led to current topics of research. It then discusses how dataflow programming evolved toward a hybrid von Neumann dataflow formulation, and adopted a more coarse-grained approach. Recent trends toward dataflow visual programming languages are then discussed with reference to key graphical dataflow languages and their development environments. Finally, the article details four key open topics in dataflow programming languages.
Image Retrieval from the World Wide Web
Authors: Kherfi M. L. , Ziou D. , Bernardi A.
Published: October 2004

With the explosive growth of the World Wide Web, the public is gaining access to massive amounts of information. However, locating needed and relevant information remains a difficult task, whether the information is textual or visual. Text search engines have existed for some years now and have achieved a certain degree of success. However, despite the large number of images available on the Web, image search engines are still rare. In this article, we show that in order to allow people to profit from all this visual information, there is a need to develop tools that help them to locate the needed images with good precision in a reasonable time, and that such tools are useful for many applications and purposes. The article surveys the main characteristics of the existing systems most often cited in the literature, such as ImageRover, WebSeek, Diogenes, and Atlas WISE. It then examines the various issues related to the design and implementation of a Web image search engine, such as data gathering and digestion, indexing, query specification, retrieval and similarity, Web coverage, and performance evaluation. A general discussion is given for each of these issues, with examples of the ways they are addressed by existing engines, and 130 related references are given. Some concluding remarks and directions for future research are also presented.
Line drawing, leap years, and Euclid
Authors: Harris Mitchell A. , Reingold Edward M.
Published: October 2004

Bresenham's algorithm minimizes error in drawing lines on integer grid points; leap year calculations, surprisingly, are a generalization. We compare the two calculations, explicate the pattern, and discuss the connection of the leap year/line pattern with integer division and Euclid's algorithm for computing the greatest common divisor.
Finite state machines for strings over infinite alphabets
Authors: Neven Frank , Schwentick Thomas , Vianu Victor
Published: October 2004

Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata and logics defining the regular languages on finite alphabets. Specifically, we consider register and pebble automata, and extensions of first-order logic and monadic second-order logic. For each type of automaton we consider one-way and two-way variants, as well as deterministic, nondeterministic, and alternating control. We investigate the expressiveness and complexity of the automata and their connection to the logics, as well as standard decision problems. Some of our results answer open questions of Kaminski and Francez on register automata.
Symbolic semantic rules for producing compact STGLAs from value passing process descriptions
Authors: Bernardo Marco
Published: October 2004

Value passing process algebras with infinite data domains need to be equipped with symbolic semantic models in order for their analysis to be possible. This means that appropriate symbolic models and the related verification algorithms must be developed, together with suitable semantic rules mapping the value passing process descriptions to such symbolic models. In this article, we first introduce the model of the symbolic transition graphs with lookahead assignment (STGLAs), a variant of the symbolic transition graphs with assignment (STGAs) of Lin that can undergo to the strong, weak and observational bisimulation equivalence checking algorithms of Li and Chen. We then define a set of symbolic semantic rules that map a useful fragment of value passing CCS to finite STGLAs without making any assumption about the variable names. We demonstrate that the symbolic semantic rules are correct with respect to both the usual concrete semantic rules and the novel issue of the assignment application order. Finally, we prove that, for the considered fragment of value passing CCS, the STGLAs produced by the symbolic semantic rules are optimal with respect to a certain compactness criterion, thus improving on the symbolic models and the semantic rules previously proposed in the literature.
Termination of simply moded logic programs with dynamic scheduling
Authors: Bossi Annalisa , Etalle Sandro , Rossi Sabina , Smaus Jan-Georg
Published: October 2004

In logic programming,dynamic schedulingindicates the feature by means of which the choice of the atom to be selected at each resolution step is done at runtime and does not follow a fixed selection rule such as the left-to-right one of Prolog.Input-consuming derivationswere introduced to model dynamic scheduling while abstracting from the technical details. In this article, we provide a sufficient and necessary criterion for termination of input-consuming derivations of simply moded logic programs. The termination criterion we propose is based on a denotational semantics for partial derivations which is defined in the spirit of model-theoretic semantics previously proposed for left-to-right derivations.
Hypothesis-based semantics of logic programs in multivalued logics
Authors: Loyer Yann , Spyratos Nicolas , Stamate Daniel
Published: October 2004

We address the problem of defining semantics for logic programs in presence of incomplete and contradictory information coming from different sources. The information consists of facts that a central server collects and tries to combine using (a) a set of logical rules, that is, a logic program, and (b) a hypothesis representing the server's own estimates. In such a setting incomplete information from a source or contradictory information from different sources necessitate the use of many-valued logics in which programs can be evaluated and hypotheses can be tested. To carry out such activities we propose a formal framework based on bilattices such as Belnap's four-valued logics. In this framework we work with the class of programs defined by Fitting and we propose hypothesis-based semantics for such programs. We also establish an intuitively appealing connection between our hypothesis testing mechanism, on the one hand, and the well-founded semantics and Kripke-Kleene semantics of Datalog programs with negation, on the other hand.
Reflective metalogical frameworks
Authors: Basin David , Clavel Manuel , Meseguer José
Published: October 2004

A metalogical framework is a logic with an associated methodology that is used to represent other logics and to reason about their metalogical properties. We propose that logical frameworks can be good metalogical frameworks when their theories always have initial models and they support reflective and parameterized reasoning.We develop this thesis both abstractly and concretely. Abstractly, we formalize our proposal as a set of requirements and explain how any logic satisfying these requirements can be used for metalogical reasoning. Concretely, we present membership equational logic as a particular metalogic that satisfies these requirements. Using membership equational logic, and its realization in the Maude system, we show how reflection can be used for different, nontrivial kinds of formal metatheoretic reasoning. In particular, one can prove metatheorems that relate theories or establish properties of parameterized classes of theories.
Static and dynamic analysis of call chains in java
Authors: Rountev Atanas , Kagan Scott , Gibas Michael
Published: October 2004

This work presents a parameterized framework for static and dynamic analysis of call chains in Java components. Such analyses have a wide range of uses in tools for software understanding and testing. We also describe a test coverage tool built with these analyses and the use of the tool on a real-world test suite. Our experiments evaluate the exact precision of several instances of the framework and provide a novel approach for estimating the limits of class analysis technology for computing precise call chains.
Testing of java web services for robustness
Authors: Fu Chen , Ryder Barbara G. , Milanova Ana , Wonnacott David
Published: October 2004

This paper presents a new compile-time analysis that enables a testing methodology for white-box coverage testing of error recovery code (i.e., exception handlers) in Java web services using compiler-directed fault injection. The analysis allows compiler-generated instrumentation to guide the fault injection and to record the recovery code exercised. (An injected fault is experienced as a Java exception.) The analysis (i) identifies the
exception-flow 'def-uses'
to be tested in this manner, (ii) determines the kind of fault to be requested at a program point, and (iii) finds appropriate locations for code instrumentation. The analysis incorporates refinements that establish sufficient context sensitivity to ensure relatively precise def-use links and to eliminate some spurious def-uses due to demonstrably infeasible control flow. A runtime test harness calculates test coverage of these links using an
exception def-catch
metric. Experiments with the methodology demonstrate the utility of the increased precision in obtaining good test coverage on a set of moderately-sized Java web services benchmarks.
Testing malware detectors
Authors: Christodorescu Mihai , Jha Somesh
Published: October 2004

In today's interconnected world, malware, such as worms and viruses, can cause havoc. A malware detector (commonly known as virus scanner) attempts to identify malware. In spite of the importance of malware detectors, there is a dearth of testing techniques for evaluating them. We present a technique based on program obfuscation for generating tests for malware detectors. Our technique is geared towards evaluating the resilience of malware detectors to various obfuscation transformations commonly used by hackers to disguise malware. We also demonstrate that a hacker can leverage a malware detector's weakness in handling obfuscation transformations and can extract the signature used by a detector for a specific malware. We evaluate three widely-used commercial virus scanners using our techniques and discover that the resilience of these scanners to various obfuscations is very poor.
Covering arrays for efficient fault characterization in complex configuration spaces
Authors: Yilmaz Cemal , Cohen Myra B. , Porter Adam
Published: October 2004

Testing systems with large configurations spaces that change often is a challenging problem. The cost and complexity of QA explodes because often there isn't just one system, but a multitude of related systems. Bugs may appear in certain configurations, but not in others.The Skoll system and process has been developed to test these types of systems through distributed, continuous quality assurance, leveraging user resources around-the-world, around-the-clock. It has been shown to be effective in automatically characterizing configurations in which failures manifest. The derived information helps developers quickly narrow down the cause of failures which then improves turn around time for fixes. However, this method does not scale well. It requires one to exhaustively test each configuration in the configuration space.In this paper we examine an alternative approach. The idea is to systematically sample the configuration space, test only the selected configurations, and conduct fault characterization on the resulting data. The sampling approach we use is based on calculating a mathematical object called a covering array. We empirically assess the effect of using covering array derived test schedules on the resulting fault characterizations and provide guidelines to practitioners for their use.
Optimal strategies for testing nondeterministic systems
Authors: Nachmanson Lev , Veanes Margus , Schulte Wolfram , Tillmann Nikolai , Grieskamp Wolfgang
Published: October 2004

This paper deals with testing of nondeterministic software systems. We assume that a model of the nondeterministic system is given by a directed graph with two kind of vertices: states and choice points. Choice points represent the nondeterministic behaviour of the implementation under test (IUT). Edges represent transitions. They have costs and probabilities. Test case generation in this setting amounts to generation of a game strategy. The two players are the testing tool (TT) and the IUT. The game explores the graph. The TT leads the IUT by selecting an edge at the state vertices. At the choice points the control goes to the IUT. A game strategy decides which edge should be taken by the TT in each state. This paper presents three novel algorithms 1) to determine an optimal strategy for the bounded reachability game, where optimality means maximizing the probability to reach any of the given final states from a given start state while at the same time minimizing the costs of traversal; 2) to determine a winning strategy for the bounded reachability game, which guarantees that given final vertices are reached, regardless how the IUT reacts; 3) to determine a fast converging edge covering strategy, which guarantees that the probability to cover all edges quickly converges to 1 if TT follows the strategy.
An experimental evaluation of continuous testing during development
Authors: Saff David , Ernst Michael D.
Published: October 2004

Continuous testing uses excess cycles on a developer's workstation to continuously run regression tests in the background, providing rapid feedback about test failures as source code is edited. It is intended to reduce the time and energy required to keep code well-tested and prevent regression errors from persisting uncaught for long periods of time. This paper reports on a controlled human experiment to evaluate whether students using continuous testing are more successful in completing programming assignments. We also summarize users' subjective impressions and discuss why the results may generalize.The experiment indicates that the tool has a statistically significant effect on success in completing a programming task, but no such effect on time worked. Participants using continuous testing were three times more likely to complete the task before the deadline than those without. Participants using continuous compilation were twice as likely to complete the task, providing empirical support to a common feature in modern development environments. Most participants found continuous testing to be useful and believed that it helped them write better code faster, and 90% would recommend the tool to others. The participants did not find the tool distracting, and intuitively developed ways of incorporating the feedback into their workflow.
Test input generation with java PathFinder
Authors: Visser Willem , Pǎsǎreanu Corina S. , Khurshid Sarfraz
Published: October 2004

We show how model checking and symbolic execution can be used to generate test inputs to achieve structural coverage of code that manipulates complex data structures. We focus on obtaining branch-coverage during unit testing of some of the core methods of the red-black tree implementation in the Java
TreeMap
library, using the Java PathFinder model checker. Three different test generation techniques will be introduced and compared, namely, straight model checking of the code, model checking used in a black-box fashion to generate all inputs up to a fixed size, and lastly, model checking used during white-box test input generation. The main contribution of this work is to show how efficient white-box test input generation can be done for code manipulating complex data, taking into account complex method preconditions.
Evolutionary testing in the presence of loop-assigned flags
Authors: Baresel André , Binkley David , Harman Mark , Korel Bogdan
Published: October 2004

Evolutionary testing is an effective technique for automatically generating good quality test data. However, for structural testing, the technique degenerates to random testing in the presence of flag variables, which also present problems for other automated test data generation techniques. Previous work on the flag problem does not address flags assigned in loops.This paper introduces a testability transformation that transforms programs with loop--assigned flags so that existing genetic approaches can be successfully applied. It then presents empirical data demonstrating the effectiveness of the transformation. Untransformed, the genetic algorithm flounders and is unable to find a solution. Two transformations are considered. The first allows the search to find a solution. The second reduces the time taken by an order of magnitude and, more importantly, reduces the slope of the cost increase; thus, greatly increasing the complexity of the problem to which the genetic algorithm can be applied. The paper also presents a second empirical study showing that loop--assigned flags are prevalent in real world code. They account for just under 11% of all flags.
Evolutionary testing of classes
Authors: Tonella Paolo
Published: October 2004

Object oriented programming promotes reuse of classes in multiple contexts. Thus, a class is designed and implemented with several usage scenarios in mind, some of which possibly open and generic. Correspondingly, the unit testing of classes cannot make too strict assumptions on the actual method invocation sequences, since these vary from application to application.In this paper, a genetic algorithm is exploited to automatically produce test cases for the unit testing of classes in a generic usage scenario. Test cases are described by chromosomes, which include information on which objects to create, which methods to invoke and which values to use as inputs. The proposed algorithm mutates them with the aim of maximizing a given coverage measure. The implementation of the algorithm and its application to classes from the Java standard library are described.
The AGEDIS tools for model based testing
Authors: Hartman A. , Nagin K.
Published: October 2004

We describe the tools and interfaces created by the AGEDIS project, a European Commission sponsored project for the creation of a methodology and tools for automated model driven test generation and execution for distributed systems. The project includes an integrated environment for modeling, test generation, test execution, and other test related activities. The tools support a model based testing methodology that features a large degree of automation and also includes a feedback loop integrating coverage and defect analysis tools with the test generator and execution framework. Prototypes of the tools have been tried in industrial settings providing important feedback for the creation of the next generation of tools in this area.
Software assurance by bounded exhaustive testing
Authors: Sullivan Kevin , Yang Jinlin , Coppit David , Khurshid Sarfraz , Jackson Daniel
Published: October 2004

The contribution of this paper is an experiment that shows the potential value of a combination of selective reverse engineering to formal specifications and bounded exhaustive testing to improve the assurance levels of complex software. A key problem is to scale up test input generation so that meaningful results can be obtained. We present an approach, using Alloy and TestEra for test input generation, which we evaluate by experimental application to the Galileo dynamic fault tree analysis tool.
On the analytical comparison of testing techniques
Authors: Morasca Sandro , Serra-Capizzano Stefano
Published: October 2004

We introduce necessary and sufficient conditions for comparing the expected values of the number of failures caused by applications of software testing techniques. Our conditions are based only on the knowledge of a total or even a hierarchical order among the failure rates of the subdomains of a program's input domain. We also prove conditions for comparing the probability of causing at least one failure in three important special cases.
Automating commutativity analysis at the design level
Authors: Dennis Greg , Seater Robert , Rayside Derek , Jackson Daniel
Published: October 2004

Two operations commute if executing them serially in either order results in the same change of state. In a system in which commands may be issued simultaneously by different users, lack of commutativity can result in unpredictable behaviour, even if the commands are serialized, because one user's command may be preempted by another's, and thus executed in an unanticipated state. This paper describes an automated approach to analyzing commutativity. The operations are expressed as constraints in a declarative modelling language such as Alloy, and a constraint solver is used to find violating scenarios. A case study application to the beam scheduling component of a proton therapy machine (originally specified in OCL) revealed several violations of commutativity in which requests from medical technicians in treatment rooms could conflict with the actions of a beam operator in a master control room. Some of the issues involved in automating the analysis for OCL itself are also discussed.
Modeling and verification of an air traffic concept of operations
Authors: Muñoz César A. , Dowek Gilles , Carreño Víctor
Published: October 2004

A high level model of the concept of operations of NASA's Small Aircraft Transportation System for Higher Volume Operations (SATS-HVO) is presented. The model is a non-deterministic, asynchronous transition system. It provides a robust notion of safety that relies on the logic of the concept rather than on physical constraints such as aircraft performances. Several safety properties were established on this model. The modeling and verification effort resulted in the identification of 9 issues, including one major flaw, in the original concept. Ten recommendations were made to the SATS-HVO concept development working group. All the recommendations were accepted and incorporated into the current concept of operations. The model was written in PVS. The verification is performed using an explicit state exploration algorithm written and proven correct in PVS.
Active learning for automatic classification of software behavior
Authors: Bowring James F. , Rehg James M. , Harrold Mary Jean
Published: October 2004

A program's behavior is ultimately the collection of all its executions. This collection is diverse, unpredictable, and generally unbounded. Thus it is especially suited to statistical analysis and machine learning techniques. The primary focus of this paper is on the automatic classification of program behavior using execution data. Prior work on classifiers for software engineering adopts a classical
batch-learning
approach. In contrast, we explore an
active-learning
paradigm for behavior classification. In active learning, the classifier is trained incrementally on a series of labeled data elements. Secondly, we explore the thesis that certain features of program behavior are stochastic processes that exhibit the Markov property, and that the resultant Markov models of individual program executions can be automatically clustered into effective predictors of program behavior. We present a technique that models program executions as Markov models, and a clustering method for Markov models that aggregates multiple program executions into effective behavior classifiers. We evaluate an application of active learning to the efficient refinement of our classifiers by conducting three empirical studies that explore a scenario illustrating automated test plan augmentation.