Search

We give an overview of an application of the B method to the formalisation and verification of the GlobalPlatform Card Specification. Although there exists a semi-formal specification and some effort has been put into providing formalisations of particular features of smart card platforms, this is, as far as we know, the very first attempt to provide a complete formalisation. We describe the process followed to synthesise a mathematical model of the platform in the B language, starting from requirements stated in natural language. The model consistency has been thoroughly verified using formal techniques supported by the B method. We also discuss how the smart card industry might benefit from exploiting this formal specification and outline directions for future work. [ABSTRACT FROM AUTHOR]

Abstract interpretation is a particularly well-suited methodology to build modular correctness proof of static analysers. Proof modularity becomes essential when correctness proof is machine checked for realistic languages To deal with complex concrete and abstract domains, the notion of parameterised concretization has been proposed to allow a structural decomposition of the abstract domain and its concretization. In this paper we develop proof principles for such concretizations, based on the theoretical notion of concretization functor, with the aim of obtaining modular correctness proofs. Our technique has been tested on a machine-checked correctness proof of a static analysis for a Java-like bytecode language. [ABSTRACT FROM AUTHOR]

Multi-Processor Systems-on-Chips (MPSoCs) gather multiple processors and hardware accelerators in a single chip to meet the performance and energy consumption requirements of mobile devices. To follow the rapid evolution of such applications, the MPSoC community need flexible and programmable platforms intended to be diverted to many use cases, and hence consider definitely the software as one of the main aspects of the system design. To deal with an ever growing complexity when designing for such heterogeneous and evolving platforms, software developers have to adopt a novel software design methodology that encourages the software customization through modularity, reuse and module assembly to build systems and applications. Component-based Software Engineering (CBSE), enabling software customization by adding, removing and substituting components seems to be adequate to reach that goal. We investigate this area while developing Think, a lightweight implementation of the Fractal component model, which applies CBSE principles down to the lowest software layer: the operating system. Think allows various kinds of communication semantics from simple method invocations to RPC, recursive component composition, and comes with retargetable configuration and specification tools. In this paper, we show how Think can make flexible and customizable the operating system and application design for MPSoC a reality. [ABSTRACT FROM AUTHOR]

System software for deeply embedded devices has to cope with a broad variety of requirements and platforms, but especially with strict resource constraints. To compete against proprietary systems (and thereby to facilitate reuse), an operating system product line for deeply embedded systems has to be highly configurable and tailorable. It is therefore crucial that all selectable and configurable features can be encapsulated into fine-grained, exchangeable and reusable implementation components. However, the encapsulation of non-functional properties is often limited, due to their cross-cutting character. Fundamental system policies, like synchronization or activation points for the scheduler, have typically to be reflected in many points of the operating system component code. The presented approach is based on feature modeling, C++ class composition and overcomes the above mentioned problems by means of aspect-oriented programming (AOP). It facilitates a fine-grained encapsulation and configuration of even non-functional properties in system software. [ABSTRACT FROM AUTHOR]

Much recent work on proof-carrying code aims to build certifying compilers for single-inheritance object-oriented languages, such as Java or C#. Some modern object-oriented languages support compiling a derived class without complete information about its base class. This strategy—though necessary for supporting features such as mixins, traits, and first-class classes—is not well-supported by existing typed intermediate languages. We present a low-level IL with a type system based on the Calculus of Inductive Constructions. It is an appropriate target for efficient, type-preserving compilation of various forms of inheritance, even when the base class is unknown at compile time. Languages (such as Java) that do not require such flexibility are not penalized at run time. [ABSTRACT FROM AUTHOR]

Memory is one of the scarcest resource of embedded and constrained devices. This paper studies the memory footprint benefit of pre-deploying embedded Java systems up to their activation using romization. We find out that the more the system is deployed off-board, the more it can be efficiently and automatically customized in order to reduce its final size. This claim is validated experimentally through the production of memory images that are between 10% and 45% the size of their J2ME CLDC counterparts, while using the J2SE API and being ready-to-run without any further on-board initialization. Embedded solutions like J2ME degrade the Java environment and API right from their specification, limiting their usage perspectives. By contrast, our romization scheme generates and specializes a custom-tailored Java API for embedded applications deployed in a full-fledged J2SE environment. [ABSTRACT FROM AUTHOR]

We study secure information flow in a stack based Typed Assembly Language (TAL). We define a TAL with an execution stack and establish the soundness of its type system by proving non-interference. One of the problems of studying information flow for a low-level language is the absence of high-level control flow constructs that guide information flow analysis in high-level languages. Furthermore, in the presence of an execution stack, code that frees space on the stack must be constrained in order to avoid illegal flows. Finally, in the presence of stack polymorphism, we must ensure that type variables are instantiated without observable differences. These issues are addressed by introducing junction points into the type system, ensuring that they behave as ordered linear continuations, and that they interact safely with the execution stack. We also discuss several limitations of our approach and point out some remaining open issues. [ABSTRACT FROM AUTHOR]

This paper introduces notions of resource policy for mobile code to be run on smart devices, to integrate with the proof-carrying code architecture of the Mobile Resource Guarantees (MRG) project. Two forms of policy are used: guaranteed policies which come with proofs and target policies which describe limits of the device. A guaranteed policy is expressed as a function of a methods input sizes, which determines a bound on consumption of some resource. A target policy is defined by a constant bound and input constraints for a method. A recipient of mobile code chooses whether to run methods by comparing between a guaranteed policy and the target policy. Since delivered code may use methods implemented on the target machine, guaranteed policies may also be provided by the platform; they appear symbolically as assumptions in delivered proofs. Guaranteed policies entail proof obligations that must be established from the proof certificate. Before proof, a policy checker ensures that the guaranteed policy refines the target policy; our policy format ensures that this step is tractable and does not require proof. Delivering policies thus mediates between arbitrary target requirements and the desirability to package code and certificate only once. [ABSTRACT FROM AUTHOR]

Today many interactions are carried out online through Web sites and e-services and often private and/or sensitive information is required by service providers. A growing concern related to this widespread diffusion of on-line applications that collect personal information is that users' privacy is often poorly managed and sometimes abused. For instance, it is well known how personal information is often disclosed to third parties without the consent of legitimate data owners or that there are professional services specialized on gathering and correlating data from heterogeneous repositories, which permit to build user profiles and possibly to disclose sensitive information not voluntarily released by their owners. For these reasons, it has gained great importance to design systems able to fully preserve information privacy by managing in a trustworthy and responsible way all identity and profile information. In this paper, we investigate some problems concerning identity management for e-services and present the architecture of the Access Control Decision Function, a software component in charge of managing access request in a privacy-aware fashion. The content of this paper is a result of our ongoing activity in the framework of the PRIME project (Privacy and Identity Management for Europe) [18], funded by the European Commission, whose objective is the development of privacy-aware solutions for enforcing security. [ABSTRACT FROM AUTHOR]

This short paper introduces the issues and challenges of next generation Java-based smart card platforms. Betting on a continuous evolution toward open computing devices, next generation cards will consist in embedded Java micro-server platforms. Those platforms will be able to serve various types of services and applications thanks to two important system features: adaptability and maintainability. Two features that have to be carefully taken into account in the research perspectives described in this paper: real Java for cards, cards integration in a networked world, and flexible and adaptable cards. [ABSTRACT FROM AUTHOR]

Explicit-State Model Checking is a well-studied technique for the verification of concurrent programs. Due to exponential costs associated with model checking, researchers often focus on applying model checking to software units rather than whole programs. Recently, we have introduced a framework that allows developers to specify and model check rich properties of Java software units using the Java Modeling Language (JML). An often overlooked problem in research on model checking software units is the problem of environment generation: how does one develop code for a test harness (representing the behaviors of contexts in which a unit may eventually be deployed) for the purpose of driving the unit being checked along relevant execution paths? In this paper, we build on previous work in the testing community and we focus on the use of coverage information to assess the appropriateness of environments and to guide the design/modification of environments for model checking software units. A novel aspect of our work is the inclusion of specification coverage of JML specifications in addition to code coverage in an approach for assessing the quality of both environments and specifications. To study these ideas, we have built a framework called MAnTA on top of the Bogor Software Model Checking Framework that allows the integration of a variety of coverage analyses with the model checking process. We show how we have used this framework to add two different types of coverage analysis to our model checker (Bogor) and how it helped us find coverage holes in several examples. We make an initial effort to describe a methodology for using code and specification coverage to aid in the development of appropriate environments and JML specifications for model checking Java units. [ABSTRACT FROM AUTHOR]

The early validation of components specifications requires a proven correct formalization of the functional behavior. We use the ACL2 theorem prover the establish safety properties on it. After the first design step, we automatically translate the synthesizable VHDL into a functional form. The combination of symbolic simulation, automatic transfer function extraction, and theorem proving is used to show that the VHDL design is functionally compliant to the specification. The approach is demonstrated on a SHA-1 cryptographic circuit. [ABSTRACT FROM AUTHOR]

Ubiquitous computing requires new paradigms to assist users organizing and performing daily tasks. Supporting autonomy and providing secured execution environments are two among a lot of challenging issues. Next generation smart cards, so-called smart devices, are regarded as personal devices providing a secured execution and storage environment for application tasks and sensitive privacy information, respectively. Hardware evolution of smart devices enables them to provide capacity to host personal agents, implemented as mobile agents. Mobile agents perform essential tasks such as service negotiation in order to enable automated dynamic service delivery. This paper presents our middleware and a service delivery pattern for user-centric service provisioning by applying mobile agents to smart devices. We further discuss how the middleware platform can be integrated with a security framework for a federation of mobile agents, where a smart device is used as a central trusted entity. [ABSTRACT FROM AUTHOR]

Security policies are rules that constrain the behaviour of a system. Different, largely unrelated sets of rules typically govern the physical and logical worlds. However, increased hardware and software mobility forces us to consider those rules in an integrated fashion. We present SPIN models of four case studies where mobility plays a role. At present our models are ad-hoc. In each case the model captures both the system of interest and its security policy. The model is then formally checked against a security principle. The model checking activity shows examples of policies that are too weak to cope with mobility. [ABSTRACT FROM AUTHOR]

The JavaCard transaction mechanism can ensure that a sequence of statements either is executed to completion or is not executed at all. Transactions make verification of JavaCard programs considerably more difficult, because they cannot be formalised in a logic based on pre- and postconditions. The KeY system includes an interactive theorem prover for JavaCard source code that models the full JavaCard standard including transactions. Based on a case study of realistic size we show the practical difficulties encountered during verification of safety properties. We provide an assessment of current JavaCard source code verification, and we make concrete suggestions towards overcoming the difficulties by design for verification. The main conclusion is that largely automatic verification of realistic JavaCard software is possible provided that it is designed with verification in mind from the start. [ABSTRACT FROM AUTHOR]

A Java Card applet is, in general, not allowed to access fields and methods of other applets on the same smart card. This applet isolation property is enforced by dynamic checks in the Java Card Virtual Machine. This paper describes a refined type system for Java Card that enables static checking of applet isolation. With this type system, firewall violations are detected at compile time. Only a special kind of downcast requires dynamic checks. [ABSTRACT FROM AUTHOR]

The ESC/Java tool was a lauded advance in effective static checking of realistic Java programs, but has become out-of-date with respect to Java and the Java Modeling Language (JML). The ESC/Java2 project, whose progress is described in this paper, builds on the final release of ESC/Java from DEC/SRC in several ways. It parses all of JML, thus can be used with the growing body of JML-annotated Java code; it has additional static checking capabilities; and it has been designed, constructed, and documented in such a way as to improve the tool's usability to both users and researchers. It is intended that ESC/Java2 be used for further research in, and larger-scale case studies of, annotation and verification, and for studies in programmer productivity that may result from its integration with other tools that work with JML and Java. The initial results of the first major use of ESC/Java2, that of the verification of parts of the tally subsystem of the Dutch Internet voting system are presented as well. [ABSTRACT FROM AUTHOR]

As small, secure devices become more powerful and more wide spread, it has become desirable to support the dynamic provisioning and updating of multiple applications on such devices. This paper presents a simple mechanism for performing such provisioning and updating, even if the applications are mutually distrustful. The mechanism extends CLDC JavaTMtechnology with a classfile attribute that carries the certificates necessary to enable the added security. [ABSTRACT FROM AUTHOR]

The growing complexity of new smart card platforms, including multi-subscription or multi-application functionalities, led up to more and more difficulty in testing such systems. In previous work, we have introduced a new method for automated test generation from state-based formal specifications (B abstract machines, UML/OCL models, Z specifications). This method uses cause-effect analysis and boundary computation to produce test cases as sequences of operation invocations. This method is embedded in a model-based test generator which has been exercised on several applications in the domain of smart card software (GSM 11-11 application, electronic purse system and Java Card transaction mechanism). In all these applications, a B abstract machine was built specifically for automatic test generation by an independent validation team. Writing a specific formal model for testing has been shown to be cost-effective, and has the advantages that it can be tailored towards the desired test objectives. This paper focuses on showing the application of this test generation process from formal models in the context of Smart Card applications. We describe how the test generation can be controlled by using several model coverage criteria. These criteria are of three kinds: multiple condition coverage, boundary-value coverage and behavior coverage. This makes it possible to generate a systematic minimal test suite achieving strong coverage results. The test engineer chooses the criteria depending on the application test objectives and then fully controls the test generation process. Keywords: Automated test generation, functional testing, boundary testing, formal specifications, smart card standard. [ABSTRACT FROM AUTHOR]

The Spec# programming system is a new attempt at a more cost effective way to develop and maintain high-quality software. This paper describes the goals and architecture of the Spec# programming system, consisting of the object-oriented Spec# programming language, the Spec# compiler, and the Boogie static program verifier. The language includes constructs for writing specifications that capture programmer intentions about how methods and data are to be used, the compiler emits run-time checks to enforce these specifications, and the verifier can check the consistency between a program and its specifications. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of static checking of programs to ensure that they satisfy confidentiality policies in the presence of dynamic access control in the form of Abadi and Fournet's history-based access control mechanism. The Java virtual machine's permission-based stack inspection mechanism provides dynamic access control and is useful in protecting trusted callees from untrusted callers. In contrast, history-based access control provides a stateful view of permissions: permissions after execution are at most the permissions before execution. This allows protection of both callers and callees. The main contributions of this paper are to provide a semantics for history-based access control and a static analysis for confidentiality that takes history-based access control into account. The static analysis is a type and effects analysis where the chief novelty is the use of security types dependent on permission state. We also show that in contrast to stack inspection, confidential information can be leaked by the history-based access control mechanism itself. The analysis ensures a noninterference property formalizing confidentiality. [ABSTRACT FROM AUTHOR]

We present the Mobile Resource Guarantees framework: a system for ensuring that downloaded programs are free from run-time violations of resource bounds. Certificates are attached to code in the form of efficiently checkable proofs of resource bounds; in contrast to cryptographic certificates of code origin, these are independent of trust networks. A novel programming language with resource constraints encoded in function types is used to streamline the generation of proofs of resource usage. [ABSTRACT FROM AUTHOR]

This report gives an overview of the sixth Workshop on Formal Techniques for Java-like Programs at ECOOP 2004. It explains the motivation for the a workshop and summarises the presentations and discussions. [ABSTRACT FROM AUTHOR]

This paper describes a way of modeling inheritance (in object-oriented programming languages) in higher order logic. This particular approach is used in the LOOP project for reasoning about JAVA classes, with the proof tools PVS and ISABELLE. It relies on nested interface types to capture the superclasses, fields, methods, and constructors of classes, together with suitable casting functions incorporating the difference between hiding of fields and overriding of methods. This leads to the proper handling of late binding, as illustrated in several verification examples. [ABSTRACT FROM AUTHOR]

A formal language CCSL is introduced for describing specifications of classes in object-oriented languages. We show how class specifications in CCSL can be translated into higher order logic. This allows us to reason about these specifications. In particular, it allows us (1) to describe (various) implementations of a particular class specification, (2) to develop the logical theory of a specific class specification, and (3) to establish refinements between two class specifications. We use the (dependently typed) higher order logic of the proof-assistant PVS, so that we have extensive tool support for reasoning about class specifications. Moreover, we describe our own front-end tool to PVS, which generates from CCSL class specifications appropriate PVS theories and proofs of some elementary results. [ABSTRACT FROM AUTHOR]

There is an overwhelming number of different proof tools available and it is hard to find the right one for a particular application. Manuals usually concentrate on the strong points of a proof tool, but to make a good choice, one should also know (1) which are the weak points and (2) whether the proof tool is suited for the application in hand. This paper gives an initial impetus to a consumers' report on proof tools. The powerful higher-order logic proof tools PVS and Isabelle are compared with respect to several aspects: logic, specification language, prover, soundness, proof manager, user interface (and more). The paper concludes with a list of criteria for judging proof tools, it is applied to both PVS and Isabelle. [ABSTRACT FROM AUTHOR]