Combinatorial Interaction Testing is a black-box testing technique particularly used for highly configurable software systems, which involve a number of factors (and values) that can be combined, according to some constraints. In this context, constrained covering array (CCA) is a central combinatorial problem tasked with building a test suite of minimum size and maximum coverage of the factors' interactions.

The minimum connected dominating set problem (MCDSP) has become increasingly important in recent years due to its applicability to mobile ad hoc networks and sensor grids. This paper presents a restricted swap-based neighborhood (RSN) tailored for solving MCDSP. This novel neighborhood structure is embedded into tabu Search (TS) and a perturbation mechanism is employed to enhance diversification. The proposed RSN-TS algorithm is tested on four sets of public benchmark instances widely used in the literature. The results demonstrate the efficacy of the proposed algorithm in terms of both solution quality and computational efficiency. In particular, the RSN-TS algorithm was able to improve the best known results on 41 out of the 97 problem instances while matching the best known results on all the remaining 56 instances. Furthermore, the article analyzes some key features of the proposed approach in order to identify its critical success factors. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(2), 222–236 2017

In this paper, we propose a hybrid iterated local search (ILS) heuristic, named GPP4G-ILS, to solve the global planning problem of survivable wireless networks. The planning problem of wireless networks is to determine a set of sites among potential sites to install the various network devices in order to cover a given geographical area. It should also make the connections between the devices in accordance with well-defined constraints. The global planning consists in solving this problem without dividing it into several subproblems. The objective is to minimize the cost of the network while maximizing its survivability. The GPP4G-ILS algorithm is a new form of hybridization between the ILS algorithm and the integer linear programing (ILP) method. We propose a configuration that allows to reuse a previously developed ILP algorithm by integrating it in the ILS algorithm. This allows to benefit from the advantages of both methods. The ILS algorithm is used to effectively explore the search space, while the ILP algorithm is used to intensify the solutions obtained. The performance of the algorithm was evaluated using an exact method that generates optimal solutions for small instances. For larger instances, lower bounds have been calculated using a relaxation of the problem. The results show that the proposed algorithm is able to reach solutions that are, on average, within 0.06% of the optimal solutions and 2.43% from the lower bounds for the instances that cannot be solved optimally, within a reduced computation time.

SUMMARY Analyzing and understanding the evolution of large object‐oriented software systems is an important but difficult task in which matching algorithms play a fundamental role. An error‐tolerant graph matching (ETGM) algorithm can identify evolving classes that maintain a stable structure of relations (associations, inheritances, and aggregations) with other classes and thus likely constitute the backbone of the system. Therefore, to study the evolution of class diagrams, we first develop a novel ETGM algorithm, which improves the performance of our previous algorithm. Second, we describe the process of building an oracle to validate the results of our approach to solve the class diagram evolution problem. Third, we report for the new algorithm the impact of its parameters on the F‐measure summarizing precision (quantifying the exactness of the solution) and recall (quantifying the completeness of the solution). Finally, with tuned parameters, we carry out and report an extensive empirical evaluation of our algorithm using small (Rhino), medium (Azureus and ArgoUML), and large systems (Mozilla and Eclipse). We thus show that this novel algorithm is scalable, stable and has better time performance than its earlier version. Copyright © 2010 John Wiley & Sons, Ltd.

Matching algorithms play a fundamental role in many important but difficult software engineering activities, especially design evolution analysis and model comparison. We present MADMatch, a fast and scalable many-to-many approximate diagram matching approach based on an error-tolerant graph matching (ETGM) formulation. Diagrams are represented as graphs, costs are assigned to possible differences between two given graphs, and the goal is to retrieve the cheapest matching. We address the resulting optimization problem with a tabu search enhanced by the novel use of lexical and structural information. Through several case studies with different types of diagrams and tasks, we show that our generic approach obtains better results than dedicated state-of-the-art algorithms, such as AURA, PLTSDiff, or UMLDiff, on the exact same datasets used to introduce (and evaluate) these algorithms.

Wireless local area networks (WLANs) are more deployed today than ever before. However, this rapid growth led to uncoordinated deployment and planning tools are rarely used. In this paper, we first propose a mathematical model to solve the WLAN planning problem considering directional antennas. The problem consists of selecting the location of the access points in the network and selecting the transmit power, the antenna type and its orientation as well as the communication channel of each one. The use of interfering channels is allowed to solve the frequency allocation problem. Since the problem is NP-hard, we propose a two-step tabu-based metaheuristic algorithm to find solutions satisfying a radio coverage constraint, a throughput constraint and an interference level constraint. Our objective is to minimize the cost of the network and to distribute evenly the resources amongst the users. The aim of the first step of the algorithm is to obtain a solution that satisfies all the constraints while the second step focuses on optimizing the previously obtained solution. A new neighborhood, based on radio coverage of an access point, is proposed. The results show that solutions can be obtained with the proposed approach for real-size instances of the problem.

Buffer overflows cause serious problems in different categories of software systems. For example, if present in network or security applications, they can be exploited to gain unauthorized grant or access to the system. In embedded systems, such as avionics or automotive systems, they can be the cause of serious accidents.This paper proposes to combine static analysis and program slicing with evolutionary testing, to detect buffer overflow threats. Static analysis identifies vulnerable statements, while slicing and data dependency analysis identify the relationship between these statements and program or function inputs, thus reducing the search space.To guide the search towards discovering buffer overflow in this work we define three multi-objective fitness functions and compare them on two open-source systems. These functions account for terms such as the statement coverage, the coverage of vulnerable statements, the distance form buffer boundaries and the coverage of unconstrained nodes of the control flow graph.