Search

The adoption of Artificial Neural Networks (ANNs) in safety-related applications is often avoided because it is difficult to rule out possible misbehaviors with traditional analytical or probabilistic techniques. In this paper we present N eV er, our tool for checking safety of ANNs. N eV er encodes the problem of verifying safety of ANNs into the problem of satisfying corresponding Boolean combinations of linear arithmetic constraints. We describe the main verification algorithm and the structure of N eV er. We present also empirical results confirming the effectiveness of N eV er on realistic case studies. [ABSTRACT FROM AUTHOR]

The increasing digitization and datification of all aspects of people's daily life, and the consequent growth in the use of personal data, are increasingly challenging the current development and adoption of Machine Learning (ML). First, the sheer complexity and amount of data available in these applications strongly demands for ML algorithms that can be trained directly on complex structures, which can be naturally described by graphs. In fact, graphs inherently capture information about entities, their attributes, and relationships between them. Directly applying ML to graphs relieves domain experts and data scientists from the challenging and time-consuming problem of designing a suitable vector-based data representation used by classical ML techniques. Second, ML algorithms should not only be designed to achieve high technical and functional standards; as the automated decisions provided by these algorithms can have a relevant impact on people's lives, their behavior has to be aligned with the values and principles of individuals and society. This demands for designing automated algorithms that we, as humans, can trust, fulfilling the requirements of fairness, robustness, privacy, and explainability. Third, designing effective ML algorithms requires skills and expertise developed at different levels. This substantially hinders the democratization and widespread availability of such technology for society at large, which in turn demands for improving the level of automatization and systematization of their design process, while also providing guarantees on their performance. For this reason, this paper provides an overview of the current works focused towards learning trustworthily, automatically, and with guarantees on graphs. [ABSTRACT FROM AUTHOR]

Research literature on Probabilistic Model Checking (PMC) encompasses a well-established set of algorithmic techniques whereby probabilistic models can be analyzed. In the last decade, owing to the increasing availability of effective tools, PMC has found applications in many domains, including computer networks, computational biology and robotics. In this paper, we evaluate PMC tools - namely COMICS, MRMC and PRISM - to investigate safe reinforcement learning in robots, i.e., to establish safety of policies learned considering feedback signals received upon acting in partially unknown environments. Introduced in previous contributions of ours, this application is a challenging domain wherein PMC tools act as back-engines of an automated methodology aimed to verify and repair control policies. We present an evaluation of the current state-of-the-art PMC tools to assess their potential on various case studies, including both real and simulated robots accomplishing navigation, manipulation and reaching tasks. [ABSTRACT FROM AUTHOR]

The best currently available solvers for quantified Boolean formulas (QBF5) process their input in prenex form, i.e., all the quantifiers have to appear in the prefix of the formula separated from the purely propositional part representing the matrix. However, in many QBF5 derived from applications, the propositional part is intertwined with the quantifier structure. To tackle this problem, the standard approach is to convert such QBFs in prenex form, thereby losing structural information about the prefix. In the case of search-based solvers, the prenex-form conversion introduces additional constraints on the branching heuristic and reduces the benefits of the learning mechanisms. In this paper, we show that conversion to prenex form is not necessary: current search-based solvers can be naturally extended in order to handle nonprenex QBFs and to exploit the original quantifier structure. We highlight the two mentioned drawbacks of the conversion in prenex form with a simple example, and we show that our ideas can also be useful for solving QBFs in prenex form. To validate our claims, we implemented our ideas in the state-of-the-art search-based solver QuBE and conducted an extensive experimental analysis. The results show that very substantial speedups can be obtained. [ABSTRACT FROM AUTHOR]

Planning as satisfiability is a very efficient technique for classical planning, i.e., for planning domains in which both the effects of actions and the initial state are completely specified. In this paper we present C-sat, a SAT-based procedure capable of dealing with planning domains having incomplete information about the initial state, and whose underlying transition system is specified using the highly expressive action language C. Thus, C-sat allows for planning in domains involving (i) actions which can be executed concurrently; (ii) (ramification and qualification) constraints affecting the effects of actions; and (iii) nondeterminism in the initial state and in the effects of actions. We first prove the correctness and the completeness of C-sat, discuss some optimizations, and then we present C-plan, a system based on C-sat. C-plan works on any C planning problem, but some optimizations have not been fully implemented yet. Nevertheless, the experimental analysis shows that SAT-based approaches to planning with incomplete information are viable, at least in the case of problems with a high degree of parallelism. [Copyright &y& Elsevier]

The implementation of effective reasoning tools for deciding the satisfiability of Quantified Boolean Formulas (QBFs) is an important research issue in Artificial Intelligence. Many decision procedures have been proposed in the last few years, most of them based on the Davis, Logemann, Loveland procedure (DLL) for propositional satisfiability (SAT). In this paper we show how it is possible to extend the conflict-directed backjumping schema for SAT to the satisfiability of QBFs: When applicable, conflict-directed backjumping allows search to skip over existentially quantified literals while backtracking. We introduce solution-directed backjumping, which allows the same behavior for universally quantified literals. We show how it is possible to incorporate both conflict-directed and solution-directed backjumping in a DLL-based decision procedure for satisfiability of QBFs. We also implement and test the procedure: The experimental analysis shows that, because of backjumping, significant speed-ups can be obtained.Summing up: We present the first algorithm that applies conflict and solution directed backjumping to QBF, and demonstrate the performance of this algorithm via an empirical study. [Copyright &y& Elsevier]

A substantial effort is underway to make robots useful outside controlled environments and without direct human supervision. In practice, this can happen only after a rigorous certification process which ensures that several requirements, e.g., operation safety, are met. Automated verification of control programs can be part of cost-effective methodologies to support certification, but it is widely recognized as difficult to attain in robotics, because of several traits that characterize robot design and implementation. One such trait is the widespread usage of middleware to implement control programs in a distributed fashion. In these cases, the challenge of verification is made steep mainly by the fact that the correctness of control software depends on middleware components whose structured models might not be available, or too difficult to obtain from their documentation. Our proposal is to ease the application of automated verification techniques by identifying abstract middleware models in the form of finite-state automata. The identification procedure is itself largely automated, and the only prerequisite is for the middleware to be available for controlled experimentation. Once middleware models are computed, behaviors that would lead to unsafe operation can be spotted automatically on a composition of identified middleware and control software models using model checking techniques. The approach is based on our tool AIDE – Automata IDentification Engine – to identify abstract middleware models, and the model checker SPIN to verify control units. To validate our approach, we consider four different case studies built on YARP publish–subscribe middleware. Our results confirm that AIDE enables the extension of precise engineering methods to distributed control software in robotics. [ABSTRACT FROM AUTHOR]

Twelve years have elapsed since the first Quantified Boolean Formulas (QBFs) evaluation was held as an event linked to SAT conferences. During this period, researchers have striven to propose new algorithms and tools to solve challenging formulas, with evaluations periodically trying to assess the current state of the art. In this paper, we present an experimental account of solvers and formulas with the aim to understand the progress in the QBF arena across these years. Unlike typical evaluations, the analysis is not confined to the snapshot of submitted solvers and formulas, but rather we consider several tools that were proposed over the last decade, and we run them on different formulas from previous QBF evaluations. The main contributions of our analysis, which are also the messages we would like to pass along to the research community, are: (i) many formulas that turned out to be difficult to solve in past evaluations, remain still challenging after twelve years, (ii) there is no single solver which can significantly outperform all the others, unless specific categories of formulas are considered, and (iii) effectiveness of preprocessing depends both on the coupled solver and the structure of the formula. [ABSTRACT FROM AUTHOR]

In recent years, Satisfiability Modulo Theory (SMT) solvers are becoming increasingly popular in the Computer Aided Verification and Reasoning community. Used natively or as back-engines, they are accumulating a record of success stories and, as witnessed by the annual SMT competition, their performances and capacity are also increasing steadily. Introduced in previous contributions of ours, a new application domain providing an outstanding challenge for SMT solvers is represented by verification of Multi-Layer Perceptrons (MLPs) a widely-adopted kind of artificial neural network. In this paper we present an extensive evaluation of the current state-of-the-art SMT solvers and assess their potential in the promising domain of MLP verification. [ABSTRACT FROM AUTHOR]

From an empirical point of view, the hardness of quantified Boolean formulas (QBFs), can be characterized by the (in)ability of current state-of-the-art QBF solvers to decide about the truth of formulas given limited computational resources. In this paper, we start from the problem of computing empirical hardness markers, i.e., features that can discriminate between hard and easy QBFs, and we end up showing that such markers can be useful to improve our understanding of QBF preprocessors. In particular, considering the connection between classes of tractable QBFs and the treewidth of associated graphs, we show that (an approximation of) treewidth is indeed a marker of empirical hardness and it is the only parameter which succeeds consistently in being so, even considering several other purely syntactic candidates which have been successfully employed to characterize QBFs in other contexts. We also show that treewidth approximations can be useful to describe the effect of QBF preprocessors, in that some QBF solvers benefit from a preprocessing phase when it reduces the treewidth of their input. Our experiments suggest that structural simplifications reducing treewidth are a potential enabler for the solution of hard QBF encodings. [ABSTRACT FROM AUTHOR]

In this paper we compare the performance of all the currently available suites to evaluate and certify QBFs. Our aim is to assess the current state of the art, and also to understand to which extent QBF encodings can be evaluated producing certificates that can be checked in a reliable and efficient way. We conclude that, while the evaluation of some QBFs is still an open challenge, producing and checking certificates for many medium-to-large scale QBFs is feasible with the current technology. [ABSTRACT FROM AUTHOR]