Computer Science

Today's cloud systems heavily rely on redundancy for reliability. Nevertheless, as cloud systems become ever more structurally complex, independent infrastructure components may unwittingly share deep dependencies. These unexpected common dependencies may result in causal failures that undermine redundancy efforts. The state-of-the-art efforts, e.g., post-failure forensics, not only lead to prolonged failure recovery time in the face of structurally complex systems, but also fail to avoid expensive service downtime. We describe RepAudit, an auditing system which builds on the so-called fault graph, to identify causal failures in the cloud. To ensure the practicality, efficiency, and accuracy of our approach, we further equip RepAudit with a domain-specific auditing language framework, a set of high-performance auditing primitives. We leverage SAT solvers to construct efficient fault graph analysis algorithms. To empirically evaluate this claim, we run RepAudit on a real-world cloud storage dataset and we observed that RepAudit is 300 times more efficient than other state-of-the-art auditing tools.  RepAudit technique has been used in Alibaba Group---the system is named CloudCanary---to perform real-time audits on service update scenarios to identify the root causes of correlated failure risks, and generate improvement plans with increased reliability.  CloudCanary has successfully detected various correlated failure risks such as single-point microservice, common power source, and shared network components, preventing service outages ahead of time.  The talk will conclude with an overview of the state of the arts on network verification community which widely relies on using SAT/SMT solver to check the correctness of network behaviors. References: [1] Ennan Zhai, Ruichuan Chen, David Isaac Wolinsky, Bryan Ford: Heading Off Correlated Failures through Independence-as-a-Service. OSDI 2014: 317-334 [2] Ennan Zhai, Ruzica Piskac, Ronghui Gu, Xun Lao, Xi Wang: An auditing language for preventing correlated failures in the cloud. PACMPL 1(OOPSLA): 97:1-97:28 (2017) This talk will be given in collaboration with Ennan Zhai, a researcher at Alibaba Group.

 This tutorial provides a programmer's introduction to Satisfiability Modulo Theories based on Z3. It illustrates how to define and solve SMT problems using scripts and walks through algorithms using exposed functionality.   Pre-recorded videos not available for Friday session.  

Pre-recorded videos not available for Friday session.   The availability of efficient SAT solvers presents opportunity for designing techniques for problems "beyond SAT". We will discuss two such problems that have witnessed increase in interest over the past decade: counting and sampling. Given a formula, the problem of counting is to compute the total number of solutions while sampling seeks to sample solutions uniformly at random. Counting and sampling are fundamental problems with applications such as probabilistic reasoning, information leakage, verification, and the like. In this talk, we will discuss approach that combines the classical ideas of universal hashing with CDCL solvers to design scalable approximate counters and samplers.  

Pseudo-Boolean solving is the task of finding a solution to a collection of (linear) pseudo-Boolean constraints, also known as a 0-1 integer linear program, possibly optimizing some linear objective function. This problem can be approached using methods from conflict-driven clause learning (CDCL) SAT solving as in MaxSAT solvers, or "native" pseudo-Boolean reasoning based on variants of the cutting planes proof system, or (mixed) integer linear programming (MIP). The purpose of this tutorial is to provide a brief survey of pseudo-Boolean reasoning, MaxSAT solving, and integer linear programming, focusing on the potential for synergy between these different approaches and highlighting many open problems on both the applied and the theoretical side.

These videos provide an introduction to proof complexity, especially from the point of view of satisfiability algorithms.  There are four videos.  Part A introduces proof complexity, and discusses Frege proofs, abstract proof systems, resolution, and extended Frege proofs and extended resolution.  Part B discusses the propositional pigeonhole principle, and upper and lower bounds on the complexity of proofs of the pigeonhole principle in the extended Frege proof system, the Frege proof systems, and resolution. Part C discusses the CDCL satisfiability algorithms from the point of view from proof complexity, including discussion of clause learning, trivial resolution, unit propagation, restarts, and RUP and (D)RAT proof traces.  Part D discusses cutting planes, the Nullstellsatz and Polynomial Calculus proof systems and concludes with a short discussion of automatizability. Parts B and C are independent of each other. Part D has a modest dependency on Part B, but can also be watched independently.

This tutorial focuses on explaining the most important aspects of the search loop in modern SAT solvers. It is an online BBC talk, i.e., black board and code, switching between a virtual black board to explain details and reviewing and using code in an interleaved manner. The code part features the new SAT Satch developed from scratch for this particular occasion. It is now available at  https://github.com/arminbiere/satch. We start with an introduction on encoding problems into conjunctive normal form, the input format of SAT solvers, and then delve into search based complete algorithms for SAT solving, from DPLL to CDCL and all its modern concepts, including the implication graph, decision heuristics (VSIDS and VMTF), restarts, as well as clause data base reduction, and then end with a closer look at clause and watching data structures and how they are updated during boolean constraint propagation.

From the early 1970s until now, SAT has been the central problem in Complexity Theory, inspiring many research directions. In the tutorial, I hope to show why SAT is such a favorite with complexity theorists, by talking about classical and modern results that involve SAT or its close relatives.  We'll talk about NP-completeness, polynomial-time hierarchy, interactive proofs, PCPs, as well as (circuit) lower bounds, Exponential-Time Hypothesis, and learning.

Cyberphysical systems are roughly characterized as systems enabled by coordination between computational and physical components and resources. They appear in a vast range of applications. Most applications of cyberphysical systems are subject to strict requirements for---to name a few---safety, security, and privacy. Formal methods for specification, verification, and synthesis have the potential to provide the languages, tools, and discipline necessary to meet these strict requirements. On the other hand, this potential can be realized only through proper connections between formal methods and several other fields. This tutorial will provide an overview of the complications in the context of cyberphysical systems that may benefit---and have benefited---from formal methods. It will provide examples of problems whose solution heavily relies on formal methods: correct-by-construction synthesis of hierarchical control protocols; synthesis of strategies under limitations on information availability; and verifiability of learning-enabled components.

In this talk I will outline automated techniques for the verification and control of partially observable probabilistic systems for both discrete and dense models of time. For the discrete-time case, we formally model these systems using partially observable Markov decision processes; for dense time, we propose an extension of probabilistic timed automata in which local states are partially visible to an observer or controller. Quantitative properties of interest, relate to the probability of an event’s occurrence or the expected value of some reward measure. I will present techniques to either verify that such a property holds or to synthesise a controller for the model which makes it true. The approach is based on an integer discretisation of the model’s dense-time behaviour and a grid-based abstraction of the uncountable belief space induced by partial observability. The latter is necessarily approximate since the underlying problem is undecidable, however both lower and upper bounds on numerical results can be generated.

Game theory has been forged in the 1944 book of von Neumann (a mathematician) and Morgenstern (an economist) as a way to reason rigorously about economic behaviour, but its methodologies have since also illuminated many areas of social, political, and natural sciences. More recently, it has also enjoyed fruitful cross-fertilization with Computer Science, yielding the vibrant areas of Algorithmic Game Theory and Algorithmic Mechanism Design. Less broadly known, but relevant to the Theoretical Foundations of Computer Systems program at Simons, are the game theoretic models that originate from set theory, logic, and automata. In this tutorial, we consider a very basic model of games on graphs. We then argue that this simple model is general enough to encompass a range of classic game-theoretic models, and that it can streamline or enable solutions of notable problems, for example: - Gale-Stewart games in set theory and Martin’s Borel determinacy theorem; - Church’s reactive synthesis problem and its solution by Buchi and Landweber; - Rabin’s tree theorem and its proof using positional determinacy; - Pnueli and Rosner’s temporal synthesis problem; - evaluating nested Knaster-Tarski fixpoints; - the complexity of pivoting rules in linear optimization and stochastic planning; - star height problem. The technical focus of this tutorial is on the algorithmic aspects of one relatively simple but influential graph game model called parity games. Building efficient parity game solvers is worthwhile because many model-checking, equivalence-checking, satisfiability, and synthesis problems boil down to solving a parity game. The problem has an intriguing computational complexity status: it is both in NP and in co-NP, and in PLS and PPAD, and hence unlikely to be complete for any of those complexity classes; no compelling evidence of hardness is known; and it is a long-standing open problem if it can be solved in polynomial time. A key parameter that measures the descriptive complexity of a parity game graph is the number of distinct priorities; for example, in games arising from nested Knaster-Tarski fixpoint expressions, it reflects the number of alternations between least and greatest fixpoints. All known algorithms for several decades have been exponential in the number of priorities, until 2017 when Calude, Jain, Khoussainov, Li, and Stephan made a breakthrough by showing that the problem is FPT and that there is a quasi-polynomial algorithm. In 2018, Lehtinen has proposed another parameter called the register number and has shown that parity games can be solved in time exponential in it. This refines the quasi-polynomial complexity obtained by Calude et al. because the register number of a finite game is at most logarithmic in its size. We argue that the register number coincides with another parameter called the Strahler number, which provides structural insights and allows to solve parity games efficiently using small Strahler-universal trees. We mention preliminary experimental evidence to support Lehtinen’s thesis that most parity games in the wild have very tiny register/Strahler numbers. This strengthens a popular belief that finding a polynomial-time algorithm is more vital in theory than in practice and it suggests practical ways of turning modern quasi-polynomial algorithms into competitive solvers.

Automata on infinite words have applications in system specification, verification, and synthesis. We introduce Buchi automata, and survey interesting issues around their closure properties, expressive power, determinization, and decision problems. Below you can find Panopto links to Orna's pre-recorded talks: Part 1: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=88f4fcfc-e531-404e-bdb2-acb100a573b2 Part 2: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=5396c12c-ecff-40c5-8afc-acb100a56ed2 Part 3: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=b37fc8b9-05ef-42bb-99ca-acb100c1fc64 Part 4: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=262825e9-479e-4e7a-9386-acb30076b006   Part 5: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=257dd520-bd68-4dac-95e6-acb30088cce8 Part 6: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=7ed603a9-ce88-46ff-ae43-acb30095a97b

This is a 3 part tutorial about logic. It is organised around algorithms for checking if a formula is true in a model.There are two central variants of this problem. In the model checking problem    we are given the model and the formula, and we want to know it the formula is true in the model. In the satisfiability (dually, validity) problem    we are only given the formula, and we want to know if it is true in some (dually, every) model (perhaps from some fixed class of models). There are three parts of the tutorial (each set of slides contains a soundtrack): Part 1 (slides ) discusses the variant of the model checking problem where the model is fixed and only the formula is given on the input. (This is also known as deciding the theory of the model.)  I will particularly focus on cases where the problem can be solved using automata, and hence the corresponding logic is going to be monadic second-order logic, which is an old friend of automata. Part 2 (slides) discusses the satisfiability problem. Here, again, the main focus is on variants of the problem that can be solved using automata, namely monadic second-order logic on words, trees and graphs of bounded treewidth. Part 2 (slides), soundtrack coming Jan 20 morning) discusses the variant of the model checking problem where the formula is fixed and the model is the input. Apart from results that use automata (mainly Courcelle’s theorem about MSO model checking on graphs of bounded treewidth), I will also discuss some results about first-order logic on sparse graph classes.