Goto

Collaborating Authors

Logic & Formal Reasoning


Facebook Fellow Spotlight: Shaping the future with neural program synthesis and adversarial ML - Facebook Research

#artificialintelligence

Each year, PhD students from around the world apply for the Facebook Fellowship, a program designed to encourage and support promising doctoral students who are engaged in innovative and relevant research in areas related to computer science and engineering. Fellowship recipients receive tuition funding for up to two years to conduct their research at their respective universities, independently of Facebook. To learn about award details, eligibility, and more, visit the program page below. Xinyun is a PhD student at UC Berkeley working with Professor Dawn Song and is expected to graduate in 2022. Her research explores the intersection of deep learning, programming languages, and security, focused on neural program synthesis and adversarial machine learning (ML).



Formal Software Verification Measures Up

Communications of the ACM

The modern world runs on software. However, there is a catch: computer code often contains programming errors--some small, some large. These glitches can lead to unexpected results--and systematic failures. "In many cases, software flaws don't make any difference. In other cases, they can cause massive problems," says Kathleen Fisher, professor and chair of the computer science department at Tufts University and a former official of the U.S. Defense Advanced Research Projects Agency (DARPA).


Program Verification

Communications of the ACM

In 1969, Tony Hoare published a classical Communications' article, "An Axiomatic Basis for Computer Programming." Hoare's article culminated a sequence of works by Turing, McCarthy, Wirth, Floyd, and Manna, whose essence is an association of a proposition with each point in the program control flow, where the proposition is asserted to hold whenever that point is reach. Hoare added two important elements to that approach. First, he described a formal logic, now called Hoare Logic, for reasoning about programs. Second, he offered a compelling vision for the program-verification project: "When the correctness of a program, its compiler, and the hardware of the computer have all been established with mathematical certainty, it will be possible to place great reliance on the results of the program, and predict their properties with a confidence limited only by the reliability of the electronics."


Knowing How to Plan

arXiv.org Artificial Intelligence

Various planning-based know-how logics have been studied in the recent literature. In this paper, we use such a logic to do know-how-based planning via model checking. In particular, we can handle the higher-order epistemic planning involving know-how formulas as the goal, e.g., find a plan to make sure p such that the adversary does not know how to make p false in the future. We give a PTIME algorithm for the model checking problem over finite epistemic transition systems and axiomatize the logic under the assumption of perfect recall.


Defeasible Reasoning via Datalog$^\neg$

arXiv.org Artificial Intelligence

Hardware architectures can range from the use of GPUs and other hardware accelerators, through multi-core multi-threaded architectures, to shared-nothing cloud computing. Causes for failure to exploit these architectures include lack of expertise in the architectural features, lack of manpower more generally, and difficulty in updating legacy systems. Such problems can be ameliorated by mapping a logic to logic programming as an intermediate language. This is a common strategy in the implementation of defeasible logics. The first implementation of a defeasible logic, d-Prolog, was implemented as a Prolog meta-interpreter (Covington et al. 1997). Courteous Logic Programs (Grosof 1997) and its successors LPDA (Wan et al. 2009), Rulelog (Grosof and Kifer 2013), Flora2 (Kifer et al. 2018), are implemented in XSB (Swift and Warren 2012).


Querying in the Age of Graph Databases and Knowledge Graphs

arXiv.org Artificial Intelligence

Graphs have become the best way we know of representing knowledge. The computing community has investigated and developed the support for managing graphs by means of digital technology. Graph databases and knowledge graphs surface as the most successful solutions to this program. This tutorial will provide a conceptual map of the data management tasks underlying these developments, paying particular attention to data models and query languages for graphs.


MILP, pseudo-boolean, and OMT solvers for optimal fault-tolerant placements of relay nodes in mission critical wireless networks

arXiv.org Artificial Intelligence

In critical infrastructures like airports, much care has to be devoted in protecting radio communication networks from external electromagnetic interference. Protection of such mission-critical radio communication networks is usually tackled by exploiting radiogoniometers: at least three suitably deployed radiogoniometers, and a gateway gathering information from them, permit to monitor and localise sources of electromagnetic emissions that are not supposed to be present in the monitored area. Typically, radiogoniometers are connected to the gateway through relay nodes. As a result, some degree of fault-tolerance for the network of relay nodes is essential in order to offer a reliable monitoring. On the other hand, deployment of relay nodes is typically quite expensive. As a result, we have two conflicting requirements: minimise costs while guaranteeing a given fault-tolerance. In this paper, we address the problem of computing a deployment for relay nodes that minimises the relay node network cost while at the same time guaranteeing proper working of the network even when some of the relay nodes (up to a given maximum number) become faulty (fault-tolerance). We show that, by means of a computation-intensive pre-processing on a HPC infrastructure, the above optimisation problem can be encoded as a 0/1 Linear Program, becoming suitable to be approached with standard Artificial Intelligence reasoners like MILP, PB-SAT, and SMT/OMT solvers. Our problem formulation enables us to present experimental results comparing the performance of these three solving technologies on a real case study of a relay node network deployment in areas of the Leonardo da Vinci Airport in Rome, Italy.


Optimal personalised treatment computation through in silico clinical trials on patient digital twins

arXiv.org Artificial Intelligence

In Silico Clinical Trials (ISCT), i.e., clinical experimental campaigns carried out by means of computer simulations, hold the promise to decrease time and cost for the safety and efficacy assessment of pharmacological treatments, reduce the need for animal and human testing, and enable precision medicine. In this paper we present methods and an algorithm that, by means of extensive computer simulation-based experimental campaigns (ISCT) guided by intelligent search, optimise a pharmacological treatment for an individual patient (precision medicine). We show the effectiveness of our approach on a case study involving a real pharmacological treatment, namely the downregulation phase of a complex clinical protocol for assisted reproduction in humans.


Score-Based Explanations in Data Management and Machine Learning: An Answer-Set Programming Approach to Counterfactual Analysis

arXiv.org Artificial Intelligence

We describe some recent approaches to score-based explanations for query answers in databases and outcomes from classification models in machine learning. The focus is on work done by the author and collaborators. Special emphasis is placed on declarative approaches based on answer-set programming to the use of counterfactual reasoning for score specification and computation. Several examples that illustrate the flexibility of these methods are shown.