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.

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.

Abstract In this paper, we present an approach to conformance testing based on abstract state machines (ASMs) that combines model refinement and test execution (RATE) and its application to three case studies. The RATE approach consists in generating test sequences from ASMs and checking the conformance between code and models in multiple iterations. The process follows these steps: (1) model the system as an abstract state machine; (2) validate and verify the model; (3) generate test sequences automatically from the ASM model; (4) execute the tests over the implementation and compute the code coverage; (5) if the coverage is below the desired threshold, then refine the abstract state machine model to add the uncovered functionalities and return to step 2. We have applied the proposed approach in three case studies: a traffic light control system (TLCS), the IEEE 11073‐20601 personal health device (PHD) protocol, and the mechanical ventilator Milano (MVM). By applying RATE, at each refinement level, we have increased code coverage and identified some faults or conformance errors for all the case studies. The fault detection capability of RATE has also been confirmed by mutation analysis, in which we have highlighted that, many mutants can be killed even by the most abstract models.

Embedded systems have become prominent targets for cyberattacks. To exploit firmware’s memory corruption vulnerabilities, cybercriminals harvest reusable code gadgets from the large shared library codebase (e.g., uClibc). Unfortunately, unlike their desktop counterparts, embedded systems lack essential computing resources to enforce security hardening techniques. Recently, we have witnessed a surge of software debloating as a new defense mechanism against code-reuse attacks; it erases unused code to significantly diminish the possibilities of constructing reusable gadgets. Because of the single firmware image update style, static library debloating shows promise to fortify embedded systems without compromising performance and forward compatibility. However, static library debloating on stripped binaries (e.g., firmware’s shared libraries) is still an enormous challenge. In this paper, we show that this challenge is not insurmountable for MIPS firmware. We develop a novel system, named uTrimmer, to identify and wipe out unused basic blocks from shared libraries’ binary code, without causing additional runtime overhead or memory consumption. We propose a new method to identify address-taken blocks/functions, which further help us maintain an inter-procedural control flow graph to conservatively include library code that could be potentially used by firmware. By capturing address access patterns for position-independent code, we circumvent the challenge of determining code-pointer targets and safely eliminate unused code. We run uTrimmer to debloat shared libraries for SPEC CPU2017 benchmarks, popular firmware applications (e.g., Apache, BusyBox, and OpenSSL), and a real-world wireless router firmware image. Our experiments show that not only does uTrimmer deliver functional programs, but also it can cut the exposed code surface and eliminate various reusable code gadgets remarkably. uTrimmer’s debloating capability can compete with the static linking results.

Due to the effectiveness and efficiency in detecting defects caused by interactions of multiple factors, Combinatorial Testing (CT) has received considerable scholarly attention in the last decades. Despite numerous practical test case generation techniques being developed, there remains a paucity of studies addressing the automated oracle generation problem, which holds back the overall automation of CT. As a consequence, much human intervention is inevitable, which is time-consuming and error-prone. This costly manual task also restricts the application of higher testing strength, inhibiting the full exploitation of CT in the industrial practice. To bridge the gap between test designs and fully automated test flows, and to extend the applicability of CT, this paper presents a novel CT methodology, named COMER, to enhance the traditional CT by accounting for Metamorphic Relations (MRs). COMER puts a high priority on generating pairs of test cases which match the input rules of MRs, i.e., the Metamorphic Group (MG), such that the correctness can be automatically determined by verifying whether the outputs of these test cases violate their MRs. As a result, COMER can not only satisfy the t-way coverage as what CT does, but also automatically check test oracle as many violations as possible. Several empirical studies conducted on 31 real-world software projects have shown that COMER increased the number of metamorphic groups by an average factor of 75.9 and also increased the failure detection rate by an average factor of 11.3, when compared with CT, while the overall number of test cases generated by COMER barely increased.

Combinatorial Testing (CT) is an effective testing technique for detecting failures which are triggered by the interactions of various factors that influence the behaviour of a system. Although many studies in CT have designed elaborate test suites (called covering arrays) to systemically check each possible factor interaction, they provide weak support to locate the concrete failure-inducing interactions, i.e., the Minimal Failure-causing Schemas (MFS). To this end, a variety of MFS identification approaches have been proposed. However, as this study reveals, these approaches suffer from various issues such as cannot identify multiple overlapping MFSs, cannot handle MFSs with high degrees, cannot be applied to systems with large number of parameters, etc. These issues are essentially caused by the exponential computing complexity of checking every interaction in the test cases. Therefore, they can only focus on a subset of all the possible interactions, resulting in many interactions unnoticed. Ignoring these unnoticed interactions could potentially cause failures that have never been systematically checked. Hence, it is beneficial for MFS identification approaches to identify these interactions. In order to account for these unnoticed interactions in CT, this study introduces the notion of pending schema, based on which a theoretical framework of CT schemas is established. In particular, we formally define the determinability of a schema in CT with respect to given information; as such, the yet-to-be determined schemas are exactly the pending schemas. The relationships between the different schemas (faulty, healthy, and pending) and test cases are also theoretically analyzed. Based on which, we further propose three formulas, along with three corresponding algorithms, for the identification of the pending schemas in failing test cases, and formally prove their correctness. As a result, we reduce the complexity of obtaining pending schemas with respect to the number of factors that may have influences on the software.

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.

Hunting binary code difference without source code (i.e., binary diffing) has compelling applications in software security. Due to the high variability of binary code, existing solutions have been driven towards measuring semantic similarities from syntactically different code. Since compiler optimization is the most common source contributing to binary code differences in syntax, testing the resilience against the changes caused by different compiler optimization settings has become a standard evaluation step for most binary diffing approaches. For example, 47 top-venue papers in the last 12 years compared different program versions compiled by default optimization levels (e.g., -Ox in GCC and LLVM). Although many of them claim they are immune to compiler transformations, it is yet unclear about their resistance to non-default optimization settings. Especially, we have observed that adversaries explored non-default compiler settings to amplify malware differences.

With the proliferation of the Internet of Things (IoT) devices, Zigbee is widely adopted as a resource-efficient wireless protocol. Recently, severe vulnerabilities in Zigbee protocol implementations have compromised IoT devices from different manufacturers. It becomes imperative to perform security testing on Zigbee protocol implementations. However, it is not a trivial task to apply the existing vulnerability detection techniques such as fuzzing to Zigbee protocol implementations. In particular, it remains a significant obstacle to deal with low-level hardware events. Many existing protocol fuzzing tools lack a proper execution environment for the Zigbee protocol, which communicates via a radio channel instead of the Internet.

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.

Combinatorial testing (CT) has been proven effective in revealing the failures caused by the interaction of factors that affect the behavior of a system. The theory of Minimal Failure-Causing Schema (MFS) has been proposed to isolate the cause of a failure after CT. Most algorithms that aim to identify MFS focus on handling a single fault in the System Under Test (SUT). However, we argue that multiple faults are more common in practice, under which masking effects may be triggered so that some failures cannot be observed. The traditional MFS theory lacks a mechanism to handle such effects; hence, they may incorrectly isolate the MFS. To address this problem, we propose a new MFS model that takes into account multiple faults. We first formally analyze the impact of the multiple faults on existing MFS identifying algorithms, especially in situations where masking effects are triggered by multiple faults. We then develop an approach that can assist traditional algorithms to better handle multiple faults. Empirical studies were conducted using several kinds of open-source software, which showed that multiple faults with masking effects do negatively affect traditional MFS identifying approaches and that our approach can help to alleviate these effects.

Combinatorial testing (CT) seeks to detect potential faults caused by various interactions of factors that can influence the software systems. When applying CT, it is a common practice to first generate a set of test cases to cover each possible interaction and then to identify the failure-inducing interaction after a failure is detected. Although this conventional procedure is simple and forthright, we conjecture that it is not the ideal choice in practice. This is because 1) testers desire to identify the root cause of failures before all the needed test cases are generated and executed 2) the early identified failure-inducing interactions can guide the remaining test case generation so that many unnecessary and invalid test cases can be avoided. For these reasons, we propose a novel CT framework that allows both generation and identification process to interact with each other. As a result, both generation and identification stages will be done more effectively and efficiently. We conducted a series of empirical studies on several open-source software, the results of which show that our framework can identify the failure-inducing interactions more quickly than traditional approaches while requiring fewer test cases.

Today's data center applications are predominantly data-intensive, calling for scaling out the workload to a large number of servers for parallel processing. Unfortunately, the existing scaling laws, notably, Amdahl's and Gustafson's laws are inadequate to characterize the scaling properties of dataintensive workloads. To fill this void, in this paper, we put forward a new scaling model, called In-Proportion and Scale-Out-induced scaling model (IPSO). IPSO generalizes the existing scaling models in two important aspects. First, it accounts for the possible in-proportion scaling, i.e., the scaling of the serial portion of the workload in proportion to the scaling of the parallelizable portion of the workload. Second, it takes into account the possible scaleout-induced scaling, i.e., the scaling of the collective overhead or workload induced by scaling out. IPSO exposes scaling properties of data-intensive workloads, rendering the existing scaling laws its special cases. In particular, IPSO reveals two new pathological scaling properties. Namely, the speedup may level off even in the case of the fixed-time workload underlying Gustafson's law, and it may peak and then fall as the system scales out. Extensive MapReduce and Spark-based case studies demonstrate that IPSO successfully captures diverse scaling properties of dataintensive applications. As a result, it can serve as a diagnostic tool to gain insights on or even uncover counter-intuitive root causes of observed scaling behaviors, especially pathological ones, for data-intensive applications. Finally, preliminary results also demonstrate the promising prospects of IPSO to facilitate effective resource provisioning to achieve the best speedup-versuscost tradeoffs for data-intensive applications.

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.

Model-based testing (MBT) generates tests from behavioral models of systems. When applying MBT to safety-critical systems, one problem is that textual requirements from which the behavior model is generated focus on commonly used scenarios while missing other scenarios that may lead to hazards. We propose to combine MBT with a hazard analysis technique, Hazard and Operability analysis. We first derive guide phrases from original requirements, and use these phrases to extend original requirements by adding more alternative scenarios. Second, we create timed automata from the extended requirements. Third, we validate the automata with model checking. We report a case study where our approach was applied to train control system. We created two groups of automata from original and extended requirements, respectively. We found that the automata created from extended requirements are more likely to avoid problems such as deadlock. Furthermore, tests generated from such models cover more system behaviors.

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.

Concurrent data structures are often tested under stress to detect bugs that can only be exposed by some rare interleavings of instructions. A typical stress test for a concurrent data structure creates a number of threads that repeatedly invoke methods of the target data structure. After a failure is detected by a stress test, developers need to localize the fault causing the failure. However, the execution trace of a failed stress test may be very long, making it time-consuming to replay the failure and localize the fault. In this paper, we present an approach to minimizing stress tests for concurrent data structures. Our approach is to create a smaller test that still produces the same failure by removing some of the threads and/or method invocations in the original stress test. We apply delta debugging to identify the threads and method invocations that are essential for causing the failure. Other threads and method invocations are removed to create a smaller stress test. To increase the chance of triggering the original failure during the execution of the new stress test, we force the new execution to replay the original failed execution trace when possible, and try to guide the execution back to the failed trace when the execution diverges. We describe a tool called TestMinimizer and report the results of an empirical study in which TestMinimizer was applied to 16 real-life concurrent data structures. The results of our evaluation showed that TestMinimizer can effectively and efficiently minimize the stress tests for these concurrent data structures.

Object-oriented analysis and design (OOAD) are challenging activities and crucial to project success. The software engineer needs to understand the application, elicit requirements, and produce a design that fulfills the requirements. These are called the thinking process. Unfortunately, only a fraction of CS/SE curricula teach such a thinking process. Moreover, existing tools only support diagram drawing and diagram management, not the thinking process. As a consequence, few diagrams produced are useful for communication and construction of the working software. This paper presents an integrated development environment (IDE) supporting OOAD thinking process with manual, semi-automatic, and automatic modes. It guides students and software engineers HOW-TO perform OOAD, and lets them learn OOAD and related UML diagrams from using the IDE. Experiments and real-world projects show promising improvement of OOAD performances of students and software engineers.

Big data applications (e.g., Extract, Transform, and Load (ETL) applications) are designed to handle great volumes of data. However, processing such great volumes of data is time-consuming. There is a need to construct small yet effective test data sets during agile development of big data applications.

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.

In server applications, threads are created to handle incoming requests. Since threads consume significant resources including CPU cycles and memory, it is important to control the number of threads that are created. In this paper, we introduce a lightweight, static approach to detecting unbounded thread- instantiation loops that may exist in a server application. The key observation of our approach is that threads are objects of special significance and the decision logic for thread instantiation is typically not complex. Our approach checks loops against some bounded thread-instantiation patterns. A loop is considered bounded if a pattern match is found. Otherwise, it is considered unbounded. Our approach is heuristic by nature. That is, it does not guarantee to detect all the unbounded loops and may report unbounded loops that are actually bounded. To evaluate the effectiveness of our approach, we report an Eclipse plugin called ThreadBoundChecker which implements our approach and an experiment on 24 real-life Java server applications. The results of our evaluation show that our approach can effectively detect unbounded thread-instantiation loops in these applications. In particular, 12 unbounded thread-instantiation loops detected by our approach are confirmed by the original developers.

Recent years have seen a rapid growth in the number of virtual machines and virtual machine images that are managed to support infrastructure as a service (IaaS). For example, Amazon Elastic Compute Cloud (EC2) has 6,521 public virtual machine images. This creates several challenges in management of image files in a cloud computing environment. In particular, a large amount of duplicate data that exists in image files consumes significant storage space. To address this problem, we propose an effective image file storage technique using data deduplication with a modified fixed-size block scheme. When a user requests to store an image file, this technique first calculates the fingerprint for the image file, and then compares the fingerprint with the fingerprints in a fingerprint library. If the fingerprint of the image is already in the library, a pointer to the existing fingerprint is used to store this image. Otherwise this image will be processed using the fixed-size block image segmentation method. We design a metadata format for image files to organize image file blocks and a new MD5 index table of image files to reduce their retrieval time. The experiments show that our technique can significantly reduce the transmission time of image files that have already existed in storage. Also the deletion rate for image groups which have the same version of operating systems but different versions of software applications is up about 58%.

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.

Along with increasing popularity of social websites, online users rely more on the trustworthiness information to make decisions, extract and filter information, and tag and build connections with other users. However, such social network data often suffer from severe data sparsity and are not able to provide users with enough information. Therefore, trust prediction has emerged as an important topic in social network research. Traditional approaches are primarily based on exploring trust graph topology itself. However, research in sociology and our life experience suggest that people who are in the same social circle often exhibit similar behaviors and tastes. To take advantage of the ancillary information for trust prediction, the challenge then becomes what to transfer and how to transfer. In this article, we address this problem by aggregating heterogeneous social networks and propose a novel joint social networks mining (JSNM) method. Our new joint learning model explores the user-group-level similarity between correlated graphs and simultaneously learns the individual graph structure; therefore, the shared structures and patterns from multiple social networks can be utilized to enhance the prediction tasks. As a result, we not only improve the trust prediction in the target graph but also facilitate other information retrieval tasks in the auxiliary graphs. To optimize the proposed objective function, we use the alternative technique to break down the objective function into several manageable subproblems. We further introduce the auxiliary function to solve the optimization problems with rigorously proved convergence. The extensive experiments have been conducted on both synthetic and real- world data. All empirical results demonstrate the effectiveness of our method.

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.

Security testing has gained significant attention recently due to frequent attacks against software systems. This paper presents a trace-based security testing approach. It reuses test cases generated from previous testing methods to produce execution traces. An execution trace is a sequence of program statements exercised by a test case. Each trace is symbolically executed to produce program constraints and security constraints. A program constraint is a constraint imposed by program logic on program variables. A security constraint is a condition on program variables that must be satisfied to ensure system security. A security flaw exists if there is an assignment of values to program variables that satisfies the program constraint but violates the security constraint. This approach detects security flaws even if existing test cases do not trigger them. The novelty of this method is a test model that unifies program constraints and security constraints such that formal reasoning can be applied to detect vulnerabilities. A tool named SecTAC is implemented and applied to 14 benchmark programs and 3 open-source programs. The experiment shows that SecTAC quickly detects all reported vulnerabilities and 13 new ones that have not been detected before.

Abstract Reachability testing is an approach to verifying concurrent programs. During reachability testing, every partially ordered synchronization sequence of a program with a given input is exercised exactly once. In this paper, we present the design and implementation of a distributed reachability testing algorithm for a cluster of workstations. This algorithm allows different test sequences to be exercised concurrently by different workstations without any synchronization, and without any duplication of sequences among workstations. Dynamic load balancing is performed using a work‐stealing scheme. A novel aspect of this scheme is that work‐stealing requests progress in rounds. This round‐based structure identifies overloaded workstations to target for work stealing. Empirical studies show good speedup for four benchmark Java programs and one Lotos specification. Copyright © 2010 John Wiley & Sons, Ltd.

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.

Traditional test case generation methods usually consider coverage criteria like statement or path coverage and ignore security characteristics. The result is that a test case may fail to find vulnerabilities even if it covers the vulnerable statements. However, we argue that existing test cases are still of great value because significant human effort and time have been invested to achieve high coverage criteria. A high coverage indicates a high possibility that vulnerable statements occur in the execution traces of these test cases. Thus existing test cases could guide us to those vulnerable statements. Under this intuition, we present a method of security testing by re-examining existing test cases. The basic idea is to discover two types of constraints in a program: program constraints (PC) and security constraints (SC). The former are the constraints imposed by program statements. For example, an assignment statement i=0 constrains the value of i to be 0. The later are the constraints derived from security concerns. For example, a buffer should never be overflowed. Intuitively, a statement is vulnerable if it can make PCrarrSC be false, which means the program constraints are not strict enough to ensure the security constraints. We design and develop a tool named RETAST to demonstrate our idea and the initial result is promising.

One common approach to test sequence generation for structurally testing concurrent programs involves constructing a reachability graph (RG) and selecting a set of paths from the graph to satisfy some coverage criterion. It is often suggested that test sequence generation methods for testing sequential programs based on a control flow graph (CFG) can also be used to select paths from an RG for testing concurrent programs. However, there is a major difference between these two, as the former suffers from a feasibility problem (i.e., some paths in a CFG may not be feasible at run-time) and the latter does not. As a result, even though test sequence generation methods for sequential programs can be applied to concurrent programs, they may not be efficient. We propose four methods — two based on hot spot prioritization and two based on topological sort — to effectively generate a small set of test sequences that covers all the nodes in an RG. The same methods are also applied to the corresponding dual graph for generating test sequences to cover all the edges. A case study was conducted to demonstrate the use of our methods.

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 Java monitor is a Java class that defines one or more synchronized methods. Unlike a regular object, a Java monitor object is intended to be accessed by multiple threads simultaneously. Thus, testing a Java monitor can be significantly different from testing a regular class. In this paper, we propose a state exploration-based approach to testing a Java monitor. A novel aspect of our approach is that during exploration, threads are introduced on-the-fly, and as needed, to simulate race conditions that can occur when multiple threads try to access a monitor object at the same time. Furthermore, each transition is defined in a way such that the behavior of the threads along each path can be precisely characterized and controlled. We describe a prototype tool called MonitorExplorer and report three case studies that are designed to provide an initial evaluation of our approach

Reachability analysis is a commonly used approach to protocol validation, but it suffers from the well-known state explosion problem. In this paper, we present a new approach to reachability analysis called blocking-based simultaneous reachability analysis (or BSRA). A central notion in BSRA is that of a global blocking point. Instead of exploring every global state, BSRA only explores a set of global blocking points, which usually account for a small portion of the state space. We show how to use BSRA to detect several commonly found logical errors. Our experimental results demonstrate that BSRA can significantly reduce the number of states explored during protocol validation.

One approach to testing concurrent programs, called reachability testing, generates synchronization sequences automatically and on-the-fly, without constructing any static models. In this paper, we present a general execution model for concurrent programs that allows reachability testing to be applied to several commonly used synchronization constructs. We also present a new method for performing reachability testing. This new method guarantees that every partially ordered synchronization sequence will be exercised exactly once without having to save any sequences that have already been exercised. We describe a prototype reachability testing tool called RichTest and report some empirical results, including a comparison between RichTest and a partial order reduction-based tool called VeriSoft. RichTest performed significantly better for the programs in our study

One common approach to protocol validation is reachability analysis, which involves systematically exploring the state space of a protocol. The main challenge of reachability analysis is dealing with the state explosion problem. In this paper, we present a new reachability analysis approach, called blocking-based simultaneous reachability analysis, for protocol validation. This approach has the potential to significantly reduce the number of states that have to be explored but can still be used to detect several logical errors that are commonly found in a protocol.

One common approach to test sequence generation for structurally testing concurrent programs involves constructing a reachability graph (RG) and selecting a set of paths from the graph to satisfy some coverage criterion. It is often suggested that test sequence generation methods for testing sequential programs based on a control flow graph (CFG) can also be used to select paths from a RG for testing concurrent programs. However, there is a major difference between these two, as the former suffers from a feasibility problem (i.e., some paths in a CFG may not be feasible at run-time) and the latter does not. As a result, even though test sequence generation methods for sequential programs can be applied to concurrent programs, they may not be efficient. Moreover, in order to reduce testing effort and costs, it is important to reduce the number of test sequences being generated. Stated differently, we need methods which can generate efficient test sequences to increase the coverage in an effective way. We propose four different methods - two based on hot spot prioritization and two based on topological sort -to effectively generate a small set of test sequences that cover all the nodes in a RG. The same methods are also applied to the corresponding dual graph for generating test sequences to cover all the edges. A case study was conducted to demonstrate the use of our methods.

One approach to testing concurrent programs, called reachability testing, generates test sequences automatically, and on-the-fly, without constructing any static models. To ensure that every partially-ordered synchronization sequence of a program with a given input is exercised exactly once, existing reachability testing algorithms need to save and search through the history of synchronization sequences that have already been exercised, which is impractical for many applications. In this paper, we present a new reachability testing algorithm which does not save any synchronization sequences but still guarantees that every partially-ordered sequence will be exercised exactly once. We describe a reachability testing tool called RichTest and report some empirical results, including a comparison between RichTest and a partial order reduction based tool called VeriSoft. RichTest performed significantly better for the programs in our study.

Concurrent programming is becoming more important in modern software development. However, concurrent programs exhibit non-deterministic behavior, which makes them difficult to test. We describe how to apply reachability testing to semaphore-based multithreaded programs, i.e., programs that use semaphores to synchronize operations on shared data. A novel aspect of reachability testing is that it derives test sequences on-the-fly, avoiding the construction of any static models. Also, our reachability testing algorithms deal with partial orders directly, avoiding the test sequence explosion problem that occurs when independent events are interleaved. We describe a prototype tool called RichTest and report some preliminary results.

An asynchronous message-passing program P is nondeterministic. Given the same input, multiple executions of P may exercise different send/receive event sequences (or SR-sequences) and may even produce different results. Such nondeterminacy makes it difficult to determine the correctness of P. Let X be an input of P. Assume that any execution of P with X terminates. Reachability testing of P with X is to execute, in a systematic manner, all possible SR-sequences of P with X such that the correctness of P with X can be determined. The basic idea of reachability testing is described as follows. We first execute P with X nondeterministically to collect one or more SR-sequences. For each collected SR-sequence, we analyze its race conditions and generate race variants, which are prefixes of other SR-sequences. We replay race variants to generate new SR-sequences. For each new SR-sequence, we repeat the same process until we eventually execute all possible SR-sequences of P with X. We describe an efficient implementation of reachability testing of asynchronous message-passing programs. Our technique deals with partially-ordered SR-sequences and reduces the complexity and redundancy caused by totally-ordered SR-sequences.

Existing reachability analysis techniques for asynchronous message-passing programs assume causal communication, which means that messages sent to a destination are received in the order they are sent. In this paper, we present a new reachability analysis approach, called blocking-based simultaneous reachability analysis (BSRA). BSRA can be applied to asynchronous message-passing programs based on any communication scheme. From a global state g, BSRA allows processes to proceed simultaneously until each of them terminates or is ready to execute a receive operation. Global states reached by such executions from g are called next blocking points of g. For each next blocking point of g, waiting messages and receive operations are matched to produce immediate BSRA-based successor states of g. Intermediate global states from g to each of g's immediate BSRA-based successors are not saved. We describe an algorithm for generating BSRA-based reachability, graphs and show that this algorithm guarantees the detection of deadlocks. Our empirical results indicate that BSRA significantly reduces the number of states in reachability graphs. Extensions of BSRA for partial order reduction and model checking are discussed.

Pairwise testing is a specification-based testing criterion which requires that for each pair of input parameters of a system, every combination of valid values of these two parameters be covered by at least one test case. The authors propose a novel test generation strategy for pairwise testing.