School of Computing - Research - Working Papers - 2000

Working Papers for 2000

Gobo Lex and Yacc on the Java Virtual Machine,
J Waldron, J Power and R. Dempster

Dynamic quantatative measurements of Bytecode and Stack Frame Usage by Eiffel and Java Programs in the Java Virtual Machine is made. Two Eiffel programs are dynamically analysed while executing on the JVM, and the results compared with those from the Java Programs. The aim is to examine whether properties like instruction usage and stack frame size are properties of the Java programming language itself or are exhibited by Eiffel programs as well. Investigations analyse how the different assertion checking and optimizations possible using the SmallEiffel compiler affect bytecode and stack frame usage. Remarkably local_load, push_const and local_store instruction categories always account for very close to 40% of instructions executed, a property of the Java Virtual Machine irrespective of the programming language compiler or compiler optimizations used. Java programs executed 75% of their bytecodes within the API suggesting a way to improve the speed of Java programs would be to compile the API methods to native instructions and save these on disk in a standard format, cutting the time spent interpreting programs. Only 4.8% of instruction were in the API when Eiffel programs executed.

A comparison of component technologies based on Microsoft's Component Object Model and Sun Microsystems JavaBeans using a case study from the Financial sector,
Sean O'Donnell

The objective of this thesis is to evaluate software component technologies. To be more specific, it compares two of the leading implementations of software component technologies in the marketplace today, Microsoft's Component Object Model (COM) and Sun Microsystems Java Beans (including Enterprise Java Beans). To provide the basis for a fair comparison, both technologies were used to implement the same problem chosen from the financial services sector.

The Airline Crew Rostering Problem,
Tríona Ní Éigeartaigh, David Sinclair

The Airline Crew Rostering Problem (CRP) is concerned with finding the minimum number of flight crew to satisfy a given flight schedule while complying with a number of restrictions, such as safety regulations, union requirements and company policy.
The Airline Crew Rostering Problem is NP-Hard, which means that no exact optimal algorithm exists for solving practical problems. Many studies have been conducted in this field of research over the past forty years and solutions proposed have included exact approaches (based on the set covering problem), heuristic algorithms and also hybrid methods.
We propose a new branch & bound algorithm that views the Airline Crew Rostering Problem as a hypergraph vertex cover problem. Section 1 provides a definition of the problem and offers an overview of the proposed solution. Section 2 reviews existing techniques and published material. We examine the complexity of the Crew Rostering Problem in Section 3 and also present our new algorithm: the Hypergraph Vertex Cover Algorithm.
In Section 4 we focus on the performance and evaluation of our algorithm. Finally, Section 5 outlines our conclusions and recommendations.

Towards an Action Refinement Calculus for Abstract State Machines,
Claus Pahl

Refinement is the process of deriving specifications on a lower level of abstraction from those on a higher level. A refinement calculus for Abstract State Machines allowing to derive action specifications from another - preserving the semantics of the abstract specification - will be outlined. Abstract state machines are rephrased as objects with local state. These objects are the structures in which a modal logic of actions is interpreted. Our refinement calculus will be defined on relations between action specifications on different levels of abstraction. This extended version includes additional material on the ASM object refomulation and an extended treatment of the refinement calculus including more examples and related work.

This is an extended version of Claus Pahl: Towards an Action Refinement Calculus for Abstract State Machines, Workshop on Abstract State Machines, Monte Verita, Switzerland, March 2000.

Key Exchange using Lucas exponentiation,
Michael Scott

By using Lucas exponentiation we improve a key distribution scheme first proposed by McCurley into one which is secure against passive attack assuming the intractability of integer factorisation and a discrete logarithm problem of equal complexity.

Internet Protocol version 6 (IPv6) : What is it and migration mechanisms,
Richard Frisby, Brian Stone

IPv6 is the new version of the Internet Protocol (IP) on which communication on the Internet and intranets is based. Many believe that IP will be the only layer 3 protocol in the near future. An analysis of the classful structure of the current IP addressing scheme (IPv4), coupled with the enormous growth of the Internet over the last number of years, reveals the need for a new addressing scheme, which must provide sufficient addresses into the millennium. However several 'patches' such as Classless Inter-Domain Routing (CIDR) and Network Address Translation (NAT) have prolonged the lifetime of IPv4.
Other shortcomings of IPv4 such as its 'best-effort' delivery mechanism, lack of support for Quality of Service (QoS) and mobile users, and the manner in which security is handled, have all contributed towards the need for an improved Internet protocol. Using IPv4 there is no facility for encryption and authentication of traffic, therefore extensions to the IPv4 stack are required. IPv6 incorporates the IPsec security standards specification which should have a significant impact on the overall security of the Internet. The IPsec standards are divided into two categories, Authentication Header (AH) and Encapsulating Security Payload (ESP). The AH obviously provides authentication, a guarantee that the packet of information originated from the source address specified and that the packet was not altered during transmission. The ESP guarantees that only legitimate receivers of the packet can read its content. As the adoption of IPv6 occurs, it is likely that we will see much more security functionality implemented at the network-stack level.
This paper outlines the need for a new Internet Protocol, examines the new features and structure of IPv6 and highlights the various issues to be considered and mechanisms currently available when migrating from IPv4 to IPv6.

Component Based Development: Applied in a Real Time Embedded Environment,
Rudie Dorrepaal, Renaat Verbruggen

In this paper we investigate what is required to set up an embedded environment for reusable components and we see how all this can be applied to a real-time security system. We see what a reusable component is and what the general requirements for reusable components are. We examine how components can be specialised. We name several frameworks and look at the Enterprise JavaBeans infrastructure in detail.
In chapter 3 we will look at how we can create an environment for component-based software for Real-Time embedded systems. The biggest challenge here is how to connect the components together, so that they can communicate with each other efficiently and at the same time meet all their real time requirements. The framework for embedded component-based real-time software is based on David Steward's Port Based Object (PBO) abstraction of a component. In paragraph 3.3 we compare Enterprise JavaBeans to the Port Based Object Model.
In chapter 4 we give an example of an embedded security system, to examine how we can apply the theory of the previous chapters to a practical situation. In this example we see how we can relate the different UML diagrams to embedded components. We show a nested UML state diagram and show plug-ins in UML. We show the output subsystem where we see that the runtime event interface is the same for all output components and so we can hide the individual output components interfaces. We examine the user interface component and show the corresponding use-case diagrams that are suitable to this component. In paragraph 4.5 we look at UML deployment diagrams and an UML sequence diagram.

Formal Methods and Feature Interactions in the Plain Old Telephone System,
Patricia McQuillan, Geoff Hamilton

Without features, the telephone interface is simple and can easily be taught to a child, but the addition of telephone features makes the telephone's behaviour hard for an adult to understand. The difficulty arises not just from the need to learn several ways of using the telephone, but also from the interactions among features, which can cause each feature to behave differently in the presence of other features. Two or more features of a telephone service are said to interact if one changes the behaviour of the other. Features may also behave differently because their liveness requirements are not satisfied. These liveness requirements may be satisfied in the individual feature but are broken upon composition. One of the main objectives here is to attempt to resolve broken liveness requirements with the addition of fairness constraints. An application was developed to determine the feasibility of such liveness requirement restoration.
The tool developed can attempt to restore or satisfy liveness requirements in two different ways. The first way is to try to guarantee that the environmental liveness requirements of synchronisation actions are satisfied when two components are composed. Restoration of broken environmental liveness requirements will be attempted through the addition of fairness constraints. The second way is to try to satisfy liveness requirements entered by the user. This may also involve the addition of fairness constraints. The tool developed can be considered to be a model checker that verifies safety and liveness requirements with the additional capability of attempting broken liveness requirement restoration.

Combinator Parsers in C++: Integrating Grammar-Flow Analysis and Design Patterns,
Lisa Cosgrave, James Power, John Waldron

In this paper we describe the design and implementation of a system for representing context-free grammars in C++. The system allows for grammar representation at the object level, providing enhanced modularity and flexibility when compared to traditional generator-based approaches. We also describe the transformation of grammar flow analysis problems into an object-oriented framework using the Visitor pattern, as well as the implementation of a top-down LL(1) parser. As such, this work represents the synthesis of three presently disparate fields in parser design and implementation: combinator parsing, fixpoint-based grammar flow analysis, and object-oriented design.

Attacks on the Discrete Logarithm,
Michael J. Timmons, Mike Scott

I present a method for recovering the private key from the public parameters in the Diffie-Hellman key exchange. This method is restricted to prime-order subgroups (e.g. over Zp a 160-bit exponent and a 512-bit prime). It is a technique for solving the Discrete Logarithm problem in a subgroup of a large prime. The technique combines a method similar to Shanks' [7] with a space-saving device, to give a deterministic solution to the Discrete Logarithm. This attack does not threaten current implementations, but rather decreases the storage requirements of an existing algorithm.

Development of Technical Software - Case Study Notes,
W.G. Tuohey

A number of case studies in software development are presented. Then, aspects of software development in general are discussed in the light of these cases. The intention is to provide, in a digestible form, information that will be of practical value. The focus of the discussion is on projects with a fairly high engineering and mathematical content but much of the material presented is applicable to software developments of any kind. Conclusions and lessons learned are noted throughout, most significant of which include (1) Importance of the software requirements definition phase, (2) Need for a clear strategy to handle user requirements that are incomplete or immature, (3) Willingness to apply new methods and tools, but in an orderly and planned manner, and (4) Ensuring the development schedule accommodates time for adequate review.

Effort profile & scheduling implications of ESA's SW engineering standards,
W.G. Tuohey

The European Space Agency's Software Engineering Standards (PSS-05-0), and other similar standards, specify the elements of software projects, their phases, the technical activities within each phase, the review processes, the documentation, the associated managerial work, configuration management tasks, and so on. This paper offers an approach to synthesising these several elements with the objective of assessing impact on project planning, particularly in terms of effort expenditure profile and schedule. A number of representative model projects are analysed and implications for practice are noted.

MIKE - Mike's Integrated Key Exchange,
Michael Scott

A new key exchange algorithm is presented which integrates a low-entropy password into the well-established Diffie-Hellman key exchange. The proposed method has some advantages with respect to existing techniques such as SPEKE and PAK.