Machine learning models are increasingly used in critical applications but are mostly ''black boxes'' due to their lack of transparency. Local explanation approaches, such as LIME, address this issue by approximating the behavior of complex models near a test instance using simple, interpretable models. However, these approaches often suffer from instability and poor local fidelity. In this paper, we propose a novel approach called Adversarially Bracketed Local Explanation (ABLE) to address these limitations. Our approach first generates a set of neighborhood points near the test instance, xtest, by adding bounded Gaussian noise. For each neighborhood point D, we apply an adversarial attack to generate an adversarial point A with minimal perturbation that results in a different label than D. A second adversarial attack is then performed on A to generate a point A' that has the same label as D (and thus different than A). The points A and A' form an adversarial pair that brackets the local decision boundary for xtest. We then train a linear model on these adversarial pairs to approximate the local decision boundary. Experimental results on six UCI benchmark datasets across three deep neural network architectures demonstrate that our approach achieves higher stability and fidelity than the state-of-the-art.

Symbolic execution of smart contracts suffers from sequence explosion. Some existing tools limit the sequence length, thus being unable to adequately evaluate some functions. In this article, we propose a symbolic execution approach without limiting the sequence length. In our approach, the symbolic execution process is a two-phase model that maximizes code coverage while reducing the number of sequences to be executed. The first phase executes all sequences up to a length limit to identify the not-fully covered functions, while the second attempts to cover these functions according to state evaluation and a function graph structure. We have developed a tool called SmartExecutor and conducted an experimental evaluation on the SGUARD dataset. The experimental results indicate that compared with state-of-the-art tools, SmartExecutor achieves higher code coverage with less time. It also detects more vulnerabilities than Mythril, a state-of-the-art symbolic execution tool.

In machine learning, hyperparameter optimization (HPO) is essential for effective model training and significantly impacts model performance. Hyperparameters are predefined model settings which fine-tune the model's behavior and are critical to modeling complex data patterns. Traditional HPO approaches such as Grid Search, Random Search, and Bayesian Optimization have been widely used in this field. However, as datasets grow and models increase in complexity, these approaches often require a significant amount of time and resources for HPO. This research introduces a novel approach using t-way testing---a combinatorial approach to software testing used for identifying faults with a test set that covers all t-way interactions---for HPO. T-way testing substantially narrows the search space and effectively covers parameter interactions. Our experimental results show that our approach reduces the number of necessary model evaluations and significantly cuts computational expenses while still outperforming traditional HPO approaches for the models studied in our experiments.

Machine learning (ML)-based models are often black box, making it challenging to understand and interpret their decision-making processes. Surrogate models are constructed to approximate the behavior of a target model and are an essential tool for analyzing black-box models. The construction of a surrogate model typically includes querying the target model with carefully selected data points and using the responses from the target model to infer information about its structure and parameters.

The speaker recognition evaluation is conducted in a framework in which three score distributions and two decision thresholds are employed, and the statistic of interest is an average of the two weighted sums of the probabilities of type I and type II errors at the two thresholds correspondingly. And data dependence caused by multiple use of the same subjects exists ubiquitously in order to generate more samples because of limited resources. Under such circumstances, statistical analysis is carried out. First, the standard error (SE) of measure is estimated using the nonparametric three-sample two-layer bootstrap algorithm on a two-layer data structure constructed after dataset optimization due to data dependence, based upon our prior rigorous statistical research in ROC analysis on large datasets with data dependence. Second, only based on such SEs, can the one-classifier and two-classifier significance testing in statistics be carried out to provide quantitative information in terms of the significance level, i.e.,p-value, while dealing with evaluation and comparison of classifiers. In comparison, the positive correlation coefficient must be taken into account, which is computed using a synchronized resampling algorithm; otherwise, the likelihood of detecting the statistical significance of difference between the performance levels of two classifiers can be wrongly reduced.

A smart contract is often used to handle financial transactions. Unlike traditional programs, contract codes cannot be changed after deployment. It is crucial to test smart contracts thoroughly before deployment. In this paper, we present a fuzzing approach to testing smart contracts. Our fuzzing approach utilizes constraint solving, selective state exploration, and combinatorial testing to improve code coverage. Constraint solving generates test inputs that meet preconditions in a smart contract. Selective state exploration allows different state-dependent behaviors to be exercised while alleviating the state explosion problem. Combinatorial testing is used to exercise parameter interactions in a systematic manner. We implemented our approach in a tool called MagicMirror and evaluated our approach using more than 2,000 contracts. The experimental results show that MagicMirror effectively achieves high code coverage and detects vulnerabilities.

Summary In this paper, we report on applying combinatorial testing to Internet of Things (IoT) home automation hub systems. We detail how to create a dedicated input parameter model of an IoT home automation hub system for use with combinatorial test case generation strategies. Further, we developed an automated test execution framework and two test oracles for evaluation purposes. We applied and evaluated our proposed methodological approach to a real‐world IoT system and analysed the obtained results of various combinatorial test sets with different properties generated based on the derived input model. Additionally, we compare these results to a random testing approach. Our empirical testing evaluations revealed multiple errors in the tested devices and also showed that all considered approaches performed nearly equally well.

Combinatorial testing typically considers a single input model and creates a single test set that achieves$t$-way coverage. This paper addresses the problem of combinatorial test generation for multiple input models with shared parameters. We formally define the problem and propose an efficient approach to generating multiple test sets, one for each input model, that together satisfy$t$-way coverage for all of these input models while minimizing the amount of redundancy between these test sets. We report an experimental evaluation that applies our approach to five real-world applications. The results show that our approach can significantly reduce the amount of redundancy between the test sets generated for multiple input models and perform better than a post-optimization approach.

Combinatorial testing has been shown to be a very effective strategy for software testing. After a failure is detected, the next task is to identify one or more faulty statements in the source code that have caused the failure. In this paper, we present a fault localization approach, called BEN, which produces a ranking of statements in terms of their likelihood of being faulty by leveraging the result of combinatorial testing. BEN consists of two major phases. In the first phase, BEN identifies a combination that is very likely to be failure-inducing. A combination is failure-inducing if it causes any test in which it appears to fail. In the second phase, BEN takes as input a failure-inducing combination identified in the first phase and produces a ranking of statements in terms of their likelihood to be faulty. We conducted an experiment in which our approach was applied to the Siemens suite and four real-world programs, flex, grep, gzip and sed, from Software Infrastructure Repository (SIR). The experimental results show that our approach can effectively and efficiently localize the faulty statements in these programs.

When a failure occurs in a big data application, debugging with the original dataset can be difficult due to the large amount of data being processed. This paper introduces a framework for effectively generating method-level tests to facilitate debugging of big data applications. This is achieved by running a big data application with the original dataset and by recording the inputs to a small number of method executions, which we refer to as method-level tests, that preserve certain code coverage, e.g., edge coverage. The size of each method-level test is further reduced if needed, while maintaining code coverage. When debugging, a developer could inspect the execution of these method-level tests, instead of the entire program execution with the original dataset. We applied the framework to seven algorithms in the WEKA tool. The initial results show that in many cases a small number of method-level tests are sufficient to preserve code coverage. Furthermore, these tests could kill between 57.58% to 91.43% of the mutants generated using a mutation testing tool. This suggests that the framework could significantly reduce the efforts required for debugging big data applications.

Rule-based systems are important in application domains such as artificial intelligence and business rule engines.When translated into an implementation, simple expressions in rules may map to a large body of code that requires testing.We show how rule-based systems may be tested efficiently, using combinatorial methods and a constraint solver in a test method that is pseudo-exhaustive, which we define as exhaustive testing of all combinations of variable values on which a decision is dependent.The method has been implemented in a tool that can be applied to testing and verification for a wide range of applications.

Cryptographic hash functions are security-critical algorithms with many practical applications, notably in digital signatures. Developing an approach to test them can be particularly difficult, and bugs can remain unnoticed for many years. We revisit the NIST hash function competition, which was used to develop the SHA-3 standard, and apply a new testing strategy to all available reference implementations. Motivated by the cryptographic properties that a hash function should satisfy, we develop four tests. The Bit-Contribution Test checks if changes in the message affect the hash value, and the Bit-Exclusion Test checks that changes beyond the last message bit leave the hash value unchanged. We develop the Update Test to verify that messages are processed correctly in chunks, and then use combinatorial testing methods to reduce the test set size by several orders of magnitude while retaining the same fault-detection capability. Our tests detect bugs in 41 of the 86 reference implementations submitted to the SHA-3 competition, including the rediscovery of a bug in all submitted implementations of the SHA-3 finalist BLAKE. This bug remained undiscovered for seven years, and is particularly serious because it provides a simple strategy to modify the message without changing the hash value returned by the implementation. We detect these bugs using a fully-automated testing approach.

BACKGROUND: Cell image segmentation (CIS) is an essential part of quantitative imaging of biological cells. Designing a performance measure and conducting significance testing are critical for evaluating and comparing the CIS algorithms for image-based cell assays in cytometry. Many measures and methods have been proposed and implemented to evaluate segmentation methods. However, computing the standard errors (SE) of the measures and their correlation coefficient is not described, and thus the statistical significance of performance differences between CIS algorithms cannot be assessed. RESULTS: We propose the total error rate (TER), a novel performance measure for segmenting all cells in the supervised evaluation. The TER statistically aggregates all misclassification error rates (MER) by taking cell sizes as weights. The MERs are for segmenting each single cell in the population. The TER is fully supported by the pairwise comparisons of MERs using 106 manually segmented ground-truth cells with different sizes and seven CIS algorithms taken from ImageJ. Further, the SE and 95% confidence interval (CI) of TER are computed based on the SE of MER that is calculated using the bootstrap method. An algorithm for computing the correlation coefficient of TERs between two CIS algorithms is also provided. Hence, the 95% CI error bars can be used to classify CIS algorithms. The SEs of TERs and their correlation coefficient can be employed to conduct the hypothesis testing, while the CIs overlap, to determine the statistical significance of the performance differences between CIS algorithms. CONCLUSIONS: A novel measure TER of CIS is proposed. The TER's SEs and correlation coefficient are computed. Thereafter, CIS algorithms can be evaluated and compared statistically by conducting the significance testing.

The data dependency due to multiple use of the same subjects has impact on the standard error (SE) of the detection cost function (DCF) in speaker recognition evaluation. The DCF is defined as a weighted sum of the probabilities of type I and type II errors at a given threshold. A two-layer data structure is constructed: target scores are grouped into target sets based on the dependency, and likewise for non-target scores. On account of the needed equal probabilities for scores being selected when resampling, target sets must contain the same number of target scores, and so must non-target sets. In addition to the bootstrap method with i.i.d. assumption, the nonparametric two-sample one-layer and two-layer bootstrap methods are carried out based on whether the resampling takes place only on sets, or subsequently on scores within the sets. Due to the stochastic nature of the bootstrap, the distributions of the SEs of the DCF estimated using the three different bootstrap methods are created and compared. After performing hypothesis testing, it is found that data dependency increases not only the SE but also the variation of the SE, and the two-layer bootstrap is more conservative than the one-layer bootstrap. The rationale regarding the different impacts of the three bootstrap methods on the estimated SEs is investigated.

We present a coverage measurement for TLS cipher suites recommendations provided by various regulatory and intelligence organizations such as the IETF, Mozilla, ENISA, German BSI, and USA NSA. These cipher suites are measured and analyzed using a combinatorial approach, which was made feasible via developing the necessary input models. Besides shedding light on the coverage achieved by the proposed recommendations, we discuss implications towards aspects of test quality. One of them relates to the testing of a TLS implementation, where a system designer or tester should expand the TLS cipher suite registry and integrate the information back to the TLS implementation itself such that the (overall) testing effort is reduced.

Summary Modelling a software system is often a challenging prerequisite to automatic test case generation. Modelling the navigation structure of a dynamic web application is particularly challenging because of the presence of a large number of pages that are created dynamically and the difficulty of reaching a dynamic page unless a set of appropriate input values are provided for the parameters. To address the first challenge, some form of abstraction is required to enable scalable modelling. For the second challenge, techniques are required to select appropriate input values for parameters and systematically combine them to reach new pages. This paper presents a combinatorial approach in building a navigation graph for dynamic web applications. The navigation graph can then be used to automatically generate test sequences for testing web applications. The novelty of our approach is twofold. First, we use an abstraction scheme to control the page explosion problem, where pages that are likely to have the same navigation behaviour are grouped together and are represented as a single node in the navigation graph. Second, assuming that values of individual parameters are supplied manually or generated from other techniques, we combine parameter values such that well‐defined combinatorial coverage of input parameter values is achieved. Using combinatorial coverage can significantly reduce the number of requests that have to be submitted while still achieving effective coverage of the navigation structure. We implement our combinatorial approach in a tool,Tansuo, and apply the tool on seven open‐source web applications. We evaluate the effectiveness ofTansuo's exploration process guided byt‐way coverage, fort= 1,2,3, with respect to code coverage, and find that the navigation structure exploration byTansuo, in general, results in high code coverage (more than 80% statement coverage for most of our subject applications when dead code is removed). We compareTansuo's effectiveness with two other navigation graph tools and find thatTansuo is more effective. Our empirical results indicate that using pairwise coverage inTansuo results in the efficient generation of navigation graphs and effective exploration of dynamic web applications. Copyright © 2016 John Wiley & Sons, Ltd.

This poster presents some measures of combinatorial coverage that can be helpful in estimating residual risk related to insufficient testing of rare interactions, and a tool for computing these measures.

Combinatorial testing has been shown to be a very effective testing strategy. An important problem in combinatorial testing is dealing with constraints, i.e., restrictions that must be satisfied in order for a test to be valid. In this paper, we present an efficient algorithm, called IPOG-C, for constraint handling in combinatorial testing. Algorithm IPOG-C modifies an existing combinatorial test generation algorithm called IPOG to support constraints. The major contribution of algorithm IPOG-C is that it includes three optimizations to improve the performance of constraint handling. These optimizations can be generalized to other combinatorial test generation algorithms. We implemented algorithm IPOG-C in a combinatorial test generation tool called ACTS. We report experimental results that demonstrate the effectiveness of algorithm IPOG-C. The three optimizations increased the performance by one or two orders of magnitude for most subject systems in our experiments. Furthermore, a comparison of ACTS to three other tools suggests that ACTS can perform significantly better for systems with more complex constraints.

In this paper, we introduce a combinatorial test generation research tool called Advanced Combinatorial Testing System (or ACTS). ACTS supports t-way combinatorial test generation with several advanced features such as mixed-strength test generation and constraint handling. To facilitate its use and integration with other tools, ACTS provides three types of external interface, including a graphic user interface, a command line interface, and an application programming interface. ACTS is a freely distributed research tool and has been downloaded by more than 1200 companies and organizations.

Combinatorial testing has been shown to be a very effective testing strategy. After a failure is detected, the next task is to identify the fault that causes the failure. In this paper, we present an approach to fault localization that leverages the result of combinatorial testing. Our approach is based on a notion called failure-inducing combinations. A combination is failure-inducing if it causes any test in which it appears to fail. Given a failure-inducing combination, our approach derives a group of tests that are likely to exercise similar traces but produce different outcomes. These tests are then analyzed to locate the faults. We conducted an experiment in which our approach was applied to the Siemens suite as well as the grep program from the SIR repository that has 10068 lines of code. The experimental results show that our approach can effectively and efficiently localize the faults in these programs.

In this paper we present a case study of applying combinatorial testing to test a combinatorial test generation tool called ACTS. The purpose of this study is two-fold. First, we want to gain experience and insights about how to apply combinatorial testing in practice. Second, we want to evaluate the effectiveness of combinatorial testing applied to a real-life system. ACTS has 24637 lines of uncommented code, and provides a command line interface and a fairly sophisticated graphic user interface. The main challenge of this study was to model the input space in terms of a set of parameters and values. Once the model was designed, we generated test cases using ACTS, which were then later used to test ACTS. The results of this study show that input space modeling can be a significant undertaking, and needs to be carefully managed. The results also show that combinatorial testing is effective in terms of achieving high code coverage and fault detection.

A t-way combinatorial test set is designed to detect failures that are triggered by combinations involving no more than t parameters. Assume that we have executed a t-way test set and some tests have failed. A natural question to ask is: What combinations have caused these failures? Identifying such combinations can facilitate the debugging effort, e.g., by reducing the scope of the code that needs to be inspected. In this paper, we present an approach to identifying failure-inducing combinations, i.e., combinations that have caused some tests to fail. Given a t-way test set, our approach first identifies and ranks a set of suspicious combinations, which are candidates that are likely to be failure-inducing combinations. Next, it generates a set of new tests, which can be executed to refine the ranking of suspicious combinations in the next iteration. This process can be repeated until a stopping condition is satisfied. We conducted an experiment in which our approach was applied to several benchmark programs. The experimental results show that our approach can effectively and efficiently identify failure-inducing combinations in these programs.

Many software testing problems involve sequences of events. This paper applies combinatorial methods to testing problems that have n distinct events, where each event occurs exactly once. The methods described in this paper were motivated by testing needs for systems that may accept multiple communication or sensor connections and generate output to several communication links and other interfaces, where it is important to test the order in which connections occur. Although pair wise event order testing (both A followed by B and B followed by A) has been described, our algorithm ensures that any t events will be tested in every possible t-way order.

Combinatorial Testing (CT) is a systematic way of sampling input parameters of the software under test (SUT). A t-way combinatorial test set can exercise all behaviors of the SUT caused by interactions between t input parameters or less. Although combinatorial testing can provide fault detection capability, it is often desirable to isolate the input combinations that cause failures. Isolating these failure-inducing combinations aids developers in understanding the causes of failures. Previous work directly uses classification tree analysis on the results of combinatorial testing to model the failure inducing combinations. But in many scenarios, the effectiveness of classification depends upon whether the analyzed test set is sufficient for classification. In addition, generating combinatorial tests for more-than-6-way combination is generally expensive. To address these issues, we propose an approach that uses existing combinatorial testing results to generate additional tests that enhance the effectiveness of classification. In addition, our approach also includes a technique to reduce the complexity of the resulting classification tree so that developers can understand the nature of failure-inducing combinations. We present the preliminary results of our approach applied on the TCAS benchmark.

Buffer overflow vulnerabilities are program defects that can cause a buffer to overflow at runtime. Many security attacks exploit buffer overflow vulnerabilities to compromise critical data structures. In this paper, we present a black-box testing approach to detecting buffer overflow vulnerabilities. Our approach is motivated by a reflection on how buffer overflow vulnerabilities are exploited in practice. In most cases the attacker can influence the behavior of a target system only by controlling its external parameters. Therefore, launching a successful attack often amounts to a clever way of tweaking the values of external parameters. We simulate the process performed by the attacker, but in a more systematic manner. A novel aspect of our approach is that it adapts a general software testing technique called combinatorial testing to the domain of security testing. In particular, our approach exploits the fact that combinatorial testing often achieves a high level of code coverage. We have implemented our approach in a prototype tool called Tance. The results of applying Tance to five open-source programs show that our approach can be very effective in detecting buffer overflow vulnerabilities.

Regression testing can be among the most challenging of software assurance tasks because program changes often introduce faults, including unexpected interactions among different parts of the code. Unanticipated interactions may also occur when software is modified for a new platform. Techniques such as pairwise testing are not sufficient for detecting these faults, because empirical evidence shows that some errors are triggered only by the interaction of three, four, or more parameters. However, new algorithms and tools make it possible to generate tests that cover complex combinations of values (2-way to 6-way), or to analyze existing test suites and automatically generate tests that provide combinatorial coverage. The key advantage of this approach is that it produces better testing using a fraction of the tests required by other methods.

Modeling the navigation structure of a dynamic Web application is a challenging task because of the presence of dynamic pages. In particular, there are two problems to be dealt with: (1) the page explosion problem, i.e., the number of dynamic pages may be huge or even infinite; and (2) the request generation problem, i.e., many dynamic pages may not be reached unless appropriate user requests are supplied. As a user request typically consists of multiple parameter values, the request generation problem can be further divided into two problems: (1) How to select appropriate values for individual parameters? (2) How to effectively combine individual parameter values to generate requests? This paper presents a combinatorial approach to building a navigation graph. The novelty of our approach is two-fold. First, we use an abstraction scheme to control the page explosion problem. In this scheme, pages that are likely to have the same navigation behavior are grouped together, and are represented as a single node in a navigation graph. Grouping pages reduces and bounds the size of a navigation graph for practical applications. Second, assuming that values of individual parameters are supplied by using other techniques or generated manually by the user, we combine parameter values in a way that achieves a well-defined combinatorial coverage called pairwise coverage. Using pairwise coverage can significantly reduce the number of requests that have to be submitted while still achieving effective coverage of the navigation structure. We report a prototype tool called Tansuo, and apply the tool to five open source Web applications. Our empirical results indicate that Tansuo can efficiently generate Web navigation graphs for these applications.

Abstract This paper presents two strategies for multi‐way testing (i.e.t‐way testing witht>2). The first strategy generalizes an existing strategy, called in‐parameter‐order, from pairwise testing to multi‐way testing. This strategy requires all multi‐way combinations to be explicitly enumerated. When the number of multi‐way combinations is large, however, explicit enumeration can be prohibitive in terms of both the space for storing these combinations and the time needed to enumerate them. To alleviate this problem, the second strategy combines the first strategy with a recursive construction procedure to reduce the number of multi‐way combinations that have to be enumerated. Both strategies are deterministic, i.e. they always produce the same test set for the same system configuration. This paper reports a multi‐way testing tool called FireEye, and provides an analytic and experimental evaluation of the two strategies. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract One approach to testing concurrent programs is called reachability testing, which derives test sequences automatically and on‐the‐fly, without constructing a static model. Existing reachability testing algorithms are exhaustive in that they are intended to exercise all possible synchronization sequences of a concurrent program with a given input. In this paper, we present a new testing strategy, calledt‐way reachability testing, that adopts the dynamic framework of reachability testing but selectively exercises a subset of synchronization sequences. The selection of the synchronization sequences is based on a combinatorial testing strategy calledt‐way testing. We present an algorithm that implementst‐way reachability testing, and report the results of several case studies that were conducted to evaluate its effectiveness. The results indicate thatt‐way reachability testing can substantially reduce the number of synchronization sequences exercised during reachability testing while still effectively detecting faults. Copyright © 2007 John Wiley & Sons, Ltd.

A conformance test is a software assurance test that is applied in order to determine if specification requirements of the software are being met. It is a time-independent model, where the software object is subjected to an a priori known test suite. The reliability of the software is the probability that it will function properly for values in the input space. Because the input space is usually very large, it is impossible to sample all input values, so in order to provide better sampling coverage, the input space is partitioned into homogeneous subspaces. Samples are drawn from each subspace for testing the software. The conformance tests based on these samples are required to pass all tests in the test suite. Based on these data, the classical statistical estimate of reliability is one. Such an estimate may be unrealistic if the sample sizes are not large. Even in such a scenario a nontrivial confidence interval is provided for the reliability.

Abstract Code scalability, crucial on any parallel system, determines how well parallel code avoids becoming a bottleneck as its host computer is made larger. The scalability of computer code can be estimated by statistically designed experiments that empirically approximate a multivariate Taylor expansion of the code's execution response function. Each suspected code bottleneck corresponds to a first‐order term in the expansion, the coefficient for that term indicating how sensitive execution is to changes in the suspect location. However, it is the expansion coefficients for second‐order interactions between code segments and the number of processors that are fundamental to discovering which program elements impede parallel speedup. A new, unified view of these second‐order coefficients yields an informal relative scalability test of high utility in code development. Discussion proceeds through actual examples, including a straightforward illustration of the test applied to SLALOM, a complex, multiphase benchmark. A quick graphical shortcut makes the scalability test readily accessible.

Abstract The synthetic‐perturbation screening (SPS) methodology is based on an empirical approach; SPS introduces artificial perturbations into the MIMD program and captures the effects of such perturbations by using the modern branch of statistics called design of experiments. SPS can provide the basis of a powerful tool for screening MIMD programs for performance bottlenecks. This technique is portable across machines and architectures, and scales extremely well on massively parallel processors. The purpose of this paper is to explain the general approach and to extend it to address specific features that are the main source of poor performance on the shared memory programming model. These include performance degradation due to load imbalance and insufficient parallelism, and overhead introduced by synchronizations and by accessing shared data structures. We illustrate the practicality of SPS by demonstrating its use on two very different case studies: a large image understanding benchmark and a parallel quicksort.

The Synthetic-Perturbation Tuning (SPT) methodology is base d on compirical approach that introduces artificial delays into the MIMD program and captures the effects of such delays by using the modrn branch statistics called design of experiments.