Register context-free grammars (RCFG), register pushdown automata (RPDA) and register tree automata (RTA) are extensions of their classical counterparts to handle data values in a restricted way. These extended models are paid attention as models of query languages for structured documents such as XML with data values. This paper investigates the computational complexity of the basic decision problems for the models. We show that the membership and emptiness problems for RCFG are EXPTIME-complete and also show the membership problem becomes PSPACE-complete and NP-complete for ε-rule free RCFG and growing RCFG, respectively while the emptiness problem remains EXPTIME-complete for these subclasses. The complexities of these problems for RPDA and RTA as well as their language expressive powers are also investigated.

Access control models are adopted in modern component-based systems, such as Java, in order to protect critical resources and operations. One of the last models presented, Information-Based Access Control model (IBAC), has been proposed to solve the excessive restrictiveness of the History-Based Access Control model (HBAC), which may incorrectly prevent the execution of security-sensitive operations that should be executed. However, the semantics of the IBAC model are relatively recent and complicated to be easily implemented in a real environment. In this paper we informally propose an algorithm to approximate a subset of IBAC programs into a program that uses HBAC semantics. Accomplishing this, an IBAC program from the subset we defined could be implemented in an environment that is supported by HBAC.

We propose a new architecture for trust management in ubiquitous environments that deals with RBAC policy, digital signatures, and user presence in a uniform framework. The proposed architecture includes inferences about user presence from incomplete sensor signals based on the hidden Markov model. We implemented a prototype system for a connection service in an office computer network with an RFID tag sensor system.Experimental results show that the proposed architecture is effective in providing both useful and secure services in a ubiquitous environment.

Stack inspection is a key technology for runtime access control of programs in a network environment. In this paper, a verification problem to decide whether a given program with stack inspection satisfies a given security property is discussed. First, the computational complexity of the problem is investigated. Since the result implies the problem is computationally intractable in general, we introduce a practically important subclass of programs which exactly model programs containing check Permission of Java development kit 1.2. We show that the problem for this subclass is solvable in linear time in the size of a program.

Java development kit 1.2 provides a runtime access control mechanism which inspects a control stack to examine whether the program has appropriate access permissions. Guaranteeing that each execution of a program with stack inspection satisfies required security properties is desirable. Jensen et al. introduced a verification problem of deciding for a given program P and a given security property written in a temporal logic formula, whether every reachable state of P satisfies . They showed that the problem is decidable for the class of programs which do not contain mutual recursion. In this paper, we show that the set of state sequences of a program is always an indexed language and consequently the verification problem is decidable. Our result is stronger than Jensen's in that a security property can be specified by a regular language, whose expressive power is stronger than temporal logic, and in that a program can contain mutual recursion.