14006300
Abstraction and refinement in protocol derivation
Protocols may be derived from initial components by composition, refinement, and transformation. Adding function variables to a previous protocol logic, we develop an abstraction-instantiation method for reasoning about a class of protocol refinements. The main idea is to view changes in a protocol as a combination of finding a meaningful "protocol template" that contains function variables in messages, and producing the refined protocol as an instance of the template. Using higher-order protocol logic, we can develop a single proof for all instances of a template. A template can also be instantiated to another template, or a single protocol may be an instance of more than one template, allowing separate protocol properties to be proved modularly. These methods are illustrated using some challenge-response and key exchange protocol templates and an exploration of the design space surrounding JFK (just fast keying) and related protocols from the IKE (Internet key exchange) family, which produces some interesting protocols not previously studied in the open literature.
64829873
Secure Protocol Composition
This paper continues the program initiated in [5], towards a derivation system for security protocols. The general idea is that complex protocols can be formally derived, starting from basic security components, using a sequence of refinements and transformations, just like logical proofs are derived starting from axioms, using proof rules and transformations. The claim is that in practice, many protocols are already derived in such a way, but informally. Capturing this practice in a suitable formalism turns out to be a considerable task. The present paper proposes rules for composing security protocols from given security components. In general, security protocols are, of course, not compositional: information revealed by one may interfere with the security of the other. However, annotating protocol steps by pre- and post-conditions, allows secure sequential composition. Establishing that protocol components satisfy each other's invariants allows more general forms of composition, ensuring that the individually secure sub-protocols will not interact insecurely in the composite protocol. The applicability of the method is demonstrated on modular derivations of two standard protocols, together with their simple security properties.
1971532
A derivation system and compositional logic for security protocols
Many authentication and key exchange protocols are built using an accepted set of standard concepts such as Diffie-Hellman key exchange, nonces to avoid replay, certificates from an accepted authority, and encrypted or signed messages. We propose a general framework for deriving security protocols from simple components, using composition, refinements, and transformations. AS a case study, we examine the structure of a family of key exchange protocols that includes Station-TO-Station (STS), ISO-9798-3, Just Fast Keying (JFK), IKE and related protocols, derving all members of the family from two basic protocols, In order to associate formal proofs with protocol derivations, we extend our previous security protocol logic with preconditions, temporal assertions, composition rules, and Several other improvements. Using the logic, which we prove is sound with respect to the standard symbolic model of protocol execution and attack (the "Dolev-Yao model"), the security properties of the standard signature based Challange- Response protocol and the Diffie-Hellman key exchange protocol are estabilished. The ISO-9798-3 protocol is then proved correct by composing the correctness proofs of these two simple protocols Although our current formal logic is not sufficient to modulary prove security for all of our current protocol derivations. the derivation system provides a framework for further improvements.
2481740
Compositional analysis of contract signing protocols
We develop a general method for reasoning about contract-signing protocols using a specialized protocol logic. The method is applied to prove properties of the Asokan-Shoup-Waidner and the Garay-Jacobson-MacKenzie protocols. Our method offers certain advantages over previous analysis techniques. First, it is compositional: the security guarantees are proved by combining the independent proofs for the three sub-protocols of which each protocol is comprised. Second, the formal proofs are carried out in a "template" form, which gives us a reusable proof that may be instantiated for the ASW and GJM protocols, as well as for other protocols with the same arrangement of messages. Third, the proofs follow the design intuition. In particular, in proving game-theoretic properties like fairness, we demonstrate that the specific strategy that the protocol designer had in mind works, instead of showing that one exists. Finally, our results hold even when an unbounded number of sessions are executed in parallel.
2400545
Generating Boolean networks with a prescribed attractor structure
MOTIVATION
Dynamical modeling of gene regulation via network models constitutes a key problem for genomics. The long-run characteristics of a dynamical system are critical and their determination is a primary aspect of system analysis. In the other direction, system synthesis involves constructing a network possessing a given set of properties. This constitutes the inverse problem. Generally, the inverse problem is ill-posed, meaning there will be many networks, or perhaps none, possessing the desired properties. Relative to long-run behavior, we may wish to construct networks possessing a desirable steady-state distribution. This paper addresses the long-run inverse problem pertaining to Boolean networks (BNs).


RESULTS
The long-run behavior of a BN is characterized by its attractors. The rest of the state transition diagram is partitioned into level sets, the j-th level set being composed of all states that transition to one of the attractor states in exactly j transitions. We present two algorithms for the attractor inverse problem. The attractors are specified, and the sizes of the predictor sets and the number of levels are constrained. Algorithm complexity and performance are analyzed. The algorithmic solutions have immediate application. Under the assumption that sampling is from the steady state, a basic criterion for checking the validity of a designed network is that there should be concordance between the attractor states of the model and the data states. This criterion can be used to test a design algorithm: randomly select a set of states to be used as data states; generate a BN possessing the selected states as attractors, perhaps with some added requirements such as constraints on the number of predictors and the level structure; apply the design algorithm; and check the concordance between the attractor states of the designed network and the data states.


AVAILABILITY
The software and supplementary material is available at http://gsp.tamu.edu/Publications/BNs/bn.htm
805959
Providing Real-Time Response, State Recency and Temporal Consistency in Databases for Rapidly Changing Environments
Abstract Databases have been proposed as the chosen platform to develop automated control systems for environments where the state of the system changes rapidly, and actions need to be taken with timing constraints, such as stock trading, air traffic control, network management and process control. The workload in such systems consists primarily of two types: (a) updates , which report the state of the environment to the database and arrive very frequently, and (b) transactions which arrive with deadlines. In this paper we develop algorithms to install these updates rapidly enough to ensure “state recency” while allocating sufficient resources to transactions to minimize tardiness. We also require that these transactions read temporally consistent data. In summary, this paper contributes in the following three interrelated issues: 1. 1. First and foremost, we look at some interesting problems regarding amalgamating temporal and real-time databases. 2. 2. We look at simultaneous satisfaction of state recency and temporal consistency which are central issues in the class of systems considered in this paper, i.e., rapidly changing systems. 3. 3. We design algorithms that attempt to achieve equilibrium with regard to the conjoint processing of frequently arriving state updates and time constrained transactions. © 1997 Published by Elsevier Science Ltd
9941907
Intervention in context-sensitive probabilistic Boolean networks
MOTIVATION
Intervention in a gene regulatory network is used to help it avoid undesirable states, such as those associated with a disease. Several types of intervention have been studied in the framework of a probabilistic Boolean network (PBN), which is essentially a finite collection of Boolean networks in which at any discrete time point the gene state vector transitions according to the rules of one of the constituent networks. For an instantaneously random PBN, the governing Boolean network is randomly chosen at each time point. For a context-sensitive PBN, the governing Boolean network remains fixed for an interval of time until a binary random variable determines a switch. The theory of automatic control has been previously applied to find optimal strategies for manipulating external (control) variables that affect the transition probabilities of an instantaneously random PBN to desirably affect its dynamic evolution over a finite time horizon. This paper extends the methods of external control to context-sensitive PBNs.


RESULTS
This paper treats intervention via external control variables in context-sensitive PBNs by extending the results for instantaneously random PBNs in several directions. First, and most importantly, whereas an instantaneously random PBN yields a Markov chain whose state space is composed of gene vectors, each state of the Markov chain corresponding to a context-sensitive PBN is composed of a pair, the current gene vector occupied by the network and the current constituent Boolean network. Second, the analysis is applied to PBNs with perturbation, meaning that random gene perturbation is permitted at each instant with some probability. Third, the (mathematical) influence of genes within the network is used to choose the particular gene with which to intervene. Lastly, PBNs are designed from data using a recently proposed inference procedure that takes steady-state considerations into account. The results are applied to a context-sensitive PBN derived from gene-expression data collected in a study of metastatic melanoma, the intent being to devise a control strategy that reduces the WNT5A gene's action in affecting biological regulation, since the available data suggest that disruption of this influence could reduce the chance of a melanoma metastasizing.
7662147
Buffer management in real-time active database systems
Abstract Real-time, active database systems (RTADBSs) have attracted the attention of researchers in recent times. Such systems are envisioned as control systems for environments as diverse as process control, network management and automated financial trading. Sensors distributed throughout the system report the state of the system to the database. Unacceptable state reports typically result in corrective actions being triggered with deadlines. Thus RTADBSs incorporate both real-time as well as active characteristics. In this paper we study buffer management in RTADBSs. Buffer management is recognized as not being a well studied area in real-time systems. As a result of our work, we postulate (Prefetching Anticipatorily and Priority basEd Replacement) (PAPER), a new buffer management scheme that relies on two strategies: prefetching and priority based buffer replacement. We report the result of studies of the performance of PAPER, as compared to that of existing buffer management algorithms. The insights derived from this paper impact both real-time database systems as well as RTADBSs.
11950525
Anonymous publish/subscribe in P2P networks
One of the most important issues to deal with in peer-to-peer networks is how to disseminate information. In this paper, we use a completely new approach to solving the information dissemination problem. Our approach uses the publish/subscribe paradigm. The publish/subscribe method is the most inclusive strategy to establish communication between the information providers (publishers) and the information consumers (subscribers). We give a formal definition of publish/subscribe systems. We then use the publish/subscribe communication paradigm to design deterministic protocols (topic and content-based) for peer-to-peer networks. Our protocols are designed on top of an innovative information dissemination scheme, and can cope with the anonymity and mobility of both publishers and subscribers, weak-connectivity, and polarization, which are some of the characteristics of peer-to-peer networks. Moreover, in our solutions, every node could play a role of both publisher and subscriber The algorithms are designed completely independent of the underlying routing substrates. The key advantage of our protocols is that they are scalable without additional re-organization cost. To the best of our knowledge, this is the first time the content-based subscription has been addressed in peer-to-peer networks.