The integrity of sensor datasets used in smart home applications is crucial for tasks like activity recognition and automation. We identify common validity issues such as event ordering errors, lifecycle inconsistencies, and data corruption, which are often overlooked but can significantly affect the reliability of analyses. We present a toolbox based on the BeepBeep stream processing library that enables efficient verification of 19 sanity checks on data streams. Our analysis of 15 publicly available smart home datasets collected by five different research teams reveals that most of them violate key assumptions about sensor behavior, emphasizing the need for pre-validation.

The Boolean Matrix Factorization (BMF) problem aims to represent a n×m Boolean matrix as the Boolean product of two matrices of small rank k, where the product is computed using Boolean algebra operations. However, finding a BMF of minimum rank is known to be NP-hard, posing challenges for heuristic algorithms and exact approaches in terms of rank found and computation time, particularly as matrix size or the number of entries equal to 1 grows. In this paper, we present a new approach to simplifying the matrix to be factorized by reducing the number of 1-entries, which allows to directly recover a Boolean factorization of the original matrix from its simplified version. We introduce two types of simplification: one that performs numerous simplifications without preserving the original rank and another that performs fewer simplifications but guarantees that an optimal BMF on the simplified matrix yields an optimal BMF on the original matrix. Furthermore, our experiments show that our approach outperforms existing exact BMF algorithms.

Code smells are the result of poor design choices within software systems that complexify source code and impede evolution and performance. Therefore, detecting code smells within software systems is an important priority to decrease technical debt. Furthermore, the emergence of mobile applications (apps) has brought new types of Android-specific code smells, which relate to limitations and constraints on resources like memory, performance and energy consumption. Among these Android-specific smells are those that describe inappropriate behaviour during the execution that may negatively impact software quality. Static analysis tools, however, show limitations for detecting these behavioural code smells and properly detecting behavioural code smells requires considering the dynamic behaviour of the apps. To dynamically detect behavioural code smells, we hence propose three contributions : (1) A method, the Dynamicsmethod, a step-by-step method for the specification and dynamic detection of Android behavioural code smells; (2) A tool, the Dynamicstool, implementing this method on seven code smells; and (3) A validation of our approach on 538 apps from F-Droidwith a comparison with the static analysis detection tools,aDoctorand Paprika, from the literature. Our method consists of four steps: (1) the specification of the code smells, (2) the instrumentation of the app, (3) the execution of the apps, and (4) the detection of the behavioural code smells. Our results show that many instances of code smells that cannot be detected with static detection tools are indeed detected with our dynamic approach with an average precision of 92.8% and an average recall of 53.4%.

The k-undercover Boolean matrix factorization problem aims to approximate a m×n Boolean matrix X as the Boolean product of an m×k and a k×n matrices A◦B such that X is a cover of A◦B, i.e., no representation error is allowed on the 0’s entries of the matrix X. To infer an optimal and “block-optimal” k-undercover, we propose two exact methods based on MaxSAT encodings. From a theoretical standpoint, we prove that our method of inferring “block-optimal” k-undercover is a (1 - 1/e) ≈ 0.632 approximation for the optimal k-undercover problem. From a practical standpoint, experimental results indicate that our “block-optimal” k-undercover algorithm outperforms the state-of-the-art even when compared with algorithms for the more general k-undercover Boolean Matrix Factorization problem for which only minimizing reconstruction error is required.

Abstract While the back-and-forth method has been often attributed to Cantor, it turns out that in the original proof of the characterisation of countable linear dense orders, the mapping is constructed in a single direction. Cameron has called this method Forth and has shown that it can fail to build an automorphism for some homogeneous structures. We give in this paper a characterisation of those homogeneous structures for which Forth always builds an automorphism. This generalises results by Cameron and McLeish.

Configuration Logic (CL) is a formal language that allows a network engineer to express constraints in terms of the actual parameters found in the configuration of network devices. There exists an efficient algorithm that can automatically check a pool of devices for conformance to a set of CL constraints; moreover, this algorithm can point to the part of the configuration responsible for the error when a constraint is violated. A CL validation engine has been integrated into a network management tool called ValidMaker. We show on a simple use case scenario based on Virtual Local Area Networks how representative formal constraints can be expressed with CL and efficiently validated with ValidMaker.

An anomaly in a firewall is a relationship between two of its rules that may hint at a possible misconfiguration of its filter. One notable limitation of existing solutions for firewall analysis is that they provide algorithms tailored for the verification of specific anomalies. We introduce a modal logic, called Visibility Logic (VL), which can be used to express arbitrary patterns between rules inside a firewall. A model checker allows one to verify any formula expressed in visibility logic, of which traditional anomalies are merely particular instances, with running times of under one second for 1,500 rules.

An increasing number of popular SOAP web services exhibit a stateful behavior, where a successful interaction is determined as much by the correct format of messages as by the sequence in which they are exchanged with a client. The set of such constraints forms a "message contract” that needs to be enforced on both sides of the transaction; it often includes constraints referring to actual data elements inside messages. We present an algorithm for the runtime monitoring of such message contracts with data parameterization. Their properties are expressed in {\rm LTL}\hbox{-}{\rm FO}^+, an extension of Linear Temporal Logic that allows first-order quantification over the data inside a trace of XML messages. An implementation of this algorithm can transparently enforce an {\rm LTL}\hbox{-}{\rm FO}^+ specification using a small and invisible Java applet. Violations of the specification are reported on-the-fly and prevent erroneous or out-of-sequence XML messages from being exchanged. Experiments on commercial web services from Amazon.com and Google indicate that {\rm LTL}\hbox{-}{\rm FO}^+ is an appropriate language for expressing their message contracts, and that its processing overhead on sample traces is acceptable both for client-side and server-side enforcement architectures.

Rule-based filters are sequences of rules formed of a condition and a decision. Rules are applied sequentially up to the first fulfilled condition, whose matching decision determines the outcome. Such filters are particularly useful in network management, where they filter packets allowed to flow in or out of an interface. Properties of filters which either reveal or hint to misconfiguration (anomalies) have been largely studied in the network management community. We show that in fact such properties are of a spatial and temporal nature. Accordingly we introduce a spatio-temporal language appropriate for filter properties, use it to describe major filter anomalies and finally prove that verifying a property in this language can be done in time polynomial in the number of filter rules.

Most works that extend workflow validation beyond syntactical checking consider constraints on the sequence of messages exchanged between services. These constraints are expressed only in terms of message names and abstract away their actual data content. We provide examples of real-world “data-aware” Web service constraints where the sequence of messages and their content are interdependent. To this end, we present {\rm CTL}\hbox{-}{\rm FO}^+, an extension over Computation Tree Logic that includes first-order quantification on message content in addition to temporal operators. We show how {\rm CTL}\hbox{-}{\rm FO}^+ is adequate for expressing data-aware constraints, give a sound and complete model checking algorithm for {\rm CTL}\hbox{-}{\rm FO}^+, and establish its complexity to be PSPACE-complete. A “naive” translation of {\rm CTL}\hbox{-}{\rm FO}^+ into CTL leads to a serious exponential blowup of the problem that prevents existing validation tools to be used. We provide an alternate translation of {\rm CTL}\hbox{-}{\rm FO}^+ into CTL, where the construction of the workflow model depends on the property to validate. We show experimentally how this translation is significantly more efficient for complex formulas and makes model checking of data-aware temporal properties on real-world Web service workflows tractable using off-the-shelf tools.

We present an algorithm for the runtime monitoring of business process properties with data parameterization. The properties are expressed in LTL-FO+, an extension to traditional Linear Temporal Logic that includes full first-order quantification over the data inside a trace of XML messages. The algorithm works "on-the-fly": it keeps in memory only the states that are necessary at each step. Initial results indicate that LTL-FO+ is an appropriate language for expressing data dependencies on message traces and that its processing overhead on sample traces is acceptable.

Configuration Logic (CL) is a fragment of XQuery that allows first-order quantification over node labels. In this paper, we study CL satisfiability and seek a deterministic decision procedure to build models of satisfiable CL formulae. To this end, we show how to revert CL satisfiability into an equivalent CTL satisfiability problem in order to leverage existing model construction algorithms for CTL formulae.

Most works that extend workflow validation beyond syntactical checking consider constraints on the sequence of messages exchanged between services. However, these constraints are expressed only in terms of message names and abstract away their actual data content. Using the context of the User-controlled Lightpath initiative (UCLP) hosted by the CANARIE consortium, we provide examples of real- world "data-aware" web service constraints where the sequence of messages and their content are interdependent. We present CTL-FO+, an extension over Computation Tree Logic that includes first-order quantification on state variables in addition to temporal operators. We show how CTL- FO+is adequate for expressing data-aware constraints, give a complete model checking algorithm for CTL-FO+and establish its complexity to be PSPACE-complete. This makes using CTL-FO+for validating workflow properties no harder than using the Linear Temporal Logic (LTL) already used by some web service tools. Finally, we show how the modelling of data-aware properties is an increase in expressiveness that cannot be efficiently simulated by these tools.

Querying and efficiently validating properties on labelled tree structures has become an important part of research in numerous domains. In this paper, we show how a fragment of XPath called configuration logic (CL) can be embedded into computation tree logic. This framework embeds into CTL a larger subset of XPath than previous work and in particular allows universally and existentially quantified variables in formulas. Finally, we show how the variable binding mechanism of CL can be seen as a branching-time equivalent of the "freeze" quantifier

We introduce a logical formalism for describing properties of configurations of computing systems. This logic of trees allows quantification on node labels, which are modalities containing variables. We explain the motivation behind our formalism and give both a classical semantics and a new equivalent one based on partial functions on variables.

Abstract We generalize to theories of modules (complete or not) a result of U. Felgner stating that a complete theory of abelian groups is a Horn theory if and only if it is closed under products. To prove this we show that a reduced product of modules ΠFMi (i ϵ I) is elementarily equivalent to a direct product of ultraproducts of the modules Mi(i ϵ I).