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.

Multi-objective evolutionary algorithms (MOEAs) are widely used for searching optimal solutions in complex multi-component applications. Traditional MOEAs for multi-component deep learning (MCDL) systems face challenges in enhancing the search efficiency while maintaining the diversity. To combat these, this paper proposes the first LLM-empowered adaptive evolutionary search algorithm to detect safety violations in MCDL systems. Inspired by the context-understanding ability of Large Language Models (LLMs), our approach promotes the LLM to comprehend the optimization problem and generate an initial population tailed to evolutionary objectives. Subsequently, it employs adaptive selection and variation to iteratively produce offspring, balancing the evolutionary efficiency and diversity. During the evolutionary process, to navigate away from the local optima, our approach integrates the evolutionary experience back into the LLM. This utilization harnesses the LLM's quantitative reasoning prowess to generate differential seeds, breaking away from current optimal solutions. We evaluate our approach in finding safety violations of MCDL systems, and compare its performance with state-of-the-art MOEA methods. Experimental results show that our approach can significantly improve the efficiency and diversity of the evolutionary search.

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.

Heterogeneous robots can work together to accomplish a variety of complex tasks and have shown great potential in many fields. There are many efforts to make robot task orchestration more efficient. However, current methods still have some limitations, including the lack of a high-level abstraction for programming method and fault handling mechanism. In this paper, we design a state machine-based, fault-tolerant framework for heterogeneous multi-robot collaboration named HeRo, to effectively support the development of heterogeneous multi-robot systems. HeRo has three key techniques: (1) a state machine-based programming language to flexibly model robot behaviors and tasks; (2) a state synchronization mechanism to achieve information exchange and maintain the consistency among heterogeneous robots in distributed environments; (3) a fault detection and recovery mechanism to monitor the system's runtime states and use Large Language Model (LLM) combined with Planning Domain Definition Language (PDDL) to enable automated recovery. We evaluate the effectiveness and fault recovery capability of the framework by setting up manufacturing task and fault scenarios with varying difficulty in the ARIAC simulation environment, achieving a 100% task completion rate, with low system overhead and flexible scalability.

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.

Boolean expression matching plays an important role in many applications. However, existing solutions still show efficiency and scalability limitations. For example, existing solutions often exhibit degraded performance when applied to high-dimensional and diverse workloads, and existing algorithms rarely consider supporting concurrent matching and index updating under multicore environments. To overcome these limitations, in this article, we first design the PS-Tree data structure to efficiently index Boolean expressions in one dimension. By dividing predicates into disjoint predicate spaces, PS-Tree achieves high matching performance and good expressiveness. Based on the PS-Tree , we propose a Boolean expression matching algorithm called PSTDynamic . By dynamically adjusting the index and efficiently filtering out a large proportion of unmatching expressions, PSTDynamic achieves high matching performance under high-dimensional and diverse workloads. For multicore environment, we further extend the PSTDynamic algorithm to PSTParallel to achieve scalability with lower matching latency and higher matching throughput. We run experiments on both synthetic and real-world datasets. The experiments verify that our proposed algorithms show high efficiency and parallelism. Moreover, they also achieve fast index construction and a small memory footprint. Comprehensive experiments show that our solutions drastically outperform state-of-the-art methods.

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.

Kubernetes is the leading cluster management platform, and within Kubernetes, an operator is an application-specific program that leverages the Kubernetes API to automate operation tasks for managing an application deployed on a Kubernetes cluster. Users can declare a desired state for the managed cluster, specifying their configuration preferences. The operator program is responsible for reconciling the cluster's actual state to align with the desired state. However, the complex, dynamic, and distributed nature of the overall system can introduce operator bugs, and lead to severe consequences, e.g., outages and undesired cluster state. In this paper, we conduct the first comprehensive study on 210 operator bugs from 36 Kubernetes operators. For all the studied bugs, we investigate their root causes, manifestations, impacts and fixing. Our study reveals many interesting findings that can guide the detection and testing of operator bugs, as well as the development of more reliable operators.

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.

Ensuring the reliability and consistency of Internet of Things (IoT) systems is critical. Traditional approaches to maintaining consistency often rely on retry and rollback mechanisms, which can be inadequate and lead to further complications. These methods struggle with the complexity and heterogeneity of IoT systems, failing to provide robust and general solutions for real-time consistency assurance.

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.

Web applications play an important role in modern society. Quality assurance of web applications requires lots of manual efforts. In this paper, we propose WebQT, an automatic test case generator for web applications based on reinforcement learning. Specifically, to increase testing efficiency, we design a new reward model, which encourages the agent to mimic human testers to interact with the web applications. To alleviate the problem of state redundancy, we further propose a novel state abstraction technique, which can identify different web pages with the same functionality as the same state, and yields a simplified state space. We evaluate WebQT on seven open-source web applications. The experimental results show that WebQT achieves 45.4% more code coverage along with higher efficiency than the state-of-the-art technique. In addition, WebQT also reveals 69 exceptions in 11 real-world web applications.

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.

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.

Trigger-Action Programming (TAP) is a popular way of creating smart home automation applications. It can orchestrate IoT devices to fulfill user intents and make users’ daily lives more convenient. However, users’ daily lives usually have many complex scenarios that must be accomplished through several actions. The existing approaches cannot handle such situations as they mainly focus on creating simple TAP rules with a single action. This paper proposes SGen, an approach to automatically generate scenario-centric TAP rules by mining historical event traces. We first define two types of scenarios according to the characters of user activities. Accordingly, SGen identifies correlated and periodic events and uses them to synthesize scenario-centric TAP rules bottom-up without requiring all events of a potential scenario to happen at the exact moment and in the same order every time. Afterward, SGen ranks and recommends rules by prioritizing the candidates based on their diversity and significance. Finally, we evaluate SGen with two real-world datasets. The experimental results confirm that the generated scenario-centric TAP rules can match user scenarios and are more efficient in fulfilling user intents than simple rules.

Regression testing is an important means of assessing the quality of Node.js applications. However, non-deterministic executions inside Node.js framework could make test cases intermittently pass or fail on the same version of code, which are called flaky tests. Flaky tests can cause unreliable test results, and make developers waste a significant amount of time debugging the bugs that do not belong to the target application. In this paper, we conduct an empirical study on 87 flaky tests from 7 popular Node.js applications, and analyze the non-determinism that causes these flaky tests. Through this study, there is a wide range of non-determinism to cause flaky tests, including non-deterministic event triggering order, non-deterministic function calls, non-deterministic process/thread scheduling order, non-deterministic execution of asynchronous tasks and non-deterministic event triggering data. The result reveals that, existing approaches on event race detection are not sufficient for flaky test detection. In future, researchers can design flaky test detection approaches targeted at different categories of non-determinism.

Trigger-action programming (TAP) is a widely used development paradigm that simplifies the Internet of Things (loT) automation. However, the exceptional interactions between automation applications may result in interferences, such as conflicts and infinite loops, which cause undesirable consequences and even security and safety risks. While several techniques have been proposed to address this problem, they are often restricted in handling explicit and simple conflicts without considering contextual influences. In addition, they suffer from performance issues when applying to large-scale applications. To address these challenges, we design an effective and practical tool KnowDetector with comprehensive domain knowledge to detect application interferences. To detect application interferences, KnowDetector constructs an automation graph with 1) events, conditions, and actions from automation applications, 2) vertices representing physical environment channels, and 3) edges derived from potential semantic relations between the vertices. In order to make the graph extensively capture the interactions between automation applications, we propose a knowledge model named KnowloT that accurately characterizes loT devices with command-level loT services and the intricate relations between these services and the contextual environment. We abstract the interference detection into a graph pattern-matching problem and summarize ten application interference patterns of four types. Finally, KnowDetector can efficiently detect application interferences by searching for sub-graphs matching the patterns within the automation graph. We evaluated KnowDetector on three real-world datasets. The results demonstrated that it outperformed the other state-of-the-art tools with the highest precision, recall, and F-measure. In addition, KnowDetector is scalable to detect application interferences within a large number of applications with a minimal time overhead.

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.

Autonomous Driving Systems (ADSs) are safety-critical, and must be fully tested before being deployed on real-world roads. To comprehensively evaluate the performance of ADSs, it is essential to generate various safety-critical scenarios. Most of existing studies assess ADSs either by searching high-dimensional input space, or using simple and pre-defined test scenarios, which are not efficient or not adequate. To better test ADSs, this paper proposes to automatically generate safety-critical test scenarios for ADSs by influential behavior patterns, which are mined from real traffic trajectories. Based on influential behavior patterns, a novel scenario generation technique, CRISCO, is presented to generate safety-critical scenarios for ADSs testing. CRISCO assigns participants to perform influential behaviors to challenge the ADS. It generates different test scenarios by solving trajectory constraints, and improves the challenge of those non-critical scenarios by adding participants’ behavior from influential behavior patterns incrementally. We demonstrate CRISCO on an industrial-grade ADS platform, Baidu Apollo. The experiment results show that our approach can effectively and efficiently generate critical scenarios to crash ADS, and it exposes 13 distinct types of safety violations in 12 hours. It also outperforms two state-of-art ADS testing techniques by exposing more 5 distinct types of safety violations on the same roads.

Autonomous Driving Systems (ADSs) are safety-critical systems, and safety violations of Autonomous Vehicles (AVs) in real traffic will cause huge losses. Therefore, ADSs must be fully tested before deployed on real world roads. Simulation testing is essential to find safety violations of ADS. This paper proposes MOSAT, a multi-objective search-based testing framework, which constructs diverse and adversarial driving environment to expose safety violations of ADSs. Specifically, based on atomic driving maneuvers, MOSAT introduces motif pattern, which describes a sequence of maneuvers that can challenge ADS effectively. MOSAT constructs test scenarios by atomic maneuvers and motif patterns, and uses multi-objective genetic algorithm to search for adversarial and diverse test scenarios. Moreover, in order to test the performance of ADS comprehensively during long-mile driving, we design a novel continuous simulation testing technique, which runs the scenarios generated by multiple parallel search processes alternately in the simulator and can continuously create different perturbations to ADS. We demonstrate MOSAT on an industrial-grade platform, Baidu Apollo, and the experimental results show that MOSAT can effectively generate safety-critical scenarios to crash ADSs and it exposes 11 distinct types of safety violations in a short period of time. It also outperforms state-of-the-art techniques by finding more 6 distinct safety violations on the same road.

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.

Docker is the de-facto container technology for software system deployment and delivery. A Dockerfile specifies how to containerize a system into a Docker image. However, creating a Dockerfile is not trivial since resolving the dependencies (e.g., third-party libraries) of diverse software requires comprehensive domain knowledge. In this paper, we propose DockerGen to containerize software packages automatically. DockerGen constructs a knowledge graph containing rich knowledge of building Docker images by analyzing nearly 220 thousand Dockerfiles. DockerGen exploits the knowledge graph to containerize the target software by creating a Dockerfile specifying the base image, dependencies, and the operation workflow. We evaluate DockerGen on 100 software packages of various categories. DockerGen achieves a 73% build success rate and a 59% configuration success rate. The experimental result indicates it is viable to automate software containerization based on a domain knowledge graph.

With the increasing number of browsers and platforms on which the applications can be executed, cross-browser incompatibilities (XBIs) are becoming a serious problem for organizations to develop web-based software. In order to eliminate cross browser issues, existing work tries to repair layout XBIs using search-based technique. However, the designed fitness function is too strict, and may miss the chance to repair some layout XBIs. For each reported layout XBI, it will search all possible candidate fixes, and cannot reuse existing repair solutions for similar issues. This paper proposes to combine learning and search based technique to improve the state-of-the-art of automated repair of layout XBIs. By extracting the characteristics of successfully repaired layout XBIs and learn a decision tree, our approach will accelerate the search process by directly applying the recommended solution to fix similar XBIs. Moreover, by redesigning search-based repair process, our technique can improve the chance to repair layout XBIs. The initial evaluation shows that the proposed approach is effective.

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.

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.

Web 2.0 application based on JavaScript is a wide-spread application domain today as it delivers rich, interactive user experiences. However, with the increasing number of browsers and platforms on which the applications can be executed, cross-browser incompatibilities (XBIs) are becoming a serious problem for organizations to develop modern JavaScript-based Web applications. Although lots of XBIs detection techniques have been proposed, there are still some limitations: 1) existing techniques are prone to generating certain false positives/negatives that result from the fact that they ignore non-deterministic events (e.g., timer, asynchronous request/response) inside the browser; 2) detection process is inefficient, as the same elements located in different pages will be repeatedly checked even if they stay unchanged after an event is triggered. Leveraging existing record/replay technique, we proposed X-Check, a novel cross-browser testing technique, which supports automated XBIs detection effectively. To improve the efficiency of XBIs detection, this paper further designed an incremental detection algorithm by only checking DOM-mutated and layout-changed nodes. Our empirical evaluation shows that X-Check is effective and efficient. For the selected 21 real-world Web applications, it identifies XBIs with a fairly high precision (83 percent) and recall (93 percent), and improves the performance of XBIs detection about 5.79 times compared to its non-optimized version.

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.

Regression testing is an expensive activity in software development. To speed it up, regression test selection (RTS) is a promising approach by selecting a subset of tests which are affected by code changes. Although there are lots of regression test selection tools, most of them aim to unit tests, require direct code dependency between tests and code under test, and cannot be applied to Web applications to select end-to-end web tests. This paper presents WebRTS, a dynamic RTS tool for regression testing of Web applications. By tracking the process of Http request and object construction in the server, WebRTS can collect accurate test dependencies for each test in isolation, and supports parallel regression testing of distributed Web application. The design of WebRTS is also flexible, and it can be combined with different web testing frameworks. The experimental results show that WebRTS is effective and can be used to select regression tests for Java Web applications. Video: https://youtu.be/OlAsvrX7HXc. Source code: https://gitlab.com/aozeliu18/webrts.

Modern distributed applications are moving toward a microservice architecture, in which each service is developed and managed independently, and new features and updates are delivered continuously. A guiding principle of microservice architecture is that it is vital to anticipate and mitigate a variety of hardware and software failures. In order to test the fault handling capabilities of microservices automatically, this paper presents IntelliFT, a guided resilience testing technique for microservice based applications, which aims to expose the defects in the fault-handling logic effectively within a fixed time limit. The characteristic of IntelliFT is that it leverages existing integration tests of the applications under test to explore the fault space, and decides whether injected faults can lead to severe failures by designing fitness-guided search technique. Our experimental results on a medium-size microservice benchmark system show that the proposed technique is effective, improves the state-of-the-art, and can quickly expose bugs in the recovery logic.

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.

Record-and-replay tools are important for quality assurance of Web applications by capturing user case scenarios and executing them automatically when needed. However, the tests generated by existing techniques are brittle, and often lead to test breakages as the dynamic behavior and frequent updates of modern Web applications. In this paper, we propose WebRR, a self-replay enhanced robust record-and-replay technique for Web applications testing. The novelty of WebRR is that, it introduces a new self-replay mechanism in the recording phase, which checks the captured event from the record module online, and generates multiple locators (including DOM locators, visual locator and proximity locators) automatically, to improve the robustness of generated test cases. During the replay, it combines multiple locators and new local workflow repair technique to repair test breakages, and can improve the resilience of generated tests to frequent updates of the applications. We applied our approach to 3 enterprise Web applications, which are deployed in a large power grid company of China. The experimental results show that WebRR is effective, and substantially improve the robustness of end-to-end web tests that are generated using record-and-replay technique.

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.

Data produced by version control systems are widely used in software research and development. Version control data users always use the name or email address field to identify the committer or author of a modification. However, developers may use multiple names and email addresses, which brings difficulties for identification of distinct developers. In this paper, we sample 450 Git repositories from GitHub to study the multiple names and email addresses of developers. We conduct a conservative estimation of its prevalence and impact on related measurements. We merge the multiple names and email addresses of a developer through a method of high precision. With the merged identities, we obtain a number of interesting findings, e.g., about 6% of the developers used multiple names or email addresses in more than 60% of the repositories, and they contributed about half of all the commits. Our impact analysis shows that the multiple names and email addresses issue cannot be ignored for the basic related measurements, e.g., the number of developers in a repository. Our results could help researchers and practitioners have a more clear understanding of multiple names and email addresses in practice to improve the accuracy of related measurements.

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.

Docker images, having the idea of "build once, run anywhere", are widely used as the reusable delivery artifacts. Currently, there are a huge number of online Docker repositories that provide images as the off-the-shelf blocks to construct large and complicated systems. Tags would improve the reusability as they provide concise semantics. However, tags are not well supported for Docker images, and manual tagging is still exhausting. We propose STAR, a Specialized Tagging Approach for Docker Repositories, to address the problem of automatically multi-labeling the large number of repositories. STAR takes Dockerfiles of the repositories as the primary input, which because a Dockerfile contains all the instructions for building a Docker image. STAR is based on two prediction models. By taking a Dockerfile as the specific text description, we model a repository with its labeled tags and Dockerfile terms, and use Labeled Latent Dirichlet Allocation algorithm to recommend tags. By regarding a Dockerfile as the configuration code, we construct a feature model based on Dockerfile key instructions and use a similarity-based ranking algorithm to recommend tags. Given an untagged repository, STAR outputs two probability scores for each tag with the two models and takes a weighted sum of them as the final score. Finally, STAR ranks all the tags according to their scores and recommends the top K ones. We evaluate STAR on over 100,000 repositories of Docker Hub. The experimental results show that STAR outperforms the state-of-the-art approaches in terms of Recall@5 and Recall@10.

With the advent of Web 2.0 application, and the increasing number of browsers and platforms on which the applications can be executed, cross-browser incompatibilities (XBIs) are becoming a serious problem for organizations to develop web-based software. Although many techniques and tools have been proposed to detect cross-browser issues, there still lacks a comprehensive approach to locate the root causes of various cross-browser issues. To address this limitation, this paper proposes X-Diag, an automated technique for debugging XBIs based on our findings from an extensive study of the root causes of XBIs in real-world applications. The characteristic of X-Diag is that it narrows down the root causes of cross-browser issues step-by-step by checking whether such issues are caused by incompatible DOM APIs, CSS properties or Html elements. Our empirical evaluation shows that X-Diag is effective in locating the root causes of cross-browser issues, and can provide useful support to developers for (eventually) eliminate XBIs.

This paper presents an effective model-based GUI testing technique for Android apps. To avoid local and repetitive exploration, our approach groups equivalent widgets in a state and designs a novel feedback-based exploration strategy, which dynamically adjusts the priority of actions based on the execution result of those already triggered ones, and tends to select actions that can reach news states of apps. We implemented our technique in a tool, called CrawlDroid, and conducted empirical experiments. Our results show that the proposed technique is effective, and covers more code within a fixed testing budget.

In the traditional software development and deployment, the centralized monolithic is always adopted, as the modules are tightly coupled, which caused many inconvenience in software DevOps. The modules with bottlenecks in monolithic application cannot be extend separately as the application is an integral part, and different module cannot use different technology stack. To prolong the lifecycle of the monolithic applications, its need to migrated it to microservice architecture. Due to the complex logic and large number of third party framework libraries depended, get an accurate comprehensive of the application characteristics is challenging. The existing research mostly based on the static characteristics, lack of consideration of the runtime dynamic characteristics, and the completeness and accuracy of the static analysis is inadequate. To resolve above problems, we combined static and dynamic analysis to get static structure and runtime behavior characteristics of monolithic application. We employed the coupling among functions to evaluate the degree of dependence, and through function clustering to achieve the migration of legacy monolithic applications and its data to microservices architecture. Through the empirical study of migrate the typical legacy project to microservices, it is proved that we proposed method can offer precise guidance and assistance in the migration procedure. Experiments show that the method has high accuracy and low performance cost.

It is a big challenge to pick up the best cloud configuration for recurring big data analytics jobs running in clouds. Prior efforts may get in a sub-optimal configuration due to a broad spectrum of cloud configurations with a few test runs, such as CherryPick. We present HW3C which is a heuristic based workload classification and cloud configuration system for big data analytics jobs, our insight is classifying a job by comparing its resource preference and usage informantion with other jobs, and then using heuristic rules to distinguish bad samples from good ones in Bayesian Optimization algorithm. Our experiments on HiBench and SparkBench in Aliyun ECS show that the performance of job had been improved by 53% in average comparing with CherryPick, meanwhile the resource cost had been reduced by 40% in average.

Docker repositories usually contain Docker images and Dockerfiles, where Docker images are a kind of off-the-shelf artifact and Dockerfiles specify how to automatically build Docker images following the notion of Infrastructure-as-Code. Given a huge number of Docker repositories, tag recommendation is essential to ensure that relevant ones can be easily retrieved, because tagging is practical in describing, bookmarking, navigating and searching software objects. However, in Docker Hub, tags are not well supported to semantically describing the repositories, and manually tagging is still an exhausting and time-consuming task.

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.

It is well known that the fragmentation of Android ecosystem has caused severe compatibility issues. Therefore, for Android apps, cross-platform testing (the apps must be tested on a multitude of devices and operating system versions) is particularly important to assure their quality. Although lots of cross-platform testing techniques have been proposed, there are still some limitations: 1) it is time-consuming and error-prone to encode platform-agnostic tests manually, 2) test scripts generated by existing record/replay techniques are brittle and will break when replayed on different platforms, 3) Developers, and even test vendors have not equipped some special Android devices. As a result, apps have not been tested sufficiently, leading to many compatibility issues after releasing. To address these limitations, this paper proposes AppCheck, a crowdsourced testing service for Android apps. To generate tests that will explore different behavior of the app automatically, AppCheck crowdsources event trace collection over the Internet, and various touch events will be captured when real users interact with the app. The collected event traces are then transformed into platform-agnostic test scripts, and directly replayed on the devices of real users. During the replay, various data (e.g., screenshots and layout information) will be extracted to identify compatibility issues. Our empirical evaluation shows that AppCheck is effective and improves the state of the art.

Flash-based Solid State Drive (SSD) is widely used in the virtualization environment, usually as the cache of the hard disk drive-based Virtual Machine (VM) storage, to improve the IO performance. Existing SSD caching schemes are mainly driven by VM-centric metrics. They treat the VMs as independent units and focus on critical low-level performance metrics of individual VMs, such as the working set, the IO latency, or the throughput. However, for elastic Hadoop applications consisting of multiple VMs, the workload is rapidly changing, and the importance of differnet VMs may be different even if they have the same low-level IO pattern. In this situation, the VM-centric SSD caching schemes may not lead to the best performance, i.e., the shortest job completion time. Considering the importance of VMs and relationships among VMs inside the application may potentially better improve the performance, which we regard as the application-centric metrics. We propose the Application-Centric SSD caching for Hadoop applications (ACSSD), which reduces the job completion time from the application level. AC-SSD uses the genetic algorithm based approach to calculate the nearly optimal weights of virtual machines for allocating SSD cache space and controlling the I/O Operations Per Second (IOPS) based on the importance of the VMs. Moreover, AC-SSD introduces the closed-loop adaptation to face the rapidly changing workload. The evaluation shows that AC-SSD reduces the job completion time by up to 39% for IO sensitive workloads, and up to 29% for rapidly changing workloads.

Stream processing system (SPS) faces the problem of node failure when running over a long period of time. In addition, "exactly once" precise semantic guarantee is more and more important for SPS in some scenarios. In general, the approaches to achieve precise semantic is by using global snapshot, which should store state and records to external reliable storage or rely on transactions. However, these approaches suffer from high recovery latency, because of large I/O disk overhead. In order to reduce excessive latency in failure recovery, we save the intermediate results which are produced during the stream processing, and propose an algorithm DCAS which asynchronously snapshots state to implements precise recovery. In addition, we use in-memory distributed cache to provide the storage of intermediate results and snapshots to reduce recovery latency. We evaluate our failure recovery approach in recovery latency and runtime overhead. The experimental results show that our approach is 2 to 6 times faster than other conventional failure recovery approaches, and induces a 6% runtime overhead.

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.

Web application systems, comprising of heterogeneous and loosely coupled components, are usually highly-configurable due to the large number of configuration entries scattering in the components. The dependencies between components lead their entries correlate to one another, which makes the system deployment and migration daunting and error-prone. For two correlated entries, changing value of one entry requires the value change of the other. Otherwise, some implied constraints would be violated and the system failure will occur. Keeping track of entry correlations, which is essential to system reliabilities, is not a simple work as it often crosses products and requires in-depth domain knowledge. This paper proposes a method to automate the process of determining entry correlations. The method first narrows down the exploring scale to those frequently-set entries based on crawled sample data. Then, it generates a correlation score for each entry pair, which is calculated according to entry names, values and inferred types. Thirdly, a set of heuristics are provided to determine a candidate set of the likely correlations. Finally, a rank-ordered list of entry correlations is output so that system administrators can consult it to check system configuration systematically. Based on the method, we implement a tool, Correlation Explorer, and make experiments and evaluations with some real world systems. The result shows that Correlation Explorer is effective in finding a large portion of entry correlations.

With rapidly growing popularity, Location Based Services (LBS), e.g., Google Maps, Yahoo Local, WeChat, FourSquare, etc., started offering web-based search features that resemble a kNN query interface. Specifically, for a user-specified query location q, these websites extract from the objects in their backend database the top-k nearest neighbors to q and return these k objects to the user through the web interface. Here k is often a small value like 50 or 100. For example, McDonald [1] returns the top 25 nearest restaurants for a user-specified location through its locations search webpage.

With the advent of Web 2.0 application, and the increasing number of browsers and platforms on which the applications can be executed, cross-browser incompatibilities (XBIs) are becoming a serious problem for organizations to develop web-based software. Although some techniques and tools have been proposed to identify XBIs, a number of false positives and false negatives still exist as they cannot assure the same execution when the application runs across different browsers. To address this limitation, leveraging existing record/replay technique, we developed X-Check, a novel cross-browser testing technique and tool, which supports automated XBIs detection with high accuracy. Our empirical evaluation shows that X-Check is effective and improves the state of the art.

Big data applications that rely on relational databases gradually expose limitations on scalability and performance. In recent years, Hadoop ecosystem has been widely adopted as an evolving solution. This paper presents the migration of a legacy data analytics application in a provincial data center. The target platform follows "no one size fits all" method. Considering different workloads, data storage is hybrid with distributed file system (HDFS) and distributed NoSQL database. Beyond the architecture re-design, we focus on the problem of data model transformation from relational database to NoSQL database. We propose a query-aware approach to free developers from tedious manual work. The approach generates query-specific views (NoView) for NoSQL and re-structures the views to align with NoSQL's data model. Our results show that the migrated application achieves high scalability and high performance. We believe that our practice provides valuable insights (such as NoSQL data modeling methodology), and the techniques can be easily applied to other similar migrations.

With the advent of Web 2.0 application, and the increasing number of browsers and platforms on which the applications can be executed, cross-browser incompatibilities (XBIs) are becoming a serious problem for organizations to develop web-based software. Although some techniques and tools have been proposed to identify XBIs, they cannot assure the same execution when the application runs across different browsers as only explicit user activity is considered, and thus prone to generating both false positives and false negatives. To address this limitation, this paper describes X-Check, a platform that enables cross-browser testing as a service by leveraging record/replay technique. Comparing to existing techniques and tools, X-Check supports to detect cross-browser issues with high accuracy. It also provides useful support to developers for diagnosis and (eventually) elimination of XBIs. Our empirical evaluation shows that X-Check is effective, improves the state of the art.

Mobile systems usually support an event-based model of concurrent programming. This model, although advantageous to maintain responsive user interfaces, may lead to subtle concurrency errors due to unforeseen threads interleaving coupled with non-deterministic reordering of asynchronous events. These bugs are very difficult to reproduce even by the same user action sequences that trigger them, due to the undetermined schedules of underlying events and threads. In this paper, we proposed RacerDroid, a novel technique that aims to expose concurrency bugs in android applications by actively controlling event schedule and thread interleaving, given the test cases that have potential data races. By exploring the state model of the application constructed dynamically, our technique starts first to generate a test case that has potential data races based on the results obtained from existing static or dynamic race detection technique. Then it reschedules test cases execution by actively controlling event dispatching and thread interleaving to determine whether such potential races really lead to thrown exceptions or assertion violations. Our preliminary experiments show that RacerDroid is effective, and it confirms real data races, while at the same time eliminates false warnings for Android apps found in the wild.

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.

Many websites offering Location Based Services (LBS) provide a$k$NN search interface that returns the top-$k$nearest-neighbor objects (e.g., nearest restaurants) for a given query location. This paper addresses the problem of crawling all objects efficiently from an LBS website, through the public$k$NN web search interface it provides. Specifically, we develop crawling algorithm for 2D and higher-dimensional spaces, respectively, and demonstrate through theoretical analysis that the overhead of our algorithms can be bounded by a function of the number of dimensions and the number of crawled objects, regardless of the underlying distributions of the objects. We also extend the algorithms to leverage scenarios where certain auxiliary information about the underlying data distribution, e.g., the population density of an area which is often positively correlated with the density of LBS objects, is available. Extensive experiments on real-world datasets demonstrate the superiority of our algorithms over the state-of-the-art competitors in the literature.

The large-scale dynamic cloud computing environment has raised great challenges for fault diagnosis in Web applications: First, fluctuating workloads cause traditional application models to change over time; second, modeling the behaviors of complex applications usually requires domain knowledge which is difficult to obtain; third, managing large-scale applications manually is impractical for operators. To address these issues, this paper proposes an automatic fault (F) diagnosis (D) framework for (4) Web applications in cloud (C) computing (FD4C). In this paper, we propose an online incremental clustering method to recognize access behavior patterns. We also use correlation analysis to model the correlations between the workloads and application performance/resource utilization metrics in a specific access behavior pattern. FD4C detects faults by discovering the abrupt changes of correlation coefficients with control charts. Then, FD4C identifies the fault-related metrics using a feature selection method. To evaluate our proposal, we inject typical faults into TPC-W benchmark and apply FD4C to diagnose the injected faults. The experimental results show that FD4C can effectively detect the typical faults and accurately locate the metrics related to the faults.

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

Despite suffering from inefficiency and flexibility limitations, the filter-based routing (FBR) algorithm is widely used in content-based publish/subscribe (pub/sub) systems. To address its limitations, we propose a dynamic destination-based routing algorithm called D-DBR, which decomposes pub/sub into two independent parts: Content-based matching and destination based multicasting. D-DBR exhibits low event matching cost and high efficiency, flexibility, and robustness for event routing in small-scale overlays. To improve its scalability to large-scale overlays, we further extend D-DBR to a new routing algorithm called MERC. MERC divides the overlay into interconnected clusters and applies content-based and destination-based mechanisms to route events inter- and intra-cluster, respectively. We implemented all algorithms in the PADRES pub/sub system. Experimental results show that our algorithms outperform the FBR algorithm.

The large-scale dynamic cloud computing environment has raised great challenges for fault diagnosis in Web applications. First, fluctuating workloads cause traditional application models to change over time. Moreover, modeling the behaviors of complex applications always requires domain knowledge which is difficult to obtain. Finally, managing large-scale applications manually is impractical for operators. This paper addresses these issues and proposes an automatic fault diagnosis method for Web applications in cloud computing. We propose an online incremental clustering method to recognize access behavior patterns, and uses CCA to model the correlation between workloads and the metrics of application performance/resource utilization in a specific access behavior pattern. Our method detects anomalies by discovering the abrupt change of correlation coefficients with a EWMA control chart, and then locates suspicious metrics using a feature selection method combining ReliefF and SVM-RFE. We validate our method by injecting typical faults in TPC-W an industry-standard benchmark, and the experimental results demonstrate that it can effectively detect typical faults.

With the advent of Web 2.0 application, and the increasing number of browsers and platforms on which the applications can be executed, cross-browser incompatibilities (XBIs) are becoming a serious problem for organizations to develop web-based software with good user experience. Although some techniques and tools have been proposed to identify XBIs, some XBIs are still missed as only partial state space is explored (by the crawler) in the testing environment. To address this limitation, based on record/replay technique, this paper proposed a crowdsourcing framework to detect cross-browser issues for Web application deployed in the field. Our empirical evaluation shows that the proposed technique is effective and efficient, improves on the state of the art.

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.

As an exchange foundation of cloud software services, the cloud marketplace plays an important role to promote the capability and creativity of cloud services. However, existing cloud marketplaces are usually based on online stores operated by some particular companies. Users are usually required to get involved in their particular ecosystems, seriously restricting their creativity and competition. Moreover, these marketplaces lack efficient and flexible service publishing and discovery mechanisms. Therefore, this makes them difficult to handle a huge number of dynamic cloud service exchanges efficiently. To address this issue, we propose in this paper an open cloud marketplace middleware system for cloud software services based on a service publishing and subscription model. This model extends traditional content-based distributed publish/subscribe paradigm. By introducing the matching mechanism of multidimensional contents such as service functionality, service behavior, and quality of service etc, a new distributed publish/subscribe paradigm for service publishing and subscription is proposed. This new paradigm allows service providers to publish their services to and allows service consumers to subscribe services from the open marketplace based on service descriptions and requirements. We illustrate the design of the open cloud marketplace and present our preliminary results.

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

Despite suffering from inefficiency and flexibility limitations, the filter-based routing (FBR) algorithm is widely used in content-based publish/subscribe (pub/sub) systems. To address its limitations, we propose a dynamic destination-based routing algorithm called D-DBR, which decomposes pub/sub into two independent parts: Content-based matching and destination-based multicasting. D-DBR exhibits low event matching cost and high efficiency, flexibility, and robustness for event routing in small scale overlays. To boost scalability, we further complement D-DBR with a new routing algorithm called MERC. MERC divides the overlay into interconnected clusters and applies content-based and destination-based mechanisms to route events inter- and intra-cluster, respectively. We implemented all algorithms in the PADRES pub/sub system. Experimental results show that our algorithms outperform FBR in terms of improving event dissemination throughput by up to 700% and reducing the end-to-end latency by up to 55%.

A large number of web data repositories are hidden behind restrictive web interfaces, making it an important challenge to enable data analytics over these hidden web databases. Most existing techniques assume a form-like web interface which consists solely of categorical attributes (or numeric ones that can be discretized). Nonetheless, many real-world web interfaces (of hidden databases) also feature checkbox interfaces-e.g., the specification of a set of desired features, such as A/C, navigation, etc., for a car-search website like Yahoo! Autos. We find that, for the purpose of data analytics, such checkbox-represented attributes differ fundamentally from the categorical/numerical ones that were traditionally studied. In this paper, we address the problem of data analytics over hidden databases with checkbox interfaces. Extensive experiments on both synthetic and real datasets demonstrate the accuracy and efficiency of our proposed algorithms.

As most clouds are based on virtualization technology, more and more virtual machine images are created within data centers. Depending on the need of disaster recovery, the storage space used for backup would easily sprawl to a TB or PB level with the growth of images. Unfortunately, different images have a large amount of same data segments. Those duplicated data segments will lead to serious waste of storage resource. Although there is a lot of work focus on deduplication storage and could achieve a good result in removing duplicate copies, they are not very suitable for virtual machine image deduplication in a cloud environment. Because huge resource usage of deduplication operations could lead to serious performance interference to the hosting virtual machines. This paper propose a local deduplication method which can speed up the operation progress of virtual machine image deduplication and reduce the operation time. The method is based on an improved k-means clustering algorithm, which could classify the metadata of backup image to reduce the search space of index lookup and improve the index lookup performance. Experiments show that our approach is robust and effective. It can significantly reduce the performance interference to hosting virtual machine with an acceptable increase in disk space usage.

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.

Web-based API is a new trend for publishing services. To correctly use the API, developers should follow certain service specifications. Data contract is a service specification to express the constraints over the data model used in the APIs. Data contracts, however are not always readily available in a formalized format if not undocumented at all. In this paper, we present an approach to infer formal data contracts for Web-based API. The approach integrates information of the parameters, error messages and testing result of Web-based API. We demonstrate how this approach infers complicated data preconditions for Web-based API in the real-world Web API platforms.

The rise of software-as-a-service has led to the development of Web 2.0 application. In many cases, the server's functionality is made publicly available as an instance of Web services. However, these services can't be invoked arbitrarily, and some behavior constraints must be obeyed. This paper explores an approach to generate data-centric properties automatically by mining execution logs.

For service-based applications which are composed of multiple independent third-parties, continuous monitoring is required to assure that runtime behavior of the systems complies with specified properties. However, most existing work only detects the violation while not consider how to enforce the properties so that the constraint can not be violated at runtime. To address this limitation, this paper presents EnforceBCL, a framework for enforcing data-centric properties for concurrent service-based applications. Users of EnforceBCL can specify the properties to be enforced using the expressive behavior constraint enforcement language. Data-centric property is enforced at runtime by blocking the process whose next action would violate it. The impacted processes can be unblocked and allowed to execute when the specified property eventually reaches a safe state. EnforceBCL also provides the mechanism to detect possible deadlock during the enforcement of the property, and executes corresponding handler to solve the deadlock. To evaluate the effectiveness and efficiency of the proposed approach, we conducted several experiments. Results show that EnforceBCL is able to effectively enforce data-centric properties for concurrent service-based applications and also incurs less performance overhead.

Developers usually use in-memory data caching system like Hazelcast with the application server to offload the backend database for scaling Internetware. Unfortunately, such caches do not integrate well with the database or the application. Developers need to take a large effort to rewrite the existing data access logic and manually manage the caching data. In this paper, we present EasyCache, a novel data caching approach, which provides transparent cache pre-loading, accessing and consistency maintenance to relieve developers of the burden of cache using and management. First, EasyCache translates each row of data in the existing database table into application cached object to pre-load cache data. Second, EasyCache allows applications to access the data cache using SQL statements and translates them into key/value based cache operations. Finally, EasyCache provides asynchronous/synchronous strategies to persist the cache data changes into the backend database. We design and implement EasyCache as a JDBC driver with Hazelcast as the caching layer. To evaluate our prototype, a detailed set of experiments were performed using the TPC-W benchmark. In the experiments, the only programming effort with EasyCache is point the application to the EasyCache JDBC driver. In contrast, when using Hazelcast as a traditional application-level caching system, we need to modify the TPC-W code over 2000 lines for 15 man days. Our experiments also show that, compared to a system with no cache and with query result cache, using EasyCache leads to up to 692× and 77× performance improvement respectively.

One-sided communication decouples data movement and synchronization by providing support for asynchronous reads and updates of distributed shared data. While such interfaces can be extremely efficient, they also impose challenges in properly performing asynchronous accesses to shared data. This paper presents MC-Checker, a new tool that detects memory consistency errors in MPI one-sided applications. MCChecker first performs online instrumentation and captures relevant dynamic events, such as one-sided communications and load/store operations. MC-Checker then performs analysis to detect memory consistency errors. When found, errors are reported along with useful diagnostic information. Experiments indicate that MC-Checker is effective at detecting and diagnosing memory consistency bugs in MPI one-sided applications, with low overhead, ranging from 24.6% to 71.1%, with an average of 45.2%.

Rule execution is the core step of rule-based semantic web reasoning. However, most existing approaches are centralized, which cannot scale out to reason big semantic web datasets. In this paper, we described a kind of semantic web rule execution mechanism using MapReduce programming model, which not only can handle RDFS and OWL ter Horst semantic rules, but also can be used in SWRL reasoning. Theoretical analysis is present on the scalability of this rule execution mechanism. Result shows that it can scale well as Mapreduce framework.

Virtual machine image encapsulates the whole software stack including operating system, middleware, user application and other software products. Failure occurred in any layer of the software stack will be treated as image failure. However, virtual machine image with potential failures can be convert to template and spread to a wide range by means of template replication. And this paper refer to this phenomenon as "image failure propagation". Usually, patching is a widely adopted solution to resolve software failures. Nevertheless, virtual machine image patches are difficult to deliver to the final users in cloud computing environment for its openness and multi-tenancy features. This paper described image failure propagation model for the first time and proposed a promoting mechanism based on pub/sub computing paradigm to combat with the patching delivery problem.

Map-Reduce is a powerful solution for processing and analyzing large-scale data. Just as Hadoop and Spark are able to deal with terabyte data and even more. Users only need to complete "map" and "reduce" function, the Map-Reduce framework can finish variety jobs. But many machine learning and data mining algorithms cannot leverage the Map-Reduce framework or it would take large efforts to modify the algorithm itself. This issue can be explained by the following ways: 1. Map-Reduce is a batch operation so that most of Map-Reduce frameworks do not built-in to support iteration. 2. Map-Reduce is absolutely parallel, each vertex cannot obtain all records, so none of them could get the global optimal model. In this paper, we proposed a job management tool to enable the Map-Reduce framework to support iteration, called "de-parallel". This make the Map-Reduce framework like Hadoop so that Map-Reduce could run more algorithms and support more various tasks. In addition, our tool does not modify the Map-Reduce framework itself. In face MR-Runner interacts with Map-Reduce framework like a "client", therefore MR-Runner could be deployed in any single PC instead of Map-Reduce cluster. We also abstract the mainly interface related to Map-Reduce frameworks, this makes our tool portable to the representative Map-Reduce frameworks.

Everyone has a characteristic pattern of daily activities. This study applies cluster analysis to identify a computer user's daily behavior patterns based on 1000 China users' 4-weeks software and web usage. Clustering models are built for 4 different behavior definition methods with different time period divisions and feature measurement selections. With these patterns, we build classification models to predict new users' daily behavior pattern with their half day activity logs. For example, if we know one user use computer for entertainment in the morning, we can predict his behavior in the afternoon and evening. The prediction model can be used to recommend suitable items to users according to their current behavior status. Our method can get 92.5% prediction correctness for the best.

As a rising application paradigm, cloud computing enables the resources to be virtualized and shared among applications. In a typical cloud computing scenario, customers, Service Providers (SP), and Platform Providers (PP) are independent participants, and they have their own objectives with different revenues and costs. From PPs' viewpoints, much research work reduced the costs by optimizing VM placement and deciding when and how to perform the VM migrations. However, some work ignored the fact that the balanced use of the multi-dimensional resources can affect overall resource utilization significantly. Furthermore, some work focuses on the selection of the VMs and the target servers without considering how to perform the reconfigurations. In this paper, with a comprehensive consideration of PPs' interests, we propose a framework to improve their profits by maximizing the resource utilization and reducing the reconfiguration costs. Firstly, we use the vector arithmetic to model the objective of balancing the multi-dimensional resources use and propose a VM deployment optimization method to maximize the resource utilization. Then a two-level runtime reconfiguration strategy, including local adjustment and VM parallel migration, is presented to reduce the VM migration and shorten the total migration time. Finally, we conduct some preliminary experiments, and the results show that our framework is effective in maximizing the resource utilization and reducing the costs of the runtime reconfiguration.

Performance isolation is a key requirement for application-level multi-tenant sharing hosting environments. It requires knowledge of the resource consumption of the various tenants. It is of great importance not only to be aware of the resource consumption of a tenant's given kind of transaction mix, but also to be able to be aware of the resource consumption of a given transaction type. However, direct measurement of CPU resource consumption requires instrumentation and incurs overhead. Recently, regression analysis has been applied to indirectly approximate resource consumption, but challenges still remain for cases with non-determinism and multicollinearity. In this work, we adapts Kalman filter to estimate CPU consumptions from easily observed data. We also propose techniques to deal with the non-determinism and the multicollinearity issues. Experimental results show that estimation results are in agreement with the corresponding measurements with acceptable estimation errors, especially with appropriately tuned filter settings taken into account. Experiments also demonstrate the utility of the approach in avoiding performance interference and CPU overloading.

As one database offloading strategy, elastic key-value stores are often introduced to speed up the application performance with dynamic scalability. Since the workload is varied, efficient data migration with minimal impact in service is critical for the issue of elasticity and scalability. However, due to the new virtualization technology, real-time and low-latency requirements, data migration within cloud-based key-value stores has to face new challenges: effects of VM interference, and the need to trade off between the two ingredients of migration cost, namely migration time and performance impact. To fulfill these challenges, in this paper we explore a new approach to optimize the data migration. Explicitly, we build two interference-aware models to predict the migration time and performance impact for each migration action using statistical machine learning, and then create a cost model to strike a balance between the two ingredients. Using the load rebalancing scenario as a case study, we have designed one cost-aware migration algorithm that utilizes the cost model to guide the choice of possible migration actions. Finally, we demonstrate the effectiveness of the approach using Yahoo! Cloud Serving Benchmark (YCSB).

Live data migration is an important technique for key-value stores. However, due to the stateful feature, new virtualization technology, stringent low latency requirements and unexpected workload changes, key-value stores deployed in cloud environment have to face new challenges for data migration: effects of VM interference, and the need to trade off between the two ingredients of migration cost, say migration time and performance impact. To address these challenges, we focus on the data migration problem in a load rebalancing scenario and build a new framework that aims to rebalance load while minimizing migration costs. We build two interference-aware prediction models to predict the migration time and performance impact for each action using statistical machine learning and then create a cost model to strike a right balance between the two ingredients of cost. A cost-aware migration algorithm is designed to utilize the cost model and balance rate to guide the choice of possible migration actions. We demonstrate the effectiveness of the data migration approach as well as the cost model and two prediction models using YCSB.

Detecting anomalies are essential for improving the reliability of enterprise applications. Current approaches set thresholds for metrics or model correlations between metrics, and anomalies are detected when the thresholds are violated or the correlations are broken. However, we have found that the dynamic workload fluctuating over multiple time scales causes system metrics and their correlations to change. Moreover, it is difficult to model various metric correlations in complex applications. This paper addresses these problems and proposes an online anomaly detection approach for enterprise applications. A method is presented for recognizing workload patterns with an incremental clustering algorithm. The Local Outlier Factor (LOF) based on the specific workload pattern is adopted for detecting anomalies. Our approach is evaluated on a testbed running the TPC-W benchmark. The experimental results show that our approach can capture workload fluctuations accurately and detect the typical faults effectively.

The problem of load rebalancing is an important issue for cloud-based key-value stores. However, the new virtualization environment and the store's stateful feature make this classical issue more challenging. In this paper, we build a new load rebalancing framework for cloud-based key-value stores, namely ElastiCat. It can be used for auto reconfiguring the store system with minimal costs and no disruption to the availability of the service. To evaluate and minimize the rebalancing costs, we firstly build two interference-aware prediction models to predict the data migration time and performance impact for each action using statistical machine learning and then create a cost model to strike a right balance between them. A cost-aware rebalancing algorithm is designed to utilize the cost model and balance rate to create a rebalancing plan and guide the choice of possible rebalancing actions. To maintain the availability of storage service, we propose a lightweight piggy-back based data access protocol. Finally, we demonstrate the effectiveness of the framework as well as the cost model using YCSB.

In-memory data grid (IMDG) is a novel data processing middleware for Internetware. It provides higher scalability and performance compared with traditional rational database. However, because the data stored in IMDG must follow the key/value data model, new challenges have been proposed. One important aspect is that IMDG does not support standard data accessing languages such as JPA and SQL, and application developers must design their programs according to the peculiarities of an IMDG product. This results in complex and error-prone code, especially for the programmers who have no deep understanding of IMDG. In this paper, we propose a data accessing reference architecture for IMDG and a methodology to design and implement its data accessing layer. In this methodology, data accessing engine construction, data model designation and join operation supporting are presented. Moreover, following this methodology, we develop and implement a JPA compatible data accessing engine for Hazelcast as a case study, which proves the feasibility of our approach.

Although the market for smartphones is growing rapidly, their utility remains severely limited by the battery life. As such, much research effort has been made to understand the power consumption of the application running on mobile devices. However, dynamic profiling tools need to run on the customized android platform, making them not suitable for ordinary mobile app developers. To address this limitation, this paper proposed a light-weight approach to find possible I/O energy wasting code in Android apps through static program analysis technique. We also provide a case study to evaluate the effectiveness of our approach.

The performance of multi-service applications are known to be determined mainly by the interactions between workload and behaviors of the application. The change of workload can lead to dynamic service demands on system resources, and even cause dynamic bottleneck switches between services inside the application. In this paper, to profiling large-applications' behaviors, and help to locate the bottleneck and optimize their capacities, we focus on modeling their behavior according to the workload. Although this topic has been well studied at testing stage, building such a model under live workload remains a challenge, because the workload and application behaviors are time-varying. To tackle this problem, we propose an adaptive approach to build and rebuild performance model according to log files. Both the user behaviors and their corresponding internal service relations are modeled, and the CPU time consumed by each service is also obtained through Kalman filter, which can "absorb" some level of noise in real-world data. Our model can explain the behaviors of both the whole application and the individual services, and provide valuable information for capacity planning and bottleneck detection. At last, our work is evaluated with TPC-W bench mark, whose results can demonstrate the effectiveness of our approach.

Cloud computing provide scalability and high availability for web applications using such techniques as distributed caching and clustering. As one database offloading strategy, elastic caching platforms (ECPs) are introduced to speed up the performance or handle application state management with fault tolerance. Several cache strategies for ECPs have been proposed, say replicated strategy, partitioned strategy and near strategy. We first evaluate the impact of the three cache strategies using the TPC-W benchmark and find that there is no single cache strategy suitable for all conditions, the selection of the best strategy is related with workload patterns, cluster size and the number of concurrent users. This raises the question of when and how the cache strategy should be reconfigured as the condition varies which has received comparatively less attention. In this paper, we present a machine learning based approach to solving this problem. The key features of the approach are off-line training coupled with on-line system monitoring and robust synchronization process after triggering a reconfiguration, at the same time the performance model is periodically updated. More explicitly, first a rule set used to identify which cache strategy is optimal under the current condition are trained with the system statistics and performance results. We then introduce a framework to switch the cache strategy on-line as the workload varies and keep its overhead to acceptable levels. Finally, we illustrate the advantages of this approach by carrying out a set of experiments.

Middleware sharing is one of the important resource sharing approaches which enables sharing of costs across a large pool of users. However, the shared Java middleware server easily causes interference on performance between concurrent user requests. A key requirement to an effective performance isolation is the knowledge of the resource consumption of the various kinds of use requests classified according to different application context information. Direct measurement of resource consumption requires instrumentation which is impractical. In this paper, we demonstrate that CPU consumptions of various kinds of user requests on a given hardware can be approximated by a proposed Kalman filter based approach. Experimental results derived from testing the approach by using the TPC-W e-commerce suite deployed on a widely-used Java middleware server (Tomcat) illustrate the potential of this approach.

Runtime monitoring of Web service compositions has been widely acknowledged as a significant approach to understand and guarantee the quality of services. However, existing runtime monitoring solutions consider only the constraints on the sequence of messages exchanged between partner services and ignore the actual data contents inside the messages. As a result, it is difficult to monitor some dynamic properties such as how message data of interest is processed between different participants. To address this issue, we propose an efficient, non-intrusive online monitoring approach to dynamically analyze data-centric properties for service-oriented applications involving multiple participants. By introducing Par-BCL - a Parametric Behavior Constraint Language for web services - to define monitoring parameters, various data-centric temporal behavior properties for Web services can be specified and monitored. This approach broadens the monitored patterns to include not only message exchange orders, but also the data contents bound to the parameters. To reduce runtime overhead, we statically analyze the monitored properties to generate parameter state machine from the event pattern automata to optimize monitoring. The experiments show that our solution is efficient and promising.

Abstract With the drastic development of semantic‐driven applications, assessing the quality of ontologies has received more attention. Measuring and assessing the quality of ontologies can help ontology engineers to control project management and reduce the risk of project failures. However, most of the existing ontology metrics for measuring and assessing the quality of ontologies are defined based on ontology structure, and neglect the stability of ontology measurement. In this paper, we concentrate on stable ontology measurement by using semantically derived ontology metrics. We propose four ontology cohesion metrics, which fully consider the implicitly expressed semantic information and are defined based on ontological semantics rather than ontology structure. Before measuring and assessing an ontology, we materialize a pre‐processing for stable ontology measurement by treating the ontology. The proposed ontology cohesion metrics are theoretically validated by the validation criteria of object‐oriented software. The experimental results show that we can successfully collect more semantic knowledge from the testing ontologies for stable ontology measurement by using the proposed ontology cohesion metrics. The ontology cohesion metrics proposed in this paper can be reasonably used as a cogent complementarity of existing ontology metrics. Copyright © 2010 John Wiley & Sons, Ltd.

The efficiency of subscription subsumption checking remains a key issue for content-based publish/subscribe systems. In this paper, we propose an efficient data structure called subscription subsumption graph (SSG). This data structure could differentiate the two types of subsumption relationships and help speed up the process of subsumption checking and subscription cancellation. We then present a two-phase approach to subscription subsumption checking. Phase one is mainly about checking of non-numeric constraints by using an index structure which could help filter out most of irrelevant subscriptions while phase two is about checking of remaining numeric constraints where SSG is employed. Finally, we introduce an efficient SSG-based unsubscription algorithm that could find out which subscriptions need to be forwarded without any redundant computing. We illustrate the advantages of this approach by carrying out extensive experiments.

Runtime monitoring of Web service compositions with WS-BPEL has been widely acknowledged as a significant approach to understand and guarantee the quality of services. However, most existing monitoring technologies only track patterns related to the execution of an individual process. As a result, the possible inconsistency failure caused by implicit interactions among concurrent process instances cannot be detected. To address this issue, this paper proposes an approach to specify the behavior properties related to shared resources for web service compositions and verify their consistency with the aid of a parametric stateful aspect extension to WS-BPEL. Parameters are introduced in pattern specification, which allows monitoring not only events but also their values bound to the parameters at runtime to keep track of data flow among concurrent process instances. An efficient implementation is also provided to reduce the runtime overhead of monitoring and event observation. Our experiments show that the proposed approach is promising.

Recent pervasive systems are designed to be context-aware so that they are able to adapt to continual changes of their environments. Rule-based adaptation, which is commonly adopted by these applications, introduces new challenges in software design and verification. Recent research results have identified some faulty or unwanted adaptations caused by factors such as asynchronous context updating, and missing or faulty context reading. In addition, adaptation rules based on simple event models and propositional logic are not expressive enough to address these factors and to satisfy users' expectation in the design. We tackle these challenges at design stage by introducing sequential event patterns in adaptation rules to eliminate faulty and unwanted adaptations with features provided in the event pattern query language. We illustrate our approach using the recent published examples of adaptive applications, and show that it is promising on designing more reliable context-aware adaptive applications.

With the great success of internet technology, internetware has become one of the most important software paradigms. But the open, dynamic and uncertain network makes it difficult to guarantee the performance of internetwares. Feed forward control method has been proved to be an effective mechanism for performance guarantee in advance, but it is difficult to work well in such a dynamic environment, in which performance aspects are highly changeable because for the load fluctuation and software updates. In this paper, we proposed an adaptive performance modeling approach to adapt the environment and provide fine-grained performance guarantee. In our approach, the service invocation sequences corresponding to the load of internetware are constructed adaptively. And the service time of each service, which is the most performance parameter of our performance tool, is accurately acquired through Kalman filter.

Mashup tools allow end users graphically build complex mashups using pipes to connect web data sources into a data flow. Because end users are of poor technical expertise, the designed data flows may be inefficient. This paper targets on enhancing the performance of mashups via automatically refactoring the structure of its data flows. First a set of operational semantics features are selected for annotating the operators in data flows and refactoring rules are defined to generate all candidate semantics equivalent data flows. Then a heuristic algorithm is described for accurately searching the data flow of minimal execution time by constructing a partially ordered set of data flows based on their cost estimation. This approach is applicable to general mashup data flows without knowing complete operational semantics of their operators and the efficiency improvement is demonstrated by experiments.

PaaS (Platform-as-a-Service) which provides execution environment for applications deployed in cloud is a key technology of cloud computing. However, to meet various requirements of different users on software platform under changing application environment, it's crucial to design and develop extensible, customizable and dynamic PaaS systems. In this paper, we analyze the software requirements of PaaS. Then a PaaS system architecture using R-OSGi as software foundation is designed. Finally, the presented approach is validated by a case study involving a web-based application E-bookstore.

The advent of Internet technology introduces a revolution to software application and development paradigms. Traditional software development and application patterns have been shifted to Internet-based service sharing and collaboration among partners all over the Internet. This imposes new challenges and complexity in the lifecycle of software development, deployment and maintenance. Middleware, an intermediate layer to abstract the homogeneity and hide the difference of underlying systems, can be used to reduce the complexity for Internet application development. In this paper, we exploit the needs of middleware support for Internet-based applications from a service perspective. We investigate the potential requirements and features of Internetware, and the state-of-the-art solutions. We also analyze the remaining issues, the challenges and potential future research directions.

In service-oriented system, by using service selection methods, service entities can be dynamically bound to abstract services. Major of current system have assumed that candidate services are independent of each other. However, recent research has discovered that services do have correlations which will impact Quality-of-Service (QoS) of the composition service [9]. This paper outlines the service-correlation-aware service selection approach, gives a detailed system design, and implements it as an Eclipse plug-in and integrates it into a composite service development environment. To demonstrate the practical utilization of this approach, we employ it to development of a travel agency system. The exploitation further validate that this solution can be applied to a large extent.

Model-based performance prediction is a promising cost effective approach to analyze performance of software in early development stages. The key of this approach is to build a performance model suitably coupled with the software artifacts. But this approach is very difficult to be employed in middleware based applications because middleware bring lots of expense to the system performance. Building a performance model directly including details of middleware is somewhat impractical for these details are far from clear to application designers. This paper describes a performance impacts separation framework which separates an application into isolate aspects. Designers only need to care about the application level model design, our framework will automatically compose each aspect together to form a complete model, using an extended aspect-oriented modeling (AOM) technologies. This AOM method is designed particularly for middleware based system designs. A case study has been presented to illustrate that our framework can deal with different deployment scenarios of middleware based application easily.

To achieve self-healing web services composition, much work has been studied in the area of web services composition recently. However, most work addresses the problem of runtime monitoring, diagnosis and recovery in isolation. What is missing, however, is a unified solution that can be used to tackle this challenge in a principled manner. This paper presents a fresh view on self-healing web services composition. In particular, rather than building baseline system model a priori, we advocate using statistical learning theory(SLT) technique to extract it by observing the behavior of web services composition and locate the potential anomaly.

In context-ware computing paradigm, context-aware middleware plays a key role. The middleware collects and manipulates contexts from environments, providing context-aware applications well-defined interfaces to adapt their behaviors when environments change. However, some minor difference in the implementation of context-aware middleware may cause the same context-aware application behave differently. Such behavior deviation may lead to serious problems or even disasters for a context-aware application. It is thus desirable to check whether a mobile context-aware application behaves consistently before moving it from one middleware to another, or whether a context-aware application still works correctly when upgrading the underlying middleware? Existing approaches for context-aware applications are not adequate for detecting such behavior deviation because these approaches do not consider the impacts of the difference in the middleware implementation. In this paper, we study the strategies in the implementation of context-aware middleware and their impacts on the behavior of context-aware applications. By exploring the implied scenarios where a context-aware application may behave differently, new testing approach is proposed to detect the behavior deviation of a context-aware application running on different middleware by generating test cases to cover these implied scenarios.

To ensure the relaxed atomicity of transactional composite service (TCS), a lot of relaxed atomicity models have been proposed, but they don't handle the concurrency control problem specific to their relaxed atomicity model, which can leads to unexpected results when multiple TCS run concurrently. In this paper, we propose a novel concurrency control mechanism to support the user-defined relaxed atomicity model for service composition. Based on the analysis of the two typical kinds of inconsistency caused by cascade compensation and cycle dependency, concurrency control mechanism to confine the forming and changing of dependency is presented, which can eliminate the inconsistencies while maintaining the relaxed atomicity of individual TCS.

The execution of composite web services with WS-BPEL relies on externally autonomous Web services. This implies the need to constantly monitor the running behavior of the involved parties. Moreover, monitoring the execution of such processes is critical to enforce business policies and meet reliability goals. This paper proposes a stateful aspect extension to WS-BPEL, as a solution to support flexible behavior pattern monitoring for composite Web services. Specifically, in the stateful aspect, history-based pointcut specifies the pattern of interest within a range, while advice describes the associated action to manage the process if the specified pattern occurs. We also present its implementation based on finite state automata through runtime weaving mechanism. Our experiments indicate the proposed monitoring approach incurs minimal overhead.

With the increasing number of Web Services with similar or identical functionality, the non-functional properties of a Web Service will become more and more important. Hence, a choice needs to be made to determine which services are to participate in a given composite service. In general, multi-QoS constrained Web Services composition, with or without optimization, is a NP-complete problem on computational complexity that cannot be exactly solved in polynomial time. A lot of heuristics and approximation algorithms with polynomial- and pseudo-polynomial-time complexities have been designed to deal with this problem. However, these approaches suffer from excessive computational complexities that cannot be used for service composition in runtime. In this paper, we propose a efficient approach for multi-QoS constrained Web Services selection. Firstly, a user preference model was proposed to collect the user's preference. And then, a correlation model of candidate services are established in order to reduce the search space. Based on these two model, a heuristic algorithm is then proposed to find a feasible solution for multi-QoS constrained Web Services selection with high performance and high precision. The experimental results show that the proposed approach can achieve the expecting goal.

Currently, the significance of a portal stems not only from being a handy way to access data but also from being the means of facilitating the integration with Web applications. This paper proposes an interaction instance oriented approach for integrating web applications in portals. The key aspect is to enable a user to have the same interaction experiences from a portal that he/she accesses the web application directly. The approach is thus focused on the description of the presentation layer of the interaction instances of a web application and a portlet, which defines an interaction instance as consecutive web pages or fragments. Web application integration is then transformed to the problem that how to translate all web pages of an interaction instance of a Web application to certain view equivalence regions, which form the interaction instance of a portlet. Experiments show that the approach is effective and efficient.

The paradigmatic shift from function-oriented Web services to interactive Web services(IWSs) addresses lots of issues such as repetitious development for user interface and tiresome understanding of underlying service operations. However, the composition of existing IWSs to create value-added ones is still a prominent problem. Considering the special interactive characteristics of IWSs, current approaches to compose function-oriented services are inappropriate. This paper proposes a novel user satisfaction model to evaluate the interactive quality of a composite IWS completely. Based on the satisfaction model, an effective satisfaction-driven approach is also developed for service selection in IWSs composition, which can meet diverse interactive requirements of users.

Overload management is of vital importance in wide-area publish/subscribe systems, yet current solutions are best-effort. In this paper, we present an admission control scheme for overload management in large-scale and scalable content-based publish/subscribe systems. We analyze the stumbling block for implementing admission control in publish/subscribe systems, and point out how it differs from admission control schemes in other research areas. We propose a cover relation based algorithm to compute subscription resource requirements and an admission control algorithm based on subscription routing. The scheme ensures time, space and flows decoupling without sacrificing scalability of publish/subscribe systems. Finally, we conduct experiments to verify the effectiveness of the scheme.

End-to-end reliability is an important issue in building large-scale distributed enterprise applications based on multi-tier architecture, but the support of reliability as adopted in conventional replication or transactions mechanisms is not enough due to their distinct objectives - replication guarantees the liveness of computational operations by using forward error recovery, while transactions guarantee the safety of application data by using backward error recovery. Combining the two mechanisms for stronger reliability is a challenging task Current solutions, however, are typically on the assumption of simple transaction pattern where a request from a single client executes in the context of exactly one transaction at the middle-tier application server, and seldom think about some complex patterns, such as client transaction enclosing multiple client requests or nested transactions. In this paper, we first identify four transaction pattern classes, and then propose a fault-tolerant scheme that can uniformly provide exactly-once semantic reliability support for these patterns. In this scheme, application servers are passively replicated to endow business logics with high reliability and high availability. In addition, by replicating transaction coordinator, the blocking problem of 2PC protocol during distributed transactions processing is eliminated. We have implemented this approach and integrated it into our own J2EE application server, OnceAS. Also, its effectiveness is discussed in different transaction patterns and the corresponding performance is evaluated

Web services, with an emphasis on open standards and flexibility, can provide benefits over existing capital markets integration practices. However, Web services must first meet certain technical requirements including performance, security and so on. SOAP, based on Extensible Markup Language (XML), inherits not only the advantages of XML, but its relatively poor performance. This makes SOAP a poor choice for many high-performance Web services. In this paper, we propose a new approach to improve Web services performance. Focusing on avoiding traditional XML parsing and Java reflection at runtime, we create a service-specific SOAP processor to accelerate execution. Through our experiments in this paper, we observed that our approach obtained about a treble performance gain (maximum) by incorporating the SOAP processor into the SOAP engine

Traditional Web services are function oriented, where various developed standards mainly assist business applications to expose their functional descriptions, but each service consumer is required to develop different presentation logics for the same business logic respectively. Although works on the interactive Web service (IWS) make some progress and achieve the result of WSRP, researchers keep on making efforts to encapsulate user interface with the functional interface so as to present available information of content and facilitate the direct interactions between users and back-end services. Regarding IWS this paradigm of Web services, service selection shifts focus from function orientation to presentation orientation. This paper proposes a novel IWS description model with the extension of an element-view and its three sub-elements including presentation, content and interaction, with which IWS can be described more completely and accurately. Based on the description model, an IWS selection model with matching rules is developed, which can meet diverse selection requirements of service consumers at multiple levels and aspects

Security is playing an increasingly important role in nowadays business. However, at present there isn't an effective method to secure SOAP attachments. This paper proposes a novel security model for SOAP attachments, which encrypts the attachments and provides digital signature without changing client's and server's implementations. In the multi-intermediaries scenario, the whole message is divided into two parts and sent respectively: the primary part goes through as the original message path via intermediaries, while the attachments are sent directly from client to server via no intermediary. Therefore, it improves the efficiency of services and reduces the probability of the attachments' being attacked. A prototype of this security model is implemented on the Web application server and the experiment results show the feasibility of secure attachments in enterprise applications

The multi-tier architecture of J2EE provides good modularity and scalability by partitioning an application into several tiers, and becomes the mainstream for distributed applications development on Internet/Intranet. Current reliability solutions in this architecture are typically dependent on either replication, which provides at-least-once guarantee, or transaction processing, which guarantees at-most-once semantics. In practice, the end-to-end reliability guarantee of exactly-once semantics is necessary, especially for some complex transaction scenarios, such as client transaction or nested transaction. In this paper, we describe a fault-tolerant algorithm that can provide this enhanced reliability support through combining replication and transaction processing. We use passive replication to protect business processing at middle-tier application server. A client stub transparently intercepts client request and automatically resubmits it in the case of failure. In addition, transaction coordinator is passively replicated to prevent the blocking problem of distributed transaction. Also, different application scenarios are discussed to illustrate the effectiveness of this algorithm, and a performance study based on our implementation in J2EE application server, OnceAS, shows the overhead of it is acceptable

In this paper we propose a declarative method for modeling the performance impact of container middleware to component-based system. The method abstracts the major performance impact factors, and these factors are modeled as sub-models by using UML activity diagram with UML profile for schedulability, performance and time annotations. Through a model assembly descriptor file associated with specific component application, the model assembling algorithm proposed in this paper can automatically composite the performance impacting factors into component application UML model. The declarative method helps to realize the separation of concerns between component application performance modeling and middleware impact. Using a case study, we validate proposed method

Web services are considered as solution for solving the interoperability problem and the challenge of integration. How to manage Web services more efficiently is a key problem to the applications based on Web services at present. This paper presents a framework for application server based Web services management named FASWSM. The main contribution of FASWSM is Web service adaptation, so that a Web service can be plugged into the application server (AS) as a Web service adapter which enables a Web service to be managed by the application server. Therefore, the Web services management efforts are greatly reduced by leveraging various services provided by the AS. The FASWSM also provides mechanisms for dynamical reconfiguration which improve the extensibility and flexibility of Web services management. The FASWSM has been applied to OnceAS 2.0 application server, and the experiments data show that FASWSM outperforms JAX-RPC in terms of Web service invocation.

As a basic reliability guarantee technology in distributed systems, failure detection provides the ability of timely detecting the liveliness of runtime systems. Effective failure detection is very important to J2EE application server (JAS), the leading middleware in Web computing environment, and it also needs to meet the requirements of reconfiguration, flexibility and adaptability. Based on the QoS (quality of service) specification of failure detector, this paper presents a QoS-enable failure detection framework for JAS, which satisfies the requirements of dynamically adjusting qualities and flexible integration of failure detectors. The work has been implemented in OnceAS application server that is developed by Institute of Software, Chinese Academy of Sciences. The experiments show that the framework can provide good QoS of failure detection in JAS.

As we have been gaining more experiences in services provision, online services are becoming increasingly complex. They have moved from simple service provision and invocation to very sophisticated service interaction and cooperation. As presented in this paper, service cooperation will be a promising computation model to achieve overall goals beyond individual capabilities. Based on the supreme wide spread of service-oriented development (SODA), the process-oriented platform (POP), with favourable flexibility derived from late binding, will be the optimum approach to this end. The PI production developed by us is such a system implementation, in which architecture, components, and functionalities are also introduced in detail. We believe that the service cooperation paradigm is a hopeful solution to future service evolution, and the PI system will be an instructive explorer to reach this new horizon

As the Internet environment becomes more and more dynamic, open and mutable, future software have to be more autonomic, reactive, adaptive, cooperative, and evolvable. To meet the need, we introduce emerging service cooperation middleware providing such infrastructure support. Derived from Chinese ancient five-elements ideology, a similar service cooperation philosophy is developed. Complying the idea, we develop a workflow system, PI, supporting Process Intelligence. We believe that the service cooperation will become a feasible solution to the future complex environment.

Advancing information technologies are increasing the evolution and variation of software resources. Applications that cannot adapt to dynamic environments will decrease their usefulness, particularly to business process systems that face requirements changed frequently. After surveying related work, we propose a new formalism for modeling dynamic process in which the state space and transition function are enriched so that one model can transit to another model at runtime by the computational reflection that aims to represent and modify its own design. Such goal necessitates an appropriate runtime environment. We introduce the service cooperation middleware (SCM) because it is service-oriented, into which the reflection mechanism is easily attached to support structural and behavioural changes on processes at runtime.

A transactional workflow is composed of traditional flat transactions, and its execution has relaxed transactional atomicity. Due to different termination characteristics of transactions, a transactional workflow may be not well-formed. Moreover, only one workflow is allowed to execute a non-compensatable transaction with the current scheduling protocol. We present a transactional workflow model and formally define the correctness criteria of transactional workflow structure (well-formedness) and execution (serializability). We then propose an efficient method for well-formedness validation through a set of computation rules. Finally a scheduling protocol based on two kinds of locking granularities is presented. The protocol is different from related research in the fine-grained locking on transaction instances and coarse-grained locking on transaction classes, multiple workflows are therefore allowed to execute non-compensatable transactions if they are not conflict in a predicated future execution.

While e-commerce continuously grows prosperous, some advantages e-commerce applications claimed haven't really been gained. More seriously, the availability and reliability of these systems are particularly hard to obtain. The e-commerce protocols, as the core of e-commerce applications, ask for new development approach and techniques to be introduced for their highly reliable and safe design and implementation. This paper describes research on synthesis of extended UML formalism and formal verification techniques for automatic development of e-commerce protocols. In this paper, we refine AUML protocol diagrams for visual modeling, and develop algorithm and rules to translate visually modeled e-commerce protocols into formal models that are then validated using model checking. This approach is applied to the design of an e-commerce protocol, NetBill, as example. Our objective is to create tools that enable designers to automatically develop available and reliable e-commerce protocols.

Recent advances in wireless and mobile networks have led to the exponential growth of mobile applications. Unlike conventional computing, mobile computing has stringent constraints in network resources, such as bandwidth and connectivity. As such, data in mobile applications are often cached at clients to increase performance, data availability and reliability. Formal verification of cache coherence in data access is essential in ascertaining the validity of a cache coherence protocol. Although a number of studies have been made in this subject, few researchers focused on mobile data access. In this paper, we present an automatic approach towards formal validation of a cache validation protocol supporting mobile data access. This approach combines the flexibility of visual modeling techniques with the rigor of formal validation. As it is difficult to construct the formal model of protocol, we have developed a set of formalization and translation rules to automate the process of construction. The reliability of the protocol has been verified using model checking.