Bug fixing holds significant importance in software development and maintenance. Recent research has made substantial strides in exploring the potential of large language models (LLMs) for automatically resolving software bugs. However, a noticeable gap in existing approaches lies in the oversight of collaborative facets intrinsic to bug resolution, treating the process as a single-stage endeavor. Moreover, most approaches solely take the buggy code snippet as input for LLMs during the patch generation stage. To mitigate the aforementioned limitations, we introduce a novel stage-wise framework named PATCH. Specifically, we first augment the buggy code snippet with corresponding dependence context and intent information to better guide LLMs in generating the correct candidate patches. Additionally, by taking inspiration from bug management practices, we decompose the bug-fixing task into four distinct stages: bug reporting, bug diagnosis, patch generation, and patch verification. These stages are performed interactively by LLMs, aiming to simulate the collaborative behavior of programmers during the resolution of software bugs. By harnessing these collective contributions, PATCH effectively enhances the bug-fixing capability of LLMs. We implement PATCH by employing the powerful dialogue-based LLM ChatGPT. Our evaluation on the widely used bug-fixing benchmark BFP demonstrates that PATCH has achieved better performance than state-of-the-art LLMs.

Unit testing plays a pivotal role in the software development lifecycle, as it ensures code quality. However, writing high-quality unit tests remains a time-consuming task for developers in practice. More recently, the application of large language models (LLMs) in automated unit test generation has demonstrated promising results. Existing approaches primarily focus on interpreted programming languages (e.g., Java), while mature solutions tailored to compiled programming languages like C++ are yet to be explored. The intricate language features of C++, such as pointers, templates, and virtual functions, pose particular challenges for LLMs in generating both executable and high-coverage unit tests. To tackle the aforementioned problems, this article introduces CITYWALK , a novel LLM-based framework for C++ unit test generation. CITYWALK enhances LLMs by providing a comprehensive understanding of the dependency relationships within the project under test via program analysis. Furthermore, CITYWALK incorporates language-specific knowledge about C++ derived from project documentation and empirical observations, significantly improving the correctness of the LLM-generated unit tests. We implement CITYWALK by employing the widely popular LLM GPT-4o. The experimental results show that CITYWALK outperforms current state-of-the-art approaches on a collection of ten popular C++ projects. Our findings demonstrate the effectiveness of CITYWALK in generating high-quality C++ unit tests.

The last five years have seen a rise of model checking guided testing (MCGT) approaches for systematically testing distributed systems. MCGT approaches generate test cases for distributed systems by traversing their verified abstract state spaces, simultaneously solving the three key problems faced in testing distributed systems, i.e., test input generation, test oracle construction and execution space enumeration. However, existing MCGT approaches struggle with traversing the huge state space of distributed systems, which can contain billions of system states. This makes the process of finding bugs time-consuming and expensive, often taking several weeks.In this paper, we propose Mosso to speed up model checking guided testing for distributed systems. We observe that there exist lots of redundant test scenarios in the abstract state space of distributed systems. Considering the characteristics of these redundant test scenarios, we propose three strategies: action independence, node symmetry and scenario equivalence, to identify and prioritize unique test scenarios when traversing the state space. We have applied Mosso on three real-world distributed systems. By employing the three strategies, our approach has achieved an average speedup of 56Χ (up to 208Χ) compared to the state-of-art MCGT approach. Additionally, our approach has successfully uncovered 2 previously-unknown bugs.

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.

Graph database systems store graph data as nodes and relationships, and utilize graph query languages (e.g., Cypher) for efficiently querying graph data. Proving the equivalence of graph queries is an important foundation for optimizing graph query performance, ensuring graph query reliability, etc. Although researchers have proposed many SQL query equivalence provers for relational database systems, these provers cannot be directly applied to prove the equivalence of graph queries. The difficulty lies in the fact that graph query languages (e.g., Cypher) adopt significantly different data models (property graph model vs. relational model) and query patterns (graph pattern matching vs. tabular tuple calculus) from SQL. In this paper, we propose GraphQE, an automated prover to determine whether two Cypher queries are semantically equivalent. We design a U-semiring based Cypher algebraic representation to model the semantics of Cypher queries. Our Cypher algebraic representation is built on the algebraic structure of unbounded semirings, and can sufficiently express nodes and relationships in property graphs and complex Cypher queries. Then, determining the equivalence of two Cypher queries is transformed into determining the equivalence of the corresponding Cypher algebraic representations, which can be verified by SMT solvers. To evaluate the effectiveness of GraphQE, we construct a dataset consisting of 148 pairs of equivalent Cypher queries. Among them, we have successfully proven 138 pairs of equivalent Cypher queries, demonstrating the effectiveness of GraphQE.

Modern managed language runtimes (e.g., Java, Go and C#) rely on garbage collection (GC) mechanisms to automatically allocate and reclaim in-memory objects. The efficiency of GC implementations can greatly impact the overall performance of runtime-based applications. To improve GC performance, the academic and industrial communities have proposed several approaches to evaluate the GC implementations in an individual runtime. However, these approaches target a specific managed language (e.g., Java), and cannot be used to compare the GC implementations in different runtimes. In this paper, we propose GEAR, an automated approach to construct consistent GC workloads for different managed language runtimes, which can further be used to evaluate GC implementations across different runtimes. Specifically, we design a group of runtime-agnostic Memory Operation Primitives (MOP), which can portray the memory usage information that influences GC. GEAR can further automatically convert a MOP program into runtime-specific programs for the target runtimes, which serve as a consistent GC workload for different runtimes. To build MOP programs with real-world GC workloads, we instrument the commonly-used runtime Java Virtual Machine (JVM) to collect the memory operation trace during a Java application's execution, and then transform the memory operation trace into a MOP program. The experimental result on three widely-used runtimes (i.e., Java, Go and C#) shows that GEAR can generate consistent GC workloads for different runtimes. We further conduct a comprehensive study on these three runtimes, and reveal some interesting findings about their GC performance, providing useful guidance for improving their GC implementations.

Database Management Systems (DBMSs) utilize transactions to guarantee data consistency and integrity. Incorrect implementations of transaction processing mechanisms can introduce critical transaction bugs, which can lead to incorrect database states after the involved transactions complete. However, we lack an effective test oracle to determine whether a DBMS produces a correct database state for a given concurrent transaction schedule. In this paper, we propose a general property for concurrent transaction schedules, write-specific serializability , in which a schedule of concurrent transactions should produce the same database state as a corresponding serial schedule of the same transactions. Through our empirical study on 35 critical transaction bugs collected from six widely-used DBMSs, we find that write-specific serializability can be an effective test oracle to expose critical transaction bugs in DBMSs. We further develop a simple and general transaction testing approach, WriteCheck, to automatically detect write-specific serializability violations by identifying inconsistencies in the final database states produced by the original transaction schedule and its corresponding serial schedule. We evaluate WriteCheck on the latest versions of six production-grade DBMSs, and have found 22 write-specific serializability violations, 11 of which have been confirmed as new critical transaction bugs.

Relational Database Management Systems (DBMSs) provide flexible DDL (Data Definition Language) statements that enable the creation, modification, and deletion of database schemas. In addition to database schemas, relational DBMSs typically manage various schema-related information internally, e.g., schema changes, tablespace allocation, and block-level data layout. However, incorrect implementations related to schema-related information maintenance and utilization can introduce schema-related logic bugs. These bugs can cause DQL (Data Query Language) statements to return incorrect query results and DML (Data Manipulation Language) statements to create incorrect database states. Existing approaches mainly focus on detecting logic bugs in DQL statements, but are ineffective in detecting schema-related logic bugs. In this paper, we propose a novel and general testing approach, DDLCheck, to effectively detect schema-related logic bugs in relational DBMSs. We first generate a complex DDL sequence seq gen that consists of various types of DDL statements, and then synthesize a rather simple DDL sequence seq syn , which utilizes CREATE statements to create the same database schema as seq gen . Executing the same SQL statements on the two databases created by seq gen and Seq syn should yield the same execution results. Any discrepancy between their execution results indicates a schema-related logic bug. To improve the testing efficiency of DDLCheck, we further design a DDL-sequence-oriented testing optimization strategy, which can help DDLCheck explore diverse schema-related information and detect schema-related logic bugs quickly. We implement and evaluate DDLCheck on six widely-used relational DBMSs. We have detected 34 bugs in these DBMSs, of which 29 bugs have been confirmed as previously unknown bugs and 9 bugs have been fixed.

Popular big data frameworks commonly run atop Java Virtual Machine (JVM) and rely on garbage collection (GC) mechanism to automatically allocate/reclaim in-memory objects. Existing garbage collectors are designed based on the hypothesis that most objects are short lived. However, big data frameworks usually generate many long-lived data objects, which can cause heavy GC overhead. Recent approaches have reduced GC overhead in big data frameworks but still suffer from heavy human efforts, additional runtime overhead, or suboptimal GC efficiency. This article describes the design of BridgeGC , a big-data-friendly garbage collector that significantly reduces GC overhead introduced by long-lived data objects. BridgeGC follows a cross-level co-design. At the big data framework level, BridgeGC provides two annotations for framework developers to denote the creation and release of data objects. Based on the annotations, BridgeGC tracks the lifecycles of annotated data objects and optimizes their allocation/reclamation at the GC level. At the GC level, we design a label-based allocator that stores data objects separately from other objects and balances their memory usage in the same JVM, leading to fewer GC cycles. We further design an efficient collector to eliminate unnecessary marking and copying of data objects during GC cycles, lowering the GC time. We have integrated BridgeGC into OpenJDK ZGC. The extensive evaluation, using two popular big data frameworks (Flink and Spark) and a key–value database (Cassandra), shows that BridgeGC achieves 31–82% GC time reduction compared to the baseline ZGC. BridgeGC also outperforms other traditional and academic garbage collectors in end-to-end performance.

Transactions are used to guarantee data consistency and integrity in Database Management Systems (DBMSs), and have become an indispensable component in DBMSs. However, faulty designs and implementations of DBMSs' transaction processing mechanisms can introduce transaction bugs, and lead to severe consequences, e.g., incorrect database states and DBMS crashes. An in-depth understanding of real-world transaction bugs can significantly promote effective techniques in combating transaction bugs in DBMSs.

Graph database systems (GDBs) allow efficiently creating, modifying, and retrieving graph data in a graph database. To accelerate graph queries, GDBs usually adopt various and complex optimization strategies. However, incorrect optimizations in GDBs can introduce optimization bugs, which cause a graph query to compute an incorrect query result, e.g., omitting a vertex in a graph database. In this paper, we propose Differential Optimization Testing (DOT), an effective and automated approach to detect optimization bugs in GDBs that adopt Gremlin as their query language. The main idea of DOT is that, given a Gremlin query$Q$, we execute it on the target GDB with two different optimization configurations and then verify whether they can compute the same query results for query$Q$. Any inconsistency between their query results indicates an optimization bug in the target GDB. To improve the efficiency of differential testing in DOT, we further propose an optimization-guided approach, aiming to explore more optimization strategies and more graph database features. We evaluate DOT on six popular and widely-used GDBs, i.e., Neo4j, OrientDB, JanusGraph, HugeGraph, TinkerGraph, and ArcadeDB. In total, we have found 28 unique optimization bugs, 16 of which have been confirmed as previously-unknown bugs.

Graph Database Systems (GDBs) support efficiently storing and retrieving graph data, and have become a critical component in many important applications. Many widely-used GDBs utilize the Gremlin query language to create, modify, and retrieve data in graph databases, in which developers can assemble a sequence of Gremlin APIs to perform a complex query. However, incorrect implementations and optimizations of GDBs can introduce logic bugs, which can cause Gremlin queries to return incorrect query results, e.g., omitting vertices in a graph database. In this paper, we propose Query Di sassembling (QuDi), an effective testing technique to automatically detect logic bugs in Gremlin-based GDBs. Given a Gremlin query Q, QuDi disassembles Q into a sequence of atomic graph traversals TList, which shares the equivalent execution semantics with Q. If the execution results of Q and TList are different, a logic bug is revealed in the target GDB. We evaluate QuDi on six popular GDBs, and have found 25 logic bugs in these GDBs, 10 of which have been confirmed as previously-unknown bugs by GDB developers.

Database Management Systems (DBMSs) are widely used to efficiently store and retrieve data. DBMSs usually support various metadata, e.g., integrity constraints for ensuring data integrity and indexes for locating data. DBMSs can further utilize these metadata to optimize query evaluation. However, incorrect metadata-related optimizations can introduce metadata-related logic bugs, which can cause a DBMS to return an incorrect query result for a given query. In this paper, we propose a general and effective testing approach, Raw database construction (Radar), to detect metadata-related logic bugs in DBMSs. Given a database db containing some metadata, Radar first constructs a raw database rawDb , which wipes out the metadata in db and contains the same data as db. Since db and rawDb have the same data, they should return the same query result for a given query. Any inconsistency in their returned query results indicates a metadata-related logic bug. To effectively detect metadata-related logic bugs, we further propose a metadata-oriented testing optimization strategy to focus on testing previously unseen metadata, thus detecting more metadata-related logic bugs quickly. We implement and evaluate Radar on five widely-used DBMSs, and have detected 42 bugs, of which 38 have been confirmed as new bugs and 16 have been fixed by DBMS developers.

Distributed systems have become the backbone of cloud computing. Incorrect system designs and implementations can greatly impair the reliability of distributed systems. Although a distributed system design modelled in the formal specification can be verified by formal model checking, it is still challenging to figure out whether its corresponding implementation conforms to the verified specification. An incorrect system implementation can violate its verified specification, and causes intricate bugs.

Decentralized Finance (DeFi) ecosystem has grown rapidly in the past few years. In the DeFi ecosystem, flash loan is a novel type of uncollateralized loan with nearly negligible lending costs. Malicious attackers can easily borrow a large number of crypto assets, and utilize them to disrupt the price of crypto assets to make a profit. Many flash loan based price manipulation attacks have been reported recently, and caused immense economic losses, e.g., 30 million USD in a single attack. In this paper, we conduct an empirical study on real-world flash loan based attacks in the past two years and present three attack patterns for price manipulation attacks. Then, we propose an approach, LeiShen, to automatically detect price manipulation attacks with asset transfers. We evaluate LeiShen on the first 14,500,000 blocks in Ethereum, and detect 180 attacks with a precision of 78.9%. Among our newly-found attacks, the severest attack has caused a total loss of more than 6.1 million USD.

Transactions are used to maintain the data integrity of databases, and have become an indispensable feature in modern Database Management Systems (DBMSs). Despite extensive efforts in testing DBMSs and verifying transaction processing mechanisms, isolation bugs still exist in widely-used DBMSs when these DBMSs violate their claimed transaction isolation levels. Isolation bugs can cause severe consequences, e.g., incorrect query results and database states. In this paper, we propose a novel transaction testing approach, Transaction oracle construction (Troc), to automatically detect isolation bugs in DBMSs. The core idea of Troc is to decouple a transaction into independent statements, and execute them on their own database views, which are constructed under the guidance of the claimed transaction isolation level. Any divergence between the actual transaction execution and the independent statement execution indicates an isolation bug. We implement and evaluate Troc on three widely-used DBMSs, i.e., MySQL, MariaDB, and TiDB. We have detected 5 previously-unknown isolation bugs in the latest versions of these DBMSs.

To support high reliability and availability, modern cloud systems are designed to be resilient to node crashes and reboots. That is, a cloud system should gracefully recover from node crashes/reboots and continue to function. However, node crashes/reboots that occur under special timing can trigger crash recovery bugs that lie in incorrect crash recovery protocols and their implementations. To ensure that a cloud system is free from crash recovery bugs, some fault injection approaches have been proposed to test whether a cloud system can correctly recover from various crash scenarios. These approaches are not effective in exploring the huge crash scenario space without developers' knowledge. In this paper, we propose Crash Fuzz, a fault injection testing approach that can effectively test crash recovery behaviors and reveal crash recovery bugs in cloud systems. CrashFuzz mutates the combinations of possible node crashes and reboots according to runtime feedbacks, and prioritizes the combinations that are prone to increase code coverage and trigger crash recovery bugs for smart exploration. We have implemented CrashFuzz and evaluated it on three popular open-source cloud systems, i.e., ZooKeeper, HDFS and HBase. CrashFuzz has detected 4 unknown bugs and 1 known bug. Compared with other fault injection approaches, CrashFuzz can detect more crash recovery bugs and achieve higher code coverage.

Database Management Systems (DBMSs) provide efficient data retrieval and manipulation for many applications through Structured Query Language (SQL). Incorrect implementations of DBMSs can result in logic bugs, which cause SELECT queries to fetch incorrect results, or UPDATE and DELETE queries to generate incorrect database states. Existing approaches mainly focus on detecting logic bugs in SELECT queries. However, logic bugs in UPDATE and DELETE queries have not been tackled. In this paper, we propose a novel and general approach, which we have termed Differential Query Execution (DQE), to detect logic bugs in SELECT, UPDATE and DELETE queries of DBMSs. The core idea of DQE is that different SQL queries with the same predicate usually access the same rows in a database. For example, a row updated by an UPDATE query with a predicate φ should also be fetched by a SELECT query with the same predicate φ, If not, a logic bug is revealed in the target DBMS. To evaluate the effectiveness and generality of DQE, we apply DQE on five production-level DBMSs, i.e., MySQL, MariaDB, TiDB, CockroachDB and SQLite. In total, we have detected 50 unique bugs in these DBMSs, 41 of which have been confirmed, and 11 have been fixed. We expect that the simplicity and generality of DQE can greatly improve the reliability of DBMSs.

Deep Neural Network (DNN) classifiers easily yield high confidence for Out-of-Distribution (OOD) examples beyond the training distribution, i.e., In-Distribution (ID), leading to classification errors. Detecting and rejecting various OOD examples is crucial for the reliability of DNNs. More challenging, well-built detections can also suffer from being re-bypassed by adversarial attacks perturbing unseen OOD examples. Some existing works introduce adversarial training on the auxiliary outliers to improve the robustness of OOD detection. However, in this work, we find that applying adversarial training on the auxiliary outliers is insufficient to make the detection robust to strong adaptive attacks. To fix this bug of OOD detection, we propose a semi-supervised adversarial training approach, RobDet, which mines adversarially perturbed ID examples from within the neighborhood of clean ID ones as auxiliary outliers and uses multiple "other" classes to train them together with other auxiliary clean and adversarially perturbed outliers to enhance the robustness of OOD detection without significantly sacrificing the performance on clean OOD examples. Experiments show that RobDet has a significant advantage in detecting malicious OOD examples generated by strong adaptive attacks while maintaining advanced performance in detecting clean OOD examples.

Dynamic taint tracking is a powerful information flow analysis approach, which can be applied in many analysis scenarios, e.g., debugging, testing, and security vulnerability detection. Most dynamic taint tracking approaches are designed for standalone systems, and cannot support inter-node taint tracking in distributed systems. Few inter-node taint tracking approaches are designed for specific distributed systems, e.g., Apache Spark, and require specific modifications to different distributed systems.In this paper, we present DisTA, a generic dynamic taint tracking tool for Java-based distributed systems. By instrumenting common network communication modules in Java, DisTA can perform inter-node taint tracking for different distributed systems with little manual efforts. We evaluate DisTA on five large-scale real-world distributed systems, e.g., ZooKeeper and Yarn, and require only 10 LOC launch script modification on average. The experimental results show that DisTA can accurately track all inter-node taints with a relatively low overhead.

Built on the WeChat social platform, WeChat Mini-Programs are widely used by more than 400 million users every day. Consequently, the reliability of Mini-Programs is particularly crucial. However, WeChat Mini-Programs suffer from various bugs related to execution environment, lifecycle management, asynchronous mechanism, etc. These bugs have seriously affected users' experience and caused serious impacts.

Besides third-party packages, the Python interpreter and system libraries are also critical dependencies of a Python program. In our empirical study, 34% programs are only compatible with specific Python interpreter versions, and 24% programs require specific system libraries. However, existing techniques mainly focus on inferring third-party package dependencies. Therefore, they can lack other necessary dependencies and violate version constraints, thus resulting in program build failures and runtime errors.

Smart devices have been widely adopted in our daily life. A smart home system, e.g., Home Assistant and openHAB, can be equipped with hundreds and even thousands of smart devices. A smart home system communicates with smart devices through various device integrations, each of which is responsible for a specific kind of devices. Developing high-quality device integrations is a challenging task, in which developers have to properly handle the heterogeneity of different devices, unexpected exceptions, etc. We find that device integration bugs, i.e., iBugs, are prevalent and have caused various consequences, e.g., causing devices unavailable, unexpected device behaviors.

Graph database systems (GDBs) allow efficiently storing and retrieving graph data, and have become the critical component in many applications, e.g., knowledge graphs, social networks, and fraud detection. It is important to ensure that GDBs operate correctly. Logic bugs can occur and make GDBs return an incorrect result for a given query. These bugs are critical and can easily go unnoticed by developers when the graph and queries become complicated. Despite the importance of GDBs, logic bugs in GDBs have received less attention than those in relational database systems.

Database Management Systems (DBMSs) utilize transactions to ensure the consistency and integrity of data. Incorrect transaction implementations in DBMSs can lead to severe consequences, e.g., incorrect database states and query results. Therefore, it is critical to ensure the reliability of transaction implementations.

Bitcoin has emerged as a popular decentralized cryptocurrency and attracted much attention from the public. Bitcoin embodies the Nakamoto consensus to reach an agreement about its blockchain ledger. However, the Nakamoto consensus can suffer from selfish mining attacks. Existing studies on selfish mining usually assume that the total mining power is divided into two parts (i.e., honest and selfish), and ignore propagation delay among miners. The assumptions cannot reflect real-world scenarios, in which multiple miners generate blocks at a fixed interval and propagate them with certain delay. Therefore, it is unknown how the practical factors, i.e., multiple miners and propagation delay, can affect selfish mining.In this paper, we explore the impact of multiple miners and propagation delay on selfish mining. First, we propose a new selfish mining strategy that can handle these factors. Second, we design a simulation approach to analyze the performance of the new selfish mining strategy. From our empirical study we observe many interesting findings that can be utilized in combating selfish mining. For example, the blockchain system with a higher orphan rate is more vulnerable to the selfish mining attack.

Spreadsheets are widely used in various business tasks, and contain amounts of valuable data. However, spreadsheet tables are usually organized in a semi-structured way, and contain complicated semantic structures, e.g., header types and relations among headers. Lack of documented semantic table structures, existing data analysis and error detection tools can hardly understand spreadsheet tables. Therefore, identifying semantic table structures in spreadsheet tables is of great importance, and can greatly promote various analysis tasks on spreadsheets.

Node.js has become a widely-used event-driven architecture for server-side and desktop applications. Node.js provides an effective asynchronous event-driven programming model, and supports asynchronous tasks and multi-priority event queues. Unexpected races among events and asynchronous tasks can cause severe consequences. Existing race detection approaches in Node.js applications mainly adopt random fuzzing technique, and can miss races due to large schedule space.In this paper, we propose a dynamic race detection approach NRace for Node.js applications. In NRace, we build precise happens-before relations among events and asynchronous tasks in Node.js applications, which also take multi-priority event queues into consideration. We further develop a predictive race detection technique based on these relations. We evaluate NRace on 10 realworld Node.js applications. The experimental result shows that NRace can precisely detect 6 races, and 5 of them have been confirmed by developers.

The blockchain technology is regarded as a significant trust-building technology and has attracted much attention from the public. The longest chain rule has been widely applied in blockchain systems to reach consensus on the distributed ledger. However, the longest chain rule cannot support a higher transaction throughput due to its lower security. As an alternative solution to the longest chain rule, GHOST is proposed as a safer consensus rule. Existing studies show that the longest chain rule can suffer from selfish mining attacks. However, it is unclear how selfish mining attacks perform on GHOST. In this paper, we explore the performance of selfish mining on GHOST. We first propose the original selfish mining (GHOST-SM) and stubborn mining (GHOST-StuM) for GHOST. We then evaluate these two selfish mining strategies on our blockchain simulation system. The experimental result shows that GHOST achieves better security than the longest chain rule. However, when the block generation rate increases, the security of GHOST is close to the longest chain rule. For example, the threshold for selfish mining attacks of GHOST is increased by 47.55% and 0.60% compared to the longest chain rule corresponding to the block generation interval of 1 second and 15 seconds.

Deep learning (DL) has been widely adopted in many safety-critical scenarios. Deep neural networks (DNNs) usually play the core part in these DL systems. Existing studies have shown that DNNs can suffer from various vulnerabilities, and cause severe consequences. To improve the testing adequacy of DNNs, researchers have proposed several coverage criteria, e.g., neuron coverage in DeepXplore. The prediction result of a DNN is jointly determined by the outputs of neurons and the connection weights that they connect into next-level neurons. However, existing coverage criteria use only the output of a neuron to determine the activation state of the neuron and ignore the connection weights it emits.In this paper, we propose DeepCon, a novel contribution coverage. In DeepCon, we define a term contribution as the combination of the output of a neuron and the connection weight it emits, and use the contribution coverage to gauge the testing adequacy of DNNs. DeepCon can thoroughly cover both neurons and the connection weights they emit and can scale well to large DNNs. We further propose a contribution coverage guided test generation approach, DeepCon-Gen, which can automatically generate tests and activate inactivated contributions of DNNs. We evaluate DeepCon and DeepCon-Gen on five different DNNs over two popular datasets. The experimental results show that DeepCon can well present the testing adequacy of these DNNs. DeepCon-Gen can effectively activate the inactivated contributions, and 62.6% of the generated tests can lead to mispredictions.

Stream clustering is an important data mining technique to capture the evolving patterns in real-time data streams. Today’s data streams, e.g., IoT events and Web clicks, are usually high-speed and contain dynamically-changing patterns. Existing stream clustering algorithms usually follow an online-offline paradigm with a one-record-at-a-time update model, which was designed for running in a single machine. These stream clustering algorithms, with this sequential update model, cannot be efficiently parallelized and fail to deliver the required high throughput for stream clustering.In this paper, we present DistStream, a distributed framework that can effectively scale out online-offline stream clustering algorithms. To parallelize these algorithms for high throughput, we develop a mini-batch update model with efficient parallelization approaches. To maintain high clustering quality, DistStream’s mini-batch update model preserves the update order in all the computation steps during parallel execution, which can reflect the recent changes for dynamically-changing streaming data. We implement DistStream atop Spark Streaming, as well as four representative stream clustering algorithms based on DistStream. Our evaluation on three real-world datasets shows that DistStream-based stream clustering algorithms can achieve sublinear throughput gain and comparable (99%) clustering quality with their single-machine counterparts.

Apache Spark has been widely used to build big data applications. Spark utilizes the abstraction of Resilient Distributed Dataset (RDD) to store and retrieve large-scale data. To reduce duplicate computation of an RDD, Spark can cache the RDD in memory and then reuse it later, thus improving performance. Spark relies on application developers to enforce caching decisions by using persist() and unpersist() APIs, e.g., which RDD is persisted and when the RDD is persisted / unpersisted. Incorrect RDD caching decisions can cause duplicate computations, or waste precious memory resource, thus introducing serious performance degradation in Spark applications. In this paper, we propose CacheCheck, to automatically detect cache-related bugs in Spark applications. We summarize six cache-related bug patterns in Spark applications, and then dynamically detect cache-related bugs by analyzing the execution traces of Spark applications. We evaluate CacheCheck on six real-world Spark applications. The experimental result shows that CacheCheck detects 72 previously unknown cache-related bugs, and 28 of them have been fixed by developers.

In order to speed up spreadsheet development productivity, end users can create a spreadsheet table by copying and modifying an existing one. These two tables share the similar computational semantics, and form a table clone. End users may modify the tables in a table clone, e.g., adding new rows and deleting columns, thus introducing structure changes into the table clone. Our empirical study on real-world spreadsheets shows that about 58.5% of table clones involve structure changes. However, existing table clone detection approaches in spreadsheets can only detect table clones with the same structures. Therefore, many table clones with structure changes cannot be detected.

Network partitions are inevitable in large-scale cloud systems. Despite developer's efforts in handling network partitions throughout designing, implementing and testing cloud systems, bugs caused by network partitions, i.e., partition bugs, still exist and cause severe failures in production clusters. It is challenging to expose these partition bugs because they often require network partitions to start and stop at specific timings.

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

Node.js has been widely-used as an event-driven server-side architecture. To improve performance, a task in a Node.js application is usually divided into a group of events, which are non-deterministically scheduled by Node.js. Developers may assume that the group of events (named atomic event group) should be atomically processed, without interruption. However, the atomicity of an atomic event group is not guaranteed by Node.js, and thus other events may interrupt the execution of the atomic event group, break down the atomicity and cause unexpected results. Existing approaches mainly focus on event race among two events, and cannot detect high-level atomicity violations among a group of events. In this paper, we propose NodeAV, which can predictively detect atomicity violations in Node.js applications based on an execution trace. Based on happens-before relations among events in an execution trace, we automatically identify a pair of events that should be atomically processed, and use predefined atomicity violation patterns to detect atomicity violations. We have evaluated NodeAV on real-world Node.js applications. The experimental results show that NodeAV can effectively detect atomicity violations in these Node.js applications.

Exception mechanism is widely used in cloud systems. This is mainly because it separates the error handling code from main business logic. However, the huge space of potential error conditions and the sophisticated logic of cloud systems present a big hurdle to the correct use of exception mechanism. As a result, mistakes in the exception use may lead to severe consequences, such as system downtime and data loss. To address this issue, the communities direly need a better understanding of the exception-related bugs, i.e., eBugs, which are caused by the incorrect use of exception mechanism, in cloud systems. In this paper, we present a comprehensive study on 210 eBugs from six widely-deployed cloud systems, including Cassandra, HBase, HDFS, Hadoop MapReduce, YARN, and ZooKeeper. For all the studied eBugs, we analyze their triggering conditions, root causes, bug impacts, and their relations. To the best of our knowledge, this is the first study on eBugs in cloud systems, and the first one that focuses on triggering conditions. We find that eBugs are severe in cloud systems: 74% of our studied eBugs affect system availability or integrity. Luckily, exposing eBugs through testing is possible: 54% of the eBugs are triggered by non-semantic conditions, such as network errors; 40% of the eBugs can be triggered by simulating the triggering conditions at simple system states. Furthermore, we find that the triggering conditions are useful for detecting eBugs. Based on such relevant findings, we build a static analysis tool, called DIET, and apply it to the latest versions of the studied systems. Our results show that DIET reports 31 bugs and bad practices, and 23 of them are confirmed by the developers as "previously-unknown" ones.

Popular big data frameworks, ranging from Hadoop MapReduce to Spark, rely on garbage-collected languages, such as Java and Scala. Big data applications are especially sensitive to the effectiveness of garbage collection (i.e., GC), because they usually process a large volume of data objects that lead to heavy GC overhead. Lacking in-depth understanding of GC performance has impeded performance improvement in big data applications. In this paper, we conduct the first comprehensive evaluation on three popular garbage collectors, i.e., Parallel, CMS, and G1, using four representative Spark applications. By thoroughly investigating the correlation between these big data applications' memory usage patterns and the collectors' GC patterns, we obtain many findings about GC inefficiencies. We further propose empirical guidelines for application developers, and insightful optimization strategies for designing big-data-friendly garbage collectors.

Spreadsheets are widely used in various business tasks. Spreadsheet users may put similar data and computations by repeating a block of cells (a unit) in their spreadsheets. We name the unit and all its expanding ones as an expandable group. All units in an expandable group share the same or similar formats and semantics. As a data storage and management tool, expandable groups represent the fundamental structure in spreadsheets. However, existing spreadsheet systems do not recognize any expandable groups. Therefore, other spreadsheet analysis tools, e.g., data integration and fault detection, cannot utilize this structure of expandable groups to perform precise analysis. In this paper, we propose ExpCheck to automatically extract expandable groups in spreadsheets. We observe that continuous units that share the similar formats and semantics are likely to be an expandable group. Inspired by this, we inspect the format of each cell and its corresponding semantics, and further classify them into expandable groups according to their similarity. We evaluate ExpCheck on 120 spreadsheets randomly sampled from the EUSES and VEnron corpora. The experimental results show that ExpCheck is effective. ExpCheck successfully detect expandable groups with F1-measure of 73.1%, significantly outperforming the state-of-the-art techniques (F1-measure of 13.3%).

In large-scale distributed systems, node crashes are inevitable, and can happen at any time. As such, distributed systems are usually designed to be resilient to these node crashes via various crash recovery mechanisms, such as write-ahead logging in HBase and hinted handoffs in Cassandra. However, faults in crash recovery mechanisms and their implementations can introduce intricate crash recovery bugs, and lead to severe consequences.

To reduce the effort of creating similar spreadsheets, end users may create expected spreadsheets from some predesigned templates, which contain necessary table layouts (e.g., headers and styles) and formulas, other than from scratch. When there are no explicitly predesigned spreadsheet templates, end users often take an existing spreadsheet as the instance template to create a new spreadsheet. However, improper template design and usage can introduce various issues. For example, a formula error in the template can be easily propagated to all its instances without users’ noticing. Since template design and usage are rarely documented in literature and practice, practitioners and researchers lack understanding of them to achieve effective improvement. In this paper, we conduct the first empirical study on the design and the usage of spreadsheet templates based on 47 predesigned templates (490 instances in total), and 21 instance template groups (168 template and instance pairs in total), extracted from the Enron corpus. Our study reveals a number of spreadsheet template design and usage issues in practice, and also sheds lights on several interesting research directions.

Spreadsheets play an important role in various business tasks, such as financial reports and data analysis. In spreadsheets, empty cells are widely used for different purposes, e.g., separating different tables, or default value "0". However, a user may delete a formula unintentionally, and leave a cell empty. Such ad-hoc modification may introduce a faulty empty cell that should have a formula. We observe that the context of an empty cell can help determine whether the empty cell is faulty. For example, is the empty cell next to a cell array in which all cells share the same semantics? Does the empty cell have headers similar to other non-empty cells'? In this paper, we propose EmptyCheck, to detect faulty empty cells in spreadsheets. By analyzing the context of an empty cell, EmptyCheck validates whether the cell belong to a cell array. If yes, the empty cell is faulty since it does not contain a formula. We evaluate EmptyCheck on 100 randomly sampled EUSES spreadsheets. The experimental result shows that EmptyCheck can detect faulty empty cells with high precision (75.00%) and recall (87.04%). Existing techniques can detect only 4.26% of the true faulty empty cells that EmptyCheck detects.

API specifications play an important role in software development. However, API specifications are often not well documented, especially for JavaScript. Many JavaScript API specifications lack of precise type information for API parameters and return values. In this paper, we propose a static approach for mining JavaScript type specifications automatically. We gather the usage information of return values and parameters statically, and infer types of return values based their usages, by identifying a known type which they are used most likely to be, and infer parameters by identifying the most used parameters. We evaluate the approach on the homepages of Alexa top 1000 websites, the experimental results show that our approach can gain high precision. Our case study on jQuery shows that our approach gains high precision and reasonable recall on jQuery, and we can use our inferred API type specifications to detect 2 jQuery misusage errors in real-world web sites, and 1 missing type error in jQuery documentations.

Configuration management tools, CMTs for short, are a set of indispensable software for DevOps (Development and Operations). CMTs automate system deployment and configuration through CMT modules, which are reusable, shareable units of configuration code. Therefore, thousands of CMT modules have been developed for various systems, and are still growing fast. Although CMT repositories usually provide keyword-and tag-based search, a large number of search results could prevent users from finding desired CMT modules. CMT modules could be managed in a hierarchical categorization, which can limit the search scope in specified categories, and thus help to improve search performance. Unfortunately, there is no hierarchical categorization in all CMT repositories. In this paper, we propose a hierarchical categorization approach for CMT modules. Our approach first extracts frequently-used module tags as categories, and constructs the category hierarchy by mining the hierarchical relations among tags. We leverage online module profiles (names, descriptions and tags) as source information to do categorization. It trains a set of classifiers by taking TF-IDF (term frequency-inverse document frequency) of module profiles as features. Finally, our evaluation on more than 11,000 CMT modules shows that our approach could obtain 90 fine-grained and multi-layered categories, and does categorization for CMT modules with high precision (0.81), recall (0.88) and F-Measure (0.85).

Operation services are reusable and shareable units of configuration code executed by configuration management tools (CMTs), achieving continuous deployment and continuous delivery. With the prevalence of DevOps (Development and Operations), thousands of operation services have been developed for various software systems, and they are publicly available through the online repositories of popular CMTs. However, locating and retrieving desired operation services is challenging since keyword-and tag-based search provided by a repository is with low precision. In this paper, we implement a hierarchical categorization approach based search service, named OSFinder, which searches and locates desired operation services more accurately. OSFinder first constructs a category hierarchy for operation services across multiple repositories, and then it classifies over 13,000 operation services into 90 categories based on machine learning technique, finally it provides a search for users. With OSFinder, a user can narrow down his search scope by tracking the category hierarchy in a top-down way, and then searches in a small group with keywords. The evaluation shows that OSFinder outperforms keyword-and tag-based search.

Node.js becomes increasingly popular in building server-side JavaScript applications. It adopts an event-driven model, which supports asynchronous I/O and non-deterministic event processing. This asynchrony and non-determinism can introduce intricate concurrency bugs, and leads to unpredictable behaviors. An in-depth understanding of real world concurrency bugs in Node.js applications will significantly promote effective techniques in bug detection, testing and fixing for Node.js. In this paper, we present NodeCB, a comprehensive study on real world concurrency bugs in Node.js applications. Specifically, we have carefully studied 57 real bug cases from open-source Node.js applications, and have analyzed their bug characteristics, e.g., bug patterns and root causes, bug impacts, bug manifestation, and fix strategies. Through this study, we obtain several interesting findings, which may open up many new research directions in combating concurrency bugs in Node.js. For example, one finding is that two thirds of the bugs are caused by atomicity violation. However, due to lack of locks and transaction mechanism, Node.js cannot easily express and guarantee the atomic intention.

Version information plays an important role in spreadsheet understanding, maintaining and quality improving. However, end users rarely use version control tools to document spreadsheets' version information. Thus, the spreadsheets' version information is missing, and different versions of a spreadsheet coexist as individual and similar spreadsheets. Existing approaches try to recover spreadsheet version information through clustering these similar spreadsheets based on spreadsheet filenames or related email conversation. However, the applicability and accuracy of existing clustering approaches are limited due to the necessary information (e.g., filenames and email conversation) is usually missing. We inspected the versioned spreadsheets in VEnron, which is extracted from the Enron Corporation. In VEnron, the different versions of a spreadsheet are clustered into an evolution group. We observed that the versioned spreadsheets in each evolution group exhibit certain common features (e.g., similar table headers and worksheet names). Based on this observation, we proposed an automatic clustering algorithm, SpreadCluster. SpreadCluster learns the criteria of features from the versioned spreadsheets in VEnron, and then automatically clusters spreadsheets with the similar features into the same evolution group. We applied SpreadCluster on all spreadsheets in the Enron corpus. The evaluation result shows that SpreadCluster could cluster spreadsheets with higher precision (78.5% vs. 59.8%) and recall rate (70.7% vs. 48.7%) than the filename-based approach used by VEnron. Based on the clustering result by SpreadCluster, we further created a new versioned spreadsheet corpus VEnron2, which is much bigger than VEnron (12,254 vs. 7,294 spreadsheets). We also applied SpreadCluster on the other two spreadsheet corpora FUSE and EUSES. The results show that SpreadCluster can cluster the versioned spreadsheets in these two corpora with high precision (91.0% and 79.8%).

Spreadsheets are widely used by end users for numerical computation in their business. Spreadsheet cells whose computation is subject to the same semantics are often clustered in a row or column as a cell array. When a spreadsheet evolves, the cells in a cell array can degenerate due to ad hoc modifications. Such degenerated cell arrays no longer keep cells prescribing the same computational semantics, and are said to exhibit ambiguous computation smells. We propose CACheck, a novel technique that automatically detects and repairs smelly cell arrays by recovering their intended computational semantics. Our empirical study on the EUSES and Enron corpora finds that such smelly cell arrays are common. Our study also suggests that CACheck is useful for detecting and repairing real spreadsheet problems caused by smelly cell arrays. Compared with our previous work AmCheck, CACheck detects smelly cell arrays with higher precision and recall rate.

Spreadsheets are widely used by end users for various business tasks, such as data analysis and financial reporting. End users may perform similar tasks by cloning a block of cells (table) in their spreadsheets. The corresponding cells in these cloned tables are supposed to keep the same or similar computational semantics. However, when spreadsheets evolve, thus cloned tables can become inconsistent due to ad-hoc modifications, and as a result suffer from smells. In this paper, we propose TableCheck to detect table clones and related smells due to inconsistency among them. We observe that two tables with the same header information at their corresponding cells are likely to be table clones. Inspired by existing fingerprint-based code clone detection techniques, we developed a detection algorithm to detect this kind of table clones. We further detected outliers among corresponding cells as smells in the detected table clones. We implemented our idea into TableCheck, and applied it to real-world spreadsheets from the EUSES corpus. Experimental results show that table clones commonly exist (21.8%), and 25.6% of the spreadsheets with table clones suffer from smells due to inconsistency among these clones. TableCheck detected table clones and their smells with a precision of 92.2% and 85.5%, respectively, while existing techniques detected no more than 35.6% true smells that TableCheck could detect.

JavaScript libraries, such as JQuery, are widely used in web applications. In these libraries' event delegation models, a DOM element's event handler is usually bound to its parent nodes. This makes it difficult for developers to figure out the user-defined event handlers of a specified DOM element. In this paper, we propose an approach that identifies the user-defined event handlers of DOM elements in a web page. We dynamically collect the execution trace for each triggered event in a web page, and analyze how each function is used in the execution trace to discover the event handlers for each event. We evaluate our approach on seven real-world web applications. The result shows that our approach is effective, with an overall precision of 100% and recall of 99.8%.

Traditional web applications are not suitable for mobile devices, because mobile devices are usually equipped with small screens and use slow and expensive mobile network. In order to adapt web applications to mobile devices, existing approaches reconstruct particular web applications, or adapt only partial views of web pages. They require a lot of additional reconstructing work or network bandwidth. In this paper we propose an approach that can extract a part of a web page as an executable web control efficiently. Our approach monitors the execution of user code, builds a dependency graph of executed user code, and performs slicing based on the dependency graph. The evaluation on two real-world web applications shows that our approach is able to extract executable web controls efficiently, and for the two web applications, visiting extracted web controls instead of the original web pages can save 98% and 23% of bandwidth respectively.

JavaScript has become the most popular language for client-side web applications. Due to JavaScript's highly-dynamic features and event-driven design, it is not easy to debug web application errors. Record-replay techniques are widely used to reproduce errors in web applications. However, the key events related to an error are hidden in the massive event trace collected during a long running. As a result, error diagnosis with the long event trace is exhausting and time-consuming. We present a tool JSTrace that can effectively cut down the web application error reproducing time and facilitate the diagnosis. Based on the dynamic dependencies of JavaScript and DOM instructions, we develop a novel dynamic slicing technique that can remove events irrelevant to the error reproducing. In this process, many events and related instructions are removed without losing the reproducing accuracy. Our evaluation shows that the reduced event trace can faithfully reproduce errors with an average reduction rate of 96%.

Out of memory (OOM) errors occur frequently in data-intensive applications that run atop distributed data-parallel frameworks, such as MapReduce and Spark. In these applications, the memory space is shared by the framework and user code. Since the framework hides the details of distributed execution, it is challenging for users to pinpoint the root causes and fix these OOM errors. This paper presents a comprehensive characteristic study on 123 real-world OOM errors in Hadoop and Spark applications. Our major findings include: (1) 12% errors are caused by the large data buffered/cached in the framework, which indicates that it is hard for users to configure the right memory quota to balance the memory usage of the framework and user code. (2) 37% errors are caused by the unexpected large runtime data, such as large data partition, hotspot key, and large key/value record. (3) Most errors (64%) are caused by memory-consuming user code, which carelessly processes unexpected large data or generates large in-memory computing results. Among them, 13% errors are also caused by the unexpected large runtime data. (4) There are three common fix patterns (used in 34% errors), namely changing the memory/dataflow-related configurations, dividing runtime data, and optimizing user code logic. Our findings inspire us to propose potential solutions to avoid the OOM errors: (1) providing dynamic memory management mechanisms to balance the memory usage of the framework and user code at runtime; (2) providing users with memory+disk data structures, since accumulating large computing results in in-memory data structures is a common cause (15% errors).

Spreadsheets are widely used by end users for numerical computation in their business. Spreadsheet cells whose computation is subject to the same semantics are often clustered in a row or column. When a spreadsheet evolves, these cell clusters can degenerate due to ad hoc modifications or undisciplined copy-and-pastes. Such degenerated clusters no longer keep cells prescribing the same computational semantics, and are said to exhibit ambiguous computation smells. Our empirical study finds that such smells are common and likely harmful. We propose AmCheck, a novel technique that automatically detects and repairs ambiguous computation smells by recovering their intended computational semantics. A case study using AmCheck suggests that it is useful for discovering and repairing real spreadsheet problems.