摘要 :
The choice of test oracle—the artifact that determines whether an application under test executes correctly—can significantly impact the effectiveness of the testing process. However, despite the prevalence of tools that support...
展开
The choice of test oracle—the artifact that determines whether an application under test executes correctly—can significantly impact the effectiveness of the testing process. However, despite the prevalence of tools that support test input selection, little work exists for supporting oracle creation. We propose a method of supporting test oracle creation that automatically selects the —the set of variables monitored during testing—for expected value test oracles. This approach is based on the use of mutation analysis to rank variables in terms of fault-finding effectiveness, thus automating the selection of the oracle data. Experimental results obtained by employing our method over six industrial systems (while varying test input types and the number of generated mutants) indicate that our method—when paired with test inputs generated either at random or to satisfy specific structural coverage criteria—may be a cost-effective approach for producing small, effective oracle data sets, with fault finding improvements over current industrial best practice of up to 1,435 percent observed (with typical improvements of up to 50 percent).
收起
摘要 :
Metamorphic testing is a promising technique for testing software systems when the oracle problem exists, and has been successfully applied to various application domains and paradigms. An important and essential task in metamorph...
展开
Metamorphic testing is a promising technique for testing software systems when the oracle problem exists, and has been successfully applied to various application domains and paradigms. An important and essential task in metamorphic testing is the identification of metamorphic relations, which, due to the absence of a systematic and specification-based methodology, has often been done in an ad hoc manner-something which has hindered the applicability and effectiveness of metamorphic testing. To address this, a systematic methodology for identifying metamorphic relations based on the category-choice framework, called metric, is introduced in this paper. A tool implementing this methodology has been developed and examined in an experiment to determine the viability and effectiveness of metric, with the results of the experiment confirming that metric is both effective and efficient at identifying metamorphic relations.
收起
摘要 :
The biased oracles, which were originally motivated from cryptographic quantum reductions for the quantum Goldreich-Levin theorem, have been investigated in the contexts of the quantum oracle computation. In this note, we propose ...
展开
The biased oracles, which were originally motivated from cryptographic quantum reductions for the quantum Goldreich-Levin theorem, have been investigated in the contexts of the quantum oracle computation. In this note, we propose the biased-oracle version of the Beaudrap-Cleve-Watrous algorithm using the quantum advice state. As an application of the biased-oracle algorithm, we give a general construction of hardcore predicates for some special quantum one-way function, of which security for classical one-way functions cannot be proved by classical cryptographic reductions under the assumption that some special classical one-way permutation exists.
收起
摘要 :
A blockchain is a form of distributed ledger technology where transactions as data state changes are permanently recorded securely and transparently without the need for third parties. Besides, introducing smart contracts to the b...
展开
A blockchain is a form of distributed ledger technology where transactions as data state changes are permanently recorded securely and transparently without the need for third parties. Besides, introducing smart contracts to the blockchain has added programmability, revolutionizing the software ecosystem toward decentralized applications. Although promising, the usability of smart contracts is primarily limited to on-chain data without access to the external systems (i.e., off-chain) where real-world data and events reside. This connectability to off-chain data for smart contracts and blockchain is an open practical problem referred to as the "oracle problem" and is defined as how real-world data can be transferred into/from the blockchain. Hence, Blockchain oracles are introduced and implemented in the form of application programming interfaces connecting the real world to the blockchain for mitigating such a limitation. This article studies and analyzes how blockchain oracles provide final feedback (i.e., outcome) to smart contracts and survey blockchain oracle technologies and mechanisms regarding data integrity and correctness. Since the existing solutions are extensive in terms of characteristics and usage, we investigate their structure and principles by classifying the blockchain oracle implementation techniques into two major groups voting-based strategies and reputation-based ones. The former mainly relies on participants' stakes for outcome finalization, while the latter considers reputation and performance metrics in conjunction with authenticity-proof mechanisms for data correctness and integrity. We present the result of this classification with a thorough discussion of the state of the art and provide the remaining challenges and future research directions in the end.
收起
摘要 :
Given an unlabeled, unweighted, and undirected graph with n vertices and small (but not necessarily constant) treewidth k, we consider the problem of preprocessing the graph to build space-efficient encodings (oracles) to perform ...
展开
Given an unlabeled, unweighted, and undirected graph with n vertices and small (but not necessarily constant) treewidth k, we consider the problem of preprocessing the graph to build space-efficient encodings (oracles) to perform various queries efficiently. We assume the word RAM model where the size of a word is Ω(log n) bits. The first oracle, we present, is the navigation oracle which facilitates primitive navigation operations of adjacency, neighborhood, and degree queries. By way of an enumeration argument, which is of interest in its own right, we show the space requirement of the oracle is optimal to within lower order terms for all graphs with n vertices and treewidth k. The oracle supports the mentioned queries all in constant worst-case time. The second oracle, we present, is an exact distance oracle which facilitates distance queries between any pair of vertices (i.e., an all-pairs shortest-path oracle). The space requirement of the oracle is also optimal to within lower order terms. Moreover, the distance queries perform in Ω (k~3 log~3 k) time. Particularly, for the class of graphs of popular interest, graphs of bounded treewidth (where k is constant), the distances are reported in constant worst-case time.
收起
摘要 :
Sequence Analysis requires to elaborate data structures, which allow both an efficient storage and use. A new one was introduced in 1999 by Cyril ALLAUZEN, Maxime CROCHEMORE and Mathieu RAFFINOT. This structure is linear on the si...
展开
Sequence Analysis requires to elaborate data structures, which allow both an efficient storage and use. A new one was introduced in 1999 by Cyril ALLAUZEN, Maxime CROCHEMORE and Mathieu RAFFINOT. This structure is linear on the size of the represented word both in time and space. It has the smallest number of states and it accepts at least all substrings of the represented word. This structure is called Factor Orade. Authors developed another structure on the basis of Factor Oracle, which has the same properties except it accepts at least all suffixes instead of all factors of the represented word. This structure is then called Suffix Oracle. The characterization of the language recognized by the Factor/Suffix Oracle of a given word is an open problem, for which we provide a solution. Using this result, we show that these structures may accept an exponential number of words, which are not factors/suffixes of the given word.
收起
摘要 :
Matroid intersection is one of the most powerful frameworks of matroid theory that generalizes various problems in combinatorial optimization. Edmonds' fundamental theorem provides a min-max characterization for the unweighted set...
展开
Matroid intersection is one of the most powerful frameworks of matroid theory that generalizes various problems in combinatorial optimization. Edmonds' fundamental theorem provides a min-max characterization for the unweighted setting, while Frank's weight-splitting theorem provides one for the weighted case. Several efficient algorithms were developed for these problems, all relying on the usage of one of the conventional oracles for both matroids. In the present paper, we consider the tractability of the matroid intersection problem under restricted oracles. In particular, we focus on the rank sum, common independence, and maximum rank oracles. We give a strongly polynomial-time algorithm for weighted matroid intersection under the rank sum oracle. In the common independence oracle model, we prove that the unweighted matroid intersection problem is tractable when one of the matroids is a partition matroid and that even the weighted case is solvable when one of the matroids is an elementary split matroid. Finally, we show that the common independence and maximum rank oracles together are strong enough to realize the steps of our algorithm under the rank sum oracle.
收起
摘要 :
Consider a computability and complexity theory in which the classical set-theoretic oracle to a Turing machine is replaced by a physical process, and oracle queries return measurements of physical behaviour. The idea of such physi...
展开
Consider a computability and complexity theory in which the classical set-theoretic oracle to a Turing machine is replaced by a physical process, and oracle queries return measurements of physical behaviour. The idea of such physical oracles is relevant to many disparate situations, but research has focussed on physical oracles that were classic deterministic experiments which measure physical quantities. In this paper, we broaden the scope of the theory of physical oracles by tackling non-deterministic systems. We examine examples of three types of non-determinism, namely systems that are: (1) physically nondeterministic, as in quantum phenomena; (2) physically deterministic but whose physical theory is non-deterministic, as in statistical mechanics; and (3) physically deterministic but whose computational theory is non-deterministic caused by error margins. Physical oracles that have probabilistic theories we call stochastic physical oracles. We propose a set SPO of axioms for a basic form of stochastic oracles. We prove that Turing machines equipped with a physical oracle satisfying the axioms SPO compute precisely the non-uniform complexity class BPP / / log* in polynomial time. This result of BPP / / log* is a computational limit to a great range of classical and non-classical measurement, and of analogue-digital computation in polynomial time under general conditions.
收起
摘要 :
We study the problem of nonparametric estimation of a probability density of unknown smoothness in L-2(R). Expressing mean integrated squared error (MISE) in the Fourier domain, we show that it is close to mean squared error in th...
展开
We study the problem of nonparametric estimation of a probability density of unknown smoothness in L-2(R). Expressing mean integrated squared error (MISE) in the Fourier domain, we show that it is close to mean squared error in the Gaussian sequence model. Then applying a modified version of Stein's blockwise method, we obtain a linear monotone oracle inequality. Two consequences of this oracle inequality are that the proposed estimator is sharp minimax. adaptive over a scale of Sobolev classes of densities, and that its MISE is asymptotically smaller than or equal to that of kernel density estimators with any bandwidth provided that the kernel belongs to a large class of functions including many standard kernels.
收起
摘要 :
In this paper, we focus on obtaining an accurate classifier in active learning, when there are multiple noisy oracles with different and unknown levels of expertise to provide labels for selected instances. We propose a probabilis...
展开
In this paper, we focus on obtaining an accurate classifier in active learning, when there are multiple noisy oracles with different and unknown levels of expertise to provide labels for selected instances. We propose a probabilistic model of active learning with multiple noisy oracles (PMActive). Our goal is formulized as to select the most reliable oracle and estimate the actual label on training data. When an instance is selected in every round of active learning, we firstly model the accuracies of individual oracles based on observed noisy labels, and select the most reliable oracle of all to provide a label for the instance. After adding the new instance-label pair into the training set, the actual label of the instance is estimated and used for enhancing the performance of the current classifier. The experimental results indicate that the PMActive method can work with different noise levels of oracles. Compared with the baselines which are commonly used in this area of active learning, the PMActive method is superior in obtaining a more accurate classifier.
收起
原文获取