ABSTRACT Practical problems in scientific computation that solve differential equations rarely have explicit exact solutions. Therefore, verifying the correctness of such programs has long been a challenge due to the difficulty of producing expected outputs on test cases. In this paper, the principles of metamorphic testing are applied to verify programs that solve second‐order elliptic differential equations. We present a testing process specifically tailored for the verification testing of scientific computation programs and integrate it to the process of developing scientific software. Unlike existing approaches, we formally derive metamorphic relations from the numerical models of differential equations built in development process of scientific computing programs. The experimental results clearly show that our approach is effective in detecting faults commonly found in scientific computing programs. It outperforms the fault detecting ability of the trend method, which is a traditional testing method for scientific software.

Load balancing plays a crucial role in realising the benefits of microservices, especially to achieve elastic scalability and performance optimisation. However, it is different from load balancing for virtual machines, because workloads on microservices are harder to predict and the number of services in the systems is large. In this paper, we formalise load balance as an emergent property of the microservices ecosystem, and employ scenario calculus to formally analyse the impact of scheduling on service capability and scalability. We discovered that elastic round robin scheduling is highly scalable but the service capability is limited by the slowest microservice instance. In contrast, shortest waiting queue scheduling is less scalable, but the service capability is higher.

Presents the introductory welcome message from the conference proceedings. May include the conference officers' congratulations to all involved with the conference event and publication of the proceedings record.

Presents the introductory welcome message from the conference proceedings. May include the conference officers' congratulations to all involved with the conference event and publication of the proceedings record.

The work reported in this paper is based on our previous work on the formalisation of design patterns and their compositions and instantiations. We define the notion of validity of pattern compositions and analyse whether pattern operators preserve validity. The article is an extended abstract of the paper entitled "On the Composibility of Design Patterns" published in IEEE Transactions on Software Engineering, Vol. 41, No. 11, pp. 1138-1152 (Nov. 2015).

Research on Web Services and Services Computing began shortly after the start of the new millennium and with the first major research conference on the subject, the International Conference on Web Services, starting in 2003. Due to the new and practical utility of Web service technology, many researchers began to work in this field. New ideas, applications and related technologies continue to invigorate this discipline. This special issue of IEEE Transactions on Services Computing considers four such topics that lead to “Advances in Web Services Research”: Cloud Services; Polices and Agreements; Services Engineering; and Service/Process Mining. It consists of the best extended papers from the two premier research conferences on services computing: the 2015 IEEE International Conference on Web Services and the 2015 IEEE Conference on Services Computing.

Software-as-a-Service (SaaS) is a model of cloud computing in which software functions are delivered to the users as services. The past few years have witnessed its global flourishing. In the foreseeable future, SaaS applications will integrate with the Internet of Things, Mobile Computing, Big Data, Wireless Sensor Networks, and many other computing and communication technologies to deliver customizable intelligent services to a vast population. This will give rise to an era of what we call Big SaaS systems of unprecedented complexity and scale. They will have huge numbers of tenants/users interrelated in complex ways. The code will be complex too and require Big Data but provide great value to the customer. With these benefits come great societal risks, however, and there are other drawbacks and challenges. For example, it is difficult to ensure the quality of data and metadata obtained from crowd sourcing and to maintain the integrity of conceptual model. Big SaaS applications will also need to evolve continuously. This paper will discuss how to address these challenges at all stages of the software lifecycle.

Tenant level check pointing is a novel fault-tolerance technique proposed in our previous work for large-scale software-as-a-service applications. This paper evaluates the technique by a theoretical analysis of the technique and an empirical study using workload benchmarks of real large-scale cluster systems. We propose the notion of accumulated delay as a measurement of the performance of check pointing techniques. It reflects the effect of check pointing on system performance as experienced by the end users. Both theoretical analysis and empirical study show that tenant level check pointing significantly outperforms traditional bulk check pointing as measured by the amount of accumulated delays.

With the advent of embedded and mobile computing techniques, software systems are increasingly operated in open and dynamic environments. Such systems desire self-adaptive capabilities. This paper proposes an agent-oriented approach to the modeling and simulation of distributed adaptive systems. The approach enables to construct structural and behavioral models at a high abstraction level, and to validate the models at design stage through model simulation. The modeling language facilitates devising decentralized adaption logic at both component and system levels. Simulation demonstrates how a system dynamically re-organizes in response to the changes in the operating context. Case studies show that our approach can support various self-adaptation mechanisms with which a multi-agent system adjusts to internal failures, unexpected environment, or user's changing requirements.

In real applications, design patterns are almost always to be found composed with each other. It is crucial that these compositions be validated. This paper examines the notion of validity, and develops a formal method for proving or disproving it, in a context where composition is performed with formally defined operators on formally specified patterns. In particular, for validity, we require that pattern compositions preserve the features, semantics and soundness of the composed patterns. The application of the theory is demonstrated by a formal analysis of overlap-based pattern compositions and a case study of a real pattern-oriented software design.

This paper is a report on The 8th IEEE/ACM International Workshop on Automation of Software Test (AST 2013) at the 35th International Conference on Software Engineering (ICSE 2013). It sets a special theme on testing-as-a-service (TaaS). Keynote speech and charette discussions are organized around this special theme. Eighteen full research papers and six short papers will be presented in the two-day workshop. The report will give the background of the workshop and the selection of the special theme, and report on the organization of the workshop. The provisional program will be presented with a list of the sessions and papers to be presented at the workshop.

The accurate description of service semantics plays a crucial role in service discovery, composition and interaction. Most work in this area has been focussed on ontological descriptions, which are searchable and machine-understandable, but do not define service functionality in a verifiable and testable way. Formal specification techniques, having evolved over the past 30 years, can define semantics verifiably and testablly, but they have not yet been applied to service computing because formal specifications are not searchable. There is a huge gap between these two methods of semantics description. In this paper, we bridge the gap. Our technique is to specify services formally in an algebraic specification language and then to extract ontological description as profiles in the language OWL-S, with the associated searchability benefits. We present a prototype tool for performing this transformation and report a case study to demonstrate the feasibility of our approach. The algebraic specification language we use is SOFIA (Service Oriented Formalism in Algebras).

A cloud often provides a RESTful interface with which to access its services. These are usually specified through an open but informal document in the IT industry. There is no agreed standard for the specification of RESTful web services. In this paper, we propose the application of an algebraic method to the formal specification of such services and report a case study with the GoGrid's RESTful API, an industrial real system that provides Infrastructure-as-a-Service. The case study demonstrates that the algebraic approach can provide formal unambiguous specifications that are easy to read and write. It also demonstrates that formalisation can identify and eliminate ambiguity and inconsistency in informal documents.

In a pattern-oriented software design process, design decisions are made by selecting and instantiating appropriate patterns, and composing them together. In our previous work, we enabled these decisions to be formalized by defining a set of operators on patterns with which instantiations and compositions can be represented. In this article, we investigate the algebraic properties of these operators. We provide and prove a complete set of algebraic laws so that equivalence between pattern expressions can be proven. Furthermore, we define an always-terminating normalization of pattern expression to a canonical form which is unique modulo equivalence in first-order logic. By a case study, the pattern-oriented design of an extensible request-handling framework, we demonstrate two practical applications of the algebraic framework. First, we can prove the correctness of a finished design with respect to the design decisions made and the formal specification of the patterns. Second, we can even derive the design from these components.

Due to the time-varying nature of real workload, a large scale computer system has quite a number of idle nodes in most time of operation. They consume energy, but do nothing useful. To save the huge energy waste caused by such active idle nodes, most modern compute nodes provide multiple level dynamic sleep mechanisms to reduce power consumption. However, awaking sleeping nodes takes time, thus affects the response times and performance of the system. A node is deeper in sleep, it consumes less energy, but has longer wakeup latency. This paper proposes a sleep state management model to balance the system's energy consumption and response times. In this model, idle nodes are classified into different groups according to their sleep states. Each group contains nodes of same level of sleep depth and forms a reserve pool of a certain readiness level. In a resource allocation process, nodes in the pool of highest level of readiness are preferentially provided to the application. When the nodes in the pool of the highest readiness level are not sufficient, the nodes in the pool(s) of next level(s) of readiness are allocated. After each allocation and reclaim of nodes, the numbers of nodes in each level of pools are adjusted by changing the sleep depth of the nodes up and down. Thus, the reserve pools can be maintained at all times. Obviously, a key factor that affects the effectiveness of the idle node management is the sizes of the reserve pools. This paper proposes and investigates a self-adaptive approach to this problem so that the sizes of reserve pools are dynamically adjusted according to the applications. Our experiments demonstrated that, by applying our self-adaptive management, the power consumption of idle nodes can be reduced by 84.12% with the cost of slowdown rate being only 8.85%.

Agents are difficult to test because it is notoriously complicated to observe their proactive, autonomous and non-deterministic behaviours and hard to judge their correctness in dynamic environments. This paper proposes a specification-based test automation framework and presents a tool called CATest for testing multi-agent systems (MAS). The agent-based formal specification language SLABS plays three roles in the framework. First, it is used to guide the instrumentation of the agent under test so that its behaviour can be observed and recorded systematically. Second, the correctness of agent's behaviours recorded during test executions are automatically checked against the formal specifications. Finally, the test adequacy is measured by the coverage of the specification and determined according to a set of adequacy criteria specifically designed for testing MAS. An experiment with the tool has demonstrated its capability of detecting faults in MAS.

The author presents a theorem that states that the correctness of a software system can be validated by testing on a finite number of test cases provided that the program and specification are in a learnable set of functions. Moreover, such testing can be performed without writing down a formal specification. This lays a foundation of the current practice of software testing where formal specifications are not available. This theorem implies that what current testing practice lacks is an analysis of the "complexity" of the program to determine a learnable set within which the program and the specification vary.

Design is one of the most elusive tasks in any engineering or creative activity. Design problems have been recognized as wicked or ill-structured. Software design is even more difficult because software is the most complicated man-made artifact and system. One of the key characteristics of design is its creativeness. The question is, therefore, can design benefit from creative computing? In other words, can software design be a successful subject of the research on creative computing? For a long time, people have been search for design methodologies so that design can be mastered through education and learning, even become mechanical and automated. Researchers in the subject area of Computer Aided Design (CAD) have developed software tools to support various design activities in design process but the creativity, which still relies on human beings. The research on software design in the past decades has made some breakthroughs that may lead to a revolutionary new type of software design tools so that software developers can benefit from creative computing. These research results combined with the general theory of design methodologies may make creativity in software design benefit from automation. The following briefly examine such theories and research results in the light of creative computing.

Software testers are confronted with great challenges in testing Web Services (WS) especially when integrating to services owned by other vendors. They must deal with the diversity of implementation techniques used by the other services and to meet a wide range of test requirements. However, they are in lack of software artifacts, the means of control over test executions and observation on the internal behavior of the other services. An automated testing technique must be developed to be capable of testing on-the-fly nonintrusively and nondisruptively. Addressing these problems, this paper proposes a framework of collaborative testing in which test tasks are completed through the collaboration of various test services that are registered, discovered, and invoked at runtime using the ontology of software testing STOWS. The composition of test services is realized by using test brokers, which are also test services but specialized in the coordination of other test services. The ontology can be extended and updated through an ontology management service so that it can support a wide open range of test activities, methods, techniques, and types of software artifacts. The paper presents a prototype implementation of the framework in semantic WS and demonstrates the feasibility of the framework by running examples of building a testing tool as a test service, developing a service for test executions of a WS, and composing existing test services for more complicated testing tasks. Experimental evaluation of the framework has also demonstrated its scalability.

This paper proposes an intelligent broker approach to service composition and collaboration. The broker employs a planner to generate service composition plans according to service usage and workflow knowledge, dynamically searches for services according to the plan, then invokes and coordinates the executions of the selected services at runtime. A prototype called I-Broker has been implemented to support the approach, which can be instantiated by populating the knowledge-base with domain specific knowledge to form domain specific brokers. This paper also reports experiments that evaluate the scalability of the approach.

Check pointing is an effective fault tolerant technique to improve the reliability of large scale parallel computing systems. However, check pointing causes a large number of computation nodes to store a huge amount of data into file system simultaneously. It does not only require a huge storage space to store system state, but also brings a tremendous pressure on the communication network and I/O subsystem because a massive demand of accesses are concentrated in a short period of time. Data compression can reduce the size of checkpoint data to be saved in the file system and to go through the communication network. However, compression induces a huge time overhead especially in large scale parallel systems, which is the main technical barrier of its practical usability. In this paper, we propose a parallel compression check pointing technique to reduce the time overhead in socket-level heterogeneous architectures. It integrates a number of parallel processing techniques, including transmitting checkpoint data between CPU, GPU and file system in double buffered pipelines, aggregating file write operations, SIMD parallel compression algorithm running on GPU, etc. The paper also reports an implementation of the technique on the Tianhe-1 supercomputer system and the evaluation experiments with the system. The experiment data show that the technique is efficient and practically usable.

Meta-modeling plays an important role in model driven software development methodology. In our previous work, a graphic extension of BNF (GEBNF) was proposed to define the abstract syntax of graphic modeling languages. From a GEBNF syntax definition, a first order predicate logic language can be induced so that meta-modeling can be performed formally by specifying a predicate on the domain of syntactically valid models. In this paper, we investigate the theoretical foundation of this meta-modeling approach. We first formally define the semantics of GEBNF syntax definitions as algebras that contain no junk and satisfy constraints derived from GEBNF syntax rules. The semantics of the induced logic is then formally defined by regarding such algebras as models. We then formally prove that well-formed syntax definitions together with syntax morphisms form a category, where syntax morphisms represent the translations between modeling languages. The models (i.e. algebras) in a modeling language and the homomorphisms between them also form a category. Finally, we prove that the functors from GEBNF syntax definitions to the categories of models and to sentences in the induced first order logic form an institution. Therefore, GEBNF and its induced logics form a valid formal specification language for models.

Abstract This paper surveys the research on power management techniques for high‐performance systems. These include both commercial high‐performance clusters and scientific high‐performance computing (HPC) systems. Power consumption has rapidly risen to an intolerable scale. This results in both high operating costs and high failure rates so it is now a major cause for concern. It has imposed new challenges to the development of high‐performance systems. In this paper, we first review the basic mechanisms that underlie power management techniques. Then we survey two fundamental techniques for power management: metrics and profiling. After that, we review the research for the two major types of high‐performance systems: commercial clusters and supercomputers. Based on this, we discuss the new opportunities and problems presented by the recent adoption of virtualization techniques, and again we present the most recent research on this. Finally, we summarize and discuss the future research directions. Copyright © 2010 John Wiley & Sons, Ltd.

A modelling language can be defined by a metamodel in UML class diagram. This paper defines the semantics of such metamodels through two mappings: a signature mapping from metamodels to signatures of first order languages and an axiom mapping from metamodels to sets of axioms over the signature. Valid models, i.e. instances of the metamodel, are therefore mathematical structures in the signature that satisfies the axioms. This semantics definition enables us to analyse the logical consistency and completeness of metamodels. A software tool called LAMBDES is implemented to translate metamodels into first order logic systems and analyse them by employing the theorem prover SPASS. Case studies with the tool detected inconsistency and incompleteness in the metamodel of UML 2.0 and an AspectJ profile.

Generation of adequate test cases is difficult and expensive, especially for testing software systems whose input is structurally complex. This paper presents an approach called data mutation to generating a large number of test data from a few seed test cases. It is inspired by mutation testing methods, but differs from them in the aim and the way that mutation operators are defined and used. While mutation testing is a method for measuring test adequacy, data mutation is a method of test case generation. In traditional mutation testing, mutation operators are used to transform the program under test. In contrast, mutation operators in our approach are applied on input data to generate test cases, hence called data mutation operators. The paper reports a case study with the method on testing an automated modelling tool to illustrate the applicability of the proposed method. Experiment data clearly demonstrate that the method is adequate and cost effective, and able to detect a large proportion of faults. 1

Hong Zhu, S. C. Cheung, Joseph R. Horgan, J. Jenny Li; Guest Editorial to the Special Issue on Automation of Software Testing, The Computer Journal, Volume 52,

The formal specification of design patterns is widely recognised as being vital to their effective and correct use in software development. It can clarify the concepts underlying patterns, eliminate ambiguity and thereby lay a solid foundation for tool support. This paper further advances an approach that uses first order predicate logic to specify design patterns by capturing the dynamic behaviour represented in sequence diagrams. A case study of all 23 patterns in the Gang of Four catalogue demonstrates that it can not only capture dynamic features but also simplify the specification of structural properties.

This paper presents a method of component testing based on algebraic specifications. An algorithm for generating checkable test cases is proposed. A prototype testing tool called CASCAT for testing Java Enterprise Beans is developed. It has the advantages of high degree of automation, which include test case generation, test harness construction and test result checking. It achieves scalability by allowing incremental integration. It also allows testing to focus on a subset of used functions and key properties, thus suitable for component testing. The paper also reports an experimental evaluation of the method and the tool.

Emergent behavior is an essential feature in multi-agent systems and plays a significant role in the applications of agent technology. Because of the huge gap between individual agents' behaviors and those of the whole system, specifying and reasoning about emergent behaviors are notoriously difficult. Simulation has been the essential method to study emergent behaviors in multi-agent systems. In this paper, we report an experimental study of the emergent behaviors of self-organized agent communities, in which emergent behaviors play a crucial role. The experiments confirmed the results of a theoretical analysis of agent communities using a formal theory called scenario calculus. It further provided insight into the dynamic features of the system that were very difficult to obtain by using formal logic, such as the speed of convergence to the emergent states and the relationships between the convergence time and various parameters of self-organized agent communities systems.

Algebraic testing is an automated software testing method based on algebraic formal specifications. It has the advantages of highly automated testing process and independence of the software's implementation details. This paper applies the method to software components. An automated testing tool called CASCAT for Java components is presented. A case study of the tool shows the high fault detecting ability.

This paper presents an automated software tool SQUARE (software quality and architecture modelling environment). It is designed and implemented to support the analysis of software quality from software architectural designs. The tool is based on a model-based method and follows a structured process to systematically derive quality models from software architectural designs by adapting and applying the principles of system hazard analysis. Through identification of potential quality hazards and their consequences, the quality related properties of the components and connectors and the causal relationships between them are derived and then translated into a quality model represented in a graphical notation. The tool enables automated analysis of the quality models in the graphical notation to recognize a number of types of software quality features including quality sensitive components, quality risks and quality trade-off points, etc. A case study with a real e-commerce system is also reported

Testing Web services (WS) application systems is difficult and expensive. It imposes great challenges to existing testing methods, techniques and tools. This paper analyses the problems in testing WS applications and proposes a service oriented framework to solve the problems. It enables collaborations between various parties involved in the development of WS applications via service request and service providing. It also enables special testing services to be provided as WS to perform testing tasks on behalf of their customers. The key technical issues of the approach are discussed

No abstract available.

SLABS is a formal specification language designed for modular and composable specification of multi-agent systems. This paper reports our attempts to support SLABS at the level of programming languages. A programming language, SLABSp, is presented to support two distinguished mechanisms, namely caste and scenario, in caste-centric methodology of agent-oriented software development. Based on Java platform, the SLABSp has been implemented by compiling the programs into Java with the multi-agent runtime environment.

Information timeliness is crucial for media-based Websites. AI though a couple of timeliness design strategies have been developed, timeliness measurement is still in its infancy. Based on our previous research, this paper presents three timeliness measures and reports the empirical validation of them in a case study conducted during the recent Olympic Games.

Scenario has been used to describe agent behaviors in the context of environment situations in the specification languages for agent-based systems, such as SLABS. It becomes an important language facility in the declaration of an agent for specifying its behaviors in its environment. Therefore, towards agent-oriented programming, it is necessary to introduce and implement scenario mechanism in programming languages. This paper reports our attempts to support the language facility from the view of programming languages, and presents an approach to facilitating the scenario mechanism in agent-oriented programming. The basic idea is to extend object-oriented programming language to support agent-oriented programming, where Java is chosen as the base language. Firstly, the language framework of agent-oriented programming, SLABSp is presented, mostly conforming to SLABS, whose syntax is extended based on Java. Scenario mechanism is introduced as the new feature in the programming language. Secondly, the underlying object models are defined to serve as the semantics of the language, where agents are modeled by a couple of objects. A compiler has been built to compile the agent-oriented programs into Java. A running platform has been constructed as the multiagent runtime environment of SLABSp.

In model-driven software development, inconsistency of a model must be detected and eliminated to ensure the quality of the model. This paper investigates the consistency check in the modelling of multi-agent systems (AMS). Consistency constraints are formally defined for the CAMLE language, which was proposed in our previous work for modelling MAS. Uses of the consistency constraints in the implementation of a modelling environment for automatic consistency check and model transformation are discussed.

This paper presents an agent-based software environment for testing Web-based applications. The infrastructure of the system consists of a light weight agent platform that supports agent communication, an ontology of software testing that enables flexible integration of multiple agents, and a formalism using XML to represent both the basic and compound concepts of the ontology. Relations between testing concepts are defined and their properties are analysed. A number of agents are implemented to perform various tasks in testing Web-based applications. Broker agents use the ontology as a means of inferences to manage the knowledge about agents and assign each task to the most appropriate agent.

Quality is a fundamental concept in software and information system development. It is also a complex and elusive concept. A large number of quality models have been developed for understanding, measuring and predicting quality of software and information systems. It has been recognised that quality models should be constructed in accordance to the specific features of the application domain. This paper proposes a systematic method for constructing quality models of information systems. A diagrammatic notation is devised to represent quality models that enclose application specific features. Techniques of hazard analysis for the development and deployment of safety related systems are adapted for deriving quality models from system architectural designs. The method is illustrated by a part of Web-based information systems.

Component-based software development has been viewed as an emerging paradigm of software development. This paper analyzes the requirements of configuration management in component-based development process. Based on the analysis, a prototype configuration management system is proposed to meet the requirements. An example of using the system is also given.

Integration testing plays a crucial role in component-based software development. Complementary to the existing works on the selection of test cases and measurement of test adequacy in integration testing, the paper focuses on questions about how to observe the behaviours of a large and complicated system during dynamic testing. We first analyse the structure of white-box integration testing and propose a family of integration testing methods. We then discuss and formalise the requirements of proper uses of test drivers and component stubs in incremental integration. Finally, we propose a set of axioms for integration testing of concurrent systems.

Being autonomous, proactive and adaptive, an agent-based system may demonstrate emergent behaviours, which are neither designed by the developers nor expected by the users of the system. Whether or not such emergent behaviours are advantageous, methods for the specification of agent behaviours must be developed to enable software engineers to analyse agent-based systems before they are implemented. This paper presents a formal specification language SLABS for agent-based systems. It is a model-based specification language defined based on the notion of agents as encapsulations of data, operations and behaviours. The behaviour of an agent is defined by a set of rules that describe the action/reaction of the agent in certain environment scenarios. The style and expressiveness of the language is demonstrated by examples like ants, personal assistants and speech-act style of agent communications.

Scenario analysis is a vehicle for separating concerns in the elicitation of users' requirements. It is also a means of requirements validation and verification. In the practical application of the method, a number of key activities must be supported by automated tools, which include: (a) the analysis of consistency among scenarios, (b) the analysis of the consistency and completeness of a set of scenarios with respect to requirements models, (c) the synthesis of requirements models from a set of scenarios, and (d) the generation of scenarios from requirements models for requirements validation. This paper presents an automatic toolkit that supports these activities. It adapts the idea of scenario analysis (originally proposed in object-oriented analysis) to the structured analysis method.

Developing software on the bases of formal functional specifications in first order logic and algebraic languages has been the prime endeavour of research on formal methods. But, the industrial development community has been slow to adopt formal methods. Instead, researchers and software engineers in the area of software requirements engineering have advanced various notations for defining user's requirements and systematic methods of developing requirements definitions. There is a wide gap between the current practice of software requirements engineering and the research on formal specification and software formal development. This paper presents the system NDRASS, which supports requirements engineering with the methods of current state of practice and to link such practice to formal methods by automatically generating formal functional specifications in Z.

Software testing can be viewed as an inductive inference process during which the tester attempts to deduce software properties from its behaviour on a finite number of test cases. This paper investigates the foundation of software testing by interpreting the axioms of test adequacy criteria as properties of inductive inference. The interpretation manifests the conservative and simplest hypothesis nature of the induction underlying software testing. It also yields results relating adequate testing to software correctness and reliability. The convergence of the inductive inference process is proved to be a condition of the correctness of tested software. By measuring the convergence according to the probability of an inference result being correct up to a given error rate, a new approach to software reliability estimation is proposed, which differs from existing ones in taking software complexity into account.

Software test adequacy criteria are rules to determine whether a software system has been adequately tested. A central question in the study of test adequacy criteria is how they relate to fault detecting ability. We identify two idealized software testing scenarios. In the first scenario, which we call prior testing scenario, software testers are provided with an adequacy criterion in addition to the software under test. The knowledge of the adequacy criterion is used to generate test cases. In the second scenario, which we call posterior testing scenario, software testers are not provided with the knowledge of adequacy criterion. The criterion is only used to decide when to stop the generation of test cases. In 1993, Frankl and Weyuker proved that the subsume relation between software test adequacy criteria does not guarantee better fault detecting ability in the prior testing scenario. We investigate the posterior testing scenario and prove that in this scenario the subsume relation does guarantee a better fault detecting ability. Two measures of fault detecting ability will be used, the probability of detecting faults and the expected number of exposed errors.

Abstract This paper discusses the transformation power of Burstall and Darlington's folding/unfolding system, i.e. what kind of programs can be derived from a given one. A necessary condition of derivability is proved. The notion of inherent complexity of recursive functions in introduced. A bound on efficiency gain by folding/unfolding transformations is obtained for all reasonable computation models. The well-known partial correctness and incompleteness of the system are corollaries of the result. Examples of underivability are given, e.g. binary searching cannot be derived from linear searching, merge sorting cannot be derived from insert sorting.

Abstract The term ‘inductive inference’ denotes the process of hypothesizing a general rule from examples. It can be considered as the inverse process of program testing, which is a process of sampling the behaviour of a program and gathering confidence in the quality of the software from the samples. As one of the fundamental and ubiquitous components of intelligent behaviour, much effort has been spent on both the theory and practice of inductive inference as a branch of artificial intelligence. In this paper, software testing and inductive inference are reviewed to illustrate how the rich and solid theory of inductive inference can be used to study the foundations of software testing.