Recovering Software Specifications with Inductive Logic Programming

AAAI Conferences

We consider using machine learning techniques to help understand a large software system. In particular, we describe how learning techniques can be used to reconstruct abstract Datalog specifications of a certain type of database software from examples of its operation. In a case study involving a large (more than one million lines of C) real-world software system, we demonstrate that off-the-shelf inductive logic programming methods can be successfully used for specification recovery; specifically, Grende12 can extract specifications for about one-third of the modules in a test suite with high rates of precision and recall. We then describe two extensions to Grende12 which improve performance on this task: one which allows it to output a set of candidate hypotheses, and another which allows it to output specifications containing determinations. In combination, these extensions enable specifications to be extracted for nearly two-thirds of the benchmark modules with perfect recall, and precision of better than 60%.

Planning in Dynamic Environments Through Temporal Logic Monitoring

AAAI Conferences

We present a framework that enables online planning for robotic systems in dynamic environments. The PLANrm framework presented in this work utilizes the theory of robustness and monitoring of Metric Temporal Logic (MTL) specifications to inspect and modify available plans to both avoid obstacles and satisfy specifications in a dynamic environment. The use of MTL allows the practitioner to set complex event and timing based specifications that need to be satisfied in the execution of the plan. The monitoring algorithm inspects the possible paths in a bounded window and selects and adjusts a path to satisfy the specifications. In this paper, we present initial results on the framework and an extended summary of the algorithmic results. The approach is illustrated using a running example of a car-like model with a number of MTL specifications.

On Formal Specification of Maple Programs Artificial Intelligence

This paper is an example-based demonstration of our initial results on the formal specification of programs written in the computer algebra language MiniMaple (a substantial subset of Maple with slight extensions). The main goal of this work is to define a verification framework for MiniMaple. Formal specification of MiniMaple programs is rather complex task as it supports non-standard types of objects, e.g. symbols and unevaluated expressions, and additional functions and predicates, e.g. runtime type tests etc. We have used the specification language to specify various computer algebra concepts respective objects of the Maple package DifferenceDifferential developed at our institute.

Scaffolding and the Insufficiency of the Intentional Stance as a Conceptual Underpinning for Multiagent Systems

AAAI Conferences

The intentional stance, which has been a conceptual underpinning of much work on multiagent systems, cannot provide an account of coordinated behavior in terms that can apply equally to humans and to agents. We suggest that one must also include social scaffolding in the sense in which "scaffolding" is used by Andy Clark. Critical aspects of the relevant social scaffolding can be formulated in terms of notions familiar from formalisms that have been applied to software systems and to humans alike.

Search-based Program Synthesis

Communications of the ACM

Writing programs that are both correct and efficient is challenging. A potential solution lies in program synthesis aimed at automatic derivation of an executable implementation (the "how") from a high-level logical specification of the desired input-to-output behavior (the "what"). A mature synthesis technology can have a transformative impact on programmer productivity by liberating the programmer from low-level coding details. For instance, for the classical computational problem of sorting a list of numbers, the programmer has to simply specify that given an input array A of n numbers, compute an output array B consisting of exactly the same numbers as A such that B[i] B[i 1] for 1 i n, leaving it to the synthesizer to figure out the sequence of steps needed for the desired computation. Traditionally, program synthesis is formalized as a problem in deductive theorem proving:17 A program is derived from the constructive proof of the theorem that states that for all inputs, there exists an output, such that the desired correctness specification holds.