Static analysis has profoundly improved software quality over the past decades, evolving from compiler-integrated optimizations and simple linting to sophisticated analyses for bug detection, security, and program understanding. In contrast, static analysis for hardware remains underexploited, resembling the early state of software analysis. Most existing hardware static analyses are confined to compiler optimizations and linting, lacking the sophistication needed to uncover complex design flaws. Furthermore, we observe that many hardware bugs reported in recent literature could have been identified by sophisticated static analyses that account for hardware-specific semantics and data flow; however, such bug detection analyses are absent today. To exploit the untapped potential of sophisticated hardware analysis, we present a series of bug detection analyses for Verilog, the predominant hardware description language (HDL). Moreover, these analyses are built upon our fundamental analyses that capture essential hardware-specific characteristics---such as bit-vector arithmetic, register synchronization, and digital component concurrency---and enable the examination of hardware data and control flows. Together, these analyses form a well-organized analysis suite with a modular design, in which diverse fundamental analyses combine to support bug detection, hardware understanding, and other potential clients. To implement these analyses, we further offer dedicated infrastructure, including a Verilog front end, an intermediate representation (IR) for analysis, and an analysis manager. To validate the utility of our analyses, we applied them to real-world hardware projects. Unlike software, real-world hardware projects tend to contain fewer but harder-to-detect bugs, as they typically undergo extensive simulation and rigorous verification to prevent the prohibitive costs of hardware defects. Despite this, our preliminary experimental results are highly promising: applying these proposed analyses to popular real-world Verilog projects (averaging 1.5K+ GitHub stars) uncovered nine previously unknown bugs, all confirmed by developers; moreover, we successfully identified a total of 18 bugs beyond the capabilities of existing static analyses for Verilog bug detection (i.e., linters). These results underscore the transformative potential of sophisticated static analysis in hardware design. Our analysis suite and infrastructure are also highly reusable: on average, each bug-detection client built on our analysis suite requires about 270 LoC, compared to 5,700 LoC when developed from scratch. By open-sourcing the entire system, involving substantial engineering effort (100K+ LoC), we aim to encourage further innovation and applications of sophisticated static analysis for hardware, hopefully fostering a similarly vibrant ecosystem that software analysis enjoys.

The landscape of Verilog toolchains for electronic design automation (EDA) is diverse, and their reliability is crucial, as errors can lead to significant debugging challenges and delays in development. Methodologies such as testing and formal verification have been applied to identify and eliminate defects in these toolchains. We propose a framework named VeriXmith to interconnect design tools involved in logical synthesis and simulation for cross-checking. These tools process circuit designs and produce outputs in different languages, such as Verilog netlists from synthesizers and C++ programs from simulators. Since these outputs represent the same circuit semantics, we can leverage this semantic consistency to verify the tools that translate one representation into another. Our approach involves creating semantics extractors to extend the range of circuit representations available for semantic equivalence checking by converting them into a canonical and comparable form. Additionally, we develop mutation operators for Verilog designs to introduce new data/control paths and language constructs, enhancing the diversity of circuit designs as test inputs. By validating semantic equivalence, our framework successfully identifies defects in existing Verilog toolchains. An exploratory experiment uncovers 31 previously unknown bugs in well-known open-source Verilog tools, including Verilator and Yosys.

Regression errors of Deep Neural Network (DNN) models refer to the case that predictions were correct by the old-version model but wrong by the new-version model. They frequently occur when upgrading DNN models in production systems, causing disproportionate user experience degradation. In this paper, we propose a lightweight regression error reduction approach with two goals: 1) requiring no model retraining and even data, and 2) not sacrificing the accuracy. The proposed approach is built upon the key insight rooted in the unmanaged model uncertainty, which is intrinsic to DNN models, but has not been thoroughly explored especially in the context of quality assurance of DNN models. Specifically, we propose a simple yet effective ensemble strategy that estimates and aligns the two models' uncertainty. We show that a Pareto improvement that reduces the regression errors without compromising the overall accuracy can be guaranteed in theory and largely achieved in practice. Comprehensive experiments with various representative models and datasets confirm that our approaches significantly outperform the state-of-the-art alternatives.

Neuro-symbolic systems combine the abilities of neural perception and logical reasoning. However, end-to-end learning of neuro-symbolic systems is still an unsolved challenge. This paper proposes a natural framework that fuses neural network training, symbol grounding, and logical constraint synthesis into a coherent and efficient end-to-end learning process. The capability of this framework comes from the improved interactions between the neural and the symbolic parts of the system in both the training and inference stages. Technically, to bridge the gap between the continuous neural network and the discrete logical constraint, we introduce a difference-of-convex programming technique to relax the logical constraints while maintaining their precision. We also employ cardinality constraints as the language for logical constraint learning and incorporate a trust region method to avoid the degeneracy of logical constraint in learning. Both theoretical analyses and empirical evaluations substantiate the effectiveness of the proposed framework.

Greetings and welcome to the third issue of IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS (TCSS) for 2023. The authors are delighted to share some exciting news with our esteemed readership.

Non-crashing functional bugs of Android apps can seriously affect user experience. Often buried in rare program paths, such bugs are difficult to detect but lead to severe consequences. Unfortunately, very few automatic functional bug oracles for Android apps exist, and they are all specific to limited types of bugs. In this paper, we introduce a novel technique named deep-state differential analysis, which brings the classical "bugs as deviant behaviors" oracle to Android apps as a generic automatic test oracle. Our oracle utilizes the observations on the execution of automatically generated test inputs that (1) there can be a large number of traces reaching internal app states with similar GUI layouts, and only a small portion of them would reach an erroneous app state, and (2) when performing the same sequence of actions on similar GUI layouts, the outcomes will be limited. Therefore, for each set of test inputs terminating at similar GUI layouts, we manifest comparable app behaviors by appending the same events to these inputs, cluster the manifested behaviors, and identify minorities as possible anomalies. We also calibrate the distribution of these test inputs by a novel input calibration procedure, to ensure the distribution of these test inputs is balanced with rare bug occurrences.

Learning node representations in a network has a wide range of applications. Most of the existing work focuses on improving the performance of the learned node representations by designing advanced network embedding models. In contrast to these work, this article aims to provide some understanding of the rationale behind the existing network embedding models, e.g.,whya given embedding algorithm outputs the specific node representations andhowthe resulting node representations relate to the structure of the input network. In particular, we propose to discern the edge influence for two widely-studied classes of network embedding models, i.e., skip-gram based models and graph neural networks. We provide algorithms to effectively and efficiently quantify the edge influence on node representations, and further identify high-influential edges by exploiting the linkage between edge influence and network structure. Experimental evaluations are conducted on real datasets showing that: 1) in terms of quantifying edge influence, the proposed method is significantly faster (up to$2,000\times$) than straightforward methods with little quality loss, and 2) in terms of identifying high-influential edges, the identified edges by the proposed method have a significant impact in the context of downstream prediction task and adversarial attacking.

Attributed network embedding aims to learn low dimensional node representations by combining both the network's topological structure and node attributes. Most of the existing methods either propagate the attributes over the network structure or learn the node representations by an encoder-decoder framework. However, propagation based methods tend to prefer network structure to node attributes, whereas encoder-decoder methods tend to ignore the longer connections beyond the immediate neighbors. In order to address these limitations while enjoying the best of the two worlds, we design cross fusion layers for unsupervised attributed network embedding. Specifically, we first construct two separate views to handle network structure and node attributes, and then design cross fusion layers to allow flexible information exchange and integration between the two views. The key design goals of the cross fusion layers are three-fold: 1) allowing critical information to be propagated along the network structure, 2) encoding the heterogeneity in the local neighborhood of each node during propagation, and 3) incorporating an additional node attribute channel so that the attribute information will not be overshadowed by the structure view. Extensive experiments on three datasets and three downstream tasks demonstrate the effectiveness of the proposed method.

Recovering missing values in time series is critical when performing time series analysis. And the blackouts issue studied in this paper, described as losing all the data during a certain period, is among the most urgent issues due to its devastating impact on service quality, and is challenging because of the absence of coevolving data sequences for reference. As a result, many existing approaches that rely on data from other coevolving sequences for missing value recovery are infeasible in handling blackouts. To address the issue, this work proposes a novel Hankel matrix factorization approach, HKMF-T, to recover missing values during blackouts for tagged time series, where a tagged time series consists of a data sequence and a corresponding tag sequence. Motivated by real-world observations, HKMF-T decomposes the data sequence into two components: 1) an internal, slowly-varying smooth trend, and 2) external impacts indicated by the tag sequence. By transforming a partially observed data sequence into a corresponding Hankel matrix, we learn the above two components and estimate the missing values under a unified framework of Hankel matrix factorization. Extensive experiments are conducted to evaluate the practical performance of HKMF-T on real-world data sets. And the results suggest HKMF-T outperforms the baseline approaches for blackouts with long durations.

Although it has been commercially successful to deploy weakly consistent but highly-responsive distributed datastores, the tension between developing complex applications and obtaining only weak consistency guarantees becomes more and more severe. The almost strong consistency tradeoff aims at achieving both strong consistency and low latency in the common case. In distributed storage systems, we investigate the generic notion of almost strong consistency in terms of designing fast read algorithms while guaranteeing Probabilistic Atomicity with well-Bounded staleness (PAB). This problem has been explored in the case where only one client can write the data. However, the more general case where multiple clients can write the data has not been studied. In this article, we study the fast read algorithm for PAB in the multi-writer case. We show the bound of data staleness and the probability of atomicity violation by decomposing inconsistent reads into the read inversion and the write inversion patterns. We implement the fast read algorithm and evaluate the consistency-latency tradeoffs based on the instrumentation of Cassandra and the YCSB benchmark framework. The theoretical analysis and the experimental evaluations show that our fast read algorithm guarantees PAB, even when faced with dynamic changes in the computing environment.

Many applications use contexts to understand their environments and make adaptation. However, contexts are often inaccurate or even conflicting with each other (a.k.a. context inconsistency). To prevent applications from behaving abnormally or even failing, one promising approach is to deploy constraint checking to detect context inconsistencies. A variety of constraint checking techniques have been proposed, based on different incremental or parallel mechanisms for the efficiency. They are commonly deployed with the strategy that schedules constraint checking immediately upon context changes. This assures no missed inconsistency, but also limits the detection efficiency. One may break the limit by grouping context changes for checking together, but this can cause severe inconsistency missing problem (up to 79.2 percent). In this article, we propose a novel strategy GEAS to isolate latent interferences among context changes and schedule constraint checking with adaptive group sizes. This makes GEAS not only improve the detection efficiency, but also assure no missed inconsistency with theoretical guarantee. We experimentally evaluated GEAS with large-volume real-world context data. The results show that GEAS achieved significant efficiency gains for context inconsistency detection by 38.8-566.7 percent (or 1.4x-6.7x). When enhanced with an extended change-cancellation optimization, the gains were up to 2,755.9 percent (or 28.6x).

Network embedding aims to automatically learn the node representations in networks. The basic idea of network embedding is to first construct a network to describe the neighborhood context for each node, and then learn the node representations by designing an objective function to preserve certain properties of the constructed context network. The vast majority of the existing methods, explicitly or implicitly, follow a pointwise design principle. That is, the objective can be decomposed into the summation of the certain goodness function over each individual edge of the context network. In this paper, we propose to go beyond such pointwise approaches, and introduce the ranking-oriented design principle for network embedding. The key idea is to decompose the overall objective function into the summation of a goodness function over a set of edges to collectively preserve their relative rankings on the context network. We instantiate the ranking-oriented design principle by two new network embedding algorithms, including a pairwise network embedding method PaWine which optimizes the relative weights of edge pairs, and a listwise method LiWine which optimizes the relative weights of edge lists. Both proposed algorithms bear a linear time complexity, making themselves scalable to large networks. We conduct extensive experimental evaluations on five real datasets with a variety of downstream learning tasks, which demonstrate that the proposed approaches consistently outperform the existing methods.

Generating high-quality system call sequences is not only important to testing file system implementations, but also challenging due to the astronomically large input space. This paper introduces a new approach to the workload generation problem by building layered models and abstract workloads refinement. This approach is instantiated as a three-layer file system model for file system workload generation. In a short-period experiment run, sequential workloads (system call sequences) manifested over a thousand crashes in mainline Linux Kernel file systems, with 12 previously unknown bugs being reported. We also provide evidence that such workloads benefit other domain-specific testing techniques including crash consistency testing and concurrency testing.

Deep learning (DL) applications are becoming increasingly popular. Their reliabilities largely depend on the performance of DL models integrated in these applications as a central classifying module. Traditional techniques need to retrain the models or rebuild and redeploy the applications for coping with unexpected conditions beyond the models' handling capabilities. In this paper, we take a fault tolerance approach, Dissector, to distinguishing those inputs that represent unexpected conditions (beyond-inputs) from normal inputs that are still within the models' handling capabilities (within-inputs), thus keeping the applications still function with expected reliabilities. The key insight of Dissector is that a DL model should interpret a within-input with increasing confidence, while a beyond-input would probably cause confused guesses in the prediction process. Dissector works in an application-specific way, adaptive to DL models used in applications, and extremely efficiently, scalable to large-size datasets from complex scenarios. The experimental evaluation shows that Dissector outperformed state-of-the-art techniques in the effectiveness (AUC: avg. 0.8935 and up to 0.9894) and efficiency (runtime overhead: only 3.3--5.8 milliseconds). Besides, it also exhibited encouraging usefulness in defensing against adversarial inputs (AUC: avg. 0.9983) and improving a DL model's actual accuracy in use (up to 16% for CIFAR-100 and 20% for ImageNet).

Android apps demand high-quality test inputs, whose generation remains an open challenge. Existing techniques fall short on exploring complex app functionalities reachable only by a long, meaningful, and effective test input. Observing that such test inputs can usually be decomposed into relatively independent short use cases, this paper presents ComboDroid, a fundamentally different Android app testing framework. ComboDroid obtains use cases for manifesting a specific app functionality (either manually provided or automatically extracted), and systematically enumerates the combinations of use cases, yielding high-quality test inputs.

Trained DNN models are increasingly adopted as integral parts of software systems, but they often perform deficiently in the field. A particularly damaging problem is that DNN models often give false predictions with high confidence, due to the unavoidable slight divergences between operation data and training data. To minimize the loss caused by inaccurate confidence, operational calibration, i.e., calibrating the confidence function of a DNN classifier against its operation domain, becomes a necessary debugging step in the engineering of the whole system.

Cyber-physical software delivers context-aware services through continually interacting with its physical environment and adapting to the changing surroundings. However, when the software's assumptions on the environment no longer hold, the interactions can introduce errors for leading to unexpected behaviors and even system failures. One promising solution to this problem is to conduct runtime monitoring of invariants. Violated invariants reflect latent erroneous states (i.e., abnormal states that could lead to failures). In turn, monitoring when program executions violate the invariants can allow the software to take alternative measures to avoid danger. In this article, we present context-based Multiinvariant detection (CoMID), an approach that automatically infers invariants and detects abnormal states for cyber-physical programs. CoMID consists of two novel techniques, namely context-based trace grouping and multiinvariant detection. The former infers contexts to distinguish different effective scopes for CoMID's derived invariants, and the latter conducts ensemble evaluation of multiple invariants to detect abnormal states during runtime monitoring. We evaluate CoMID on real-world cyber-physical software. The results show that CoMID achieves a 5.7-28.2% higher true-positive rate and a 6.8-37.6% lower false-positive rate in detecting abnormal states, as compared with the existing approaches. When deployed in field tests, CoMID's runtime monitoring improves the success rate of cyber-physical software in its task executions by 15.3-31.7%.

Recommending suitable tags for online textual content is a key building block for better content organization and consumption. In this paper, we identify three pillars that impact the accuracy of tag recommendation: (1) sequential text modeling meaning that the intrinsic sequential ordering as well as different areas of text might have an important implication on the corresponding tag(s) , (2) tag correlation meaning that the tags for a certain piece of textual content are often semantically correlated with each other, and (3) content-tag overlapping meaning that the vocabularies of content and tags are overlapped. However, none of the existing methods consider all these three aspects, leading to a suboptimal tag recommendation. In this paper, we propose an integral model to encode all the three aspects in a coherent encoder-decoder framework. In particular, (1) the encoder models the semantics of the textual content via Recurrent Neural Networks with the attention mechanism, (2) the decoder tackles the tag correlation with a prediction path, and (3) a shared embedding layer and an indicator function across encoder-decoder address the content-tag overlapping. Experimental results on three realworld datasets demonstrate that the proposed method significantly outperforms the existing methods in terms of recommendation accuracy.

Hashtags can greatly facilitate content navigation and improve user engagement in social media. Meaningful as it might be, recommending hashtags for photo sharing services such as Instagram and Pinterest remains a daunting task due to the following two reasons. On the endogenous side, posts in photo sharing services often contain both images and text, which are likely to be correlated with each other. Therefore, it is crucial to coherently model both image and text as well as the interaction between them. On the exogenous side, hashtags are generated by users and different users might come up with different tags for similar posts, due to their different preference and/or community effect. Therefore, it is highly desirable to characterize the users’ tagging habits. In this paper, we propose an integral and effective hashtag recommendation approach for photo sharing services. In particular, the proposed approach considers both the endogenous and exogenous effects by a content modeling module and a habit modeling module, respectively. For the content modeling module, we adopt the parallel co-attention mechanism to coherently model both image and text as well as the interaction between them; for the habit modeling module, we introduce an external memory unit to characterize the historical tagging habit of each user. The overall hashtag recommendations are generated on the basis of both the post features from the content modeling module and the habit influences from the habit modeling module. We evaluate the proposed approach on real Instagram data. The experimental results demonstrate that the proposed approach significantly outperforms the state-of-theart methods in terms of recommendation accuracy, and that both content modeling and habit modeling contribute significantly to the overall recommendation accuracy.

Mobile apps have been an indispensable part in our daily life. However, there exist many potentially harmful apps that may exploit users' privacy data, e.g., collecting the user's information or sending messages in the background. Keeping these undesired apps away from the market is an ongoing challenge. While existing work provides techniques to determine what apps do, e.g., leaking information, little work has been done to answer, are the apps' behaviors compatible with the intentions reflected by the app's UI? In this work, we explore the synergistic cooperation of deep learning and program analysis as the first step to address this challenge. Specifically, we focus on the UI widgets that respond to user interactions and examine whether the intentions reflected by their UIs justify their permission uses. We present DeepIntent, a framework that uses novel deep icon-behavior learning to learn an icon-behavior model from a large number of popular apps and detect intention-behavior discrepancies. In particular, DeepIntent provides program analysis techniques to associate the intentions (i.e., icons and contextual texts) with UI widgets' program behaviors, and infer the labels (i.e., permission uses) for the UI widgets based on the program behaviors, enabling the construction of a large-scale high-quality training dataset. Based on the results of the static analysis, DeepIntent uses deep learning techniques that jointly model icons and their contextual texts to learn an icon-behavior model, and detects intention-behavior discrepancies by computing the outlier scores based on the learned model. We evaluate DeepIntent on a large-scale dataset (9,891 benign apps and 16,262 malicious apps). With 80% of the benign apps for training and the remaining for evaluation, DeepIntent detects discrepancies with AUC scores 0.8656 and 0.8839 on benign apps and malicious apps, achieving 39.9% and 26.1% relative improvements over the state-of-the-art approaches.

Network embedding, which learns the low-dimensional representations of nodes, has gained significant research attention. Despite its superior empirical success, often measured by the prediction performance of downstream tasks (e.g., multi-label classification), it is unclear \em why a given embedding algorithm outputs the specific node representations, and \em how the resulting node representations relate to the structure of the input network. In this paper, we propose to discern the edge influence as the first step towards understanding skip-gram basd network embedding methods. For this purpose, we propose an auditing framework Near, whose key part includes two algorithms (Near-add \ and Near-del ) to effectively and efficiently quantify the influence of each edge. Based on the algorithms, we further identify high-influential edges by exploiting the linkage between edge influence and the network structure. Experimental results demonstrate that the proposed algorithms (Near-add \ and Near-del ) are significantly faster (up to $2,000\times$) than straightforward methods with little quality loss. Moreover, the proposed framework can efficiently identify the most influential edges for network embedding in the context of downstream prediction task and adversarial attacking.

Recovering missing values in time series is critical when performing time series analysis. And the blackouts issue studied in this paper, described as losing all the data during a certain period, is among the most urgent and challenging issues. While the existing approaches for missing value recovery in time series could not handle this issue properly, in this work, we proposes a Hankel matrix factorization-based approach for tagged time series called HKMF-T, following the idea of decomposing a data sequence into the smooth trend and the external impact components. By transforming the data sequence into its Hankel matrix form, HKMF-T models the smooth trend implied by high-order temporal correlations as the product of two low-rank matrices, and learns the external impacts indicated by a corresponding tag sequence. Through extensive experiments conducted on three real-world data sets, HKMF-T shows its effectiveness by outperforming all baseline methods for blackouts with durations longer than nine sampling intervals.

This paper introduces a new, fully automated modelbased approach for effective testing of Android apps. Different from existing model-based approaches that guide testing with a static GUI model (i.e., the model does not evolve its abstraction during testing, and is thus often imprecise), our approach dynamically optimizes the model by leveraging the runtime information during testing. This capability of model evolution significantly improves model precision, and thus dramatically enhances the testing effectiveness compared to existing approaches, which our evaluation confirms.We have realized our technique in a practical tool, APE. On 15 large, widely-used apps from the Google Play Store, APE outperforms the state-of-the-art Android GUI testing tools in terms of both testing coverage and the number of detected unique crashes. To further demonstrate APE's effectiveness and usability, we conduct another evaluation of APE on 1,316 popular apps, where it found 537 unique crashes. Out of the 38 reported crashes, 13 have been fixed and 5 have been confirmed.

Commit messages, which summarize the source code changes in natural language, are essential for program comprehension and software evolution understanding. Unfortunately, due to the lack of direct motivation, commit messages are sometimes neglected by developers, making it necessary to automatically generate such messages. State-of-the-art adopts learning based approaches such as neural machine translation models for the commit message generation problem. However, they tend to ignore the code structure information and suffer from the out-of-vocabulary issue. In this paper, we propose CoDiSum to address the above two limitations. In particular, we first extract both code structure and code semantics from the source code changes, and then jointly model these two sources of information so as to better learn the representations of the code changes. Moreover, we augment the model with copying mechanism to further mitigate the out-of-vocabulary issue. Experimental evaluations on real data demonstrate that the proposed approach significantly outperforms the state-of-the-art in terms of accurately generating the commit messages.

Traceability recovery allows developers to extract and comprehend the trace links among software artifacts (e.g., requirements and code). These trace links can provide important support to software maintenance and evolution tasks. Information Retrieval (IR) is now widely accepted as the key technique of semi-automatic tools to recover candidate trace links based on textual similarities among artifacts. However, the vocabulary mismatch problem between different artifacts hinders the performance of these IR-based approaches. Thus, a growing body of enhancing strategies were proposed based on user feedback. They allow to adjust the textual similarities of candidate links after users accept or reject part of these links. Recently, several approaches successfully used this strategy to improve the performance of IR-based traceability recovery. However, these approaches require a large amount of user feedback, which is infeasible in practice. In this paper, we propose to improve IR-based traceability recovery by introducing only a small amount of user feedback into the closeness analysis on call and data dependencies in code. Specifically, our approach iteratively asks users to verify a chosen candidate link based on the quantified functional similarity for each code dependency (called closeness) and the generated IR values. The verified link is then used as the input to re-rank the unverified candidate links. An empirical evaluation based on five real-world systems shows that our approach can outperform four baseline approaches by using only a small amount of user feedback.

Spreadsheets are widely used, but subject to various defects and severe consequences due to poor maintenance by end users. Existing spreadsheet defect detection techniques fall short of effectiveness, either due to limited scopes or relying on rigid patterns. In this paper, we discuss and improve one state-of-the-art technique, CUSTODES, which uses cell clustering and anomaly detection to extend its scope and make its patterns adaptive to varying spreadsheet styles, but is prone to fragile clustering when involving irrelevant cells, leading to a largely reduced detection precision. We present WARDER to refine CUSTODES's cell clustering based on validity properties, and experimental results show that WARDER improves the precision by 20.7% on average or reach 100% for 79.8% worksheets on cell clustering, which contributes to a precision improvement of 23.1% for defect detection. WARDER also exhibits satisfactory results, against other spreadsheet defect detection techniques, and on another large-scale spreadsheet corpus VEnron2.

With the increasing adoption of Deep Neural Network (DNN) models as integral parts of software systems, efficient operational testing of DNNs is much in demand to ensure these models' actual performance in field conditions. A challenge is that the testing often needs to produce precise results with a very limited budget for labeling data collected in field.

Mobile applications (apps for short) often need to display images. However, inefficient image displaying (IID) issues are pervasive in mobile apps, and can severely impact app performance and user experience. This paper presents an empirical study of 162 real-world IID issues collected from 243 popular open-source Android apps, validating the presence and severity of IID issues, and then sheds light on these issues' characteristics to support future research on effective issue detection. Based on the findings of this study, we developed a static IID issue detection tool TAPIR and evaluated it with real-world Android apps. The experimental evaluations show encouraging results: TAPIR detected 43 previously-unknown IID issues in the latest version of the 243 apps, 16 of which have been confirmed by respective developers and 13 have been fixed.

Secondary index is used to accelerate the queries on non-rowkey columns in HBase by maintaining index items synchronously or asynchronously. Although existing asynchronous indexes have less inserting overhead than synchronous ones, they still need additional process to repair the possible inconsistency. This paper proposes an approach of embedding index repairing into data maintenance to save the extra process and meanwhile reduce the consistency-persisting cost. We implement this approach into a store engine as well as the corresponding client API, coprocessor and index-delete queue to constitute an effective secondary index building system for HBase. Experiments on YCSB benchmark show that it achieves a good balance between read and write performance, as well as better stability than other index building approaches.

Ensuring the quality of mobile applications (apps) needs to explore the GUI thoroughly. In practice, exhaustively exploring every GUI widget is unscalable on large real-world apps since it usually suffers from the problem of widgets explosion. To mitigate the problem, many existing testing tools usually detect and group homogeneous widgets heuristicly with different level of model abstraction since these widgets behave the same. However, no heuristic always works well. Heterogeneous widgets with divergent behaviors can be mistakenly grouped, which largely limits the testing effectiveness. This paper proposes a technique to effective GUI testing of Android apps with dynamic feedback-directed widgets grouping. Initially, we group the widgets according to the structure of the GUI. During testing, we observe behaviors of widgets in a group and regroup improperly-grouped widgets dynamically. Then, we apply a feedback-directed strategy to effectively accelerate the GUI exploration. The proposed technique is implemented as a practical tool for Android apps, named WGDroid. We evaluated WGDroid on 17 widely-used Android apps and compared it with the state-of-the-art GUI testing tools, i.e., AimDroid, SAPIENZ, and Monkey on both emulators and real devices. WGDroid outperformed the three tools in all testing coverages and also detected the most unique crashes. In particular, WGDroid discovered 208 more activities on 12 large benchmark apps on real devices and 11 more activities on another 5 benchmark apps on emulators, than the best of the other tools. These results show that WGDroid can significantly accelerate the GUI exploration.

Android fragmentation is a double-edged sword of the Android ecosystem. On the one hand, it promotes Android's prevalence. On the other hand, the numerous combinations of various system versions, customized features, system drivers, and device models make it infeasible, if not impossible, for developers to exhaustively test their apps for potential compatibility issues. Previous research has proposed promising techniques for detecting these issues. However, they suffer from severe false positive problems due to their lack of third-party library detection or imprecise program analysis. In this paper, we present ELEGANT, an automated tool to effectively detect and locate fragmentation-induced compatibility issues for Android apps. ELEGANT exploits whitelist-enhanced or obfuscation-insensitive techniques to detect and alleviate the impact of third-party libraries on the analysis precision, and uses a three-step static detection algorithm to increase the precision of its program analysis. We experimentally evaluated ELEGANT with 22 real-world popular Android apps. The experimental results confirmed ELEGANT's effectiveness on detecting and locating Android fragmentation-induced compatibility issues, as well as realizing an impressive reduction on false positives by around 70%.

This paper presents the CARMUS framework for continuous activity recognition with missing values on smartphones. Besides the power and resource constraints discussed in existing work, our framework is proposed to further tackle the critical issue of missing values during data collection. We demonstrate the issue's impact on continuous recognition through a motivating example, and specify two challenges-blackouts and resource constraints-with respect to smartphone-based sensing and processing platforms. To address the challenges, CARMUS provides a novel framework which involves a light-weight admission control unit and a data imputation unit intuited by the daily repeated pattern and temporal smoothness of human activity data. Based on extensive experiments conducted on a real-world data set with 37% of the data missing, we show that the CARMUS framework is effective for achieving an 85.5% recognition accuracy by adopting the state-of-the-art imputation algorithms.

Dynamic software updating (DSU) is a technique to upgrade a running software system on the fly without stopping the system. During updating, the runtime state of the modified components of the system needs to be properly transformed into a new state, so that the modified components can still correctly interact with the rest of the system. However, the transformation is non-trivial to realize due to the gap between the low-level implementations of two versions of a program. This paper presents AOTES, a novel approach to automating object transformations for dynamic updating of Java programs. AOTES bridges the gap by abstracting the old state of an object to a history of method invocations, and re-invoking the new version of all methods in the history to get the desired new state. AOTES requires no instrumentation to record any data and thus has no overhead during normal execution. We propose and implement a novel technique that can synthesize an equivalent history of method invocations based on the current object state only. We evaluated AOTES on software updates taken from Apache Commons Collections, Tomcat, FTP Server and SSHD Server. Experimental results show that AOTES successfully handled 51 of 61 object transformations of 21 updated classes, while two state-of-the-art approaches only handled 11 and 6 of 61, respectively.

Bug tracking systems, which help to track the reported software bugs, have been widely used in software development and maintenance. In these systems, recognizing relevant source files among a large number of source files for a given bug report is a time-consuming and labor-intensive task for software developers. To tackle this problem, information retrieval methods have been widely used to capture either the textual similarities or the semantic similarities between bug reports and source files. However, these two types of similarities are usually considered separately and the historical bug fixings are largely ignored by the existing methods. In this paper, we propose a supervised topic modeling method (STMLOCATOR) for automatically locating the relevant source files for a given bug report. In particular, the proposed model is built upon three key observations. First, supervised modeling can effectively make use of the existing fixing histories. Second, certain words in bug reports tend to appear multiple times in their relevant source files. Third, longer source files tend to have more bugs. By integrating the above three observations, the proposed STMLOCATOR utilizes historical fixings in a supervised way and learns both the textual similarities and semantic similarities between bug reports and source files. We further consider a special type of bug reports with stack-traces in bug reports, and propose a variant of STMLOCATOR to tailor for such bug reports. Experimental evaluations on three real data sets demonstrate that the proposed STMLOCATOR can achieve up to 23.6% improvement in terms of prediction accuracy over its best competitors, and scales linearly with the size of the data. Moreover, the proposed variant further improves STMLOCATOR by up to 76.2% on those bug reports with stack-traces.

With the rapid development of mobile devices, Android applications (apps) are universally used. However, attackers repackage Android apps and release them to the markets for illegal purposes, which brings great threats to the Android ecosystem. To leverage the popularity of original apps, they keep similar software behaviors to confuse app users. Furthermore, repackaged apps can be obfuscated or encrypted to avoid being detected. Besides, hybrid mobile apps, built by combining web technology and native elements, are becoming a preferred choice for developers. The structure of hybrid apps differs a lot from that of native apps which would raise great challenges to repackaging detection. Existing works still have some limitations in detecting repackaging from obfuscated and encrypted apps. Besides, few of them can deal with hybrid apps. In this paper, we proposed an approach based on the app UI regions extracted from app's runtime UI traces. We also implement a tool named RegionDroid based on the approach. We apply RegionDroid to tree datasets with totally 369 apps. It successfully finds all the 98 obfuscated or encrypted repackaged pairs in dataset S1. It also shows good credibility in distinguishing another 114 commercial apps in dataset S2. We also test our approach in dataset S3with 157 hybrid apps by comparing them pairwisely and the false positive rate is 0.016%.

Routing the bug reports to potential fixers (i.e., bug triaging), is an integral step in software development and maintenance. However, manually inspecting and assigning bug reports is tedious and time-consuming, especially in those software projects that have a large amount of bug reports and developers. To make bug triaging more efficient, many machine learning and information retrieval based approaches have been proposed to automatically assign bug reports for suitable developers to fix. However, these techniques typically ignore two important facts in bug fixing. First, for some bug reports, the bug reporter himself/herself is one of the developers in the project, and he/she is likely to fix his/her reported bugs in the future. Second, for some bug reports, there may be a tossing sequence which contains several developers from the first potential fixer to the last actual fixer. Such tossing sequences encode valuable information such as the dependency of developers for the bug triaging task. To make use of the above facts, we propose a sequence to sequence model named SeqTriage to automatically route a given bug report to its responsible fixer. Evaluation results on three different open-source projects show that the proposed approach has significantly improved the accuracy of bug triaging compared with the state-of-the-art approaches (20% at best and 5% at least).

Services are widely used in Android apps. However, services may leak such that they are no longer used but cannot be recycled by the Garbage Collector. Service leaks may cause an app to misbehave, and are vulnerable to malicious external apps when the service is exported or it is accessible through other exported services. In this paper, we present LESDroid for exported service leaks detection. LESDroid automatically generates service instances and workloads (start/stop or bind/unbind of exported services) of the app under test, and applies a designated oracle to the heap snapshot for service leak detection. We evaluated LESDroid using 375 commercial apps, and found 97 leaked services and 98 distinct leak entries in 70 apps.

Regular expression (regex) with modern extensions is one of the most popular string processing tools. However, poorly-designed regexes can yield exponentially many matching steps, and lead to regex Denial-of-Service (ReDoS) attacks under well-conceived string inputs. This paper presents Rescue, a three-phase gray-box analytical technique, to automatically generate ReDoS strings to highlight vulnerabilities of given regexes. Rescue systematically seeds (by a genetic search), incubates (by another genetic search), and finally pumps (by a regex-dedicated algorithm) for generating strings with maximized search time. We implemenmted the Rescue tool and evaluated it against 29,088 practical regexes in real-world projects. The evaluation results show that Rescue found 49% more attack strings compared with the best existing technique, and applying Rescue to popular GitHub projects discovered ten previously unknown ReDoS vulnerabilities.

The replicated list object is frequently used to model the core functionality of replicated collaborative text editing systems. Since 1989, the convergence property has been a common specification of a replicated list object. Recently, Attiya et al. proposed the strong/weak list specification and conjectured that the well-known Jupiter protocol satisfies the weak list specification. The major obstacle to proving this conjecture is the mismatch between the global property on all replica states prescribed by the specification and the local view each replica maintains in Jupiter using data structures like 1D buffer or 2D state space. To address this issue, we propose CJupiter (Compact Jupiter) based on a novel data structure called $n$-ary ordered state space for a replicated client/server system with $n$ clients. At a high level, CJupiter maintains only a single $n$-ary ordered state space which encompasses exactly all states of each replica. We prove that CJupiter and Jupiter are equivalent and that CJupiter satisfies the weak list specification, thus solving the conjecture above.

The replicated list object is frequently used to model the core functionality of replicated collaborative text editing systems. Recently, Attiya et al. proposed the strong/weak list specification and conjectured that the well-known Jupiter protocol satisfies the weak list specification. The major obstacle to proving this conjecture is the mismatch between the global property on all replica states prescribed by the specification and the local view each replica maintains in Jupiter using data structures like 1D buffer or 2D state space. To address this issue, we propose CJupiter (Compact Jupiter) based on a novel data structure called n-ary ordered state space for a replicated client/server system with n clients. At a high level, CJupiter maintains only a single n-ary ordered state space which encompasses exactly all states of each replica. We prove that CJupiter and Jupiter are equivalent and that CJupiter satisfies the weak list specification, thus solving the conjecture above.

Machine learning (ML) programs are being widely used in various human-related applications. However, their testing always remains to be a challenging problem, and one can hardly decide whether and how the existing knowledge extracted from training scenarios suit new scenarios. Existing approaches typically have restricted usages due to their assumptions on the availability of an oracle, comparable implementation, or manual inspection efforts. We solve this problem by proposing a novel program synthesis based approach, SynEva, that can systematically construct an oracle-alike mirror program for similarity measurement, and automatically compare it with the existing knowledge on new scenarios to decide how the knowledge suits the new scenarios. SynEva is lightweight and fully automated. Our experimental evaluation with real-world data sets validates SynEva's effectiveness by strong correlation and little overhead results. We expect that SynEva can apply to, and help evaluate, more ML programs for new scenarios.

A multithreaded program's interleaving space is discrete and astronomically large, making effectively sampling thread schedules for manifesting concurrency bugs a challenging task. Observing that concurrency bugs can be manifested by adjusting thread relative speeds, this paper presents the new concept of speed space in which each vector denotes a family of thread schedules. A multithreaded program's speed space is approximately continuous, easy-to-sample, and preserves certain categories of concurrency bugs. We discuss the design, implementation, and evaluation of our speed-controlled scheduler for exploring adversarial/abnormal schedules. The experimental results confirm that our technique is effective in sampling diverse schedules. Our implementation also found previously unknown concurrency bugs in real-world multithreaded programs.

Cyber-Physical Systems (CPS) intrinsically combine hardware and physical systems with software and network, which are together creating complex and correlated interactions. CPS applications often experience uncertainty in interacting with environment through unreliable sensors. They can be faulty and exhibit runtime errors if developers have not considered environmental interaction uncertainty adequately. Existing work in verifying CPS applications ignores interaction uncertainty and thus may overlook uncertainty-related faults. To improve verification accuracy, in this article we propose a novel approach to verifying CPS applications with explicit modeling of uncertainty arisen in the interaction between them and the environment. Our approach builds an Interactive State Machine network for a CPS application and models interaction uncertainty by error ranges and distributions. Then it encodes both the application and uncertainty models to Satisfiability Modulo Theories (SMT) formula to leverage SMT solvers searching for counterexamples that represent application failures. The precision of uncertainty model can affect the verification results. However, it may be difficult to model interaction uncertainty precisely enough at the beginning, because of the uncontrollable noise of sensors and insufficient data sample size. To further improve the accuracy of the verification results, we propose an approach to identifying and calibrating imprecise uncertainty models. We exploit the inconsistency between the counterexamples’ estimate and actual occurrence probabilities to identify possible imprecision in uncertainty models, and the calibration of imprecise models is to minimize the inconsistency, which is reduced to a Search-Based Software Engineering problem. We experimentally evaluated our verification and calibration approaches with real-world CPS applications, and the experimental results confirmed their effectiveness and efficiency.

Information retrieval methods have been proposed to help developers locate related buggy source files for a given bug report. The basic assumption of these methods is that the bug description in a bug report should be textually similar to its buggy source files. However, the metadata (such as the component and version information) in bug reports is largely ignored by these methods. In this paper, we propose to explore the metadata for the bug localization task. In particular, we first apply a generative model to locate buggy source files based on the bug descriptions, and then propose to add the available metadata in bug reports into the localization process. Experimental evaluations on several software projects indicate that the metadata is useful to improve the localization accuracy and that the proposed bug localization method outperforms several existing methods.

Memory leak, one of the most common problems threatening android apps, might drain the limited memory of mobile devices, cause unexpected delays, no-responses or even crashes to apps. Activity/Fragment Leak is one of the most common and serious causes of memory leaks and has a vast influence on the Android app market. Existing work to identify leaked activities/fragments either depend highly on the experience of developers, or require app's source code and manual interactions. In this paper, we propose an automatic tool named LeakDAF for detecting leaked activities/fragments automatically without manual intervention. LeakDAF makes use of UI testing technique to execute automatically the app under test, and applies memory analysis technique to inspect dumped heap files to identify leaked activities and fragments based on Android's mechanisms for managing them. To evaluate the effectiveness of LeakDAF, we successfully applied it to 35 open source and 64 commercial apps, and we detected at least one leaked activity or fragment for 10 open source apps and 35 commercial apps.

Activities are the fundamental components of Android applications (apps). However, existing approaches to automated testing for Android apps cannot effectively manage the transitions between activities, e.g., too rarely or too often. Besides, some techniques need to repeatedly restart from scratch and revisit every intermediate activity to reach a specific one, which leads to unnecessarily long transitions and wasted time. To address these problems, we propose AimDroid, a practical model-based approach to automated testing for Android apps that aims to manage the exploration of activities and meantime minimize unnecessary transitions between them. Specifically, AimDroid applies an activity-insulated multi-level strategy during testing and replaying. It systematically discovers unexplored activities and then intensively exploits every discovered individual with a reinforcement learning guided random algorithm. We conduct comprehensive experiments on 50 popular closed-source commercial apps that in total have billions of daily usages in China. The results demonstrate that AimDroid outperforms both Sapienz and Monkey in activity, method and instruction coverage, respectively. In addition, AimDroid also reports more crashes than the other two.

Context-aware applications adapt their behavior based on collected contexts. However, contexts can be inaccurate due to sensing noise, which might cause applications to misbehave. One promising approach is to check contexts against consistency constraints at runtime, so as to detect context inconsistencies for applications and resolve them in time. The checking is typically immediate upon each collected context change. Such a scheduling strategy is intuitive for avoiding missing context inconsistencies in the detection, but may cause low-efficiency problems for heavy-workload checking scenarios, even if equipped with existing incremental or parallel constraint checking techniques. One may choose to check contexts in a batch way to increase the efficiency by reducing the number of constraint checking. However, this can easily cause missed context inconsistencies, denying the purpose of inconsistency detection. In this paper, we propose a novel scheduling strategy GEAS of two nice properties: (1) adaptively tuning the batch window to avoid missing any context inconsistency; (2) generic to checking techniques with no or little adjustment. We experimentally evaluated GEAS against the immediate strategy with existing constraint checking techniques. The experimental results show that GEAS achieved 143-645% efficiency improvement without missing any context inconsistency, while alternatives caused 39.2-65.3% loss of detected context inconsistencies.

The concept of complex event processing (CEP) and complex-event-aware service have been extensively studied to retrieve relevant information from massive amount of realtime streaming events. In mobile environment, the Mobilityaware CEP (MCEP) system was proposed to address the issue of synchronization problem between different query ranges and MCEP operators. We noticed that MCEP systems lack the ability to process event in parallel and scale out when system load is high. In this paper, we proposed a parallel architecture for MCEP. The architecture can handle the synchronization problem and guarantee the correctness of event processing result. We also proposed a scaling strategy that can automatically scale out operators while ensures semantic transparency. An empirical evaluation based on up to 10 ViMs demonstrated that our approach is able to achieve higher throughput while keeping the MCEP synchronization mechanism valid.

In recent years, with the explosive growth of mobile smart phonesnes, the number of Android applications (apps) increases rapidly. Attackers usually leverage the popumobile smart phoneslarity of Android apps by inserting malwares, modifying the original apps, repackaging and releasing them for their own illegal purposes. To avoid repackaged apps from being detected, they usually use sorts of obfuscation and encryption tools. As a result, it's important to detect which apps are repackaged. People often intuitively judge whether two apps are a repackaged pair by executing them and observing their runtime user interface (UI) traces. Hence, we propose layout group graph (LGG) built from UI trances to model those UI behaviors and use LGG as the birthmark of Android apps for identification. Based on LGG, we also implement a dynamic repackaging detection tool, RepDroid. Since our method does not require the apps' source code, it is resilient to app obfuscation and encryption. We conducted an experiment with two data sets. The first set contains 98 pairs of repackaged apps. The original apps and repackaged ones are compared and we can detect all of these repackaged pairs. The second set contains 125 commercial apps. We compared them pair-wisely and the false positive rate was 0.08%.

Latent factor models have become a prevalent method in recommender systems, to predict users' preference on items based on the historical user feedback. Most of the existing methods, explicitly or implicitly, are built upon the first-order rating distance principle, which aims to minimize the difference between the estimated and real ratings. In this paper, we generalize such first-order rating distance principle and propose a new latent factor model (HoORaYs) for recommender systems. The core idea of the proposed method is to explore high-order rating distance, which aims to minimize not only (i) the difference between the estimated and real ratings of the same (user, item) pair (i.e., the first-order rating distance), but also (ii) the difference between the estimated and real rating difference of the same user across different items (i.e., the second-order rating distance). We formulate it as a regularized optimization problem, and propose an effective and scalable algorithm to solve it. Our analysis from the geometry and Bayesian perspectives indicate that by exploring the high-order rating distance, it helps to reduce the variance of the estimator, which in turns leads to better generalization performance (e.g., smaller prediction error). We evaluate the proposed method on four real-world data sets, two with explicit user feedback and the other two with implicit user feedback. Experimental results show that the proposed method consistently outperforms the state-of-the-art methods in terms of the prediction accuracy.

In this paper, we study the problem of pedestrian relative positioning with respect to their walking direction. Existing approaches are mainly based on trajectory information or device proximity detection, and they highly rely on infrastructure or specialized device support. Importantly, most work does not provide relative position information with respect to people's walking direction. To address the above issues, we propose a direction-aware, audio-based solution that only uses daily wearable devices. Based on the fact that pedestrian's arms often swing back and forth during walking, we develop the wrist-body model that formally models the distance change between a user's wrist and his/her walking mate's body when walking together. Based on this model, we design our system by attaching the audio sources to a user's wrists and an audio receiver to the other user's body. We develop key indicators that characterize the received audio signal's Doppler shift induced by arm swing motions and the differences in signal strength. We further propose methods such as cycle segmentation and aggregation to deal with several real-world challenges. The performance of our approach is studied through extensive experiments. Evaluation conducted using real-world data suggests the prototype system achieves 85.9% positioning accuracy, demonstrating its effectiveness.

Several relaxed variants of Snapshot Isolation (SI) have been proposed for improved performance in distributed transactional key-value stores. These relaxed variants, however, provide no specification or control of the severity of the anomalies with respect to SI. They have also been designed to be used statically throughout the whole system life cycle. To overcome these drawbacks, we propose the idea of parameterized and runtime-tunable snapshot isolation. We first define a new transactional consistency model called Relaxed Version Snapshot Isolation (RVSI), which can formally and quantitatively specify the anomalies it may produce with respect to SI. To this end, we decompose SI into three "view properties", for each of which we introduce a parameter to quantify one of three kinds of possible anomalies: k1-BV (k1-version bounded backward view), k2-FV (k2-version bounded forward view), and k3-SV (k3-version bounded snapshot view). We then implement a prototype partitioned replicated distributed transactional key-value store called Chameleon across multiple data centers. While achieving RVSI, Chameleon allows each transaction to dynamically tune its consistency level at runtime. The experiments show that RVSI helps to reduce the transaction abort rates when applications are willing to tolerate certain anomalies. We also evaluate the individual impacts of k1-BV, k2-FV, and k3-SV on reducing the transaction abort rates in various scenarios. We find that it depends on the issue delays between clients and replicas which of k1 and k2 plays a major role in reducing transaction abort rates.

Information Retrieval (IR) identifies trace links based on textual similarities among software artifacts. However, the vocabulary mismatch problem between different artifacts hinders the performance of IR-based approaches. A growing body of work addresses this issue by combining IR techniques with code dependency analysis such as method calls. However, so far the performance of combined approaches is highly dependent to the correctness of IR techniques and does not take full advantage of the code dependency analysis. In this paper, we combine IR techniques with closeness analysis to improve IR-based traceability recovery. Specifically, we quantify and utilize the “closeness” for each call and data dependency between two classes to improve rankings of traceability candidate lists. An empirical evaluation based on three real-world systems suggests that our approach outperforms three baseline approaches.

A consistency/latency tradeoff arises as soon as a distributed storage system replicates data. For low latency, distributed storage systems often settle for weak consistency conditions, providing little guarantee on data consistency. In this paper, we propose the notion of almost strong consistency as an option for the consistency/latency tradeoff. It provides both deterministically bounded staleness of data versions for reads and probabilistic quantification on the rate of “reading stale data”, while achieving low latency. We then investigate almost strong consistency in terms of probabilistically-atomic 2-atomicity. Our PA2AM algorithm for the single-writer model completes each read in one communication round-trip, and guarantees that each read obtains the value of within the latest two versions. To quantify the rate of “reading the stale version”, we decompose the so-called “old-new inversion” anomaly into long-lived write concurrency patterns and non-monotonic read-write patterns, and propose a queueing model and a timed balls-into-bins model to analyze them, respectively. The probabilistic analysis not only demonstrates that old-new inversions rarely occur, but also reveals that the read-write pattern dominates in preventing them from occurring. These are then supported by our experiments. To further demonstrate the benefits of probabilistically-atomic 2-atomicity, we also compare it to weak consistency conditions.

In recent years, recommender system is one of indispensable components in many e-commerce websites. One of the major challenges that largely remains open is the cold-start problem, which can be viewed as a barrier that keeps the cold-start users/items away from the existing ones. In this paper, we aim to break through this barrier for cold-start users/items by the assistance of existing ones. In particular, inspired by the classic Elo Rating System, which has been widely adopted in chess tournaments, we propose a novel rating comparison strategy (RAPARE) to learn the latent profiles of cold-start users/items. The centerpiece of our RAPARE is to provide a fine-grained calibration on the latent profiles of cold-start users/items by exploring the differences between cold-start and existing users/items. As a generic strategy, our proposed strategy can be instantiated into existing methods in recommender systems. To reveal the capability of RAPARE strategy, we instantiate our strategy on two prevalent methods in recommender systems, i.e., the matrix factorization based and neighborhood based collaborative filtering. Experimental evaluations on five real data sets validate the superiority of our approach over the existing methods in cold-start scenario.

Community Question Answering (CQA) sites, such as Stack Overflow and Yahoo! Answers, have become very popular in recent years. These sites contain rich crowdsourcing knowledge contributed by the site users in the form of questions and answers, and these questions and answers can satisfy the information needs of more users. In this article, we aim at predicting the voting scores of questions/answers shortly after they are posted in the CQA sites. To accomplish this task, we identify three key aspects that matter with the voting of a post, i.e., the non-linear relationships between features and output, the question and answer coupling, and the dynamic fashion of data arrivals. A family of algorithms are proposed to model the above three key aspects. Some approximations and extensions are also proposed to scale up the computation. We analyze the proposed algorithms in terms of optimality, correctness, and complexity. Extensive experimental evaluations conducted on two real data sets demonstrate the effectiveness and efficiency of our algorithms.

Elderly care is one of the many applications supported by real-time activity recognition systems. Traditional approaches use cameras, body sensor networks, or radio patterns from various sources for activity recognition. However, these approaches are limited due to ease-of-use, coverage, or privacy preserving issues. In this paper, we present a novel wearable Radio Frequency Identification (RFID) system aims at providing an easy-to-use solution with high detection coverage. Our system uses passive tags which are maintenance-free and can be embedded into the clothes to reduce the wearing and maintenance efforts. A small RFID reader is also worn on the user's body to extend the detection coverage as the user moves. We exploit RFID radio patterns and extract both spatial and temporal features to characterize various activities. We also address the issues of false negative of tag readings and tag/antenna calibration, and design a fast online recognition system. Antenna and tag selection is done automatically to explore the minimum number of devices required to achieve target accuracy. We develop a prototype system which consists of a wearable RFID system and a smartphone to demonstrate the working principles, and conduct experimental studies with four subjects over two weeks. The results show that our system achieves a high recognition accuracy of 93.6 percent with a latency of 5 seconds. Additionally, we show that the system only requires two antennas and four tagged body parts to achieve a high recognition accuracy of 85 percent.

With the great popularity of mobile devices, the amount of mobile apps has grown at a more dramatic rate than ever expected. A technical challenge is how to recommend suitable apps to mobile users. In this work, we identify and focus on a unique characteristic that exists in mobile app recommendation—that is, an app usually corresponds to multiple release versions. Based on this characteristic, we propose a fine-grain version-aware app recommendation problem. Instead of directly learning the users’ preferences over the apps, we aim to infer the ratings of users on a specific version of an app. However, the user-version rating matrix will be sparser than the corresponding user-app rating matrix, making existing recommendation methods less effective. In view of this, our approach has made two major extensions. First, we leverage the review text that is associated with each rating record; more importantly, we consider two types of version-based correlations. The first type is to capture the temporal correlations between multiple versions within the same app, and the second type of correlation is to capture the aggregation correlations between similar apps. Experimental results on a large dataset demonstrate the superiority of our approach over several competitive methods.

Dynamic software updating (DSU) is a technique that can update running software systems without stopping them. Most existing approaches require programmer participation to guarantee the correctness of dynamic updating. However, manually preparing dynamic updating is error-prone and time-consuming. Therefore, other approaches prefer to aggressively perform updating without programmer intervention, which may definitely lead to unanticipated runtime errors. To reduce human effort and enhance the reliability for dynamic updating, we leverage automatic runtime recovery (ARR) techniques to recover runtime errors caused by improper dynamic updating. This paper presents ADSU, a fully automatic DSU system using ARR. We evaluate ADSU with real updates from widely used open source software systems, i.e., Apache Tomcat, Apache FTP Server and jEdit. The preliminary results have shown that ADSU succeeds in automatically applying 11 of 16 real-world updates that existing counterparts cannot.

Smartphones are indispensable in people's daily lives. As smartphone apps are being increasingly concurrent, developers are increasingly unable to tackle the complexity and to avoid subtle concurrency bugs. To better address this issue, we propose a novel approach to manifesting concurrency bugs in Android apps based on the fact that one can simultaneously generate input events and their schedules for an app. We conduct static-dynamic hybrid analysis to find potentially conflicting resource accesses in an app. The app is then automatically pressure-tested by guided event and schedule generation. We implemented the prototype tool AATT and evaluated it over thirteen popular real-world open-source apps. AATT successfully found 9 concurrency bugs out of which 7 were previously unknown.

Mobile applications (apps) are mostly driven by touch gestures whose interactions are natural to human beings. However, generating gesture events for effective and efficient testing of such apps remains to be a challenge. Existing event generation techniques either feed the apps under test with random gestures or exhaustively enumerate all possible gestures. While the former strategy leads to incomplete test coverage, the latter suffers from efficiency issues. In this paper, we study the particular problem of gesture event generation for Android apps. We present a static analysis technique to obtain the gesture information: each UI component's potentially relevant gestures, so as to reduce the amount of gesture events to be delivered in the automated testing. We implemented our technique as a prototype tool GAT and evaluated it with real-world Android apps. The experimental results show that GAT is both effective and efficient in covering more code as well as detecting gesturerelated bugs.

Dynamic software updating (DSU) aims to patch software for fixing bugs or adding functions while it is running. Before update, developers need to make a dynamic patch ready, which includes update points, state transformers and a corresponding code patch. Existing practice mostly assumes manual preparation of dynamic patches, but this process can be both time-consuming and error-prone. Some pioneer work attempts to automate this process, but cannot guarantee the generation of safe dynamic patches for most updates. This paper presents a novel approach CURE to automatically generating safe dynamic patches. CURE takes two versions of software and their test cases as input, and automatically synthesizes state transformers and selects update points. We applied CURE to 28 updates for three real-world server software. The experimental results show that CURE generated safe dynamic patches automatically and their corresponding updates achieved an 88.7% success rate, as compared to 74.3% for TOS and 61.2% for default patches.

Tag recommendation is helpful for the categorization and searching of online content. Existing tag recommendation methods can be divided into collaborative filtering methods and content based methods. In this paper, we put our focus on the content based tag recommendation due to its wider applicability. Our key observation is the tag-content co-occurrence, i.e., many tags have appeared multiple times in the corresponding content. Based on this observation, we propose a generative model (Tag2Word), where we generate the words based on the tag-word distribution as well as the tag itself. Experimental evaluations on real data sets demonstrate that the proposed method outperforms several existing methods in terms of recommendation accuracy, while enjoying linear scalability.

Energy inefficiency of smartphone apps is one of the important non-functional issues. It is common, but difficult to diagnose, and often involves sensor usage. GreenDroid provides a novel approach to systematically diagnose energy inefficiency problems in smartphone apps running on Android platforms. It derives an application execution model (AEM) from Android framework and leverages it to realistically simulate an application's runtime behaviors. It also automatically analyzes an application's sensory data utilization, monitors sensor listener and wake lock usage, and reports actionable information to developers.

Software systems are often subject to unexpected runtime errors. Automatic runtime recovery (ARR) techniques aim at recovering them from erroneous states and maintaining them functional in the field. This paper proposes Ares , a novel, practical approach to performing ARR. Our key insight is to leverage a system's already built-in error handling support to recover from unexpected errors. To this end, we synthesize error handlers via two methods: error transformation and early return. We also equip Ares with a lightweight in-vivo testing infrastructure to select the right synthesis methods and avoid potentially dangerous error handlers. Unlike existing ARR techniques based on heavyweight mechanisms (e.g., checkpoint-restart and runtime monitoring), our approach expands the intrinsic capability of runtime error resilience already existing in software systems to handle unexpected errors. Ares's lightweight mechanism makes it practical and easy to be integrated into production environments. We have implemented Ares on top of both the Java HotSpot VM and Android ART, and applied it to 52 real-world bugs. The results are promising — Ares successfully recovers from 39 of them and incurs low overhead.

Smoking behavior detection has attracted much research interest for its significant impact on smokers' physical and mental health. Existing research has shown the potential of using wearable devices for fine-grained smoking puff and session detection by detecting a smoker's content of breathing, lighter usage, breathing, and gesture patterns. However, the existing systems are complex, and they are usually vulnerable to confounding activities and diversity of smoking behavior. To address these limitations, this paper proposes the design and implementation of a simple and compact smart neckband device for smoking detection. The device is equipped with both passive and active acoustic sensors to detect smoking sessions and puffs. We propose a hierarchical processing framework in which the lower-layer detects the sub-movements, i.e., lighter usage, hand-to-mouth gesture and deep breathing, from perceived audio data; and the higher-layer, based on the lower-layerąŕs detection results, detects smoking puffs and sessions using temporal sequence analysis techniques. Real-world experiments suggest our system can accurately detect smoking puffs and sessions with F1 score of respectively 93.59% and 92.96% in complex environments with the presence of confounding activities and diverse ways of smoking.

Combinatorial testing detects faults by trying different value combinations for program inputs. Traditional combinatorial testing treats programs as black box and focuses on manipulating program inputs (named input-based combinatorial testing or ICT). In this paper, we explore the possibility of conducting combinatorial testing via white-box branch information. Similarly, different combinations of branches taken in an execution are tried to test whether they help detect faults and to what extent. We name this technique branch-based combinatorial testing (BCT). We propose ways to address challenges in realizing BCT, and evaluate BCT with Java programs. The results reported that BCT can effectively detect faults even with low-level combinations, say 3-4 ways, which suggest it to be a strong test adequacy criterion. We also found that our greedy strategy for minimizing test suites reduces over 50% tests for reaching certain way levels, and merging nested branches detects faults more cost-effectively than considering them separately.

Software should behave correctly even in adverse conditions. Particularly, we study the problem of automated validation of crash consistency, i.e., file system data safety when systems crash. Existing work requires non-trivial manual efforts of specifying checking scripts and workloads, which is an obstacle for software developers. Therefore, we propose C3, a novel approach that makes crash consistency validation as easy as pressing a single button. With a program and an input, C3 automatically reports inconsistent crash sites. C3 not only exempts developers from the need of writing crash site checking scripts (by an algorithm that computes editing distance between file system snapshots) but also reduces the reliance on dedicated workloads (by test amplification). We implemented C3 as an open-source tool. With C3, we found 14 bugs in open-source software that have severe consequences at crash and 11 of them were previously unknown to the developers, including in highly mature software (e.g., GNU zip and GNU coreutils sort) and popular ones being actively developed (e.g., Adobe Brackets and TeXstudio).

Order of shared memory accesses, known as the shared memory dependence, is the cornerstone of dynamic analyses of concurrent programs. In this paper, we study the problem of reducing shared memory dependences. We present the first online software-only algorithm to reduce shared memory dependences without vector clock maintenance, opening a new direction to a broad range of applications (e.g., deterministic replay and data race detection). Our algorithm exploits a simple yet effective observation, that adaptive variable grouping can recognize and match spatial locality in shared memory accesses, to reduce shared memory dependences. We designed and implemented the bisectional coordination protocol, which dynamically maintains a partition of the program's address space without its prior knowledge, such that shared variables in each partitioned interval have consistent thread and spatial locality properties. Evaluation on a set of real-world programs showed that by paying a 0--54.7% (median 21%) slowdown, bisectional coordination reduced 0.95--97% (median 55%) and 16--99.99% (median 99%) shared memory dependences compared with RWTrace and LEAP, respectively.

Pervasive applications are involving more and more autonomous computing and communicating devices, augmented with the abilities of sensing and controlling the logical/physical environment. To enable context-awareness for such applications, we are challenged by the intrinsic asynchrony of the computing environment. Predicate detection is a well studied technique dedicated to detecting global predicates over asynchronous computations and can be employed to achieve context-awareness of the asynchronous environment. However, there is no methodological framework which guides us to systematically apply the abstract predicate detection theory to the development of concrete context-aware applications. To this end, we present the Predicate Detection-based ContextAwareness (PD-CA) framework. PD-CA maps the concepts of context-awareness to concepts of predicate detection. PD-CA also presents a design process of providing middleware support for context-aware applications. Under the guidance of the PD-CA framework, we design and implement the Middleware Infrastructure for Predicate detection in Asynchronous environments (MIPA). We also propose the programming toolkit to facilitate the development of context-aware applications based on MIPA, and demonstrate the use of the toolkit by a case study of a chemical plant safety management application. Experimental evaluations show the performance of MIPA in enabling context-awareness despite of the asynchrony.

Using magnetic field data as fingerprints for smartphone indoor positioning has become popular in recent years. Particle filter is often used to improve accuracy. However, most of existing particle filter based approaches either are heavily affected by motion estimation errors, which result in unreliable systems, or impose strong restrictions on smartphone such as fixed phone orientation, which are not practical for real-life use. In this paper, we present a novel indoor positioning system for smartphones, which is built on our proposed reliability-augmented particle filter. We create several innovations on the motion model, the measurement model, and the resampling model to enhance the basic particle filter. To minimize errors in motion estimation and improve the robustness of the basic particle filter, we propose a dynamic step length estimation algorithm and a heuristic particle resampling algorithm. We use a hybrid measurement model, combining a new magnetic fingerprinting model and the existing magnitude fingerprinting model, to improve system performance, and importantly avoid calibrating magnetometers for different smartphones. In addition, we propose an adaptive sampling algorithm to reduce computation overhead, which in turn improves overall usability tremendously. Finally, we also analyze the “Kidnapped Robot Problem” and present a practical solution. We conduct comprehensive experimental studies, and the results show that our system achieves an accuracy of 1~2 m on average in a large building.

Data replication technologies in distributed storage systems introduce the problem of data consistency. For high performance, data replication systems often settle for weak consistency models, such as Pipelined-RAM consistency. To determine whether a data replication system provides Pipelined-RAM consistency, we study the problem ofverifying Pipelined-RAM consistencyover read/write traces (VPC, for short). Four variants of VPC (labeled VPC-SU, VPC-MU, VPC-SD, and VPC-MD) are identified according to whether there are Multiple shared variables (or one Single variable) and whether write operations can assign Duplicate values (or only Unique values) to each shared variable. We prove that VPC-SD is$\sf {NP}$-complete (so is VPC-MD) by reducing the strongly$\sf {NP}$-complete problem3-Partitionto it. For VPC-MU, we present theRead-Centricalgorithm with time complexity$O(n^4)$, where$n$is the number of operations. The algorithm constructs an operation graph by iteratively applying a rule which guarantees that no overwritten values can be read later. It incrementally processes all the read operations one by one, and exploits the total order between the dictating writes on the same variable to avoid redundant applications of the rule. The experiments have demonstrated its practical efficiency and scalability.

Abstract Traditional fingerprint‐based localization techniques mainly rely on infrastructure support such as GSM and Wi‐Fi. They require war‐driving, which is both time‐consuming and labor‐intensive. With recent advances of smartphone sensors, sensor‐assisted localization techniques are emerging. However, they often need user‐specific training and more power intensive sensing, resulting in infeasible solutions for real deployment. In this paper, we present Barometer‐based floor Localization system (B‐Loc), a novel floor localization system to identify the floor level in a multi‐floor building on which a mobile user is located. It makes use of the barometer on smartphone. B‐Loc does not rely on any Wi‐Fi infrastructure and requires neither war‐driving nor prior knowledge of the buildings. Leveraging on crowdsourcing, B‐Loc builds the barometer fingerprint map, which contains the barometric pressure value for each floor level to locate users' floor levels. We conduct both simulation and field studies to demonstrate the accuracy, scalability, and robustness of B‐Loc. Our simulation shows that B‐Loc can locate the user fast and the field study in a 10‐floor building shows that B‐Loc achieves an accuracy of over 98%. Copyright © 2016 John Wiley & Sons, Ltd.

Contextual information is proven helpful to recommender system. And context-aware recommender system(CARS) has been applied in various applications. To improve the accuracy of context-aware recommendation and make recommender application development easier, we develop a lightweight software framework named ConRec, which introduces a dynamic context oriented approach to extend traditional reduction based recommender. This framework takes the dynamic nature of context into full consideration from different aspects to get better recommendation result. The dynamism of context exists in the process of context modeling, the computation of context weight and the handling of newly emergent context. In ConRec, context is dynamically modeled by clustering similar context values into one set automatically, rather than statically predefined by domain experts. Users' preferences to different types of context are explicitly measured through context weighting function based on real dataset. Moreover, ConRec supports incrementally adding new type of context to recommendation process, which reduces much cost of re-building the whole recommender model. Based on our improved reduction-based algorithm, ConRec is built as a highly scalable and reusable software framework for developing context-aware recommender applications. Finally, we evaluate our proposed approach on public datasets and get more accurate recommendation than traditional methods.

Debugging is challenging and labor-intensive. Debugging programs with weak or no oracle is even more difficult due to lack of passing and failing test runs as well as their comparisons. To address these challenges, we exploit metamorphic relations to construct new programs that are enhanced with synthesized oracle, and combine concolic testing and branch-switching debugging to localize potentially faulty places in original programs. We name our approach concolic metamorphic debugging (or Comedy for short). We experimentally evaluated Comedy with real-world Java programs. The experimental results reported that Comedy successfully generated debugging report for 88.4% of 2,330 faulty programs. The average branch distance between the reported locations and the real fault places is only 1.68. Besides, 36% of the debugging reports precisely locate the fault.

As applications deployed in a smart space share the same physical environment, they may interfere (or even conflict) with one another. To guarantee the performance and user experience of the entire smart space, mechanisms for handling such interferes (or conflicts) have to be introduced. We believe that conflicts among multiple applications are caused by their different requirements and impacts on the shared environment, and we model the conflict resolution problem as a Constraint Satisfaction Problem(CSP). We further propose a framework for managing and coordinating context-aware applications in a smart space, and provide an effective and efficient strategy to solve the corresponding CSP. Exhausted simulations are carried out to show the effectiveness of the proposed resolution strategy.

Smartphone applications are becoming increasingly popular. However, these applications can suffer limited power budgets or malfunctioned sensing issues from their host devices. Computation offloading addresses this issue by delegating local computation workloads to remote servers. In this paper, we present Cose Droid, a framework that supports dynamic computation- and sensing-offloading across different Android mobile devices. This enables Android applications to virtually "borrow" computation or sensing resources from other devices. We experimentally evaluated Cose Droid with real-world Android applications. The experimental results confirmed Cose Droid's effectiveness in on-demand offloading, as well as supporting sensor variety and spontaneous sensing recovery.

Inter-thread shared memory dependences are crucial to understanding the behavior of concurrent systems, as such dependences are the cornerstone of time-travel debugging and further predictive trace analyses. To enable effective and efficient shared memory dependence tracing, we present an optimistic scheme addressing the challenge of capturing exact dependences between unsynchronized events to reduce the probe effect of program instrumentation. Specifically, our approach achieved a wait-free fast path for thread-local reads on x86-TSO relaxed memory systems, and simultaneously achieved precise tracing of exact read-after-write, write-after-write and write-after-read dependences on the fly. We implemented an open-source RWTrace tool, and evaluation results show that our approach not only achieves efficient shared memory dependence tracing, but also scales well on a multi-core computer system.

Requirements traceability benefits many software engineering activities, such as change impact analysis and risk assessment. However, these activities require complete and correct traceability links which is not trivial, making traceability assessment an important field of study. In recent years, requirements traceability research has focused on using call dependencies within source code to understand how code properties contribute to the implementation of a requirement and to assess whether traceability links are correct and complete. These approaches largely ignore the role of existing data dependencies within the source code. That is, methods may never call each other, but may still depend upon another by sharing data. We identified five research questions and validated them on five software systems, covering 4 to 72 KLOC. We found that data dependencies are as relevant as call dependencies for assessing requirements traceability. Even more interesting, our analyses show that data dependencies complement call dependencies in the assessment. These findings have strong implications on code understanding, including trace capture, maintenance, and validation techniques. Copyright © 2015 John Wiley & Sons, Ltd.

Context-aware applications adapt their behavior based on contexts. Contexts can, however, be incorrect. A popular means to build dependable applications is to augment them with a set of constraints to govern the consistency of context values. These constraints are evaluated upon context changes to detect inconsistencies so that they can be timely handled. However, we observe that many context inconsistencies are unstable. They vanish by themselves and do not require handling. Such inconsistencies are detected due to misaligned sensor sampling or improper inconsistency detection scheduling. We call them unstable context inconsistencies (or STINs). STINs should be avoided to prevent unnecessary inconsistency handling and unstable behavioral adaptation to applications. In this article, we study STINs systematically, from examples to theoretical analysis, and present algorithms to suppress their detection. Our key insight is that only certain patterns of context changes can make a consistency constraint subject to the detection of STINs. We derive such patterns and proactively use them to suppress the detection of STINs. We implemented our idea and applied it to real-world applications. Experimental results confirmed its effectiveness in suppressing the detection of numerous STINs with negligible overhead, while preserving the detection of stable context inconsistencies that require inconsistency handling.

Software update in wireless sensor networks requires the ability of disseminating bulk data to specified sensors of a network with low latency in an energy efficient manner. This paper proposes a target-aware, transmission power-adaptive, and collision-free data dissemination protocol to fulfill these requirements. This protocol disseminates data to sensors of a network by first constructing a connected dominating set (CDS) in the network. We propose a target-aware CDS construction to exclude many unnecessary non-target sensors from the data dissemination process. By allowing some dominators of the CDS to increase their transmission power to disseminate data to more dominatees, the protocol efficiently reduces the total energy consumption. In addition, we propose a collision-based channel assignment strategy to eliminate communication collisions among dominators so as to reduce latency. We have implemented the protocol and evaluated it through simulations and a real application scenario. Our experimental results show that the proposed protocol at most reduces non-target sensors by 75.3%, total energy consumption by 57.1%, and latency by 39.8% compared to existing dissemination protocols.

Content-based communication is a novel communication paradigm that enables users to communicate with others based on message's content, instead of message's address. Groupware is a kind of software that supports coordination between individual users. An important feature of groupware is that the communication between the specified users is at a high frequency, which is determined by the applied coordination mechanism. Efficient communication in a groupware can support effective coordination between the users. This paper presents a topology-enhanced content-based network, which combines content-based communication with the topology between groupware users, to support content-based communication in groupware. We give a predicate-based method to define cooperation topology, which can effectively describe the topology between groupware users. We also propose a multi-level index structure to support efficient matching of cooperation topology in the forwarding mechanism of the proposed network. We implement the basic feature of our network and evaluate the prototype in a motivating scenario consisting of several coordination tasks. The results show that our method improves the message forwarding efficiency of 1 to 2 magnitude orders.

Mobile devices are gradually taking over traditional computers' dominance in human lives. With the ever-increasing shipment of mobile apps running on these devices, their quality issues become a severe challenge. Although automated testing techniques are being widely studied, they mostly fall short of handling mobile apps' complex interactions, e.g., A finger swipe or device shaking gesture, leading to inadequate testing. In this paper, we present a novel User Guided Automation (UGA) technique to address testing challenges incurred by such complex interactions. UGA exploits user insights to complement automated testing techniques by recording user-guided app executions, replaying apps to certain stop points, and systematically exploring state space from these stop points. We implemented our work as a prototype UGA tool on Android platform and evaluated it on seven real-world Android apps. Evaluation results show that UGA achieved 1.59-21.78× improvement in terms of method coverage over state-of-the-art automated techniques in testing mobile apps.

Applications in pervasive computing are often context-aware. However, due to uncontrollable environmental noises, contexts collected by applications can be distorted or even conflicting with each other. This is known as the context inconsistency problem. To provide reliable services, applications need to validate contexts before using them. One promising approach is to check contexts against consistency constraints at the runtime of applications. However, this can bring heavy computations due to tremendous amounts of contexts, thus leading to deteriorated performance to applications. Previous work has proposed incremental or concurrent checking techniques to improve the checking performance, but they heavily rely on CPU computing. In this paper, we propose a novel technique GAIN to exploit GPU computing to improve the checking performance. GAIN can automatically recognize parallel units in a constraint and schedule their checking in parallel on GPU cores. We evaluated GAIN with various constraints under different workloads. Our evaluation results show that, compared to CPU-based computing, GAIN saves CPU computing resources for pervasive applications while checks constraints much more efficiently.

Community Question Answering (CQA) sites have become valuable repositories that host a massive volume of human knowledge. How can we detect a high-value answer which clears the doubts of many users? Can we tell the user if the question s/he is posting would attract a good answer? In this paper, we aim to answer these questions from the perspective of the voting outcome by the site users. Our key observation is that the voting score of an answer is strongly positively correlated with that of its question, and such correlation could be in turn used to boost the prediction performance. Armed with this observation, we propose a family of algorithms to jointly predict the voting scores of questions and answers soon after they are posted in the CQA sites. Experimental evaluations demonstrate the effectiveness of our approaches.

Collaborative filtering is a fundamental building block in many recommender systems. While most of the existing collaborative filtering methods focus on explicit, multi-class settings (e.g., 1-5 stars in movie recommendation), many real-world applications actually belong to the one-class setting where user feedback is implicitly expressed (e.g., views in news recommendation and video recommendation). The main challenges in such one-class setting include the ambiguity of the unobserved examples and the sparseness of existing positive examples.

Using magnetic field data as fingerprints for localization in indoor environment has become popular in recent years. Particle filter is often used to improve accuracy. However, most of existing particle filter based approaches either are heavily affected by motion estimation errors, which makes the system unreliable, or impose strong restrictions on smartphone such as fixed phone orientation, which is not practical for real-life use. In this paper, we present an indoor localization system named MaLoc, built on our proposed augmented particle filter. We create several innovations on the motion model, the measurement model and the resampling model to enhance the traditional particle filter. To minimize errors in motion estimation and improve the robustness of particle filter, we augment the particle filter with a dynamic step length estimation algorithm and a heuristic particle resampling algorithm. We use a hybrid measurement model which combines a new magnetic fingerprinting model and the existing magnitude fingerprinting model to improve the system performance and avoid calibrating different smartphone magnetometers. In addition, we present a novel localization quality estimation method and a localization failure detection method to address the "Kidnapped Robot Problem" and improve the overall usability. Our experimental studies show that MaLoc achieves a localization accuracy of 1~2.8m on average in a large building.

Traditional fingerprint based localization techniques mainly rely on infrastructure support such as GSM, Wi-Fi or GPS. They work by war-driving the entire indoor spaces which is both time-consuming and labor-intensive. With recent advances of smartphone and sensing technologies, sensor-assisted localization techniques leveraging on mobile phone sensing are emerging. However, sensors are inherently noisy, making this technique challenging for real deployment. In this paper, we present F-Loc, a novel floor localization system to identify the floor level in a multi-floor building on which a mobile user is located. It does not need to war-drive the entire building. Leveraging on crowdsourcing and mobile phone sensing, we collect users' Wi-Fi traces and accelerometer readings. Through advanced clustering and cluster manipulating techniques, we are able to build the Wi-Fi map of the entire building, which can then be used for floor localization. We conduct both simulation and field studies to demonstrate the accuracy, scalability, and robustness of F-Loc. Our field study in a 10-floor building shows that F-Loc achieves an accuracy of over 98%.

Deterministic replay tools help programmers debug concurrent programs. However, for long-running programs, a replay tool may generate huge log of shared memory access dependences. In this paper, we present CARE, an application-level deterministic record and replay technique to reduce the log size. The key idea of CARE is logging read-write dependences only at per-thread value prediction cache misses. This strategy records only a subset of all exact read-write dependences, and reduces synchronizations protecting memory reads in the instrumented code. Realizing that such record strategy provides only value-deterministic replay, CARE also adopts variable grouping and action prioritization heuristics to synthesize sequentially consistent executions at replay in linear time. We implemented CARE in Java and experimentally evaluated it with recognized benchmarks. Results showed that CARE successfully resolved all missing read-write dependences, producing sequentially consistent replay for all benchmarks. CARE exhibited 1.7--40X (median 3.4X) smaller runtime overhead, and 1.1--309X (median 7.0X) smaller log size against state-of-the-art technique LEAP.

Self-adaptive applications address environmental dynamics systematically. They can be faulty and exhibit runtime errors when environmental dynamics are not considered adequately. It becomes more severe when uncertainty exists in their sensing and adaptation to environments. Existing work verifies self-adaptive applications, but does not explicitly consider environmental constraints or uncertainty. This gives rise to inaccurate verification results. In this paper, we address this problem by proposing a novel approach to verifying self-adaptive applications suffering uncertainty in their environmental interactions. It builds Interactive State Machine (ISM) models for such applications and verifies them with explicit consideration of environmental constraints and uncertainty. It then refines verification results by prioritizing counterexamples according to their probabilities. We experimentally evaluated our approach with real-life self-adaptive applications, and the experimental results confirmed its effectiveness. Our approach reported 200-660% more counterexamples than not considering uncertainty, and eliminated all false counterexamples caused by ignoring environmental constraints.

Community Question Answering (CQA) sites have become valuable platforms to create, share, and seek a massive volume of human knowledge. How can we spot an insightful question that would inspire massive further discussions in CQA sites? How can we detect a valuable answer that benefits many users? The long-term impact (e.g., the size of the population a post benefits) of a question/answer post is the key quantity to answer these questions. In this paper, we aim to predict the long-term impact of questions/answers shortly after they are posted in the CQA sites. In particular, we propose a family of algorithms for the prediction problem by modeling three key aspects, i.e., non-linearity, question/answer coupling, and dynamics. We analyze our algorithms in terms of optimality, correctness, and complexity. We conduct extensive experimental evaluations on two real CQA data sets to demonstrate the effectiveness and efficiency of our algorithms.

Traditional fingerprint based localization techniques mainly rely on infrastructure support such as GSM and Wi-Fi. They require war-driving which is both time-consuming and labor-intensive. With recent advances of smartphone sensors, sensor-assisted localization techniques are emerging. However, they often need user-specific training and more power intensive sensing, resulting in infeasible solutions for real deployment. In this paper, we present B-Loc, a novel floor localization system to identify the floor level in a multi-floor building on which a mobile user is located. It makes use of the barometer on smartphone only. B-Loc does not rely on any Wi-Fi infrastructure and requires neither war-driving nor prior knowledge of the buildings. Leveraging on crowd sourcing, B-Loc builds the barometer fingerprint map which contains the barometric pressure value for each floor level to locate users' floor levels. We conduct both simulation and field studies to demonstrate the accuracy, scalability, and robustness of B-Loc. Our field study in a 10-floor building shows that B-Loc achieves an accuracy of over 98%.

We have seen increasingly popularity in embedding barometer into smartphone today. A barometer measures the barometric pressure, and it can be used for a variety of applications. For example, in localization techniques, it is used to detect the altitude or altitude change of a user. Unfortunately, t

Traditional fingerprint based localization techniques mainly rely on infrastructure support such as RFID, Wi-Fi or GPS. They operate by war-driving the entire space which is both time-consuming and labor-intensive. In this paper, we present M-Loc, a novel infrastructure-free localization system to locate mobile users in a metro line. It does not rely on any Wi-Fi infrastructure, and does not need to war-drive the metro line. Leveraging crowdsourcing, we collect accelerometer, magnetometer and barometer readings on smartphones, and analyze these sensor data to extract patterns. Through advanced data manipulating techniques, we build the pattern map for the entire metro line, which can then be used for localization. We conduct field studies to demonstrate the accuracy, scalability, and robustness of M-Loc. The results of our field studies in 3 metro lines with 55 stations show that M-Loc achieves an accuracy of 93% when travelling 3 stations, 98% when travelling 5 stations.

Inferring the pair-wise trust relationship is a core building block for many real applications. State-of-the-art approaches for such trust inference mainly employ the transitivity property of trust by propagating trust along connected users, but largely ignore other important properties such as trust bias, multi-aspect, etc. In this paper, we propose a new trust inference model to integrate all these important properties. To apply the model to both binary and continuous inference scenarios, we further propose a family of effective and efficient algorithms. Extensive experimental evaluations on real data sets show that our method achieves significant improvement over several existing benchmark approaches, for both quantifying numerical trustworthiness scores and predicting binary trust/distrust signs. In addition, it enjoys linear scalability in both time and space.

The event stream model of computation has a wide range of applications, e.g, computer system monitoring, physical environment sensing/surveillance, and stock trade monitoring. Sliding windows are widely used to facilitate effective event stream processing. However, it is greatly challenged when the event sources are distributed and asynchronous. One important technique to cope with the asynchrony is to utilize that the meaningful snapshots of an asynchronous computation form a distributive lattice. It thus becomes the central challenge whether this lattice structure still preserves and how to maintain it at runtime, when we restrict our attention to events within sliding windows. To address this challenge, we first prove that the snapshots of the asynchronous event streams within the sliding windows form a convex distributive lattice (denoted by Lat-Win). This enables us to easily integrate existing predicate specification and detection techniques, to express and monitor properties of our concern over asynchronous event streams. Then we propose an algorithm to maintain Lat-Win at runtime. The proposed scheme is evaluated in a context-aware smart office scenario, where activities of the user can be recognized by monitoring multiple streams of sensed events. The Lat-Win algorithm is implemented on the open-source context-aware middleware we developed. The evaluation results first show the advantage of adopting sliding windows over asynchronous event streams. Then they show the performance of detecting specified predicates within Lat-Win, with dynamic changes in the computing environment.

Smartphone applications' energy efficiency is vital, but many Android applications suffer from serious energy inefficiency problems. Locating these problems is labor-intensive and automated diagnosis is highly desirable. However, a key challenge is the lack of a decidable criterion that facilitates automated judgment of such energy problems. Our work aims to address this challenge. We conducted an in-depth study of 173 open-source and 229 commercial Android applications, and observed two common causes of energy problems: missing deactivation of sensors or wake locks, and cost-ineffective use of sensory data. With these findings, wepropose an automated approach to diagnosing energy problems in Android applications. Our approach explores an application's state space by systematically executing the application using Java PathFinder (JPF). It monitors sensor and wake lock operations to detect missing deactivation of sensors and wake locks. It also tracks the transformation and usage of sensory data and judges whether they are effectively utilized by the application using our state-sensitive data utilization metric. In this way, our approach can generate detailed reports with actionable information to assist developers in validating detected energy problems. We built our approach as a tool, GreenDroid, on top of JPF. Technically, we addressed the challenges of generating user interaction events and scheduling event handlers in extending JPF for analyzing Android applications. We evaluated GreenDroid using 13 real-world popular Android applications. GreenDroid completed energy efficiency diagnosis for these applications in a few minutes. It successfully located real energy problems in these applications, and additionally found new unreported energy problems that were later confirmed by developers.

Runtime reconfigurations of component-based systems must be undertaken with careful considerations of dependency between components. The safer and less disruptive a reconfiguration strategy is, the more accurate dependency information it needs. This paper proposes to manage dynamic dependency between components with mealy machine automatically derived from the implementation of components. To maintain the current dependency information for a component at runtime, the corresponding machine is instrumented into the component implementation in such a way that it is always synchronized with the execution of the component. We implemented a prototypical tool for this approach and evaluated it with a realistic benchmark application. The results show that our approach achieves a high accuracy and keeps low overheads without introducing any manual work.

Service composition provides supports for automatic construction of required services on the fly from component services provided by different providers. In a smart space, as new providers may come in and existing ones may leave from time to time, the collection of available component services may change dynamically, resulting in broken compositions. Automatic reselection or recomposition mechanisms can be applied to fix broken compositions. However, they may introduce extra efforts and time and there are applications requiring (composed)services to be continuously available (at least) during a period of time, otherwise the applications would break down. Both the situations affect users' experience. If we could know how long each component service would be continuously available, we could optimize the composition process by reducing the frequency of broken compositions. In this paper we propose a scheme to achieve the goal. It utilizes presence-patterns of providers to estimate how long a component service may continuously available and it always selects the most continuously available composition that matches requirements. Simulations are carried out to show how and how well the presence-patterns based scheme work.

Internetware is envisioned as a new software paradigm where software developers usually need to interact with unknown partners as well as the software entities developed by them. To reduce uncertainty and boost collaborations in such setting, it is important to provide trustworthiness evaluation mechanisms so that trustworthy partners/entities can be easily found. In this work, we propose a novel trustworthiness evaluation mechanism by enhancing existing mechanisms with similarity and non-negative constraints. To be specific, we first extend an existing multi-aspect trust inference model by incorporating the non-negative constraint. One of the advantages of such constraint is its strong interpretability. Second, we incorporate similarity into two neighborhood models borrowed from recommender systems. When computing similarity, we make use of the intermediate results from the first step. Finally, these models are combined under a machine learning framework. To show the effectiveness of our method, we conduct experiments on a real data-set. The results show that: both our non-negativity extension and similarity computation improve the evaluation accuracy of the original methods, and the combined method outperforms several state-of-the-art methods.

Cyber-physical systems are systems that integrate the digital computational world with the real physical world, often using sensors and actuators as interfaces. There exist many application domains of cyber-physical systems such as autonomous systems, process control systems, robotic systems, and context-aware systems. The physical world is a complex and continuous world that changes in real-time while the computational world is a simplified and discrete world that often stores a delayed, likely inaccurate image of the physical world using sensory data. The mismatch between these two worlds poses unique challenges of developing software for cyber-physical systems.

Self-adaptive applications can easily contain faults. Existing approaches detect faults, but can still leave some undetected and manifesting into failures at runtime. In this paper, we study the correlation between occurrences of application failure and those of consistency failure. We propose fixing consistency failure to reduce application failure at runtime. We name this environment rematching, which can systematically reconnect a self-adaptive application to its environment in a consistent way. We also propose enforcing atomicity for application semantics during the rematching to avoid its side effect. We evaluated our approach using 12 self-adaptive robot-car applications by both simulated and real experiments. The experimental results confirmed our approach's effectiveness in improving dependability for all applications by 12.5-52.5%.

Trust inference, which is the mechanism to build new pair-wise trustworthiness relationship based on the existing ones, is a fundamental integral part in many real applications, e.g., e-commerce, social networks, peer-to-peer networks, etc. State-of-the-art trust inference approaches mainly employ the transitivity property of trust by propagating trust along connected users (a.k.a. trust propagation), but largely ignore other important properties, e.g., prior knowledge, multi-aspect, etc.

Formal specification and runtime detection of contextual properties is one of the primary approaches to enabling context awareness in pervasive computing environments. Due to the intrinsic dynamism of the pervasive computing environment, dynamic properties, which delineate concerns of context-aware applications on the temporal evolution of the environment state, are of great importance. However, detection of dynamic properties is challenging, mainly due to the intrinsic asynchrony among computing entities in the pervasive computing environment. Moreover, the detection must be conducted at runtime in pervasive computing scenarios, which makes existing schemes do not work. To address these challenges, we propose the property detection for asynchronous context (PDAC) framework, which consists of three essential parts: 1) Logical time is employed to model the temporal evolution of environment state as a lattice. The active surface of the lattice is introduced as the key notion to model the runtime evolution of the environment state; 2) Specification of dynamic properties is viewed as a formal language defined over the trace of environment state evolution; and 3) The SurfMaint algorithm is proposed to achieve runtime maintenance of the active surface of the lattice, which further enables runtime detection of dynamic properties. A case study is conducted to demonstrate how the PDAC framework enables context awareness in asynchronous pervasive computing scenarios. The SurfMaint algorithm is implemented and evaluated over MIPA--the open-source context-aware middleware we developed. Performance measurements show the accuracy and cost-effectiveness of SurfMaint, even when faced with dynamic changes in the asynchronous pervasive computing environment.

Practical software systems are subject to frequent updates for fixing their bugs or addressing new requirements. Updating a software system without stopping and restarting it is desired, as this helps reduce the redeployment cost as well as achieving the high availability. Existing techniques for dynamically updating Java programs may introduce noticeable pauses during which these programs are unable to function. We in this paper present Javelus, a dynamic Java update system with greatly reduced pausing time but without sacrificing update flexibility and system efficiency. Different from previous approaches, Javelus uses a lazy update mechanism with which an object-to-update will not be updated until it is really used. We implemented Javelus on top of an industry-strength OpenJDK HotSpot VM. We evaluated Javelus with real updates to Tomcat 7 and the same micro array benchmark used in evaluating Jvolve and DCE VM. The experiments report promising results that Javelus only incurred a pausing time two orders of magnitude smaller than those of Jvolve and DCE VM.

Self-adaptive systems are attractive due to their ability of adapting to changeable environments automatically. However, such systems may be subject to runtime failures when all environmental dynamics cannot be adequately considered at design time. When such failures occur at runtime, a system's internal adaptation logic usually has become inconsistent with its environment, according to our observation. We call this inconsistency sync-loss error. From our project experiences, we empirically identified a strong correlation between sync-loss error and system failure. This motivated us to fix sync-loss error in order to reduce failure for self-adaptive systems. In this paper, we formulate the problem of detecting sync-loss error, and present a framework ReSync to automatically fix sync-loss errors by desynchronizing a system with its environment. We experimentally evaluated ReSync on real robot cars with 20 different system versions. The evaluation reported promising results that ReSync can automatically recover our robot car systems from sync-loss errors, and significantly reduce the failure rate from 90.9% to 11.7-28.8%.

Trust inference is an essential task in many real world applications. Most of the existing inference algorithms suffer from the scalability issue, making themselves computationally costly, or even infeasible, for the graphs with more than thousands of nodes. In addition, the inference result, which is typically an abstract, numerical trustworthiness score, might be difficult for the end-user to interpret. In this paper, we propose sub graph extraction to address these challenges. The core of the proposed method consists of two stages: path selection and component induction. The outputs of both stages can be used as an intermediate step to speed up a variety of existing trust inference algorithms. Our experimental evaluations on real graphs show that the proposed method can accelerate existing trust inference algorithms, while maintaining high accuracy. In addition, the extracted sub graph provides an intuitive way to interpret the resulting trustworthiness score.

Detecting and resolving context inconsistency is critical to pervasive computing applications and infrastructures. Context inconsistency occurs when an application perceives contexts that breach predefined consistency constraints. This can drive an application to behave abnormally or even cause failure. Existing work commonly assumes the presence of a single application suffering from context inconsistency, such that specific repair actions can be taken to resolve the inconsistency for this application. However, when multiple applications run on the same infrastructure, they may impose conflicting requirements on resolving context inconsistency. In this paper, we propose a novel view-based approach ConsView to address such conflicting requirements. In ConsView, each application has a specific view to its own contexts that satisfy its own requirement on resolving context inconsistency. Such views are called consistent context views. We discuss the challenges of doing so and our ideas for addressing them. We implemented a prototype infrastructure supporting consistent context views, and evaluated it experimentally with simulated applications of real-life settings. The results confirmed the effectiveness and efficiency of our ConsView approach.

Using mobile devices, people can easily obtain their location information, and access a wide range of location based services (LBSs). Many existing LBSs rely in accurate, continuous, and real-time streams of location information to provide quality of service guarantees. In this case, even if an user accesses LBSs anonymously, the identity of the user can still be revealed by analyzing the mobility trace. To protect user privacy, existing work sacrifice the quality of LBSs by degrading spatial and temporal accuracy. To achieve a better tradeoff between user privacy and the quality of service, we present a novel approach, Complete Bipartite Anonymity (CBA), to confuse the paths of nearby users by connecting different users' real traces with fake ones. CBA protects user privacy as users become indistinguishable after their paths are confused, the quality of service of LBSs is also guaranteed since users are able to report their accurate locations. We evaluate CBA by comparing the system and privacy performance with existing techniques such as Path Confusion or Query Obfuscation using a real-world data set, the results show that our scheme increases the chance for a user joining an anonymity group by 10 times in low user density areas, and reduces the resources consumed by about 90% for achieving the same anonymity degree.

It is common practice for requirements traceability research to consider method call dependencies within the source code (e.g., fan-in/fan-out analyses). However, current approaches largely ignore the role of data. The question this paper investigates is whether data dependencies have similar relationships to requirements as do call dependencies. For example, if two methods do not call one another, but do have access to the same data then is this information relevant? We formulated several research questions and validated them on three large software systems, covering about 120 KLOC. Our findings are that data relationships are roughly equally relevant to understanding the relationship to requirements traces than calling dependencies. However, most interestingly, our analyses show that data dependencies complement call dependencies. These findings have strong implications on all forms of code understanding, including trace capture, maintenance, and validation techniques (e.g., information retrieval).

There are more and more services that fulfill similar functionality, such as image service provided by Flickr, Picasa and Facebook. Which should be adopted to construct our software system in the open, dynamic and non-deterministic Internet environment is a key problem. Earlier work[15, 9] analyze this problem from the point view of QoS and established generic and extensible QoS computation framework for service selection. However those framework are almost designed for individuals. As social network emerges and gets widespread, people tend to be more connected and self-organize themselves into groups. Benefits of all members should be considered when we select service for group. In this article, we propose a revised group recommendation algorithm which takes advantage of collaborative filtering technology for service selection. As the experiment demonstrates, our algorithm exhibits high accuracy.

Internetware applications are context-aware and adaptive to their environmental changes. Faulty adaptation may arise when these applications face unexpected situations. Such adaptation faults can be difficult to detect at design time. The recent Adaptation Finite-State Machine (A-FSM) approach proposes to statically analyze model-based context-aware applications for adaptation faults. However, this approach may suffer expressiveness and precision problems. To address these limitations, we propose an Adaptation Model (AM) approach. As compared with A-FSM, AM offers increased expressive power to model complex rules, and guarantees soundness in fault detection. Besides, AM deploys an efficient rule evaluation technique to cater for context-aware applications that are subject to continual environmental changes. We evaluated our AM approach using both simulated and real-world experiments with two applications. The experimental results confirmed that AM can detect real faults missed by A-FSM, and avoid false positives that were misreported otherwise.

Formal specification and runtime detection of temporal properties for pervasive context is one of the primary approaches to achieving context-awareness. Though temporal logics have been widely used in specification of temporal properties, they are faced with severe challenges in Pervasive Computing (PvC) scenarios. First, temporal logics are traditionally defined over infinite traces of possible system behavior. However in PvC scenarios, applications observe finite prefixes of (potentially infinite) traces of environment state evolution, and adapt their behavior accordingly. Second, specification and detection of temporal properties are challenged by the intrinsic asynchrony of PvC environments. Discussions above necessitate a systematic approach to formal specification and runtime detection of temporal properties for asynchronous context. To this end, we propose CTL3(3-valued Computation Tree Logic), which i) adopts 3-valued semantics to capture the inconclusiveness when applications only observe finite prefixes of environment state evolution; ii) inherits the notion of branching time to capture the uncertainty resulting from the asynchrony of PvC environments. A case study is conducted to demonstrate how CTL3supports context-awareness in PvC scenarios. The runtime checking algorithm of CTL3is implemented and evaluated over MIPA - the open-source context-aware middle-ware we developed. The case study demonstrates the necessity of adopting CTL3in PvC scenarios, while the performance measurements show the cost-effectiveness of runtime checking contextual properties in CTL3.

Mobile phone localization plays a key role in the fast-growing Location Based Applications domain. Most of the existing localization schemes rely on infrastructure support such as GSM, WiFi or GPS. In this paper, we present FTrack, a novel floor localization system to identify the floor level in a multi-floor building on which a mobile user is located. FTrack uses the mobile phone's accelerometer only without any infrastructure support. It does not require any prior knowledge of the building such as floor height. By capturing user encounters and analyzing user trails, FTrack finds the mapping from the traveling time (when taking the elevator) or the step counts (when walking on the stairs) between any two floors to the number of floor levels. The mapping can then be used for mobile users to pinpoint their current floor levels. We conduct both simulation and field studies to demonstrate the effectiveness of FTrack. Our field trial in a 10-floor building shows that FTrack achieves an accuracy of over 90% after two hours in our experiment.

Runtime detection of contextual properties is one of the primary approaches to enabling context-awareness in pervasive computing scenarios. Among various properties the applications may specify, the concurrency property, i.e., property delineating concurrency among contextual activities, is of great importance. It is because the concurrency property is one of the most frequently specified properties by context-aware applications. Moreover, the concurrency property serves as the basis for specification of many other properties. Existing schemes implicitly assume that context collecting devices share the same notion of time. Thus, the concurrency property can be easily detected. However, this assumption does not necessarily hold in pervasive computing environments, which are characterized by the asynchronous coordination among heterogeneous computing entities. To cope with this challenge, we identify and address three essential issues. First, we introduce logical time to model behavior of the asynchronous pervasive computing environment. Second, we propose the logic for specification of the concurrency property. Third, we propose the Concurrent contextual Activity Detection in Asynchronous environments (CADA) algorithm, which achieves runtime detection of the concurrency property. Performance analysis and experimental evaluation show that CADA effectively detects the concurrency property in asynchronous pervasive computing scenarios.

WS-BPEL processes can facilitate service discovery when the services have multiple interfaces in certain order. Current approaches derive the abstract WS-BPEL processes directly from the corresponding executable ones by hiding or omitting the internal activities. However, these simple approaches may prevent the services from being found by valuable potential partners at service discovery stage. To address this problem, we propose a novel approach to refactoring the executable and abstract WS-BPEL processes for service discovery. We show the application of our approach through a typical travel agency service.

There is an increasing demand for the runtime reconfiguration of distributed systems in response to changing environments and evolving requirements. Reconfiguration must be done in a safe and low-disruptive way. In this paper, we propose version consistency of distributed transactions as a safe criterion for dynamic reconfiguration. Version consistency ensures that distributed transactions be served as if there were operating on a single coherent version of the system despite possible reconfigurations that may happen meanwhile. The paper also proposes a distributed algorithm to maintain dynamic dependences between components at architectural level and enable low-disruptive version-consistent dynamic reconfigurations. An initial assessment through simulation shows the benefits of the proposed approach with respect to timeliness and low degree of disruption.

Recognizing human activities from sensor readings has recently attracted much research interest in pervasive computing due to its potential in many applications, such as assistive living and healthcare. This task is particularly challenging because human activities are often performed in not only a simple (i.e., sequential), but also a complex (i.e., interleaved or concurrent) manner in real life. Little work has been done in addressing complex issues in such a situation. The existing models of interleaved and concurrent activities are typically learning-based. Such models lack of flexibility in real life because activities can be interleaved and performed concurrently in many different ways. In this paper, we propose a novel pattern mining approach to recognize sequential, interleaved, and concurrent activities in a unified framework. We exploit Emerging Pattern-a discriminative pattern that describes significant changes between classes of data-to identify sensor features for classifying activities. Different from existing learning-based approaches which require different training data sets for building activity models, our activity models are built upon the sequential activity trace only and can be applied to recognize both simple and complex activities. We conduct our empirical studies by collecting real-world traces, evaluating the performance of our algorithm, and comparing our algorithm with static and temporal models. Our results demonstrate that, with a time slice of 15 seconds, we achieve an accuracy of 90.96 percent for sequential activity, 88.1 percent for interleaved activity, and 82.53 percent for concurrent activity.

The advances of wireless networking and sensor technology open up an interesting opportunity to infer human activities in a smart home environment. Existing work in this paradigm focuses mainly on recognizing activities of single user. In this work, we focus on the fundamental problem of recognizing activities of multiple users using a wireless body sensor network, and propose a scalable pattern mining approach to recognize both single- and multiuser activities in a unified framework. We exploit Emerging Pattern-a discriminative knowledge pattern which describes significant changes among activity classes of data-for building activity models and design a scalable, noise-resistant, Emerging Pattern-based Multiuser Activity Recognizer (epMAR) to recognize both single- and multiuser activities. We develop a multimodal, wireless body sensor network for collecting real-world traces in a smart home environment, and conduct comprehensive empirical studies to evaluate our system. Results show that epMAR outperforms existing schemes in terms of accuracy, scalability, and robustness.

The emerging participatory sensing applications have brought a privacy risk where users expose their location information. Most of the existing solutions preserve location privacy by generalizing a precise user location to a coarse-grained location, and hence they cannot be applied in those applications requiring fine-grained location information. To address this issue, in this paper we propose a novel method to preserve location privacy by anonymizing coarse-grained locations and retaining fine-grained locations using Attribute Based Encryption (ABE). In addition, we do not assume the service provider is an trustworthy entity, making our solution more feasible to practical applications. We present and analyze our security model, and evaluate the performance and scalability of our system.

Mobile devices are more and more popular in recent years. As a result, there're huge requests of mobile applications, especially those integrated with multiple information. However, on one hand, most of the mobile applications at present just contain some certain kinds of information and they cannot adapt to the rapid change of users' requirements, either. On the other hand, to build these applications, it's usually time consuming and there are not enough resource components with programmable interfaces. In this paper, we propose an approach based on Internerware to building web page integration applications for mobile device. We introduce a framework that provides abundant internet-programmable interfaces, a flexible integration mechanism to meet the users' rapid changing requirements and a reliable mechanism that guarantees the quality of the referred resources effectively. With this framework, we can rapidly build an application that integrates all the information according to users' requirement.

Self-adaptive software is expected to adjust itself attributes or structures at runtime in response to changes. Aiming at addressing some challenging problems such as difficult mathematically modeling software using the current control theoretical methods, we propose a novel fuzzy-control-based approach to achieve self-adaptive software, which is presented as framework of fuzzy self-adaptive software (FFSAS). In this framework, the general model, the implementation architecture, and the design methodology are put forward and discussed in detail. The fuzzy-control-based approach is evaluated with a news-website case study.

Real-time activity recognition using body sensor networks is an important and challenging task and it has many potential applications. In this paper, we propose a real time, hierarchical model to recognize both simple gestures and complex activities using a wireless body sensor network. In this model, we first use a fast, lightweight template matching algorithm to detect gestures at the sensor node level, and then use a discriminative pattern based real-time algorithm to recognize high-level activities at the portable device level. We evaluate our algorithms over a real-world dataset. The results show that the proposed system not only achieves good performance (an average precision of 94.9%, an average recall of 82.5%, and an average real-time delay of 5.7 seconds), but also significantly reduces the network communication cost by 60.2%.

One of the major applications of wireless ad hoc networks is to extend the Internet coverage and support pervasive and efficient data dissemination and sharing. To reduce data access cost and delay, caching has been widely used as an important technique. The efficiency of data access in caching systems largely depends on the cost for maintaining cache consistency, which can be high in wireless ad hoc networks due to network dynamism. Therefore, to make better trade-off between cache consistency and the cost incurred, it would be highly desirable to provide users the flexibility in specifying consistency requirements for their applications. In this paper, we propose a general consistency model called Probabilistic Delta Consistency (PDC), which integrates the flexibility granted by existing consistency models, covering them as special cases. We also propose the Flexible Combination of Push and Pull (FCPP) algorithm which satisfies user-specified consistency requirements under the PDC model. The analytical model of FCPP is used to derive the balance of minimizing the consistency maintenance cost and ensuring the specified consistency requirement. Extensive simulations are conducted to evaluate whether FCPP can satisfy arbitrarily specified consistency requirements, and whether FCPP works cost-effectively in dynamic wireless ad hoc networks. The evaluation results show that FCPP can adaptively tune itself to satisfy various user-specified consistency requirements. Moreover, it can save the traffic cost by up to 50 percent and reduce the query delay by up to 40 percent, compared with the widely used Pull with TTR algorithm.

Abstract Cooperative caching is an important technique to support pervasive Internet access. In order to ensure valid data access, the cache consistency must be maintained properly. However, this problem has not been sufficiently studied in mobile computing environments, especially those with ad hoc networks. There are two essential issues in cache consistency maintenance: consistency control initiation and data update propagation. Consistency control initiation not only decides the cache consistency provided to the users, but also impacts the consistency maintenance cost. This issue becomes more challenging in asynchronous and fully distributed ad hoc networks. To this end, we propose the predictive consistency control initiation (PCCI) algorithm, which adaptively initiates consistency control based on its online predictions of forthcoming data updates and cache queries. In order to efficiently propagate data updates through multi‐hop wireless connections, the hierarchical data update propagation (HDUP) algorithm is proposed. Theoretical analysis shows that cooperation among the caching nodes facilitates data update propagation. Extensive simulations are conducted to evaluate performance of both PCCI and HDUP. Evaluation results show that PCCI cost‐effectively initiates consistency control even when faced with dynamic changes in data update rate, cache query rate, node speed, and number of caching nodes. The evaluation results also show that HDUP saves cost for data update propagation by up to 66%. Copyright © 2009 John Wiley & Sons, Ltd.

Internetware is envisioned as a new software paradigm for resource integration and sharing in the open, dynamic and autonomous network environment. In this paper we discuss our visions and explorations of this new paradigm, with focus placed on the methodological perspective. A set of enabling techniques on flexible coordination of autonomous services, automatic adaptation to changing environment and trust management-based assurance of dependability are proposed to help the development of Internetware applications.

Service-oriented computing is a promising approach to software system construction by selecting and composing autonomous services under the open, dynamic and non-deterministic Internet environment. Appropriate selection of high quality services used in from numerous candidates declaring similar functionalities is crucial to the overall quality of the composed system. As authority centers are not generally available in open environments, reputation-based mechanisms must be adopted to evaluate services. With more and more reputation systems proposed in the literature, there is an increasing need to evaluate and compare them objectively and systematically with a common controlled experiment of trust network environment. In this paper we propose a general simulation framework based on dynamic trust network for this purpose. Especially, the framework is capable to simulate the dynamic evolutions of the trust network, in addition to the static snapshots of the trust relationships. With this framework, some case studies are made to evaluate the effectiveness of several representative reputation mechanisms, and some interesting characters are revealed.

This demo displays the use of the prototypical ARTEMIS middleware system, which is developed at Nanjing University to support the construction, execution and evolution of applications in the open, dynamic and decentralized network environment of the Internet. To adapt to such a new environment, software application systems must be more flexible, more reactive, and more evolvable than before [1]. Built upon services from autonomous external sources, these application systems also have to explicitly consider the trustworthiness of the services. With these considerations, this version of ARTEMIS middleware is featured by its support for (1) multiple coordination modes based on various software architecture styles; (2) dynamic software architecture-based online reconfigurations, in reaction to the runtime changes in the environment and requirements; (3) trustworthiness evaluation at both the service level and the system level, which helps users to ensure and improve user's satisfaction on the system constructed.

Understanding and recognizing human activities from sensor readings is an important task in pervasive computing. Existing work on activity recognition mainly focuses on recognizing activities for a single user in a smart home environment. However, in real life, there are often multiple inhabitants l

Understanding and recognizing human activities from sensor readings is an important task in pervasive computing. In this paper, we investigate the fundamental problem of recognizing activities for multiple users from sensor readings in a home environment, and propose a novel pattern mining approach

Recognizing human activities from sensor readings has recently attracted much research interest in pervasive computing. This task is particularly challenging because human activities are often performed in not only a simple (i.e., sequential), but also a complex (i.e., interleaved and concurrent) manner in real life. In this paper, we propose a novel emerging patterns based approach to sequential, interleaved and concurrent activity recognition (epSICAR). We exploit emerging patterns as powerful discriminators to differentiate activities. Different from other learning-based models built upon the training dataset for complex activities, we build our activity models by mining a set of emerging patterns from the sequential activity trace only and apply these models in recognizing sequential, interleaved and concurrent activities. We conduct our empirical studies in a real smart home, and the evaluation results demonstrate that with a time slice of 15 seconds, we achieve an accuracy of 90.96% for sequential activity, 87.98% for interleaved activity and 78.58% for concurrent activity.

Contexts, the pieces of information that capture the characteristics of computing environments, are often inconsistent in the dynamic and uncertain pervasive computing environments. Various schemes have been proposed to check context consistency for pervasive applications. However, existing schemes implicitly assume that the contexts being checked belong to the same snapshot of time. This limitation makes existing schemes do not work in pervasive computing environments, which are characterized by the asynchronous coordination among computing devices. The main challenge imposed on context consistency checking by asynchronous environments is how to interpret and detect concurrent events. To this end, we propose in this paper the concurrent events detection for asynchronous consistency checking (CEDA) algorithm. An analytical model, together with corresponding numerical results, is derived to study the performance of CEDA. We also conduct extensive experimental evaluation to investigate whether CEDA is desirable for context-aware applications. Both theoretical analysis and experimental evaluation show that CEDA accurately detects concurrent events in time in asynchronous pervasive computing environments, even with dynamic changes in message delay, duration of events and error rate of context collection.

Due to the dynamic and anonymous nature of open environments, it is critically important for agents to identify trustful cooperators which work consistently as they claim. In the e-services and e-commerce communities, trust and reputation systems are applied broadly as one kind of decision support systems, and aim to cope with the consistency problems caused by uncertain trust relationships. However, challenges still exist: on the one hand, we require more flexible trust computation models to satisfy various personal requirements since agents in these communities are heterogeneous; on the other hand, trust and reputation systems calculate the trustworthiness of agents based on the agents' past behavior. The open environments are dynamic, agents are anonymous and the records about agents' past behavior are distributed in the environments, so agents have to search the required records through the environments due to their lack of valid information. Thus, efficient, scalable and effective information collection strategies are required to address these issues. In this paper we present a distributed trust and reputation system to cope with the challenges. We propose a novel and flexible trust computation model based on artificial neural networks. With the advantages of ANN, our trust model tunes the parameters automatically to adapt to various personal requirements. We propose a broker-assisting information collection strategy based on clustering method. With the support of brokers, subcommunities are managed by reputation mechanism in an efficient and scalable way and help their members collect information with high quality. We show the performance of our trust and reputation system by simulation.

Context-awareness is a key issue in pervasive computing. Context-aware applications are prone to the context consistency problem, where applications are confronted with conflicting contexts and cannot decide how to adapt themselves. In pervasive computing environments, users are often willing to accept certain degree of context inconsistency, as long as it can reduce the consistency maintenance cost, e.g., query delay and battery power. However, existing consistency maintenance schemes do not enable the users to make such tradeoffs. To this end, we propose the probabilistic consistency checking for pervasive context (PCCPC) algorithm. Detailed performance analysis shows that PCCPC enables the users to check consistency over arbitrarily specified ratio of context. We also conduct experiments to study the cost reduced by probabilistic checking. The analytical and the experimental results show that PCCPC enables the users to efficiently make tradeoffs between context consistency and the associated checking cost.

Facing changing environments and evolving business rules, composite services ought to be adaptable, even at run-time. Existing mainstream service composition languages and execution engines exhibit insufficient support for variability and adaptability to cater for dynamic changes. Research efforts have been put on the extension of the languages and argumentation of the engines. However, how to ensure the correctness for the adaptation of a running composite service instance and minimize unnecessary re-execution of component services remains a challenge. To address this problem, we propose a model-based approach that allows run-time adaptation of composite services. It is based on an instance transfer mechanism that transfers an active instance of the old service composition schema to a appropriate state of the new schema. Algorithms are proposed to find the appropriate destination states of the transformation. After the migration, the suspended instances can resume their execution according to the new schema. An example based on a FindRoute composite service is also included.

Location Based Service (LBS) is one kind of ubiquitous applications whose functions are based on the locations of clients. The core of LBS is an effective positioning system. As wireless LAN (WLAN) costs less and is easy to access, using WLAN for indoor positioning has been widely studied recently. K nearest neighbors (KNN) is one of the basic deterministic fingerprint based algorithms and widely used for WLAN-based indoor positioning. However, KNN takes all the nearest K neighbors for calculating the estimated result, which could be improved if some selective work could be done to those neighbors beforehand. In this paper we propose a new scheme called "cluster filtered KNN" (CFK). CFK utilizes clustering technique to partition those neighbors into different clusters and chooses one cluster as the delegate. In the end, the final estimate can be calculated only based on the elements of the delegate. With experiments, we found that CFK does outperform KNN.

The value-based software process (VBSP) is gaining more and more attention. However, the quantitative analysis techniques for VBSPs could not closely follow up the fast developing paces of the modeling techniques. In this paper, we proposes a decision-based stochastic extension of object petri nets (OPN) to resolve the issues. OPNs are well suited for modeling VBSPs and stochastic object petri nets (SOPN) combine the benefits of OPNs and the stochastic theory. The decision-based stochastic object petri net (DB-SOPN) model is economics driven and links value creation with decision making, multi-stakeholder satisfying, and risk management. It includes two levels: the high level models the guideline of the software process life cycle; and the low-level represents the different stakeholder's perspectives of the process. Some activities of a process have candidate policies that will produce different value reward. Our model simulates the entire software process, and compares various combinations of candidate policies to make the value reward of the process maximum.

Building large-scale smart environments is one of the long-term goals of ubiquitous computing. The widespread of context information in such environments necessitates an effective context retrieval mechanism. This paper proposes a novel context retrieval method based on applications' query patterns. We propose high dimensional vector to model contexts from applications' perspective, and apply the normalized inner product of high dimensional vectors to measure context distance. Contexts with similar query patterns are clustered into the same group. To improve the performance of context retrieval, we build distributed indices on each node to speed up a local search, and create shortcuts based on clustering results to facilitate query routing. We show how our proposed methods can be applied to existing context retrieval mechanisms. Our experimental results show that our method can significantly reduce retrieval cost.

Pervasive computing is to enhance the environment by embedding many computers that are gracefully integrated with human users. To achieve this, the key research thrust is to create a smart context-awareness environment which should enclose various users and satisfy different needs of the users. Building such smart environments is still difficult and complex due to lacking a uniform infrastructure that can adapt to diverse smart domains. To address this problem, we propose a context-aware computing infrastructure, called FollowMe. Our infrastructure integrates an ontology based context model and a workflow based application model with the OSGi framework. By plugging different domain contexts and applications, FollowMe can be customized to various domains.

Commercial organizations increasingly need software processes sensitive to business value, quick to apply, and capable of early analysis for subprocess consistency and compatibility. This paper presents experience in applying a lightweight synthesis of a Value-Based Software Quality Achievement (VBSQA) process and an Object-Petri-Net-based process model (called VBSQA-OPN) to achieve a manager-satisfactory process for software quality achievement in an on-going ERP software project in China. The results confirmed that 1) the application of value-based approaches was inherently better than value-neutral approaches adopted by most ERP software projects; 2) the VBSQA-OPN model provided project managers with a synchronization and stabilization framework for process activities, success-critical stakeholders and their value propositions; 3) process visualization and simulation tools significantly increased management visibility and controllability for the success of software project.

PSEE (Process-centered Software Engineering Environment) can manage and monitor software process. Software process modeling language is a core element in PSEE system. Due to the particularity and the complexity, software process model includes multi-views: activity view, product view and role view, which should be considered in modeling software process. Based on the similarity between multi-view software process modeling and object Petri nets, this paper proposes the MOPN-SP-net model which is a multi-view software process model based on multi-object Petri nets. The model includes twolevel models: system net and object net. A multi-view paradigm including activity views and product views is provided. Activity views are described by system nets and product views are described by object nets. MOPN-SP-net includes multi-views of software process model, which is characterized with clearer hierarchy, simpler structure, and more extendibility.

Open service gateway initiative (OSGi), a service-oriented component model which follows the concepts of service-oriented programming, significantly reduces the time and complexity to construct applications by registering and discovering services. However, this mechanism focusing on the interfaces and static properties of related services, ignores the behavior of the services, let alone the runtime errors caused by behavior inconsistency. In addition to the related theory of service behavior model and behavior consistency relation of single services in service discovery and substitution, this article defines coordination protocol, composite service and behavior consistent service coordination to handle the applications built on multiple services. On the top of OSGi, we propose a feasible middleware architecture called SOBECA, which includes a runtime environment and a development toolkit to facilitate the development of service behavior consistent applications.

The requirement for modifying system structure during system execution is specified by dynamic software architectures. The system architecture style should remain one style or transform within a scope so that some constraints need to be imposed on during the system execution. Our work expands such an idea along two directions in the setting of formalism. The first direction is to model the system by a graph-based calculus stressing the structure. The other direction lies in that we tailor spatial logic to be a suitable logic as the system specification for structure. The model and specification are basis for the model checking algorithm that is to verify whether the system evolution satisfies some structure constraints. We invite a master-slave architecture style as a running example from the beginning and throughout the paper to demonstrate our approach. Such work can be seen as the basis of the structure analysis for architectures.

The open and dynamic Internet environment greatly urges software entities that are distributed on different locations to coordinate with each other to accomplish a computing task. Software architecture is applied to abstract the software entities to be components and the coordination between them to be connectors and then a model is extracted as the architecture on which the design, analysis and verification are based. Currently, the notion of dynamic software architectures that can modify their architecture and enact modifications during the system execution has become one of the most active research areas. In this paper, we focus on the dynamic evolution of system structure other than coordination mechanisms (e.g. communication protocols). It is widely recognized that some restrictions should be imposed on the system evolution to ensure that the system structure may remain one style or transform within a scope. These conditions, to a large extent, make the system execute under control as expected.

The /spl pi/-calculus is one of the most important mobile process calculi and has been well studied in literature. Temporal logic is thought of as a good compromise between description convenience and abstraction and can support useful computational applications, such as model-checking. We use a symbolic transition graph inherited from /spl pi/-calculus to model concurrent systems. A wide class of processes, that is, finite-control processes, can be represented as a finite symbolic transition graph. A new version of modal logic for the /spl pi/-calculus, an extension of the modal /spl mu/-calculus with Boolean expressions over names, and primitives for name input and output are introduced as an appropriate temporal logic for the /spl pi/-calculus. Since we make a distinction between proposition and predicate, the possible interactions between recursion and first-order quantification can be solved. A concise semantics interpretation for our modal logic is given. Based on this work, we provide a model checking algorithm for the logic. This algorithm follows Winskel's well known tag set method to deal with the fixpoint operator. As for the problem of name instantiating, our algorithm follows the 'on-the-fly' style, and systematically employs schematic names. The correctness of the algorithm is shown.

Two of the fundamental issues in designing protocols for message passing between mobile agents (MAs) are tracking the migration of the target agent and forwarding messages to it. Even with an ideal fault-free network-transport mechanism, messages can be dropped during MA migration. Therefore, in order to provide reliable message delivery, protocols need to overcome message loss caused by asynchronous operations of agent migration and message forwarding. In this paper, two known message forwarding approaches, namely push and pull, are explored to design adaptive and reliable message delivery protocols. Based on a commonly used MA tracking model, the pros and cons of these two approaches are evaluated, both qualitatively and quantitatively. The comparative performance evaluation is presented in terms of network traffic and delay in message processing. We also propose improvements to the pull approach to reduce network traffic and the message delay. We conclude that with different message passing and migration patterns and varying requirements of real-time message processing, specific applications can select different message delivery approaches to achieve the desired level of performance and flexibility.

Abstract This paper presents a graph‐oriented framework, called WebGOP, for architecture modeling and programming of Web‐based distributed applications. WebGOP is based on the graph‐oriented programming (GOP) model, under which the components of a distributed program are configured as a logical graph and implemented using a set of operations defined over the graph. WebGOP reshapes GOP with a reflective object‐oriented design, which provides powerful architectural support in the World Wide Web environment. In WebGOP, the architecture graph is reified as an explicit object which itself is distributed over the network, providing a graph‐oriented context for the execution of distributed applications. The programmer can specialize the type of graph to represent a particular architecture style tailored for an application. WebGOP also has built‐in support for flexible and dynamic architectures, including both planned and unplanned dynamic reconfiguration of distributed applications. We describe the WebGOP framework, a prototypical implementation of the framework on top of SOAP, and a performance evaluation of the prototype. The prototype demonstrated the feasibility of our approach. Results of the performance evaluation showed that the overhead introduced by WebGOP over SOAP is reasonable and acceptable. Copyright © 2003 John Wiley & Sons, Ltd.

This paper presents a mailbox-based scheme for designing flexible and adaptive message delivery protocols in mobile agent (MA) systems. The scheme associates each mobile agent with a mailbox while allowing the decoupling between them, i.e., a mobile agent can migrate to a new site without bringing its mailbox. By separating the concerns of locating the mailbox of a mobile agent and delivering a message to the agent, we obtain a large space of protocol design with flexibility. Using a three-dimensional model based on the scheme, we have developed a taxonomy of MA communication protocols, which not only covers, as special cases, several known MA message delivery protocols, but also allows for the design of new ones well suited for various application requirements. We describe such an efficient and adaptive protocol derived front the model. The protocol guarantees reliable delivery of messages to mobile agents. We analyze the design trade-offs and performance of the protocol, using an analytic model as well as extensive simulation experiments.

Two of the fundamental issues in message passing between mobile agents are tracking the migration of the target agent and delivering messages to it. In order to provide reliable message delivery, protocols are needed to overcome message loss caused by asynchronous operations of agent migration and message forwarding. In this paper, two message forwarding approaches, namely push and pull, are explored to design adaptive and reliable message delivery protocols. The pros and cons of these two approaches are evaluated, both qualitatively and quantitatively. The comparative performance evaluation is in terms of network traffic and delay in message processing. We also propose improvements to the pull approach to reduce network traffic and the message delay. We conclude that with different communication and migration patterns and requirements of real-time message processing, specific applications can select different message delivery approaches to achieve the desired level of performance and flexibility.

This paper presents a novel approach, called WebGOP, for architecture modeling and programming of web-based distributed applications. WebGOP uses the graph-oriented programming (GOP) mode, under which the components of a distributed program are configured as a logical graph and implemented using a set of operations defined over the graph. WebGOP extends the application of GOP to the World Wide Web environment and provides more powerful architectural support. In WebGOP, the architecture graph is reified as an explicit object which itself is distributed over the network providing a graph-oriented context for the execution of distributed applications. The programmer can specialize the type of a graph to represent a particular architecture style tailored for an application. WebGOP also has built-in support for flexible and dynamic architectures, including dynamic reconfiguration. We describe the WebGOP framework, a prototypical implementation of the framework on top of SOAP, and performance evaluation of the prototype. Results of the performance evaluation showed that the overhead introduced by WebGOP over SOAP is reasonable and acceptable.

Software coordination is central to the construction of large-scale high-performance distributed applications with software services scattered over the decentralized Internet. In this paper, a new mobile-agent-based architecture is proposed for the utilization and coordination of geographically distributed computing resources. Under this architecture, a user application is built with a set of software agents that can travel across the network autonomously. These agents utilize the distributed resources and coordinate with each other to complete their task. This approach’s advantages include the natural expression and flexible deployment of the coordination logic, the dynamic adaptation to the network environment and the potential of better application performance. This coordination architecture, together with an object-oriented hierarchical parallel application framework and a graphical application construction tool, is implemented in the HOOPE environment, which provides a systematic support for the development and execution of Internet-based distributed and parallel applications in the petroleum exploration industry.