An ever-increasing number of critical infrastructures rely heavily on the assumption that security protocols satisfy a wealth of requirements. Hence, the importance of certifying e.g., privacy properties using methods that are better at detecting attacks can hardly be overstated. This paper scrutinises the “unlinkability” privacy property using relations equating behaviours that cannot be distinguished by attackers. Starting from the observation that some reasonable design choice can lead to formalisms missing attacks, we draw attention to a classical concurrent semantics accounting for relationship between past events, and show that there are concurrency-aware semantics that can discover attacks on all protocols we consider. More precisely, we focus on protocols where trace equivalence is known to miss attacks that are observable using branching-time equivalences. We consider the impact of three dimensions: design decisions made by the programmer specifying an unlinkability problem (style), semantics respecting choices during execution (branching-time), and semantics sensitive to concurrency (non-interleaving), and discover that reasonable styles miss attacks unless we give attackers enough power to observe choices and concurrency. Our main contribution is to draw attention to how a popular concurrent semantics – history-preserving bisimilarity – when defined for the non-interleaving applied π -calculus, can discover attacks on all protocols we consider, regardless of the choice of style. Furthermore, we can describe all such attacks using a novel modal logic that is hence suitable to formally certify attacks on privacy properties. This study highlights the threats posed by relying exclusively on tools implementing coarser semantics for protocol verification, and justifies in a very precise sense why security practitioners should account for history between past events to build reliable tools.

We prove a Kleene theorem for higher-dimensional automata. It states that the languages they recognise are precisely the rational subsumption-closed sets of finite interval pomsets. The rational operations on these languages include a gluing composition, for which we equip pomsets with interfaces. For our proof, we introduce higher-dimensional automata with interfaces, which are modelled as presheaves over labelled precube categories, and develop tools and techniques inspired by algebraic topology, such as cylinders and (co)fibrations. Higher-dimensional automata form a general model of non-interleaving concurrency, which subsumes many other approaches. Interval orders are used as models for concurrent and distributed systems where events extend in time. Our tools and techniques may therefore yield templates for Kleene theorems in various models and applications.

The eXtensible Access Control Markup Language (XACML) is a popular OASIS standard for the specification of fine-grained access control policies. However, the standard does not provide a proper solution for the verification of XACML access control policies before their deployment. The first step for the formal verification of XACML policies is to formally specify such policies. Hence, this paper presents XACML2mCRL2, a tool for the automatic translation of XACML access control policies into mCRL2. The mCRL2 specifications generated by our tool can be used for formal verification of important properties of access control policies such as completeness of inconsistency, using the well-known mCRL2 toolset.

We prove a Kleene theorem for higher-dimensional automata (HDAs). It states that the languages they recognise are precisely the rational subsumption-closed sets of interval pomsets. The rational operations include a gluing composition, for which we equip pomsets with interfaces. For our proof, we introduce HDAs with interfaces as presheaves over labelled precube categories and use tools inspired by algebraic topology, such as cylinders and (co)fibrations. HDAs are a general model of non-interleaving concurrency, which subsumes many other models in this field. Interval orders are used as models for concurrent or distributed systems where events extend in time. Our tools and techniques may therefore yield templates for Kleene theorems in various models and applications.

Purpose This paper aims to present arguments about how a complex concept of privacy labeling can be a solution to the current state of privacy. Design/methodology/approach The authors give a precise definition of Privacy Labeling (PL), painting a panoptic portrait from seven different perspectives: Business, Legal, Regulatory, Usability and Human Factors, Educative, Technological and Multidisciplinary. They describe a common vision, proposing several important “traits of character” of PL as well as identifying “undeveloped potentialities”, i.e. open problems on which the community can focus. Findings This position paper identifies the stakeholders of the PL and their needs with regard to privacy, describing how PL should be and look like to address these needs. Main aspects considered are the PL’s educational power to change people’s knowledge of privacy, tools useful for constructing PL and the possible visual appearances of PL. They also identify how the present landscape of privacy certifications could be improved by PL. Originality/value The authors adopt a multidisciplinary approach to defining PL as well as give guidelines in the form of goals, characteristics, open problems, starting points and a roadmap for creating the ideal PL.

Abstract Schematic drawings showing railway tracks and equipment are commonly used to visualize railway operations and to communicate system specifications and construction blueprints. Recent advances in on-line collaboration and modeling tools have raised the expectations for quickly making changes to models, resulting in frequent changes to layouts, text, and/or symbols in schematic drawings. Automating the creation of high-quality schematic views from geographical and topological models can help engineers produce and update drawings efficiently. This paper introduces four methods for automatically producing schematic railway drawings with increasing level of quality and control over the result. The final method, implemented in the open-source tool that we have developed, can use any combination of the following optimization criteria, which can have different priorities in different use cases: width and height of the drawing, the diagonal line lengths, and the number of bends. We show how to encode schematic railway drawings as an optimization problem over Boolean and numerical domains, using combinations of unary number encoding, lazy difference constraints, and numerical optimization into an incremental SAT formulation. We compare drawings resulting from each of the four methods, applied to models of real-world engineering projects and existing railway infrastructure. We also show how to add symbols and labels to the track plan, which is important for the usefulness of the final outputs. Since the proposed tool is customizable and efficiently produces high-quality drawings from railML 2.x models, it can be used (as it is or extended) both as an integrated module in an industrial design tool like RailCOMPLETE, or by researchers for visualization purposes.

Abstract This paper proposes a new method of combining SAT with discrete event simulation. This new integration proved useful for designing a solver for capacity analysis in early phase railway construction design. Railway capacity is complex to define and analyze, and existing tools and methods used in practice require comprehensive models of the railway network and its timetables. Design engineers working within the limited scope of construction projects report that only ad-hoc, experience-based methods of capacity analysis are available to them. Designs often have subtle capacity pitfalls which are discovered too late, only when network-wide timetables are made—there is a mismatch between the scope of construction projects and the scope of capacity analysis, as currently practiced. We suggest a language for capacity specifications suited for construction projects, expressing properties such as running time, train frequency, overtaking and crossing. Such specifications can be used as contracts in the interface between construction projects and network-wide capacity analysis. We show how these properties can be verified fully automatically by building a special-purpose solver which splits the problem into two: an abstracted SAT-based dispatch planning, and a continuous-domain dynamics with timing constraints evaluated using discrete event simulation. The two components communicate in a CEGAR loop (counterexample-guided abstraction refinement). This architecture is beneficial because it clearly distinguishes the combinatorial choices on the one hand from continuous calculations on the other, so that the simulation can be extended by relevant details as needed. We describe how loops in the infrastructure can be handled to eliminate repeating dispatch plans, and use case studies based on data from existing infrastructure and ongoing construction projects to show that our method is fast enough at relevant scales to provide agile verification in a design setting. Similar SAT modulo discrete event simulation combinations could also be useful elsewhere where one or both of these methods are already applicable such as in bioinformatics or hardware/software verification.

Abstract We introduce languages of higher-dimensional automata (HDAs) and develop some of their properties. To this end, we define a new category of precubical sets, uniquely naturally isomorphic to the standard one, and introduce a notion of event consistency. HDAs are then finite, labeled, event-consistent precubical sets with distinguished subsets of initial and accepting cells. Their languages are sets of interval orders closed under subsumption; as a major technical step, we expose a bijection between interval orders and a subclass of HDAs. We show that any finite subsumption-closed set of interval orders is the language of an HDA, that languages of HDAs are closed under binary unions and parallel composition, and that bisimilarity implies language equivalence.

In recent years, it has come to attention that governments have been doing mass surveillance of personal communications without the consent of the citizens. As a consequence of these revelations, developers have begun releasing new protocols for end-to-end encrypted conversations, extending and making popular the old Off-the-Record protocol. New implementations of such end-to-end encrypted messaging protocols have appeared, and several popular chat applications have been updated to use such protocols. In this survey, we compare six existing applications for end-to-end encrypted instant messaging, namely, Signal, WhatsApp, Wire, Viber, Riot, and Telegram, most of them implementing one of the recent and popular protocols called Signal. We conduct five types of experiments on each of the six applications using the same hardware setup. During these experiments, we test 21 security and usability properties specially relevant for applications (not protocols). The results of our experiments demonstrate that the applications vary in terms of the usability and security properties they provide, and none of them are perfect. In consequence, we make 12 recommendations for improvement of either security, privacy, or usability, suitable for one or more of the tested applications.

We introduce Dynamic Structural Operational Semantics (DSOS or Dynamic SOS) as a framework for describing semantics of programming languages that include dynamic software upgrades, i.e., for upgrading software code during run-time. DSOS is built on top of the Modular SOS of P. Mosses, with an underlying category theory formalization. The idea of Dynamic SOS is to bring out the essential differences between dynamic upgrade constructs and program execution constructs. The important feature of Modular SOS (MSOS) that we exploit in DSOS is the sharp separation of the program execution code from the additional (data) structures needed at run-time. In DSOS we aim to achieve the same modularity and decoupling for dynamic software upgrades. This is partly motivated by the long term goal of having machine-checkable proofs for general results like type safety. We exemplify Dynamic SOS on two languages supporting dynamic software upgrades, namely the C-like Proteus, which supports updating of variables, functions, records, or types at specific program points, and Creol, which supports dynamic class upgrades in the setting of concurrent objects. Existing type analyses for software upgrades can be done on top of DSOS too, as we illustrate for Proteus. As a side contribution we define a general encapsulating construction on Modular SOS useful in situations where a form of encapsulation of the execution is needed. We use encapsulation to give modular semantics to the concurrent object-oriented programming language Creol with active objects and asynchronous method invocations.

Railway capacity is complex to define and analyze, and existing tools and methods used in practice require comprehensive models of the railway network and its timetables. Design engineers working within the limited scope of construction projects report that only ad-hoc, experience-based methods of capacity analysis are available to them. Designs have subtle capacity pitfalls which are discovered too late, only when network-wide timetables are made - there is a mismatch between the scope of construction projects and the scope of capacity analysis, as currently practiced.We suggest a language for capacity specifications suited for construction projects, expressing properties such as running time, train frequency, overtaking and crossing. Verifying these properties amounts to solving a planning problem constrained by discrete control system logic, network topology, laws of motion, and sparse communication. To describe train dynamics one uses second-order linear differential equations which when solved analytically give rise to non-linear equations over real variables.We argue that reasoning over the whole discrete/continuous solution space is not efficient with current state-of-the-art solvers. Instead, we have solved the problem by building a special-purpose solver which splits the problem into two: an abstracted SAT-based dispatch planning, and continuous-domain dynamics and timing constraints evaluated using discrete event simulation. The two components communicate in a CEGAR-loop (counterexample-guided abstraction refinement). We show that our method is fast enough at relevant scales to provide agile verification in a design setting, and we present case studies based on data from existing infrastructure and ongoing construction projects.

In designing safety-critical infrastructures s.a. railway systems, engineers often have to deal with complex and large-scale designs. Formal methods can play an important role in helping automate various tasks. For railway designs formal methods have mainly been used to verify the safety of so-called interlockings through model checking, which deals with state change and rather complex properties, usually incurring considerable computational burden (e.g., the state-space explosion problem). In contrast, we focus on static infrastructure models, and are interested in checking requirements coming from design guidelines and regulations, as usually given by railway authorities or safety certification bodies. Our goal is to automate the tedious manual work that railway engineers do when ensuring compliance with regulations, through using software that is fast enough to do verification on-the-fly, thus being able to be included in the railway design tools, much like a compiler in an IDE. In consequence, this paper describes the integration into the railway design process of formal methods for automatically extracting railway models from the CAD railway designs and for describing relevant technical regulations and expert knowledge as properties to be checked on the models. We employ a variant of Datalog and use the standardized “railway markup language” railML as basis and exchange format for the formalization. We developed a prototype tool and integrated it in industrial railway CAD software, developed under the name RailCOMPLETE®. This on-the-fly verification tool is a help for the engineer while doing the designs, and is not a replacement to other more heavy-weight software like for doing interlocking verification or capacity analysis. Our tool, through the export into railML, can be easily integrated with these other tools. We apply our tool chain in a Norwegian railway project, the upgrade of the Arna railway station.

Identity and authentication solutions often lack usability and scalability, or do not provide high enough authentication assurance. The concept of Lucidman (Local User-Centric Identity Management) is an approach to providing scalable, secure and user friendly identity and authentication functionalities. In this context we demonstrate the use of an OffPAD (Offline Personal Authentication Device) as a trusted device to support different forms of authentication. The Lucidman/OffPAD approach consists of locating the identity management and authentication functionalities on the user side instead of on the server side or in the cloud. This demo aims to show how OffPAD strengthens authentication assurance, improves usability, minimizes trust requirements, and has the advantage that trusted online interaction can be achieved even on malware infected client platforms. The trusted device OffPAD has been designed as a phone cover, therefore not requiring the user to carry an extra gadget. We focus on six demonstrators, three useful in e-banking and three in the hospital domain where nurses, doctors, or patients are authenticated and access is granted in various situations base on the OffPAD. A video with the same title is available online at www.offpad.org.

The development of resource-constrained embedded systems that are naturally state-driven is still a challenging issue, especially in industrial applications -- developed on a bare-bone style runtime system with basic programming features. This is because of the complexity of state-driven design in embedded applications, such as parallel and complicated event-based activity flows, and complicated constraints for transitioning between program states. State machines are considered a systematic approach for such needs. However, existing approaches, in this area, either do not satisfactorily address the above complexity aspects, or force the developer to write code intermingling state handling logic with the functional code. To tackle these issues, we propose TOKEN IT, a state machine-based development framework for resource-constrained embedded systems. Using TOKEN IT, the programmer models the application as a set of parallel processes, where each process consists of sequenced activities with state constraints such as delayed transitions or interdependency between the states of parallel processes. TOKEN IT, then, processes the obtained model and associates a token to each sequential flow of activities, synthesizing them and executing state transitions according to the constraints expressed in the TOKEN IT model. The evaluation results show that TOKEN IT reduces significantly the complexity of state-driven programming in embedded systems at an acceptable memory cost and with no extra processing overhead.

The paper presents an action-based formal language called CL for abstract specification of legal contracts. The purpose of the language is to be used to reason about legal contracts (and electronic contracts on the long run). CL combines the legal notions obligation, permission, and prohibition from deontic logic with the action modality of propositional dynamic logic (PDL). The deontic modalities are applied only over actions, thus following the ought-to-do approach. The language includes a synchrony operator to model "actions performed at the same time", and a special complementation operation to encode the violation of obligations. The language has a formal semantics in terms of normative structures, specially defined to capture several natural properties of legal contracts. We focus on the informal presentation of the choices made when designing CL, and its semantics.