Using genetic algorithms to generate test sequences for complex timed systems

The generation of test data for state-based specifications is a computationally expensive process. This problem is magnified if we consider that time constraints have to be taken into account to govern the transitions of the studied system. The main goal of this paper is to introduce a complete methodology, supported by tools, that addresses this issue by representing the test data generation problem as an optimization problem. We use heuristics to generate test cases. In order to assess the suitability of our approach we consider two different case studies: a communication protocol and the scientific application BIPS3D. We give details concerning how the test case generation problem can be presented as a search problem and automated. Genetic algorithms (GAs) and random search are used to generate test data and evaluate the approach. GAs outperform random search and seem to scale well as the problem size increases. It is worth to mention that we use a very simple fitness function that can be easily adapted to be used with other evolutionary search techniques.     

Verifying data refinements using a model checker

In this paper, we consider how refinements between state-based specifications (e.g., written in Z) can be checked by use of a model checker. Specifically, we are interested in the verification of downward and upward simulations which are the standard approach to verifying refinements in state-based notations. We show how downward and upward simulations can be checked using existing temporal logic model checkers.In particular, we show how the branching time temporal logic CTL can be used to encode the standard simulation conditions. We do this for both a blocking, or guarded, interpretation of operations (often used when specifying reactive systems) as well as the more common non-blocking interpretation of operations used in many state-based specification languages (for modelling sequential systems). The approach is general enough to use with any state-based specification language, and we illustrate how refinements between Z specifications can be checked using the SAL CTL model checker using a small example.     

VbTrace: using view-based and model-driven development to support traceability in process-driven SOAs

In process-driven, service-oriented architectures, there are a number of important factors that hinder the traceability between design and implementation artifacts. First of all, there are no explicit links between process design and implementation languages not only due to the differences of syntax and semantics but also the differences of granularity. The second factor is the complexity caused by tangled process concerns that multiplies the difficulty of analyzing and understanding the trace dependencies. Finally, there is a lack of adequate tool support for establishing and maintaining the trace dependencies between process designs and implementations. We present in this article a view-based, model-driven traceability approach that tackles these challenges. Our approach supports (semi-)automatically eliciting and (semi-)formalizing trace dependencies among process development artifacts at different levels of granularity and abstraction. A proof-of-concept tool support has been realized, and its functionality is illustrated via an industrial case study.     

A Meta-Model for Model-Driven Web Development

Several model-driven development (MDD) techniques for web applications exist; these techniques use meta-models for defining transformations and designing models. In this paper, we propose a meta-model for abstract web applications that can be mapped to multiple platforms. We extend a UML-based model to support specific features of the Web and Web 2.0 as well as to establish a bridge to functional and usability requirements through use cases and user interface (UI) prototypes. The meta-model also helps avoid a common MDD-related problem caused by name-based dependencies. Finally, mappings to a number of specific web platforms are presented in order to validate the appropriateness of the meta-model as an abstract web model.     

Expressing aspectual interactions in requirements engineering: Experiences,problems and solutions

Aspect Oriented Requirements Engineering (AORE) provides support for modularizing crosscutting requirements. In the context of an industrial project in the domain of Slot Machines we needed to perform AORE, with a special emphasis on dependencies and interactions among concerns. We were however unable to find any report of large-scale industrial applications of AORE approaches that treat dependencies and interactions. We therefore evaluated two AORE approaches: Theme/Doc and MDSOCRE, to establish their applicability in our setting. In this paper we report on the limitations of both approaches we encountered and propose extensions that allow them to cope with concern interactions. We also show how these extensions provide the needed expressiveness by applying them to our industrial case study.     

Functional dependencies with null values, fuzzy values, and crispvalues

Based on the concepts of the semantic proximity, we present a definition of the fuzzy functional dependency, We show that the inference rules for fuzzy functional dependencies, which are the same as Armstrong's axioms for the crisp case, are correct and complete. We also show that dependent constraints with dull values constitute a lattice. Functional dependencies in classical relational databases and null functional dependencies can be viewed as a special case of fuzzy functional dependencies. By applying the unified functional dependencies to the relational database design, we can represent the data with fuzzy values, null values and crisp values under relational database management systems, By using fuzzy functional dependencies, we can compress the range of a fuzzy value and make this fuzzy value “clearer”     

An approach to analyzing the software process change impact using process slicing and simulation

When a software process is changed, a project manager needs to perform two types of change impact analysis activities: one for identifying the affected elements of a software process which is affected by the change and the other for analyzing the quantitative impact of the change on the project performance. We propose an approach to obtain the affected elements of a software process using process slicing and developing a simulation model based on the affected elements to quantitatively analyzing the change using simulation. We suggest process slicing to obtain the elements affected by the change. Process slicing identifies the affected elements of a software process using a process dependency model. The process dependency model contains activity control dependencies, artifact information dependencies, and role replacement dependencies. We also suggest transformation algorithms to automatically derive the simulation model from the process model containing the affected elements. The quantitative analysis can be performed by simulating the simulation model. In addition, we provide the tool to support our approach. We perform a case study to validate the usefulness of our approach. The result of the case study shows that our approach can reduce the effort to identify the elements affected by changes and examine alternatives for the project.     

Attribute dependencies for data with grades I*,†

This paper examines attribute dependencies in data that involve grades, such as a grade to which an object is red or a grade to which two objects are similar. We thus extend the classical agenda by allowing graded, or “fuzzy”, attributes instead of Boolean, yes-or-no attributes in case of attribute implications, and allowing approximate match based on degrees of similarity instead of exact match based on equality in case of functional dependencies. In a sense, we move from bivalence, inherently present in the now-available theories of dependencies, to a more flexible setting that involves grades. Such a shift has far-reaching consequences. We argue that a reasonable theory of dependencies may be developed by making use of mathematical fuzzy logic, a recently developed many-valued logic. Namely, the theory of dependencies is then based on a solid logic calculus the same way classical dependencies are based on classical logic. For instance, rather than handling degrees of similarity in an ad hoc manner, we consistently treat them as truth values, the same way as true (match) and false (mismatch) are treated in classical theories. In addition, several notions intuitively embraced in the presence of grades, such as a degree of validity of a particular dependence or a degree of entailment, naturally emerge and receive a conceptually clean treatment in the presented approach. In the first part of this two-part paper, we discuss motivations, provide basic notions of syntax and semantics and develop basic results which include entailment of dependencies, associated closure structures and a logic of dependencies with two versions of completeness theorem.     

A heuristic-based regression test case prioritization approach for object-oriented programs

We propose a novel regression test case prioritization technique based on an analysis of a dependence model for object-oriented programs. We first construct an intermediate dependence model of a program from its source code. When the program is modified, the model is updated to reflect the changes. Our constructed model represents control and data dependencies as well as information pertaining to various types of dependencies arising from object relations such as association, inheritance and aggregation. We determine the affected nodes in the model by constructing the union of the forward slices corresponding to each changed model element. The test cases covering one or more affected nodes are selected for regression testing. The test cases in the selected regression test suite are then prioritized based on their weights and the weight of a test case is determined by assigning weights to the affected nodes. Our experimental results indicate that our approach on an average achieves an increase in the APFD metric value by 9.01 % as compared to a related approach.     

Discovering branching and fractional dependencies in databases

The discovery of dependencies between attributes in databases is an important problem in data mining, and can be applied to facilitate future decision-making. In the present paper some properties of the branching dependencies are examined. We define a minimal branching dependency and we propose an algorithm for finding all minimal branching dependencies between a given set of attributes and a given attribute in a relation of a database. Our examination of the branching dependencies is motivated by their application in a database storing realized sales of products. For example, finding out that arbitrary p products have totally attracted at most q new users can prove to be crucial in supporting the decision making.In addition, we also consider the fractional and the fractional branching dependencies. Some properties of these dependencies are examined. An algorithm for finding all fractional dependencies between a given set of attributes and a given attribute in a database relation is proposed. We examine the general case of an arbitrary relation, as well as a particular case where the problem of discovering the fractional dependencies is considerably simplified.     

基于UML规格说明测试用例生成工具

利用UML状态图,采用基于状态的测试数据生成标准生成测试用例。其中UML状态图是测试用例生成的关键部分,在某种意义上,UML状态图能够图容易生成测试用例。     

Model Checking Downward Simulations

This paper shows how downward simulation can be checked using existing temporal logic model checkers. In particular, we show how the branching time temporal logic CTL can be used to encode the standard downward simulation conditions. We do this for both a blocking, or guarded, interpretation of operations (often used when specifying reactive systems) as well as the more common non-blocking interpretation of operations used in many state-based specification languages (for modelling sequential systems). The approach is general enough to use with any state-based specification language, and any CTL model checker in which the language can be encoded.     

Experience with modularity in consul

The use of modularity in the design and implementation of complex software simplifies the development process, as well as facilitating the construction of customized configurations. This paper describes our experience using modularity in Consul, a communication substrate used for constructing fault-tolerant distributed programs. First, Consul is presented as a case study of how modularity is feasible in both the design and the implementation of such systems. Secondly, general lessons about modularity in fault-tolerant systems based on our experience with Consul are given. Issues that are addressed include deciding how the system is divided into various modules, dealing with problems that result when protocols are combined, and ensuring that the underlying object infrastructure provides adequate support. The key observation is that the modularization process is most affected by dependencies between modules, both direct dependencies caused by one module explicitly using another's operation and indirect dependencies where one module is affected by another without direct interaction. Although our observations are based on designing and implementing Consul, the lessons are applicable to any fault-tolerant distributed system.     

State-based scheduling with tree schedules: analysis and evaluation

Distributed real-time systems require bounded communication delays and achieve them by means of a predictable and verifiable control mechanism for the communication medium. Real-time bus arbitration mechanisms control access to the medium and guarantee bounded communication delays. These arbitration mechanisms can be static dispatch tables or dynamic, algorithmic approaches. In this work, we introduce a real-time bus arbitration mechanism called tree schedules that takes the best parts of both sides: It can be analyzed like static dispatch tables, and it provides a certain degree of flexibility similar to algorithmic approaches. We present tree schedules as a framework to specify real-time traffic and introduce mechanisms to analyze it. We discuss how tree schedules can capture application-specific behavior in a time-triggered state-based supply model by means of conditional branching built into the model. We present analysis results for this model specifically aiming at schedulability in fixed and dynamic priority schemes and waiting time analysis. Finally, we demonstrate the advantages of state-based supply over stateless supply by means of two case studies.     

On the combination of logical and probabilistic models for?information analysis

Formal logical tools are able to provide some amount of reasoning support for information analysis, but are unable to represent uncertainty. Bayesian network tools represent probabilistic and causal information, but in the worst case scale as poorly as some formal logical systems and require specialized expertise to use effectively. We describe a framework for systems that incorporate the advantages of both Bayesian and logical systems. We define a formalism for the conversion of automatically generated natural deduction proof trees into Bayesian networks. We then demonstrate that the merging of such networks with domain-specific causal models forms a consistent Bayesian network with correct values for the formulas derived in the proof. In particular, we show that hard evidential updates in which the premises of a proof are found to be true force the conclusions of the proof to be true with probability one, regardless of any dependencies and prior probability values assumed for the causal model. We provide several examples that demonstrate the generality of the natural deduction system by using inference schemes not supportable directly in Horn clause logic. We compare our approach to other ones, including some that use non-standard logics.     

Design synthesis from interaction and state-based specifications

Interaction-based and state-based modeling are two complementary approaches of behavior modeling. The former focuses on global interactions between system components. The latter concentrates on the internal states of individual components. Both approaches have been proven useful in practice. One challenging and important research objective is to combine the modeling power of both effectively and then use the combination as the basis for automatic design synthesis. We present a combination of interaction-based and state-based modeling, namely, live sequence charts and Z, for system specification. We then propose a way of generating distributed design from the combinations. Our approach handles systems with intensive interactive behaviors as well as complex state structures.     

基于UML活动图生成功能测试线索

测试自动化是提高软件测试效率的重要途径。基于UML模型的面向对象软件测试是当前研究的热点。这些研究大都是类或集成测试,对于如何自动生成较为完整、合理的系统测试用例较少。在总结研究现状的基础上,以应用举例的方式提出一种从描述系统用例问顺序依赖关系的活动图和用例实现的活动图中获取系统功能测试线索的方法。     

Impact analysis of ERP post-implementation modifications: Design,tool support and evaluation

ERP systems evolve in the post-implementation phase because of changing business requirements. Post-implementation changes are likely to decrease the quality of ERP systems and of the data that they use, which negatively impacts organisational performance. We propose a framework for impact analysis of ERP post-implementation modifications. Our framework allows mapping dependencies among ERP system components and, based on these dependencies, automatically assessing the impact of a proposed change on both the design-time structure and run-time landscape of the system through a novel set of impact metrics. The framework also provides semi-automatic support to safely terminating the running process instances affected by change. The framework is evaluated with expert users in two pseudo-real ERP system implementations.     

An empirical study of unspecified dependencies in make-based build systems

Software developers rely on a build system to compile their source code changes and produce deliverables for testing and deployment. Since the full build of large software systems can take hours, the incremental build is a cornerstone of modern build systems. Incremental builds should only recompile deliverables whose dependencies have been changed by a developer. However, in many organizations, such dependencies still are identified by build rules that are specified and maintained (mostly) manually, typically using technologies like make. Incomplete rules lead to unspecified dependencies that can prevent certain deliverables from being rebuilt, yielding incomplete results, which leave sources and deliverables out-of-sync. In this paper, we present a case study on unspecified dependencies in the make-based build systems of the glib, openldap, linux and qt open source projects. To uncover unspecified dependencies in make-based build systems, we use an approach that combines a conceptual model of the dependencies specified in the build system with a concrete model of the files and processes that are actually exercised during the build. Our approach provides an overview of the dependencies that are used throughout the build system and reveals unspecified dependencies that are not yet expressed in the build system rules. During our analysis, we find that unspecified dependencies are common. We identify 6 common causes in more than 1.2 million unspecified dependencies.