Compiling and verifying SC-SystemJ programs for safety-critical reactive systems

Most of today's embedded systems are very complex. These systems, controlled by computer programs, continuously interact with their physical environments through network of sensory input and output devices. Consequently, the operations of such embedded systems are highly reactive and concurrent. Since embedded systems are deployed in many safety-critical applications, where failures can lead to catastrophic events, an approach that combines mathematical logic and formal verification is employed in order to ensure correct behavior of the control algorithm. This paper presents What You Prove Is What You Execute (WYPIWYE) compilation strategy for a Globally Asynchronous Locally Synchronous (GALS) programming language called Safey-Critical SystemJ. SC-SystemJ is a safety-critical subset of the SystemJ language. A formal big-step transition semantics of SC-SystemJ is developed for compiling SC-SystemJ programs into propositional Linear Temporal Logic formulas. These LTL formulas are then converted into a network of Mealy automata using a novel and efficient compilation algorithm. The resultant Mealy automata have a straightforward syntactic translation into Promela code. The resultant Promela models can be used for verifying correctness properties via the SPIN model-checker. Finally there is a single translation procedure to compile both: Promela and C/Java code for execution, which satisfies the De-Bruijn index, i.e. this final translation step is simple enough that is can be manually verified.     

Using schedulers to test probabilistic distributed systems

Formal methods are one of the most important approaches to increasing the confidence in the correctness of software systems. A formal specification can be used as an oracle in testing since one can determine whether an observed behaviour is allowed by the specification. This is an important feature of formal testing: behaviours of the system observed in testing are compared with the specification and ideally this comparison is automated. In this paper we study a formal testing framework to deal with systems that interact with their environment at physically distributed interfaces, called ports, and where choices between different possibilities are probabilistically quantified. Building on previous work, we introduce two families of schedulers to resolve nondeterministic choices among different actions of the system. The first type of schedulers, which we call global schedulers, resolves nondeterministic choices by representing the environment as a single global scheduler. The second type, which we call localised schedulers, models the environment as a set of schedulers with there being one scheduler for each port. We formally define the application of schedulers to systems and provide and study different implementation relations in this setting.     

Knowledge Condition Games

Understanding the flow of knowledge in multi-agent protocols is essential when proving the correctness or security of such protocols. Current logical approaches, often based on model checking, are well suited for modeling knowledge in systems where agents do not act strategically. Things become more complicated in strategic settings. In this paper we show that such situations can be understood as a special type of game – a knowledge condition game – in which a coalition “wins” if it is able to bring about some epistemic condition. This paper summarizes some results relating to these games. Two proofs are presented for the computational complexity of deciding whether a coalition can win a knowledge condition game with and without opponents (Σ₂P-complete and NP-complete respectively). We also consider a variant of knowledge condition games in which agents do not know which strategies are played, and prove that under this assumption, the presence of opponents does not affect the complexity. The decision problem without opponents is still NP-complete, but requires a different proof.Sieuwert van Otterloo thanks the Institute for Logic, Language and Information in Amsterdam for its hospitality during the period that this paper was finalized.     

Static analysis of Linear Logic programming

Linear Logic is gaining momentum in computer science because it offers a unified framework and a common vocabulary for studying and analyzing different aspects of programming and computation. We focus here on models where computation is identified with proof search in the sequent system of Linear Logic. A proof normalization procedure, called “focusing”, has been proposed to make the problem of proof search tractable. Correspondingly, there is a normalization procedure mapping formulae of Linear Logic into a syntactic fragment of that logic, calledLinLog, where the focusing normalization for proofs can be most conveniently expressed. In this paper, we propose to push this compilation/normalization process further, by applying abstract interpretation and partial evaluation techniques to (focused) proofs inLinLog. These techniques provide information concerning the evolution of the computational resources (formulae) during the execution (proof construction). The practical outcome that we expect from this theoretical effort is the definition of a general tool for statically analyzing and reasoning about the runtime behavior of programs in frameworks where computations can be accounted for in terms of proof search in Linear Logic.     

Temporal logics with incommensurable distances are undecidable

Temporal Logic based on the two modalities “Since” and “Until” (TL) is the most popular logic for the specification of reactive systems. It is often called the linear time temporal logic. However, metric properties of real time cannot be expressed in this logic. The simplest modalities with metric properties are “X will happen within δ units of time”. The extension of TL by all these modalities with rational δ is decidable. We show that the extension of the linear time temporal logic by two modalities “X will happen within one unit of time”, “X will happen within τ unit of time” is undecidable, whenever τ is irrational.     

Simple and safe SQL queries with C++ templates

Most large software applications rely on an external relational database for storing and managing persistent data. Typically, such applications interact with the database by first constructing strings that represent SQL statements, and then submitting these for execution by the database engine. The fact that these statements are only checked for correctness at runtime is a source for many potential defects, including type and syntax errors and vulnerability to injection attacks.The AraRat system presented here offers a method for dealing with these difficulties by coercing the host C++ compiler to do the necessary checks of the generated strings. A library of templates and preprocessor directives is used to embed in C++ a little language representing an augmented relational algebra formalism. Type checking of this embedded language, carried out by our template library, assures, at compile-time, the correctness and safety of the generated SQL strings. All SQL statements constructed by AraRat are guaranteed to be syntactically correct, and type safe with respect to the database schema. Moreover, AraRat statically ensures that the generated statements are immune to all injection attacks.The standard techniques of “expression templates” and “compile-time symbolic derivation” for compile-time representation of symbolic structures, are enhanced in our system. We demonstrate the support of a type system and a symbol table lookup of the symbolic structure. A key observation of this work is that type equivalence of instantiated nominally typed generics in C++ (as well as other languages, e.g., Java) is structural rather than nominal. This makes it possible to embed the structural type system, characteristic to persistent data management, in the nominal type system of C++.For some of its advanced features, AraRat relies on two small extensions to the standard C++ language: the typeof pseudo operator and the __COUNTER__ preprocessor macro.     

Verifying concurrent probabilistic systems using probabilistic-epistemic logic specifications

In this paper, we address the problem of verifying probabilistic and epistemic properties in concurrent probabilistic systems expressed in PCTLK. PCTLK is an extension of the Probabilistic Computation Tree Logic (PCTL) augmented with Knowledge (K). In fact, PCTLK enjoys two epistemic modalities K_i for knowledge and \(Pr_{\triangledown b}K_{i}\) for probabilistic knowledge. The approach presented for verifying PCTLK specifications in such concurrent systems is based on a transformation technique. More precisely, we convert PCTLK model checking into the problem of model checking Probabilistic Branching Time Logic (PBTL), which enjoys path quantifiers in the range of adversaries. We then prove that model checking a formula of PCTLK in concurrent probabilistic programs is PSPACE-complete. Furthermore, we represent models associated with PCTLK logic symbolically with Multi-Terminal Binary Decision Diagrams (MTBDDs), which are supported by the probabilistic model checker PRISM. Finally, an application, namely the NetBill online shopping payment protocol, and an example about synchronization illustrated through the dining philosophers problem are implemented with the MTBDD engine of this model checker to verify probabilistic epistemic properties and evaluate the practical complexity of this verification.     

From Coalition Logic to STIT

STIT is a logic of agency that has been proposed in the nineties in the domain of philosophy of action. It is the logic of constructions of the form “agent a sees to it that φ”. We believe that STIT theory may contribute to the logical analysis of multiagent systems. To support this claim, in this paper we show that there is a close relationship with more recent logics for multiagent systems. We focus on Pauly's Coalition Logic and the logic of the cstit operator, as described by Horty. After a brief presentation of Coalition Logic and a discrete-time version (including a next operator) of the STIT framework, we introduce a translation from Coalition Logic to the discrete STIT logic, and prove that it is correct.     

The monadic second-order logic of graphs IX: Machines and their behaviours

We establish that every monadic second-order property of the behaviour of a machine (transition systems and tree automata are typical examples of machines) is a monadic second-order property of the machine itself. In this way, we clarify the distinction between “dynamic” properties of machines (i.e., properties of their behaviours), and their “static” properties (i.e., properties of the graphs or relational structures representing them). It is important for program verification that the dynamic properties that one wants to verify can be formulated statically, in the simplest possible way. As a corollary of our main result, we also obtain that the monadic theory of an algebraic tree is decidable.     

Proof systems that take advice

One of the starting points of propositional proof complexity is the seminal paper by Cook and Reckhow [J. Symbolic Logic, 1979], where they defined propositional proof systems as poly-time computable functions which have all propositional tautologies as their range. Motivated by provability consequences in bounded arithmetic, Cook and Kraj?´?ek [J. Symbolic Logic, 2007] have recently started the investigation of proof systems which are computed by poly-time functions using advice.In this paper we concentrate on three fundamental questions regarding this new model. First, we investigate whether a given language L admits a polynomially bounded proof system with advice. Depending on the complexity of the underlying language L and the amount and type of the advice used by the proof system, we obtain different characterizations for this problem. In particular, we show that this question is tightly linked with the question whether L has small nondeterministic instance complexity.The second question concerns the existence of optimal proof systems with advice. For propositional proof systems, Cook and Kraj?´?ek gave a surprising positive answer which we extend to all languages.These results show that providing proof systems with advice yields a more powerful model, but this model is also less directly applicable in practice. Our third question therefore asks whether the usage of advice in propositional proof systems can be simplified or even eliminated. While in principle, the advice can be very complex, we show that propositional proof systems with logarithmic advice are also computable in poly-time with access to a sparse NP-oracle. Employing a recent technique of Buhrman and Hitchcock [CCC, 2008] we also manage to transfer the advice from the proof to the proven formula, which leads to a more practical computational model.     

Identification- and Elimination-Based Parallel Query Processing Techniques for Object-Oriented Databases

The newly developed object-oriented database management systems provide rich facilities for the modeling and processing of structural as well as behavioral properties of complex application objects. However, due to their inherent generality, new functionalities to be added to these systems as they continue to evolve, and high performance demand in many application domains, efficient parallel algorithms and architectures would be needed to meet the performance requirement for processing large OODBs. In our previous work, we have shown that processing OODBs can be viewed as the manipulation of patterns of object associations. In this paper, we present several parallel, multiwavefront algorithms based on two approaches, i.e., identification and elimination approaches, to verify association patterns specified in queries. Both approaches allow more processors to operate concurrently on a query than the traditional tree-structured query processing approach, thus introducing a higher degree of parallelism in query processing. We present a graph model to transform the query processing problem into a graph problem. Based on the graph model, proofs of correctness of both approaches for tree-structured queries are given, and a combined approach for solving cyclic queries is also provided. We present a new data structure to represent associations between objects, parallel algorithms based on these approaches, and some evaluation results obtained from an actual implementation of these algorithms on an nCUBE 2 parallel computer.     

Kripke modelling and verification of temporal specifications of a multiple UAV system

A verifiable multiple UAV system cooperatively monitoring a road network is presented in this paper. The focus is on formal modelling and verification which can guarantee correctness of concurrent reactive systems such as multi-UAV systems. Kripke modelling is used to formally model the distributed cooperative control strategy, and to verify correctness of the specifications. Desirable properties of the mission such as liveness are specified in Computation Tree Logic (CTL). Model checking technique is used to exhaustively explore the state space to verify whether the system behaviour, modelled by Kripke model, satisfies the specifications. Violation of a specification is analysed by means of the counter-example generated by SMV model checking tool.     

CTRL: Extension of CTL with regular expressions and fairness operators to verify genetic regulatory networks

Model checking has proven to be a useful analysis technique not only for concurrent systems, but also for genetic regulatory networks (Grns). Applications of model checking in systems biology have revealed that temporal logics should be able to capture both branching-time and fairness properties (needed for specifying multistability and oscillation properties, respectively). At the same time, they should have a user-friendly syntax easy to employ by non-experts. In this paper, we define Computation Tree Regular Logic (Ctrl), an extension of Ctl with regular expressions and fairness operators that attempts to match these criteria. Ctrl subsumes both Ctl and Ltl, and has a reduced set of temporal operators indexed by regular expressions. We also develop a translation of Ctrl into Hennessy-Milner Logic with Recursion (HmlR), an equational variant of the modal μ-calculus. This has allowed us to obtain an on-the-fly model checker with diagnostic for Ctrl by directly reusing the verification technology available in the Cadp toolbox. We illustrate the application of the Ctrl model checker by analyzing the Grn controlling the carbon starvation response of Escherichia coli.     

The Dynamification of Modal Dependence Logic

We examine the transitions between sets of possible worlds described by the compositional semantics of Modal Dependence Logic, and we use them as the basis for a dynamic version of this logic. We give a game theoretic semantics, a (compositional) transition semantics and a power game semantics for this new variant of modal Dependence Logic, and we prove their equivalence; and furthermore, we examine a few of the properties of this formalism and show that Modal Dependence Logic can be recovered from it by reasoning in terms of reachability. Then we show how we can generalize this approach to a very general formalism for reasoning about transformations between pointed Kripke models.     

A Branching Time Temporal Framework for Quantitative Reasoning

Temporal logics such as Computation Tree Logic (CTL) and Linear Temporal Logic (LTL) have become popular for specifying temporal properties over a wide variety of planning and verification problems. In this paper we work towards building a generalized framework for automated reasoning based on temporal logics. We present a powerful extension of CTL with first-order quantification over the set of reachable states for reasoning about extremal properties of weighted labeled transition systems in general. The proposed logic, which we call Weighted Quantified Computation Tree Logic (WQCTL), captures the essential elements common to the domain of planning and verification problems and can thereby be used as an effective specification language in both domains. We show that in spite of the rich, expressive power of the logic, we are able to evaluate WQCTL formulas in time polynomial in the size of the state space times the length of the formula. Wepresent experimental results on the WQCTL verifier.     

Base extension using a convolution sum in residue number systems

Base extension is an important operation in residue number systems. The method for base extension proposed in this paper approaches the solution through an approximation which is correct in nearly all cases. Rare corrences of uncertainties about the correctness of the result are detected and corrected using iterations. The novel method is superior to the method proposed by Shenoy and Kumaresan [5] as it does not need the help of an additional redundant modulus. For a special class of problems the latter method cannot be used at all. The presented base extension provides a unique tool with time complexity of log₂ n withn denoting the amount of moduli.     

Reasoning about UML/OCL class diagrams using constraint logic programming and formula

Model Driven Engineering promotes the use of models as the main artifacts in software and system development. Verification and validation of models are key activities to ensure the quality of the system under development. This paper presents a framework to reason about the satisfiability of class models described using the Unified Modeling Language (UML). The proposed framework allows us to identify possible design flaws as early as possible in the software development cycle. More specifically, we focus on UML Class Diagrams annotated with Object Constraint Language (OCL) invariants, which are considered to be the main artifacts in Object-Oriented analysis and design for representing the static structure of a system. We use the Constraint Logic programming (CLP) paradigm to reason about UML Class Diagrams modeling foundations. In particular, we use Formula as a model-finding and design space exploration tool. We also present an experimental Eclipse plug-in, which implements our UML model to Formula translation proposal following a Model Driven Architecture (MDA) approach. The proposed framework can be used to reason, validate, and verify UML Class Diagram software designs by checking correctness properties and generating model instances using the model exploration tool Formula.     

An integrated framework for the diagnosis and correction of rule-based programs

We present a generic scheme for the declarative debugging of programs that are written in rewriting-based languages that are equipped with narrowing. Our aim is to provide an integrated development environment in which it is possible to debug a program and then correct it automatically. Our methodology is based on the combination (in a single framework) of a semantics-based diagnoser that identifies those parts of the code that contain errors and an inductive learner that tries to repair them, once the bugs have been located in the program. We develop our methodology in several steps. First, we associate with our programs a semantics that is based on a (continuous) immediate consequence operator, T_R, which models the answers computed by narrowing and is parametric w.r.t. the evaluation strategy, which can be eager or lazy. Then, we show that, given the intended specification of a program R, it is possible to check the correctness of R by a single step of T_R. In order to develop an effective debugging method, we approximate the computed answers semantics of R and derive a finitely terminating bottom-up abstract diagnosis method, which can be used statically. Finally, a bug-correction program synthesis methodology attempts to correct the erroneous components of the wrong code. We propose a hybrid, top-down (unfolding-based) as well as bottom-up (induction-based), correction approach that is driven by a set of evidence examples which are automatically produced as an outcome by the diagnoser. The resulting program is proven to be correct and complete w.r.t. the considered example sets. Our debugging framework does not require the user to provide error symptoms in advance or to answer difficult questions concerning program correctness. An implementation of our debugging system has been undertaken which demonstrates the workability of our approach.