Professor Helen Treharne

Swarm attestation protocols extend remote attestation by allowing a verifier to efficiently measure the integrity of software code running on a collection of heterogeneous devices across a network. Many swarm attestation protocols have been proposed for a variety of system configurations. However, these protocols are currently missing explicit specifications of the properties guaranteed by the protocol and formal proofs of correctness. In this paper, we address this gap in the context of list swarm attestation protocols, a category of swarm attestation protocols that allow a verifier to identify the set of healthy provers in a swarm. We describe the security requirements of swarm attestation protocols. We focus our work on the SIMPLE+ protocol, which we model and verify using the tamarin prover. Our proofs enable us to identify two variations of SIMPLE+: (1) we remove one of the keys used by SIMPLE+ without compromising security, and (2) we develop a more robust design that increases the resilience of the swarm to device compromise. Using tamarin, we demonstrate that both modifications preserve the desired security properties.

We define and formalise a generic cryptographic construction that underpins coupling of companion devices, e.g., biometrics-enabled devices, with main devices(e.g., PCs), in a user-aware manner, mainly for on-demand authentication and secure storage for applications running on the main device. We define the security requirements of such constructions, provide a full instantiation in a protocol-suite and prove its computational as well as Dolev-Yao security. Finally, we implement our protocol suite and one password-manager use-case

LoRaWAN (Low-power Wide-Area Networks) is the main specification for application-level IoT (Internet of Things). The current version, published in October 2017, is LoRaWAN 1.1, with its 1.0 precursor still being the main specification supported by commercial devices such as PyCom LoRa transceivers. Prior (semi)-formal investigations into the security of the LoRaWAN protocols are scarce, especially for Lo-RaWAN 1.1. Moreover, amongst these few, the current encodings [4], [9] of LoRaWAN into verification tools unfortunately rely on much-simplified versions of the LoRaWAN protocols, undermining the relevance of the results in practice. In this paper, we fill in some of these gaps. Whilst we briefly discuss the most recent cryptographic-orientated works [5] that looked at LoRaWAN 1.1, our true focus is on producing formal analyses of the security and correctness of LoRaWAN, mechanised inside automated tools. To this end, we use the state-of-the-art prover, Tamarin. Importantly, our Tamarin models are a faithful and precise rendering of the LoRaWAN specifications. For example, we model the bespoke nonce-generation mechanisms newly introduced in LoRaWAN 1.1, as well as the "classical" but shortdomain nonces in LoRaWAN 1.0 and make recommendations regarding these. Whilst we include small parts on device-commissioning and application-level traffic, we primarily scrutinise the Join Procedure of LoRaWAN, and focus on version 1.1 of the specification, but also include an analysis of Lo-RaWAN 1.0. To this end, we consider three increasingly strong threat models, resting on a Dolev-Yao attacker acting modulo different requirements made on various channels (e.g., secure/insecure) and the level of trust placed on entities (e.g., honest/corruptible network servers). Importantly, one of these threat models is exactly in line with the LoRaWAN specification, yet it unfortunately still leads to attacks. In response to the exhibited attacks, we propose a minimal patch of the LoRaWAN 1.1 Join Procedure, which is as backwards-compatible as possible with the current version. We analyse and prove this patch secure in the strongest threat model mentioned above. This work has been responsibly disclosed to the LoRa Alliance, and we are liaising with the Security Working Group of the LoRa Alliance, in order to improve the clarity of the LoRaWAN 1.1 specifications in light of our findings, but also by using formal analysis as part of a feedback-loop of future and current specification writing.

Event-B provides a flexible framework for stepwise system development via refinement. The framework supports steps for (a) refining events (one-by-one), (b) splitting events (one-by-many), and (c) introducing new events. In each of the steps events can moreover possibly be anticipated or convergent. All such steps are accompanied with precise proof obligations. Still, it remains unclear what the exact relationship - in terms of a behaviour-oriented semantics - between an Event-B machine and its refinement is. In this paper, we give a CSP account of Event-B refinement, with a treatment for the first time of splitting events and of anticipated events. To this end, we define a CSP semantics for Event-B and show how the different forms of Event-B refinement can be captured as CSP refinement.

In this paper we propose a new imperceptible yellow printer dot watermarking scheme for documents printed on a colour printer. The scheme takes advantage of the imperfections of the human visual system to hide thousands of yellow dots over the entire page. It takes inspiration from the methods used by laser printer manufacturers for printer identification. The novelty of our approach is in providing an automatic embedding and detection method that can survive the distortions of printing and scanning. In order to achieve this a new moving window detection method is proposed. An error correction code is employed to handle the errors that could be present following detection. The scheme is evaluated through embedding and detection experiments on different types of documents; including text, architectural drawings and a cartoon. Our scheme offers an embedding capacity of 26,190 bits per page. Experiments were conducted using error correction codes with rates of 1/2, 1/3 and 1/5, given payloads of 13,095, 8,730, and 5,238 bits per A4 page respectively. We are able to successfully recover the watermark in all documents at a rate of 1/2 and 1/5, and in all document except one at 1/3. Further experiments were conducted with a smaller dot size to evaluate the impact it has on our results. With the smaller dot size we were still able to recover the watermarks from all documents when using an error correction code with rate 1/5. The capacity offered by this approach far exceeds the capacity offered by existing binary watermarking schemes, which are robust to printing and scanning. The substantially larger capacity opens up a wider range of possible applications as well as the possibility of using more robust cryptographic techniques for authentication.

This paper considers the issues involved in translating specifications described in the CSP||B formal method into Handel-C. There have previously been approaches to translating CSP descriptions to Handel-C, and the work presented ill this paper is part of a programme of work to extend it to include the B component of a CSP parallel to B description. Handel-C is a suitable target language because of its capability of programming communication and state. and its compilation route to hardware. The paper presents two case studies that investigate aspects of the translation: a buffer case study, and all abstract arbiter case Study. These investigations have exposed a number of issues relating to the translation of the B component, and have identified a range of options available, informing more recent work oil the development of a style for CSP parallel to B specifications particularly appropriate to translation to Handel-C.

This paper introduces action refinement in the context of CSP||B. Our motivation to include this notion of refinement within the CSP parallel to B framework is the desire to increase flexibility in the refinement process. We introduce the ability to change the events of a CSP process and the B machines when refining a system. Notions of refinement based on traces and on traces/divergences are introduced in which abstract, events arc, refined by sequences of concrete events. A complementary notion of refinement between B machines is also introduced, yielding compositionality results for refinement of CSP parallel to B controlled components. The paper also introduces a notion of I/O refinement into our action refinement framework.

Prˆet `a Voter and Punchscan are two electronic voting schemes that both use paper based ballot forms, part of which is detached and destroyed, to provide receipt-free voter verifiability. However, both schemes share the chain voting problem and the part destruction problem. The first is where anyone who can see the ballot form before it is used can coerce a voter who uses it and the latter where a voter who can leave with the complete form can prove to a coercer the contents of the vote. In this paper we provide a comparison of the schemes from a systems perspective. We also introduce a visual encryption solution to both the above problems.

Recent work on combining CSP and B has provided ways of describing systems comprised of components described in both B (to express requirements on state) and CSP (to express interactive and controller behaviour). This approach is driven by the desire to exploit existing tool support for both CSP and B, and by the need for compositional proof techniques. This paper is concerned with the theory underpinning the approach, and proves a number of results for the development and verification of systems described using a combination of CSP and B. In particular, new results are obtained for the use of the hiding operator, which is essential for abstraction. The paper provides theorems which enable results obtained (possibly with tools) on the CSP part of the description to be lifted to the combination. Also, a better understanding of the interaction between CSP controllers and B machines in terms of non-discriminating and open behaviour on channels is introduced, and applied to the deadlock-freedom theorem. The results are illustrated with a toy lift controller running example.

Direct Anonymous Attestation (Daa) is a set of cryptographic schemes used to create anonymous digital signatures. To provide additional assurance, Daa schemes can utilise a Trusted Platform Module (Tpm) that is a tamper-resistant hardware device embedded in a computing platform and which provides cryptographic primitives and secure storage. We extend Chen and Li’s Daa scheme to support: 1) signing a message anonymously, 2) self-certifying Tpm keys, and 3) ascertaining a platform’s state as recorded by the Tpm’s platform configuration registers (PCR) for remote attestation, with explicit reference to Tpm 2.0 API calls.We perform a formal analysis of the scheme and are the first symbolic models to explicitly include the low-level Tpm call details. Our analysis reveals that a fix proposed by Whitefield et al. to address an authentication attack on an Ecc-Daa scheme is also required by our scheme. Developing a finegrained, formal model of a Daa scheme contributes to the growing body of work demonstrating the use of formal tools in supporting security analyses of cryptographic protocols. We additionally provide and benchmark an open-source C++ implementation of this Daa scheme supporting both a hardware and a software Tpm and measure its performance.

CSP||B is an approach to combining the process algebra CSP with the formal development method B, enabling the formal description of systems involving both event-oriented and state-oriented aspects of behaviour. The approach provides architectures which enable the application of CSP verification tools and B verification tools to the appropriate parts of the overall description. Previous work has considered how large descriptions can be verified using coarse grained component parts. This paper presents a generalisation of that work so that CSP vertical bar vertical bar B descriptions can be decomposed into finer grained components, chunks, which focus on demonstrating the absence of particular divergent behaviour separately. The theory underpinning chunks is applicable not only to CSP vertical bar vertical bar B specification but to CSP specifications. This makes it an attractive technique to decomposing large systems for analysing with FDR.

Much research work has been done on formalizing UML diagrams, but less has focused on using this formalization to analyze the dynamic behaviours between formalized components. In this paper we propose using a subset of fUML (Foundational Subset for Executable UML) as a semi-formal language, and formalizing it to the process algebraic specification language CSP, to make use of FDR as a model checker. Our formalization includes modelling the asynchronous communication framework used within fUML. This allows different interpretations of the communications model to be evaluated. To illustrate the approach, we use the modelling of the Tokeneer ID Station specifications into fUML, and formalize them in CSP to check if the model is deadlock free.

Our aim is to develop a watermarking method for formatted text documents that is robust to printing and scanning, but with a greater capacity than has previously been achieved. Our end goal is to develop a system with sufficient capacity to embed a simple authenticating watermark. Our method is based on our previous technique of multi-set embedding but now makes use of all word spaces and treats the document as one long line. As part of the modifications we propose a new method of calculating the threshold between letter and word spaces, based on frequency distributions, and have modified the way we conduct threshold buffering. Experiments have been carried out at two different resolutions, 150dpi and 300dpi, on 9 different documents using three different watermarks. We have seen an average increase in capacity of 20 percent whilst also improving the level of robustness to printing and scanning. © 2007 IEEE.

Much research work has been done on linking UML, and formal methods but few have focused on using formal methods to check the integrity of the UML models so that the models can be verified. In this paper we focus on executable UML and on the issues related to concurrent state machines. We show that one integrated formal methods approach, CSP parallel to B, has the potential to be tailored to support reasoning about concurrent state machines and in turn expose any weaknesses in the UML model. We identify future avenues of research so that a system methodology based on executable UML can be enhanced by formal reasoning.

This paper reports on the preparation of test cases using a prototype within the context of a formal development. It describes an approach to building a prototype using an example. It discusses how a prototype contributes to the testing activity as part of a lifecycle based on the use of formal methods. The results of applying the approach to an embedded avionics case study are also presented.

In this paper we propose a new authentication and localisation scheme to produce a watermark which can be embedded in a limited capacity binary text document and that will work in a print and scan environment. The scheme utilises Message Authentication Codes (MAC), specifically OMACs, which create a cryptographic fixed-length summary of a document. An OMAC must be truncated to a form part of our watermark and is used during authentication. The remainder of the watermark is used during localisation. We have created over 2,000,000 watermarks in controlled experiments to evaluate their ability to authenticate a document and localise any changes. In addition, we have embedded an authenticating watermark into seven different documents and authenticated them after printing and scanning.

CSP ∥ B is a formal approach to specification that combines CSP and B. In this paper we present our tool that automatically translates a subset of executable UML (xUML) models into CSP ∥ B, for the purpose of verification and increased validation at the early stages of a software engineering development lifecycle. The tool is being developed for our industrial collaborators, AWE plc, in order to strengthen their software engineering process which uses xUML. As part of this process, AWE and Kennedy Carter Ltd. have built an xUML to SPARK Ada code generator, which is also employed to contribute a higher level of safety assurance at the latter stages of the lifecycle. Our tool is based on a model-text transformation strategy that uses the xUML meta-model to map to CSP and B constructs. The tool generates machine readable CSP and B; we present a simple example to demonstrate the transformation strategy, and the analysis of the resulting specification.

Anonymous Single-Sign-On authentication schemes have been proposed to allow users to access a service protected by a verifier without revealing their identity. This has become more important with the introduction of strong privacy regulations. In this paper we describe a new approach whereby anonymous authentication to different verifiers is achieved via authorisation tags and pseudonyms. The particular innovation of our scheme is that authentication can occur only between a user and its designated verifier for a service, and the verification cannot be performed by any other verifier. The benefit of this authentication approach is that it prevents information leakage of a user's service access information, even if the verifiers for these services collude. Our scheme also supports a trusted third party who is authorised to de-anonymise the user and reveal her whole service access information if required. Furthermore, our scheme is lightweight because it does not rely on attribute or policy-based signature schemes to enable access to multiple services. The scheme's security model is given together with a security proof, an implementation and a performance evaluation.

In this paper, a least distortion approach is proposed for halftone image watermarking. The impacts of distortion and tonality problems in halftoning are analyzed. An iterative linear gain model is developed to optimize perceptual quality of watermarking halftone images with efficient computation complexity O(1). An optimum linear gain for data hiding error diffusion is derived and mapped into a standard linear gain model, with the tonality evaluated using the average power spectral density. As compared with Fu and Au’s data hiding error diffusion method, our experiments show that our proposed linear gain model can achieve an improvement of between 6.5% to 12% using weighted signal-to-noise ratio (WSNR) and an improvement of between 11% to 23% measured by visual image fidelity (VIF).

CSP||B is a formal approach to specification that combines CSP and B. In this paper we present our tool that automatically translates a subset of executable UML (xUML) models into CSP parallel to B, for the purpose of verification and increased validation at the early stages of a software engineering development lifecycle. The tool is being developed for our industrial collaborators, AWE plc, in order to strengthen their software engineering process which uses xUML. As part of this process, AWE and Kennedy Carter Ltd. have built an xUML to SPARK Ada code generator, which is also employed to contribute a higher level of safety assurance at the latter stages of the lifecycle. Our tool is based on a model-text transformation strategy that uses the xUML meta-model to map to CSP and B constructs. The tool generates machine readable CSP and B; we present a simple example to demonstrate the transformation strategy, and the analysis of the resulting specification.

This paper reports on the preparation of test cases using a prototype within the context of a formal development. It describes an approach to building a prototype using an example. It discusses how a prototype contributes to the testing activity as part of a lifecycle based on the use of formal methods. The results of applying the approach to an embedded avionics case study are also presented.

Several formal methods have been proposed for the specification and safety verification of railway applications. In order to be successful they need industrial strength tools to support the animation, proof, model checking and simulation of such systems. The complexity of railway systems means that capabilities of the analysis tools have consistently been improving. In our approach we propose that the complexity of analysis of railway interlocking systems can also be managed through incremental addition of system detail and decomposition of system specifications themselves. We propose a domain specific language (DSL) which describes the core aspects of a railway interlocking system and demonstrate how one can identify suitable decompositions in terms of the DSL. The DSL informs our system engineering approach which uses a graphical editor to input railway scheme plans, supports the automatic generation of CSP jj B specifications of the plans and uses the ProB tool for their animation and model checking.

The B-Method is a state-based formal method that describes behaviour in terms of MACHINES whose states change under OPERATIONS. The process algebra CSP is an event-based formalism that enables descriptions of patterns of system behaviour. We present a combination of the two views where a CSP process acts as a control executive and its events simply drive corresponding OPERATIONS. We define consistency between the two views in terms of existing semantic models. We identify proof conditions which are strong enough to ensure consistency and thus guarantee safety and liveness properties.

In this paper we demonstrate how the formal model constructed in our previous work [1], can be modified in order to analyse additional Buyer-Seller Watermarking Protocols, identifying which specific sections of the CSP scripts remain identical and which require modification. First, we model the protocol proposed by Memon and Wong [2], an examplar of the Offline Watermarking Authority (OFWA) Model, defined in the framework by Poh and Martin [3]. Second, we model the Shao protocol [4] as an example of a protocol fitting the Online Watermarking Authority (ONWA) Model. Our analysis of the protocols reaffirms the unbinding attack described by Lei et al.[5] on the Memon and Wong protocol and we identify a new unbinding attack on the protocol proposed by Shao.

CSP||B is an integration of the process algebra Communicating Sequential Processes (CSP), and the B-Method, which enables consistent controllers to be written for B machines in a verifiable way. Controllers are consistent if they call operations only when they are enabled. Previous work has established a way of verifying consistency between controllers and machines by translating control flow to AMN and showing that a control loop invariant is preserved. This paper offers an alternative approach, which allows fragments of control flow expressed as annotations to be associated with machine operations. This enables designers’ understanding about local relationships between successive operations to be captured at the point the operations are written, and used later when the controller is developed. Annotations provide a bridge between controllers and machines, expressing the relevant aspects of control flow so that controllers can be verified simply by reference to the annotations without the need to consider the details of the machine operations. This paper presents the approach through two instances of annotations with their associated control languages, covering recursion, prefixing, choice, and interrupt.

There is great interest in the application of nanotechnology to medicine, but concerns for safety are paramount. We present a modelling technique based on CSP and B as a starting point for simulation of networks of nano-robots. The model and the simulations are central features of our proposed approach to the construction of safety cases for nanomedicine applications, and complex networks of cooperating components in general. Our work is based on a case study: the clotting behaviour of (artificial) platelets. We present a model, and discuss its analysis and uses

Recent work on combining CSP and B has provided ways of describing systems comprised of components described in both B (to express requirements on state) and CSP (to express interactive and controller behaviour). This approach is driven by the desire to exploit existing tool support for both CSP and B, and by the need for compositional proof techniques. This paper is concerned with the theory underpinning the approach, and proves a number of results for the development and verification of systems described using a combination of CSP and B. In particular, new results are obtained for the use of the hiding operator, which is essential for abstraction. The paper provides theorems which enable results obtained (possibly with tools) on the CSP part of the description to be lifted to the combination. Also, a better understanding of the interaction between CSP controllers and B machines in terms of non-discriminating and open behaviour on channels is introduced, and applied to the deadlock-freedom theorem. The results are illustrated with a toy lift controller running example.

Identifying the originating device for a given media, i.e. the type, brand, model and other characteristics of the device, is currently one of the important fields of digital forensics. This paper proposes a forensic technique based on the Benford’s law to identify the printer’s brand and model from the printed-and-scanned images at which the first digit probability distribution of multi-size block DCT coefficients are extracted that constitutes a feature vector as the input to support vector machine (SVM) classifier. The proposed technique is different from the traditional use of noise feature patterns appeared in the literature. It uses as few as nine numbers of forensic features representing each printer by leveraging properties of the Benford’s law for printer identification. Experiments conducted over electrophotographic (EP) printers and deskjet printers achieve an average of 96.0% classification rate of identification for five distinct printer brands and an average of 94.0% classification rate for six diverse printer models out of those five brands.

In this paper, a least distortion data hiding approach is proposed for halftone image watermarking. The impacts of distortion and tonality problems in halftoning are analyzed. An iterative linear gain model is developed to optimize perceptual quality of watermarking halftone images. An optimum linear gain for data hiding error diffusion is derived and mapped into a standard linear gain model, with the tonality evaluated using the average power spectral density. Our experiments show that the proposed linear gain model can achieve an improvement of between 6.5% to 12% as compared to Fu and Au’s data hiding error diffusion method using the weighted signal-to-noise ratio(WSNR).

Direct Anonymous Attestation (DAA) is a cryptographic scheme that provides Trusted Platform Module (TPM)backed anonymous credentials. We develop TAMARIN modelling of the ECC-based version of the protocol as it is standardised and provide the first mechanised analysis of this standard. Our analysis confirms that the scheme is secure when all TPMS are assumed honest, but reveals a break in the protocol's expected authentication and secrecy properties for all TPMs even if only one is compromised. We propose and formally verify a minimal fix to the standard. In addition to developing the first formal analysis of ECC-DAA, the paper contributes to the growing body of work demonstrating the use of formal tools in supporting standardisation processes for cryptographic protocols.

Online voting for independent elections is generally supported by trusted election providers. Typically these providers do not offer any way in which a voter can verify their vote, and hence the providers are trusted with ballot privacy and in ensuring correctness. Despite the desire to offer online voting for political elections, this lack of transparency and verifiability is often seen as a significant barrier to the large-scale adoption of online elections. Adding verifiability to an online election increases transparency and integrity, as well as allowing voters to verify that the vote they cast has been recorded correctly and included in the tally. However, replacing existing online systems with those that provide verifiable voting requires new algorithms and code to be deployed, and this presents a significant business risk to commercial election providers, as well as the societal risk for official elections selecting for public office. In this paper we present the first step in an incremental approach which minimises the business risk but demonstrates the advantages of verifiability, by developing an implementation of key elements of a Selene-based verifiability layer and adding it to an operational online voting system. Selene is a verifiable voting protocol that publishes votes in plaintext alongside a voter's tracker. These trackers enable voters to confirm that their votes have been captured correctly by the system, such that the election provider does not know which tracker has been allocated to which voter. This results in a system where even a " dishonest but cautious " election authority running the system cannot be sure of changing the result in an undetectable way, and hence gives stronger guarantees on the integrity of the election than were previously present. We explore the challenges presented by adding a verifiability layer to an operational system. The system was used in two initial trials conducted within real contested elections. We conclude by outlining the further steps in the road-map towards the deployment of a fully trustworthy online voting system.

Transforming Unified Modelling Language (UML) models into a formal representation to check certain properties has been addressed many times in the literature. However, the lack of automatic formalization for executable UML models and provision of model checking results as modeller-friendly feedback has inhibited the practical use of such approaches in real life projects. In this paper, we address those issues by performing the automatic formalization of the Foundational subset for executable UML (fUML) models into communicating sequential processes without any interaction with the modeller, who should be isolated from the formal methods domain. The formal analysis provides the modeller with a UML sequence diagram that represents the model checking result in the case where an error has been found in the model. This work also considers the formalization of systems that depend on asynchronous communication between components in order to allow checking of the dynamic concurrent behaviour of systems.We have designed a comprehensive framework that is implemented as a plugin to MagicDraw (the CASE tool we use) that we call Compass. The framework depends on Epsilon as a model transformation tool that utilizes the Model Driven Engineering approach. It also implements an optimization approach to be able to model check concurrent systems using FDR2, and at the same time comply with the fUML inter-object communication mechanism. In order to validate our framework, we have checked a Tokeneer fUML model against deadlock using Compass. The model checking results are reported in this paper showing the advantages of our framework.

Passwords are the de facto standard for authentication despite their significant weaknesses. While businesses are currently focused on implementing multi-factor authentication to provide greater security, user adoption is still low. An alternative, WebAuthn, uses cryptographic key pairs to provide password-less authentication. WebAuthn has been standardised and is resilient to phishing attacks. However, its adoption is also very low; the barriers to adoption include usability and resilience of keys. We propose a novel architecture for password-less authentication designed to improve usability and deployability. Our architecture is based on the WebAuthn standards and supports registration and login to web-services. We support a WebAuthn authenticator that generates and uses the key pairs on the client device by providing resilience for these key pairs by using a backup key store in the cloud. We also propose a WebAuthn authenticator using a key store in the cloud so that password-less authentication can be used interoperably between devices. We also assess the properties of these architectures against identified threats and how they can form the basis for improving usability and lowering the technical barriers to adoption of password-less authentication.

Much research work has been done on linking UML and formal methods but few have focused on using formal methods to check the integrity of the UML models so that the models can be verified. In this paper we focus on executable UML and on the issues related to concurrent state machines. We show that one integrated formal methods approach, CSP || B, has the potential to be tailored to support reasoning about concurrent state machines and in turn expose any weaknesses in the UML model. We identify future avenues of research so that a system methodology based on executable UML can be enhanced by formal reasoning.

This paper develops a case study using the process algebra CSP to enable controlled interaction between B machines. This illustrates how B machines are essential components within a combined communicating system. The development steps used to build the case study are new: they are applications of theoretical results which allow us to focus on the external interface of a combined communicating system, compositionally verify it, and show that it is a refinement of a more abstract specification described in CSP. This allows safety and liveness properties to be established for combinations of communicating B machines.

This paper describes a way of using the process algebra CSP to enable controlled interaction between B machines. This approach supports compositional verification: each of the controlled machines, and the combination of controller processes, can be analysed and verified separately in such a way as to guarantee correctness of the combined communicating system. Reasoning about controlled machines separately is possible due to the introduction of guards and assertions into description of the controller processes in order to capture assumptions about other controlled machines and provide guarantees to the rest of the system. The verification process can be completely supported by difierent tools. The use of separate controller processes facilitates the iterative development and analysis of complex control flows within the system. The approach is motivated and illustrated with a non-trivial running example.

Event-B has emerged as one of the dominant state-based formal techniques used for modelling control-intensive applications. Due to the blocking semantics of events, their ordering is controlled by their guards. In this paper we explore how process algebra descriptions can be defined alongside an Event-B model. We will use CSP to provide explicit control flow for an Event-B model and alternatively to provide a way of separating out requirements which are dependent on control flow information. We propose and verify new conditions on combined specifications which establish deadlock freedom. We discuss how combined specifications can be refined and the challenges arising from this. The paper uses Abrial’s Bridge example as the basis of a running example to illustrate the framework.

The safety analysis of interlocking railway systems involves verifying collision and derailment freedom. In this paper we propose a structured way of refining track plans, in order to expand track segments so that they form collections of track segments. We show how the abstract model can be model checked to ensure the safety properties, which must also hold in the corresponding concrete track plan, so that we will never need to model check the concrete track plan directly. We also identify the minimal number of trains that needs to be considered as part of the model checking, and we demonstrate the practicality of the approach on various scenarios. © 2013 Springer-Verlag Berlin Heidelberg.

In this paper we present a new way of reconciling Event-B refinement with linear temporal logic (LTL) properties. In particular, the results presented in this paper allow properties to be established for abstract system models, and identify conditions to ensure that the properties (suitably translated) continue to hold as those models are developed through refinement. There are several novel elements to this achievement: (1) we identify conditions that allow LTL properties to be mapped across refinement chains; (2) we provide translations of LTL predicates to reflect the introduction through refinement of new events and the renaming and splitting of existing events; (3) we do this for an extended version of LTL particularly suited to Event-B, including state predicates and enabledness of events, which can be model-checked at the abstract level. Our results are more general than any previous work in this area, covering liveness in the context of anticipated events, and relaxing constraints between adjacent refinement levels. The approach is illustrated with a case study. This enables designers to develop event based models and to consider their execution patterns so that liveness and fairness properties can be verified for Event-B systems.

The introduction of probabilistic behaviour into the B-Method is a recent development. In addition to allowing probabilistic behaviour to be modelled, the relationship between expected values of the machine state can be expressed and verified. This paper explores the application of probabilistic B to a simple case study: tracking the volume of liquid held in a tank by measuring the flow of liquid into it. The flow can change as time progresses, and sensors are used to measure the flow with some degree of accuracy and reliability, modelled as non-deterministic and probabilistic behaviour respectively. At the specification level, the analysis is concerned with the expectation clause in the probabilistic B machine and its consistency with machine operations. At the refinement level, refinement and equivalence laws on probabilistic GSL are used to establish that a particular design of sensors delivers the required level of reliability.

Users accessing services are often required to provide personal information, for example, age, profession and location, in order to satisfy access polices. This personal information is evident in the application of e-ticketing where discounted access is granted to visitor attractions or transport services if users satisfy policies related to their age or disability or other defined over attributes. We propose a privacy-preserving electronic ticket scheme using attribute-based credentials to protect users’ privacy. The benefit of our scheme is that the attributes of a user are certified by a trusted third party so that the scheme can provide assurances to a seller that a user’s attributes are valid. The scheme makes the following contributions: (1) users can buy different tickets from ticket sellers without releasing their exact attributes; (2) two tickets of the same user cannot be linked; (3) a ticket cannot be transferred to another user; (4) a ticket cannot be double spent. The novelty of our scheme is to enable users to convince ticket sellers that their attributes satisfy the ticket policies and buy discounted tickets anonymously. This is a step towards identifying an e-ticketing scheme that captures user privacy requirements in transport services. The security of our scheme is proved and reduced to a well-known complexity assumption. The scheme is also implemented and its performance is empirically evaluated.

We present a symbolic reachability analysis approach for B that can provide a significant speedup over traditional explicit state model checking. The symbolic analysis is implemented by linking ProB to LTSmin, a high-performance language independent model checker. The link is achieved via LTSmin's PINS interface, allowing ProB to benefit from LTSmin's analysis algorithms, while only writing a few hundred lines of glue-code, along with a bridge between ProB and C using ZeroMQ. ProB supports model checking of several formal specification languages such as B, Event-B, Z and TLA. Our experiments are based on a wide variety of B-Method and Event-B models to demonstrate the efficiency of the new link. Among the tested categories are state space generation and deadlock detection; but action detection and invariant checking are also feasible in principle. In many cases we observe speedups of several orders of magnitude. We also compare the results with other approaches for improving model checking, such as partial order reduction or symmetry reduction. We thus provide a new scalable, symbolic analysis algorithm for the B-Method and Event-B, along with a platform to integrate other model checking improvements via LTSmin in the future.

The introduction of probabilistic behaviour into the B-method is a recent development. In addition to allowing probabilistic behaviour to be modelled, the relationship between expected values of the machine state can be expressed and verified. This paper explores the application of probabilistic B to a simple case study: tracking the volume of liquid held in a tank by measuring the flow of liquid into it. The flow can change as time progresses, and sensors are used to measure the flow with some degree of accuracy and reliability, modelled as non-deterministic and probabilistic behaviour respectively. At the specification level, the analysis is concerned with the EXPECTATION clause in the probabilistic B machine and its consistency with machine operations. At the refinement level, refinement and equivalence laws on probabilistic GSL are used to establish that a particular design of sensors delivers the required level of reliability.

The safety analysis of interlocking railway systems involves verifying freedom from collision, derailment and run-through (that is, trains rolling over wrongly-set points). Typically, various unrealistic assumptions are made when modelling trains within networks in order to facilitate their analyses. In particular, trains are invariably assumed to be shorter than track segments; and generally only a very few trains are allowed to be introduced into the network under consideration. In this paper we propose modelling methodologies which elegantly dismiss these assumptions. We first provide a framework for modelling arbitrarily many trains of arbitrary length in a network; and then we demonstrate that it is enough with our modelling approach to consider only two trains when verifying safety conditions. That is, if a safety violation appears in the original model with any number of trains of any and varying lengths, then a violation will be exposed in the simpler model with only two trains. Importantly, our modelling framework has been developed alongside - and in conjunction with - railway engineers. It is vital that they can validate the models and verification conditions, and - in the case of design errors - obtain comprehensible feedback. We demonstrate our modelling and abstraction techniques on two simple interlocking systems proposed by our industrial partner. As our formalization is, by design, near to their way of thinking, they are comfortable with it and trust it.

An anonymous single sign-on (ASSO) scheme allows users to access multiple services anonymously using one credential. We propose a new ASSO scheme, where users can access services anonymously through the use of anonymous credentials and unlinkably through the provision of designated verifiers. Notably, verifiers cannot link a user’s service requests even if they collude. The novelty is that when a designated verifier is unavailable, a central authority can authorize new verifiers to authenticate the user on behalf of the original verifier. Furthermore, a central verifier can also be authorized to de-anonymize users and trace their service requests. We formalize the scheme along with a security proof and provide an empirical evaluation of its performance. This scheme can be applied to smart ticketing where minimizing the collection of personal information of users is increasingly important to transport organizations due to privacy regulations such as general data protection regulations (GDPRs).

The introduction of probabilistic behaviour into the B-Method is a recent development. In addition to allowing probabilistic behaviour to be modelled, the relationship between expected values of the machine state can be expressed and verified. This paper explores the application of probabilistic B to a simple casestudy: tracking the volume of liquid held in atank by measuring the flow of liquid into it. The flow can change as time progresses, and sensors are used to measure the flow with some degree of accuracy and reliability, modelled as non-deterministic and probabilistic behaviour respectively. At the specification level, the analysis is concerned with the expectation clause in the probabilistic B machine and its consistency with machine operations. At the refinement level, refinement and equivalence laws on probabilistic GSL are used to establish that a particular design of sensors delivers the required level of reliability.

This volume contains the revised version of a selection of papers presented at the B 2011 Workshop, a satellite event of the 17th International Symposium on Formal Methods (FM 2011). It took place in Limerick, Ireland, on 21st June, 2011.

We describe a novel framework for modelling railway interlockings which has been developed in conjunction with railway engineers. The modelling language used is CSP(Formula presented.)B. Beyond the modelling we present a variety of abstraction techniques which make the analysis of medium- to large-scale networks feasible. The paper notably introduces a covering technique that allows railway scheme plans to be decomposed into a set of smaller scheme plans. The finitisation and topological abstraction techniques are extended from previous work and are given formal foundations. All three techniques are applicable to other modelling frameworks besides CSP(Formula presented.)B. Being able to apply abstractions and simplifications on the domain model before performing model checking is the key strength of our approach. We demonstrate the use of the framework on a real-life, medium-size scheme plan.

Research on vehicular networking (V2X) security has produced a range of security mechanisms and protocols tailored for this domain, addressing both security and privacy. Typically, the security analysis of these proposals has largely been informal. However, formal analysis can be used to expose flaws and ultimately provide a higher level of assurance in the protocols. This paper focusses on the formal analysis of a particular element of security mechanisms for V2X found in many proposals, that is the revocation of malicious or misbehaving vehicles from the V2X system by invalidating their credentials. This revocation needs to be performed in an unlinkable way for vehicle privacy even in the context of vehicles regularly changing their pseudonyms. The Rewire scheme by Förster et al. and its subschemes Plain and R-token aim to solve this challenge by means of cryptographic solutions and trusted hardware. Formal analysis using the Tamarin prover identifies two flaws: one previously reported in the literature concerned with functional correctness of the protocol, and one previously unknown flaw concerning an authentication property of the R-token scheme. In response to these flaws we propose Obscure Token (O-token), an extension of Rewire to enable revocation in a privacy preserving manner. Our approach addresses the functional and authentication properties by introducing an additional key-pair, which offers a stronger and verifiable guarantee of successful revocation of vehicles without resolving the long-term identity. Moreover O-token is the first V2X revocation protocol to be co-designed with a formal model.

Event-B provides a flexible framework for stepwise system development via refinement. The framework supports steps for (a) refining events (one-by-one), (b) splitting events (one-by-many), and (c) introducing new events. In each of the steps events can be indicated as convergent (to be made internal) or anticipated (treatment deferred to a later refinement step). All such steps are accompanied with precise proof obligations. However, no behavioural semantics has been provided to validate the proof obligations, and no formal justification has previously been given for the application of these rules in a refinement chain. Behavioural semantics expresses a clear relationship between the first and last machines in a refinement chain. The framework we present provides a coherent justification for Abrial’s approach to refinement in Event-B, and its generalisation to interface extension: adding events to the interface. In this paper, we give a behavioural semantics for Event-B refinement, with a treatment for the first time of splitting events and of anticipated events, adding to the well-understood treatment of convergent events. To this end, we define a CSP semantics for Event-B and show how the different forms of Event-B refinement can be captured as CSP refinement. It turns out that the appropriate CSP refinement relationship is influenced by the particular Event-B development strategy taken. We present two such strategies, one allowing, the other disallowing interface extensions.

This paper is concerned with event refinement in the context of CSP‖B. Our motivation to include this notion within the CSP‖B framework is the desire to increase flexibility in the refinement process. This approach provides the ability to change the events of CSP processes and B machines when refining a system. Notions of refinement based on traces and on traces/divergences allow abstract events to be refined by sequences of concrete events. A complementary notion of refinement between B machines is also proposed, yielding compositionality results for refinement of CSP‖B controlled components. The paper also introduces a notion of I/O refinement into our event refinement framework.

CSP parallel to B is a formal approach which combines state and event-based descriptions of a system. It enables the automatic verification of dynamic properties using model checking techniques. In this paper we identify a variation on the standard CSP parallel to B architecture so that it is more applicable to support the specification of information systems. We specify a library system using this new architecture. We examine several safety and liveness requirements and demonstrate that we can compositionally verify them using FDR. If a property fails to model check we identify an abstraction technique which enables us to pinpoint the cause of the failure.

Recent work on combining CSP and B has provided ways of describing systems comprised of components described in both B (to express requirements on state) and CSP (to express interactive and controller behaviour). This approach is driven by the desire to exploit existing tool support for both CSP and B, and by the need for compositional proof techniques. This paper is concerned with the theory underpinning the approach, and proves a number of results for the development and verification of systems described using a combination of CSP and B. In particular, new results are obtained for the use of the hiding operator, which is essential for abstraction. The paper provides theorems which enable results obtained (possibly with tools) on the CSP part of the description to be lifted to the combination. Also, a better understanding of the interaction between CSP controllers and B machines in terms of non-discriminating and open behaviour on channels is introduced, and applied to the deadlock-freedom theorem. The results are illustrated with a toy lift controller running example.

The safety analysis of interlocking railway systems involves verifying freedom from collision, derailment and run-through (that is, trains rolling over wrongly-set points). Typically, various unrealistic assumptions are made in order to facilitate their analyses. In particular, trains are invariably assumed to be shorter than track segments; and generally only a very few trains are allowed to be introduced into the network under consideration. In this paper we propose modelling methodologies which elegantly dismiss these assumptions. We first provide a framework for modelling arbitrarily many trains of arbitrary length in a network; and then we demonstrate that it is enough with our modelling approach to consider only two trains when verifying safety conditions. That is, if a safety violation appears in the original model with any number of trains of any and varying lengths, then a violation will be exposed in the simpler model with only two trains. Importantly, our modelling framework has been developed alongside – and in conjunction with – railway engineers. It is vital that they can validate the models and verification conditions, and – in the case of design errors – obtain comprehensible feedback. We demonstrate our modelling and abstraction techniques on two simple interlocking systems proposed by our industrial partner. As our formalization is, by design, near to their way of thinking, they are comfortable with it and trust it

Event-B provides a flexible framework for stepwise system development via re finement. The framework supports steps for (a) re fining events (one-by-one), (b) splitting events (one-by-many), and (c) introducing new events. In each of the steps events can be indicated as convergent (to be made internal) or anticipated (treatment deferred to a later refi nement step). All such steps are accompanied with precise proof obligations. However, no behavioural semantics has been provided to validate the proof obligations, and no formal justifi cation has previously been given for the application of these rules in a re finement chain. Behavioural semantics expresses a clear relationship between the first and last machines in a re finement chain. The framework we present provides a coherent justi fication for Abrial's approach to re finement in Event-B, and its generalisation to interface extension: adding events to the interface. In this paper, we give a behavioural semantics for Event-B refi nement, with a treatment for the first time of splitting events and of anticipated events, adding to the well-understood treatment of convergent events. To this end, we de fine a CSP semantics for Event-B and show how the di fferent forms of Event-B refi nement can be captured as CSP re finement. It turns out that the appropriate CSP refi nement relationship is influenced by the particular Event-B development strategy taken. We present two such strategies, one allowing, the other disallowing interface extensions.

Refinement in Event-B supports the development of systems via proof based step-wise refinement of events. This refinement approach ensures safety properties are preserved, but additional reasoning is required in order to establish liveness and fairness properties. In this paper we present results which allow a closer integration of two formal methods, Event-B and linear temporal logic. In particular we show how a class of temporal logic properties can carry through a refinement chain of machines. Refinement steps can include introduction of new events, event renaming and event splitting. We also identify a general liveness property that holds for the events of the initial system of a refinement chain. The approach will aid developers in enabling them to verify linear temporal logic properties at early stages of a development, knowing they will be preserved at later stages. We illustrate the results via a simple case study.

Direct Anonymous Attestation (DAA) is a cryptographic scheme that provides Trusted Platform Module (TPM)- backed anonymous credentials. We develop TAMARIN modelling of the ECC-based version of the protocol as it is standardised and provide the first mechanised analysis of this standard. Our analysis confirms that the scheme is secure when all TPMs are assumed honest, but reveals a break in the protocol’s expected authentication and secrecy properties for all TPMs even if only one is compromised. We propose and formally verify a minimal fix to the standard. In addition to developing the first formal analysis of ECC-DAA, the paper contributes to the growing body of work demonstrating the use of formal tools in supporting standardisation processes for cryptographic protocols.

Event-B!CSP is a combination of Event-B and CSP in which CSP controllers are used in conjunction with Event-B machines to allow a more explicit approach to control flow. Recent results have provided an approach to stepwise refinement of such combinations. This paper presents a simplified Bounded Retransmission Protocol case study, inspired by Abrial’s treatment of this example, to illustrate several aspects new in the approach. The case study includes refinement steps to illustrate four different aspects of this approach to refinement: (1) splitting events; (2) introducing convergent looping behaviour; (3) the relationship between anticipated, convergent, and devolved events; and (4) converging anticipated events.

This technical report provides the CSP semantic basis for stepwise refinement in Event-B!CSP. It provides the foundation for combining Event- B machines with CSP control processes in the context of refinement. A number of proof rules are presented which are sufficient to establish refinement of an Event-B!CSP combination. This report focuses on traces, both finite and infinite, which allows consideration of safety specifications and also consideration of divergence-freedom. Several refinement steps in Event-B!CSP in the development of a simple bounded retransmission protocol are presented to illustrate the approach.

Pret a Voter and Punchscan are two electronic voting schemes that both use paper based ballot forms, part of which is detached and destroyed, to provide receipt-free voter verifiability. However, both schemes share the chain voting problem and the part destruction problem. The first is where anyone who can see the ballot form before it is used can coerce a voter who uses it and the latter where a voter who can leave with the complete form can prove to a coercer the contents of the vote. In this paper we provide a comparison of the schemes from a systems perspective. We also introduce a visual encryption solution to both the above problems.

This paper is concerned with the formal modelling of sig- nalling and point control in the domain of railway engineering. Rules for handling interlocking to ensure railway safety and liveness are often intricate and challenging to verify. We develop a CSP||B model taking a “natural modelling” approach, where the models are as close as possible to the domain model, providing traceability and ease of understanding to the domain expert. This leads to a natural separation between the global modelling of the tracks in B, and the CSP encapsulation of the local views of the individual trains following the driving rules. The ap- proach is illustrated through a small case study (Mini-Alvey), and the model provides verification through formal proofs or informative counter example traces if verification fails.

This paper proposes a texture analysis of the printed document based on Local Binary Pattern (LBP) descriptor for the application of printer identification. The LBP provides a statistical description of the pixels’ gray level differences within their neighborhoods. The occurrence histogram of local binary patterns is able to capture the document’s texture modifications by the distortion during the printing-and-scanning process, such as halftoning, geometric distortion, and mechanical defects. The most frequently appeared local binary patterns represent bright or dark flat regions. Furthermore, Gou et al. proposed an approach based on the combination of three different types of statistical features for scanner identification.We deconstruct their approach in order to evaluate the effectiveness of each type of features for printer identification. Our proposed LBP descriptor based model provides an excellent identification rate at approximately 99.4%, with a low variance. These results were achieved by Support Vector Machine (SVM) classification via n-fold cross validation and leave one out. They exceed any of the results obtained using the features, employed by the Gou et al. approach either singularly or in combination. Our experiments were conducted on 350 printed images, as well as 350 printed text documents, by a set of similar printers, two of which were exactly identical. The proposed model remains robust against common image processing, including averaging filtering, median filtering, sharpening, rotation, resizing, and JPEG compression.