news Free Access Share on Zohar Manna (1939–2018) Authors: Nachum Dershowitz School of Computer Science, Tel Aviv University, Tel Aviv-Yafo, Israel School of Computer Science, Tel Aviv University, Tel Aviv-Yafo, IsraelSearch about this author , Richard Waldinger Artificial Intelligence Center, SRI International, Menlo Park, CA, USA Artificial Intelligence Center, SRI International, Menlo Park, CA, USASearch about this author Authors Info & Claims Formal Aspects of ComputingVolume 31Issue 6Dec 2019 pp 643–660https://doi.org/10.1007/s00165-019-00500-4Published:01 December 2019Publication History 1citation58DownloadsMetricsTotal Citations1Total Downloads58Last 12 Months49Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Network virtualization provides a flexible solution to reduce costs, share network resources and improve recovery time upon failure. An important part of virtual network management consists in migrating them in order to optimize resource allocation and react to link failures. However, the migration process might entail the loss of security properties in the virtual network, such as confidentiality. In this paper, we present the first approach combining formal models and virtualization to prove confidentiality preservation during the migration process. We describe the network environment, the migration process and the confidentiality with a set of logical predicates that will be used by SNARK to obtain the formal proof of the preservation. We validate our theoretical approach by exhibiting confidentiality violation detection on an illustrative use case.

We describe ongoing research using natural English text queries as an intelligent interface for inferring answers from structured data in a specific domain. Users can express queries whose answers need to be deduced from data in different databases, without knowing the structures of those databases nor even the existence of the sources used. Users can pose queries incrementally, elaborating on an initial query, and ask follow-up questions based on answers to earlier queries.

Rule-based systems are being applied to tasks of increasing responsibility. Deductive methods are being applied to their validation, to detect flaws in these systems and to enable us to use them with more confidence. Each system of rules is encoded as a set of axioms that define the system theory. The operation of the rule language and information about the subject domain are also described in the system theory. Validation tasks, such as establishing termination, unreachability, or consistency, or verifying properties of the system, are all phrased as conjectures. If we succeed in establishing the validity of the conjecture in the system theory, we have carried out the corresponding validation task. If the proof is restricted to be sufficiently constructive, we may extract from it information other than a simple yes/no answer. For example, we may obtain a description of a situation in which an error or anomaly may occur. A method for the gradual formulation of specifications based on the attempted proof of a series of conjectures has been found to be suitable for rule-based systems. Such a specification can serve as the basis for a reengineering of the system using conventional software technology. Validation conjectures are proved or disproved by a new theorem-proving system, SNARK, which implements (nonclausal) resolution and paramodulation, an optional constructive restriction, and some facilities for proof by induction. The system has already been applied to prove properties of a number of simple rule-based systems.

An informal tutorial for program synthesis is presented, with an emphasis on deductive methods. According to this approach, to construct a program meeting a given specification, the authors prove the existence of an object meeting the specified conditions. The proof is restricted to be sufficiently constructive, in the sense that, in establishing the existence of the desired output, the proof is forced to indicate a computational method for finding it. That method becomes the basis for a program that can be extracted from the proof. The exposition is based on the deductive-tableau system, a theorem-proving framework particularly suitable for program synthesis. The system includes a nonclausal resolution rule, facilities for reasoning about equality, and a well-founded induction rule.>

We introduce a logical formalism for the specification of the dynamic behavior of databases. The evolution of databases is characterized by both the dynamic integrity constraints which describe the properties of state transitions and the transactions whose executions lead to state transitions. Our formalism is based on a variant of first-order situational logic in which the states of computations are explicit objects. Integrity constraints and transactions are uniformly specifiable as expressions in our language. We also point out the application of the formalism to the verification and synthesis of transactions.

Two deduction rules are introduced to give streamlined treatment to relations of special importance in an automated theorem-proving system. These rules, the relation replacement and relation matching rules, generalize to an arbitrary binary relation the paramodulation and E-resolution rules, respectively, for equality, and may operate within a nonclausal or clausal system. The new rules depend on an extension of the notion of polarity to apply to subterms as well as to subsentences, with respect to a given binary relation. The rules allow us to eliminate troublesome axioms, such as transitivity and monotonicity, from the system; proofs are shorter and more comprehensible, and the search space is correspondingly deflated.

Program synthesis is the systematic derivation of a program from a given specification. A deductive approach to program synthesis is presented for the construction of recursive programs. This approach regards program synthesis as a theorem-proving task and relies on a theorem-proving method that combines the features of transformation rules, unification, and mathematical induction within a single framework.

Deductive techniques are presented for deriving programs systematically from given specifications. The specifications express the purpose of the desired program without giving any hint of the algorithm to be employed. The basic approach is to transform the specifications repeatedly according to certain rules, until a satisfactory program is produced. The rules are guided by a number of strategic controls. These techniques have been incorporated in a running program-synthesis system, called DEDALUS.

Techniques derived from mathematical logic promise to provide an alternative to the conventional methodology for constructing, debugging, and optimizing computer programs. Ultimately, these techniques are intended to lead to the automation of many of the facets of the programming process.

This paper describes a theorem prover that embodies knowledge about programming constructs, such as numbers, arrays, lists, and expressions. The program can reason about these concepts and is used as part of a program verification system that uses the Floyd-Naur explication of program semantics. It is implemented in the QA4 language; the QA4 system allows many bits of strategic knowledge, each expressed as a small program, to be coordinated so that a program stands forward when it is relevant to the problem at hand. The language allows clear, concise representation of this sort of knowledge. The QA4 system also has special facilities for dealing with commutative functions, ordering relations, and equivalence relations; these features are heavily used in this deductive system. The program interrogates the user and asks his advice in the course of a proof. Verifications have been found for Hoare's FIND program, a real-number division algorithm, and some sort programs, as well as for many simpler algorithms. Additional theorems have been proved about a pattern matcher and a version of Robinson's unification algorithm.