一种基于改进遗传算法的路径测试用例生成方法

采用遗传算法求解路径覆盖的测试用例生成问题是软件测试自动化的研究热点。针对传统标准遗传方法搜索测试用例易产生早熟收敛和收敛速度较慢的不足,设计了自适应的交叉算子和变异算子,提高了算法的全局寻优能力。基于动态生成算法框架,通过程序静态分析,考虑了分支嵌套深度的影响,结合层接近度和分支距离法,提出一种新的适应度函数。实验结果表明,该算法在面向路径的测试用例生成上优于传统方法,提高了测试效率。     

Modelling dynamic memory management in constraint-based testing

Constraint-based testing (CBT) is the process of generating test cases against a testing objective by using constraint solving techniques. When programs contain dynamic memory allocation and loops, constraint reasoning becomes challenging as new variables and new constraints should be created during the test data generation process. In this paper, we address this problem by proposing a new constraint model of C programs based on operators that model dynamic memory management. These operators apply powerful deduction rules on abstract states of the memory enhancing the constraint reasoning process. This allows to automatically generate test data respecting complex coverage objectives. We illustrate our approach on a well-known difficult example program that contains dynamic memory allocation/deallocation, structures and loops. We describe our implementation and provide preliminary experimental results on this example that show the highly deductive potential of the approach.     

AutoGen: Easing model management through two levels of abstraction

Due to its extensive potential applications, model management has attracted many research interests and gained great progress. To provide easy-to-use interfaces, we have proposed a graph transformation-based model management approach that provides intuitive interfaces for manipulation of graphical data models. The approach consists of two levels of graphical operators: low-level customizable operators and high-level generic operators, both of which consist of a set of graph transformation rules. Users need to program or tune the low-level operators for desirable results. To further improve the ease-of-use of the graphical model management, automatic generation of low level of operators is highly desirable. The paper formalizes specifications of low- and high-level operators and proposes a generator to automatically transform high-level operators into low-level operators upon specific input data models. Based on graph transformation theoretical foundation, we design an algorithm for the generator to automatically produce low-level operators from input data models and mappings according to a high-level operator. The generator, called AutoGen, therefore eliminates many tedious specifications and thus eases the use of the graphical model management system.     

Distance semantics for database repair

In many scenarios, a database instance violates a given set of integrity constraints. In such cases, it is often required to repair the database, that is, to restore its consistency. A primary motif behind the repairing approaches is the principle of minimal change, which is the aspiration to keep the recovered data as faithful as possible to the original (inconsistent) database. In this paper, we represent this qualitative principle quantitatively, in terms of distance functions and some underlying metrics, and so introduce a general framework for repairing inconsistent databases by distance-based considerations. The uniform way of representing repairs and their semantics clarifies the essence behind several approaches to consistency restoration in database systems, helps to compare the underlying formalisms, and relates them to existing methods of defining belief revision operators, merging data sets, and integrating information systems.      

Hybrid genetic algorithms for constrained placement problems

When solving real-world problems, often the main task is to find a proper representation for the candidate solutions. Strings of elementary data types with standard genetic operators may tend to create infeasible individuals during the search because of the discrete and often constrained search space. This article introduces a generally applicable representation for 2D combinatorial placement and packing problems. Empirical results are presented for two constrained placement problems, the facility layout problem and the generation of VLSI macro-cell layouts. For multiobjective optimization problems, common approaches often deal with the different objectives in different phases and thus are unable to efficiently solve the global problem. Due to a tree structured genotype representation and hybrid, problem-specific operators, the proposed approach is able to deal with different constraints and objectives in one optimization step     

Performance comparison of enhanced PSO and DE variants for dynamic energy/reserve scheduling in multi-zone electricity market

During the last decade, energy regulatory policies all over the globe have been influenced by the introduction of competition. In a multi-area deregulated power market, competitive bidding and allocation of energy and reserve is crucial for maintaining performance and reliability. The increased penetration of intermittent renewable generation requires for sufficient allocation of reserve services to maintain security and reliability. As a result the market operators and generating companies are opting for market models for joint energy and reserve dispatch with a cost minimization/profit maximization goal. The joint dispatch (JD) problem is more complex than the traditional economic dispatch (ED) due to the additional constraints like the reserve limits, transmission limits, area power balance, energy-reserve coupling constraints and separate sectional price offer curves for both, energy and reserve.The present work proposes a model for the joint static/dynamic dispatch of energy and reserve in deregulated market for multi-area operation using enhanced versions of particle swarm optimization (PSO) and differential evolution (DE). A parameter automation strategy is employed in the classical PSO and DE algorithms (i) to enhance their search capability; (ii) to avoid premature convergence; and (iii) to maintain a balance between global and local search. The performance of enhanced PSO and DE variants is compared for single/multi-area power systems for static/dynamic operation, taking both linear and non-smooth cost functions. The proposed approach is validated on two test systems for different demands, reserve requirements, tie-line capacities and generator outages.     

Automated production of computer generated video image databases with applications in operator training

The use of video disk technology is becoming widespread in industrial training applications. This paper treats one such application, the use of synthetic displays in the training of vehicle operators. MOVIE.BYU, a CGI package for generating continuous tone images was used to prepare and present various views of an airport database. These views were recorded on a videodisk recorder for subsequent playback in a near real-time mode for training use. Once the scenario of views to be created and stored was determined, the process ran automatically without the need for operator intervention.

It is suggested that this approach offers a cost-effective alternative to more traditional approaches to animated scene generation for a significant class of problems.     

A Faà di Bruno Hopf algebra for a group of Fliess operators with applications to feedback

A Faà di Bruno type Hopf algebra is developed for a group of integral operators known as Fliess operators, where operator composition is the group product. Such operators are normally written in terms of generating series over a noncommutative alphabet. Using a general series expansion for the antipode, an explicit formula for the generating series of the compositional inverse operator is derived. The result is applied to analytic nonlinear feedback systems to produce an explicit formula for the feedback product, that is, the generating series for the Fliess operator representation of the closed-loop system written in terms of the generating series of the Fliess operator component systems. This formula is employed to provide a proof that local convergence is preserved under feedback.     

A fuzzy self-tuning parallel genetic algorithm for optimization

The genetic algorithm (GA) is now a very popular tool for solving optimization problems. Each operator has its special approach route to a solution. For example, a GA using crossover as its major operator arrives at solutions depending on its initial conditions. In other words, a GA with multiple operators should be more robust in global search. However, a multiple operator GA needs a large population size thus taking a huge time for evaluation. We therefore apply fuzzy reasoning to give effective operators more opportunity to search while keeping the overall population size constant. We propose a fuzzy self-tuning parallel genetic algorithm (FPGA) for optimization problems. In our test case FPGA there are four operators—crossover, mutation, sub-exchange, and sub-copy. These operators are modified using the eugenic concept under the assumption that the individuals with higher fitness values have a higher probability of breeding new better individuals. All operators are executed in each generation through parallel processing, but the populations of these operators are decided by fuzzy reasoning. The fuzzy reasoning senses the contributions of these operators, and then decides their population sizes. The contribution of each operator is defined as an accumulative increment of fitness value due to each operator's success in searching. We make the assumption that the operators that give higher contribution are more suitable for the typical optimization problem. The fuzzy reasoning is built under this concept and adjusts the population sizes in each generation. As a test case, a FPGA is applied to the optimization of the fuzzy rule set for a model reference adaptive control system. The simulation results show that the FPGA is better at finding optimal solutions than a traditional GA.     

Multiresolution Design of Aperture Operators

The design of an aperture operator is based on adequately constraining the spatial domain and the graylevel range in order to diminish the space of operators and, consequently, the estimation error. The design of a resolution constrained operator is based on adequately combining information from two or more different resolutions and has the same motivation, that is, diminish the space of operators to facilitate design. This paper joins these approaches and studies multiresolution design of aperture operators for grayscale images. Spatial resolution constraint, range resolution constraint and the combination of both constraints are characterized, and the error increase by using the constrained filter in place of the optimal unconstrained one is analyzed. Pyramidal multiresolution design involves applying the resolution constraint approach hierarchically, from the higher to the lower resolution space. These approaches are also characterized and their error increase analyzed. The system that has been implemented to design pyramidal multiresolution operators is described and has its complexity (memory and runtime) analyzed. Several simulations and two applications for deblurring are shown and compared to optimal linear filters. The results confirm the usefulness of the approach.     

Concurrent Java Test Generation as a Search Problem

A Random test generator generates executable tests together with their expected results. In the form of a noise-maker, it seeds the program with conditional scheduling primitives (such as yield()) that may cause context switches. As a result different interleavings are potentially produced in different executions of the program. Determining a-priori the set of seeded locations required for a bug to manifest itself is rarely possible.This work proposes to reformulate random test generation of concurrent Java programs as a search problem. Hence, it allows applying a set of well known search techniques from the domain of AI to the input space of the test generator. By iteratively refining the input parameters fed to the test generator, the search process creates testing scenarios (i.e. interleavings) that maximizes predefined objective functions. We develop geneticFinder, a noise-maker that uses a genetic algorithm as a search method. We demonstrate our approach by maximizing two objective functions: the high manifestation rate of concurrent bugs and the exporting of a high degree of debugging information to the user. Experimental results show our approach is effective.     

HIERARCHICAL ARC CONSISTENCY FOR DISJOINT REAL INTERVALS IN CONSTRAINT LOGIC PROGRAMMING

There have been many proposals for adding sound implementations of numeric processing to Prolog. This paper describes an approach to numeric constraint processing which has been implemented in Echidna, a new constraint logic programming (CLP) language. Echidna uses consistency algorithms which can actively process a wider variety of numeric constraints than most other CLP systems, including constraints containing some common nonlinear functions. A unique feature of Echidna is that it implements domains for real-valued variables with hierarchical data structures and exploits this structure using a hierarchical arc consistency algorithm specialized for numeric constraints. This gives Echidna two advantages over other systems. First, the union of disjoint intervals can be represented directly. Other approaches require trying each disjoint interval in turn during backtrack search. Second, the hierarchical structure facilitates varying the precision of constraint processing. Consequently, it is possible to implement more effective constraint processing control algorithms which avoid unnecessary detailed domain analysis. These advantages distinguish Echidna from other CLP systems for numeric constraint processing.     

Theory of fault-based predicate testing for computer programs

Predicates appear in both the specification and implementation of a program. One approach to software testing, referred to as predicate testing, is to require certain types of tests for a predicate. In this paper, three fault-based testing criteria are defined for compound predicates, which are predicates with one or more AND/OR operators. BOR (boolean operator) testing requires a set of tests to guarantee the detection of (single or multiple) boolean operator faults, including incorrect AND/OR operators and missing/extra NOT operators. BRO (boolean and relational operator) testing requires a set of tests to guarantee the detection of boolean operator faults and relational operator faults (i.e., incorrect relational operators). BRE (boolean and relational expression) testing requires a set of tests to guarantee the detection of boolean operator faults, relational operator faults, and a type of fault involving arithmetical expressions. It is shown that for a compound predicate with n, n>0, AND/OR operators, at most n+2 constraints are needed for BOR testing and at most 2*n+3 constraints for BRO or BRE testing, where each constraint specifies a restriction on the value of each boolean variable or relational expression in the predicate. Algorithms for generating a minimum set of constraints for BOR, BRO, and BRE testing of a compound predicate are given, and the feasibility problem for the generated constraints is discussed. For boolean expressions that contain multiple occurrences of some boolean variables, how to combine BOR testing with the meaningful impact strategy (Weyuker et al., 1994) is described     

Triggered Updates for Temporal Consistency in Real-Time Databases

A real-time database systemhas temporal consistency constraints in addition to timing constraints.The timing constraints require a transaction to be completedby a specified deadline, and the temporal consistency constraintsrequire that temporal data read by a transaction be up-to-date.If a transaction reads out-of-date data, it will become temporallyinconsistent. A real-time database system consists of differenttypes of temporal data objects, including derived objects. Thevalue of a derived object is computed from a set of other objects,known as the read-set of the derived object. The derived objectmay not always reflect the current state of its read-set; a derivedobject can become out-of-date even if its read-set is up-to-date.Any subsequent transaction reading the derived object will thenbecome temporally inconsistent. In this case, in order to readup-to-date objects, a transaction will have to wait until someother transaction updates the out-of-date object. However, indoing so, the waiting transaction may miss its deadline, particularlyif the update is not periodic but instead arrives randomly. Wepropose to update the outdated objects so that not only is thetemporal consistency improved, but also the number of misseddeadlines does not increase significantly, and as a result thereis an overall improvement in the performance of the system. Wepropose, implement and study a novel approach, to be known astriggered updates, to improve temporal consistency in firm real-timedatabase systems when updates are not periodic. We identify propertiesof triggered updates and explain how they work by giving bothan intuitive and a probabilistic analysis. We present strategiesfor generating triggered updates, discuss their suitability invarious contexts and perform a detailed simulation study to evaluatetheir performance. Results show that it is possible to improvetemporal consistency without degrading the timeliness of real-time database systems to a great deal.     

Perturbation of strongly and polynomially stable Riesz-spectral operators

In this paper we consider bounded and relatively bounded finite rank perturbations of a Riesz-spectral operator generating a polynomially stable semigroup of linear operators on a Hilbert space. We concentrate on a commonly encountered situation where the spectrum of the unperturbed operator is contained in the open left half-plane of the complex plane and approaches the imaginary axis asymptotically. We present conditions on the perturbing operator such that the spectrum of the perturbed operator is contained in the open left half-plane of the complex plane and additional conditions for the strong and polynomial stabilities of the perturbed semigroup. We consider two applications of the perturbation results. In the first example we apply the results to the perturbation of a polynomially stabilized one-dimensional wave equation. In the second example we consider the perturbation of a closed-loop system consisting of a distributed parameter system and an observer-based feedback controller solving the robust output regulation problem related to an infinite-dimensional signal generator.     

A Taxonomy of Spatial Data Integrity Constraints

Spatial data quality has become an issue of increasing concern to researchers and practitioners in the field of Spatial Information Systems (SIS). Clearly the results of any spatial analysis are only as good as the data on which it is based. There are a number of significant areas for data quality research in SIS. These include topological consistency; consistency between spatial and attribute data; and consistency between spatial objects representation and their true representation on the ground. The last category may be subdivided into spatial accuracy and attribute accuracy. One approach to improving data quality is the imposition of constraints upon data entered into the database. This paper presents a taxonomy of integrity constraints as they apply to spatial database systems. Taking a cross disciplinary approach it aims to clarify some of the terms used in the database and SIS fields for data integrity management. An overview of spatial data quality concerns is given and each type of constraint is assessed regarding its approach to addressing these concerns. Some indication of an implementation method is also given for each.     

EvoGeneSys,a new evolutionary approach to graph generation

Graphs are widely used to represent complex and structured information of interest in various fields of science and engineering. When using graph representations, problems of special interest often imply searching. For example, searching for the prototypes representing a dataset of graphs or for the graph that optimizes a set of parameters. In any case, it is necessary that the problem solution be expressed in terms of graphs. Therefore, defining effective methods for automatically generating single graphs, or sets of graphs, representing problem solutions, is a key issue. A new evolutionary computation-based approach specifically devised for generating graphs is presented. The method is based on a special data structure, called multilist, which allows the encoding of any type of graph, directed or undirected, with or without attributes. Graph encoding by multilists makes it possible to define effective crossover and mutation operators, overcoming the problems normally encountered when implementing genetic operators on graphs. Further advantages of the proposed approach are that it does not require any problem specific knowledge and it is able to search for graphs whose number of nodes is not known a priori. Three sets of experiments were performed to test the proposed approach and the solutions found were compared with those obtained by other approaches proposed in the literature.     

Patterns of self-stabilization in database consistency maintenance

A substantial portion of the database programming efforts are invested in integrity constraints enforcement. Traditionally, both the constraint semantics and their enforcement were embedded inside application programs. In recent years several studies have dealt with specifying integrity constraints as separate entities (e.g. rules), and relating the database consistency requirements to these rules. In this paper we deal with the complementary issue of stabilizing the database when update exceptions occur. While a simplistic approach is to abort any transaction that inflicts consistency violations, this is not always the desired action. We take advantage of the empirical observation that most of the exception-handling policies follow a small number of behavior patterns. Unlike some previous approaches that base their repair solution on syntactic analysis of the constraints and performance issues, we base our approach on the application semantics as reflected in these behavioral patterns. We describe a model that uses high-level abstractions called stabilizer types denoting these behavior patterns for consistency restorations, whose exact semantics is case dependent. It follows the fault tolerance's self-stabilization approach. An inference mechanism translates these abstractions into executable active rules. This approach provides high-level language to the exception handling portion of the application and substantially reduces the required programming.