ABSTRACT Self‐adaptive applications are becoming increasingly attractive, with the ability to smartly understand their runtime environments (or contexts) and deliver adaptive services, for example, location‐aware navigation or resource‐sensitive suggestions. However, due to inherent noises in the process of sensing and interpreting environmental information, there is a growing demand for guarding the consistency of collected contexts to avoid application misbehaviour and, at the same time, minimize extra costs. Existing work attempted to achieve this by speeding up the kernel constraint checking module inside the consistency guarding process. Most of these efforts were spent on reusing previous checking results or parallelizing the checking process, but they all leave one central step of constraint checking, that is, link generation, untouched. In this step, the checking engine provides reasons to explain the violation of constraints under check. It occupies a substantial part of the total time cost. Focusing on this key link generation step, we proposed MG, which deploys a rigourous analysis to automatically identify and avoid redundancy in the link generation without harming any correctness of the checking results. MG has been proven sound (always guaranteeing correctness) and complete (entirely removing redundancy). Moreover, based on our observation that MG's redundancy elimination also assists another core step of constraint checking to reduce unnecessary computation further, we additionally enhance MG with an escape‐condition optimization to escape unnecessary evaluation of truth values to further improve the efficiency of constraint checking in an aspect other than link generation. We call it MG+ for distinguishing. Our experiments with synthesized and real‐world consistency constraints reported that, compared with existing work, MG eliminates all link redundancy (83% to 0%), and based on it, MG+ further reduces significant truth value calculations (e.g., 49.74% reduction when combined with ECC and Con‐C). Generally, MG brought 14–500 speed‐ups in link generation, and MG+ further made 1.2–1.9 speed‐ups in truth value evaluation. Altogether, MG reduced the total constraint checking time up to 45.4%, and MG+ reduced it up to 61.0%.

Constraint checking techniques are being widely used for ensuring the consistency of software artifacts during their development and evolution (e.g., detecting inconsistency in an application's running contexts or identifying rule violation in the code being developed). Typically, consistency constraints are formulated and checked upon the changes of software artifacts under checking. When any constraint is violated, an inconsistency is said to occur and then follow-up actions can be taken to remedy the problem. Currently, various constraint checking techniques have been proposed and implemented with sophisticated mechanisms for higher efficiency and scalability. However, these implementations could be far from being well tested due to their oracle problems, i.e., hardly able to tell what the checking result should be, given any software artifacts and their consistency constraints to check. In this paper, we leverage metamorphic testing and propose a family of metamorphic relations catered for testing constraint checking implementations. We dedicatedly design these relations by following the sensitivity principle via a fine-granularity control and the diversity principle via input-oriented transformations. Our experiments reported promising results (disclosing 80 % mutation bugs and five real bugs) without the need of any manual labeling.

Python projects grow quickly by code reuse and building automation based on third-party libraries. However, the version constraints associated with these libraries are prone to mal-configuration, and this forms a major obstacle to correct project building (known as dependency-conflict (DC) building failure). Our empirical findings suggest that such mal-configured version constraints were mainly prepared manually, and could essentially be refined for better quality to improve the chance of successful project building. We propose a LooCo approach to refining Python projects’ library version constraints by automatically loosening them to maximize their solutions, while keeping the libraries to observe their original behaviors. Our experimental results with real-life Python projects report that LooCo could efficiently refine library version constraints (0.4s per version loosening) by effective loosening (5.5 new versions expanded on average) automatically, and transform 54.8% originally unsolvable cases into solvable ones (i.e., successful building) and significantly increase solutions (21 more on average) for originally solvable cases.

Nowadays applications are getting increasingly attractive by being capable of adapting their behaviors based on their understanding to running environments (a.k.a. contexts). However, such capability can be subject to illness or even unexpected crash, when contexts, for suffering environmental noises, become inaccurate or even conflict with each other. Fortunately, various constraint checking techniques have been proposed to validate contexts against consistency constraints, in order to guard context consistency for applications in a timely manner. However, with the growth of environmental dynamics and context volume, it is getting more and more challenging to check context consistency in time. In this paper, we propose a novel approach, INFuse, to soundly fuse together two lines of techniques, namely, incremental checking and concurrent checking, for efficient constraint checking. Realizing such check fusion has to address the challenges rising from the gap between the micro analysis for reusable elements in incremental checking and the macro collection of parallel tasks in concurrent checking. INFuse solves the challenges by automatically deciding maximal concurrent boundaries for context changes under checking (i.e., what-correctness problem), and soundly fusing incremental and concurrent checking for context consistency (i.e., how-correctness problem), with theoretical guarantees. Our experimental evaluation with real-world data shows that INFuse could improve constraint checking efficiency by 18.6x–171.1x, as compared with existing state-of-the-art techniques.

Adaptive applications rely on conditions about their environments (or contexts) to deliver smart services, e.g., location-aware services. Due to inherent noises in environmental sensing and interpretation, there is an increasing demand for guarding the consistency of contexts to avoid application misbehavior, and at the same time minimizing the guarding cost. Existing work has tried to reduce the cost by speeding up the kernel constraint checking module inside the consistency guarding process. Most efforts have been spent on reusing previous checking results or checking constraints in parallel, while leaving untouched one central problem of link generation, the step that consumes a substantially large part of the total time cost for explaining why constraints have been violated. In this paper, we propose a novel technique, MG, to automatically identify and remove redundant link generation, without harming any checking result. We show that MG is sound (always checking correctly) and complete (removing all redundancy). Our experiments with synthesized and real-world consistency constraints reported that compared with existing work, MG achieved significant efficiency improvements on the link generation (tens to hundreds times speedup), and could reduce the total constraint checking time up to 45.4%.

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

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

Context-Aware Systems (a.k.a. CASs) integrate cyber and physical space to provide context-aware adaptive functionalities. Building context-aware systems is challenging due to the uncertainty of the real physical environment. Therefore, input validation for context-aware systems plays a significant role in keeping the systems executing safely. Input validation approaches have been proposed to monitor and guard the executions of context-aware systems. However, few of these works (17%, 2 out of 12) evaluated their approaches with a real context-aware system in a real physical environment. In this paper, we study and compare the effectiveness of input validation approaches for context-aware system in both a simulated and a physical environment. We built a testing platform, RM-Testing, based on DJI RoboMaster S1 robot car. We implemented three up-to-date input validation approaches, and evaluated their effectiveness in improving the success rate of the robot car’s executions. The results show that the selected input validation approaches are effective in guarantee the safe execution of context-aware systems, which improve the success rate by 82% in the simulated environment, and 50% in the physical environment. However, the effectiveness of these approaches does vary in different environment. Thus, we believe that such CASs-based input validation works should be evaluated in the physical environment to better validate their effectiveness and usefulness.

Software systems assisted with deep neural networks (DNNs) are gaining increasing popularities. However, one outstanding problem is to judge whether a given application scenario suits a DNN model, whose answer highly affects its concerned system's performance. Existing work indirectly addressed this problem by seeking for higher test coverage or generating adversarial inputs. One pioneering work is SynEva, which exactly addressed this problem by synthesizing mirror programs for scenario suitableness evaluation of general machine learning programs, but fell short in supporting DNN models. In this paper, we propose VISION to eValuatIng Scenario suItableness fOr DNN models, specially catered for DNN characteristics. We conducted experiments on a real-world self-driving dataset Udacity, and the results show that VISION was effective in evaluating scenario suitableness for DNN models with an accuracy of 75.6-89.0% as compared to that of SynEva, 50.0-81.8%. We also explored different meta-models in VISION, and found out that the decision tree logic learner meta-model could be the best one for balancing VISION's effectiveness and efficiency.

Spreadsheets are widely used but subject to various defects. In this paper, we present SGuard to effectively detect spreadsheet defects. SGuard learns spreadsheet features to cluster cells with similar computational semantics, and then refines these clusters to recognize anomalous cells as defects. SGuard well balances the trade-off between the precision (87.8%) and recall rate (71.9%) in the defect detection, and achieves an F-measure of 0.79, exceeding existing spreadsheet defect detection techniques. We introduce the SGuard implementation and its usage by a video presentation (https://youtu.be/gNPmMvQVf5Q), and provide its public download repository (https://github.com/sheetguard/sguard).

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.

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.

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.

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.