A technique to analyze information-flow in object-oriented programs

Traditional information-flow analysis is mainly based on data-flow and control-flow equations. In object-oriented programs, because of the mechanisms such as encapsulation, inheritance, and polymorphism, information-flow analysis becomes quite complex and therefore it is not enough to analyze object-oriented information-flow using traditional techniques. Some new techniques are required in order to efficiently analyze the information-flow between basic components (such as statements, methods, classes or packages) in object-oriented programs. Based on object-oriented program slicing techniques, we discuss how to compute the amount of information-flow, the width of information-flow, the correlation coefficient between basic components as well as degree of coupling of a basic component can be computed. We also discuss some applications of the information-flow.     

On decidability and closure properties of language classes with respect to bio-operations

We present general results that are useful in showing closure and decidable properties of large classes of languages with respect to biologically-inspired operations. We use these results to prove new decidability results and closure properties of some classes of languages under bio-operations such hairpin-inversion, the recently studied operation of pseudo-inversion, and other bio-operations. We also provide techniques for proving undecidability results. In particular, we give a new approach for proving the undecidability of problems for which the usual method of reduction to the undecidability of the Post Correspondence Problem seems hard to apply. Our closure and decidability results strengthen or generalize previous results.     

Variants of top-down tree transducers with look-ahead

In this article we consider deterministic and strongly deterministic top-down tree transducers with regular look-ahead, with regular check, with deterministic top-down look-ahead, and with deterministic top-down check. We compare the transformational power of these tree transducer classes by giving a correct inclusion diagram of the tree transformation classes induced by them. Along with the comparison we decompose some of the examined classes into simpler classes and we introduce the concept of the deterministic top-down tree automata with deterministic top-down look-ahead. We show that these recognizers recognize a tree language class which is strictly between the class of regular tree languages and the class of tree languages recognizable by deterministic top-down tree automata. We also study the closure properties of the examined tree transformation classes. We show that some classes are closed under composition while others, for example the class of tree transformations induced by deterministic top-down tree transducers with deterministic top-down look-ahead, are not.     

On the expressibility of functions in XQuery fragments

XQuery is a powerful XML query language with many features and syntactic constructs. For many common queries we do not need all the expressive power of XQuery. We investigate the effect of omitting certain features of XQuery on the expressive power of the language. We start from a simple base fragment which can be extended by several optional features being aggregation functions such as count and sum, sequence generation, node construction, position information in for loops, and recursion. In this way we obtain 64 different XQuery fragments which can be divided into 17 different equivalence classes such that two fragments can express the same functions if they are in the same equivalence class. Moreover, we investigate the relationships between these equivalence classes and derive some properties of the fragments within these equivalence classes.     

Mediating secure information flow policies

In this paper, we study secure information flow policies in the sense of Meadows [C. Meadows, Extending the Brewer–Nash model to a multi-level context. IEEE Computer Society Symposium on Research in Security and Privacy (1990) 95–102.] and others for aggregated datasets, collectively. We first present a method for combining different sensitivity levels over a common dataset and investigate its ramifications on information flow policies. Next, safe-flow policies are formulated in full generality using domain-theoretic tools, and systematically derived as closure operators from Scott continuous functions. Maximum safe-flow policies correspond to the top element of the lattice of the derived closure-operator collection. We then introduce a categorical framework for information flow, in which amalgamation is used to formulate and characterize information-flow policy merging.Our methods for mediating information flow policies should be of practical interest for information sharing among multiple agencies. Our formulation of safe-flow policies as closure operators from Scott continuous functions and the associated categorical formulation of safe-flow policy merging provide a sound and general theoretical foundation for the first time for this topic, setting a stage for further development in this area.     

Composing Stack-Attributed Tree Transducers

Stack-attributed tree transducers extend attributed tree transducers with a pushdown stack device for attribute values, which make them strictly more powerful. This paper presents an algorithm for the composition of stack-attributed tree transducers with attributed tree transducers. The algorithm is an extension of the existing method to compose attributed tree transducers. It leads to some natural closure properties of the corresponding classes of tree transformations.     

Refinement of actions and equivalence notions for concurrent systems

We study an operator for refinement of actions to be used in the design of concurrent systems. Actions on a given level of abstraction are replaced by more complicated processes on a lower level. This is done in such a way that the behaviour of the refined system may be inferred compositionally from the behaviour of the original system and from the behaviour of the processes substituted for actions. We recall that interleaving models of concurrent systems are not suited for defining such an operator in its general form. Instead, we define this operator on several causality based, event oriented models, taking into account the distinction between deadlock and successful termination. Then we investigate the interplay of action refinement with abstraction in terms of equivalence notions for concurrent systems, considering both linear time and branching time approaches. We show that besides the interleaving equivalences, also the equivalences based on steps are not preserved under refinement of actions. We prove that linear time partial order semantics are invariant under refinement. Finally we consider various bisimulation equivalences based on partial orders and show that the finest two of them are preserved under refinement whereas the others are not. Termination sensitive versions of these equivalences are even congruences for action refinement. Received 11 May 1998 / 19 June 2000     

A uniform presentation of confidentiality properties

Security (in the sense of confidentiality) properties are properties of shared systems. A suitable model of shared systems, in which one can formally define the term security property and then proceed to catalog several security properties, is presented. The purpose is to present various information-flow properties in a manner that exposes their differences and similarities. Abstraction is the main tool, and everything that is not central to the purpose is discarded. The presentation is generic in the model of computation. The abstraction lays bare a regular structure into which many interesting information-flow properties fall. A shared system is represented by a relation. How this model lets one reason about information flow is discussed and the term information flow property is formally defined. Various information-flow properties are described. Composability and probabilistic security properties are addressed     

Computational probabilistic noninterference

Information flow and noninterference are popular concepts for expressing confidentiality and integrity properties. We present the first general definition of probabilistic noninterference in reactive systems that includes a computational case. This case is essential for coping with real cryptography since noninterference properties can usually only be guaranteed if the underlying cryptographic primitives have not been broken. This might happen, but only with negligible probability. We show that our noninterference definition is maintained under simulatability, the notion of secure implementation of modern cryptography. This allows secure composition of systems and yields a general strategy for including cryptographic primitives in information-flow proofs. As an example we study a cryptographic firewall guarding two honest users from their environment.     

Detection of global predicates: Techniques and their limitations

Summary. We show that the problem of predicate detection in distributed systems is NP-complete. In the past, efficient algorithms have been developed for special classes of predicates such as stable predicates, observer independent predicates, and conjunctive predicates. We introduce a class of predicates, semi-linear predicates, which properly contains all of the above classes. We first discuss stable, observer independent and semi-linear classes of predicates and their relationships with each other. We also study closure properties of these classes with respect to conjunction and disjunction. Finally, we discuss algorithms for detection of predicates in these classes. We provide a non-deterministic detection algorithm for each class of predicate. We show that each class can be equivalently characterized by the degree of non-determinism present in the algorithm. Stable predicates are defined as those that can be detected by an algorithm with the most non-determinism. All other classes can be derived by appropriately constraining the non-determinism in this algorithm.     

Arithmetic Complexity, Kleene Closure, and Formal Power Series

The aim of this paper is to use formal power series techniques to study the structure of small arithmetic complexity classes such as GapNC ¹ and GapL. More precisely, we apply the formal power series operations of inversion and root extraction to these complexity classes. We define a counting version of Kleene closure and show that it is intimately related to inversion and root extraction within GapNC ¹ and GapL. We prove that Kleene closure, inversion, and root extraction are all hard operations in the following sense: there is a language in AC ⁰ for which inversion and root extraction are GapL-complete and Kleene closure is NLOG-complete, and there is a finite set for which inversion and root extraction are GapNC ¹ -complete and Kleene closure is NC ¹ -complete, with respect to appropriate reducibilities. The latter result raises the question of classifying finite languages so that their inverses fall within interesting subclasses of GapNC ¹ , such as GapAC ⁰ . We initiate work in this direction by classifying the complexity of the Kleene closure of finite languages. We formulate the problem in terms of finite monoids and relate its complexity to the internal structure of the monoid. Some results in this paper show properties of complexity classes that are interesting independent of formal power series considerations, including some useful closure properties and complete problems for GapL.     

Models for concurrency: towards a classification

Models for concurrency can be classified with respect to three relevant parameters: behaviour/ system, interleaving/noninterleaving, linear/branching time. When modelling a process, a choice concerning such parameters corresponds to choosing the level of abstraction of the resulting semantics.

In this paper, we move a step towards a classification of models for concurrency based on the parameters above. Formally, we choose a representative of any of the eight classes of models obtained by varying the three parameters, and we study the formal relationships between them using the language of category theory.     

Pumping languages †

We study some pumping properties and the classes of languages having these properties. We describe how these classes are interrelated and related to the Chomsky hierarchy of languages. We further study their closure properties.     

De Bruijn''s syntax and reductional behaviour of λ-terms: the typed case

In this paper, we consider the typed versions of the λ-calculus written in a notation which helps describe canonical forms more elegantly than the classical notation, and enables to divide terms into classes according to their reductional behaviour. In this notation, β-reduction can be generalised from a relation on terms to one on equivalence classes. This class reduction covers many known notions of generalised reduction. We extend the Barendregt cube with our class reduction and show that the subject reduction property fails but that this is not unique to our class reduction. We show that other generalisations of reduction (such as the σ-reduction of Regnier) also behave badly in typed versions of the λ-calculus. Nevertheless, solution is at hand for these generalised reductions by adopting the useful addition of definitions in the contexts of type derivations. We show that adding such definitions enables the extensions of type systems with class reduction and σ-reduction to satisfy all the desirable properties of type systems, including subject reduction and strong normalisation. Our proposed typing relation ^c is the most general relation in the literature that satisfies all the desirable properties of type systems. We show that classes contain all the desirable information related to a term with respect to typing, strong normalisation, subject reduction, etc.     

Two complementary operations inspired by the DNA hairpin formation: Completion and reduction

We consider two complementary operations: Hairpin completion introduced in [D. Cheptea, C. Martin-Vide, V. Mitrana, A new operation on words suggested by DNA biochemistry: Hairpin completion, in: Proc. Transgressive Computing, 2006, pp. 216–228] with motivations coming from DNA biochemistry and hairpin reduction as the inverse operation of the hairpin completion. Both operations are viewed here as formal operations on words and languages. We settle the closure properties of the classes of regular and linear context-free languages under hairpin completion in comparison with hairpin reduction. While the class of linear context-free languages is exactly the weak-code image of the class of the hairpin completion of regular languages, rather surprisingly, the weak-code image of the class of the hairpin completion of linear context-free languages is a class of mildly context-sensitive languages. The closure properties with respect to the hairpin reduction of some time and space complexity classes are also studied. We show that the factors found in the general cases are not necessary for regular and context-free languages. This part of the paper completes the results given in the earlier paper, where a similar investigation was made for hairpin completion. Finally, we briefly discuss the iterated variants of these operations.     

Blending design patterns with aspects: A quantitative study

Design patterns often need to be blended (or composed) when they are instantiated in a software system. The composition of design patterns consists of assigning multiple pattern elements into overlapping sets of classes in a software system. Whenever the modularity of each design pattern is not preserved in the source code, their implementation becomes tangled with each other and with the classes’ core responsibilities. As a consequence, the change or removal of each design pattern will be costly or prohibitive as the software system evolves. In fact, composing design patterns is much harder than instantiating them in an isolated manner. Previous studies have found design pattern implementations are naturally crosscutting in object-oriented systems, thereby making it difficult to modularly compose them. Therefore, aspect-oriented programming (AOP) has been pointed out as a natural alternative for modularizing and blending design patterns. However, there is little empirical knowledge on how AOP models influence the composability of widely used design patterns. This paper investigates the influence of using AOP models for composing the Gang-of-Four design patterns. Our study categorizes different forms of pattern composition and studies the benefits and drawbacks of AOP in these contexts. We performed assessments of several pair-wise compositions taken from 3 medium-sized systems implemented in Java and two AOP models, namely, AspectJ and Compose*. We also considered complex situations where more than two patterns involved in each composition, and the patterns were interacting with other aspects implementing other crosscutting concerns of the system. In general, we observed two dominant factors impacting the pattern composability with AOP: (i) the category of the pattern composition, and (ii) the AspectJ idioms used to implement the design patterns taking part in the composition.     

Denotational semantics of object specification

From an arbitrary temporal logic institution we show how to set up the corresponding institution of objects. The main properties of the resulting institution are studied and used in establishing a categorial, denotational semantics of several basic constructs of object specification, namely aggregation (parallel composition), interconnection, abstraction (interfacing) and monotonic specialization. A duality is established between the category of theories and the category of objects, as a corollary of the Galois correspondence between these concrete categories. The special case of linear temporal logic is analysed in detail in order to show that categorial products do reflect interleaving and reducts may lead to internal non-determinism. Received: 30 May 1996 / 4 November 1997     

Shared-memory parallel programming in C++

A set of portable parallel-programming constructs for C, implemented in M4 macros called Parmacs, developed by researchers at Argonne National Laboratory, is considered. The Parmacs macros make it possible to write parallel C programs for shared-memory, distributed-memory, and mixed-memory systems; are portable, highly functional, and efficient; and provide sufficient functions to build a variety of parallel programs. However, they have several problems. The M4 macros are awkward to use and hard to read, so it is easy to make errors when using them. They are a mechanism outside the C language; thus, someone familiar only with C cannot readily read the code. They are not cleanly extensible, and their use is not type-checked. It is shown that using C++, rather than C, addresses these problems adequately. The Parmacs macros are described, the C++ Parmacs classes and runtime model are presented, and examples that show the use of the C++ Parmacs constructs are given. The work described considers only shared-memory constructs. Directions for future work are indicated     

Correct-by-construction model driven engineering composition operators

Model composition is a crucial activity in Model Driven Engineering both to reuse validated and verified model elements and to handle separately the various aspects in a complex system and then weave them while preserving their properties. Many research activities target this compositional validation and verification (V & V) strategy: allow the independent assessment of components and minimize the residual V & V activities at assembly time. However, there is a continuous and increasing need for the definition of new composition operators that allow the reconciliation of existing models to build new systems according to various requirements. These ones are usually built from scratch and must be systematically verified to assess that they preserve the properties of the assembled elements. This verification is usually tedious but is mandatory to avoid verifying the composite system for each use of the operators. Our work addresses these issues, we first target the use of proof assistants for specifying and verifying compositional verification frameworks relying on formal verification techniques instead of testing and proofreading. Then, using a divide and conquer approach, we focus on the development of elementary composition operators that are easy to verify and can be used to further define complex composition operators. In our approach, proofs for the complex operators are then obtained by assembling the proofs of the basic operators. To illustrate our proposal, we use the Coq proof assistant to formalize the language-independent elementary composition operators Union and Substitution and the proof that the conformance of models with respect to metamodels is preserved during composition. We show that more sophisticated composition operators that share parts of the implementation and have several properties in common (especially: aspect oriented modeling composition approach, invasive software composition, and package merge) can then be built from the basic ones, and that the proof of conformance preservation can also be built from the proofs of basic operators.