Vision-Language Models (VLMs) extend Large Language Models (LLMs) with visual perception capabilities, unlocking broad applications across many domains. However, ensuring their safety remains a critical challenge, as adversarial visual inputs can easily bypass built-in safeguards and elicit harmful content. In this paper, we uncover a phenomenon we call delayed safety awareness, where a jailbroken VLM initially produces harmful content but ultimately recognizes the harmfulness at the end of the generation process. We attribute this phenomenon to the fact that the model's safety awareness against jailbreaks cannot be effectively transferred to the intermediate stages of text generation. Motivated by this insight, we introduce SafetyReminder, a simple yet effective defense that optimizes a learnable soft prompt using our proposed Safety-Activation Prompt Tuning (SAPT). This soft prompt is inserted into the generated text to activate the safety awareness of the model, steering it toward refusal when harmful content arises while preserving helpfulness in benign scenarios. We evaluate our method on three established harmful benchmarks and across three types of adversarial attacks. Experimental results demonstrate that our method achieves state-of-the-art defense performance with strong generalization, offering a practical and lightweight solution for safe deployment of VLMs.

Deep learning models often suffer from performance degradation in unseen domains, posing a risk for safety-critical applications such as autonomous driving. To tackle this problem, recent studies have leveraged pre-trained Visual Foundation Models (VFMs) to enhance generalization. However, exsiting works mainly focus on designing intricate networks for VFMs, neglecting their inherent strong generalization potential. Moreover, these methods typically perform inference on low-resolution images. The loss of detail hinders accurate predictions in unseen domains, especially for small objects. In this paper, we argue that simply fine-tuning VFMs and leveraging high-resolution images unleash the power of VFMs for generalizable semantic segmentation. Therefore, we design a VFM-based segmentation network (VFMNet) that adapts VFMs to this task with minimal fine-tuning, preserving their generalizable knowledge. Then, to fully utilize high-resolution images, we train a Mask-guided Refinement Network (MGRNet) to refine VFMNet's predictions combining detailed image features. Furthermore, we adopt a two-stage coarse-to-fine inference approach. MGRNet is used to refine the low-confidence regions predicted by VFMNet to obtain fine-grained results. Extensive experiments demonstrate the effectiveness of our method, outperforming state-of-the-art methods by 3.3% on the average mIoU in synthetic-to-real domain generalization.

Collecting and annotating data for semantic segmentation can end up costing a lot of time and energy. Unsupervised Domain Adaptation (UDA) for semantic segmentation allows models trained on certain source domain data (such as the GTA synthetic dataset) to be applied to certain target data (like the Cityscapes real dataset), significantly decreasing the requirement for target-domain manual pixel-level annotations.In this paper, we suggest a cross-domain unified semantic segmentation network training framework, the Attention Distribution Adaptation Network (ADAN). It (1) proposes the Content Consistency Transformation (CCT), which maps source domain data to an intermediate domain that has a data distribution that is comparable to that of the target domain, and (2) introduces the Attention Adaptation Module (AAM), which bolsters the synchronization of attention between the intermediate domain and the target domain. ADAN achieved unprecedented mIoUs of 77.2 and 68.8 on GTA→Cityscapes and Synthia→Cityscapes, respectively, corresponding to improvements of +1.3 and +0.6 over the state of the art.

Motion planning is a difficult task, especially when generating feasible future trajectories in complex and interactive scenarios. While recent advancements in imitation-based planning have shown significant progress, this approach often encounters causal confusion in dynamic traffic environments. This confusion will cause the planner to incorrectly associate certain actions with outcomes, leading to suboptimal or unsafe plans. To address this, we introduce a novel framework called$\overline{C}^{2}L$, which improves the planner's latent Causal understanding by incorporating Contrastive Learning and counterfactual data augmentation. Additionally, we propose a shortcut eliminator to extract copycat-free features from history states, reducing the impact of temporal spurious correlations. We validate our method on the nuPlan and interPlan benchmarks, with extensive experiments demonstrating that$C^{2}L$delivers highly competitive performance compared to state-of-the-art methods.

The fractal property has been regarded as a fundamental property of complex networks, characterizing the self-similarity of a network. Such a property is usually numerically characterized by the fractal dimension metric, and it not only helps the understanding of the relationship between the structure and function of complex networks but also finds a wide range of applications in complex systems. The existing literature shows that class-level software networks (i.e., class dependency networks) are complex networks with the fractal property. However, the fractal property at the feature (i.e., methods and fields) level has never been investigated, although it is useful for measuring class complexity and predicting bugs in classes. Furthermore, existing studies on the fractal property of software systems were all performed on un-weighted software networks and have not been used in any practical quality assurance tasks such as bug prediction. Generally, considering the weights on edges can give us more accurate representations of the software structure and thus help us obtain more accurate results. The illustration of an approach’s practical use can promote its adoption in practice. In this article, we examine the fractal property of classes by proposing a new metric. Specifically, we build a Feature-Level Software Network (FLSN) for each class to represent the methods/fields and their couplings (including coupling frequencies) within the class and propose a new metric, Fractal Dimension for Classes (FDC) , to numerically describe the fractal property of classes using FLSNs, which captures class complexity. We evaluate FDC theoretically against Weyuker’s nine properties, and the results show that FDC adheres to eight of the nine properties. Empirical experiments performed on a set of 12 large open source Java systems show that (i) for most classes (larger than \(96\%\) ), there exists the fractal property in their FLSNs, (ii) FDC is capable of capturing additional aspects of class complexity that have not been addressed by existing complexity metrics, (iii) FDC significantly correlates with both the existing class-level complexity metrics and the number of bugs in classes, and (iv) FDC , when used together with existing class-level complexity metrics, can significantly improve bug prediction in classes in three scenarios (i.e., bug-count , bug-classification , and effort-aware ) of the cross-project context, but in the within-project context, it cannot.

Icons are ubiquitous visual elements in graphic design, yet their creation is often complex and time-consuming. To resolve this problem, we draw inspiration from the booming text-to-image field and propose Text-Guided Icon Set Expansion, a novel task that helps users design high-quality icons using textual descriptions. Besides, users can control the style consistency of the created icons by inputting a few hand-crafted icons as style reference. Despite its practicality, the task poses two unique challenges. (i) Abstract Concept Visualization. Abstract concepts like technology and health are frequently encountered in icon creation, but their visualization is not straightforward and requires a grounding process that translates them into physical, easy-to-depict objects. (ii) Fine-grained Style Transfer. Unlike ordinary images, icons exhibit richer fine-grained stylistic elements, including tones, line widths, shapes, shadow effects, etc., which puts higher demands on capturing and preserving detailed styles during icon generation.

Key class identification approaches aim at identifying the most important classes to help developers, especially newcomers, start the software comprehension process. So far, many supervised and unsupervised approaches have been proposed; however, they have not considered the effort to comprehend classes. In this article, we identify the challenge of “ effort-aware key class identification ”; to partially tackle it, we propose an approach, EASE , which is implemented through a modification to existing unsupervised key class identification approaches to take into consideration the effort to comprehend classes. First, EASE chooses a set of network metrics that has a wide range of applications in the existing unsupervised approaches and also possesses good discriminatory power . Second, EASE normalizes the network metric values of classes to quantify the probability of any class to be a key class and utilizes Cognitive Complexity to estimate the effort required to comprehend classes. Third, EASE proposes a metric, RKCP , to measure the relative key-class proneness of classes and further uses it to sort classes in descending order. Finally, an effort threshold is utilized, and the top-ranked classes within the threshold are identified as the cost-effective key classes. Empirical results on a set of 18 software systems show that (i) the proposed effort-aware variants perform significantly better in almost all (≈98.33%) the cases, (ii) they are superior to most of the baseline approaches with only several exceptions, and (iii) they are scalable to large-scale software systems. Based on these findings, we suggest that (i) we should resort to effort-aware key class identification techniques in budget-limited scenarios; and (ii) when using different techniques, we should carefully choose the weighting mechanism to obtain the best performance.

Developing correct multi-threaded programs is challenging and concurrency bugs can be easily introduced. Many of them, known as concurrency vulnerabilities, can be exploited to launch attacks. Fuzzing is shown to be a practical and effective technique to expose vulnerabilities. However, existing works on fuzzing concurrency vulnerabilities almost all follow the framework (like AFL++) designed for fuzzing sequential vulnerabilities. Unlike sequential vulnerabilities, concurrency ones cannot be easily triggered. Concurrency vulnerabilities rely on both inputs and thread interleaving to be exposed while existing fuzzing techniques mainly focus on how to generate effective inputs. We present a new framework based on an existing fuzzing technique, AFL++, to integrate the predictive techniques for effective concurrency vulnerability detection. For every input (the original and the mutated ones), we call a predictive tool such that, even if a concurrency vulnerability is not really triggered, it can be predicted. To overcome heavy efficiency challenges existing in predictive tools, we propose to selectively call a predictive tool based on concurrency coverage criteria. We have selected a sound predictive tool SeqCheck and adapted it to propose our fuzzing framework PredFuzz. We compared our tool with two tools, AFL++ integrated with Google ThreadSanitizer and AFL++ directly integrated with SeqCheck, on six previously studied multi-threaded programs. The experimental results showed that PredFuzz detected significantly more vulnerabilities than AFL++ integrated with ThreadSanitizer and about 70% vulnerabilities detected by AFL++ directly integrated with SeqCheck. Besides, it is extremely efficient without compromising the fuzzing speed of AFL++: it added a smaller slowdown to AFL++ than ThreadSanitizer did and achieved a speedup of more than 1,000x when compared to AFL++ directly integrated with SeqCheck.

Conditional graphic layout generation, which generates realistic layouts according to user constraints, is a challenging task that has not been well-studied yet. First, there is limited discussion about how to handle diverse user constraints flexibly and uniformly. Second, to make the layouts conform to user constraints, existing work often sacrifices generation quality significantly. In this work, we propose LayoutFormer++ to tackle the above problems. First, to flexibly handle diverse constraints, we propose a constraint serialization scheme, which represents different user constraints as sequences of tokens with a predefined format. Then, we formulate conditional layout generation as a sequence-to-sequence transformation, and leverage encoder-decoder framework with Transformer as the basic architecture. Furthermore, to make the layout better meet user requirements without harming quality, we propose a decoding space restriction strategy. Specifically, we prune the predicted distribution by ignoring the options that definitely violate user constraints and likely result in low-quality layouts, and make the model samples from the restricted distribution. Experiments demonstrate that LayoutFormer++ outperforms existing approaches on all the tasks in terms of both better generation quality and less constraint violation.

Key classes are excellent starting points for developers, especially newcomers, to comprehend an unknown software system. Though many unsupervised key class identification approaches have been proposed in the literature by representing software as class dependency networks (aka software networks) and using some network metrics (e.g., h-index, a-index, and coreness), they are never aware of the field where the nodes exist and the effect of the field on the importance of the nodes in it. According to the classic field theory in physics, every material particle is in a field through which they exert an impact on other particles in the field via non-contact interactions (e.g., electromagnetic force, gravity, and nuclear force). Similarly, every node in a software network might also exist in a field, which might affect the importance of class nodes in it. In this paper, we propose an approach, iFit, to identify key classes in object-oriented software systems. First, we represent software as a CSNWD(Weighted Directed Class-level Software Network) to capture the topological structure of software, including classes, their couplings, and the direction and strength of couplings. Second, we assume that the nodes in the CSNWDexist in a gravitation-like field and propose a new metric, CG (Cumulative Gravitation-like importance), to measure the importance of classes. CG is inspired by Newton's gravitational formula and uses the PageRank value computed by a biased-PageRank algorithm as the masses of classes. Finally, classes in the system are sorted in descending order according to their CG values, and a cutoff is utilized, that is, the top-ranked classes are recommended as key classes. The experiments were performed on a data set composed of six open-source Java systems from the literature. The results show that iFit is superior to the baseline approaches on 93.75% of the total cases, and is scalable to large-scale software systems. Besides, we find that iFit is neutral to the weighting mechanisms used to assign the weights for different coupling types in the CSNWD, that is, when applying iFit to identify key classes, we can use any one of the weighting mechanisms.

Conditional graphic layout generation, which automatically maps user constraints to high-quality layouts, has attracted widespread attention today. Although recent works have achieved promising performance, the lack of versatility and data efficiency hinders their practical applications. In this work, we propose LayoutPrompter, which leverages large language models (LLMs) to address the above problems through in-context learning. LayoutPrompter is made up of three key components, namely input-output serialization, dynamic exemplar selection and layout ranking. Specifically, the input-output serialization component meticulously designs the input and output formats for each layout generation task. Dynamic exemplar selection is responsible for selecting the most helpful prompting exemplars for a given input. And a layout ranker is used to pick the highest quality layout from multiple outputs of LLMs. We conduct experiments on all existing layout generation tasks using four public datasets. Despite the simplicity of our approach, experimental results show that LayoutPrompter can compete with or even outperform state-of-the-art approaches on these tasks without any model training or fine-tuning. This demonstrates the effectiveness of this versatile and training-free approach. In addition, the ablation studies show that LayoutPrompter is significantly superior to the training-based baseline in a low-data regime, further indicating the data efficiency of LayoutPrompter. Our project is available at https://github.com/microsoft/LayoutGeneration/tree/main/LayoutPrompter.

Code documentation can be helpful in many software quality assurance tasks. However, due to resource constraints (e.g., time, human resources, and budget), programmers often cannot document their work completely and timely. In the literature, two approaches (one is supervised and the other is unsupervised) have been proposed to prioritize documentation effort to ensure the most important classes to be documented first. However, both of them contain several limitations. The supervised approach overly relies on a difficult-to-obtain labeled data set and has high computation cost. The unsupervised one depends on a graph representation of the software structure, which is inaccurate since it neglects many important couplings between classes. In this paper, we propose an improved approach, named Pride, to prioritize documentation effort. First, Pride uses a weighted directed class coupling network to precisely describe classes and their couplings. Second, we propose a PageRank-like algorithm to quantify the importance of classes in the whole class coupling network. Third, we use a set of software metrics to quantify source code complexity and further propose a simple but easy-to-operate filtering rule. Fourth, we sort all the classes according to their importance in descending order and use the filtering rule to filter out unimportant classes. Finally, a threshold$k$is utilized, and the top-$k$% ranked classes are the identified important classes to be documented first. Empirical results on a set of nine software systems show that, according to the average ranking of the Friedman test, Pride is superior to the existing approaches in the whole data set.

Autonomous vehicle (AV) systems must be comprehensively tested and evaluated before they can be deployed. High-fidelity simulators such as CARLA or LGSVL allow this to be done safely in very realistic and highly customizable environments. Existing testing approaches, however, fail to test simulated AVs systematically, as they focus on specific scenarios and oracles (e.g., lane following scenario with the “no collision” requirement) and lack any coverage criteria measures. In this paper, we propose$\mathtt {AVUnit}$, a framework for systematically testing AV systems against customizable correctness specifications. Designed modularly to support different simulators,$\mathtt {AVUnit}$consists of two new languages for specifying dynamic properties of scenes (e.g. changing pedestrian behaviour after waypoints) and fine-grained assertions about the AV's journey.$\mathtt {AVUnit}$further supports multiple fuzzing algorithms that automatically search for test cases that violate these assertions, using robustness and coverage measures as fitness metrics. We evaluated the implementation of$\mathtt {AVUnit}$for the LGSVL+Apollo simulation environment, finding 19 kinds of issues in Apollo, which indicate that the open-source Apollo does not perform well in complex intersections and lane-changing related scenarios.

The fairness characteristic is a critical attribute of trusted AI systems. A plethora of research has proposed diverse methods for individual fairness testing. However, they are suffering from three major limitations, i.e., low efficiency, low effectiveness, and model-specificity. This work proposes ExpGA, an explanation-guided fairness testing approach through a genetic algorithm (GA). ExpGA employs the explanation results generated by interpretable methods to collect high-quality initial seeds, which are prone to derive discriminatory samples by slightly modifying feature values. ExpGA then adopts GA to search discriminatory sample candidates by optimizing a fitness value. Benefiting from this combination of explanation results and GA, ExpGA is both efficient and effective to detect discriminatory individuals. Moreover, ExpGA only requires prediction probabilities of the tested model, resulting in a better generalization capability to various models. Experiments on multiple real-world benchmarks, including tabular and text datasets, show that ExpGA presents higher efficiency and effectiveness than four state-of-the-art approaches.

Autonomous driving systems (ADSs) must be tested thoroughly before they can be deployed in autonomous vehicles. High-fidelity simulators allow them to be tested against diverse scenarios, including those that are difficult to recreate in real-world testing grounds. While previous approaches have shown that test cases can be generated automatically, they tend to focus on weak oracles (e.g. reaching the destination without collisions) without assessing whether the journey itself was undertaken safely and satisfied the law. In this work, we propose , an automated framework for testing ADSs against real-world traffic laws, which is designed to be compatible with different scenario description languages. provides a rich driver-oriented specification language for describing traffic laws, and a fuzzing engine that searches for different ways of violating them by maximising specification coverage. To evaluate our approach, we implemented it for Apollo+LGSVL and specified the traffic laws of China. was able to find 14 violations of these laws, including 173 test cases that caused accidents.

Concurrent programs with multiple threads executing in parallel are widely used to unleash the power of multicore computing systems. Owing to their complexity, a lot of research focuses on testing and debugging concurrent programs. Besides correctness, we find that security can also be compromised by concurrency. In this article, we present concurrent program spectre (ConcSpectre), a new security threat that hides malware in nondeterministic thread interleavings. To demonstrate such threat, we have developed a stealth malware technique called concurrent logic bomb by partitioning a piece of malicious code and injecting its components separately into a concurrent program. The malicious behavior can be triggered by certain thread interleavings that rarely happen (e.g.,$< $1%) under a normal execution environment. However, with a new technique called controllable probabilistic activation, we can activate such ConcSpectre malware with a very high probability (e.g.,$>$90%) by remotely disturbing thread scheduling. In the evaluation, more than 1000 ConcSpectre samples are generated, which bypassed most of the antivirus engines in VirusTotal and four well-known online dynamic malware analysis systems. We also demonstrate how to remotely trigger a ConcSpectre sample on a web server and control its activation probability. Our work shows an urgent need for new malware analysis methods for concurrent programs.

In a very recent paper by Qu et al. (IEEE Transactions on Software Engineering, vol. 47 no. 2, pp. 348-366, Feb. 1 2021, doi:10.1109/TSE.2019.2892959), the authors propose an effective equation, top-core, to improve the performance of effort-aware bug prediction models. A distinctive feature of top-core is that it takes into account the coreness of a class in a Class Dependency Network (CDN) when calculating the relative risk of a class to be buggy. In this comment, we show that Qu et al.'s paper contains three shortcomings that may influence the performance of top-core or even have the potential to lead to erroneous results. First, we show that the CDN that they use to calculate the coreness of classes is not very accurate, neglecting many important types of dependency relations between classes such as method call relation, access relation, and instantiates relation. Second, they trained a Logistic Regression model using the scikit-learn framework to predict the probability of a specific class to be buggy. It is actually an L2 regularized Logistic Regression model, which is dependent on the scale of the features. But they neglected to normalize the features, making the obtained results erroneous. Finally, the number of execution times (viz. 10 times in the paper of Qu et al.) they used to reduce the bias caused by the randomness (viz. random split of instances and the process to handle class-imbalance problem) in the experiments is too small to ensure that the obtained results converge to stable values; but they failed to signify the precision level of their results for comparison. In this comment, we provide solutions to the problems by using i) an improved CDN (ICDN) to represent the structure of software systems, ii) the z-score method to normalize the features, and iii) an adaptive mechanism to determine the number of execution times. In the experiments, we find that Qu et al.'s approach based on the Logistic Regression model does not perform significantly better than the state-of-the-art approach Ree, which is inconsistent with the conclusion in Qu et al.'s work. We also observe that replacing CDN with ICDN does improve the performance of Qu et al.'s approach.

Jiaqi Guo, Ziliang Si, Yu Wang, Qian Liu, Ming Fan, Jian-Guang Lou, Zijiang Yang, Ting Liu. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2021.

Memory vulnerabilities are the main causes of software security problems. However, detecting vulnerabilities in multi-threaded programs is challenging because many vulnerabilities occur under specific executions, and it is hard to explore all possible executions of a multi-threaded program. Existing approaches are either computationally intensive or likely to miss some vulnerabilities due to the complex thread interleaving. This paper introduces a novel approach to detect concurrency memory vulnerabilities based on partial orders of events. A partial order on a set of events represents the definite execution orders of events. It allows constructing feasible traces exposing specific vulnerabilities by exchanging the execution orders of vulnerability-potential events. It also reduces the search space of possible executions and thus improves computational efficiency. We propose new algorithms to extract vulnerability-potential event pairs for three kinds of memory vulnerabilities. We also design a novel algorithm to compute a potential event pair's feasible set, which contains the relevant events required by a feasible trace. Our method extends existing approaches for data race detection by considering that two events are protected by the same lock. We implement a prototype of our approach and conduct experiments to evaluate its performance. Experimental results show that our tool exhibits superiority over state-of-the-art algorithms in both effectiveness and efficiency.

Clone detection is widely exploited for software vulnerability search. The approaches based on source code analysis cannot be applied to binary clone detection because the same source code can produce significantly different binaries due to different operating systems, microprocessor architectures and compilers. In this paper, we presentBinSeeker, a cross-platform binary seeker that integrates semantic learning and emulation. With the help of the labeled semantic flow graph,BinSeekercan quickly identify$M$candidate functions that are most similar to the vulnerability from the target binary. The value of$M$is relatively large so this semantic learning procedure essentially eliminates those functions that are very unlikely to have the vulnerability. Then, semantic emulation is conducted on these$M$candidates to obtain their dynamic signature sequences. By comparing signature sequences,BinSeekerproduces top-$N$functions that exhibit most similar behavior to that of the vulnerability. With fast filtering of semantic learning and accurate comparison of semantic emulation,BinSeekerseeks vulnerability precisely with little overhead. The experiments on six widely used programs with fifteen known CVE vulnerabilities demonstrate thatBinSeekeroutperforms three state-of-the-art toolsGenius,GeminiandCACompare. Regarding search accuracy,BinSeekerachieves an MRR value of 0.65 in the target programs, whereas the MRR values byGenius,GeminiandCACompareare 0.17, 0.07 and 0.42, respectively. If we consider ranking a function with the targeted vulnerability in the top-5 as accurate,BinSeekerachieves the accuracy of 93.33 percent, while the accuracy of the other three tools is merely 33.33, 13.33 and 53.33 percent, respectively. Such accuracy is achieved with 0.27s on average to determine whether the target binary function contains a known vulnerability, and the time for the other three tools are 1.57s, 0.15s and 0.98s, respectively. Compared to the time used to manually identify the true positive vulnerability from the false positive candidates reported by Gemini, the time overhead ofBinSeekeris negligible. Evidently, the proposedBinSeekerachieves a better balance between accuracy and efficiency.

Software comprehension is an important part of software maintenance. To understand a piece of large and complex software, the first problem to be solved is where to start the understanding process. Choosing to start the comprehension process from the important software elements has proven to be a practical way. Research on complex networks opens new opportunities for identifying important elements, and many approaches have been proposed. However, the software networks that existing approaches use neglect the multilayer nature of software systems. That is, nodes in the network can have different types of relationships at the same time, and each type of relationship forms a specific layer. Worse still, they mainly focus on identifying important classes, and little work has been done on quantifying package importance. In this paper, we propose an ElementRank approach to provide a ranked list of classes (or packages) for maintainers to start the comprehension process. The top-ranked classes (or packages) can be seen as the starting points for the software comprehension process at the class (or package) level. First, we introduce two kinds of multilayer software networks to describe the topological structure of software at the class level and package level, respectively. Second, we propose a weighted PageRank algorithm to calculate the weighted PageRank value of classes (or packages) in each layer of the corresponding multilayer software network. Then, we use AHP (Analytic Hierarchy Process) to weigh each layer in the corresponding multilayer software network, and further aggregate the weighted PageRank value to obtain the global weighted PageRank value for each class (or package). Finally, all the classes (or packages) are ranked according to their global weighted PageRank values in a descending order, and the top-ranked classes (or packages) can serve as the starting points for the software comprehension process at the class (or package) level. ElementRank is validated theoretically using the widely accepted Weyuker’s criteria. Theoretical results show that the global weighted PageRank value for classes (or packages) satisfies most of Weyuker’s properties. Furthermore, ElementRank is evaluated empirically using a set of twelve open source software systems. Through a set of experiments, we show the rank correlation between the results of ElementRank and that of the approaches in the related work, and the benefits of ElementRank are also illustrated in comparison with other approaches in the related work. Empirical results also show that ElementRank can be applied to large software systems.

Regression faults, which make working code stop functioning, are often introduced when developers make changes to the software. Many regression fault localization techniques have been proposed. However, issues like inaccuracy and lack of explanation are still obstacles for their practical application. In this work, we propose a trace-based approach to identifying not only where the root cause of a regression bug lies, but also how the defect is propagated to its manifestation as the explanation. In our approach, we keep the trace of original correct version as reference and infer the faulty steps on the trace of regression version so that we can build a causality graph of how the defect is propagated. To this end, we overcomes two technical challenges. First, we align two traces derived from two program versions by extending state-of-the-art trace alignment technique for regression fault with novel relaxation technique. Second, we construct causality graph (i.e., explanation) by adopting a technique calledalignment slicing and mendingto isolate the failure-inducing changes and explain the failure. Our comparative experiment with the state-of-the-art techniques including dynamic slicing, delta-debugging, and symbolic execution on 24 real-world regressions shows that (1) our approach is more accurate on isolating the failure-inducing changes, (2) the generated explanation requires acceptable manual effort to inspect, and (3) our approach requires lower runtime overhead. In addition, we also conduct an applicability experiment based on Defects4J bug repository, showing the potential limitations of our trace-based approach and providing guidance for its practical use.

The great influence of Bitcoin has promoted the rapid development of blockchain-based digital currencies, especially the altcoins, since 2013. However, most altcoins share similar source codes, resulting in concerns about code innovations. In this paper, an empirical study on existing altcoins is carried out to offer a thorough understanding of various aspects associated with altcoin innovations. Firstly, we construct the dataset of altcoins, including source code repositories, GitHub fork relations, and market capitalizations (cap). Then, we analyze the altcoin innovations from the perspective of source code similarities. The results demonstrate that more than 85% of altcoin repositories present high code similarities. Next, a temporal clustering algorithm is proposed to mine the inheritance relationship among various altcoins. The family pedigrees of altcoin are constructed, in which the altcoin presents similar evolution features as biology, such as power-law in family size, variety in family evolution, etc. Finally, we investigate the correlation between code innovations and market capitalization. Although we fail to predict the price of altcoins based on their code similarities, the results show that altcoins with higher innovations reflect better market prospects.

Smart contracts empowered by blockchains often manage digital assets in a distributed and decentralized environment. People believe in smart contracts based on these new technologies. Unfortunately, malicious smart contacts, such as smart Ponzi scheme contracts (ponzitracts, for short), pose risk. Existing techniques detect ponzitracts by analyzing the code as well as a large amount of transaction data after time-consuming deployment. However, a conclusion based on transaction data can only be gotten after the damage has been caused. This paper proposes PonziDetector, a ponzitract detection technique that does not rely on transaction data. Behavior forest is introduced into PonziDetector to capture dynamic behaviors of smart contracts during interacting with them, which makes it possible to early detect ponzitracts. The empirical study demonstrates that PonziDetector, without transaction data, can improve the precision and the recall of the state-of-the-art to 94.6% and 93.0% respectively. This means that PonziDetector can avoid potential losses by early detecting ponzitracts.

With the advent of multicore processors, there is a great need to write parallel programs to take advantage of parallel computing resources. However, due to the nondeterminism of parallel execution, the malware behaviors sensitive to thread scheduling are extremely difficult to detect. Dynamic taint analysis is widely used in security problems. By serializing a multithreaded execution and then propagating taint tags along the serialized schedule, existing dynamic taint analysis techniques lead to under-tainting with respect to other possible interleavings under the same input. In this paper, we propose an approach called DSTAM that integrates symbolic analysis and guided execution to systematically detect tainted instances on all possible executions under a given input. Symbolic analysis infers alternative interleavings of an executed trace that cover new tainted instances, and computes thread schedules that guide future executions. Guided execution explores new execution traces that drive future symbolic analysis. We have implemented a prototype as part of an educational tool that teaches secure C programming, where accuracy is more critical than efficiency. To the best of our knowledge, DSTAM is the first algorithm that addresses the challenge of taint analysis for multithreaded program under fixed inputs.

State-of-the-art fuzzers implement various optimizations to enhance their performance. As the optimizations reside in different stages such as input seed selection and mutation, it is tempting to combine the optimizations in different stages. However, our initial attempts demonstrate that naive combination actually worsens the performance, which explains that most optimizations are still isolated by stages and metrics. In this paper, we present InteFuzz, the first framework that synergically integrates multiple fuzzing optimizations. We analyze the root cause for performance degradation in naive combination, and discover optimizations conflict in coverage criteria and optimization granularity. To resolve the conflicts, we propose a novel priority-based scheduling mechanism. The dynamic integration considers both branch-based and block-based coverage feedbacks that are used by most fuzzing optimizations. In our evaluation, we extract four optimizations from popular fuzzers such as AFLFast and FairFuzz and compare InteFuzz against naive combinations. The evaluation results show that InteFuzz outperforms the naive combination by 29% and 26% in path-and branch-coverage. Additionally, InteFuzz triggers 222 more unique crashes, and discovers 33 zero-day vulnerabilities in real-world projects with 12 registered as CVEs.

Record-and-replay tools are indispensable for quality assurance of mobile applications. Due to its importance, an increasing number of tools are being developed to record and replay user interactions for Android. However, by conducting an empirical study of various existing tools in industrial settings, researchers have revealed a gap between the characteristics requested from industry and the performance of publicly available record-and-replay tools. The study concludes that no existing tools under evaluation are sufficient for industrial applications. In this paper, we present a record-and-replay tool called SARA towards bridging the gap and targeting a wide adoption. Specifically, a dynamic instrumentation technique is used to accommodate rich sources of inputs in the application layer satisfying various constraints requested from industry. A self-replay mechanism is proposed to record more information of user inputs for accurate replaying without degrading user experience. In addition, an adaptive replay method is designed to enable replaying events on different devices with diverse screen sizes and OS versions. Through an evaluation on 53 highly popular industrial Android applications and 265 common usage scenarios, we demonstrate the effectiveness of SARA in recording and replaying rich sources of inputs on the same or different devices.

Concurrency vulnerabilities are extremely harmful and can be frequently exploited to launch severe attacks. Due to the non-determinism of multithreaded executions, it is very difficult to detect them. Recently, data race detectors and techniques based on maximal casual model have been applied to detect concurrency vulnerabilities. However, the former are ineffective and the latter report many false negatives. In this paper, we present CONVUL, an effective tool for concurrency vulnerability detection. CONVUL is based on exchangeable events, and adopts novel algorithms to detect three major kinds of concurrency vulnerabilities. In our experiments, CONVUL detected 9 of 10 known vulnerabilities, while other tools only detected at most 2 out of these 10 vulnerabilities. The 10 vulnerabilities are available at https://github.com/mryancai/ConVul.

Test case prioritization is widely used in testing with the purpose of detecting faults as early as possible. Most existing techniques exploit coverage to prioritize test cases based on the hypothesis that a test case with higher coverage is more likely to catch bugs. Statement coverage and function coverage are the two widely used coverage granularity. The former typically achieves better test case prioritization in terms of fault detection capability, while the latter is more efficient because it incurs less overhead. In this paper we argue that static information such as statement and function coverage may not be the best criteria for guiding dynamic executions. Executions that cover the same set of statements /functions can may exhibit very different behavior. Therefore, the abstraction that reduces program behavior to statement/function coverage can be too simplistic to predicate fault detection capability. We propose a new approach that exploits function call sequences to prioritize test cases. This is based on the observation that the function call sequences rather than the set of executed functions is a better indicator of program behavior. Test cases that reveal unique function call sequences may have better chance to encounter faults. We choose function instead of statement sequences due to the consideration of efficiency. We have developed and implemented a new prioritization strategy AGC (Additional Greedy method Call sequence), that exploit function call sequences. We compare AGC against existing test case prioritization techniques on eight real-world open source Java projects. Our experiments show that our approach outperforms existing techniques on large programs (but not on small programs) in terms of bug detection capability. The performance shows a growth trend when the size of program increases.

Reproducibility is the ability of recreating identical binaries under pre-defined build environments. Due to the need of quality assurance and the benefit of better detecting attacks against build environments, the practice of reproducible builds has gained popularity in many open-source software repositories such as Debian and Bitcoin. However, identifying the unreproducible issues remains a labour intensive and time consuming challenge, because of the lacking of information to guide the search and the diversity of the causes that may lead to the unreproducible binaries.

As multithreaded programs become increasingly popular, plagiarism of multithreaded programs starts to plague the software industry. Although there has been tremendous progress on software plagiarism detection technology, existing dynamic birthmark approaches are applicable only to sequential programs, due to the fact that thread scheduling nondeterminism severely perturbs birthmark generation and comparison. We propose a framework called TOB (Thread-oblivious dynamic Birthmark) that revives existing techniques so they can be applied to detect plagiarism of multithreaded programs. This is achieved by thread-oblivious algorithms that shield the influence of thread schedules on executions. We have implemented a set of tools collectively called TOB-PD (TOB based Plagiarism Detection tool) by applying TOB to three existing representative dynamic birthmarks, including SCSSB (System Call Short Sequence Birthmark), DYKIS (DYnamic Key Instruction Sequence birthmark) and JB (an API based birthmark for Java). Our experiments conducted on large number of binary programs show that our approach exhibits strong resilience against state-of-the-art semantics-preserving code obfuscation techniques. Comparisons against the three existing tools SCSSB, DYKIS and JB show that the new framework is effective for plagiarism detection of multithreaded programs. The tools, the benchmarks and the experimental results are all publicly available.

Symbolic execution is emerging as a powerful technique for generating test inputs systematically to achieve exhaustive path coverage of a bounded depth. However, its practical use is often limited by path explosion because the number of paths of a program can be exponential in the number of branch conditions encountered during the execution. To mitigate the path explosion problem, we propose a new redundancy removal method called postconditioned symbolic execution. At each branching location, in addition to determine whether a particular branch is feasible as in traditional symbolic execution, our approach checks whether the branch is subsumed by previous explorations. This is enabled by summarizing previously explored paths by weakest precondition computations. Postconditioned symbolic execution can identify path suffixes shared by multiple runs and eliminate them during test generation when they are redundant. Pruning away such redundant paths can lead to a potentially exponential reduction in the number of explored paths. Since the new approach is computationally expensive, we also propose several heuristics to reduce its cost. We have implemented our method in the symbolic execution engine KLEE [1] and conducted experiments on a large set of programs from the GNU Coreutils suite. Our results confirm that redundancy due to common path suffix is both abundant and widespread in real-world applications.

Driven by new software development processes and testing in clouds, system and integration testing nowadays tends to produce enormous number of alarms. Such test alarms lay an almost unbearable burden on software testing engineers who have to manually analyze the causes of these alarms. The causes are critical because they decide which stakeholders are responsible to fix the bugs detected during the testing. In this paper, we present a novel approach that aims to relieve the burden by automating the procedure. Our approach, called Cause Analysis Model, exploits information retrieval techniques to efficiently infer test alarm causes based on test logs. We have developed a prototype and evaluated our tool on two industrial datasets with more than 14,000 test alarms. Experiments on the two datasets show that our tool achieves an accuracy of 58.3% and 65.8%, respectively, which outperforms the baseline algorithms by up to 13.3%. Our algorithm is also extremely efficient, spending about 0.1s per cause analysis. Due to the attractive experimental results, our industrial partner, a leading information and communication technology company in the world, has deployed the tool and it achieves an average accuracy of 72% after two months of running, nearly three times more accurate than a previous strategy based on regular expressions.

With the advent of multicore processors, there is a trend towards multithreading to take advantage of parallel computing resources. Due to greatly increased complexity, programmers need effective testing methodology that can thoroughly test multithreaded programs. There has been significant progress based on symbolic execution that attempts to exhaustively explore all the intra-thread paths and inter-thread interleavings. However, such testing approach faces two insuperable challenges. Firstly, exploring an astronomically large number of paths and interleavings limits its scalability. Secondly, a path itself does not directly help programmers understand program behavior. In this paper, we propose an alternate testing methodology that focuses on definition-use data flow instead of paths/interleavings. Such approach not only leads to orders of magnitude reduction in testing complexity, but also gives programmers direct help on examining the shared variable usage in a multithreaded program.

Predicting the number of defects in software modules can be more helpful in the case of limited testing resources. The highly imbalanced distribution of the target variable values (i.e., the number of defects) degrades the performance of models for predicting the number of defects. As the first effort of an in-depth study, this paper explores the potential of using resampling techniques and ensemble learning techniques to learn from imbalanced defect data for predicting the number of defects. We study the use of two extended resampling strategies (i.e., SMOTE and RUS) for regression problem and an ensemble learning technique (i.e., the AdaBoost.R2 algorithm) to handle imbalanced defect data for predicting the number of defects. We refer to the extension of SMOTE and RUS for predicting the Number of Defects as SmoteND and RusND, respectively. Experimental results on 6 datasets with two performance measures show that these approaches are effective in handling imbalanced defect data. To further improve the performance of these approaches, we propose two novel hybrid resampling/boosting algorithms, called SmoteNDBoost and RusNDBoost, which introduce SmoteND and RusND into the AdaBoost.R2 algorithm, respectively. Experimental results show that SmoteNDBoost and RusNDBoost both outperform their individual components (i.e., SmoteND, RusND and AdaBoost.R2).

Graphic user interface (GUI) is an integral part of many software applications. However, GUI testing remains a challenging task. The main problem is to generate a set of high-quality test cases, i.e., sequences of user events to cover the often large input space. Since manually crafting event sequences is labor-intensive and automated testing tools often have poor performance, we propose a new GUI testing framework to efficiently generate progressively longer event sequences while avoiding redundant sequences. Our technique for identifying the redundancy among these sequences relies on statically checking a set of simple and syntactic-level conditions, whose reduction power matches and sometimes exceeds that of classic techniques based on partial order reduction. We have evaluated our method on 17 Java Swing applications. Our experimental results show the new technique, while being sound and systematic, can achieve more than 10X reduction in the number of test sequences compared to the state-of-the-art GUI testing tools.

Data race is a major source of concurrency bugs. Dynamic data race detection tools (e.g., FastTrack) monitor the execu-tions of a program to report data races occurring in runtime. However, such tools incur significant overhead that slows down and perturbs executions. To address the issue, the state-of-the-art dynamic data race detection tools (e.g., LiteRace) ap-ply sampling techniques to selectively monitor memory access-es. Although they reduce overhead, they also miss many data races as confirmed by existing studies. Thus, practitioners face a dilemma on whether to use FastTrack, which detects more data races but is much slower, or LiteRace, which is faster but detects less data races. In this paper, we propose a new sam-pling approach to address the major limitations of current sampling techniques, which ignore the facts that a data race involves two threads and a program under testing is repeatedly executed. We develop a tool called AtexRace to sample memory accesses across both threads and executions. By selectively monitoring the pairs of memory accesses that have not been frequently observed in current and previous executions, AtexRace detects as many data races as FastTrack at a cost as low as LiteRace. We have compared AtexRace against FastTrack and LiteRace on both Parsec benchmark suite and a large-scale real-world MySQL Server with 223 test cases. The experiments confirm that AtexRace can be a replacement of FastTrack and LiteRace.

Software developers can search, share and learn development experience, solutions, bug fixes and open source projects in software information sites such as StackOverflow and Freecode. Many software information sites rely on tags to classify their contents, i.e. software objects, in order to improve the performance and accuracy of various operations on the sites. The quality of tags thus has a significant impact on the usefulness of these sites. High quality tags are expected to be concise and can describe the most important features of the software objects. Unfortunately tagging is inherently an uncoordinated process. The choice of tags made by individual software developers is dependent not only on a developer's understanding of the software object but also on the developer's English skills and preferences. As a result, the number of different tags grows rapidly along with continuous addition of software objects. With thousands of different tags, many of which introduce noise, software objects become poorly classified. Such phenomenon affects negatively the speed and accuracy of developers' queries. In this paper, we propose a tool called TagMulRec to automatically recommend tags and classify software objects in evolving large-scale software information sites. Given a new software object, TagMulRec locates the software objects that are semantically similar to the new one and exploit their tags. We have evaluated TagMulRec on four software information sites, StackOverflow, AskUbuntu, AskDifferent and Freecode. According to our empirical study, TagMulRec is not only accurate but also scalable that can handle a large-scale software information site with millions of software objects and thousands of tags.

Symbolic execution is a powerful technique for systematically exploring the paths of a program and generating the corresponding test inputs. However, its practical usage is often limited by thepath explosionproblem, that is, the number of explored paths usually grows exponentially with the increase of program size. In this paper, we argue that for the purpose of fault detection it is not necessary to systematically explore the paths, and propose a new symbolic execution approach to mitigate the path explosion problem by predicting and eliminating the redundant paths based on symbolic value. Our approach can achieve the equivalent fault detection capability as traditional symbolic execution without exhaustive path exploration. In addition, we develop a practical implementation called Dependence Guided Symbolic Execution (DGSE) to soundly approximate our approach. Through exploiting program dependence, DGSE can predict and eliminate the redundant paths at a reasonable computational cost. Our empirical study shows that the redundant paths are abundant and widespread in a program. Compared with traditional symbolic execution, DGSE only explores 6.96 to 96.57 percent of the paths and achieves a speedup of 1.02$\times$to 49.56$\times$. We have released our tool and the benchmarks used to evaluate DGSE$^\ast$.

Software defect prediction aims to determine whether a software module is defect-prone by constructing prediction models. The performance of such models is susceptible to the high dimensionality of the datasets that may include irrelevant and redundant features. Feature selection is applied to alleviate this issue. Because many feature selection methods have been proposed, there is an imperative need to analyze and compare these methods. Prior empirical studies may have potential controversies and limitations, such as the contradictory results, usage of private datasets and inappropriate statistical test techniques. This observation leads us to conduct a careful empirical study to reinforce the confidence of the experimental conclusions by considering several potential source of bias, such as the noise in the dataset and the dataset types. In this paper, we investigate the impact of 32 feature selection methods on the defect prediction performance over two versions of the NASA dataset (i.e., the noisy and clean NASA datasets) and one open source AEEEM dataset. We use a state-of-the-art double Scott-Knott test technique to analyze these methods. Experimental results show that the effectiveness of these feature selection methods on defect prediction performance varies significantly over all the datasets.

Concurrency bugs only occur under certain interleaving. Existing randomized techniques are usually ineffective. PCT innovatively generates scheduling, before executing a program, based on priori-ties and priority change points. Hence, it provides a probabilistic guarantee to trigger concurrency bugs. PCT randomly selects prior-ity change points among all events, which might be effective for non-deadlock concurrency bugs. However, deadlocks usually in-volve two or more threads and locks, and require more ordering constraints to be triggered. We interestingly observe that, every two events of a deadlock usually occur within a short range. We gener-ally formulate this range as the bug Radius, to denote the max dis-tance of every two events of a concurrency bug. Based on the bug radius, we propose RPro (Radius aware Probabilistic testing) for triggering deadlocks. Unlike PCT, RPro selects priority change points within the radius of the targeted deadlocks but not among all events. Hence, it guarantees larger probabilities to trigger dead-locks. We have implemented RPro and PCT and evaluated them on a set of real-world benchmarks containing 10 unique deadlocks. The experimental results show that RPro triggered all deadlocks with higher probabilities (i.e., >7.7x times larger on average) than that by PCT. We also evaluated RPro with radius varying from 1 to 150 (or 300). The result shows that the radius of a deadlock is much smaller (i.e., from 2 to 114 in our experiment) than the num-ber of all events. This further confirms our observation and makes RPro meaningful in practice.

GUIs are event-driven applications where the flow of the program is determined by user actions such as mouse clicks and key presses. GUI testing is a challenging task not only because of the combinatorial explosion in the number of event sequences, but also because of the difficulty to cover the large number of data values. We propose GUICat, the first cloud based GUI testing framework that simultaneously generates event sequences and data values. It is a white-box GUI testing tool that augments traditional sequence generation techniques with concolic execution. We also propose a cloudbased parallel algorithm for mitigating both event sequence explosion and data value explosion, by distributing the concolic execution tasks over public clouds such as Amazon EC2. We have evaluated the tool on standard GUI testing benchmarks and showed that GUICat significantly outperforms state-of-the-art GUI testing tools. The video demo URL is https://youtu.be/rfnnQOmZqj4.

Bug triaging refers to the process of assigning a bug to the most appropriate fixer. As the scale and complexity of software increases, bug triaging becomes a tedious and time-consuming work. Existing bug triaging approaches typically treat it as a problem of optimizing recommendation accuracy. However, the time that different fixers may spend also varies. Thus, we take time cost as another optimizing objective aside from accuracy and use modern portfolio theory to strike a balance between them. In addition, for fixers with little fixing records, we need more data to build profiles about their expertise. To address these problems, we propose a bug triaging approach with awareness of accuracy and time cost, and we use bug reports from other projects to enrich the bug fixing history of fixers. We evaluate our approach with experiments on data collected from Bugzilla. The experiment results validate the effectiveness of our approach.

Linguistic pairwise comparison matrices are widely used in decision-making procedures. However, the matrices often give conflicting results when there are multiple criteria under consideration. Despite intensive research, achieving consistency of such matrices remains a daunting task. In this paper, a novel approach based on linguistic discrete region is proposed to address the challenge. Unlike existing methods that require a single value for each comparison, our approach allows a comparison to be expressed by a discrete region with multiple linguistic terms. Such front-end gives users more freedom to express their opinions. In the back-end, we propose an iterative searching algorithm that is able to achieve approximate optimal consistency for the comparison matrices with discrete region values. The final results are single-value matrices that not only guarantee approximate optimal consistency but comply with evaluators' intentions a well, as our approach does not modify any linguistic values like many existing methods. We have conducted extensive evaluations, and our empirical study confirms that the linguistic discrete region-based approach significantly improves the consistency of linguistic pairwise comparison matrices.

We propose a new automated debugging method for regression testing based on a synergistic application of both dynamic and semantic analysis. Our method takes a failure- inducing test input, a buggy program, and an earlier correct version of the same program, and computes a minimal set of code changes responsible for the failure, as well as explaining how the code changes lead to the failure. Although this problem has been the subject of intensive research in recent years, existing methods are rarely adopted by developers in practice since they do not produce sufficiently accurate fault explanations for real applications. Our new method is significantly faster and more accurate than existing methods for explaining failed regression tests in real applications, due to its synergistic analysis framework that iteratively applies both dynamic analysis and a constraint solver based semantic analysis to leverage their complementary strengths. We have implemented our new method in a software tool based on the LLVMcompiler and the KLEE symbolic virtual machine. Our experiments on large real Linux applications show that the new method is both efficient and effective in practice.

Symbolic execution is emerging as a powerful technique for generating test inputs systematically to achieve exhaustive path coverage of a bounded depth. However, its practical use is often limited by path explosion because the number of paths of a program can be exponential in the number of branch conditions encountered during the execution. To mitigate the path explosion problem, we propose a new redundancy removal method called postconditioned symbolic execution. At each branching location, in addition to determine whether a particular branch is feasible as in traditional symbolic execution, our approach checks whether the branch is subsumed by previous explorations. This is enabled by summarizing previously explored paths by weakest precondition computations. Postconditioned symbolic execution can identify path suffixes shared by multiple runs and eliminate them during test generation when they are redundant. Pruning away such redundant paths can lead to a potentially \emph{exponential} reduction in the number of explored paths. We have implemented our method in the symbolic execution engine KLEE and conducted experiments on a large set programs from the GNU Coreutils suite. Our results confirm that redundancy due to common path suffix is both abundant and widespread in real- world applications.

Symbolic execution is a powerful technique for systematic testing of sequential and multithreaded programs. However, its application is limited by the high cost of covering all feasible intra-thread paths and inter-thread interleavings. We propose a new assertion guided pruning framework that identifies executions guaranteed not to lead to an error and removes them during symbolic execution. By summarizing the reasons why previously explored executions cannot reach an error and using the information to prune redundant executions in the future, we can soundly reduce the search space. We also use static concurrent program slicing and heuristic minimization of symbolic constraints to further reduce the computational overhead. We have implemented our method in the Cloud9 symbolic execution tool and evaluated it on a large set of multithreaded C/C++ programs. Our experiments show that the new method can reduce the overall computational cost significantly.

Role based access control (RBAC) is a widely used approach to access control with well-known advantages in managing authorization policies. This paper considers user-role reachability analysis of administrative role based access control (ARBAC), which defines administrative roles and specifies how members of each administrative role can change the RBAC policy. Most existing works on user-role reachability analysis assume the separate administration restriction in ARBAC policies. While this restriction greatly simplifies the user-role reachability analysis, it also limits the expressiveness and applicability of ARBAC. In this paper, we consider analysis of ARBAC without the separate administration restriction and present new techniques to reduce the number of ARBAC rules and users considered during analysis. We also present parallel algorithms that speed up the analysis on multi-core systems. The experimental results show that our techniques significantly reduce the analysis time, making it practical to analyze ARBAC without separate administration.

During software debugging, a significant amount of effort is required for programmers to identify the root cause of a manifested failure. In this article, we propose a cascade fault localization method to help speed up this labor-intensive process via a combination of weakest precondition computation and constraint solving. Our approach produces a cause tree, where each node is a potential cause of the failure and each edge represents a casual relationship between two causes. There are two main contributions of this article that differentiate our approach from existing methods. First, our method systematically computes all potential causes of a failure and augments each cause with a proper context for ease of comprehension by the user. Second, our method organizes the potential causes in a tree structure to enable on-the-fly pruning based on domain knowledge and feedback from the user. We have implemented our new method in a software tool called CaFL, which builds upon the LLVM compiler and KLEE symbolic virtual machine. We have conducted experiments on a large set of public benchmarks, including real applications from GNU Coreutils and Busybox. Our results show that in most cases the user has to examine only a small fraction of the execution trace before identifying the root cause of the failure.

A software birthmark is a unique characteristic of a program. Thus, comparing the birthmarks between the plaintiff and defendant programs provides an effective approach for software plagiarism detection. However, software birthmark generation faces two main challenges: the absence of source code and various code obfuscation techniques that attempt to hide the characteristics of a program. In this paper, we propose a new type of software birthmark called DYnamic Key Instruction Sequence (DYKIS) that can be extracted from an executable without the need for source code. The plagiarism detection algorithm based on our new birthmarks is resilient to both weak obfuscation techniques such as compiler optimizations and strong obfuscation techniques implemented in tools such as SandMark, Allatori and Upx. We have developed a tool called DYKIS-PD (DYKIS Plagiarism Detection tool) and conducted extensive experiments on large number of binary programs. The tool, the benchmarks and the experimental results are all publicly available.

The availability of inexpensive multicore hardware presents a turning point in software development. In order to benefit from the continued exponential throughput advances in new processors, the software applications must be multithreaded programs. As multithreaded programs become increasingly popular, plagiarism of multithreaded programs starts to plague the software industry. Although there has been tremendous progress on software plagiarism detection technology, existing dynamic approaches remain optimized for sequential programs and cannot be applied to multithreaded programs without significant redesign. This paper fills the gap by presenting two dynamic birthmark based approaches. The first approach extracts key instructions while the second approach extracts system calls. Both approaches consider the effect of thread scheduling on computing software birthmarks. We have implemented a prototype based on the Pin instrumentation framework. Our empirical study shows that the proposed approaches can effectively detect plagiarism of multithread programs and exhibit strong resilience to various semantic-preserving code obfuscations.

The consistency of pair-wise comparison matrix is a serious challenge for the multiple-criteria decision-making problem. However, existing methods are either too complicated to be applied in the revising process of the inconsistent comparison matrix or are difficult to preserve most of the original comparison information due to the use of a new pairwise comparison matrix. In this paper, a discrete region-based approach is proposed to improve the consistency of the pair-wise comparison matrix. When the decision makers feel confused or uncertain, they could express their evaluation as a discrete region containing multiple judgments, instead of a single result. A new data structure, named as set-matrix, is designed to store the combinations of those multiple judgments. An iterative searching algorithm is designed to find the pair-wise comparison matrix with approximate optimal consistency from the set-matrix. The experiments show that: 1) the consistency is significantly improved when the experts apply the discrete region evaluation instead of the single evaluation; and 2) the users can find the matrix with approximate optimal consistency quickly exploiting the iterative searching algorithm.

In this paper we present the OpenMP Analysis Toolkit (OAT), which uses Satisfiability Modulo Theories (SMT) solver based symbolic analysis to detect data races and deadlocks in OpenMP codes. Our approach approximately simulates real executions of an OpenMP program through schedule permutation. We conducted experiments on real-world OpenMP benchmarks and student homework assignments by comparing our OAT tool with two commercial dynamic analysis tools: Intel Thread Checker and Sun Thread Analyzer, and one commercial static analysis tool: Viva64 PVS Studio. The experiments show that our symbolic analysis approach is more accurate than static analysis and more efficient and scalable than dynamic analysis tools with less false positives and negatives.

The Multicore Communications API (MCAPI) is a new message-passing API that was released by the Multicore Association. MCAPI provides an interface designed for closely distributed embedded systems with multiple cores on a chip and/or chips on a board. Similar to parallel programs in other domains, debugging MCAPI programs is a challenging task due to their nondeterministic behavior. In this article we present a tool that is capable of deterministically replaying MCAPI program executions, which provides valuable insight for MCAPI developers in case of failure.

Ability to record and replay an execution can significantly help programmers debug their programs, especially parallel programs. De-terministically replaying a multiprocessor's execution under a relaxed memory model has remained a challenging problem. This is an important problem as most modern processors only support a relaxed memory model to enable many performance critical optimizations. The most common consistency model implemented in processors is the Total Store Order (TSO). We present an efficient and low-complexity processor based solution for recording and replaying under the Total Store Order (TSO) memory model. Processor provides support for logging data fetched on cache misses. Using this information each thread can be de-terministically replayed. A TSO-compliant casual order between the shared-memory accesses executed in different threads is then inferred using an offline algorithm based on Satisfiability Modulo Theory (SMT) solver. We also discuss methods to bound the search space during offline analysis and several optimizations to reduce the offline analysis time.

Ability to replay a program's execution on a multi-processor system can significantly help parallel programming. To replay a shared-memory multi-threaded program, existing solutions record its program input (I/O, DMA, etc.) and the shared-memory dependencies between threads. Prior processor based record-and-replay solutions are efficient, but they require non-trivial modifications to the coherency protocol and the memory sub-system for recording the shared-memory dependencies.

We present an efficient symbolic search algorithm for software model checking. Our algorithms perform word-level reasoning by using a combination of decision procedures in Boolean and integer and real domains, and use novel symbolic search strategies optimized specifically for sequential programs to improve scalability. Experiments on real-world C programs show that the new symbolic search algorithms can achieve several orders-of-magnitude improvements over existing methods based on bit-level (Boolean) reasoning.

This paper presents a lightweight interval analysis technique for determining the lower and upper bounds for program variables and its application in improving software model checking techniques. The experiments demonstrate that it is an effective approach to alleviate the state explosion problem in software model checking.

Class 2 opportunistic networks (oppnets) are a new paradigm for Collaborative Computing that aims at integrating communication, computation, sensing, actuation, storage, and other resources and services. Oppnets achieve global tasks and goals through the collaboration and coordination of their nodes (some of which join an oppnet dynamically). We describe the concept of oppnets, discuss related work, and present the standard API framework for oppnets name Oppnet Virtual Machine (OVM). We present the design and implementation details of a small-scale proof-of-concept system, named MicroOppnet, in terms of the OVM primitives. We describe both the design and implementation of MicroOppnet, which not only is a proof of concept but also constitutes our tool for experiments in collaborative computing with oppnets. We are currently working on extending MicroOppnet into a larger oppnet prototype and an oppnet testbed.

Scientific workflows have recently emerged as a new paradigm for representing and managing complex distributed scientific computations and data analysis, and have enabled and accelerated many scientific discoveries. Many scientific workflows are distributed and collaborative as they result from some collaborative research projects that involve a number of geographically distributed organizations. In these workflows, information flow control becomes a key security problem. In this paper, we propose to model a scientific workflow using a hierarchical state machine and present techniques for verifying and controlling information propagation in scientific workflow environments based on hierarchical state machines. To the best of our knowledge, this is the first effort for information flow analysis in the area of scientific workflows.

We present a novel paradigm of opportunistic networks or oppnets in the context of emergency preparedness and response (EPR). Oppnets constitute the category of ad hoc networks where diverse systems, not employed originally as nodes of an oppnet, join it dynamically in order to perform certain tasks they have been called to participate in. After describing the oppnets and their operation, we discuss the oppnet virtual machine (OVM) - a standard implementation framework for oppnet applications. Oppnets can significantly improve effectiveness and efficiency of EPR one of the six mission areas within the national strategy for homeland security. They can also improve other diverse applications, including agriculture, environment, healthcare, manufacturing, surveillance, and transportation. Oppnets should create new application niches as yet hard to imagine. To the best of our knowledge we have been the first to work on oppnets.

Existing BDD-based symbolic algorithms designed for hardware designs do not perform well on software programs. We propose novel techniques based on unique characteristics of software programs. Our algorithm divides an image computation step into a disjunctive set of easier ones that can be performed in isolation. We use hypergraph partitioning to minimize the number of live variables in each disjunctive component, and variable scopes to simplify transition relations and reachable state subsets. Our experiments on nontrivial C programs show that BDD-based symbolic algorithms can directly handle software models with a much larger number of state variables than for hardware designs.

We present a new approach to ensure the secure execution of itinerary-driven mobile agents, in which the specification of the navigational behavior of an agent is separated from the specification of its computational behavior. We empower each host with an access control policy so that the host will deny the access from an agent whose itinerary does not conform to the host's access control policy. A host uses model checking algorithms to check if the itinerary of the agent conforms to its access control policy written in mu-calculus, and if so, grant access permission. In order to address the state explosion problem for model checking itineraries, we propose an approach called model generation code. In this approach, instead of verifying the itinerary itself, a host actually checks the conservative models of a mobile agent. If a conservative model does not satisfy the host's access control policy, the mobile agent will provide refined models for further verification. Our preliminary results show that this is a practical and promising approach to ensure the secure execution of mobile agents

Finite state models generated from software programs have unique characteristics that are not exploited by existing model checking algorithms. In this paper, we propose a novel disjunctive image computation algorithm and other simplifications based on these characteristics. Our algorithm divides an image computation into a disjunctive set of easier ones that can be performed in isolation. Hypergraph partitioning is used to minimize the number of live variables in each disjunctive component. We use the live variables to simplify transition relations and reachable state subsets. Our experiments on a set of real-world C programs show that the new algorithm achieves orders-of-magnitude performance improvement over the best known conjunctive image computation algorithm

We present an efficient symbolic search algorithm for software model checking. The algorithm combines multiple symbolic representations to efficiently represent the transition relation and reachable states and uses a combination of decision procedures for Boolean and integer representations. Our main contributions include: (1) mixed symbolic representations to model C programs with rich data types and complex expressions; and (2) new symbolic search strategies and optimization techniques specific to sequential programs that can significantly improve the scalability of model checking algorithms. Our controlled experiments on real-world software programs show that the new symbolic search algorithm can achieve several orders-of-magnitude improvements over existing methods. The proposed techniques are extremely competitive in handling sequential models of non-trivial sizes, and also compare favorably to popular Boolean-level model checking algorithms based on BDDs and SAT

With the success of formal verification techniques like equivalence checking and model checking for hardware designs, there has been growing interest in applying such techniques for formal analysis and automatic verification of software programs. This paper provides a brief tutorial on model checking of C programs. The essential approach is to model the semantics of C programs in the form of finite state systems by using suitable abstractions. The use of abstractions is key, both for modeling programs as finite state systems and for reducing the model sizes in order to manage verification complexity. We provide illustrative details of a verification platform called F-Soft, which provides a range of abstractions for modeling software, and uses customized SAT-based and BDD-based model checking techniques targeted for software.

Bounded Model Checking (BMC) based on Boolean Satisfiability (SAT) procedures has recently gained popularity as an alternative to BDD-based model checking techniques for finding bugs in large designs. In this paper, we explore the use of learning from BDDs, where learned clauses generated by BDD-based analysis are added to the SAT solver, to supplement its other learning mechanisms. We propose several heuristics for guiding this process, aimed at increasing the usefulness of the learned clauses, while reducing the overheads. We demonstrate the effectiveness of our approach on several industrial designs, where BMC performance is improved and the design can be searched up to a greater depth by use of BDD-based learning.

Resolution-based proof analysis techniques have been proposed recently to identify a sufficient set of reasons for unsatisfiability derived by a CNF-based SAT solver. We have adapted these techniques to work with a hybrid SAT solver. We use the proof analysis technique with SAT-based BMC, in order to, generate useful abstract models. Our abstraction procedure is used iteratively in a top-down framework, starting from the concrete design, where we apply BMC on increasingly more abstract models. We apply various SAT-based and BDD-based verification methods on these abstract models, in order to obtain proofs of correctness, or to perform deeper searches for counterexamples. We demonstrate the effectiveness of our prototype implementation on several large industry designs.

In this paper, we present a new technique for the efficient dynamic detection and removal of inactive clauses, i.e. clauses that do not affect the solutions of interest of a Boolean Satisfiability (SAT) problem. The algorithm is based on the extraction of gate connectivity information during generation of the Boolean formula from the circuit, and its use in the inner loop of a branch-and-bound SAT algorithm. The motivation for this optimization is to exploit the circuit structure information, which can be used to find unobservable gates at circuit outputs under dynamic conditions. It has the potential to speed up all applications of SAT in which the SAT formula is derived from a logic circuit. In particular, we find that it has considerable impact on an image computation algorithm based on SAT. We present practical results for benchmark circuits which show that the use of this optimization consistently improves the performance for reachability analysis, in some cases enabling the prototype tool to reach more states than otherwise possible.

Methods based on Boolean satisfiability (SAT) typically use a conjunctive normal form (CNF) representation of the Boolean formula, and exploit the structure of the given problem through use of various decision heuristics and implication methods. We propose a new decision heuristic based on separator-set induced partitioning of the underlying CNF graph. It targets those variables whose choice generates clause partitions with disjoint variable supports. This can potentially improve performance of SAT applications by decomposing the problem dynamically within the search. In the context of a recently proposed image computation method combining SAT and BDDs, this results in simpler BDD subproblems. We provide algorithms for CNF partitioning - one based on a clause-variable dependency matrix, and another based on standard hypergraph partitioning techniques, and also for the use of partitioning information in decision heuristics for SAT. The effectiveness of the proposed partition-based heuristic is shown with practical results for reachability analysis of benchmark sequential circuits.