Abstract Program options provide flexible software functionality control but complicate fuzz testing, as triggering many behaviors require specific option combinations. Although existing option-aware fuzzing approaches attempt to mutate options as inputs or leverage AI technologies to extract option relationships from documentation, these methods have limitations. Documentation is often incomplete, and some option dependencies are embedded deeply within program logic via data or control flows, making these methods challenging to detect all possible dependencies. This paper introduces OSmartPro , an advanced option-fuzzing approach that directly extracts options and infers option dependencies from source code. Given LLM’s capabilities to interpret program semantics, OSmartPro employs LLM-assisted static analysis to handle diverse option-parsing structures and extract comprehensive options. Through control and data dependency analysis, it constructs option impact graph , which it uses to guide fuzzing strategies. The tool successfully extracted complete options from all 59 programs in our test set, uncovering undocumented options in over 66% of them. Additionally, OSmartPro inferred 14,701 option combinations, identified 45.03% more execution paths compared to AFL++, and uncovered 54 zero-day vulnerabilities, of which 18 awarded CVE IDs. Lastly, in a benchmark comparison against four option-aware fuzzers, OSmartPro achieved higher line coverage in 66.7% (20 out of 30) of the programs.

Learning with softmax cross-entropy on one-hot labels often leads to overconfidence on the correct class. While label smoothing regulates this overconfidence by redistributing some confidence from the correct class to other incorrect classes, it compromises the representation in the logits about the similarity between samples of different classes and may hurt calibration if higher confidence is required for high accuracy. To overcome these limitations, we propose a Virtual Smoothing (VS) label that redistributes certain confidence from the correct class to additional VS classes to regularize overconfidence. In VS labels, the VS class nodes act as adversaries to the original class nodes, enforcing regularization by clustering samples across all classes. The zero confidence assigned to each incorrect class also allows the incorrect logits to be different from each other without erasing information about sample similarities. The prediction probability can still approach 1 when applying softmax to the logits of the original real classes, which avoids harming but consistently improves calibration. Experiments show that VS labels consistently improve accuracy and calibration while providing better logits for improved knowledge distillation. Additionally, VS labels exhibit effectiveness in improving adversarial training, robust distillation, and out-of-distribution detection.

Network protocol fuzzing faces significant challenges in exploring cross-state vulnerabilities due to the sparse reward problem in traditional coverage-guided approaches. Existing tools struggle with extremely low success rates that lead to uniform sampling and ineffective state space exploration. This paper presents SCSPFUZZ, a novel learning-based protocol fuzzing framework that employs Thompson Sampling with enhanced reward criteria and a conscious cross-state mutation engine to overcome these fundamental limitations. SCSPFUZZ employs a clustering mechanism based on syntactic similarity and protocolspecific state coverage to maintain a diverse seed pool, which reduces redundant executions and improves exploration. To tackle the sparse-reward problem, a seed-adaptive selection algorithm dynamically refines reward criteria for more effective guidance. Furthermore, a novel cross-state mutation strategy integrates fast seed crossover with an enhanced byte inference mechanism to boost deep state exploration. Together, the seed clustering mechanism, seed-adaptive selection algorithm, and cross-state mutation strategies enable effective state-aware fuzzing for network protocols. Evaluations on 11 real-world implementations from ProFuzzBench show an average 10.4% increase in code coverage and 14% more unique crashes compared to AFLNet, demonstrating its effectiveness.

A significant portion of Android applications available in app markets are processed using packing techniques. While these protection methods enhance software security, they also increase the difficulty of detecting malicious behavior, posing challenges for static malware analysis. In this work, we first construct a comprehensive Android dataset named PkDroid, which consists of $\mathbf{1 3, 1 4 8}$ samples with diverse packing states including 6,111 packed applications. We analyze the impact of packed software on malware detection, emphasizing that the imbalanced distribution of packed applications weakens the effectiveness of malware detection. To solve this problem, we propose a novel deep learningbased static malware detection approach that leverages grayscale images generated from both original and unpacked DEX files. We transform DEX bytecode into grayscale images and integrate dilated convolutions with a hard sample sampler to boost robustness and accuracy under packing interference. Extensive experiments on the constructed dataset show that our method achieves a detection accuracy of 95.3% without relying on packing features, representing a 3.15% improvement over existing methods, and demonstrates improved resistance to packing techniques as well as enhanced detection of Android malware. This study not only introduces a valuable dataset for research on packed software in malware detection but also proposes an effective packinginsensitive method for Android malware detection.

Recently, dynamic concurrency bug predictions have kept making notable progress in improving concurrency coverage while ensuring soundness. Most of them rely solely on dynamic information in traces and overlook the static semantics of the program when predicting bugs. To ensure soundness, they assume that any (memory) read can fully affect subsequent program execution via control-flow and data-flow. However, the assumption over-approximates constraints among (memory) writes and reads and hence limits reordering space over thread interleaving, ultimately leading to false negatives. From program semantics, only a subset of reads actually affect their subsequent executions. Therefore, by refining dependencies between reads and subsequent executions based on static program semantics, one can refine the assumption and eliminate unnecessary constraints. This can bring a chance to explore more thread interleaving space and uncover more concurrency bugs. However, refining dependencies can compromise soundness and bring heavy overhead. To tackle these challenges, this paper introduces the concept of Necessary Consistent Read Event (NRE) and a hybrid analysis algorithm. NRE refines dependencies between reads and their subsequent events and is used to identify necessary constraints where a read probably affects the execution of its subsequent events. Next, we design an efficient and accurate hybrid analysis algorithm to calculate NREs for each event in the trace. The hybrid analysis algorithm maps events to program SSA instructions and simulates executions based on the original trace. NRE and the algorithm can enhance the capabilities of existing concurrency bug prediction methods at a low cost, regardless of the type of concurrency bug they target. In this paper, we focused on data race and developed NRE and the algorithm as a prototype tool RECONP. We conducted a set of comparative experiments on MySQL with M2 and Seqcheck. The results show that RECONP can detect 46.9% and 22.4% more data races than M2 and Seqcheck, respectively. And the hybrid algorithm only accounts for 34% of the total time cost.

Program options are ubiquitous and serve as a fundamental mechanism for configuring and customizing software behaviors. Given their widespread use, testing program options becomes essential to ensure that the software behaves as expected across various configurations. Existing option-aware fuzzers either mutate options as if they were standard program inputs or employ NLP techniques to deduce relationships among options from the documentation. However, there has not been a whitebox approach that generates option combinations by capturing the inherent execution logic of the program.

The application of machine learning methods to solve combinatorial problems has garnered considerable research interest. In this paper, we propose MAgg (**M**etamorphic **Agg**regation), a method to augment machine learning models for combinatorial problems at inference time using metamorphic relations. MAgg models metamorphic relations using directed graphs, which are then fed to a Graph Neural Network (GNN) model to improve the aggregation of predictions across transformed input instances. By incorporating metamorphic relations, MAgg essentially extends standard Test-Time Augmentation (TTA), eliminating the necessity of label-preserving transformations and expanding its applicability to a broader range of supervised learning tasks for combinatorial problems. We evaluate the proposed MAgg method on three mainstream machine learning tasks for combinatorial problems, namely Boolean Satisfiability Prediction (SAT), Decision Traveling Salesman Problem Satisfiability Prediction (Decision TSP), and Graph Edit Distance Estimation (GED). The evaluation result shows significant improvements over base models in all three tasks, corroborating the effectiveness and versatility of the proposed method.

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

Concurrent programs are normally composed of multiple concurrent threads sharing memory space. These threads are often interleaved, which may lead to some non-determinism in execution results, even for the same program input. This poses huge challenges to the testing of concurrent programs, especially on the test result verification—that is, the prevalent existence of the oracle problem. In this article, we investigate the application of metamorphic testing (MT), a mainstream technique to address the oracle problem, into the testing of concurrent programs. Based on the unique features of interleaved executions in concurrent programming, we propose an extended notion of metamorphic relations, the core part of MT, which are particularly designed for the testing of concurrent programs. A comprehensive testing approach, namely ConMT , is thus developed and a tool is built to automate its implementation on concurrent programs written in Java. Empirical studies have been conducted to evaluate the performance of ConMT, and the experimental results show that in addition to addressing the oracle problem, ConMT outperforms the baseline traditional testing techniques with respect to a higher degree of automation, better bug detection capability, and shorter testing time. It is clear that ConMT can significantly improve the cost-effectiveness for the testing of concurrent programs and thus advances the state of the art in the field. The study also brings novelty into MT, hence promoting the fundamental research of software testing.

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.

Data races seriously threaten the correctness of concurrent programs. Earlier works can report false positives. Recently, trace-based predictive analysis has achieved sound results by inferring feasible traces based on sound partial orders or constraint solvers. However, they hold the same assumption: any read event may affect the control-flow of a predicted trace. Thus, being control-flow sensitive, they have to enforce any read event (in an inferred trace) to either read the same value or a value from the same event as that in the original trace, albeit some slightly relax this. This (even with relaxation) severely limits their predictive ability and many true data races can be missed. We introduce the concept of Fix-Point Event and propose a new partial order model. This allows us to not only predict races with witness traces (like existing works with no control-flow changes) but also soundly infer existences of witness traces with potential control-flow changes. Thus, we can achieve a higher concurrency coverage and detect more data races soundly. We have implemented above as a tool ToccRACE and conducted a set of experiments on a benchmark of seven real-world programs and a large-scale software MySQL, where MySQL produced 427 traces with a total size of 3.4TB. Compared with the state-of-the-art sound data race detector SeqCheck,ToccRACE is significantly more effective by detecting 84.4%/200% more unique/dynamic races on the benchmark programs and 52.22%/49.8% more unique/dynamic races on MySQL, incurring reasonable time and memory costs (about 1.1x×43.5x on the benchmark programs and 10x/1.03x on MySQL). Furthermore, ToccRACE is sound and is comnlcte on two threads.

One of the aims of the development and spread of autonomous driving technology is to reduce traffic accidents caused by human factors. But recently reported data on fatal accidents involving autonomous driving system (ADS) shows that this important goal has not been achieved. So there is an emerge requirement on more comprehensive and targeted testing especially on safe driving. In this paper, we propose an approach to automatically building critical testing scenarios from real-world accident data. Firstly, we propose a new model called M-CPS (Multi-channel Panoptic Segmentation) to extract the effective information from the accident record (such as images or videos), and separate the independent individuals of different traffic participants for further scene recovery. Compared with the traditional panoramic segmentation models, M-CPS model is able to effectively handle segmentation challenges due to the shooting angle, image quality, pixel overlap and other problems existing in the accident record. Next, the extracted core information is then connected with the virtual testing platform to generate the original scene set. Besides, we also design a mutation testing solution on the basis of the original scene set, thus greatly enriching the scene library for testing. In our experiments, the M-CPS model reaches a result of 66.1% PQ on CityScapes test set, shows that our model has only slight fluctuations on performance compared with the best benchmark model on pure panoptic segmentation task. It also reaches a result of 84.5% IoU for semantic segmentation branch and 40.3% mAP for instance segmentation branch on SHIFT dataset. Then we use UCF-Crime, CADP and US-Accidents datasets to generate the original and mutated scene set. Those generated scene sets are connected to Apollo and Carla simulation platforms to test ADS prototypes. We find three types of scenarios that can lead to accidents of ADS prototypes, which indicates that the existing ADS prototype has defects. Our solution provides a new possible direction for the recovery of key scenarios in ADS testing, and can improve the efficiency in related fields.

Parallelization is a promising way to improve the performance of Python programs. Unfortunately, developers may miss parallelization possibilities, because they usually do not concentrate on parallelization. Many approaches have been proposed to parallelize Python programs automatically, however, they are either domain-specific or require manual annotation. Thus they cannot solve the problem well in general. In this paper, we propose PyPar, an effective tool aiming at discovering parallelization possibilities in real-world Python programs. PyPar doesn’t need manual annotation and is universally applicable. It first drives a data-dependence analysis to determine whether two pieces of code can run concurrently. The key is the use of a graph-theoretic approach. Next, it adopts a dynamic selection strategy to eliminate inefficient parallelisms. Finally, PyPar produces a parallelism report as well as a referential parallelized program, which is built by PyPar using one of the three parallelization methods (thread-based, processbased, and Ray-based). We have implemented a prototype of PyPar and evaluated it on six well-designed widely-used real-world Python packages: Scikit-Image, SciPy, librosa, trimesh, Scikit-learn and seaborn. In total, 1,240 functions are tested, and PyPar found 127 parallelizable functions among them. Based on manual filtering, only 7 of them are false positives (i.e., a 94.5% precision). The remaining 120 are parallelizable (almost 10% among all functions under test), and most of them can be efficiently sped up by gaining an acceleration of up to 90% , with an average of 44%. The acceleration in practice is close to theoretical estimation. The results show that even well-designed practical Python programs can be further parallelized for speeding up, and PyPar can bring effective and efficient parallelization on real-world Python programs.

Reference counting (refcounting) is widely used in Linux kernel. However, it requires manual operations on the related APIs. In practice, missing or improperly invoking these APIs has introduced too many bugs, known as refcounting bugs. To evaluate the severity of these bugs in history and in future, this paper presents a comprehensive study on them.

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.

Existing programming practices for building Android apps mainly follow the “one-size-fits-all” strategy to include lots of functions and adapt to most types of devices. However, this strategy can result in software bloat and many serious issues, such as slow download speed, and large attack surfaces. Existing solutions cannot effectively debloat an app as they either lack flexibility or require human efforts. This work proposes a novel feature-oriented debloating approach and builds a prototype, namedXDebloat, to automate this process in a flexible manner. First, We propose three feature location approaches to mine features in an app. XDebloat supports feature location approaches at a fine granularity. It also makes the feature location results editable. Second, XDebloat considers several Android-oriented issues (i.e., callbacks) to perform a more precise analysis. Third, XDebloat supports two major debloating strategies: pruning-based debloating and module-based debloating. We evaluate XDebloat with 200 open-source and 1,000 commercial apps. The results show that XDebloat can successfully remove components from apps or transform apps into on-demand modules within 10 minutes. For thepruning-baseddebloating strategy, on average, XDebloat can remove 32.1% code from an app. For themodule-baseddebloating strategy, XDebloat can help developers build instant apps or app bundles automatically.

Security of smart contracts has attracted increasing attention in recent years. Many researchers have devoted themselves to devising testing tools for vulnerability detection. Each published tool has demonstrated its effectiveness through a series of evaluations on their own experimental scenarios. However, the inconsistency of evaluation settings such as different data sets or performance metrics, may result in biased conclusion.

A growing number of bugs have been reported by vulnerability discovery solutions. Among them, some bugs are hard to diagnose or reproduce, including data race bugs caused by thread interleavings. Few solutions are able to well address this issue, due to the huge space of interleavings to explore. What’s worse, in security analysis scenarios, analysts usually have no access to the source code of target programs and have troubles in comprehending them.

Concurrency bugs are extremely difficult to detect. Recently, several dynamic techniques achieve sound analysis. M2 is even complete for two threads. It is designed to decide whether two events can occur consecutively. However, real-world concurrency bugs can involve more events and threads. Some can occur when the order of two or more events can be exchanged even if they occur not consecutively. We propose a new technique SeqCheck to soundly decide whether a sequence of events can occur in a specified order. The ordered sequence represents a potential concurrency bug. And several known forms of concurrency bugs can be easily encoded into event sequences where each represents a way that the bug can occur. To achieve it, SeqCheck explicitly analyzes branch events and includes a set of efficient algorithms. We show that SeqCheck is sound; and it is also complete on traces of two threads.

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.

Multithreaded programs can have deadlocks, even after deployment, so users may want to run deadlock tools on deployed programs. However, current deadlock predictors such as MagicLock and UnDead have large overheads that make them impractical for end-user deployment and confine their use to development time. Such overhead stems from running an exponential-time algorithm on a large execution trace. In this paper, we present the first low-overhead deadlock predictor, called AirLock, that is fit for both in-house testing and deployed programs. AirLock maintains a small predictive lock reachability graph, searches the graph for cycles, and runs an exponential-time algorithm only for each cycle. This approach lets AirLock find the same deadlocks as MagicLock and UnDead but with much less overhead because the number of cycles is small in practice. Our experiments with real-world benchmarks show that the average time overhead of AirLock is 3.5%, which is three orders of magnitude less than that of MagicLock and UnDead. AirLock's low overhead makes it suitable for use with fuzz testers like AFL and on-the-fly after deployment.

Smartphones are frequently involved in accessing private user data. Although many studies have been done to prevent malicious apps from leaking private user data, only a few recent works examine how to remove the sensitive information from the data collected by smartphone hardware resources (e.g., camera). Unfortunately, none of them investigates whether a malicious app can obtain such sensitive information when (or right before/after) a legitimate app collects such data (e.g., taking photos). To fill in the gap, in this paper, we model such attacks as the Resource Race Attack (RRAttack) based on races between two apps during their requests to exclusive resources to access sensitive information. RRAttacks have three categories according to when a race on requesting resources occurs: Pre-Use, In-Use, and Post-Use attacks. We further conduct the first systematic study on the feasibility of launching the RRAttacks on two heavily used exclusive Android resources: camera and touchscreen. In details, we perform Proof-of-Concept (PoC) attacks to reveal that, (a) camera is highly vulnerable to both In-Use and Post-Use attacks; and (b) touchscreen is vulnerable to Pre-Use attacks. Particularly, we demonstrate successful RRAttacks on them to steal private information, to cause financial loss, and to steal user passwords from Android 6 to the latest Android Q. Moreover, our analyses on 1,000 apps indicate that most of them are vulnerable to one to three RRAttacks. Finally, we propose a set of defense strategies against RRAttacks for user apps, system apps, and Android system itself.

In the above named work (ibid., vol. 45, no. 10, pp. 984???1001, Oct. 2019), the corresponding author should have been listed as Bin Liang. The footnote information is corrected here.

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.

Memory corruption vulnerabilities can occur in multithreaded executions, known as concurrency vulnerabilities in this paper. Due to non-deterministic multithreaded executions, they are extremely difficult to detect. Recently, researchers tried to apply data race detectors to detect concurrency vulnerabilities. Unfortunately, these detectors are ineffective on detecting concurrency vulnerabilities. For example, most (90%) of data races are benign. However, concurrency vulnerabilities are harmful and can usually be exploited to launch attacks. Techniques based on maximal causal model rely on constraints solvers to predict scheduling; they can miss concurrency vulnerabilities in practice. Our insight is, a concurrency vulnerability is more related to the orders of events that can be reversed in different executions, no matter whether the corresponding accesses can form data races. We then define exchangeable events to identify pairs of events such that their execution orders can be probably reversed in different executions. We further propose algorithms to detect three major kinds of concurrency vulnerabilities. To overcome potential imprecision of exchangeable events, we also adopt a validation to isolate real vulnerabilities. We implemented our algorithms as a tool ConVul and applied it on 10 known concurrency vulnerabilities and the MySQL database server. Compared with three widely-used race detectors and one detector based on maximal causal model, ConVul was significantly more effective by detecting 9 of 10 known vulnerabilities and 6 zero-day vulnerabilities on MySQL (four have been confirmed). However, other detectors only detected at most 3 out of the 16 known and zero-day vulnerabilities.

Code mining has been proven to be a promising approach to inferring implicit programming rules for finding software bugs. However, existing methods may report large numbers of false positives and false negatives. In this paper, we propose a novel approach called EAntMiner to improve the effectiveness of code mining. EAntMiner elaborately reduces noises from statements irrelevant to interesting rules and different implementation forms of the same logic. During preprocessing, we employ program slicing to decompose the original source repository into independent sub-repositories. In each sub-repository, statements irrelevant to critical operations (automatically extracted from source code) are excluded and various semantics-equivalent implementations are normalized into a canonical form as far as possible. Moreover, to tackle the challenge that some bugs are difficult to be detected by mining frequent patterns as rules, we further developed a kNN-based method to identify them. We have implemented EAntMiner and evaluated it on four large-scale C systems. EAntMiner successfully detected 105 previously unknown bugs that have been confirmed by corresponding development communities. A set of comparative evaluations also demonstrate that EAntMiner can effectively improve the precision of code mining.

Inferring programming rules from source code based on data mining techniques has been proven to be effective to detect software bugs. Existing studies focus on discovering positive rules in the form of A ⇒ B, indicating that when operation A appears, operation B should also be here. Unfortunately, the negative rules (A ⇒ ¬ B), indicating the mutual suppression or conflict relationships among program elements, have not gotten the attention they deserve. In fact, violating such negative rules can also result in serious bugs.

Heap overflow is one of the most widely exploited vulnerabilities, with a large number of heap overflow instances reported every year. It is important to decide whether a crash caused by heap overflow can be turned into an exploit. Efficient and effective assessment of exploitability of crashes facilitates to identify severe vulnerabilities and thus prioritize resources. In this paper, we propose the first metrics to assess heap overflow crashes based on both the attack aspect and the feasibility aspect. We further present HCSIFTER, a novel solution to automatically assess the exploitability of heap overflow instances under our metrics. Given a heap-based crash, HCSIFTER accurately detects heap overflows through dynamic execution without any source code or debugging information. Then it uses several novel methods to extract program execution information needed to quantify the severity of the heap overflow using our metrics. We have implemented a prototype HCSIFTER and applied it to assess nine programs with heap overflow vulnerabilities. HCSIFTER successfully reports that five heap overflow vulnerabilities are highly exploitable and two overflow vulnerabilities are unlikely exploitable. It also gave quantitatively assessments for other two programs. On average, it only takes about two minutes to assess one heap overflow crash. The evaluation result demonstrates both effectiveness and efficiency of HC Sifter.

Deadlocks are critical problems afflicting parallel applications, causing software to hang with no further progress. Existing detection tools suffer not only from significant recording performance overhead, but also from excessive memory and/or storage overhead. In addition, they may generate numerous false alarms. Subsequently, after problems have been reported, tremendous manual effort is required to confirm and fix these deadlocks. This paper designs a novel system, UnDead, that helps defeat deadlocks in production software. Different from existing detection tools, UnDead imposes negligible runtime performance overhead (less than 3 % on average) and small memory overhead (around 6%), without any storage consumption. After detection, UnDead automatically strengthens erroneous programs to prevent future occurrences of both existing and potential deadlocks, which is similar to the existing work-Dimmunix. However, UnDead exceeds Dimmunix with several orders of magnitude lower performance overhead, while eliminating numerous false positives. Extremely low runtime and memory overhead, convenience, and automatic prevention make UnDead an always-on detection tool, and a "band-aid" prevention system for production software.

It is difficult to fix atomicity violations correctly. Existing gate lock algorithm (GLA) simply inserts gate locks to serialize exe-cutions, which may introduce performance bugs and deadlocks. Synthesized context-aware gate locks (by Grail) require complex source code synthesis. We propose Fixer to adaptively fix ato-micity violations. It firstly analyses the lock acquisitions of an atomicity violation. Then it either adjusts the existing lock scope or inserts a gate lock. The former addresses cases where some locks are used but fail to provide atomic accesses. For the latter, it infers the visibility (being global or a field of a class/struct) of the gate lock such that the lock only protects related accesses. For both cases, Fixer further eliminates new lock orders to avoid introducing deadlocks. Of course, Fixer can produce both kinds of fixes on atomicity violations with locks. The experi-mental results on 15 previously used atomicity violations show that: Fixer correctly fixed all 15 atomicity violations without introducing deadlocks. However, GLA and Grail both intro-duced 5 deadlocks. HFix (that only targets on fixing certain types of atomicity violations) only fixed 2 atomicity violations and introduced 4 deadlocks. Fixer also provides an alternative way to insert gate locks (by inserting gate locks with proper visibility) considering fix acceptance.

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.

Manual deadlock fixing is error-prone and time-consuming. Existing generic approach (GA) simply inserts gate locks to fix deadlocks by serializing executions, which could introduce various new deadlocks and incur high runtime overhead. We propose a novel approach DFixer to fix deadlocks without introducing any new deadlocks by design. DFixer only selects one thread of a deadlock to pre-acquire a lock w together with another lock h, where before fixing, the deadlock occurs when the thread holds lock h and waits for lock w. As such, DFixer eliminates a hold-and-wait necessary condition, preventing the deadlock from occurring. The thread performing pre-acquisition is carefully selected such that no other synchronization exists in between the two original acquisitions. Otherwise, DFixer further introduces a context-aware conditional protected by above lock w to guarantee the correctness of DFixer. The evaluation is on 20 deadlocks, including 17 from widely-used real-world C/C++ programs. It shows that DFixer successfully fixed all deadlocks. Whereas GA introduced 9 new deadlocks; a latest work Grail failed to fix 8 deadlocks and introduced 3 new deadlocks on others. On average, DFixer incurred only 2.1% overhead, where GA and Grail incurred 15.8% and 11.5% overhead, respectively.

Detecting bugs with code mining has proven to be an effective approach. However, the existing methods suffer from reporting serious false positives and false negatives. In this paper, we developed an approach called AntMiner to improve the precision of code mining by carefully preprocessing the source code. Specifically, we employ the program slicing technique to decompose the original source repository into independent sub-repositories, taking critical operations (automatically extracted from source code) as slicing criteria. In this way, the statements irrelevant to a critical operation are excluded from the corresponding sub-repository. Besides, various semantics-equivalent representations are normalized into a canonical form. Eventually, the mining process can be performed on a refined code database, and false positives and false negatives can be significantly pruned. We have implemented AntMiner and applied it to detect bugs in the Linux kernel. It reported 52 violations that have been either confirmed as real bugs by the kernel development community or fixed in new kernel versions. Among them, 41 cannot be detected by a widely used representative analysis tool Coverity. Besides, the result of a comparative analysis shows that our approach can effectively improve the precision of code mining and detect subtle bugs that have previously been missed.

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.

Dynamic data race detection incurs heavy runtime overheads. Recently, many sampling techniques have been proposed to detect data races. However, some sampling techniques (e.g., Pacer) are based on traditional happens-before relation and incur a large basic overhead. Others utilize hardware to reduce their sampling overhead (e.g., DataCollider) and they, however, detect a race only when the race really occurs by delaying program executions. In this paper, we study the limitations of existing techniques and propose a new data race definition, named as Clock Races, for low overhead sampling purpose. The innovation of clock races is that the detection of them does not rely on concrete locks and also avoids heavy basic overhead from tracking happens-before relation. We further propose CRSampler (Clock Race Sampler) to detect clock races via hardware based sampling without directly delaying program executions, to further reduce runtime overhead. We evaluated CRSampler on Dacapo benchmarks. The results show that CRSampler incurred less than 5% overhead on average at 1% sampling rate. Whereas, Pacer and DataCollider incurred larger than 25% and 96% overhead, respectively. Besides, at the same sampling rate, CRSampler detected significantly more data races than that by Pacer and DataCollider.

Existing deadlock detectors are either not scalable or may report false positives when suggesting cycles as potential deadlocks. Additionally, they may not effectively trigger deadlocks and handle false positives. We propose a technique called ConLock+, which firstly analyzes each cycle and its corresponding execution to identify a set of scheduling constraints that are necessary conditions to trigger the corresponding deadlock. The ConLock+technique then performs a second run to enforce the set of constraints, which will trigger a deadlock if the cycle is a real one. Or if not, ConLock+reports a steering failure for that cycle and also identifies other similar cycles which would also produce steering failures. For each confirmed deadlock, ConLock+performs a static analysis to identify conflicting memory access that would also contribute to the occurrence of the deadlock. This analysis is helpful to enable developers to understand and fix deadlocks. ConLock+has been validated on a suite of real-world programs with 16 real deadlocks. The results show that across all 811 cycles, ConLock+confirmed all of the 16 deadlocks with a probability of ≥80 percent. For the remaining cycles, ConLock+reported steering failures and also identified that five deadlocks also involved conflicting memory accesses.

Happens-before relation is widely used to detect data races dynami-cally. However, it could easily hide many data races as it is inter-leaving sensitive. Existing techniques based on randomized sched-uling are ineffective on detecting these hidden races. In this paper, we propose DrFinder, an effective and precise dynamic technique to detect hidden races. Given an execution, DrFinder firstly analyz-es the lock acquisitions in it and collects a set of "may-trigger" relations. Each may-trigger relation consists of a method and a type of a Java object. It indicates that, during execution, the method may directly or indirectly acquire a lock of the type. In the subsequent executions of the same program, DrFinder actively schedules the execution according to the set of collected may-trigger relations. It aims to reverse the set of happens-before relation that may exist in the previous executions so as to expose those hidden races. To effectively detect hidden races in each execution, DrFinder also collects a new set of may-trigger relation during its scheduling, which is used in its next scheduling. Our experiment on a suite of real-world Java multithreaded programs shows that DrFinder is effective to detect 89 new data races in 10 runs. Many of these races could not be detected by existing techniques (i.e., FastTrack, ConTest, and PCT) even in 100 runs.

Many large-scale multithreaded programs incur deadlock bugs. Existing deadlock warning detection techniques only report warning scenarios, which may or may not be real deadlocks. Each warning should be further verified on whether it may manifest into a real deadlock. For this purpose, a number of active randomized testing schedulers have been developed to trigger them, and yet pervious experiments show that their deadlock confirmation probability can be low. This paper presents ASN, a novel barrier-based randomized scheduler that triggers real deadlocks with high probabilities. We exploit the insights that in a confirmation run, the threads involved in a real deadlock should properly acquire one or more sets of locks prior to deadlocking. ASN automatically identifies three interesting sets of such positions. It guides the threads participating in a given warning to stay at these position sets in turn. When all the threads are staying at the last position set, ASN checks whether any deadlock that matches with the given warning has been triggered. We have evaluated ASN on 15 deadlock bugs in a suite of real-world multithreaded programs. The results show that ASN either confirms more deadlocks from the benchmark suite or triggers the same deadlocks with significantly higher probabilities than existing schedulers.

Many composite workflow services utilize non-imperative XML technologies such as WSDL, XPath, XML schema, and XML messages. Regression testing should assure the services against regression faults that appear in both the workflows and these artifacts. In this paper, we propose a refinement-oriented level-exploration strategy and a multilevel coverage model that captures progressively the coverage of different types of artifacts by the test cases. We show that by using them, the test case prioritization techniques initialized on top of existing greedy-based test case prioritization strategy form a subsumption hierarchy such that a technique can produce more test suite permutations than a technique that subsumes it. Our experimental study of a model instance shows that a technique generally achieves a higher fault detection rate than a subsumed technique, which validates that the proposed hierarchy and model have the potential to improve the cost-effectiveness of test case prioritization techniques.

Many predictive deadlock detection techniques analyze multithreaded programs to suggest potential deadlocks (referred to as cycles or deadlock warnings). Nonetheless, many of such cycles are false positives. On checking these cycles, existing dynamic deadlock confirmation techniques may frequently encounter thrashing or result in a low confirmation probability. This paper presents a novel technique entitled ConLock to address these problems. ConLock firstly analyzes a given cycle and the execution trace that produces the cycle. It identifies a set of thread scheduling constraints based on a novel should-happen-before relation. ConLock then manipulates a confirmation run with the aim to not violate a reduced set of scheduling constraints and to trigger an occurrence of the deadlock if the cycle is a real deadlock. If the cycle is a false positive, ConLock reports scheduling violations. We have validated ConLock using a suite of real-world programs with 11 deadlocks. The result shows that among all 741 cycles reported by Magiclock, ConLock confirms all 11 deadlocks with a probability of 71%−100%. On the remaining 730 cycles, ConLock reports scheduling violations on each. We have systematically sampled 87 out of the 730 cycles and confirmed that all these cycles are false positives.

We present Magiclock, a novel potential deadlock detection technique by analyzing execution traces (containing no deadlock occurrence) of large-scale multithreaded programs. Magiclock iteratively eliminates removable lock dependencies before potential deadlock localization. It divides lock dependencies into thread specific partitions, consolidates equivalent lock dependencies, and searches over the set of lock dependency chains without the need to examine any duplicated permutations of the same lock dependency chains. We validate Magiclock through a suite of real-world, large-scale multithreaded programs. The experimental results show that Magiclock is significantly more scalable and efficient than existing dynamic detectors in analyzing and detecting potential deadlocks in execution traces of large-scale multithreaded programs.

Many web services represent their artifacts in the semi-structural format. Such artifacts may or may not be structurally complex. Many existing test case prioritization techniques however treat test cases of different complexity generically. In this paper, we exploit the insights on the structural similarity of XML-based artifacts between test cases, and propose a family of test case prioritization techniques that iteratively selects test case pairs without replacement. The validation experiment shows that these techniques can be more cost-effective than the studied existing techniques in exposing faults.

This paper presents the aim of TeamWork, our ongoing effort to develop a comprehensive dynamic deadlock confirmation tool for multithreaded programs. It also presents a refined object abstraction algorithm that refines the existing stack hash abstraction.

SUMMARY Many researchers employ various statistical methods to locate faults in faulty programs. Like other researchers, we sometimes have made mistakes in the quest of making statistical fault localization both practical and scientific. In this experience report, we reflect on our work conducted on this topic, organize our isolated experiences in the format of models and errors, and cast them in the context of statistics. Copyright © 2011 John Wiley & Sons, Ltd.

Many happened-before-based detectors for debugging multithreaded programs implement vector clocks to incrementally track the casual relations among synchronization events produced by concurrent threads and generate trace logs. They update the vector clocks via vector-based comparison and content assignment in every case. We observe that many such tracking comparison and assignment operations are removable in part or in whole, which if identified and used properly, have the potential to reduce the log traces thus produced. This paper presents our analysis to identify such removable tracking operations and shows how they could be used to reduce log traces. We implement our analysis result as a technique entitled LOFT. We evaluate LOFT on the well-studied PARSEC benchmarking suite and five large-scale real-world applications. The main experimental result shows that on average, LOFT identifies 63.9 percent of all synchronization operations incurred by the existing approach as removable and does not compromise the efficiency of the latter.

We present MagicFuzzer, a novel dynamic deadlock detection technique. Unlike existing techniques to locate potential deadlock cycles from an execution, it iteratively prunes lock dependencies that each has no incoming or outgoing edge. Combining with a novel thread-specific strategy, it dramatically shrinks the size of lock dependency set for cycle detection, improving the efficiency and scalability of such a detection significantly. In the real deadlock confirmation phase, it uses a new strategy to actively schedule threads of an execution against the whole set of potential deadlock cycles. We have implemented a prototype and evaluated it on large-scale C/C++ programs. The experimental results confirm that our technique is significantly more effective and efficient than existing techniques.

Many happens-before based techniques for multithreaded programs implement vector clocks to track incrementally the causal relations among the synchronization operations acting on threads and locks. In these detectors, every such operation results in a vector-based assignment to a vector clock, even though the assigned value is the same as the value of the vector clock right before the assignment. The cost of such vector-based operations however grows with the number of threads and the amount of such operations. It is unclear to what extent redundant assignments can be removed. Whether two consecutive assignments to the same vector clock of a thread result in the same content critically depends on the operations on the locks occurred in between these assignments. In this paper, we systematically explore the said insight and quantify a sufficient condition that can soundly remove such operations without affecting the precision of such tracking. We applied our approach on Fast Track to formulate LOFT. We evaluate LOFT using the PARSEC benchmarking suite. The result shows that, on average, LOFT removes 58.0% of all such operations incurred by Fast Track, and runs 16.2% faster than the latter in tracking the causal relations among these operations.