Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFinding minimum locating arrays using a CSP solver
114
0
0.0
(
0
)
Added by
Tatsuhiro Tsuchiya
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Combinatorial interaction testing is an efficient software testing strategy. If all interactions among test parameters or factors needed to be covered, the size of a required test suite would be prohibitively large. In contrast, this strategy only requires covering $t$-wise interactions where $t$ is typically very small. As a result, it becomes possible to significantly reduce test suite size. Locating arrays aim to enhance the ability of combinatorial interaction testing. In particular, $(overline{1}, t)$-locating arrays can not only execute all $t$-way interactions but also identify, if any, which of the interactions causes a failure. In spite of this useful property, there is only limited research either on how to generate locating arrays or on their minimum sizes. In this paper, we propose an approach to generating minimum locating arrays. In the approach, the problem of finding a locating array consisting of $N$ tests is represented as a Constraint Satisfaction Problem (CSP) instance, which is in turn solved by a modern CSP solver. The results of using the proposed approach reveal many $(overline{1}, t)$-locating arrays that are smallest known so far. In addition, some of these arrays are proved to be minimum.
rate research
Read More
Context: Combinatorial interaction testing is known to be an efficient testing strategy for computing and information systems. Locating arrays are mathematical objects that are useful for this testing strategy, as they can be used as a test suite that enables fault localization as well as fault detection. In this application, each row of an array is used as an individual test. Objective: This paper proposes an algorithm for constructing locating arrays with a small number of rows. Testing cost increases as the number of tests increases; thus the problem of finding locating arrays of small sizes is of practical importance. Method: The proposed algorithm uses simulation annealing, a meta-heuristic algorithm, to find locating array of a given size. The whole algorithm repeatedly executes the simulated annealing algorithm by dynamically varying the input array size. Results: Experimental results show 1) that the proposed algorithm is able to construct locating arrays for problem instances of large sizes and 2) that, for problem instances for which nontrivial locating arrays are known, the algorithm is often able to generate locating arrays that are smaller than or at least equal to the known arrays. Conclusion: Based on the results, it is concluded that the proposed algorithm can produce small locating arrays and scale to practical problems.
IR-based fault localization approaches achieves promising results when locating faulty files by comparing a bug report with source code. Unfortunately, they become less effective to locate faulty methods. We conduct a preliminary study to explore its challenges, and identify three problems: the semantic gap problem, the representation sparseness problem, and the single revision problem. To tackle these problems, we propose MRAM, a mixed RNN and attention model, which combines bug-fixing features and method structured features to explore both implicit and explicit relevance between methods and bug reports for method level fault localization task. The core ideas of our model are: (1) constructing code revision graphs from code, commits and past bug reports, which reveal the latent relations among methods to augment short methods and as well provide all revisions of code and past fixes to train more accurate models; (2) embedding three method structured features (token sequences, API invocation sequences, and comments) jointly with RNN and soft attention to represent source methods and obtain their implicit relevance with bug reports; and (3) integrating multirevision bug-fixing features, which provide the explicit relevance between bug reports and methods, to improve the performance. We have implemented MRAM and conducted a controlled experiment on five open-source projects. Comparing with stateof-the-art approaches, our MRAM improves MRR values by 3.8- 5.1% (3.7-5.4%) when the dataset contains (does not contain) localized bug reports. Our statistics test shows that our improvements are significant
We study the problem of finding the Lowner-John ellipsoid, i.e., an ellipsoid with minimum volume that contains a given convex set. We reformulate the problem as a generalized copositive program, and use that reformulation to derive tractable semidefinite programming approximations for instances where the set is defined by affine and quadratic inequalities. We prove that, when the underlying set is a polytope, our method never provides an ellipsoid of higher volume than the one obtained by scaling the maximum volume inscribed ellipsoid. We empirically demonstrate that our proposed method generates high-quality solutions faster than solving the problem to optimality. Furthermore, we outperform the existing approximation schemes in terms of solution time and quality. We present applications of our method to obtain piecewise-linear decision rule approximations for dynamic distributionally robust problems with random recourse, and to generate ellipsoidal approximations for the set of reachable states in a linear dynamical system when the set of allowed controls is a polytope.
The ongoing fourth Industrial Revolution depends mainly on robust Industrial Cyber-Physical Systems (ICPS). ICPS includes computing (software and hardware) abilities to control complex physical processes in distributed industrial environments. Industrial agents, originating from the well-established multi-agent systems field, provide complex and cooperative control mechanisms at the software level, allowing us to develop larger and more feature-rich ICPS. The IEEE P2660.1 standardisation project, Recommended Practices on Industrial Agents: Integration of Software Agents and Low Level Automation Functions focuses on identifying Industrial Agent practices that can benefit ICPS systems of the future. A key problem within this project is identifying the best-fit industrial agent practices for a given ICPS. This paper reports on the design and development of a tool to address this challenge. This tool, called IASelect, is built using graph databases and provides the ability to flexibly and visually query a growing repository of industrial agent practices relevant to ICPS. IASelect includes a front-end that allows industry practitioners to interactively identify best-fit practices without having to write manual queries.
We solve the problem of finding interspersed maximal repeats using a suffix array construction. As it is well known, all the functionality of suffix trees can be handled by suffix arrays, gaining practicality. Our solution improves the suffix tree based approaches for the repeat finding problem, being particularly well suited for very large inputs. We prove the corrrectness and complexity of the algorithms.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
