Cyber-physical systems (CPS) and Internet-of-Things (IoT) devices are increasingly being deployed across multiple functionalities, ranging from healthcare devices and wearables to critical infrastructures, e.g., nuclear power plants, autonomous vehicles, smart cities, and smart homes. These devices are inherently not secure across their comprehensive software, hardware, and network stacks, thus presenting a large attack surface that can be exploited by hackers. In this article, we present an innovative technique for detecting unknown system vulnerabilities, managing these vulnerabilities, and improving incident response when such vulnerabilities are exploited. The novelty of this approach lies in extracting intelligence from known real-world CPS/IoT attacks, representing them in the form of regular expressions, and employing machine learning (ML) techniques on this ensemble of regular expressions to generate new attack vectors and security vulnerabilities. Our results show that 10 new attack vectors and 122 new vulnerability exploits can be successfully generated that have the potential to exploit a CPS or an IoT ecosystem. The ML methodology achieves an accuracy of 97.4% and enables us to predict these attacks efficiently with an 87.2% reduction in the search space. We demonstrate the application of our method to the hacking of the in-vehicle network of a connected car. To defend against the known attacks and possible novel exploits, we discuss a defense-in-depth mechanism for various classes of attacks and the classification of data targeted by such attacks. This defense mechanism optimizes the cost of security measures based on the sensitivity of the protected resource, thus incentivizing its adoption in real-world CPS/IoT by cybersecurity practitioners.

Two major considerations when encoding pseudo-Boolean (PB) constraints into SAT are the size of the encoding and its propagation strength, that is, the guarantee that it has a good behaviour under unit propagation. Several encodings with propagation strength guarantees rely upon prior compilation of the constraints into DNNF (decomposable negation normal form), BDD (binary decision diagram), or some other sub-variants. However it has been shown that there exist PB-constraints whose ordered BDD (OBDD) representations, and thus the inferred CNF encodings, all have exponential size. Since DNNFs are more succinct than OBDDs, preferring encodings via DNNF to avoid size explosion seems a legitimate choice. Yet in this paper, we prove the existence of PB-constraints whose DNNFs all require exponential size.

Constraint Satisfaction Problems (CSPs) play a central role in many applications in Artificial Intelligence and Operations Research. In general, solving CSPs is NP-complete. The structure of CSPs is best described by hypergraphs. Therefore, various forms of hypergraph decompositions have been proposed in the literature to identify tractable fragments of CSPs. However, also the computation of a concrete hypergraph decomposition is a challenging task in itself. In this paper, we report on recent progress in the study of hypergraph decompositions and we outline several directions for future research.

Compared with constraint satisfaction problems, counting problems have received less attention. In this paper, we survey research works on the problems of counting the number of solutions to constraints. The constraints may take various forms, including, formulas in the propositional logic, linear inequalities over the reals or integers, Boolean combination of linear constraints. We describe some techniques and tools for solving the counting problems, as well as some applications (e.g., applications to automated reasoning, program analysis, formal verification and information security).

In this paper, we investigate CNF encodings, for which unit propagation is strong enough to derive a contradiction if the encoding is not consistent with a partial assignment of the variables (unit refutation complete or URC encoding) or additionally to derive all implied literals if the encoding is consistent with the partial assignment (propagation complete or PC encoding). We prove an exponential separation between the sizes of PC and URC encodings without auxiliary variables and strengthen the known results on their relationship to the PC and URC encodings that can use auxiliary variables. Besides of this, we prove that the sizes of any two irredundant PC formulas representing the same function differ at most by a factor polynomial in the number of the variables and present an example of a function demonstrating that a similar statement is not true for URC formulas. One of the separations above implies that a q-Horn formula may require an exponential number of additional clauses to become a URC formula. On the other hand, for every q-Horn formula, we present a polynomial size URC encoding of the same function using auxiliary variables. This encoding is not q-Horn in general.

We explore the potential of continuous local search (CLS) in SAT solving by proposing a novel approach for finding a solution of a hybrid system of Boolean constraints. The algorithm is based on CLS combined with belief propagation on binary decision diagrams (BDDs). Our framework accepts all Boolean constraints that admit compact BDDs, including symmetric Boolean constraints and small-coefficient pseudo-Boolean constraints as interesting families. We propose a novel algorithm for efficiently computing the gradient needed by CLS. We study the capabilities and limitations of our versatile CLS solver, GradSAT, by applying it on many benchmark instances. The experimental results indicate that GradSAT can be a useful addition to the portfolio of existing SAT and MaxSAT solvers for solving Boolean satisfiability and optimization problems.

Combinatorial problems stated as Constraint Satisfaction Problems (CSP) are examined. It is shown by example that any algorithm designed for the original CSP, and involving the AllDifferent constraint, has at least the same level of efficacy when simultaneously applied to both the original and its complementary problem. The 1-to-1 mapping employed to transform a CSP to its complementary problem, which is also a CSP, is introduced. This "Dual CSP" method and its application are outlined. The analysis of several random problem instances demonstrate the benefits of this method for variable domain reduction compared to the standard approach to CSP. Extensions to additional constraints other than AllDifferent, as well as the use of hybrid algorithms, are proposed as candidates for this Dual CSP method.

Machine learning models have been successfully used in many scientific and engineering fields. However, it remains difficult for a model to simultaneously utilize domain knowledge and experimental observation data. The application of knowledge-based symbolic AI represented by an expert system is limited by the expressive ability of the model, and data-driven connectionism AI represented by neural networks is prone to produce predictions that violate physical mechanisms. In order to fully integrate domain knowledge with observations, and make full use of the prior information and the strong fitting ability of neural networks, this study proposes theory-guided hard constraint projection (HCP). This model converts physical constraints, such as governing equations, into a form that is easy to handle through discretization, and then implements hard constraint optimization through projection. Based on rigorous mathematical proofs, theory-guided HCP can ensure that model predictions strictly conform to physical mechanisms in the constraint patch. The performance of the theory-guided HCP is verified by experiments based on the heterogeneous subsurface flow problem. Due to the application of hard constraints, compared with fully connected neural networks and soft constraint models, such as theory-guided neural networks and physics-informed neural networks, theory-guided HCP requires fewer data, and achieves higher prediction accuracy and stronger robustness to noisy observations.

Many techniques have been developed for itemset mining problems. Famous examples are mining frequent itemsets (Agrawal et al., 1993; Han et al., 2000), mining association rules (Agrawal et al., 1993; Szathmary et al., 2007), mining closed itemsets(Pasquier et al., 1999), mining high utility itemsets (Chan et al., 2003), etc. Most of these works have focused on improving the practical performance of the mining process, but few have conducted a theoretical analysis of the computational complexity of itemset mining problems. Wijsen and Meersman (1998) have proved that it is NPcomplete to decide whether there exists a valid quantitative rule. Angiulli et al. (2001) have proved that the problem of deciding whether there exists a non-redundant association rule of size at least k that is frequent and the problem of deciding whether there exists a non-redundant association rule of size at least k that is confident are both NPcomplete.

There is a need for socially assistive robots (SARs) to provide transparency in their behavior by explaining their reasoning. Additionally, the reasoning and explanation should represent the user's preferences and goals. To work towards satisfying this need for interpretable reasoning and representations, we propose the robot uses Analogical Theory of Mind to infer what the user is trying to do and uses the Hint Engine to find an appropriate assistance based on what the user is trying to do. If the user is unsure or confused, the robot provides the user with an explanation, generated by the Explanation Synthesizer. The explanation helps the user understand what the robot inferred about the user's preferences and why the robot decided to provide the assistance it gave. A knowledge-driven approach provides transparency to reasoning about preferences, assistance, and explanations, thereby facilitating the incorporation of user feedback and allowing the robot to learn and adapt to the user.