The backdoor attack poses a significant threat to deep neural networks. Existing works on poison suppression defense mainly focus on differentiating between poisoned and benign samples based on various metrics and removing the backdoor using Unlearning. However, these metrics can be bypassed by certain attacks, and Unlearning often leads to sub optimal model performance. Through examination of the model attack process, we discovered that poisoned samples always form clusters distant from benign samples in the early stages of training and when the model is fully trained, there is a unique pathway within the classifier connecting backdoor features to the target label. Leveraging these observations, in this paper, we propose a novel training method to detect poisoned samples during the early stages of training and remove the backdoor by retraining the classifier part of the model on relabeled poisoned samples. We evaluated our method against twelve attacks on four datasets, and the results showed that our method significantly outperforms existing state-of-the-art defenses. We reduced the average attack success rate to 0.07% while only decreasing the average accuracy by 0.33%. Our code is available at https://anonymous.4open.science/r/TRAP-2672.

Apart from forming the backbone of compiler optimization, static dataflow analysis has been widely applied in a vast variety of applications, such as bug detection, privacy analysis, and program comprehension. Despite its importance, performing inter-procedural dataflow analysis on large-scale programs is well-known to be challenging. In this article, we propose a novel distributed analysis framework supporting the general inter-procedural dataflow analysis. Inspired by large-scale graph processing, we devise dedicated distributed worklist algorithms for both whole-program analysis and incremental analysis. We implement these algorithms and develop a distributed framework called BigDataflow running on a large-scale cluster. The experimental results validate the promising performance of BigDataflow—BigDataflow can finish analyzing the program of million lines of code in minutes. Compared with the state-of-the-art, BigDataflow achieves much more analysis efficiency.

Large-scale Android apps that provide complex functions are gradually becoming the mainstream in Android app markets. They tend to display many GUI widgets on a single GUI page, which, unfortunately, can cause more redundant test actions—actions with similar functions—to automatic testing approaches. The effectiveness of existing testing approaches is still limited, suggesting the necessity of reducing the test effort on redundant actions. In this article, we first identify three types of GUI structures that can cause redundant actions and then propose a novel approach, called action equivalence evaluation, to find the actions with similar functions by exploiting both GUI structure and functionality. By integrating this approach with existing testing tools, the test efficacy can be improved. We conducted experiments on 17 large-scale Android apps, including three industrial apps Google News , Messenger , and WeChat . The results show that more instructions can be covered, and more crashes can be detected, compared to the state-of-the-art Android testing tools. Twenty-nine real bugs were found in our experiment, and moreover, 760 bugs over 40 versions of WeChat had been detected in the real test environment during a 3-month testing period.

Engineers utilize logs as a primary resource for fault localization in large-scale software and system testing, a process that is notoriously time-consuming, costly, and labor-intensive. Despite considerable progress in automated fault localization approaches, their applicability remains limited in such settings, due to the unavailability of fine-grained features in logs essential for most existing fault localization methods. In response, we introduce Falcon,a novel log-based fault localization framework. Falconorganizes complex semantic log information into graphical representations and employs contrastive learning to capture the differences between passed and failed logs, enabling the identification of crucial fault-related features. It also incorporates a specifically designed transitive analysis-based adaptive graph augmentation to minimize the influence of fault-unrelated log information on contrastive learning. Through extensive evaluations against 34 spectrum-based and 4 learning-based fault localization methods, Falcondemonstrates superior performance by out-performing all the methods in comparison. In addition, Falcondemonstrated its practical value by successfully identifying 71 out of 90 faults with a file-level Top-1 accuracy rate during a one-month deployment within a global company's testing system.

The use of deep learning to achieve automated software vulnerability detection has been a longstanding interest within the software security community. These deep vulnerability detectors are mostly trained in a supervised manner, which heavily relies on large-scale, high-quality vulnerability datasets. However, the vulnerability datasets used to train deep vulnerability detectors frequently exhibit class imbalance due to the inherent nature of vulnerability data, where vulnerable cases are significantly rarer than non-vulnerable cases. This imbalance adversely affects the effectiveness of these detectors. A promising solution to address the class imbalance problem is to artificially generate vulnerable samples to enhance vulnerability datasets, yet existing vulnerability generation techniques are not satisfactory due to their inadequate representation of real-world vulnerabilities or their reliance on large-scale vulnerable samples for training the generation model. This paper proposes G VI, a novel approach aimed at generating vulnerable samples to boost deep vulnerability detectors. G VI takes inspiration from human learning with imagination and proposes exploring LLMs to imagine and create new, informative vulnerable samples from given seed vulnerabilities. Specifically, we design a Chain-of-Thought inspired prompt in GVI that instructs the LLMs to first analyze the seed to retrieve attributes related to vulnerabilities and then generate a set of vulnerabilities based on the seed's attributes. Our extensive experiments on three vulnerability datasets (i.e., Devign, ReVeal, and BigVul) and across three deep vulnerability detectors (i.e., Devign, Re Veal, and Line Vul) demonstrate that the vulnerable samples generated by G VI are not only more accurate but also more effective in enhancing the performance of deep vulnerability detectors.

The growing adoption of Go for concurrent programming highlights its strengths in performance and simplicity, yet its special concurrency model-integrating shared memory with channel-based communication-introduces significant challenges for data race detection.Existing dynamic analysis tools suffer from high false negatives due to path-dependent execution, while static approaches often fail to account for features intrinsic to Go's concurrency model, such as channels and context propagation, leading to excessive false positives.To address these limitations, we present GRace, a static analysis framework tailored for Go that systematically models concurrency semantics to improve detection accuracy.GRace first identifies shared memory locations through pointer analysis and syntax-aware rules, then applies lock set analysis to filter protected accesses.By constructing a Go-specific happens-before graph that integrates Go's synchronization mechanisms (e.g., channels, Wait-Groups, Context cancellation), GRace refines event ordering and computes vector clocks to eliminate ordered accesses.Evaluated on real-world projects and benchmark datasets, GRace detected 18 data races in open-source repositories, with 11 confirmed and 8 fixed by developers.

With the rapid development of computer technology, emerging programming languages and compilers are constantly being introduced.However, these new compilers often have defects due to their short development time, insufficient testing, and the challenges they face, which affect their reliability and adoption.Traditional testing methods are limited in addressing the challenges of testing these new compilers.This paper proposes a new method for testing emerging compilers based on test case reuse, utilizing large language models to convert test cases from one programming language to another.Using C++ and Carbon language as examples, historical test cases from C++ are converted to Carbon language versions to expand the test case library for the Carbon compiler.This method involves fine-tuning a large language model to transform C++ historical bugs codes into codes suitable for the Carbon compiler, followed by verification to ensure their effectiveness.By converting and reusing test cases and implementing feature conversions to generate mutations, we improve 6.63% test coverage for Carbon compiler and discover 8 bugs.

As Android apps become increasingly dependent on network services, Network-Related Faults (NRFs) are gradually more prevalent and severely degrade user experience. These faults are typically scattered across apps and require complex, often non-trivial network patterns to trigger, which makes their detection challenging. To date, we still lack a general and in-depth understanding of NRFs in real-world Android apps. To fill this gap, we conduct the first empirical study on 154 real-world network-related bugs collected from 42 diverse, representative Android apps, investigating their characteristics, influences, triggering patterns, and origins. Our study reveals several notable findings and practical implications to guide future research on detecting and mitigating NRFs. Motivated by the empirical results and the limitations of existing Android testing approaches—namely, the lack of targeted network events and efficient injection mechanisms—we propose NATE, a novel Network-Aware Testing Enhancer that augments existing general Android testing approaches for NRF detection. NATE leverages curiosity-driven reinforcement learning to provide network-aware guidance and to inject effective network events, enabling testing approaches to explore network-related extra app functionalities and detect NRFs. When integrated with two state-of-the-art general Android testing approaches, experiments conducted on 12 large, active apps demonstrate the effectiveness and efficiency of NATE, with 1.7-5.7× as many faults detected, as well as 8.8% and 12.5% more code covered. Among the network-related faults detected by NATE, 21 have been explicitly confirmed as real-world bugs by the developers (six of which have already been fixed), where 16 of them were first reported by NATE. Notably, none of the 21 bugs were detected by the original general testing approaches, demonstrating the unique contributions of NATE.

Timing specifications are critical in real-time embedded systems, where even small time deviations may cause system failures. Although designers often model these systems using automata or sequence diagrams, formally verifying their timing properties remains computationally expensive due to the state-space explosion problem. This research proposes an acceleration framework for verifying interrupt-driven real-time systems against explicit clock value timing properties. Using partial order reduction and first-order logic encoding during verification, we abstract certain constructs in the models as parcels to avoid unnecessary state-space exploration. This parcel-based abstraction integrates seamlessly with formal models that support interruption mechanisms. Based on the framework, we implement two acceleration tactics: inclusive and external parcel pruning. Our prototype tool, Parcel, demonstrates the framework's efficacy on both existing models and large-scale models synthesized by LLMs. Experiments show that Parcel significantly improves the verification speed of large-scale, interrupt-driven models, outperforming state-of-the-art tools by thousands of times.

Despite extensive in-house testing, bugs often escape to deployed software. Whenever a failure occurs in production software, it is desirable to collect as much execution information as possible so as to help developers reproduce, diagnose and fix the bug. To reconcile the tension between trace capability, runtime overhead, and trace scale, we propose continuous tail tracing for production use. Instead of capturing only crash stacks, we produce the complete sequence of function calls and returns. Importantly, to avoid the overwhelming stress to I/O, storage, and network transfer caused by the tremendous amount of trace data, we only retain the final segment of trace. To accomplish it, we design a novel trace decoder to support precise tail trace decoding, and an effective path-based instrumentation-site selection algorithm to reduce overhead. We implemented our approach as a tool called TailTracer on top of LLVM, and conducted the evaluations over the SPEC CPU 2017 benchmark suite, the open-source database system, and real-world bugs. The experimental results validate that TailTracer achieves low-overhead tail tracing, while providing more informative trace data than the baseline.

Large-language models (LLMs) have been leveraged to enhance the capability of automated program repair techniques in recent research. While existing LLM-based program repair techniques compared favorably to other techniques based on heuristics, constraint-solving, and learning in producing high-quality patches, they mainly target bugs that can be corrected by changing a single faulty method, which greatly limits the effectiveness of such techniques in repairing bugs that demand patches spanning across multiple methods. In this work, we propose the PReMM technique to effectively propose patches changing multiple methods. PReMM builds on three core component techniques: the faulty method clustering technique to partition the faulty methods into clusters based on the dependence relationship among them, enabling a divide-and-conquer strategy for the repairing task; the fault context extraction technique to gather extra information about the fault context which can be utilized to better guide the diagnosis of the fault and the generation of correct patches; the dual-agent-based patch generation technique that employs two LLM-based agents with different roles to analyze the fault more precisely and generate patches of higher-quality. We have implemented the PReMM technique into a tool with the same name and applied the tool to repair real-world bugs from datasets Defects4J V1.2 and V2.0. PReMM produced correct patches for 307 bugs in total. Compared with ThinkRepair, the state-of-the-art LLM-based program repair technique, PReMM correctly repaired 102 more bugs, achieving an improvement of 49.8%.

Context sensitivity is a foundational technique in pointer analysis, critical and essential for improving precision but often incurring significant efficiency costs. Recent advances focus on selective context-sensitive analysis, where only a subset of program elements, such as methods or heap objects, are analyzed under context sensitivity while the rest are analyzed under context insensitivity, aiming to balance precision with efficiency. However, despite the proliferation of such approaches, existing methods are typically driven by specific code patterns, therefore lacking a comprehensive theoretical foundation for systematically identifying code scenarios that benefit from context sensitivity. This paper presents a novel and foundational theory that establishes a sound over-approximation of the ground truth, i.e., objects that really improve precision under context sensitivity. The proposed theory reformulates the identification of this upper bound into graph reachability problems over a typical Pointer Flow Graph (PFG), each of which can be efficiently solved under context insensitivity, respectively. Building on this theoretical foundation, we introduce our selective context-sensitive analysis approach, Moon . Moon performs both backward and forward traversal on a Variable Flow Graph (VFG), an optimized variant of PFG designed to facilitate efficient traversal. This traversal systematically identifies all objects that improve precision under context sensitivity. Our theoretical foundation, along with carefully designed trade-offs within our approach, allows Moon to limit the scope of objects to be selected, leading to an effective balance between its analysis precision and efficiency. Extensive experiments with Moon across 30 Java programs demonstrate that Moon achieves 37.2 X and 382.0 X speedups for 2-object-sensitive and 3-object-sensitive analyses, respectively with negligible precision losses of only 0.1% and 0.2%. These results highlight that the balance between efficiency and precision achieved by Moon significantly outperforms all previous approaches.

Persistent memory (PM), with its data persistence, has found widespread applications. However, programmers have to manually annotate PM operations in programming to achieve crash consistency, which is labor-intensive and error-prone. In this paper, to alleviate the burden of programming PM applications, we develop HybridPersist, a compiler support for user-friendly and efficient PM programming. On the one hand, HybridPersist automatically achieves crash consistency, minimally intruding on programmers with negligible annotations. On the other hand, it enhances both performance and correctness of PM programs through a series of dedicated analysis passes. The evaluations on well-known benchmarks validate that HybridPersist offers superior programming productivity and runtime performance compared to the state-of-the-art.

ABSTRACT In recent years, with the development of the open‐source community, various open‐source donation platforms have emerged. These platforms effectively alleviate the financial pressures faced by open‐source projects through diversified funding sources and flexible donation methods. As one of the most representative open‐source donation platforms, Opencollective has garnered widespread attention from both the open‐source community and academia. Although Opencollective claims to provide more funding opportunities for open‐source projects, the extent to which it effectively addresses the financial challenges faced by these projects remains unclear. While there have been studies on the effectiveness of traditional donation models, research on the effectiveness of emerging donation platforms such as Opencollective is still limited. Given that a large number of open‐source projects are urgently seeking donations, understanding the effectiveness of donations through Opencollective is crucial for these projects. To address this gap, we have made an early step in this direction. This paper conducts a comprehensive study on the effectiveness of donations through the Opencollective, employing a combination of quantitative and qualitative analysis and identifies the following key findings: (1) Opencollective attracts a diverse group of participants, including individual donors, sponsors, contributors, and project managers, with individual donors constituting the largest group. Most donations are concentrated in the range of $5 to $10, indicating that the platform largely relies on small but frequent donations from individuals. (2) Only about 26.61% of open‐source projects receive donations through Opencollective, with approximately 64.38% of these projects receiving a total donation amount of less than $50,000. The likelihood of receiving donations increases with project scale, maturity and the number of stars. Among projects that have received donations, larger projects with stronger social media promotion, greater attention and more issues are more likely to receive additional donations. (3) The positive impact of donations on project development and spend activities is significant only in the short term, with no notable long‐term effects. In contrast, donations do not have a significant short‐term impact on community engagement. Although the long‐term effect is slightly positive, it is not statistically significant. (4) The main shortcomings of Opencollective include insufficient project management and collaboration features, inadequate user experience and interface design, high transaction fees, and a lack of transparency in fund allocation and usage. Our findings provide significant theoretical support and practical recommendations for the effectiveness of emerging donation platforms and the sustainable development of open‐source projects.

Specifying channel-based asynchronous circuits in SystemVerilog is a promising alternative design paradigm to combine the advantages of asynchronous circuits and industrial electronic design automation supports. However, communicating through channels can be error-prone, potentially introducing deadlocks that cannot be detected easily through simulation. In contrast, model checking can reliably identify deadlocks, but faces challenges related to scalability and modeling capability. This research proposes a novel model checking approach, named Verilock, to detect deadlocks of channel-based asynchronous circuits specified in SystemVerilog. To address the issue of modeling capability, Verilock extracts intermodule communication behavior from SystemVerilog circuit designs and builds models in communication protocols specifically designed for this purpose. Additionally, Verilock employs a novel hierarchical model checking algorithm that conducts localized verification of well-formed groups of the system from the bottom up, thus reducing the size of the checking problems and presenting the opportunity to parallelize the checking process. Extensive experimental evaluations confirm the efficiency of Verilock in publicly accessible and randomly synthesized large-scale asynchronous circuits. Remarkably, significant benefits of the hierarchical checking approach are demonstrated through an ablative experiment.

For compositional linear hybrid automata (CLHA), whose dynamics can be characterized by linear constraints, bounded model checking (BMC) is challenging due to the complexity caused by interactions among member automata. Classical BMC approaches encode CLHA behavior using interleaving semantics, where compositions are handled with Cartesian product; as a result, the encoding is often large and complex, significantly limiting the scalability and efficiency of BMC. To address this problem, we propose three interaction relations to categorize and describe CLHA interactions through shared-label synchronization, discrete-variable read-write, and time-duration read-write. Based on the interaction relations, we devise interaction-oriented synchronization (IOS) semantics for CLHA behavior, which provides for a concise BMC encoding. In BMC, we employ a path-oriented method to check bounded reachability of CLHA, by enumerating candidate paths and checking each path’s feasibility. To prune the search space of candidate paths, we introduce a temporal relation graph (TRG) to quickly rule out infeasible paths via graph-based checking. Our method is implemented into a CLHA bounded reachability checker, BACH . Experiments indicate that it enables significant efficiency improvement over state-of-the-art tools, and performs scalable bounded reachability analysis on practical CLHA cases within seconds.

Abstract Cyber-physical systems (CPSs) are used in many safety-critical areas, making it crucial to ensure their safety. However, with CPSs increasingly dynamically deployed and reconfigured during runtime, their safety analysis becomes challenging. For one thing, reconfigurable CPSs usually consist of multiple agents dynamically connected during runtime. Their highly dynamic system topologies are too intricate for traditional modeling languages, which, in turn, hinders formal analysis. For another, due to the growing size and uncertainty of reconfigurable CPSs, their system models can be huge and even unavailable at design time. This calls for runtime analysis approaches with better scalability and efficiency. To address these challenges, we propose a scenario-based hierarchical modeling language for reconfigurable CPS. It provides template models for agent inherent features, together with an instantiation mechanism to activate single agent’s runtime behavior, communication configurations for multiple agents’ connected behaviors, and scenario task configurations for their dynamic topologies. We also present a path-oriented falsification approach to falsify system requirements. It employs classification-model-based optimization to explore search space effectively and cut unnecessary system simulations and robustness calculations for efficiency. Our modeling and falsification are implemented in a tool called . Experiments have shown that it can largely reduce modeling time and improve modeling accuracy, and perform scalable CPS falsification with high success rates in seconds.

Graphical User Interface (GUI) testing is one of the primary approaches for testing mobile apps. Test scripts serve as the main carrier of GUI testing, yet they are prone to obsolescence when the GUIs change with the apps' evolution. Existing repair approaches based on GUI layouts or images prove effective when the GUI changes between the base and updated versions are minor, however, they may struggle with substantial changes. In this paper, a novel approach named COSER is introduced as a solution to repairing broken scripts, which is capable of addressing larger GUI changes compared to existing methods. COSER incorporates both external semantic information from the GUI elements and internal semantic information from the source code to provide a unique and comprehensive solution. The efficacy of COSER was demonstrated through experiments conducted on 20 Android apps, resulting in superior performance when compared to the state-of-the-art tools METER and GUIDER. In addition, a tool that implements the COSER approach is available for practical use and future research.

As the scale and complexity of Android applications continue to grow in response to increasing market and user demands, quality assurance challenges become more significant. While previous studies have demonstrated the superiority of Reinforcement Learning (RL) in Android GUI testing, its effectiveness remains limited, particularly in large, complex apps. This limitation arises from the ineffectiveness of Tabular RL in learning the knowledge within the large state-action space of the App Under Test (AUT) and from the suboptimal utilization of the acquired knowledge when employing more advanced RL techniques. To address such limitations, this paper presents DQT, a novel automated Android GUI testing approach based on deep reinforcement learning. DQT preserves widgets' structural and semantic information with graph embedding techniques, building a robust foundation for identifying similar states or actions and distinguishing different ones. Moreover, a specially designed Deep Q-Network (DQN) effectively guides curiosity-driven exploration by learning testing knowledge from runtime interactions with the AUT and sharing it across states or actions. Experiments conducted on 30 diverse open-source apps demonstrate that DQT outperforms existing state-of-the-art testing approaches in both code coverage and fault detection, particularly for large, complex apps. The faults detected by DQT have been reproduced and reported to developers; so far, 21 of the reported issues have been explicitly confirmed, and 14 have been fixed.

End-to-end UI testing plays an indispensable role in web testing. However, the maintenance of UI test scripts can become a challenge as web applications undergo changes, leading to the potential breakage of these scripts. The manual repair of broken scripts is a time-consuming and labor-intensive process, making it imperative to study automated repair approaches. Existing approaches have relied on either the Document Object Model (DOM) or visual information alone to repair broken scripts, which show limited effectiveness as they only utilize a subset of the available information. Furthermore, merely combining the two approaches is not sufficient to improve effectiveness, as the use of two disparate methods may result in conflicting repair outcomes. In this study, we present a novel approach to web test repair that considers both information in the DOM and UI. To optimize the utilization of this information, our method classifies it as either identity-related or appearance-related, subsequently prioritizing its application in the repair process. In addition, we propose a more advanced lightweight Convolutional Neural Network based approach for better processing visual information. Our approach has been implemented as a tool named Webrl, which is available for practical use and further research. The effectiveness of Webrl was evaluated on a set of broken UI scripts constructed from 38 real-world web sites and was found to outperform the state-of-the-art approaches by a significant margin.

Code summarization aims to facilitate code com-prehension by automatically generating brief and informative summaries for source code. In software development, different projects often exhibit distinct characteristics. However, existing research frequently overlooks such project-specific knowledge, which may result in sub-optimal summarization performance. In this paper, we propose Precos, a retrieval-based method that leverages the historical examples within the project (i.e., internal corpus) for generating better code summaries. First we construct the internal corpus as a datastore, and extend the datastore by retrieving the most relevant examples for the current project from a large-scale external corpus based on the internal corpus. Then during generation, we retrieve the nearest neighbors from the datastore at each decoding step to interpolate the vanilla target-token distribution. For the retrieved neighbors, we introduce a novel locality-aware distance calibration mechanism, which calibrates the retrieval distance based on the locality of the nearest neighbors, thereby providing more accurate predictions. Experimental results demonstrate that Precos achieves a substantial improvement of up to 8.5 BLEU scores compared to the model before project-specific enhancement, and can generate better code summaries than other comparison methods while maintaining satisfactory results in additional storage, time overhead, and prediction speed11Our source code is available at https://github.com/ztw33/Precos.

Deep Neural Network (DNN) testing is one of the common practices to guarantee the quality of DNNs. However, DNN testing in general requires a significant amount of test inputs with oracle information (labels), which can be challenging and resource-intensive to obtain. To relieve this problem, we propose DATIS, a distance-aware test input selection approach for DNNs. Specifically, DATIS adopts a two-step approach for selecting test inputs. In the first step, it selects test inputs based on improved uncertainty scores derived from the distances between the test inputs and their nearest neighbor training samples. In the second step, it further eliminates test inputs that may cover the same faults by examining the distances among the selected test inputs. To evaluate DATIS, we conduct extensive experiments on 8 diverse subjects, taking into account different domains of test inputs, varied DNN structures, and diverse types of test inputs. Evaluation results show that DATIS significantly outperforms 15 baseline approaches in both selecting test inputs with high fault-revealing power and guiding the selection of data for DNN enhancement.

The coordinated vulnerability disclosure model, widely adopted in open-source software (OSS) organizations, recommends the silent resolution of vulnerabilities without revealing vulnerability information until their public disclosure. However, the inherently public nature of OSS development leads to security fixes becoming publicly available in repositories weeks before the official disclosure of vulnerabilities. This time gap poses a significant security risk to OSS users, as attackers could discover the fix and exploit vulnerabilities before disclosure. Thus, there is a critical need for OSS users to sense fixes as early as possible to address the vulnerability before any exploitation occurs. In response to this challenge, we introduce EarlyVulnFix, a novel approach designed to identify silent fixes for taint-style vulnerabilities—a persistent class of security weaknesses where attacker-controlled input reaches sensitive operations (sink) without proper sanitization. Leveraging data flow and dependency analysis, our tool distinguishes two types of connections between newly introduced code and sinks, tailored for two common fix scenarios. Our evaluation demonstrates that EarlyVulnFix surpasses state-of-the-art baselines by a substantial margin in terms of F1 score. Furthermore, when applied to the 700 latest commits across seven projects, EarlyVulnFix detected three security fixes before their respective security releases, highlighting its effectiveness in identifying unreported vulnerability fixes in the wild.

GUI models encapsulate the desired visual appearance and interactive behaviors of applications, facilitating various downstream tasks like model-based testing (MBT). Manually constructing high-quality GUI models is not only labor-intensive and costly but also prone to errors, particularly as applications evolve and require frequent model updates. Existing automated approaches for GUI model generation heavily rely on reverse engineering, where the models are abstractions of the code. As a result, they are not suitable for MBT to test functional issues because they are consistent with the code. Meanwhile, valuable development artifacts such as UI/UX design documents, which reflect design intentions, are often overlooked. In this paper, a novel approach named DemGen is proposed to seek a unique pathway for GUI model generation. Leveraging design documents, DemGen employs computer vision pre-trained models in conjunction with a rule-based correction mechanism to identify GUI elements and their intended behaviors as defined in those documents. Subsequently, the identified content is transformed into a formal GUI model adhering to the IFML modeling language. Our evaluation, conducted in collaboration with an industry partner on commercial applications, demonstrates the effectiveness and efficiency of DemGen in GUI element recognition and GUI model generation. Moreover, we conducted a comparative analysis of manual, automated, and hybrid modeling techniques, assessing the usefulness of generated models on MBT tasks.

The prominent role of mobile apps in daily life has underscored the need for robust quality assurance, leading to the development of various automated Android Graphical User Interface (GUI) testing approaches. Code coverage and fault detection are two primary metrics for evaluating the effectiveness of these testing approaches. However, conducting a reliable and robust evaluation based on the two metrics remains challenging, due to the imperfections of the current evaluation system, with a tangle of numerous metric granularities and the interference of multiple nondeterminism in tests. For instance, the evaluation solely based on the mean or total numbers of detected faults lacks statistical robustness, resulting in numerous conflicting conclusions that impede the comprehensive understanding of stakeholders involved in Android testing, thereby hindering the advancement of Android testing methodologies. To mitigate such issues, this paper presents the first comprehensive statistical study of existing Android GUI testing metrics, involving extensive experiments with 8 state-of-the-art testing approaches on 42 diverse apps, examining aspects including statistical significance, correlation, and variation. Our study focuses on two primary areas: (1) The statistical significance and correlation between test metrics and among different metric granularities. (2) The influence of test randomness and test convergence on evaluation results of test metrics. By employing statistical analysis to account for the considerable influence of randomness, we achieve notable findings: (1) Instruction, Executable Lines Of Code (ELOC), and method coverage demonstrate notable consistency across both significance evaluation and mean value evaluation, whereas the evaluation on Fatal Errors compared to Core Vitals, as well as all errors versus the well-selected errors, reveals a similarly high level of consistency. (2) There are evident inconsistencies in the code coverage and fault detection results, indicating both two metrics should be considered for comprehensive evaluation. (3) Code coverage typically exhibits greater stability and robustness in evaluation compared to fault detection, whereas fault detection is quite unstable even with the maximum test rounds ever used in previous research studies. (4) A moderate test duration is sufficient for most approaches to showcase their comprehensive overall effectiveness on most apps in both code coverage and fault detection, indicating the possibility of adopting a moderate test duration to draw preliminary conclusions in Android testing development. These findings inform practical recommendations and support our proposal of an effective framework to enhance future mobile testing evaluations.

Adversarial code examples are important to investigate the robustness of deep code models. Existing work on adversarial code example generation has shown promising results yet still falls short in practical applications due to either the high number of model invocations or the limited naturalness of generated examples. In this paper, we propose AaceGEN, an attention-guided adversarial code example generation method for deep code models. The key idea of AaceGEN is to utilize the attention distributions behind deep code models to guide the generation of adversarial code examples. As such, the code elements critical for model predictions could be prioritized for exploration, enhancing the effectiveness and efficiency of adversarial code example generation. In addition, AaceGEN implements a code transformation library providing diverse semantic-preserving code transformations for various code elements, and further conducts a search under the constraint of a maximum number of allowable code transformations to generate adversarial code examples with subtlety and stealth. Our extensive experiments on 9 diverse subjects, taking into account different software engineering tasks and varied deep code models, demonstrate that AaceGEN outperforms 3 baseline approaches under comprehensive evaluation.

Deep Neural Network (DNN) testing is one of the most widely-used techniques to guarantee the quality of DNNs. However, DNN testing typically requires the ground truth of test inputs, which is time-consuming and labor-intensive to obtain. To relieve the labeling-cost problem of DNN testing, we propose TDPR, a test input prioritization technique for DNNs based on training dynamics. The key insight of TDPR is that bug-revealing samples exhibit different learning trajectories compared to normal ones. Based on this, TDPR constructs a learning trajectory for each test input, which characterizes the evolving learning behavior of DNNs. Then, TDPR extracts features from these learning trajectories and applies learning-to-rank techniques to build a ranking model, which can intelligently utilize the generated features to prioritize test inputs. To evaluate TDPR, we conduct extensive experiments on 8 diverse subjects, considering various domains of test inputs, different DNN architectures, and diverse types of test inputs. The evaluation results demonstrate that TDPR outperforms 7 baseline approaches in both prioritizing test inputs and guiding the retraining of DNNs.

Android is the most popular mobile operating system. However, Android development requires extensive coding, especially for unique features such as lifecycle callbacks and UI widgets. Existing code completion methods typically utilize Retrieval-Augmented Generation (RAG) to provide contextual information for pre-trained code large language models (Code LLMs) to perform completion. Despite considerable progress in these methods, their effectiveness in Android development remains limited. This is because the features of Android development make it challenging for existing retrieval mechanisms to extract sufficient context effectively. In response, we propose DroidCoder, a novel Android code completion framework that employs Android development features and contextual information of code snippets to enrich RAG. It also incorporates a specifically designed loss function to fine-tune the model, enabling it to better utilize context-enhanced RAG for Android code completion. We evaluated our method on three base models and different types of applications, comparing it with two state-of-the-art code completion methods. The experimental results demonstrate that our method significantly outperforms the baselines at line-level and multi-line-level code completion and improves the quality of the completed code.

Java decompilers are programs that perform the reverse process of Java compilers, i.e., they translate Java bytecode to Java source code. They are essential for reverse engineering purposes and have become more sophisticated and reliable over the years. However, it remains challenging for modern Java decompilers to reliably perform correct decompilation on real-world programs. To shed light on the key challenges of Java decompilation, this paper provides the first systematic study on the characteristics and causes of bugs in mature, widely-used Java decompilers. We conduct the study by investigating 333 unique bugs from three popular Java decompilers. Our key findings and observations include: (1) Although most of the reported bugs were found when decompiling large, real-world code, 40.2% of them have small test cases for bug reproduction; (2) Over 80% of the bugs manifest as exceptions, syntactic errors, or semantic errors, and bugs with source code artifacts are very likely semantic errors; (3) 57.7%, 39.0%, and 41.1% of the bugs respectively are attributed to three stages of decompilers—loading structure entities from bytecode, optimizing these entities, and generating source code from these entities; (4) Bugs in decompilers’ type inference are the most complex to fix; and (5) Region restoration for structures like loop, sugaring for special structures like switch, and type inference of variables of generic types or indistinguishable types are the three most significant challenges in Java decompilation, which to some extent explains our findings in (3) and (4). Based on these findings, we present JD-Tester, a differential testing framework for Java decompilers, and our experience of using it in testing the three popular Java decompilers. JD-Testerutilizes different Java program generators to construct executable Java tests and finds exceptions, syntactic, and semantic inconsistencies (i.e. bugs) between a generated test and its compiled-decompiled version (through compilation and execution). In total, we have found 62 bugs in the three decompilers, demonstrating both the effectiveness of JD-Tester, and the importance of testing and validating Java decompilers.

Dynamic taint analysis (DTA), as a fundamental analysis technique, is widely used in security, privacy, and diagnosis, etc. As DTA demands to collect and analyze massive taint data online, it suffers extremely high runtime overhead. Over the past decades, numerous attempts have been made to lower the overhead of DTA. Unfortunately, the reductions they achieved are marginal, causing DTA only applicable to the debugging/testing scenarios. In this paper, we propose and implement HardTaint, a system that can realize production-run dynamic taint tracking. HardTaint adopts a hybrid and systematic design which combines static analysis, selective hardware tracing and parallel graph processing techniques. The comprehensive evaluations demonstrate that HardTaint introduces only around 8% runtime overhead which is an order of magnitude lower than the state-of-the-arts, while without sacrificing any taint detection capability.

Code summarization aims to generate short functional descriptions for source code to facilitate code comprehension. While Information Retrieval (IR) approaches that leverage similar code snippets and corresponding summaries have led the early research, Deep Learning (DL) approaches that use neural models to capture statistical properties between code and summaries are now mainstream. Although some preliminary studies suggest that IR approaches are more effective in some cases, it is currently unclear how effective the existing approaches can be in general, where and why IR/DL approaches perform better, and whether the integration of IR and DL can achieve better performance. Consequently, there is an urgent need for a comprehensive study of the IR and DL code summarization approaches to provide guidance for future development in this area. This article presents the first large-scale empirical study of 18 IR, DL, and hybrid code summarization approaches on five benchmark datasets. We extensively compare different types of approaches using automatic metrics, we conduct quantitative and qualitative analyses of where and why IR and DL approaches perform better, respectively, and we also study hybrid approaches for assessing the effectiveness of integrating IR and DL. The study shows that the performance of IR approaches should not be underestimated, that while DL models perform better in predicting tokens from method signatures and capturing structural similarities in code, simple IR approaches tend to perform better in the presence of code with high similarity or long reference summaries, and that existing hybrid approaches do not perform as well as individual approaches in their respective areas of strength. Based on our findings, we discuss future research directions for better code summarization.

Internet of Things (IoT) has become prevalent in various fields, especially in the context of home automation (HA). To better control HA-IoT devices, especially to integrate several devices for rich smart functionalities, trigger-action programming, such as the If This Then That (IFTTT), has become a popular paradigm. Leveraging it, novice users can easily specify their intent in applets regarding how to control a device/service through another once a specific condition is met. Nevertheless, the users may design IFTTT-style integrations inappropriately, due to lack of security experience or unawareness of the security impact of cyber-attacks against individual devices. This has caused financial loss, privacy leakage, unauthorized access and other security issues. To address these problems, this work proposes a systematic framework named MEDIC to model smart home integrations and check their security. It automatically generates models incorporating the service/device behaviors and action rules of the applets, while taking into consideration the external attacks and in-device vulnerabilities. Our approach takes around one second to complete the modeling and checking of one integration. We carried out experiments based on 200 integrations created from a user study and a dataset crawled from ifttt.com. To our great surprise, nearly 83% of these integrations have security issues.

Memory safety issues are the intrinsic diseases of C/C++ programs. Dynamic memory safety enforcement as the dominant approach has an advantage in high effectiveness, yet suffers from prohibitively high runtime overhead. Existing attempts to reduce the overhead are either labor-intensive, tightly dependent on specific hardware/compiler support, or poorly effective.

Abstract: Apart from forming the backbone of compiler optimization, static dataflow analysis has been widely applied in a vast variety of applications, such as bug detection, privacy analysis, program comprehension, etc. Despite its importance, performing interprocedural dataflow analysis on large-scale programs is well known to be challenging.In this paper, we propose a novel distributed analysis framework supporting the general interprocedural dataflow analysis.Inspired by large-scale graph processing, we devise a dedicated distributed worklist algorithm tailored for interprocedural dataflow analysis. We implement the algorithm and develop a distributed framework called BigDataflow running on a large-scale cluster.The experimental results validate the promising performance of BigDataflow – it can finish analyzing the program of millions lines of code in minutes. Compared with the state-of-the-art, BigDataflow achieves much more analysis efficiency.

With the rapid expansion of the Internet of Things, a vast number of microcontroller-based (MCU) IoT devices are now susceptible to attacks through the Internet. Vulnerabilities within the firmware are one of the most important attack surfaces. Fuzzing has emerged as one of the most effective techniques for identifying such vulnerabilities. However, when applied to IoT firmware, several challenges arise, including: 1) the inability of firmware to execute properly in the absence of peripherals; 2) the lack of support for exploring input spaces of multiple peripherals; 3) difficulties in instrumenting and gathering feedback; and 4) the absence of a fault detection mechanism. To address these challenges, we have developed and implemented an innovative peripheral-independent hybrid fuzzing tool called FirmHybirdFuzzer. This tool enables testing of MCU firmware without reliance on specific peripheral hardware. First, a unified virtual peripheral was integrated to model the behaviors of various peripherals, thus enabling the physical devices-agnostic firmware execution. Then, a hybrid event generation approach was used to generate inputs for different peripheral accesses. Furthermore, two-level coverage feedback was collected to optimize the testcase generation. Finally, a plugin-based fault detection mechanism was implemented to identify typical memory corruption vulnerabilities. A large-scale experimental evaluation has been performed to show FirmHybirdFuzzer’s effectiveness and efficiency.

Preferences, the setting options provided by Android, are an essential part of Android apps. Preferences allow users to change app features and behaviors dynamically, and therefore their impacts need to be considered when testing the apps. Unfortunately, few test cases explicitly specify the assignments of valid values to the preferences, or configurations , under which they should be executed, and few existing mobile testing tools take the impact of preferences into account or provide help to testers in identifying and setting up the configurations for running the tests. This article presents the Prefest approach to effective testing of Android apps with preferences. Given an Android app and a set of test cases for the app, Prefest amplifies the test cases with a small number of configurations to exercise more behaviors and detect more bugs that are related to preferences. In an experimental evaluation conducted on real-world Android apps, amplified test cases produced by Prefest from automatically generated test cases covered significantly more code of the apps and detected seven real bugs, and the tool’s test amplification time was at the same order of magnitude as the running time of the input test cases. Prefest ’s effectiveness and efficiency in amplifying programmer-written test cases was comparable with that in amplifying automatically generated test cases.

Safety verification is an essential requirement of neural network controlled systems when they are adopted in safety-critical fields. This paper proposes a novel approach to synthesizing neural networks as barrier certificates, which can provide safety guarantees for neural network controlled systems. We first propose the construction conditions of neural network barrier certificates, followed by an iterative framework to synthesize them. Each iteration trains a neural network as the candidate barrier certificate using the training datasets sampled from the neural network controlled system. After training, identifying whether the candidate barrier certificate is a real one for the neural network controlled system is transformed into a group of mixed-integer programming problems, which the numerical optimization solver solves with guaranteed results. We implement the tool NetBC and evaluate its performance over 6 practical benchmark examples. The experimental results show that NetBC is more effective and scalable than the existing polynomial barrier certificate-based method.

This paper presents an adversarial training framework WasserTrain for improving model robustness against the adversarial attacks in terms of the Wasserstein distance. First, an effective attack method WasserAttack is introduced with a novel encoding of the optimization problem, which directly finds the worst point within the Wasserstein ball while keeping the relaxation error of the Wasserstein transformation as small as possible. The proposed adversarial training frame-work utilizes these high-quality adversarial examples to train robust models. Experiments on MNIST show that the adversarial loss arising from adversarial examples found by our method is about three times as much as that found by the PGD-based attack method. Furthermore, within the Wasserstein ball with a radius of 0.5, the WasserTrain model achieves 31% adversarial robustness against WasserAttack, which is 22% higher than that on the PGD-based training model.

Although software libraries promote code reuse and facilitate software development, they increase the complexity of programme analysis tasks. To effectively analyse programmes built on top of software libraries, it is essential to have specifications for the library methods that can be easily processed by analysis tools. However, the availability of such specifications is seriously limited at the moment. Manually writing the specifications can be prohibitively expensive and error-prone, while existing automated approaches to inferring the specifications seldom produce results that are strong enough to be used in programme analysis. In this work, we propose the DOC2SMT approach to generating strong functional constraints in SMT for library methods based on their documentations. DOC2SMT first applies natural language processing (NLP) techniques and a set of rules to translate a method's natural language documentation into a large number of candidate constraint clauses in OCL. Then, it utilises a manually enhanced domain model to identify OCL candidate constraint clauses that comply with the problem domain in static validation, translates well-formed OCL constraints into the SMT-LIB format, and checks whether each 5MB-LIB constraint rightly abstracts the functionalities of the method under consideration via testing in dynamic validation. In the end, it reports the first functional constraint that survives both validations to the user as the result. We have implemented the approach into a supporting tool with the same name. In experiments conducted on 451 methods from the Java Collections Framework and the Java IO library, DOC2SMT generated correct constraints for 309 methods, with the average generation time for each correct constraint being merely 2.7 min. We have also applied the generated constraints to facilitate symbolic-execution-based test generation with the Symbolic Java PathFinder (SPF) tool. For 24 utility methods manipulating Java container and IO objects, SPF with access to the generated constraints produced 51.2 times more test cases than SPF without the access.

With the growth of Issue Tracking Systems, issue reports have become an important data to aid software maintenance and evaluation. Issue classification is one of the most important methods for such purpose, which aims to automatically distinguish issues related to bugs from other issues via machine learning algorithm. However, existing issue classification approaches are still inadequate due to either the incorrect usages of the textual fields of the issues or the ineffective feature representation methods. In this paper, we propose a novel issue classification approach named DeepLabel for achieving advanced issue classification. DeepLabel predicts the issue types by the ensemble of field-specific models that are applied on different textual fields, so as to make the maximum use of the information contained in the textual fields. In addition, DeepLabel adopts Word2Vec combined with attention-based Bi-directional Long Short-Term Memory (ABLSTM) as the feature extractor for the field-specific models in order to effectively extract the semantic information from the textual fields. We conduct an empirical study to evaluate the effectiveness of DeepLabel based on a widely used issue dataset. The results demonstrate that DeepLabel can significantly outperform the state-of-the-art approaches, in which DeepLabel correctly identifies more bug issues (160.1 vs. 140.1) and more non-bug issues (345.7 vs. 325.4) on average compared to the best one existing approach.

Spectrum-based fault localization(SBFL) has become one of the most widely studied localization techniques by its effectiveness and lightweightness. However, existing simple SBFL techniques are still not accurate enough for they are not able to distinguish specific locations in the same basic block. To address this problem, techniques that combine SBFL and MBFL(Mutation-based fault localization) have been proposed with the cost of introducing huge overhead from mutants. This paper proposes a graph neural network (GNN) based two-phase localization approach that localizes statements in blocks accurately and efficiently. The graph neural network introduced from our approach extracts the information from both the control flow graph and data flow graph, which includes the dependencies that distinguish the specific locations and further increase the localization accuracy. Our localization process is divided into two phases: Phase-I computes the suspiciousness score of each method and generates a ranking list, and phase-II further highlights the potential faulty locations inside a method by a fine-grained GNN with graphs in the method. We conduct experiments on 357 real bugs of 5 projects in the Defects4j benchmark. The results show that with a small overhead in our approach, the number of our successfully localized faults within the top-1, top-3, and top-5 positions is obviously higher than other SBFL techniques.

Functional scenario comprehension of screens in Android applications paves the way for Android app development and Android UI testing, especially in automated UI testing and test reuse. On the one hand, the screens of diverse Android applications contain widgets with many combinations. On the other hand, the screens of different scenarios may leverage similar widgets to fulfill the functionalities. Due to the above reasons, scenario comprehension is still hard to be solved by current approaches. In this paper, to fully understand the functionality of each screen, we propose a novel approach that employs Graph Neural Networks (GNN) to classify scenarios leveraging the transitions between screens and other available information of screens altogether. According to the result evaluated on 30 popular applications in the file management category, our approach improves the classification accuracy by at least 6% compared to previous work, demonstrating that GNN can fully utilize the potential relations and dependencies between the transitioned screens.

The lifecycle models of Android components such as Activities and Fragments predefine the possible orders in which the components' callback methods will be invoked during app executions. Correspondingly, resource utilization operations performed by Android components must comply with all possible lifecycles to ensure safe utilization of the resources in all circumstances, which, however, can be challenging to achieve. In response to the challenge, various techniques have been developed to detect resource utilization bugs that manifest themselves when components go through common lifecycles, but the fact that Android components may execute their callback methods in uncommon orders, leading to variant component lifecycles, has largely been overlooked by the existing techniques. In this paper, we first identify three variant lifecycles for Android Activities and Fragments and then develop a technique called VALA to automatically detect bugs in Android apps that are induced by the variant lifecycles and may cause resource utilization errors like resource leaks and data losses. In an experimental evaluation conducted on 35 Android apps, a supporting tool for the VALA technique automatically detected 8 resource utilization bugs. All the 8 bugs were manually confirmed to be real defects and 7 of them were reported for the first time.

With the rapid development of Deep Learning, deep predictive models have been widely applied to improve Software Engineering tasks, such as defect prediction and issue classification, and have achieved remarkable success. They are mostly trained in a supervised manner, which heavily relies on high-quality datasets. Unfortunately, due to the nature and source of software engineering data, the real-world datasets often suffer from the issues of sample mislabelling and class imbalance, thus undermining the effectiveness of deep predictive models in practice. This problem has become a major obstacle for deep learning-based Software Engineering.

Abstract BRICK is a bounded reachability checker for embedded C programs. BRICK conducts a path-oriented style checking of the bounded state space of the program, that enumerates and checks all the possible paths of the program in the threshold one by one. To alleviate the path explosion problem, BRICK locates and records unsatisfiable core path segments during the checking of each path and uses them to prune the search space. Furthermore, derivative free optimization based falsification and loop induction are introduced to handle complex program features like nonlinear path conditions and loops efficiently.

Safety control is a fundamental problem in policy design. Basic reinforcement learning is effective at learning policy with goal-reaching property. However, it does not guarantee safety property of the learned policy. This paper integrates barrier certificates into actor-critic-based reinforcement learning methods in a feedback-driven framework to learn safe policies for dynamical systems. The safe reinforcement learning framework is composed of two interactive parts: Learner and Verifier. Learner trains the policy to satisfy goal-reaching and safety properties. Since the policy is trained on training datasets, the two properties may not be retained on the whole system. Verifier validates the learned policy on the whole system. If the validation fails, Verifier returns the counterexamples to Learner for retraining the policy in the next iteration. We implement a safe policy learning tool SRLBC and evaluate its performance on three control tasks. Experimental results show that SRLBC achieves safety with no more than 0.5× time overhead compared to the baseline reinforcement learning method, showing the feasibility and effectiveness of our framework.

Cyber-physical systems (CPSs) integrate discrete computations with continuous physical processes and can be highly nonlinear and nondeterministic. Unlike the verification of CPS, which is difficult to handle, the falsification of CPS fulfills certain requirements from testing by seeking witness behavior of these systems and is easier to conduct. However, existing falsification techniques may fail to support the general complex CPS in practice because they usually focus on certain restricted classes of systems. In this article, we present a path-oriented, derivative-free approach to falsify safety properties in nonlinear and nondeterministic CPS. In our approach, we model the behavior of CPS by hybrid automata. Then, we enumerate candidate paths of hybrid automata (HA), transform the feasibility of candidate paths into optimization problems, and solve these optimization problems by our newly proposed classification model-based, derivative-free optimization algorithm. We also provide two novel pruning techniques to further improve the efficiency and efficacy of our approach: 1) a nested optimization structure with better model refinements for continuous search space pruning and 2) a hardly feasible path prefixes guided backtracking for discrete search space pruning. We implement our approach into a tool called PDF. Our experiments showed that PDF supported the safety falsification of CPS in all of our benchmarks, and it achieved success rates no lower than 95% in only seconds on 22/28 of the benchmarks.

Graphical User Interface (GUI) testing is widely used to test mobile apps. As mobile apps are frequently updated and need repeated testing, to reduce the test cost, their test cases are often coded as scripts to enable automated execution using test harnesses/tools. When those mobile apps evolve, many of the test scripts, however, may become broken due to changes made to the app GUIs. While it is desirable that the broken scripts get repaired, doing it manually can be preventively expensive if the number of tests need repairing is large. We propose in this paper a novel approach namedMeterto repairing broken GUI test scripts automatically when mobile apps evolve.Meterleverages computer vision techniques to infer GUI changes between two versions of a mobile app and uses the inferred changes to guide the repair of GUI test scripts. SinceMeteronly relies on screenshots to repair GUI tests, it is applicable to apps targeting open or closed source mobile platforms. In experiments conducted on 22 Android apps and 6 iOS apps, repairs produced byMeterhelped preserve 63.7 and 38.8 percent of all the test actions broken by the GUI changes, respectively.

Interrupt-driven programs are widely deployed in safety-critical embedded systems to perform hardware and resource dependent data operation tasks. The frequent use of interrupts in these systems can cause race conditions to occur due to interactions between application tasks and interrupt handlers (or two interrupt handlers). Numerous program analysis and testing techniques have been proposed to detect races in multithreaded programs. Little work, however, has addressed race condition problems related to hardware interrupts. In this paper, we present SDRacer, an automated framework that can detect, validate and repair race conditions in interrupt-driven embedded software. It uses a combination of static analysis and symbolic execution to generate input data for exercising the potential races. It then employs virtual platforms to dynamically validate these races by forcing the interrupts to occur at the potential racing points. Finally, it provides repair candidates to eliminate the detected races. We evaluate SDRacer on nine real-world embedded programs written in C language. The results show that SDRacer can precisely detect and successfully fix race conditions.

The paper presents a barrier certificate based approach to verifying safety properties of closed-loop systems using neural networks as controllers. It deals with the verification problem in the infinite time horizon and exploits the approximated system of the original one to synthesize the candidate barrier certificates, where the behavior of a neural network controller is approximated by a polynomial with a bounded error. Satisfiability Modulo Theories solvers are then utilized to identify real barrier certificates from those candidates. As a barrier certificate can separate the over-approximation of the reachable set from the unsafe region, once it is constructed, the safety property gets proved. We show the advantage of our approach in barrier certificates synthesis by comparing it with the state-of-the-art work on a set of benchmarks.

Hybrid systems are widely used in safety-critical areas. Hybrid optimal control synthesis, which aims to generate an optimal sequence of control inputs for a given task, is one of the most important problems in the field. The classical Gradient-based methods are efficient but they require the system under control should be differentiable. Sampling-based methods have no such limitations, but the ability of existing ones to solve complex control missions is restricted.

Barrier certificates provide safety guarantees for hybrid systems. In this paper, we propose a novel approach to synthesizing neural networks as barrier certificates. Candidate networks are trained from a special structure: ReLU neural networks consisting of two hidden layers. Then, the problem of identifying real barrier certificates from candidates is transformed into a group of mixed integer linear programming problems and a mixed integer quadratically constrained problem. Taking full advantage of the recent advance in optimization, barrier certificates validation can be performed effectively. We implement the tool SyntheBC and evaluate its performance over 3 hybrid systems and 8 continuous systems up to 12-dimensional state space. The experimental results show that our method is more scalable and effective than the classical polynomial barrier certificate method and the existing neural network based method.

Due to the increasing usage of Deep Neural Network (DNN) based autonomous driving systems (ADS) where erroneous or unexpected behaviours can lead to catastrophic accidents, testing such systems is of growing importance. Existing approaches often just focus on finding erroneous behaviours and have not thoroughly studied the impact of environmental conditions. In this paper, we propose to test DNN-based ADS under different environmental conditions to identify the critical ones, that is, the environmental conditions under which the ADS are more prone to errors. To tackle the problem of the space of environmental conditions being extremely large, we present a novel approach named TACTIC that employs the search-based method to identify critical environmental conditions generated by an image-to-image translation model. Large-scale experiments show that TACTIC can effectively identify critical environmental conditions and produce realistic testing images, and meanwhile, reveal more erroneous behaviours compared to existing approaches.

GUI testing is an essential part of regression testing for Android apps. For regression GUI testing to remain effective, it is important that obsolete GUI test scripts get repaired after the app has evolved. In this paper, we propose a novel approach named GUIDER to automated repair of GUI test scripts for Android apps. The key novelty of the approach lies in the utilization of both structural and visual information of widgets on app GUIs to better understand what widgets of the base version app become in the updated version. A supporting tool has been implemented for the approach. Experiments conducted on the popular messaging and social media app WeChat show that GUIDER is both effective and efficient. Repairs produced by GUIDER enabled 88.8% and 54.9% more test actions to run correctly than those produced by existing approaches to GUI test repair that rely solely on visual or structural information of app GUIs.

Hardware tracing modules such as Intel Processor Trace perform continuous control-flow tracing of an end-to-end program execution with an ultra-low overhead. PT has been used in a variety of contexts to support applications such as testing, debugging, and performance diagnosis. However, these hardware modules have so far been used only to trace native programs, which are directly compiled down to machine code. As high-level languages (HLL) such as Java and Go become increasingly popular, there is a pressing need to extend these benefits to the HLL community. This paper presents JPortal, a JVM-based profiling tool that bridges the gap between HLL applications and low-level hardware traces by using a set of algorithms to precisely recover an HLL program’s control flow from PT traces. An evaluation of JPortal with the DaCapo benchmark shows that JPortal achieves an overall 80% accuracy for end-to-end control flow profiling with only a 4-16% runtime overhead.

Sophisticated static analysis techniques often have complicated implementations, much of which provides logic for tuning and scaling rather than basic analysis functionalities. This tight coupling of basic algorithms with special treatments for scalability makes an analysis implementation hard to (1) make correct, (2) understand/work with, and (3) reuse for other clients. This paper presents Chianina, a graph system we developed for fully context- and flow-sensitive analysis of large C programs. Chianina overcomes these challenges by allowing the developer to provide only the basic algorithm of an analysis and pushing the tuning/scaling work to the underlying system. Key to the success of Chianina is (1) an evolving graph formulation of flow sensitivity and (2) the leverage of out-of-core, disk support to deal with memory blowup resulting from context sensitivity. We implemented three context- and flow-sensitive analyses on top of Chianina and scaled them to large C programs like Linux (17M LoC) on a single commodity PC.

Abstract During program traversing, symbolic execution collects path conditions and feeds them to a constraint solver to obtain feasible solutions. However, complex path conditions, like nonlinear constraints, which widely appear in programs, are hard to be handled efficiently by the existing solvers. In this paper, we adapt the classical symbolic execution framework with a machine learning approach for constraint satisfaction. The approach samples and learns from different solutions to identify potentially feasible area. This sampling-learning style solving can be applied in different class of complex problems easily. Therefore, incorporating this approach, our framework, MLBSE, supports the symbolic execution of not only simple linear path conditions, but also nonlinear arithmetic operations, and even black-box function calls of library methods. Meanwhile, thanks to the theoretical foundation of the machine learning based approach, when the solver fails to solve a path condition, we can have an estimation of the confidence in the satisfiability (ECS) of the problem to give users insights about how the problem is analyzed and whether they could ultimately find a solution. We implement MLBSE on the basis of Symbolic Path Finder (SPF) into a fully automatic Java symbolic execution engine. Users can feed their code to MLBSE directly, which is very convenient to use. To evaluate its performance, 22 real case programs are used as the benchmarks for MLBSE to generate test cases, which involve a total number of 1042 methods that are full of nonlinear operations, floating-point arithmetic as well as native method calls. Experiment results show that the coverage achieved by MLBSE is much higher than the state-of-the-art tools.

Summary Although software libraries promote code reuse and facilitate software development, they increase the complexity of programme analysis tasks. To effectively analyse programmes built on top of software libraries, it is essential to have specifications for the library methods that can be easily processed by analysis tools. However, the availability of such specifications is seriously limited at the moment. Manually writing the specifications can be prohibitively expensive and error‐prone, while existing automated approaches to inferring the specifications seldom produce results that are strong enough to be used in programme analysis. In this work, we propose the Doc2smt approach to generating strong functional constraints in SMT for library methods based on their documentations. Doc2smt first applies natural language processing (NLP) techniques and a set of rules to translate a method's natural language documentation into a large number of candidate constraint clauses in OCL. Then, it utilizes a manually enhanced domain model to identify OCL candidate constraint clauses that comply with the problem domain in static validation, translates well‐formed OCL constraints into the SMT‐LIB format, and checks whether each SMB‐LIB constraint rightly abstracts the functionalities of the method under consideration via testing in dynamic validation. In the end, it reports the first functional constraint that survives both validations to the user as the result. We have implemented the approach into a supporting tool with the same name. In experiments conducted on 451 methods from the Java Collections Framework and the Java IO library, Doc2smt generated correct constraints for 309 methods, with the average generation time for each correct constraint being merely 2.7 min. We have also applied the generated constraints to facilitate symbolic‐execution‐based test generation with the Symbolic Java PathFinder (SPF) tool. For 24 utility methods manipulating Java container and IO objects, SPF with access to the generated constraints produced 51.2 times more test cases than SPF without the access.

Static program analysis has been widely applied along the whole process of the program development for bug detection, code optimization, testing, etc. Although researchers have made significant work in static program analysis, it is still challenging to perform sophisticated interprocedural analysis on large-scale modern software. The underlying reason is that interprocedural analysis for large-scale modern software is highly computation- and memory-intensive, leading to poor efficiency and scalability. In this article, we introduce an efficient distributed and scalable solution for sophisticated static analysis. Specifically, we propose a data-parallel algorithm and a join-process-filter computation model for the CFL-reachability-based interprocedural analysis. Based on that, an efficient distributed static analysis engine called BigSpa is developed, which is composed of an offline batch static program analysis system and an online incremental static program analysis system. The BigSpa system has high generality and can support all kinds of static analysis tasks that can be expressed as CFL reachability problems. The performance of BigSpa is evaluated on real-world large-scale software datasets. Our experiments show that the offline batch system can exceed an order of magnitude compared with the most advanced analysis tools available on performance, and for incremental analysis with small batch updates on the same data sets, the online analysis system can achieve near real-time response, which is very fast and flexible.

Barrier certificates generation is widely used in verifying safety properties of hybrid systems because of the relatively low computational complexity it costs. Under sum of squares (SOS) relaxation, the problem of barrier certificate generation is equivalent to that of solving a bilinear matrix inequality (BMI) with a particular type. The paper reveals the special feature of the problem, and adopts it to build a novel computational method. The proposed method introduces a sequential iterative scheme that is able to find analytical solutions, rather than the nonlinear solving procedure to produce numerical solutions used by general BMI solvers and thus is more efficient than them. In addition, different from popular LMI solving based methods, it does not make the verification conditions more conservative, and thus reduces the risk of missing feasible solutions. Benefitting from these two appealing features, it can produce barrier certificates not amenable to existing methods, which is supported by a complexity analysis as well as the experiment on some benchmarks.

Ordinary users can build their smart home automation system easily nowadays, but such user-customized systems could be error-prone. Using formal verification to prove the correctness of such systems is necessary. However, to conduct formal proof, formal specifications such as Linear Temporal Logic (LTL) formulas have to be provided, but ordinary users cannot author LTL formulas but only natural language.To address this problem, this paper presents a novel approach that can automatically generate formal LTL specifications from natural language requirements based on domain knowledge and our proposed ambiguity refining techniques. Experimental results show that our approach can achieve a high correctness rate of 95.4% in converting natural language sentences into LTL formulas from 481 requirements of real examples.

Mobile applications play an important role in our daily life, while it still remains a challenge to guarantee their correctness. Model-based and systematic approaches have been applied to Android GUI testing. However, they do not show significant advantages over random approaches because of limitations such as imprecise models and poor scalability. In this paper, we propose Q-testing, a reinforcement learning based approach which benefits from both random and model-based approaches to automated testing of Android applications. Q-testing explores the Android apps with a curiosity-driven strategy that utilizes a memory set to record part of previously visited states and guides the testing towards unfamiliar functionalities. A state comparison module, which is a neural network trained by plenty of collected samples, is novelly employed to divide different states at the granularity of functional scenarios. It can determine the reinforcement learning reward in Q-testing and help the curiosity-driven strategy explore different functionalities efficiently. We conduct experiments on 50 open-source applications where Q-testing outperforms the state-of-the-art and state-of-practice Android GUI testing tools in terms of code coverage and fault detection. So far, 22 of our reported faults have been confirmed, among which 7 have been fixed.

Application program interface (API) mapping is the key to the success of code migration. Leveraging API documentation to map APIs has been explored by previous studies, and recently, code-based learning approaches have become the mainstream approach and shown better results. However, learning approaches often require a large amount of training data (e.g., projects implemented using multiple languages or API mapping datasets), which are not widely available. In contrast, API documentation is usually available, but we have observed that much information in API documentation has been underexploited. Therefore, we develop a deep-dive approach to extensively explore API documentation to create improved API mapping methods. Our documentation exploration approach involves analyzing the functional description of APIs, and also considers the parameters and return values. The results of this analysis can be used to generate not only one-to-one API mapping, but also compatible API sequences, thereby enabling one-to-many API mapping. In addition, parameter-mapping relationships, which have often been ignored in previous approaches, can be produced. We apply this approach to map APIs from Java to Swift, and the experimental results indicate that our deep-dive analysis of API documentation leads to API mapping results that are superior to those generated by existing approaches.

Unlike standalone embedded devices, behaviors of a cyber-physical system (CPS) are highly dynamic. Many parameter values (e.g., those related to nature environment and third party black box functions) are unknown offline. Furthermore, distributed sub-CPSs may exchange data online. In this article, we first propose the concept of parametric hybrid automata (PHA) to describe such complex CPSs. As some PHA parameter values are unknown until runtime, conventional offline model checking is infeasible. Instead, we propose to carry out PHA model checking online, as a fault prediction mechanism. However, this usage is challenged by the high time cost of state reachability verification, which is the conventional focus of model checking. To address this challenge, we propose that the model checking shall focus on online scenario reachability validation instead. Furthermore, we propose a mechanism to compose/decompose scenarios. Our scenario reachability validation can exploit linear programming to achieve polynomial time cost. Evaluations on a state-of-the-art train control system show that our approach can cut online model checking time cost from over 1 h to within 200 ms.

There is more than a decade-long history of using static analysis to find bugs in systems such as Linux. Most of the existing static analyses developed for these systems are simple checkers that find bugs based on pattern matching. Despite the presence of many sophisticated interprocedural analyses, few of them have been employed to improve checkers for systems code due to their complex implementations and poor scalability. In this article, we revisit the scalability problem of interprocedural static analysis from a “Big Data” perspective. That is, we turn sophisticated code analysis into Big Data analytics and leverage novel data processing techniques to solve this traditional programming language problem. We propose Graspan , a disk-based parallel graph system that uses an edge-pair centric computation model to compute dynamic transitive closures on very large program graphs. We develop two backends for Graspan, namely, Graspan-C running on CPUs and Graspan-G on GPUs, and present their designs in the article. Graspan-C can analyze large-scale systems code on any commodity PC, while, if GPUs are available, Graspan-G can be readily used to achieve orders of magnitude speedup by harnessing a GPU’s massive parallelism. We have implemented fully context-sensitive pointer/alias and dataflow analyses on Graspan. An evaluation of these analyses on large codebases written in multiple languages such as Linux and Apache Hadoop demonstrates that their Graspan implementations are language-independent, scale to millions of lines of code, and are much simpler than their original implementations. Moreover, we show that these analyses can be used to uncover many real-world bugs in large-scale systems code.

Periodically online verification has been widely recognized as a practical and promising method to handle the non-deterministic and unpredictable behavior of dynamic CPS systems. However, it is a challenge to keep the online verification of CPS systems finishing quickly in time to give enough time for the running system to respond, if any error is detected. Nevertheless, the problems under verification for each cycle are highly similar to each other. Most of the differences are caused by run-time factors like changing of parameters' values or the reorganization of active components in the system. Under this investigation, this paper presents an incremental verification technique for online verification of CPS systems. A method is given to distinguish the differences between the problem under verification and the previous verified problem. Then, by reusing the problem space of the previous verified problem as a warm-start base, the modified part can be introduced into the base, which can be solved incrementally and efficiently. A set of case studies on a real-case train control system is presented in this paper to demonstrate the performance of the incremental online verification technique.

Many real-world bugs in large-scale systems are related to object state that is supposed to obey a specified finite state machine (FSM). They are triggered when unexpected events occur on objects in certain states, making these objects transition in a way that violates their specifications. Detecting such FSM-related bugs with static analysis is challenging, especially in distributed systems that have large codebases.

The widespread real-time and embedded systems are mostly interrupt-driven because their heavy interaction with the environment is often initiated by interrupts. With the interrupt arrival being unpredictable and the interrupt handling being preemptive, a large number of possible system behaviours are generated, which makes the correctness assurance of such systems difficult and costly. Model checking is considered to be one of the effective methods for exhausting behavioural state space for correctness. However, existing modelling approaches for interrupt-driven systems are based on either calculus or automata theory, and have a steep learning curve. To address this problem, we propose a new modelling language called interrupt sequence diagram (ISD). By extending the popular UML sequence diagram notations, the ISD supports the modelling of interrupts' essential features visually and concisely. We also propose an automata-based semantics for ISD, based on which ISD can be transformed to a subset of hybrid automata so as to leverage the abundant off-the-shelf checkers. Experiments on examples from both real-world and existing literature were conducted, and the results demonstrate our approach's usability and effectiveness.

Numerical code is often applied in the safety-critical, but resource-limited areas. Hence, it is crucial for it to be correct and efficient, both of which are difficult to ensure. On one hand, accumulated rounding errors in numerical programs can cause system failures. On the other hand, arbitrary/infinite-precision arithmetic, although accurate, is infeasible in practice and especially in resource-limited scenarios because it performs thousands of times slower than floating-point arithmetic. Thus, it has been a significant challenge to obtain high-precision, easy-to-maintain, and efficient numerical code. This paper introduces a novel global optimization framework to tackle this challenge. Using our framework, a developer simply writes the infinite-precision numerical program directly following the problem's mathematical requirement specification. The resulting code is correct and easy-to-maintain, but inefficient. Our framework then optimizes the program in a global fashion (i.e., considering the whole program, rather than individual expressions or statements as in prior work), the key technical difficulty this work solves. To this end, it analyzes the program's numerical value flows across different statements through a symbolic trace extraction algorithm, and generates optimized traces via stochastic algebraic transformations guided by effective rule selection. We first evaluate our technique on numerical benchmarks from the literature; results show that our global optimization achieves significantly higher worst-case accuracy than the state-of-the-art numerical optimization tool. Second, we show that our framework is also effective on benchmarks having complicated program structures, which are challenging for numerical optimization. Finally, we apply our framework on real-world code to successfully detect numerical bugs that have been confirmed by developers.

Static program analysis is widely used in various application areas to solve many practical problems. Although researchers have made significant achievements in static analysis, it is still too challenging to perform sophisticated interprocedural analysis on large-scale modern software. The underlying reason is that interprocedural analysis for large-scale modern software is highly computation- and memory-intensive, leading to poor scalability. We aim to tackle the scalability problem by proposing a novel big data solution for sophisticated static analysis. Specifically, we propose a data-parallel algorithm and a join-process-filter computation model for the CFL-reachability based interprocedural analysis and develop an efficient distributed static analysis engine in the cloud, called BigSpa. Our experiments validated that BigSpa running on a cluster scales greatly to perform precise interprocedural analyses on millions of lines of code, and runs an order of magnitude or more faster than the existing state-of-the-art analysis tools.

Preferences, the setting options provided by Android, are an essential part of Android apps. Preferences allow users to change app features and behaviors dynamically, and therefore, need to be thoroughly tested. Unfortunately, the specific preferences used in test cases are typically not explicitly specified, forcing testers to manually set options or blindly try different option combinations. To effectively test the impacts of different preference options, this paper presents PREFEST, as a preference-wise enhanced automatic testing approach, for Android apps. Given a set of test cases, PREFEST can locate the preferences that may affect the test cases with a static and dynamic combined analysis on the app under test, and execute these test cases only under necessary option combinations. The evaluation shows that PREFEST can improve 6.8% code coverage and 12.3% branch coverage and find five more real bugs compared to testing with the original test cases. The test cost is reduced by 99% for both the number of test cases and the testing time, compared to testing under pairwise combination of options.

Modern software systems rely on information networks for communication. Such information networks are inherently unpredictable and unreliable. Consequently, software systems behave in an unstipulated manner in uncertain network conditions. Discovering unknown behaviors of these software systems in uncertain network conditions is essential to ensure their correct behaviors. Such discovery requires the development of systematic and automated methods. We propose an online and iterative model-based testing approach to evolve test models with search algorithms. Our ultimate aim is to discover unknown expected behaviors that can only be observed in uncertain network conditions. Also, we have implemented an adaptive search-based test case generation strategy to generate test cases that are executed on the system under test. We evaluated our approach with an open source video conference application-Jitsi with three search algorithms in comparison with random search. Results show that our approach is efficient in discovering unknown system behaviors. In particular, (1+1) Evolutionary Algorithm outperformed the other algorithms.

It is challenging to have a general solution to precisely detect arbitrary vulnerabilities. Thus security research has focused on detecting specific types of vulnerabilities. Missing checks for untrusted inputs used in security-sensitive operations are one of the major causes of various serious vulnerabilities. Efficiently detecting missing checks is essential for identifying insufficient attack protections and prognosing potential vulnerabilities. This paper proposes a systematic static approach to detect missing checks for manipulable data used in security-sensitive operations in C/C++ programs. We first locate customized security-sensitive operations with lightweight static analysis; then judge assailability of sensitive data used in security-sensitive operations via static taint analysis; finally, assess the existence and risk degree of missing checks using static analysis. We have implemented the approach into an automated and cross-platform tool, named Vanguard, on top of Clang/LLVM 3.6.0. Experimental results on open-source projects have shown its effectiveness and efficiency. Furthermore, Vanguard has led us to uncover five known vulnerabilities and two unknown bugs.

Dangling pointers have become an important class of software bugs that can lead to use-after-free and double-free vulnerabilities. So far, only a few approaches have been proposed to protect against dangling pointers, while most of them suffer from high overhead. In this paper, we propose a lightweight approach, named DangDone, to eliminate dangling pointers at compile time. Built upon the root cause of a dangling pointer, i.e., a pointer and its aliases are not nullified but the memory area they point to is deallocated, DangDone realizes the protection by inserting an intermediate pointer between the pointers (i.e., a pointer and its aliases) and the memory area they point to. Hence, nullifying the intermediate pointer will nullify the pointer and its aliases, which mitigates the vulnerabilities caused by dangling pointers. Experimental results have demonstrated that DangDone can protect target programs (i.e., the SPEC CPU benchmarks and the programs with known CVEs) with negligible runtime overhead (i.e., around 1% on average).

In regression GUI testing for Android apps, test scripts often fail due to changes to, rather than faults in, those apps. To avoid such false positives while still retaining the value of the old test scripts as much as possible, programmers need an automatic way to maintain the tests after the corresponding GUI has evolved. In this paper, we propose the CHATEM approach to automate GUI test script maintenance for Android apps. Taking as input the models for the GUIs of the base and updated version app and the original test scripts, CHATEM automatically extracts the changes between the two GUIs and generates maintenance actions for each change, which are then combined to form the maintenance actions for affected test scripts. In an experimental evaluation on 16 Android apps, CHATEM was able to automatically maintain the test scripts so that overall more than 95% of the remaining behaviors tested before are still tested, and almost 80% of the reusable test actions are retained in the result tests.

In safety verification of hybrid systems, barrier certificates are generated by solving the verification conditions derived from non-negative representations of different types. This paper presents a new computational method, sequential linear programming projection, for directly solving the set of verification conditions represented by the Krivine-Vasilescu-Handelman's positivstellensatz. The key idea is to decompose it into two successive optimization problems that refine the desired barrier certificate and those undetermined multipliers, respectively, and solve it in an iterative scheme. The most important benefit of the proposed approach lies in that it is much more effective than the LP relaxation method in producing real barrier certificates, and possesses a much lower computational complexity than the popular sum of square relaxation methods, which is demonstrated by the theoretical analysis on complexity and the experiment on a set of examples gathered from the literature.

Recent advances and industry standards in Internet of Things (IoT) have accelerated the real-world adoption of connected devices. To manage this hybrid system of digital real-time devices and analog environments, the industry has pushed several popular home automation IoT (HA-IoT) frameworks, such as If-This-Then-That (IFTTT), Apple HomeKit, and Google Brillo. Typically, users author device interactions by specifying the triggering sensor event and the triggered device command. In this seemingly simple software system, two dominant factors govern the system confidence properties with respect to the physical world. First, IoT users are largely nonexperts who lack the comprehensive consideration regarding potential impact and joint effect with existing rules. Second, while the increasing complexity of IoT devices enables fine-grained control (e.g., heater temperature) of continuous real-time environments, even two simply connected devices can have a huge state space to explore. In fact, bugs that wrongfully control devices and home appliances can have ramifications on system correctness and even user physical safety. It is crucial to help users to make sure the system they created meets their expectation. In this article we introduce how techniques from hybrid automata can be practically applied to assist nonexpert IoT users in the confidence checking of such hybrid HA-IoT systems. We propose an automated framework for end-to-end programming assistance. We build and check the Linear Hybrid Automata (LHA) model of the system automatically. We also present a quantifier elimination-based method to analyze the counterexample found and synthesize fix suggestions. We implemented a platform, MenShen, based on this framework and proposed techniques. We conducted sets of real HA-IoT case studies with up to 46 devices and 65 rules. Empirical results show that MenShen can find violations and generate rule fix suggestions in only 10 seconds.

The importance of regression testing in assuring the integrity of a program after changes is well recognized. One major obstacle in practicing regression testing is in maintaining tests that become obsolete due to evolved program behavior or specification. For mobile apps, the problem of maintaining obsolete GUI test scripts for regression testing is even more pressing. Mobile apps rely heavily on the correct functioning of their GUIs to compete on the market and provide good user experiences. But on the one hand, GUI tests break easily when changes happen to the GUI, On the other hand, mobile app developers often need to fight for a tight feedback loop and are left with limited time for test maintenance. In this paper, we propose a novel approach, called ATOM, to automatically maintain GUI test scripts of mobile apps for regression testing. ATOM uses an event sequence model to abstract possible event sequences on a GUI and a delta ESM to abstract the changes made to the GUI. Given both models as input, ATOM automatically updates the test scripts written for a base version app to reflect the changes. In an experiment with 22 versions from 11 production Android apps, ATOM updated all the test scripts affected by the version change, the updated scripts achieve over 80% of the coverage by the original scripts on the base version app, all except one set of updated scripts preserve over 60% of the actions in the original test scripts.

Multi-robot navigation control in the absence of reference trajectory is rather challenging as it is expected to ensure stability and feasibility while still offer fast computation on control decisions. The intrinsic high complexity of switched linear dynamical robots makes the problem even more challenging. In this paper, we propose a novel HMPC based method to address the navigation problem of multiple robots with switched linear dynamics. We develop a new technique to compute the reachable sets of switched linear systems and use them to enable the parallel computation of control parameters. We present theoretical results on stability, feasibility and complexity of the proposed approach, and demonstrate its empirical advance in performance against other approaches.

Interrupt-driven programs are widely deployed in safety-critical embedded systems to perform hardware and resource dependent data operation tasks. The frequent use of interrupts in these systems can cause race conditions to occur due to interactions between application tasks and interrupt handlers. Numerous program analysis and testing techniques have been proposed to detect races in multithreaded programs. Little work, however, has addressed race condition problems related to hardware interrupts. In this paper, we present SDRacer, an automated framework that can detect and validate race conditions in interrupt-driven embedded software. It uses a combination of static analysis and symbolic execution to generate input data for exercising the potential races. It then employs virtual platforms to dynamically validate these races by forcing the interrupts to occur at the potential racing points. We evaluate SDRacer on nine real-world embedded programs written in C language. The results show that SDRacer can precisely detect race conditions.

Mobile applications with complex GUIs are very popular today. However, generating test cases for these applications is often tedious professional work. On the one hand, manually designing and writing elaborate GUI scripts requires expertise. On the other hand, generating GUI scripts with record and playback techniques usually depends on repetitive work that testers need to interact with the application over and over again, because only one path is recorded in an execution. Automatic GUI testing focuses on exploring combinations of GUI events. As the number of combinations is huge, it is still necessary to introduce a test interface for testers to reduce its search space. This paper presents a sketch-guided GUI test generation approach for testing mobile applications, which provides a simple but expressive interface for testers to specify their testing purposes. Testers just need to draw a few simple strokes on the screenshots. Then our approach translates the strokes to a testing model and initiates a model-based automatic GUI testing. We evaluate our sketch-guided approach on a few real-world Android applications collected from the literature. The results show that our approach can achieve higher coverage than existing automatic GUI testing techniques with just 10-minute sketching for an application.

No abstract available.

Reachability analysis of linear hybrid automata (LHA) is an important problem. Classical model checking (CMC) technique is not scalable and not guaranteed to terminate. On the other hand, bounded model checking (BMC) is more cost-effective to conduct but can not guarantee the safety beyond the bound. In this paper, we seek to bridge the gap between BMC and CMC for reachability analysis of LHA. During BMC of LHA, typical procedures can discover sets of unsatisfiable constraint cores, which can be mapped back to path segments in the graph structure of LHA. If every path connecting the initial and target location has to go through such infeasible path segment, the target location is entirely not reachable. Based on this characteristic, we propose a LTL model checking based approach to check whether the target location is blocked. To further optimize the performance, we propose an automata based solution to check the LTL specification incrementally and adopt an on-the-fly algorithm to check the accepting condition to avoid an explicit construction of product automata.

The problem of probabilistic safety verification of stochastic hybrid systems is to check whether the probability that a given system will reach an unsafe region from certain initial states can be bounded by some given probability threshold. The paper considers stochastic hybrid systems where the behavior is governed by polynomial equalities and inequalities, as for usual hybrid systems, but the initial states follow some stochastic distributions. It proposes a new barrier certificate based method for probabilistic safety verification which guarantees the absolute safety in a infinite time horizon that is beyond the reach of existing techniques using either statistical model checking or probabilistic reachable set computation. It also gives a novel computational approach, by building and solving a constrained optimization problem coming from verification conditions of barrier certificates, to compute the lower bound on safety probabilities which can be compared with the given threshold. Experimental evidence is provided demonstrating the applicability of our approach on several benchmarks.

Numerical instability is a well-known problem that may cause serious runtime failures. This paper discusses the reason of instability in software development process, and presents a toolchain that not only detects the potential instability in software, but also diagnoses the reason for such instability. We classify the reason of instability into two categories. When it is introduced by software requirements, we call the instability caused by problem . In this case, it cannot be avoided by improving software development, but requires inspecting the requirements, especially the underlying mathematical properties. Otherwise, we call the instability caused by practice. We design our toolchain as four loosely-coupled tools, which combine stochastic arithmetic with infinite-precision testing. Each tool in our toolchain can be configured with different strategies according to the properties of the analyzed software. We evaluate our toolchain on subjects from literature. The results show that it effectively detects and separates the instabilities caused by problems from others. We also conduct an evaluation on the latest version of GNU Scientific Library, and the toolchain finds a few real bugs in the well-maintained and widely deployed numerical library. With the help of our toolchain, we report the details and fixing advices to the GSL buglist.

Buffer overflow is one of the most common types of software security vulnerabilities. Although researchers have proposed various static and dynamic techniques for buffer overflow detection, buffer overflow attacks against both legacy and newly-deployed software systems are still quite prevalent. Compared with dynamic detection techniques, static techniques are more systematic and scalable. However, there are few studies on the effectiveness of state-of-the-art static buffer overflow detection techniques. In this paper, we perform an in-depth quantitative and qualitative study on static buffer overflow detection. More specifically, we obtain both the buggy and fixed versions of 100 buffer overflow bugs from 63 real-world projects totalling 28 MLoC (Millions of Lines of Code) based on the reports in Common Vulnerabilities and Exposures (CVE). Then, quantitatively, we apply Fortify, Checkmarx, and Splint to all the buggy versions to investigate their false negatives, and also apply them to all the fixed versions to investigate their false positives. We also qualitatively investigate the causes for the false-negatives and false-positives of studied techniques to guide the design and implementation of more advanced buffer overflow detection techniques. Finally, we also categorized the patterns of manual buffer overflow repair actions to guide automated repair techniques for buffer overflow. The experiment data is available at http://bo-study.github.io/Buffer-Overflow-Cases/.

C programming language never performs automatic bounds checking in order to speed up execution. But bounds checking is absolutely necessary in any program. Because if a variable is out-of-bounds, some serious errors may occur during execution, such as endless loop or buffer overflows. When there are arrays used in a program, the index of an array must be within the boundary of the array. But programmers always miss the array bounds checking or do not perform a correct array bounds checking. In this paper, we perform static analysis based on taint analysis and data flow analysis to detect which arrays do not have correct array bounds checking in the program. And we implement an automatic static tool, Carraybound. And the experimental results show that Carraybound can work effectively and efficiently.

Existing CSP model checkers are incapable of verifying multiple properties concurrently in one run of a model checker, and when trying to alleviate state space explosion problem, most of reduction work are usually done after rather than before the complete state space was produced. Thus, A new CSP model checking tool named ACSPChecker was developed based on answer set programming, which is a declarative logic programming paradigm for solving combinational search problems with the feature of completely free of sequential dependencies, to verifying multiple properties concurrently in one run of a model checker. Additionally, It integrated an abstraction method, which could be used to alleviate the state space explosion before the complete state space was produced. Furthermore, a preprocessing technique of properties was proposed to improve the verification efficiency by reducing the expense spending on replicated verification of the same sub formulas. The feasibility and efficiency of ACSPChecker are illustrated by the experiments with a classic concurrency problem - dining philosophers problem.

Buffer overflow is one of the most common types of software vulnerabilities. Various static analysis and dynamic testing techniques have been proposed to detect buffer overflow vulnerabilities. With automatic tool support, static buffer overflow detection technique has been widely used in academia and industry. However, it tends to report too many false positives fundamentally due to the lack of software execution information. Currently, static warnings can only be validated by manual inspection, which significantly limits the practicality of the static analysis. In this paper, we present BovInspector, a tool framework for automatic static buffer overflow warnings inspection and validated bugs repair. Given the program source code and static buffer overflow vulnerability warnings, BovInspector first performs warning reachability analysis. Then, BovInspector executes the source code symbolically under the guidance of reachable warnings. Each reachable warning is validated and classified by checking whether all the path conditions and the buffer overflow constraints can be satisfied simultaneously. For each validated true warning, BovInspector fix it with three predefined strategies. BovInspector is complementary to prior static buffer overflow discovery schemes. Experimental results on real open source programs show that BovInspector can automatically inspect on average of 74.9% of total warnings, and false warnings account for about 25% to 100% (on average of 59.9%) of the total inspected warnings. In addition, the automatically generated patches fix all target vulnerabilities. Further information regarding the implementation and experimental results of BovInspector is available at http://bovinspectortool.github.io/project/. And a short video for demonstrating the capabilities of BovInspector is now available at https://youtu.be/IMdcksROJDg.

Symbolic execution is a widely-used program analysis technique. It collects and solves path conditions to guide the program traversing. However, due to the limitation of the current constraint solvers, it is difficult to apply symbolic execution on programs with complex path conditions, like nonlinear constraints and function calls. In this paper, we propose a new symbolic execution tool MLB to handle such problem. Instead of relying on the classical constraint solving, in MLB, the feasibility problems of the path conditions are transformed into optimization problems, by minimizing some dissatisfaction degree. The optimization problems are then handled by the underlying optimization solver through machine learning guided sampling and validation. MLB is implemented on the basis of Symbolic PathFinder and encodes not only the simple linear path conditions, but also nonlinear arithmetic operations, and even black-box function calls of library methods, into symbolic path conditions. Experiment results show that MLB can achieve much better coverage on complex real-world programs.

Precondition calculation is a fundamental program verification technique. Many previous works tried to solve this problem, but ended with limited capability due to loop statements. We conducted a survey on loops manipulating commonly-used data structures occurring in several real-world open-source programs, and found that about 80% of such loops iterate over elements of a data structure, indicating that automatic calculation of preconditions with respect to post-conditions of these loops would cover a great number of real-world programs and greatly ease code verification tasks. In this paper, we specify the execution effect of a program statement using the memories modified by the statement and the new values stored in these memories after executing the statement. Thus, conditional statements and loop statements can be uniformly reduced to a sequence of assignments. Also we present an approach to calculate preconditions with respect to given post-conditions of various program statements including loops that iterate over elements of commonly-used data structures (e.g., acyclic singly-linked lists) based on execution effects of these statements. With execution effects, post-conditions and loop invariants can also be generated. Our approach handles various types of data including numeric, boolean, arrays and user-defined structures. We have implemented the approach and integrated it into the code verification tool, Accumulator. We also evaluated the approach with a variety of programs, and the results show that our approach is able to calculate preconditions for different kinds of post-conditions, including linear ones and universally quantified ones. Preconditions generated with our approach can ease the verification task by reducing the burden of providing loop invariants and preconditions of loop statements manually, which improves the automatic level and efficiency, and makes the verification less error-prone.

This paper proposes a framework facilitating the analysis on inductively defined properties for recursive data structures. Our work has three main parts. First, it helps simplify the analysis of heap-manipulating programs by classifying inductive properties of recursive data structures into two classifications and each of them is handled with observed patterns. Second, we propose a technique called slicing and splicing to track and specify how data structures are manipulated by programs, in which data structures are first sliced into several parts and these parts are further spliced into new data structures. Third, this work presents a property-directed interprocedural analysis, together with an algorithm to check the boundaries of modified procedure-local heaps regarding the recursive data structures pointed to by the parameters passed to the procedures.

Interrupt-driven programs are often embedded in safety-critical systems to perform hardware/resource dependent data operation tasks, such as data acquisition, processing, and transformation. The interrupt programs and tasks may happen in parallel which in a result causes indeterminist concurrent problems at runtime. Data race is one of the most popular problems challenging researchers and practitioners. Various static analysis, software testing approaches have been proposed to detect data races in source code, testing, and even production run. However, static analysis may report too many false positives due to the lack of execution information. Dynamic testing may miss some important races since it could not generate adequate test cases to test all possible execution scenarios. In this paper, we propose a hybrid approach to detect data races in interrupt-driven programs based on static analysis and dynamic simulation. We implemented a prototype tool and conducted a controlled experiment to demonstrate the applicability of our approach.

Software test adequacy criteria are used to determine whether the test on a software system is sufficient. Code coverage shows how thoroughly a program is tested according to corresponding testing adequacy criteria. There are many coverage criteria used in practice to measure the test adequacy at different granularity of the target program. Length-n subpath criterion is a systematic flexible coverage criterion at a fine granularity. In this paper, we present a prototype test coverage tool named nCov for measuring length-n subpath coverage based on control flow graph. For a C program and corresponding test suite, our tool can measure the length-n subpath coverage for various n, say 1 to 8. It can also be used to select test cases for satisfying length-n subpath coverage with specific n. In addition, to improve the scalability of the tool, we propose a loop compression algorithm to record the program trace. We have conducted a controlled experiment to demonstrate the feasibility and efficiency of our tool.

The technique presented in this paper concerns the problem of how to automatically obtaining the specification of the resulting set of reachable nodes, after destructive operations over the data structure. Our work has two main contributions. First, we represent the node sets by expressions at pre-states, which facilitates the process of proving complex formulas efficiently. Second, we propose an improved version of the fold/unfold technique, which handles more general cases. Our approach is based on the observation that structure-update statements manipulate recursive data structures in a slice-and-splice way: the original data structures are sliced into several disjoint segments and these segments are further spliced into new data structures. Case studies on typical data structures show that our approach is effective and practical.

NAND flash has been widely adopted as storage devices in real-time embedded systems. However, garbage collection is needed to reclaim space and introduces a lot of time overhead. As the worst system latency is determined by the worst-case execution time of garbage collection in NAND flash, it is important to optimize garbage collection so as to give a deterministic worst system latency. On the other hand, since the garbage collection does not happen very often, optimizing garbage collection should not bring too much overhead to the average system latency. This paper presents for the first time a worst-case and average-case joint optimization scheme for garbage collection in NAND flash. With our scheme, garbage collection can be postponed to the latest stage so improves the average system latency. By combining partial garbage collection and over-provisioning, our scheme can guarantee that one free block is enough to hold all pages from both write requests and valid-page copies. The experiments have been conducted on a real embedded platform and the results show that our technique can improve both worstcase and average-case system latency compared with the previous works.

To help developers understand and reuse programs, semantic queries on the source code itself is attractive. Although programs in heterogeneous languages are being controlled for collaborative software development, most queries supported by various source code repositories are based either on the metadata of the repositories, or on indexed identifiers and method signatures. Few provide full support to search for semantic structures that are common across different programming languages. To facilitate the understanding and reuses, in this paper, we propose a novel source code query framework that (1) supports the semantic code queries across different programming languages with a new query language, (2) transforms source code to a unified abstract syntax format and handles heterogeneity at the abstract level, (3) stores source code on a cloud-based NoSQL storage in MangoDB. The efficiency of the framework has been evaluated and confirmed by experiments.

Due to many attractive and unique properties, NAND flash memory has been widely adopted in mission-critical hard real-time systems and some soft real-time systems. However, the nondeterministic garbage collection operation in NAND flash memory makes it difficult to predict the system response time of each data request. This article presents Lazy-RTGC , a real-time lazy garbage collection mechanism for NAND flash memory storage systems. Lazy-RTGC adopts two design optimization techniques: on-demand page-level address mappings, and partial garbage collection. On-demand page-level address mappings can achieve high performance of address translation and can effectively manage the flash space with the minimum RAM cost. On the other hand, partial garbage collection can provide the guaranteed system response time. By adopting these techniques, Lazy-RTGC jointly optimizes both the average and the worst system response time, and provides a lower bound of reclaimed free space. Lazy-RTGC is implemented in FlashSim and compared with representative real-time NAND flash memory management schemes. Experimental results show that our technique can significantly improve both the average and worst system performance with very low extra flash-space requirements.

The behavior space of real time hybrid systems is very complex and hence expensive to conduct the classical full state space model checking. Compared to the classical model checking, bounded model checking (BMC) is much cheaper to conduct and has better scalability. This work presents a technique that can derive, in some cases, a proof of unbounded reach ability argument of Linear Hybrid Automata (LHA) from a BMC procedure. During BMC of LHA, typical procedures can discover sets of unsatisfiable constraint cores, a.k.a. UC or IIS, in the constraint set according to the bounded continuous state space of LHA. Currently, such unsatisfiable constraints are only fed back to the constraint set to accelerate the BMC solving. In this paper, we propose that such unsatisfiable constraint core can be exploited to give general unbounded verification result of the system model. As each constraint can be mapped back to certain semantical elements of the system model, the unsatisfiable constraint cores can be mapped back into path segments, which are not feasible, in the graph structure of the LHA model. Clearly, if all the potential paths to reach the target location in the graph structure have to go through such infeasible path segments, the target location is not reachable in general, not only in the given bound. Based on this observation, we propose to encode the infeasible path segments as linear temporal logic (LTL) formulas, and present the graph structure, the discrete part, of the LHA model as a transition system. Then, we can take advantage of the mature off-the-shelf LTL model checking techniques to verify whether there exists a path to reach the target location without touching any detected IIS path segment in the graph structure of the LHA model. We implement this technique into a bounded LHA checker BACH. The experiments show that most of the benchmarks can be verified by the enhanced BACH with a clearly better performance and scalability.

Address mapping is one of the major functions in managing NAND flash. With the capacity increase of NAND flash, it becomes vitally important to reduce the RAM print of the address mapping table while not introducing big performance overhead. Demand-based address mapping is an effective approach to solve this problem, in which the address mapping table is stored in NAND flash (called translation pages), and mapping items are cached on-demand in RAM. Therefore, it is critical to manage translation pages in demand-based address mapping. This paper solves two most important problems in translation page management. First, to reduce frequent translation page updates caused by data requests, we propose a page-level caching mechanism to exploit the fundamental property of NAND flash where the basic read/write unit is one page. Second, to reduce the garbage collection overhead from translation pages, we propose a multiple write pointers strategy to group data pages corresponding to the same translation page into one data block, by which, when the data block is reclaimed via the garbage collection, we only need to update one translation page. We evaluate our scheme using a set of benchmarks from both real-world and synthetic traces. Experimental results show that our techniques can achieve significant reduction in the extra translation operations and improve the system response time.

It is encouraged to develop practical approaches to ensure that the software artifacts are created as expected or defect-free as early as possible. In the industry, software analysis and testing techniques are widely used solutions for codes and executables, respectively. However, software design artifacts can only be verified by manual peer review in design phase. In this paper, we propose an approach to automatically simulate the expected software behavior depicted in UML activity diagrams. First, UML activity diagrams are parsed and initialized semantically with a concrete execution. Second, the model is symbolically executed, to collect paths, input variables, and their path conditions. Then, the path conditions are passed to a constraint solver to generate a set of concrete value of possible input variables. Final, the generated concrete input variables are semantically executed on the model to identify the defects as well as to collect the execution path. The model simulation approach reuses the design models, automates the simulation process by using model-based concolic execution, and has the advantage of visibility and observability on model simulation. In addition, we found that the solvable paths represent behavioral scenarios. While simulating the model, input values corresponding to execution paths in the model are generated automatically. They can also be used as test suites to find the inconsistency between the design and implementation. We have also developed a prototype tool to support the above process, and have conducted a trivial case study to demonstrate the applicability of our approach.

Symbolic execution is a promising testing and analysis methodology. It systematically explores a program's execution space and can generate test cases with high coverage. One significant practical challenge for symbolic execution is how to effectively explore the enormous number of program paths in real-world programs. Various heuristics have been proposed for guiding symbolic execution, but they are generally inefficient and ad-hoc. In this paper, we introduce a novel, unified strategy to guide symbolic execution to less explored parts of a program. Our key idea is to exploit a specific type of path spectra, namely the length-n subpath program spectra, to systematically approximate full path information for guiding path exploration. In particular, we use frequency distributions of explored length-n subpaths to prioritize "less traveled" parts of the program to improve test coverage and error detection. We have implemented our general strategy in KLEE, a state-of-the-art symbolic execution engine. Evaluation results on the GNU Coreutils programs show that (1) varying the length n captures program-specific information and exhibits different degrees of effectiveness, and (2) our general approach outperforms traditional strategies in both coverage and error detection.

Dealing with crosscutting concerns has been a critical problem in software development processes. To facilitate handling crosscutting concerns at design phases, we proposed an aspect-oriented modeling and integration approach with UML activity diagrams. The primary concerns are depicted with UML activity diagrams as primary models, whereas crosscutting concerns are described with aspectual extended activity diagrams as aspect models. Aspect models can be integrated into primary models automatically. The AOM approach can reduce the complexity of design models. However, potential faults that violate desired properties of the software system might still be introduced during the modeling or integration processes. The verification technique is well-known for its ability to assure the correctness of models and uncover design problems before implementation. We propose a framework to verify aspect-oriented UML activity diagrams based on Petri net verification techniques. For verification purpose, we transform the integrated activity diagrams into Petri nets and prove the consistency of the transformation. Then, crosscutting concerns in system requirements are refined to properties in the form of CTL formulas. Finally, the Petri nets are verified against the formalized properties to report whether the aspect-oriented design models satisfies the requirements. Furthermore, we implement a tool named Jasmine-AOV to support the verification process. Case studies are conducted to evaluate the effectiveness of the proposed approach.

Data and its manipulation are essential in business processes (BPs). It is desirable to ensure within BP executions that every update to a database server guarantees to satisfy all relevant data integrity constraints (ICs). Furthermore, the earlier in a BP execution a violation is detected the more dependable the BP is. This paper studies the Process Safety Problem (PSP): will an incoming message be used in a database update causing IC violations? PSP is unsolvable in general. Taking advantage of the design-time "guard injection" technique, we propose a runtime proactive enforcement mechanism, called "process safe guarding", based on symbolic execution of BPEL processes for a bounded number of steps under "conservative strategy". Related challenges are also discussed.

Correct real-time behavior is an important aspect for time sensitive software, but it is difficult to get right. Time faults can be introduced not just during software development but also maintenance. So software maintainers without time information tend to have more chances to introduce unintended time behaviors. In this paper, we propose time change impact analysis to help maintainers estimate the potential influence of time changes on programs before the software evolves. Our main insight is that by being reminded and warned that a small-time change at some places in the source code will largely affect the whole task execution time, maintainers can be more cautious when updating such places. Because these places have a leverage effect that multiplies the task execution time in a subtle way, we call them time-leverage points. We give an approach to detect the time-leverage points based on a dynamic testing method, which instruments the program at a point for introducing a small delay and observes its impact on the task execution time. We implement a prototype tool and empirically evaluate the approach.

It is well-known that as software system evolves, the source code tends to deviate from its design model so that maintaining their consistence is challenging. Our objective is to detect code changes that influence designed program behaviour which are referred as design level changes and update the behavioural model timely and automatically to maintain consistence. We propose an approach that filters out low-level source code changes that do not influence program behaviour, abstracts code changes into updating operations for behavioral model, and automates the integration and update of activity diagrams to maintain consistence. We've recognised that it is not uncommon for developers to introduce quick and dirty implementation that unnecessarily increases program complexity or introduces suboptimal behaviour changes. So while merging code changes into behaviour model, our approach also calculates cyclometric complexity variation before and after the process so that developers can be alerted of significant and/or detrimental changes. Our tool allows the user to approve the change in code before merging and updating the model.

Regression testing is a widely used way to assure the quality of modified software. It requires executing a suite of test cases to ensure that modifications do not introduce any negative impact to software behavior. To collect test cases in the suite that can reveal modifications, different versions of software must be compared carefully. Existing approaches, relying on manual examination on programs or models to identify differences, are expensive. In the paper, we present a fully automatic approach to generating regression test cases based on activity diagram revision. By collecting execution traces and revising old activity diagrams, the approach firstly constructs new activity diagrams that can reveal software behavior changes. Then, both affected paths and new paths in activity diagrams are identified. Finally, an execution-based approach is applied to generate regression test cases whose execution can cover these paths. Experiments show the effectiveness of our approach.

Scenario-based specifications (SBSs), such as UML interaction models, offer an intuitive and visual way of describing design requirements, and are playing an increasingly important role in the design of software systems. This paper presents an approach to timing analysis of SBSs expressed by UML interaction models. The approach considers more general and expressive timing constraints in UML sequence diagrams (SDs), and gives a solution to the reachability analysis, constraint conformance analysis and bounded delay analysis problems, which reduces these problems into linear programs. With the synchronous interpretation of the SD compositions, the timing analysis algorithms in the approach form a decision procedure for a class of SBSs where any loop in any path is time-independent of the other parts in the path. These algorithms are also a semi-decision procedure for general SBSs with both the synchronous and asynchronous composition semantics. The approach also supports bounded timing analysis of SBSs, which investigates all the paths in the bound limit one by one, and performs the timing analysis for each finite path by linear programming. A tool prototype has been developed to support this approach. Copyright © 2010 John Wiley & Sons, Ltd. (This paper presents a linear programming-based approach to timing analysis of scenario-based specifications (SBSs) expressed by UML interaction models. With more general and expressive timing constraints in UML sequence diagrams, the algorithms in the approach solve the problems of the reachability, constraint conformance and bounded delay analysis of SBSs. These algorithms form a decision procedure for the loop-unlimited SBSs where any loop in any path is time-independent of the other parts in the path, and a semi-decision procedure for general SBSs.)

In run-time evolving systems, components may evolve while the system is being operated. Unsafe run-time changes may compromise the correct execution of the entire system. Traditional design-time verification techniques difficultly cope with run-time changes, and run-time monitoring may detect disfunctions only too late, when the failure arises. The desire would be to define advanced monitors with the ability to predict and prevent the potential errors happening in the future. In this direction, this paper proposes CASSANDRA, a new approach that by combining design-time and run-time analysis techniques, can “look ahead” in the near execution future, and predict potential failures. During run-time we on-the-fly construct a model of the future k-step global state space according to design-time specifications and the current execution state. Consequently, we can run-time check whether possible failures might happen in the future.

Existing reachability analysis techniques are easy to fail when applied to large compositional linear hybrid systems, since their memory usages rise up quickly with the increase of systems' size. To address this problem, we propose a tool BACH 2 that adopts a path-oriented method for bounded reachability analysis of compositional linear hybrid systems. For each component, a path is selected and all selected paths compose a path set for reachability analysis. Each path is independently encoded to a set of constraints while synchronization controls are encoded as a set of constraints too. By merging all the constraints into one set, the path-oriented reachability problem of a path set can be transformed to the feasibility problem of this resulting linear constraint set, which can be solved by linear programming efficiently. Based on this path-oriented method, BACH 2 adopts a shared label sequence guided depth first search (SLS-DFS) method to perform bounded reachability analysis of compositional linear hybrid system, where all potential path sets within the bound limit are identified and verified one by one. By this means, since only the structure of a system and the recently visited one path in each component need to be stored in memory, memory consumption of BACH 2 is very small at runtime. As a result, BACH 2 enables the verification of extremely large systems, as is demonstrated in our experiments.

Monitoring and fault tolerance are important approaches to give high confidence that long-running online software systems run correctly. But these approaches will certainly cause high overhead cost, i.e. the loss of efficiency. Multi-core platforms can make such cost acceptable because of the advantage of the parallel performance. For allowing ordinary software developers without any knowledge of multi-core platforms to handle such programming tasks more efficiently, we propose an approach to enable multi-core based monitoring and fault tolerance in C++/Java.

In recent years, coincidental correctness attracts many interests in testing area. Studies prove that it can adversely affect the effectiveness of testing. But current test adequacy criteria don't consider the effect of coincidental correctness. To address the problem, we design an approach to calculate the probability that an error in a given statement of the program under test is hidden by coincidental correctness. Such probability is used to measure the test adequacy on the statement. The test adequacy of a test suit is computed based on the adequacy on all the statement. A mutation analysis on five C programs is designed to compare the effectiveness of our adequacy criterion. The experimental results consistently approve our conjecture that such a test approach effectively quantizes the ability of test suite to find errors.

Writing reliable software is difficult. It becomes even more difficult when writing scientific software involving floating-point numbers. Computers provide numbers with limited precision; when confronted with a real whose precision exceeds that limit, they introduce approximation and error. Numerical analysts have developed sophisticated mathematical techniques for performing error and stability analysis of numerical algorithms. However, these are generally not accessible to application programmers or scientists who often do not have in-depth training in numerical analysis and who thus need more automated techniques to analyze their code.

The multi-core architecture brings more and more challenges and means to common software developers. Reliable software system design approaches can give a high confidence that long-running online software systems run correctly. But anyway these approaches will certainly cause the loss of the efficiency. We found that the multi-core architecture is a quite suitable platform to support reliable software system design and can make the cost acceptable because of its advantages of the parallel performance and prevalence. In this paper we make use of the multi-core architecture to support software fault tolerance. This approach will make the integration of software fault tolerance and the multi-core architecture as a common design choice. According to the idea of software fault tolerance, for some key software units in a system we can develop N separate versions of them with equivalent functionalities. Each version is developed independently by an isolated group to prevent identical faults among versions. All implemented versions run separately from same initial conditions and inputs. Outputs of all redundant versions are submitted to a decision module that determines a single result from multiple results as the correct output. In this paper, we give a case study to show that with the multi-core architecture, the redundant versions of a key software unit can run in parallel on different cores to improve the efficiency.

Program understanding plays an important role in the maintenance and reuse of open source code. Rapid evolving and bad documentation makes the understanding and reusing difficult. Design patterns are widely employed in the open source code. In this paper, we propose a design pattern directed clustering approach to help understand the structure of open source code. According to the approach, we have implemented a prototype tool. We also conducted an experiment on an open source system to evaluate it.

Test case generation based on design specifications is an important part of testing processes. In this paper, Unified Modeling Language activity diagrams are used as design specifications. By setting up several test adequacy criteria with respect to activity diagrams, an automatic approach is presented to generate test cases for Java programs. Instead of directly deriving test cases from activity diagrams, this approach selects test cases from a set of randomly generated ones according to a given test adequacy criterion. In the approach, we first instrument a Java program under testing according to its activity diagram model, and randomly generate abundant test cases for the program. Then, by running the instrumented program we obtain the corresponding program execution traces. Finally, by matching these traces with the behavior of the activity diagram, a reduced set of test cases are selected according to the given test adequacy criterion. This approach can also be used to check the consistency between the program execution traces and the behavior of activity diagrams.

Hybrid automata are well studied formal models for hybrid systems with both discrete and continuous state changes. However, the analysis of hybrid automata is quite difficult. Even for the simple class of linear hybrid automata, the reachability problem is undecidable. In the author's previous work, for linear hybrid automata we proposed a linear programming based approach to check one path at a time while the length of the path and the size of the automaton being checked can be large enough to handle problems of practical interest. Based on this approach, in this paper we present a prototype tool BACH to perform bounded reachability checking of linear hybrid automata. The experiment data shows that BACH has good performance and scalability, and supports our belief that BACH could become a powerful assistant to design engineers for the reachability analysis of linear hybrid automata.

Data race occurs when multiple threads simultaneously access shared data without appropriate synchronization, and at least one is write. System with a data race is nondeterministic and may generate different outputs even with the same input, according to different interleaving of data access. We present a model-based approach for detecting data races in concurrent Java programs. We extend UML Activity diagrams with data operation tags, to model program behavior. Program under test (PUT) is instrumented according to the model. It is then executed with random test cases generated based on path analysis of the model. Execution traces are reverse engineered and used for post-mortem verification. First, data races are identified by searching the time overlaps of entering and exiting critical sections of different threads. Second, implementation could be inconsistent with the design. The problem may tangle with race condition and makes it hard to detect races. We compare the event sequences with the behavior model for consistency checking. Identified inconsistencies help debuggers locate the defects in the PUT. A prototype tool named tocAj implements the proposed approach and was successfully applied to several cases studies.

The growing scale and complexity of the enterprise computing systems under distributed and heterogeneous environments present new challenges to system development, integration, and maintenance. In this paper, we present a model driven Web service development framework to combat these challenges. The framework capitalizes on the UML profile for Enterprise Distributed Object Computing (EDOC), MDA and Web services. Within the framework, first, the platform independent models (PIMs) are created using the EDOC profile. Second, the PIMs are broken down into sub PIMs according to functional decomposition, each of which can provide service independently and will be implemented in a Web service. Then, these sub PIMs are transformed into the corresponding Web service interface models for service publication and invoking. Finally, supported by model transform techniques, the sub PIMs are implemented into Web services on specific platforms. Automatic model transformation is the key to this framework, therefore, the transformation from EDOC models to Web service interface models within this framework is deeply discussed, and the detailed transformation rules are proposed. A case study is also provided to demonstrate the effectiveness of these rules and the merits of this framework

In this paper, we present a timed automaton reachability analysis algorithm which can use some other properties to improve the model checking efficiency. If the model checker aborts because of memory or CPU time limitation when checking a property P, the users can still use a set of auxiliary properties P1, P2,..., Pnabout the system to reduce the space and time requirement. People can verify these auxiliary properties by either model checking or other methods like theorem proving. This algorithm gives the users a way to reduce the space and time requirement of model checking using their knowledge about the system under check.

Test case generation is the most important part of the testing efforts, the automation of specification based test case generation needs formal or semi-formal specifications. As a semi-formal modelling language, UML is widely used to describe analysis and design specifications by both academia and industry, thus UML models become the sources of test generation naturally. Test cases are usually generated from the requirement or the code while the design is seldom concerned, this paper proposes an approach to generate test cases directly from UML activity diagram using Gray-box method, where the design is reused to avoid the cost of test model creation. In this approach, test scenarios are directly derived from the activity diagram modelling an operation. Then all the information for test case generation, i.e. input/output sequence and parameters, the constraint conditions and expected object method sequence, is extracted from each test scenario. At last, the possible values of all the input/output parameters could be generated by applying category-partition method, and test suite could be systematically generated to find the inconsistency between the implementation and the design. A prototype tool named UMLTGF has been developed to support the above process.

We use networks of UML statechart diagrams to model compositional designs for real-time systems, and present an algorithm for checking networks of statechart diagrams for the scenario-based specifications expressed by UML sequence diagrams with timing constraints. The algorithm is based on investigating the reachability graph of the integer state space of a network of statechart diagrams.

Abstract. This paper investigates the logic-automata-connection for Duration Calculus. It has been frequently observed that Duration Calculus with linear duration terms comes close to being a logic of linear hybrid automata. We attempt to make this relation precise by constructing Kleene-connection between duration-constrained regular expressions and a subclass of linear hybrid automata called loop-reset automata in which any variable tested in a loop is reset in the same loop. The formalism of duration-constrained regular expressions is an extension of regular expressions with duration constraints, which are essentially formulas of Duration Calculus without negation, yet extended by a Kleene-star operator. In this paper, we show that this formalism is equivalent in expressive power to loop-reset automata by providing a translation procedure from expressions to automata and vice verse.

For real-time systems, UML sequence diagrams describe interactions among objects, which show scenarios of the system behaviour. A simple UML sequence diagram describes exactly one scenario. For describing multiple scenarios and specifying real-time systems, we need to consider the compositions of UML sequence diagrams. In this paper, we introduce high-level graphs to describe compositions of UML sequence diagrams, and develop an algorithm for checking them for timing inconsistencies.

In object-oriented languages, encapsulation and inheritance play an important part for software reusability and maintainability. The separation of subtyping and inheritance makes inheritance a more flexible mechanism reusing code. The main enhanced flexibility is that it is allowed for subclasses to redefine inherited methods to change their specifications. However, it results in an encapsulation issue derived from the semantics of inheritance, which compromises severely reusability and maintainability in object-oriented languages. The authors present a modified inheritance mechanism which overcomes this encapsulation issue, and give its denotational semantics. This modified inheritance mechanism has been introduced in NDOOP, an object-oriented extension of Pascal bing developed by them.