Model checking for a probabilistic branching time logic with fairness

We consider concurrent probabilistic systems, based on probabilistic automata of Segala & Lynch [55], which allow non-deterministic choice between probability distributions. These systems can be decomposed into a collection of “computation trees” which arise by resolving the non-deterministic, but not probabilistic, choices. The presence of non-determinism means that certain liveness properties cannot be established unless fairness is assumed. We introduce a probabilistic branching time logic PBTL, based on the logic TPCTL of Hansson [30] and the logic PCTL of [55], resp. pCTL [14]. The formulas of the logic express properties such as “every request is eventually granted with probability at least p”. We give three interpretations for PBTL on concurrent probabilistic processes: the first is standard, while in the remaining two interpretations the branching time quantifiers are taken to range over a certain kind of fair computation trees. We then present a model checking algorithm for verifying whether a concurrent probabilistic process satisfies a PBTL formula assuming fairness constraints. We also propose adaptations of existing model checking algorithms for pCTL [4, 14] to obtain procedures for PBTL under fairness constraints. The techniques developed in this paper have applications in automatic verification of randomized distributed systems. Received: June 1997 / Accepted: May 1998     

Animating Formal Specifications with Inheritance in a DL-Based Framework

Dynamic logic (DL) provides a suitable formal framework to model actions and reasoning about them. <$>\cal OASIS<$> is a language for the specification of object-oriented conceptual models. In our model, specialisation is a relation between classes that defines an inheritance mechanism through static and dynamic partitions. A variant of DL (including the deontic operators for permission, prohibition and obligation) is the formalism used in <$>\cal OASIS<$> to deal with changes of state, triggers, preconditions, protocols and operations. The animation of conceptual models in order to validate the specification is an interesting topic. We have worked on translating <$>\cal OASIS<$> specifications automatically to concurrent environments in order to obtain a prototype useful to validate specifications by animation. The aim of this paper is to show that it is feasible to translate static and dynamic partitions automatically into dynamic logic formulae. Thus, using the same developed schema of animation it is possible to execute <$>\cal OASIS<$> specifications including inheritance.     

An Approach to Security Requirements Engineering for a High Assurance System*

Requirements specifications for high-assurance secure systems are rare in the open literature. This paper examines the development of a requirements document for a multilevel secure system that must meet stringent assurance and evaluation requirements. The system is designed to be secure, yet combines popular commercial components with specialised high-assurance ones. Functional and non-functional requirements pertinent to security are discussed. A multidimensional threat model is presented. The threat model accounts for the developmental and operational phases of system evolution and for each phase accounts for both physical and non-physical threats. We describe our team-based method for developing a requirements document and relate that process to techniques in requirements engineering. The system requirements document presented provides a calibration point for future security requirements engineering techniques intended to meet both functional and assurance goals. RID="*" ID="*"The views expressed in this paper are those of the authors and should not be construed to reflect those of their employers or the Department of Defense. This work was supported in part by the MSHN project of the DARPA/ITO Quorum programme and by the MYSEA project of the DARPA/ATO CHATS programme. Correspondence and offprint requests to: T. Levin, Department of Computer Science, Naval Postgraduate School, Monterey, CA 93943-5118, USA. Tel.: +1 831 656 2339; Fax: +1 831 656 2814; Email: levin@nps.navy.mil     

Continuity in cognition

Designing for continuous interaction requires designers to consider the way in which human users can perceive and evaluate an artefact’s observable behaviour, in order to make inferences about its state, and plan and execute their own continuous behaviour. Understanding the human point of view in continuous interaction requires an understanding of human causal reasoning, of the way in which humans perceive and structure the world, and of human cognition. We present a framework for representing human cognition, and show briefly how it relates to the analysis of structure in continuous interaction, and the ways in which it may be applied in design. Published online: 14 May 2002     

Adaptive target recognition

Target recognition is a multilevel process requiring a sequence of algorithms at low, intermediate and high levels. Generally, such systems are open loop with no feedback between levels and assuring their performance at the given probability of correct identification (PCI) and probability of false alarm (Pf) is a key challenge in computer vision and pattern recognition research. In this paper, a robust closed-loop system for recognition of SAR images based on reinforcement learning is presented. The parameters in model-based SAR target recognition are learned. The method meets performance specifications by using PCI and Pf as feedback for the learning system. It has been experimentally validated by learning the parameters of the recognition system for SAR imagery, successfully recognizing articulated targets, targets of different configuration and targets at different depression angles.     

Likelihood,probability, and knowledge1

The modal logic LL was introduced by Halpern and Rabin as a means of doing qualitative reasoning about likelihood. Here the relationship between LL and probability theory is examined. It is shown that there is a way of translating probability assertions into LL in a sound manner, so that LL in some sense can capture the probabilistic interpretation of likelihood. However, the translation is subtle; several more obvious attempts are shown to lead to inconsistencies. We also extend LL by adding modal operators for knowledge. This allows us to reason about the interaction between knowledge and likelihood. The propositional version of the resulting logic LLK is shown to have a complete axiomatization and to be decidable in exponential time, provably the best possible.     

Password hardening based on keystroke dynamics

We present a novel approach to improving the security of passwords. In our approach, the legitimate user’s typing patterns (e.g., durations of keystrokes and latencies between keystrokes) are combined with the user’s password to generate a hardened password that is convincingly more secure than conventional passwords alone. In addition, our scheme automatically adapts to gradual changes in a user’s typing patterns while maintaining the same hardened password across multiple logins, for use in file encryption or other applications requiring a long-term secret key. Using empirical data and a prototype implementation of our scheme, we give evidence that our approach is viable in practice, in terms of ease of use, improved security, and performance. Published online: 26 October 2001     

Towards an Awareness-Based Semantics for Security Protocol Analysis

We report on work-in-progress on a new semantics for analyzing security protocols that combines complementary features of security logics and inductive methods. We use awareness to model the agents' resource-bounded reasoning and, in doing so, capture a more appropriate notion of belief than those usually considered in security logics. We also address the problem of modeling interleaved protocol executions, adapting ideas from inductive methods for protocol verification. The result is an intuitive, but expressive, doxastic logic for formalizing and reasoning about attacks. As a case study, we use awareness to characterize, and demonstrate the existence of, a man-in-the-middle attack upon the Needham-Schroeder Public Key protocol. This is, to our knowledge, not only the first doxastic analysis of this attack but also the first practical application of an awareness logic. Even though defining the awareness sets of the agents, a task that is left unspecified in formal works on awareness logics, turns out to be surprisingly subtle, initial results suggest that our approach is promising for modeling, verifying and reasoning about security protocols and their properties.     

Troubleshooting in Mechanics: A Heuristic Matching Process

This paper deals with expert operators’ reasoning processes in troubleshooting. We want to know more about the information that experienced operators use. In a previous study we studied electronics troubleshooting. We found that experts used surface cues in order to implement heuristic rules even if the latter are not relevant to the current fault. We now wish to study the field of mechanics. An experiment was conducted in order to test the hypothesis of a heuristic rule-based level of control responsible for errors among experts. This paper adopts a naturalistic and ergonomic point of view about troubleshooting in mechanics. Our results show that expert mechanics operators’ errors rely on heuristics in the troubleshooting process. This strategy relies on an automated matching process between symptoms and procedures. Although this strategy is usually powerful, it is rigid and may lead the operator to not locate the fault of the latter is atypical.     

Proposal on personal identifiers generated from the STR information of DNA

The individual differences in the repeat count of several bases, short tandem repeat (STR), among all of the deoxyribonucleic acid (DNA) base sequences, can be used as unique DNA information for a personal identification (ID). We propose a method to generate a personal identifier (hereafter referred to as a “DNA personal ID”) by specifying multiple STR locations (called “loci”) and then sequencing the repeat count information. We also conducted a validation experiment to verify the proposed principle based on actual DNA data. We verified that the matching probability of DNA personal IDs becomes exponentially smaller, to about 10^-n, as n stages of loci are used and that no correlation exists among the loci. Next, we considered the various issues that will be encountered when applying DNA personal IDs to information security systems, such as biometric personal authentication systems. Published online: 9 April 2002     

Computer security

A strong factor in the early development of computers was security – the computations that motivated their development, such as decrypting intercepted messages, generating gunnery tables, and developing weapons, had military applications. But the computers themselves were so big and so few that they were relatively easy to protect simply by limiting physical access to them to their programmers and operators. Today, computers have shrunk so that a web server can be hidden in a matchbox and have become so common that few people can give an accurate count of the number they have in their homes and automobiles, much less the number they use in the course of a day. Computers constantly communicate with one another; an isolated computer is crippled. The meaning and implications of “computer security” have changed over the years as well. This paper reviews major concepts and principles of computer security as it stands today. It strives not to delve deeply into specific technical areas such as operating system security, access control, network security, intrusion detection, and so on, but to paint the topic with a broad brush. Published online: 27 July 2001     

Accuracy bounds and optimal computation of robot localization

We present an optimal method for estimating the current location of a mobile robot by matching an image of the scene taken by the robot with a model of the known environment. We first derive a theoretical accuracy bound and then give a computational scheme that can attain that bound, which can be viewed as describing the probability distribution of the current location. Using real images, we demonstrate that our method is superior to the naive least-squares method. We also confirm the theoretical predictions of our theory by applying the bootstrap procedure. Received: 17 March 1998 / Accepted: 7 April 2001     

Efficient verification of security protocols using partial-order reductions

In this paper we explore how partial-order reduction can make the task of verifying security protocols more efficient. These reduction techniques have been implemented in our tool Brutus. Partial-order reductions have proved very useful in the domain of model checking reactive systems. These reductions are not directly applicable in our context because of additional complications caused by tracking knowledge of various agents. We present partial-order reductions in the context of verifying security protocols and prove their correctness. Experimental results demonstrating the effectiveness of this reduction technique are also presented. Published online: 24 January 2003     

Disjunctive Stable Models: Unfounded Sets, Fixpoint Semantics, and Computation

Disjunctive logic programs have become a powerful tool in knowledge representation and commonsense reasoning. This paper focuses on stable model semantics, currently the most widely acknowledged semantics for disjunctive logic programs. After presenting a new notion of unfounded sets for disjunctive logic programs, we provide two declarative characterizations of stable models in terms of unfounded sets. One shows that the set of stable models coincides with the family of unfounded-free models (i.e., a model is stable iff it contains no unfounded atoms). The other proves that stable models can be defined equivalently by a property of their false literals, as a model is stable iff the set of its false literals coincides with its greatest unfounded set. We then generalize the well-founded operator to disjunctive logic programs, give a fixpoint semantics for disjunctive stable models and present an algorithm for computing the stable models of function-free programs. The algorithm's soundness and completeness are proved and some complexity issues are discussed.     

Exogenous Probabilistic Computation Tree Logic

We define a logic EpCTL for reasoning about the evolution of probabilistic systems. System states correspond to probability distributions over classical states and the system evolution is modelled by probabilistic Kripke structures that capture both stochastic and non–deterministic transitions. The proposed logic is a temporal enrichment of Exogenous Probabilistic Propositional Logic (EPPL). The model-checking problem for EpCTL is analysed and the logic is compared with PCTL; the semantics of the former is defined in terms of probability distributions over sets of propositional symbols, whereas the latter is designed for reasoning about distributions over paths of possible behaviour. The intended application of the logic is as a specification formalism for properties of communication protocols, and security protocols in particular; to demonstrate this, we specify relevant security properties for a classical contract signing protocol and for the so–called quantum one–time pad.     

Extending the Unified Modeling Language for ontology development

There is rapidly growing momentum for web enabled agents that reason about and dynamically integrate the appropriate knowledge and services at run-time. The dynamic integration of knowledge and services depends on the existence of explicit declarative semantic models (ontologies). We have been building tools for ontology development based on the Unified Modeling Language (UML). This allows the many mature UML tools, models and expertise to be applied to knowledge representation systems, not only for visualizing complex ontologies but also for managing the ontology development process. UML has many features, such as profiles, global modularity and extension mechanisms that are not generally available in most ontology languages. However, ontology languages have some features that UML does not support. Our paper identifies the similarities and differences (with examples) between UML and the ontology languages RDF and DAML+OIL. To reconcile these differences, we propose a modification to the UML metamodel to address some of the most problematic differences. One of these is the ontological concept variously called a property, relation or predicate. This notion corresponds to the UML concepts of association and attribute. In ontology languages properties are first-class modeling elements, but UML associations and attributes are not first-class. Our proposal is backward-compatible with existing UML models while enhancing its viability for ontology modeling. While we have focused on RDF and DAML+OIL in our research and development activities, the same issues apply to many of the knowledge representation languages. This is especially the case for semantic network and concept graph approaches to knowledge representations. Initial sbmission: 16 February 2002 / Revised submission: 15 October 2002 Published online: 2 December 2002     

The OODB path-method generator (PMG) using access weights and precomputed access relevance

A path-method is used as a mechanism in object-oriented databases (OODBs) to retrieve or to update information relevant to one class that is not stored with that class but with some other class. A path-method is a method which traverses from one class through a chain of connections between classes and accesses information at another class. However, it is a difficult task for a casual user or even an application programmer to write path-methods to facilitate queries. This is because it might require comprehensive knowledge of many classes of the conceptual schema that are not directly involved in the query, and therefore may not even be included in a user's (incomplete) view about the contents of the database. We have developed a system, called path-method generator (PMG), which generates path-methods automatically according to a user's database-manipulating requests. The PMG offers the user one of the possible path-methods and the user verifies from his knowledge of the intended purpose of the request whether that path-method is the desired one. If the path method is rejected, then the user can utilize his now increased knowledge about the database to request (with additional parameters given) another offer from the PMG. The PMG is based on access weights attached to the connections between classes and precomputed access relevance between every pair of classes of the OODB. Specific rules for access weight assignment and algorithms for computing access relevance appeared in our previous papers [MGPF92, MGPF93, MGPF96]. In this paper, we present a variety of traversal algorithms based on access weights and precomputed access relevance. Experiments identify some of these algorithms as very successful in generating most desired path-methods. The PMG system utilizes these successful algorithms and is thus an efficient tool for aiding the user with the difficult task of querying and updating a large OODB. Received July 19, 1993 / Accepted May 16, 1997     

Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study

Summary. The Probabilistic I/O Automaton model of [31] is used as the basis for a formal presentation and proof of the randomized consensus algorithm of Aspnes and Herlihy. The algorithm guarantees termination within expected polynomial time. The Aspnes-Herlihy algorithm is a rather complex algorithm. Processes move through a succession of asynchronous rounds, attempting to agree at each round. At each round, the agreement attempt involves a distributed random walk. The algorithm is hard to analyze because of its use of nontrivial results of probability theory (specifically, random walk theory which is based on infinitely many coin flips rather than on finitely many coin flips), because of its complex setting, including asynchrony and both nondeterministic and probabilistic choice, and because of the interplay among several different sub-protocols. We formalize the Aspnes-Herlihy algorithm using probabilistic I/O automata. In doing so, we decompose it formally into three subprotocols: one to carry out the agreement attempts, one to conduct the random walks, and one to implement a shared counter needed by the random walks. Properties of all three subprotocols are proved separately, and combined using general results about automaton composition. It turns out that most of the work involves proving non-probabilistic properties (invariants, simulation mappings, non-probabilistic progress properties, etc.). The probabilistic reasoning is isolated to a few small sections of the proof. The task of carrying out this proof has led us to develop several general proof techniques for probabilistic I/O automata. These include ways to combine expectations for different complexity measures, to compose expected complexity properties, to convert probabilistic claims to deterministic claims, to use abstraction mappings to prove probabilistic properties, and to apply random walk theory in a distributed computational setting. We apply all of these techniques to analyze the expected complexity of the algorithm. Received: February 1999 / Accepted: March 2000