Quantified formulas with Uninterpreted Functions (UFs) over non-linear real arithmetic pose fundamental challenges for Satisfiability Modulo Theories (SMT) solving. Traditional quantifier instantiation methods struggle because they lack semantic understanding of UF constraints, forcing them to search through unbounded solution spaces with limited guidance. We present AquaForte, a framework that leverages Large Language Models to provide semantic guidance for UF instantiation by generating instantiated candidates for function definitions that satisfy the constraints, thereby significantly reducing the search space and complexity for solvers. Our approach preprocesses formulas through constraint separation, uses structured prompts to extract mathematical reasoning from LLMs, and integrates the results with traditional SMT algorithms through adaptive instantiation. AquaForte maintains soundness through systematic validation: LLM-guided instantiations yielding SAT solve the original problem, while UNSAT results generate exclusion clauses for iterative refinement. Completeness is preserved by fallback to traditional solvers augmented with learned constraints. Experimental evaluation on SMT-COMP benchmarks demonstrates that AquaForte solves numerous instances where state-of-the-art solvers like Z3 and CVC5 timeout, with particular effectiveness on satisfiable formulas. Our work shows that LLMs can provide valuable mathematical intuition for symbolic reasoning, establishing a new paradigm for SMT constraint solving.

Abstract Satisfiability Modulo Theories (SMT) solvers are widely used in formal verification. In program analysis, users often encounter queries that differ only by simple syntactic mutations and are logically equivalent. These mutations typically include assertion reordering, symbol renaming, anti-symmetric relation inversion, and commutative operand reordering. However, such minor changes can cause runtimes to vary by orders of magnitude. This variability reduces the predictability required for industrial-scale verification and remains a critical challenge. This paper presents SMTStabilizer, a tool that improves the stability of SMT solvers via context-driven normalization. Since complete input normalization is as hard as the graph isomorphism problem, SMTStabilizer adopts an approximate normalization strategy to avoid the high cost of exact normalization. The framework converts formulas into a structured representation and propagates structural information across nodes, enabling each node to capture its surrounding context. Using this context information, SMTStabilizer derives a consistent ordering over subformulas. This process yields a nearly canonical form that remains consistent across isomorphic inputs. SMTStabilizer also leverages pruning techniques that exploit the syntactic structure of SMT formulas to reduce normalization time. Evaluation on millions of queries using Z3 and cvc5 shows that SMTStabilizer improves solver stability to over $$98\%$$ 98 % under 10 random mutations.

Optimization Modulo Nonlinear Real Arithmetic, abbreviated as OMT(NRA), generally focuses on optimizing a given objective subject to quantifier-free Boolean combinations of primitive constraints, including Boolean variables, polynomial equations, and inequalities. It is widely applicable in areas like program verification, analysis, planning, and so on. The existing solver, OptiMathSAT, officially supporting OMT(NRA), employs an incomplete algorithm. We present a sound and complete algorithm, Optimization Cylindrical Algebraic Covering (OCAC), integrated within the Conflict-Driven Clause Learning (CDCL) framework, specifically tailored for OMT(NRA) problems. We establish the correctness and termination of CDCL(OCAC) and explore alternative approaches using cylindrical algebraic decomposition (CAD) and first-order formulations. Our work includes the development of the first complete OMT solver for NRA, demonstrating significant performance improvements. In benchmarks generated from SMT-LIB instances, our algorithm finds the optimum value in about 150% more instances compared to the current leading solver, OptiMathSAT.

Constraint programming (CP) is a crucial technology for solving real-world constraint optimization problems (COPs), with the advantages of rich modeling semantics and high solving efficiency.Using large language models (LLMs) to generate formal modeling automatically for COPs is becoming a promising approach, which aims to build trustworthy neuro-symbolic AI with the help of symbolic solvers.However, CP has received less attention compared to works based on operations research (OR) models.We introduce ConstraintLLM, the first LLM specifically designed for CP modeling, which is trained on an open-source LLM with multiinstruction supervised fine-tuning.We propose the Constraint-Aware Retrieval Module (CARM) to increase the in-context learning capabilities, which is integrated in a Tree-of-Thoughts (ToT) framework with guided selfcorrection mechanism.Moreover, we construct and release IndusCP, the first industriallevel benchmark for CP modeling, which contains 140 challenging tasks from various domains.Our experiments demonstrate that ConstraintLLM achieves state-of-the-art solving accuracy across multiple benchmarks and outperforms the baselines by 2x on the new IndusCP benchmark.

Android apps are getting bloated by continuously integrating possibly unnecessary functional modules. This trend of software bloat negatively impacts the performance of static analysis tools. As a result, analysis reports are more likely to contain false positives and experience analysis timeouts. Consequently, developers are forced to manually inspect and troubleshoot errors, as well as restart the analysis process, making analyzers more time-consuming and less user-friendly. However, existing approaches for Android app debloating almost only consider how to remove redundant code elements or functional features from the perspective of users, thus they are unsuitable for the analyzer-oriented app debloating task in most cases. To fill this gap, we propose an Android app debloating approach that employs a novel Multi-layer Dependence Graph (MDG) structure to represent the app under analysis. We hierarchically construct the MDG by sequentially analyzing and capturing dependence at the class, method, and statement levels. Throughout this process, we dynamically identify hotspot classes and narrow down the scope for further dependence extraction, thereby alleviating the challenge of a too complicated graph structure caused by the excessive app size. We implement our approach as the tool FlowSlicer, a novel MDG-based static Android app debloater. We evaluate FlowSlicer by utilizing it to debloat the input app first and then observing the performance difference of two analysis processes which accept the original and the debloated app as input respectively. The evaluation is performed on both the hand-crafted and the real-world apps in our benchmark. Our results show that FlowSlicer is not only capable of effectively debloating Android apps but also enhancing the performance of static analyzers. For instance, cooperating with FlowSlicer, the analyzer FlowDroid could detect 212 more leaks in real-world apps in our benchmark.

Performance analysis is essential to ensure the non-functional performance requirements of a software system. However, existing runtime-based approaches suffer from the issues of efficiency and platform dependency. In this paper, we investigate the effectiveness of using the mems value to statically estimate the program performance. The mems value, originally proposed by Donald Knuth, is a static and architecture-independent metric used to measure memory access, to estimate program performance statically. We developed an instrumentation tool to record the control flow and measure the mems value by rewriting the source code. Experimental results across ten classical algorithm programs show that execution paths of a program with larger mems values consistently exhibit lower efficiency. Whereas the correlation weakens among different programs. This indicates that the mems maric is best suited for comparing the performance of various paths in the same program.

Due to the non-determinism of thread interleaving, predicting concurrency bugs has long been an extremely difficult task. Recently, several sound bug-detecting approaches were proposed. These approaches are based on local search, i.e., mutating the sequential order of the observed trace and predicting whether the mutated sequential order can trigger a bug. Surprisingly, during this process, they never consider reordering the data flow of the pointers, which can be the key point to detecting many complex bugs. To alleviate this weakness, we propose a new flow-sensitive point-to analysis technique ConPTA to help actively reorder the pointer flow during the sequential order mutation process. Based on ConPTA, we further propose a new sound predictive bug-detecting approach Eagle to predict four types of concurrency bugs. They are null pointer dereference (NPD), uninitialized pointer use (UPU), use after free (UAF), and double free (DF). By actively reordering the pointer flow, Eagle can explore a larger search space of the thread interleaving during the mutation and thus detect more concurrency bugs. Our evaluation of Eagle on 10 real-world multi-threaded programs shows that Eagle significantly outperforms four state-of-the-art bug-detecting approaches UFO, ConVul, ConVulPOE and Period in both effectiveness and efficiency.

During software evolution, it is advocated that test code should co-evolve with production code. In real development scenarios, test updating may lag behind production code changing, which may cause compilation failure or bring other troubles. Existing techniques based on pre-trained language models can be directly adopted to repair obsolete tests caused by such unsynchronized code changes, especially syntactic-related ones. However, the lack of task-oriented contextual information affects the repair accuracy on large-scale projects. Starting from an obsolete test, the key challenging task is precisely identifying and constructing Test-Repair-Oriented Contexts (TROCtxs) from the whole repository within a limited token size.In this paper, we propose Synter (SYNtactic-breaking- changes-induced TEst Repair), a novel approach based on LLMs to automatically repair obsolete test cases via precise and concise TROCtxs construction. Inspired by developers’ programming practices, we design three types of TROCtx: class context, usage context, and environment context. Given an obsolete test case to repair, Synter firstly collects the related code information for each type of TROCtx through static analysis techniques automatically. Then, it generates reranking queries to identify the most relevant TROCtxs, which will be taken as the repair-required key contexts and be input to the large language model for the final test repair.To evaluate the effectiveness of Synter, we construct a benchmark dataset that contains a set of obsolete tests caused by syntactic breaking changes. The experimental results show that Synter outperforms baseline approaches both on textual- and intent-matching metrics. With the augmentation of constructed TROCtxs, hallucinations are reduced by 57.1%.

Android is based on an event-driven model, which hides the main method, and is driven by the lifecycle methods and listeners from user interaction. FlowDroid, constructs a dummy main method statically emulating the lifecycle methods. The dummy main method has been widely used by FlowDroid and also other Android analyzers as their entry points. However, the existing dummy main method is not designed for path-sensitive analysis, whose paths may be unsatisfiable. Thus, when using original dummy main methods, path-sensitive analysis, e.g., symbolic execution, may suffer from infeasible paths. In this paper, we present DMMPP, the first dummy main method generator for Android applications with path-sensitive predicates, and the corresponding path condition is satisfiable. DMMPP constructs dummy main methods for the four types of components in an application with a more realistic simulation for the lifecycle methods. The experiment demonstrates the benefits of our tool for path-sensitive analyzers, improving 28.5 times more explored paths with a low time overhead.

The widely-used Compiler-Based Tools (CBT), such as static analyzers, process input source code using data structures inside a compiler. CBTs can be invoked together with compilers by injecting the compilation process. However, it is seldom the best practice for the inconvenience of running various CBTs, the unexpected failures due to interference with compilers, and the efficiency degradation under compilation dependencies. To fill this gap, we propose Panda, an efficient scheduler for C/C++ CBTs. It executes various CBTs in a compilation-independent manner to avoid mutual interference with the build system, and parallels the process based on an estimated makespan to improve the execution efficiency. The assessment indicates that Panda can reduce the total execution time by 19%–47% compared with compilation-coupled execution, with an average 39.03×–52.15× speedup with 64 parallel workers.

Given a known buggy code snippet, searching for similar patterns in a target project to detect unknown bugs is a reasonable approach. In practice, a search unit, such as a function, may appear quite different from the buggy snippet but actually contains a similar buggy substructure. Utilizing subgraph isomorphism identification can effectively hunt potential bugs by checking whether an approximate copy of the buggy subgraph exists within the target code graphs. Regrettably, subgraph isomorphism identification is an NP-complete problem.

The paper presents an attempt to bridge the gap between machine learning and symbolic reasoning. We build graph neural networks (GNNs) to predict the solution of the Maximum Satisfiability (MaxSAT) problem, an optimization variant of SAT. Two closely related graph representations are adopted, and we prove their theoretical equivalence. We also show that GNNs can achieve attractive performance to solve hard MaxSAT problems in certain distributions even compared with state-of-the-art solvers through experimental evaluation.

Binding calls of embedded scripting engines introduce a serious attack surface in PDF readers. To effectively test binding calls, the knowledge of parameter types is necessary. Unfortunately, due to the absence or incompleteness of documentation and the lack of sufficient samples, automatic type reasoning for binding call parameters is a big challenge. In this paper, we propose a novel operand-variation-oriented differential analysis approach, which automatically extracts features from execution traces as oracles for inferring parameter types. In particular, the parameter types of a binding call are inferred by executing the binding call with different values of different types and investigating which types cause an expected effect on the instruction operands. The inferred type information is used to guide the test generation in fuzzing. Through the evaluation on two popular PDF readers (Adobe Reader and Foxit Reader), we demonstrated the accuracy of our type reasoning method and the effectiveness of the inferred type information for improving fuzzing in both code coverage and vulnerability discovery. We found 38 previously unknown security vulnerabilities, 26 of which were certified with CVE numbers.

Automatic static analysis tools (ASATs) detect source code violations to static analysis rules and are usually used as a guard for source code quality. The adoption of ASATs, however, is often challenged because of several problems such as a large number of false alarms, invalid rule priorities, and inappropriate rule configurations. Research has shown that tracking the history of the violations is a promising way to solve the above problems because the facts of violation fixing may reflect the developers' subjective expectations on the violation detection results. Precisely identifying the revisions that induce or fix a violation is however challenging because of the imprecise matching of violations between code revisions and ignorance of merge commits in the maintenance history. In this paper, we propose ViolationTracker, an approach to precisely matching the violation instances between adjacent revisions and building the life cycle of violations with the identification of inducing, fixing, deleting, and reopening of each violation case. The approach employs code entity anchoring heuristics for violation matching and considers merge commits that used to be ignored in existing research. We evaluate ViolationTracker with a manually-validated dataset that consists of 500 violation instances and 158 threads of 30 violation cases with detailed evolution history from open-source projects. Violation Tracker achieves over 93 % precision and 98 % recall on violation matching, outperforming the state-of-the-art approach, and 99.4 % precision on rebuilding the histories of violation cases. We also show that ViolationTracker is useful to identify actionable violations. A preliminary empirical study reveals the possibility to prioritize static analysis rules according to further analysis on the actionable rates of the rules.

Exception handling is a mechanism in modern programming languages. Studies have shown that the exception handling code is error-prone. However, there is still limited research on detecting exception handling bugs, especially for C++ programs. To tackle the issue, we try to precisely represent the exception control flow in C++ programs and propose an analysis method that makes use of the control flow to detect such bugs. More specifically, we first extend control flow graph by introducing the concepts of five different kinds of basic blocks, and then modify the classic symbolic execution framework by extending the program state to a quadruple and properly processing try, throw and catch statements. Based on the above techniques, we develop a static analysis tool on the top of Clang Static Analyzer to detect exception handling bugs. We run our tool on projects with high stars from GitHub and find 36 exception handling bugs in 8 projects, with a precision of 84%. We compare our tool with four state-of-the-art static analysis tools (Cppcheck, Clang Static Analyzer, Facebook Infer and IKOS) on projects from GitHub and handmade benchmarks. On the GitHub projects, other tools are not able to detect any exception handling bugs found by our tool. On the handmade benchmarks, our tool has a significant higher recall.

Nonlinear integer constraints are common and difficult in the verification and analysis of software/hardware. SMT(QF_NIA) generalizes such constraints, which is a boolean combination of nonlinear integer arithmetic constraints. A classical method to solve SMT(QF_NIA) is bit-blasting, which reduces them to boolean satisfiability problems. Currently, the existing pure bit-blasting based solvers are noncompetitive with other state-of-the-art SMT solvers. The bit-blasting based methods have some problems: First, the bit-blasting method is hampered by nonlinear multiplication operations; second, it sometimes does not search in a proper search space; and third, it contains some redundancy.

We investigate a rigorous simulation and testing-based validation method for autonomous driving systems that integrates an existing industrial simulator and a formally defined testing environment. The environment includes a scenario generator that drives the simulation process and a monitor that checks at runtime the observed behavior of the system against a set of system properties to be validated. The validation method consists in extracting from the simulator a semantic model of the simulated system including a metric graph, which is a mathematical model of the environment in which the vehicles of the system evolve. The monitor can verify properties formalized in a first-order linear temporal logic and provide diagnostics explaining their non-satisfaction. Instead of exploring the system behavior randomly as many simulators do, we propose a method to systematically generate sets of scenarios that cover potentially risky situations, especially for different types of junctions where specific traffic rules must be respected. We show that the systematic exploration of risky situations has uncovered many flaws in the real simulator that would have been very difficult to discover by a random exploration process.

The fundamental asynchronous thread (java.lang. Thread) in Java can be easily misused, due to the lack of deep understanding for garbage collection and thread interruption mechanism. For example, a careless implementation of asynchronous thread may cause no response to the interrupt mechanism in time, resulting in unexpected thread-related behaviors, especially resource leak/waste. Currently, few works aim at these misuses and related works adopt either the dynamic approach which lacks effective inputs or the static path-sensitive approach with high time consumption due to the path explosion, causing false negatives. We have found that the behavior of threads and the interaction between threads and its referencing objects can be abstracted. In this paper, we propose an event analysis approach to detect the defects in Java programs and Android apps, which focuses on the existence or the order of the events to reduce the false negatives. We extract the misuse-related events, containing the thread events and the destroy events of the object referenced by the thread. Then we analyze the events with loop identification, happens-before relationship construction and alias determination. Finally, we implement an automatic tool named Leopard and evaluate it on real world Java programs and Android apps. Experiments show that it is efficient when comparing with the existing approach (misuse: 723 vs 47, time: 60s vs 30min), which also outperforms the existing work in precision. The manual check indicates that Leopard is more efficient and effective than existing work. Besides, 66 issues reported by us have been confirmed and 21 of them have been fixed by developers.

SMT (Satisfiability Modulo Theories) has been widely used in program verification, analysis, and test generation. But sometimes, SMT solver outputs incomprehensible solutions, especially for practical instances. Besides, due to the design of the deterministic algorithms, for a given formula, the result of each run is the same. In this paper, we concentrate on combining SMT solving with probability, which will instruct the SMT solver to give some plausible solutions. We define a special problem: PSMT, which allows solving an SMT instance with variables conforming to a certain distribution. We define distribution under constraint for PSMT, which is based on MCSAT (Model Constructing Satisfiability), a mainstream SMT-solving algorithm. We propose the Prob-MCSAT algorithm, which combines the MCSAT algorithm and introduces the probability to variables. The visualized examples show that the resulting assignments will form a clear trend based on Prob-SMT.

The satisfiability problem modulo the nonlinear real arithmetic (NRA) theory serves as the foundation for a wide range of important applications, such as model checking, program analysis, and software testing. However, due to the high computational complexity, developing efficient solving algorithms for this problem has consistently presented a substantial challenge. We present a hybrid SMT(NRA) solver, called NRAgo, which combines the efficiency of gradient-based optimization method with the completeness of algebraic solving algorithm. With our approach, the practical performance on many satisfiable instances is substantially improved. The experimental evaluation shows that NRAgo achieves remarkable acceleration effects on a set of challenging SMT(NRA) benchmarks that are hard to solve for state-of-the-art SMT solvers.

Third-party Python modules are usually implemented as binary extensions by using native code (C/C++) to provide additional features and runtime acceleration. In native code, the heap-allocated PyObjects are managed by the reference counting mechanism provided in Python/C APIs for automatic reclaiming. Hence, improper refcount manipulations can lead to memory leaks and use-after-free problems, and cannot be detected by simply pairing the occurrence of source and sink points. To detect such problems, state-of-the-art approaches have made groundbreaking contributions to identifying inappropriate final refcount values before returning from native code to Python. However, not all problems can be exposed at the end of a path. To detect those hidden in the middle of a path in native code, it is also crucial to track the lifecycle state of PyObjects through the refcount and lifecycle operations in API calls. To achieve this goal, we propose the PyObject State Transition Model (PSTM) recording the lifecycle states and refcount values of PyObjects to describe the effects of Python/C API calls and pointer operations. We track state transitions of PyObjects with symbolic execution based on the model, and report problems when a statement triggers a transition to buggy states. The program state is also expanded to handle pointer nullity checks and smart pointers of PyObjects. We conduct experiments on 12 open-source projects and detect 259 real problems out of 280 reports, which is twice as many bugs as state-of-the-art approaches. We submit 168 real bugs to those active projects, and 106 issues are either confirmed or resolved.

Cylindrical Algebraic Decomposition (CAD) is one of the pillar algorithms of symbolic computation, and its worst-case complexity is double exponential to the number of variables. Researchers found that variable order dramatically affects efficiency and proposed various heuristics. The existing learning-based methods are all supervised learning methods that cannot cope with diverse polynomial sets. This paper proposes two Reinforcement Learning (RL) approaches combined with Graph Neural Networks (GNN) for Suggesting Variable Order (SVO). One is GRL-SVO(UP), a branching heuristic integrated with CAD. The other is GRL-SVO(NUP), a fast heuristic providing a total order directly. We generate a random dataset and collect a real-world dataset from SMT-LIB. The experiments show that our approaches outperform state-of-the-art learning-based heuristics and are competitive with the best expert-based heuristics. Interestingly, our models show a strong generalization ability, working well on various datasets even if they are only trained on a 3-var random dataset. The source code and data are available at https://github.com/dongyuhang22/GRL-SVO.

Compilers are among the most critical components in the software development. Obviously, their correctness is very important, yet they are among the most complex software systems. The traditional grammar-based compiler random testing measures have two shortcomings. Firstly, the technique generating test programs for one programming language is difficult to migrate to another. The second one is that traditional grammar-based technique haven’t optimized the relation of identifier definition and use yet, causing the undefined identifiers problems or the low quality of the generated test programs. To address these problems, we propose a scope-based compiler testing method ScopeGen in this paper. To generate runnable and diverse test programs, ScopeGen supports two types of identifier strategies based on the scope information, one is scope distance based and the other is global optimization based. These identifier strategies guide the definition and use of identifiers and balance the distribution of identifiers in different scopes. Benefiting from the public grammar dataset Grammar-v4, ScopeGen can be easily migrated to various programming languages. We implement a program generator and generate grammatically correct and runnable test programs for C, Java and Python. Next, we conduct differential testing to identify various bugs in compilers by comparing the output of different compilers. The experimental evaluation of 9 compilers (gcc, clang, icc, icx, Ark, Javac, CPython, Pypy and Codon) shows that ScopeGen outperforms the two state-of-the-art methods (i.e., Csmith and YARPGen) improving more than 69% in inconsistency finding ability. By running ScopeGen we have reported 114 bugs for 4 compilers, 84 of which were confirmed.

State-of-the-art deep NLP models have achieved impressive improvements on many tasks. However, they are found to be vulnerable to some perturbations. Before they are widely adopted, the fundamental issues of robustness need to be addressed. In this paper, we design a robustness enhancement method to defend against word substitution perturbation, whose basic idea is to fight perturbation with perturbation. We find that: although many well-trained deep models are not robust in the setting of the presence of adversarial samples, they satisfy weak robustness. That means they can handle most non-crafted perturbations well. Taking advantage of the weak robustness property of deep models, we utilize non-crafted perturbations to resist the adversarial perturbations crafted by attackers. Our method contains two main stages. The first stage is using randomized perturbation to conform the input to the data distribution. The second stage is using randomized perturbation to eliminate the instability of prediction results and enhance the robustness guarantee. Experimental results show that our method can significantly improve the ability of deep models to resist the state-of-the-art adversarial attacks while maintaining the prediction performance on the original clean data.

Appropriate string test data generation is important for program testing. Complex string APIs combinations are commonly used to handle string parameters. However, the complex combinations make it difficult to express comprehensive string related constraints and generate suitable string data to trigger bugs and cover more branches. In this paper, we propose a novel approach to characterize the input strings and their operations (API invocations) with the regular expressions for string test data generation, with insight that they support rich syntax and can express the semantics of various string APIs combinations. We build a set of mapping rules that map 48 string APIs in Java to regular expressions, and design an inference algorithm to generate regular expressions for the complex string APIs combinations. With these regular expressions, more effective string data can be generated in an efficient way. Experiments on multi-type programs from assignments, LeetCode platform and open source community show that our approach can increase the branch coverage (17%) and find more bugs (+81) than the existing work. For the basic library JDK, 17 defects have been found, of which 14 are confirmed by the JDK developers and 3 are fixed in new version.

Deep neural networks have been widely adopted for many real-world applications and their reliability has been widely concerned. This paper introduces a notion of ε-weakened robustness (briefly as ε-robustness) for analyzing the reliability and some related quality issues of deep neural networks. Unlike the conventional robustness, which focuses on the “perfect” safe region in the absence of adversarial examples, ε-weakened robustness focuses on the region where the proportion of adversarial examples is bounded by user-specified ε. The smaller the value of ε is, the less vulnerable a neural network is to be fooled by a random perturbation. Under such a robustness definition, we can give conclusive results for the regions where conventional robustness ignores. We propose an efficient testing-based method with user-controllable error bounds to analyze it. The time complexity of our algorithms is polynomial in the dimension and size of the network. So, they are scalable to large networks. One of the important applications of our ε-robustness is to build a robustness enhanced classifier to resist adversarial attack. Based on this theory, we design a robustness enhancement method with good interpretability and rigorous robustness guarantee. The basic idea is to resist perturbation with perturbation. Experimental results show that our robustness enhancement method can significantly improve the ability of deep models to resist adversarial attacks while maintaining the prediction performance on the original clean data. Besides, we also show the other potential value of ε-robustness in neural networks analysis.

Various techniques based on code similarity measurement have been proposed to detect bugs. Essentially, the code fragment can be regarded as a kind of graph. Performing code graph similarity comparison to identify the potential bugs is a natural choice. However, the logic of a bug often involves only a few statements in the code fragment, while others are bug-irrelevant. They can be considered as a kind of noise, and can heavily interfere with the code similarity measurement. In theory, performing optimal vertex matching can address the problem well, but the task is NP-complete and cannot be applied to a large-scale code base. In this paper, we propose a two-phase strategy to accelerate code graph vertex matching for detecting bugs. In the first phase, a vertex matching embedding model is trained and used to rapidly filter a limited number of candidate code graphs from the target code base, which are likely to have a high vertex matching degree with the seed, i.e., the known buggy code. As a result, the number of code graphs needed to be further analyzed is dramatically reduced. In the second phase, a high-order similarity embedding model based on graph convolutional neural network is built to efficiently get the approximately optimal vertex matching between the seed and candidates. On this basis, the code graph similarity is calculated to identify the potential buggy code. The proposed method is applied to five open source projects. In total, 31 unknown bugs were successfully detected and confirmed by developers. Comparative experiments demonstrate that our method can effectively mitigate the noise problem, and the detection efficiency can be improved dozens of times with the two-phase strategy.

Inter-component communication (ICC) is a widely used mechanism in mobile apps, which enables message-based control flow transferring and data passing between Android components. Effective ICC resolution requires precisely identifying entry points, analyzing data values of ICC fields, modeling related framework APIs, etc. Due to various control-flow- and data-flow-related characteristics involved and the lack of oracles for real-world apps, the comprehensive evaluation of ICC resolution techniques is challenging.

As bugs of Python built-in types can cause code crashes, detecting them is critical to the robustness of the software. Researchers have concluded plenty of patterns for the bug causes and applied these patterns in detection tools. But these tools are only evaluated on handcrafted bugs or bugs obtained from QA pages. Because such bugs cannot reflect the complex code structures and various bug types encountered in real-world projects, the evaluation result is untrustworthy when applied to these projects. As a result, a collection of real-world reproducible bugs is essential for tool evaluation and future bug-related research. In this paper, we propose ExcePy, a benchmark for providing bugs of Python built-in types. We collect 180 bugs from the evolution of 15 real-world open-source Python projects on GitHub and then manually build test scripts for bug reproduction. Meanwhile, to improve tool evaluation efficiency, we present a code pruning strategy that can minimize buggy code size while retaining bug reproducibility and apply it to ExcePy to provide simplified buggy code. To demonstrate the benefits of ExcePy, we use three static analyzers and two fuzzers to detect bugs collected in ExcePy. We found that simplified code can significantly reduce running time and avoid many tool crashes, and bugs supplied by ExcePy can reveal limitations of existing tools in reporting real-world bugs.

This work is dedicated to improving local search solvers for the Boolean satisfiability (SAT) problem on structured instances. We propose a construct-and-cut (CnC) algorithm based on unit propagation, which is used to produce initial assignments for local search. We integrate our CnC initialization procedure within several state-of-the-art local search SAT solvers, and obtain the improved solvers. Experiments are carried out with a benchmark encoded from a spectrum repacking project as well as benchmarks encoded from two important mathematical problems namely Boolean Pythagorean Triple and Schur Number Five. The experiments show that the CnC initialization improves the local search solvers, leading to better performance than state-of-the-art SAT solvers based on Conflict Driven Clause Learning (CDCL) solvers.

The smart pointer mechanism, which is improved in the continuous versions of the C++ standards over the last decade, is designed to prevent memory-leak bugs by automatically deallocating the managed memory blocks. However, not all kinds of memory errors can be immunized by adopting this mechanism. For example, dereferencing a null smart pointer will lead to a software failure. Due to the lack of specialized support for smart pointers, the off-the-shelf C++ static analyzers cannot effectively reveal these bugs.In this paper, we propose a static approach to detecting memory-related bugs by tracking the heap memory management of smart pointers. The behaviors of smart pointers are modeled during their lifetime to trace the state transitions of managed memory blocks. And the specially designed checkers are used to check the state changes according to five collected bug patterns. To evaluate the effectiveness of our approach, we implement it on the top of the Clang Static Analyzer. A set of handmade code snippets, as well as nine popular open-source C++ projects, are used to compare our tool against four other analyzers. The results show that our approach can successfully discover nearly all the built-in bugs. And 442 out of 648 reports generated from the open-source projects are true positives after manual reviewing, where the bugs of dereferencing null smart pointers are most frequently reported. To further confirm our reports, we design patches for Aria2, Restbed, MySQL and LLVM, in which seven pull requests covering 76 bug reports have been merged by the developers up to now. The results indicate that pointers should always be carefully used even after migrated to smart pointers and static analysis upon specialized models can effectively detect such bugs.

As a widely used Android asynchronous component, AsyncTask is used to run time-consuming tasks. However, the misuse of AsyncTask will cause defects, i.e., crashes and memory leaks. Based on static analysis, existing approaches cannot accurately detect AsyncTask-related defects and produce many false positives since some paths are not reachable in practice. In this paper, we propose a dynamic detection method based on instrumentation, Monkey execution and log analysis to detect these defects. And we implement a tool AD2Checker based on the proposed method. Our experiment on 19 real-world apps shows that it has found 145 bugs and has no false positives. Moreover, it triggers crashes caused by misuse of AsyncTask.

Static analyzers can assist developers in detecting flaws and improving software quality. An analyzer often has numerous checkers, each of which implements a different checking rule. These checks can create a lot of warnings in real-world projects, putting a lot of pressure on programmers to examine them. Thus, it is critical to assess the effectiveness of these checkers before putting them to use. Typically, time-consuming questionnaires or human assessments of the warnings are employed to evaluate the checkers, which results in inefficiency when applied to real-world work. The significance and accuracy of checkers are the topics of this research, with the first reflecting the developers' attention to the checkers and the second reflecting the false-positive rate. We focus on Scala checkers in particular because, despite the popularity of the Scala programming language, there has been little study on them. We propose a method for tracking warnings in real-world projects and assessing the two features for each checker. We use 115 checks and six well-known Scala apps to demonstrate our approach. Based on the 191k warnings delivered by these checkers, the approach can identify 154k false positives, and it finds that only around 1/5 of the checks can benefit developers.

Existing GUI testing approaches of Android apps usually test apps from a single entry. In this way, the marginal activities far away from the default entry are difficult to be covered. The marginal activities may fail to be launched due to requiring a great number of activity transitions or involving complex user operations, leading to uneven coverage on activity components. Besides, since the test space of GUI programs is infinite, it is difficult to test activities under complete launching contexts using single-entry testing approaches.

Directed grey-box fuzzing is an effective technique to find bugs in programs with the guidance of user-specified target locations. However, it can hardly reach a target location guarded by certain syntax tokens (Guard Tokens for short), which is often seen in programs with string operations or grammar/lexical parsing. Only the test inputs containing Guard Tokens are likely to reach the target locations, which challenges the effectiveness of mutation-based fuzzers. In this paper, a Guard Token directed grey-box fuzzer called GTFuzz is presented, which extracts Guard Tokens according to the target locations first and then exploits them to direct the fuzzing. Specifically, to ensure the new test cases generated from mutations contain Guard Tokens, new strategies of seed prioritization, dictionary generation, and seed mutation are also proposed, so as to make them likely to reach the target locations. Experiments on real-world software show that GTFuzz can reach the target locations, reproduce crashes, and expose bugs more efficiently than the state-of-the-art grey-box fuzzers (i.e., AFL, AFLGO and FairFuzz). Moreover, GTFuzz identified 23 previously undiscovered bugs in LibXML2 and MJS.

Deep neural networks (DNNs) have been widely used in classification tasks. Studies have shown that DNNs may be fooled by artificial examples known as adversaries. A common technique for testing the robustness of a classification is to apply perturbations (such as random noise) to existing examples and try many of them iteratively, but it is very tedious and time-consuming. In this paper, we propose a technique to select adversaries more effectively. We study the vulnerability of examples by exploiting their class distinguishability. In this way, we can evaluate the probability of generating adversaries from each example, and prioritize all the examples accordingly. We have conducted an empirical study using a classic DNN model on four common datasets. The results reveal that the vulnerability of examples has a strong relationship with distinguishability. The effectiveness of our technique is demonstrated through 98.90 to 99.68% improvements in the F-measure.

Mastering the knowledge about security-sensitive functions that can potentially result in bugs is valuable to detect them. However, identifying this kind of functions is not a trivial task. Introducing machine learning-based techniques to do the task is a natural choice. Unfortunately, the approach also requires considerable prior knowledge, e.g., sufficient labelled training samples. In practice, the requirement is often hard to meet.

Facing the limited resource of smartphones, asynchronous programming significantly improves the performance of Android applications. Android provides several packaged components to ease the development of asynchronous programming. Among them, the AsyncTask component is widely used by developers since it is easy to implement. However, the abuse of AsyncTask component can decrease responsiveness and even lead to crashes. By investigating the Android Developer Documentation and technical forums, we summarize five misuse patterns about AsyncTask. To detect them, we propose a flow, context, object and field-sensitive inter-procedural static analysis approach. Specifically, the static analysis includes typestate analysis, reference analysis and loop analysis. Based on the AsyncTask-related information obtained during static analysis, we check the misuse according to predefined detection rules. The proposed approach is implemented into a tool called AsyncChecker. We evaluate AsyncChecker on a self-designed benchmark suite called AsyncBench and 1,759 real-world apps. AsyncChecker finds 17,946 misused AsyncTask instances in 1,417 real-world apps (80.6%). The precision, recall and F-measure of AsyncChecker on real-world applications are 97.2%, 89.8% and 0.93, respectively. Compared with existing tools, AsyncChecker can detect more asynchronous problems. We report the misuse problems to developers via GitHub. Several developers have confirmed and fixed the problems found by AsyncChecker. The result implies that our approach is effective and developers do take the misuse of AsyncTask as a serious problem.

The fifth version of the Hypertext Markup Language (HTML) standard is widely adopted in the diverse landscape of browser vendors and their continuously upgrading releases. One primary feature of HTML5 is native multimedia playback. The browsers’ native implementations of multimedia support bring lots of benefits such as improved security but require thorough testing, especially on the web page of complex factor combinations according to our manual checking of publicly visible existing tests. This article employs the combinatorial testing technique to trigger failure-inducing factor combinations effectively and to locate them, guided by some extracted properties that cover browsers’ major workflow of processing multimedia. Results are analyzed to give objective suggestions for browser developers to cast light on the places that implementation enhancement could be made, and for web developers to avoid undesirable effects.

Spectrum-based fault localization (SBFL) techniques can automatically localize software faults. They employ the program spectrum, such as code coverage profile with test verdicts, to rank the program entities based on their code suspiciousness. In the past decades, researchers have proposed many approaches to optimize these techniques; however, the program structure, which can influence their performance, is not taken into consideration in developing and improving these techniques. In this article, we identify and analyze the effect of the program structure on the application of SBFL techniques. We observe that some specific program structures may introduce structure bias to code suspiciousness and negatively influence the output of SBFL techniques. To mitigate these effects and improve the performance of fault localization, we propose Delta4Ts, a structure-aware technique. Delta4Ts references debugging history to alleviate the impact of structure bias in the calculation of code suspiciousness. It reasons from the observable suspicious value towards the desired suspicious value and the impact of structure bias. To evaluate Delta4Ts under practical constraints, we conduct a controlled experiment using nine widely-studied SBFL formulae on 12 C programs and 6 Java programs. The experiment results show that Delta4Ts can significantly improve the accuracy of the studied SBFL formulae by an average of 34.8% on 12 C programs and 30.6% on 6 Java programs, and improve more on subject programs associated with more history versions or having larger code sizes.

XSS is one of the common vulnerabilities in web applications. Many black-box testing tools may collect a large number of payloads and traverse them to find a payload that can be successfully injected, but they are not very efficient. And previous research has paid less attention to how to improve the efficiency of black-box testing to detect XSS vulnerability. To improve the efficiency of testing, we develop an XSS testing tool. It collects 6128 payloads and uses a headless browser to detect XSS vulnerability. The tool can discover XSS vulnerability quickly with the ART(Adaptive Random Testing) method. We conduct an experiment using 3 extensively adopted open source vulnerable benchmarks and 2 actual websites to evaluate the ART method. The experimental results indicate that the ART method can effectively improve the fuzzing method by more than 27.1% in reducing the number of attempts before accomplishing a successful injection.

Solution counting or solution space quantification (means volume computation and volume estimation) for linear constraints (LCs) has found interesting applications in various fields. Experimental data shows that integer solution counting is usually more expensive than quantifying volume of solution space while their output values are close. So it is helpful to approximate the number of integer solutions by the volume if the error is acceptable. In this paper, we present and prove a bound of such error for LCs. It is the first bound that can be used to approximate the integer solution counts. Based on this result, an approximate integer solution counting method for LCs is proposed. Experiments show that our approach is over 20x faster than the state-of-the-art integer solution counters. Moreover, such advantage increases with the problem scale.

Modal logic S5 has found various applications in artificial intelligence. With the advances in modern SAT solvers, SAT-based approach has shown great potential in solving the satisfiability problem of S5. The scale of the SAT encoding for S5 is strongly influenced by the upper bound on the number of possible worlds. In this paper, we present a novel SAT-based approach for S5 satisfiability problem. We show a normal form for S5 formulas. Based on this normal form, a conflict graph can be derived whose chromatic number provides an upper bound of the possible worlds and a lot of unnecessary search spaces can be eliminated in this process. A heuristic graph coloring algorithm is adopted to balance the efficiency and optimality. The number of possible worlds can be significantly reduced for many practical instances. Extensive experiments demonstrate that our approach outperforms state-of-the-art S5-SAT solvers.

A collection of n-2 idempotent symmetric quasigroups of order n is called a golf design if all the quasigroups in the collection are mutually disjoint. Two golf designs are said to be orthogonal if any idempotent symmetric quasigroup from one golf design has an orthogonal mate in the other golf design, and it is also called an orthogonal golf design (OG(n)). The existence of orthogonal golf designs is an open problem in combinatorial design theory. In this paper, we describe a method for solving some open cases using automated reasoning tools, employing both symmetry breaking and heuristic decision. The experimental results show that our method is highly efficient and it indeed allowed us to get some positive results in reasonable time. In particular, we apply state-of-the-art SAT solvers and constraint solvers to decide the non-existence of some instances, which can produce a formal proof.

Static analysis is widely used to detect potential defects in apps. Existing analysis tools focus on specific problems and vary in supported sensitivity, which make them difficult to reuse and extend for new analysis tasks. This paper presents Androlic, a precise static analysis framework for Android which is flow, context, object, field and path-sensitive. Through configuration items and APIs provided by Androlic, developers can easily extend it to perform custom analysis tasks. Evaluation on an example program and 20 real-world apps show that Androlic can analyze apps with high precision and efficiency.

Smart pointers are widely used to prevent memory errors in modern C++ code. However, improper usage of smart pointers may also lead to common memory errors, which makes the code not as safe as expected. To avoid smart pointer errors as early as possible, we present a coding style checker to detect possible bad smart pointer usages during compile time, and notify programmers about bug-prone behaviors. The evaluation indicates that the currently available state-of-the-art static code checkers can only detect 25 out of 116 manually inserted errors, while our tool can detect all these errors. And we also found 521 bugs among 8 open source projects with only 4 false positives.

To efficiently prune infeasible program paths, path-sensitive static analysis based bug detectors may utilize light-weight imprecise methods to check the satisfiability of path constraints, which leads to redundant reports and falsepositives. Although the false-positives can be eliminated by the post-inspection process, which re-checks the feasibility of the paths of each bug report with precise methods, the redundant reports are inspected unnecessarily. In this paper, we discuss how to improve the efficiency of the post-inspection process. We categorize the uninspected reports into disjoint sets and sort the reports in each category, which helps to decrease the number of inspection attempts. Besides, we parallelize the inspection for further speedup. The experimental results indicate that about 65.20% of needless inspections are eliminated in total. With the sorted category sets, about 52.4% of attempts are additionally reduced. And compared with the sequential execution, the parallel approach further gains an average speedup of 5.74 under 8 threads.

Monkey, which is integrated with the Android system, becomes the most widely used test input generation tool, owing to the simplicity, effectiveness and good compatibility. However, Monkey is based on coordinates of screen and oblivious to the widgets and the GUI states, which results in a great many ineffective events that have no contribution to the test. To address the major drawbacks, this paper parses the events of 200 test sequences generated by Monkey into human-readable scripts and manually investigate the effects of these events. We find three types of patterns on the ineffective events, including no-ops, single and combination of effect-free ones, and summarize them into ten rules for sequence reduction. Then, we implement a tool CHARD to match these patterns in real-world traces and prune the redundant events. The evaluation on 923 traces from various apps covering 16 categories shows that CHARD can process 1,000 events in a few seconds and identifies 41.3% events as ineffective ones. Meanwhile, the reduced sequence keeps the same functionality with the original one that can trigger the same behaviors. Our work can be applied to lessen the diagnose effort for record-and-replay, and as a preprocessing step for other works on analyzing sequences. For instance, CHARD can remove 72.6% ineffective events and saves 67.6% time of delta debugging in our experiments.

Model-based GUI exploration techniques are widely used to generate test cases for event-driven programs (such as Android apps). These techniques traverse the elements of screens during the user interaction and simultaneously construct the GUI model. Although there are a number of automatic model-based exploration tools, most of them pay more attention to the exploration procedure than the model reusing. This paper presents LAND, an effective and user-friendly test generation tool based on GUI exploration of Android apps, which constructs an elaborate window transition model ``LATTE'' that considers more Android specific characteristics and provides a customizable test generation interface by reusing the model. Experiments on 20 real-world Android apps are conducted to construct their models as well as test cases. The experimental results indicate that LAND can achieve higher code coverage and trigger exceptions in shorter sequence. It is also demonstrated that LATTE can be well reused under different requirements of test suite generation. A demo video of our tool can be found at the website https://www.youtube.com/watch?v=iqtr12eiJ_0.

Exported Activity (EA), a kind of activities in Android apps that can be launched by external components, is one of the most important inter-component communication (ICC) mechanisms to realize the interaction and cooperation among multiple apps. Existing works have pointed out that, once exposed, an activity will be vulnerable to malicious ICC attacks, such as permission leakage attack. Unfortunately, it is observed that a considerable number of activities in commercial apps are exposed inadvertently, while few works have studied the necessity and reasonability of such exposure. This work takes the first step to systematically study the exposing behavior of EAs through analyzing 13,873 Android apps. It utilizes the EA associated call relationships extracted from byte-code via data-flow analysis, as well as the launch conditions obtained from the manifest files, to guide the study on the usage and misexposure of EAs. The empirical findings are that the EA mechanism is widely adopted in development and the activities are liable to be misexposed due to the developers' misunderstanding or carelessness. Further study on subsets of apps selected according to different criteria indicates that the misexposed EAs have specific characteristics, which are manually summarized into six typical misuse patterns. As a consequence, ten heuristics are designed to decide whether an activity should be exposed or not and are implemented into an automatic tool called Mist. Experiments on the collected apps show that around one fifth EAs are unnecessarily exposed and there are more than one third EAs whose exposure may not be suggested.

As one of the most popular software testing techniques, fuzzing can find a variety of weaknesses in a program, such as software bugs and vulnerabilities, by generating numerous test inputs. Due to its effectiveness, fuzzing is regarded as a valuable bug hunting method. In this paper, we present an overview of fuzzing that concentrates on its general process, as well as classifications, followed by detailed discussion of the key obstacles and some state-of-the-art technologies which aim to overcome or mitigate these obstacles. We further investigate and classify several widely used fuzzing tools. Our primary goal is to equip the stakeholder with a better understanding of fuzzing and the potential solutions for improving fuzzing methods in the spectrum of software testing and security. To inspire future research, we also predict some future directions with regard to fuzzing.

Equipped with customized parameters, configurable software is more flexible when facing various hardware platforms and scenario options. The configurability can tailor the source code to different instances. Consequently, it is difficult for developers to enumerate all possible configurations for finding bugs, especially for large-scale configurable software systems. In this paper, we propose a method to efficiently detect bugs of such systems with static analysis techniques. The method takes advantage of combinatorial testing techniques to generate sufficient configurations. It first extracts required parameters and the corresponding constraints from a configure file. The parameters together with constraints are employed to generate configurations with required coverage. Considering the features of configuration options, we further classify the parameters into clusters, according to the tightness of their relations. Inspired from the idea of divide-and-conquer, every cluster can be assigned with a local strength, such that the tightly coupled options can be covered, without incurring other unnecessary options. Such improvement can reduce the number of required configurations, thus improving the efficiency of static analysis. The experimental results over four real-world configurable systems demonstrate the efficiency, scalability and practicality of our method.

GUI exploration is a widely adopted technique to test GUI programs, which traverses the elements of screens during the user interaction and simultaneously constructs the GUI model to describe window transitions. Specific to Android apps, an elaborate GUI model should take Android characteristics into consideration. We propose a GUI exploration approach that dynamically acquires the information of these characteristics, such as the status of widgets and arrangement of the back stack. We attach this information to the window transition graph and form a new model called LATTE (LAbeled Transition graph with sTack and widgEt). To balance the accuracy and size of model, we introduce a metric "state similarity" to merge similar states. We perform experiments on 20 real-world apps to test them and construct their LATTE models. The investigation indicates that our systematic exploration approach with regard to the Android characteristics covers more program behaviors, and the generated model can be reused to direct the further testing.

Program instrumentation is a widely used technique in dynamic analysis and testing, which makes use of probe code inserted to the target program to monitor its behaviors, or log runtime information for off-line analysis. There are a number of automatic tools for instrumentation on the source or byte code of Java programs. However, few works address this issue on the register-based Dalvik byte-code of ever-increasing Android apps. This paper presents a lightweight tool, InsDal, for inserting instructions to specific points of the Dalvik byte-code according to the requirements of users. It carefully manages the registers to protect the behavior of original code from illegal manipulation, and optimizes the inserted code to avoid memory waste and unnecessary overhead. This tool is easy to use and has been applied to several scenarios (e.g. energy analysis, code coverage analysis). A demo video of our tool can be found at the website: https://www.youtube.com/watch?v=Fpw-aygZ3kE.

Many existing symbolic execution engines for bug detection often ignore floating-point types and operations. That will result in imprecise reasoning about the feasibility of program paths, which in turn leads to false positives and negatives. Recently, there are quite some progress in satisfiability modulo theories (SMT) solving, and some tools are able to support floating-point arithmetic. Nevertheless, naturally extending a symbolic execution engine and directly replacing the back-end with the new SMT solver will not make a good static analyzer for floating-point programs.In this paper, we extend an existing symbolic execution engine for C program bug finding, so that it can deal with floating-point arithmetic and mathematical functions. For the mathematical functions, we employ an abstract model to keep a balance between overhead and precision. We also introduce a strategy, Lazy-verification, to reduce the number of SMT solver calls. We implemented our approach as a tool called Canalyze-fp. Experiments with self-developed benchmarks and non-trivial open source programs show that the proposed approach can effectively avoid the false positives and negatives, without introducing too much overhead.

Fixing bugs according to bug reports is a labor-intensive work for developers and automatic techniques can effectively decrease the manual efforts. A feasible solution is to fix specific bugs by static analysis and code instrumentation. In this paper, we present a light-weight approach to fixing the resource leak bugs that exist widely in Android apps while guaranteeing the safety that the patches should not interrupt normal execution of the original program. This approach first performs a light-weight static analysis and then carefully designs the concise patch code that will be inserted into the byte-code. When the program is running, the patches will trace the state of leaked resources and release them in a proper place. Our experiments on dozens of real-world apps show that our approach can effectively fix resource leaks in the apps with negligible extra execution time and less than 4% extra code in a few seconds.

Resource leak is a common bug in Android applications (apps for short). In general, it is caused by missing release operations of the resources provided by Android (like Camera, Media Player and Sensors) that require programmers to explicitly release them. It might lead to several serious problems for the app and system, such as performance degradation and system crash.

Android devices include many embedded resources such as Camera, Media Player and Sensors. These resources require programmers to explicitly request and release them. Missing release operations might cause serious problems such as performance degradation or system crash. This kind of defects is called resource leak. Despite a large body of existing works on testing and analyzing Android apps, there still remain several challenging problems. In this work, we present Relda2, a light-weight and precise static resource leak detection tool. We first systematically collected a resource table, which includes the resources that the Android reference requires developers release manually. Based on this table, we designed a general approach to automatically detect resource leaks. To make a more precise inter-procedural analysis, we construct a Function Call Graph for each Android application, which handles function calls of user-defined methods and the callbacks invoked by the Android framework at the same time. To evaluate Relda2's effectiveness and practical applicability, we downloaded 103 apps from popular app stores and an open source community, and found 67 real resource leaks, which we have confirmed manually.

White-box testing is an effective technique for generating test cases to provide high coverage for programs. We usually select several execution paths using some strategy, and generate a corresponding test case that follows each path. Each execution path corresponds to an input subspace bounded by constraints. Extreme values in these subspaces are very likely to trigger failures since the constraints bounding input subspaces may be faulty. In this paper, we propose a new way of defining the boundaries of comparison predicates in white-box testing, and apply constrained combinatorial testing to cover these boundaries with reduced number of test cases. Our approach can guarantee to cover all possible boundaries for each selected execution path, thus achieving high fault coverage for boundary faults, while the original structural coverage is still preserved.

Web service choreography specifies a sequence of interactions among multiple services. How to test if a Web service conforms with given choreography specification is a challenging question. It is important to generate test data (i.e. XML instance) based on the choreography. Since choreography scenarios describe expected interactions among multiple participants, it is possible to generate test data based on those scenarios. This paper presents a set of test data generating rules and algorithms based on refined type trees, which are obtained from choreography scenario and corresponding XML Schema type document. We have built a prototype tool to support automatic test data generation and illustrate the process of generating XML instances via a purchase order choreography scenario example.

Android phones come with a host of hardware components embedded in them, such as Camera, Media Player and Sensor. Most of these components are exclusive resources or resources consuming more memory/energy than general. And they should be explicitly released by developers. Missing release operations of these resources might cause serious problems such as performance degradation or system crash. These kinds of defects are called resource leaks. This paper focuses on resource leak problems in Android apps, and presents our lightweight static analysis tool called Relda, which can automatically analyze an application's resource operations and locate the resource leaks. We propose an automatic method for detecting resource leaks based on a modified Function Call Graph, which handles the features of event-driven mobile programming by analyzing the callbacks defined in Android framework. Our experimental data shows that Relda is effective in detecting resource leaks in real Android apps.

Web service choreography specifies the interaction among multiple participant, aiming to achieve common business goals. An issue is to check for the conformance of the implementation with reference to the choreography specification. To achieve that, we seek to develop software tools and a methodology to enable conformance testing of choreography. In this paper, we present our first step in that direction. Particularly, we reduce choreography scenario in order to obtain effective testing scenarios, which will greatly decrease the cost of testing. Concretely, based on XML Schema type definition of a choreography scenario, we partition XML Schema type into subtypes, which will be transformed into the input model of combinatorial tool Cascade for generating a set of combinations of variable values. The output of Cascade will be transformed to generate reduced scenarios for testing. Moreover, a purchase order choreography example is presented to demonstrate the reduction process of choreography scenarios, and a tool has been developed for supporting automatic implementation of the testing scenarios reduction.

In this paper, we study the testing of ID3v2 tags for MP3 files. We construct two combinatorial testing (CT) models for two test goals. One is for testing the audio players' recognition and display of variously encoded text information, and the other is for testing its robustness against bad header and frame sizes. We have conducted experiment son an on-vehicle leisure and entertainment system and a portable MP3player. We present some experimental results in this paper.

The Extended Finite State Machine (EFSM) is a commonly used model for specifying software systems. A test sequence for an EFSM is a sequence composed of values of input variables, which can make the EFSM “execute” along a complete path from entry to exit. Traditional test sequence generation methods for EFSM almost imitate those FSM-based approaches and focus on states identification. Most of them impose significant restrictions on the EFSM. This paper proposes a path-oriented approach to generating test cases for EFSM and presents a tool for test data generation. The experiments show that our tool can generate executable test sequences for EFSM models of software systems automatically in acceptable time.

We propose tuple density to be a new metric for combinatorial test suites. It can be used to distinguish one test suite from another even if they have the same size and strength. Moreover, it is also illustrated how a given test suite can be optimized based on this metric. The initial experimental results are encouraging.

We propose to combine symbolic execution with volume computation to compute the exact execution frequency of program paths and branches. Given a path, we use symbolic execution to obtain the path condition which is a set of constraints; then we use volume computation to obtain the size of the solution space for the constraints. With such a methodology and supporting tools, we can decide which paths in a program are executed more often than the others. We can also generate certain test cases that are related to the execution frequency, e.g., those covering cold paths.

Combinatorial testing is a widely used black-box testing technique, which is used to detect failures caused by parameter interactions (we call them faulty interactions). Traditional combinatorial testing techniques provide fault detection, but most of them provide weak fault diagnosis. In this paper, we propose a new fault characterization method called faulty interaction characterization (FIC) and its binary search alternative FIC_BS to locate one failure-causing interaction in a single failing test case. In addition, we provide a tradeoff strategy of locating multiple faulty interactions in one test case. Our methods are based on adaptive black-box testing, in which test cases are generated based on outcomes of previous tests. For locating a t-way faulty interaction, the number of test cases used is at most k (for FIC) or t(dlog2 k] + 1) + 1 (for FIC_BS), where k is the number of parameters. Simulation experiments show that our method needs smaller number of adaptive test cases than most existing methods for locating randomly-generated faulty interactions. Yet it has stronger or equivalent ability of locating faulty interactions.

Combinatorial testing is an important approach to detecting interaction errors for a system with several parameters. Existing research in this area assumes that all parameters of the system under test are always effective. However, in many realistic applications, there may exist some parameters that can disable other parameters in certain conditions. These parameters are called shielding parameters. Shielding parameters make test cases generated by the existing test model, which uses the Mixed Covering Array (MCA), fail in exposing some potential errors that should be detected. In this paper, the Mixed Covering Array with Shielding parameters (MCAS) is proposed to describe such problems. Then test cases can be generated by constructing MCAS's in three different approaches. According to the experimental results, our test model can generate satisfactory test cases for combinatorial testing with shielding parameters.

There are many test generation methods, but few of them consider the character strings. This paper proposes a method to generate test data for C programs with character strings and character string function calls, which is based on path oriented testing. Each character variable is viewed as an integer variable with the restriction that the value should be between 0 and 255. A character string is viewed as an array of characters with a predefined fixed length. Many commonly used character library functions are modeled by formulae in predicate logic with assignment statements. The model is then used to replace the function call in the program path, which will be solved by a path analysis tool to generate the test data. A prototype tool called StrGen is developed to illustrate the feasibility of this method. The results of some examples also show that this method is feasible and very efficient.

Combinatorial covering arrays have been used in several testing approaches. This paper first discusses some existing methods for finding such arrays. Then a SAT-based approach and a backtracking search algorithm are presented to solve the problem. A novel pruning strategy called SCEH is proposed to increase the efficiency of the methods. Several existing search heuristics and symmetry breaking techniques are also used in the backtracking search algorithm. Lastly, this paper introduces a tool called EXACT (exhaustive search of combinatorial test suites) which implements all the above techniques to construct the covering arrays automatically. The experimental results show that our backtracking search method outperforms other methods in many small size cases

BPEL is a language that could express complex concurrent behaviors. This paper presents a novel method of BPEL test case generation, which is based on concurrent path analysis. This method first uses an extended control flow graph (XCFG) to represent a BPEL program, and generates all the sequential test paths from XCFG. These sequential test paths are then combined to form concurrent test paths. Finally a constraint solver BoNuS is used to solve the constraints of these test paths and generate feasible test cases. Some techniques are proposed to reduce the number of combined concurrent test paths. Some test criteria derived from traditional sequential program testing are also presented to reduce the number of test cases. This method is modularized so that many test techniques such as various test criteria and complex constraint solvers can be applied. This method is tested sound and efficient in experiments. It is also applicable to the testing of other business process languages with possible extension and adaptation

The resource description framework (RDF) has been accepted as a standard for semantic representation of resources. Efficient methods and tools are needed to solve problems emerging from RDF based systems, for example, checking equality of two RDF graphs and retrieving subgraphs from another RDF graph. This paper proposes a method that encodes these problems into satisfiability (SAT) instances and solves them by employing efficient SAT solvers. A prototype tool is implemented and preliminary experimental results are given

Abstract With the advancement in network bandwidth and computing power, multimedia systems have become a popular means for information delivery. However, general principles of system testing cannot be directly applied to testing of multimedia systems on account of their stringent temporal and synchronization requirements. In particular, few studies have been made on the stress testing of multimedia systems with respect to their temporal requirements under resource saturation. Stress testing is important because erroneous behavior is most likely to occur under resource saturation. This paper presents an automatable method of test case generation for the stress testing of multimedia systems. It adapts constraint solving techniques to generate test cases that lead to potential resource saturation in a multimedia system. Coverage of the test cases is defined upon the reachability graph of a multimedia system. The proposed stress testing technique is supported by tools and has been successfully applied to a real‐life commercial multimedia system. Although our technique focuses on the stress testing of multimedia systems, the underlying issues and concepts are applicable to other types of real‐time systems. Copyright © 2002 John Wiley & Sons, Ltd.

Testing is a critical activity for database application programs as faults if undetected could lead to unrecoverable data loss. Database application programs typically contain statements written in an imperative programming language with embedded data manipulation commands, such as SQL. However relatively little study has been made in the testing of database application programs. In particular, few testing techniques explicitly consider the inclusion of database instances in the selection of test cases and the generation of test data input. In this paper, we study the generation of database instances that respect the semantics of SQL statements embedded in a database application program. The paper also describes a supporting tool which generates a set of constraints. These constraints collectively represent a property against which the program is tested. Database instances for program testing can be derived by solving the set of constraints using existing constraint solvers.