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.

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%.

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.

Sequence Containers (SC) in the C++ Standard Template Library (STL), such as the vector, are widely used in large-scale projects for their maintainability and flexibility. However, accessing the elements in an SC is bug-prone, as such operations will not check their boundaries during compilation or execution, which can lead to memory errors, such as buffer overflow problems. And these bugs are difficult to detect with available static analyzers, since the size of SCs and the target of iterators cannot be precisely tracked without accurate analysis of the behavior of SCs and iterators.

Current LiDAR-only 3D detection methods are limited by the sparsity of point clouds. The previous method used pseudo points generated by depth completion to supplement the LiDAR point cloud, but the pseudo points sampling process was complex, and the distribution of pseudo points was uneven. Meanwhile, due to the imprecision of depth completion, the pseudo points suffer from noise and local structural ambiguity, which limit the further improvement of detection accuracy. This paper presents SQDNet, a novel framework designed to address these challenges. SQDNet incorporates two key components: the SQD, which achieves sparse-to-dense matching via grid position indices, allowing for rapid sampling of large-scale pseudo points on the dense depth map directly, thus streamlining the data preprocessing pipeline. And use the density of LiDAR points within these grids to alleviate the uneven distribution and noise problems of pseudo points. Meanwhile, the sparse 3D Backbone is designed to capture long-distance dependencies, thereby improving voxel feature extraction and mitigating local structural blur in pseudo points. The experimental results validate the effectiveness of SQD and achieve considerable detection performance for difficult-to-detect instances on the KITTI test.

3D object detection based on multi-view cameras and bird’s-eye view (BEV) representation is a key task for autonomous driving, as it enables the perception systems to understand the surrounding scenes. However, most existing BEV representation methods rely on the projection matrix of camera intrinsic and extrinsic parameters, which requires a complex and time-consuming calibration process that may introduce errors and degrade the detection performance. Moreover, the calibration results may vary due to environmental changes and affect the stability of the detection system. To address this problem, we propose a calibration-free 3D object detection method that leverages a group-equivariant convolutional network to extract features from multi-view images and a projection network module to learn the implicit 3D-to-2D projection relationship for obtaining BEV representation. Furthermore, we employ contrastive learning to pre-train the projection network module without using manually annotated data. By exploiting the multi-view camera data through contrastive learning, our proposed method eliminates the need for tedious calibration, avoids calibration errors, and reduces the dependence on a large amount of annotated data for calibration-free 3D object detection. We evaluate our method on the nuScenes dataset and demonstrate its competitive performance. Our method improves the stability and reliability of 3D object detection in long-term autonomous driving.

Nowadays, many applications do not exist independently but rely on various frameworks or libraries. The frequent evolution and the complex implementation of framework APIs induce lots of unexpected post-release crashes. Starting from the crash stack traces, existing approaches either perform application-level call graph (CG) tracing or construct datasets with similar crash-fixing records to locate buggy methods. However, these approaches are limited by the completeness of CG or dependent on historical fixing records, and some of them only focus on specific manually modeled exception types. To achieve effective debugging on complex framework-specific crashes, we propose a code-separation-based locating approach that weakly relies on CG tracing and does not require any prior knowledge. Our key insight is that one crash trace with the description message can be mapped to a definite exception-thrown point in the framework, the semantics analysis of which can help to figure out the root causes of the crash-triggering procedure. Thus, we can pre-construct reusable summaries for all the framework-specific exceptions to support fault localization in application code. Based on that idea, we design the exception-thrown summary (ETS) that describes both the key variables and key APIs related to the exception triggering. Then, we perform static analysis to automatically compute such summaries and make a data-tracking of key variables and APIs in the application code to get the ranked buggy candidates. In the scenario of locating Android framework-specific crashing faults, our tool CrashTracker exhibited an overall MRR value of 0.91 and outperforms the state-of-the-art tool Anchor with higher precision. It only provides a compact candidate set and gives user-friendly reports with explainable reasons for each candidate.

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.

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.

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.

Components are the fundamental building blocks of Android applications. Different functional modules represented by components often rely on inter-component communication mechanisms to achieve cross-module data transfer and method invocation. It is necessary to conduct robustness testing on components to prevent component launching crashes and privacy leaks caused by unexpected input parameters. However, as the complexity of the input parameter structure and the diversity of possible inputs, developers may overlook specific inputs that result in exceptions. At the same time, the vast input space also brings challenges to efficient component testing. In this paper, we designed an automated test generation and execution tool for Android application components named ICTDroid, which combines static parameter extraction and adaptive-strength combinatorial testing generation to detect bugs with a compact test suite. Experiments have shown that the tool triggers 205 unique exceptions in 30 open-source applications with 1,919 test cases in 83 minutes, where the developers have confirmed six defects in three issues we reported.

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.

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.

While object detection modules are essential functionalities for any autonomous vehicle, the performance of such modules that are implemented using deep neural networks can be, in many cases, unreliable. In this paper, we develop abstraction-based monitoring as a logical framework for filtering potentially erroneous detection results. Concretely, we consider two types of abstraction, namely data-label abstraction and post-algorithm abstraction. Operated on the training dataset, the construction of data-label abstraction iterates each input, aggregates region-wise information over its associated labels, and stores the vector under a finite history length. Post-algorithm abstraction builds an abstract transformer for the tracking algorithm. Elements being associated together by the abstract transformer can be checked against consistency over their original values. We have implemented the overall framework to a research prototype and validated it using publicly available object detection datasets.

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.

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.

Deep neural networks (DNNs) have been increasingly adopted in various applications. Systematic verification and validation is essential to guarantee the quality of such systems. Due to the scalability problem, formal methods can hardly be widely applied in practice. Testing is one of feasible solutions. However, lacking of input space specification for DNNs requires a large set of test cases to be constructed to increase the testing adequacy, which leads to high labeling cost of test cases. In this paper, we put forwards a test case prioritization method for DNN classifiers, which assigns high priorities to those cases that could lead to wrong classifications. The priorities are calculated according to the activation pattern of neurons acquired from the training sets and the activated neurons collected from certain inputs. For a trained model, the method consists of two steps. First, we accumulate neuron activation patterns over the training set, and construct a set of frequently activated neurons based on the frequency (times) of activation for every class. Second, the metrics are computed according to the comparison between the activated neurons of an input and the selected set of frequently activated neurons with its output. The experimentation is carried out over three popular datasets with various neural network structures. The results demonstrate that the test cases with higher priorities are more prone to be mis-classified. And the prioritized test cases over a DNN model within same datasets are also efficient in triggering mis-classification of other DNNs with similar structures.

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.

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.

Network-on-Chip (NoC) is a promising interconnecting paradigm in the state-of-the-art multi-core architectures. Its communication network can increase the capacity of parallel data transfer such that system performance is improved. In the design of MPSoC-based applications, multiple objectives exist, such as minimizing time and energy consumption, which may conflict and certain trade-off needs to be evaluated. Heuristic-based methods such as evolutionary algorithms are always adopted to find near-optimal solutions for such applications. However, it is hard to evaluate the accuracy of those solutions. As most of the constraints on the mapping and scheduling process of NoCs can be described as logic formulas, we apply SMT-based methods for the multi-objective optimization of NoC-based MPSoCs. Moreover, to improve the scalability of the optimization problem, we propose to reduce the search space with respect to the symmetry feature of NoC architecture, and to decompose the search process according to the feature of non-dominated solutions. Extensive experimental results from random and real-case benchmarks demonstrate the accuracy of SMT-based methods in finding all the Pareto-fronts, and the efficiency of the proposed strategies.

Android Auto is designed to enhance the driving experience by extending dashboards of cars with smartphones' functionalities, among which an essential one is the message flow via notification mechanism. This paper investigates the quality of current compatible apps, and locates two main error-prone points. The study begins with manually designed black-box testing models including finite state machine and combinatorial input model according to safety requirements, and extracts testing suites from them. The tests are executed on 17 popular apps and reveal dozens of defects that might result in safety risks or inferior driving experiences. These defects are manually inspected and organized into several patterns. The experience and lessons from this empirical study are helpful to the detailed design and implementation of messaging modules.

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.

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.

The energy consumption problem is a hot topic in Android communities. The high energy cost caused by improper development brings lots of complaints from users. An effective and efficient energy consumption analysis technique can guide the developers to improve the energy efficiency of their apps. Existing researches on this problem focus on either system entity level that gives the energy consumption of the hardware, or source line level that calculates the energy cost of source codes. With the consideration of accuracy and cost of analysis, this paper proposes a lightweight and automatic approach to estimate the method-level energy consumption for Android apps. We construct a statistical model from a set of energy values obtained by Dalvik bytecode based instrumentation and software-based measurement, to predict the energy consumption of execution sequences of methods. The experiments on several real-world apps show that the proposed techniques have low overhead while persisting acceptable accuracy.

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.

Parameter shielding refers to the situation that one test parameter disables others in test execution.The quality of test case generation techniques is limited by the wide existence of parameter shielding.It is challenging to automatically find out conditions that cause the parameter shielding.This paper presents a novel approach for exploring the shielding conditions of test parameters.Our approach executes test inputs and collects runtime information of execution as features of test inputs.Then, a clustering algorithm is used to group test inputs with similar runtime information while a decision tree algorithm is built to extract the conditions in the groups.Finally, our approach identifies the shielding conditions based on the decision tree.Experiments on seven programs show that our approach can effectively detect the parameter shielding and the related conditions.

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.

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.

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