Lorenzo Carnevale
email: lcarnevale@unime.it

Antonio Celesti
email: acelesti@unime.it

Maria Fazio
email: mfazio@unime.it

Placido Bramanti
email: pbramanti@irccsme.it

Massimo Villari
email: mvillari@unime.it

Heart Disorder Detection with Menard Algorithm on Apache Spark

Keywords: Big Data, healthcare, cardiology, Heart, ECG, arrhythmia

Nowadays, healthcare is facing Big Data processing in order to support medical staff by means of decision making tools. In this context, a challenging topic is the storing and analysis of data in the cardiology field. Electrocardiogram produces signals about the heart health that need to be processed in order to detect a possible disorder. In this paper, we discuss an Apache Spark based tool and that uses the Menard algorithm. In order to validate our solution, we performed experiments on a use case in which the algorithm has been implemented in order to detect heart disorder. Experiments prove the goodness of our approach in terms of performance.

Introduction

Currently, the healthcare industry is looking at the adoption of Big Data due to the volume, velocity and variety properties of health data. Big Data solutions have been adopted so far in different healthcare fields including biotechnology [START_REF] Celesti | Are next-generation sequencing tools ready for the cloud?[END_REF], clinical analysis [START_REF] Celesti | An oais-based hospital information system on the cloud: Analysis of a nosql column-oriented approach[END_REF], and so on. Therefore, a careful study of clinical data performed by means of decision making tools helps doctors to make diagnosis.

In this regard, hospital facilities are relying on external providers or internal staff to manage and analyze clinical data. Apache Spark is a licensed framework designed to support distributed applications for creating batch applications, interactive queries and stream processing. Spark adopts the MapReduce software framework, created by Google to support distributed data computing on cluster.

In this scientific work, we used Apache Spark in order to analyze electrocardiogram (ECG) signals. Specifically, goal of our analysis was to detect heart disorder. To this end, we planned to use the Menard algorithm.

The rest of the paper is organized as follows. Related work are summarized in Section 1.2. An overview about heart physiognomy and functionality and ECG is presented in Section 1.3 and 1.4, whereas a Menard algorithm description and its Spark implementation for hearbeat peaks detection are presented in Section 1.5. Experiments and evaluation results are presented in Section 1.6. In the end, conclusion and lights to the future are summarized in Section 1.7.

Related Work

The scientific community has proposed several scientific works on heart disorder analysis in order to improve the accuracy, prevent diseases and reduce mortality. In the following, we report some of these works.

Many scientific works combine ECG signal analysis with the most famous Big Data framework: Apache Hadoop. A tele-ECG system has been proposed in [START_REF] Ma'sum | Enhanced tele ECG system using hadoop framework to deal with big data processing[END_REF]. The authors aimed to process Big Data in order to detect and monitor heart diseases. They proposed a cluster which takes advantage of Apache Spark framework. Specifically, this system classifies data using decision tree and random forest.

An analysis of arrhythmias has ben proposed in [START_REF] Wang | P wave detection and delineation based on distances transform[END_REF], in which the authors proposed an automatic detection of P-wave in an ECG. More specifically, they worked a improved method based on local distance transform, such as horizontal segments and rising or declining segment. As result, they proved the simplicity and efficiency of the algorithms for transplanting to wearable medical devices whose processing ability is weak.

In order to facilitate the data migration from medical devices to Cloud storage, we mention the work proposed in [START_REF] Carnevale | How to enable clinical workflows to integrate big healthcare data[END_REF]. The authors described the first step of an architecture able to manage the Big Data Acquisition and Integration workflow for storing health data coming from several medical instrumentations. This scientific work has proved the goodness of the method used in terms of time performance.

A Cardiovascular Disease (CVD) detection algorithm was proposed in [START_REF] Alshraideh | A web based cardiovascular disease detection system[END_REF]. The algorithm uses patient demographic data as input, along with several ECG signal features automatically extracted through signal processing techniques. The algorithm has been integrated into a web based system that can be used at anytime by patients to check their heart health status. Signals are sent from the ECG sensor attached on the patient's body to the detection algorithm via an Android device. Cross-validation results showed the 98.29% accuracy.

We aim to enrich the scientific literature by proposing a work that uses the Menard algorithm to perform the distributed calculation of an ECG signal through the Apache Spark framework, in order to detect the most common heart diseases.

The Heart. How does it work?

The heart is passively filled with blood that comes from veins and actively pushes blood through the body. A complete contraction and relaxation sequence represents the heart cycle, which normally is repeated about 75 times per minute. The figure 1.1 shows this cycle.

Specifically, in the first phase (diastole) the heart is completely relaxed and blood flows into its four cavities because of the atriovascular valves opening. The second phase (systole) begins with a short limbs contraction that completely fills ventricles with blood. Afterwards, the ventricles will contract for about 0.3 seconds. The force of their contraction closes the atrioventricular valves, opens the semilunar valves and pumps blood into the large arteries. During the last phase, blood flows into the atrioventriculars.

Heart Medical Instrumentation: the ECG

The electrocardiogram (ECG) is an instrumental diagnostic test that graphically records the rhythm and electrical activity of the heart. This allows the cardiologist to detect health disorder such as the presence of heart arrhythmias, ischemia, myocardial infarction or outcomes of a previous heart attack.

Indeed, heart pathological phenomena creates abnormal conditions in the muscle fibrocells, generating a different pattern from the standard. However, a standard pattern does not represent a proper heart condition, and vice versa, healthy people can have abnormal ECG outcomes. In these conditions, medical opinion is always mandatory.

The ECG test produces positive and negative waves, according to the signal position compared to the baseline, called isoelectric. Each wave is the graphic representation of an electric phenomenon that occurred in the heart. In particular, we can distinguish five signal period as reported in the figure 1.2. For our purpose, here we specify the QRS complex as the stimulus propagation to the ventricular muscle.

Application Design

Over the years, many algorithms have been developed for recognizing the QRS complex, which can be classified according to their complexity and performance. Specif- ically, most efficient and complex algorithms are based on appropriate techniques for filtering and processing ECG signals, whereas less complex algorithms are based on statistical thresholds. In the following, we are going to focus on a specific algorithm based on ECG signal derivation: the Menard algorithm [START_REF] Menrad | Dual microprocessor system for cardiovascular data acquisition, processing and recording[END_REF]. This is calculated using the following equation:

Y (n) = -2X(n -2) -X(n -1) + X(n + 1) + 2X(n + 2) (1.1)
Afterwards, a ζ threshold of 70% of the maximum Y (n) value is chosen:

ζ = 0.7 * max[Y (n)] (1.2)
Finally, the algorithm adopts the following decision rule to detect the QRS complex:

Y (i) > ζ ⇒ QRS (1.3)
In this scientific work, the Menard algorithm has been used for calculating the QRS complex thorugh the utilization of Apache Spark. The dataset used for the following experiments comes from the Physionet.org European ST-T Database. It includes a signal acquired by a digitizer with sampling rate equal to f s = 250Hz. In order to process it, the file must be properly formatted. For this purpose, two preliminary steps were needed.

Primarily, having to act on multiple samples at the same time, we needed to organize an appropriate set of samples on one file line because Apache Spark treates each of them as a strings RDD. Moreover, Spark distributes workload in tasks, which involves multiple lines processement of the RDD. Neverthess, the Menard algorithm implementation performs the derivation through the formula 1.1, which shows how a continuous set of data is needed. Indeed, in order to determine the nth element of the derivative, we needed to know the two previous and subsequent elements of the nth ECG signal. Thus, we overlap content introducing row by row redundancy (except the last one). This avoids the information losing during the cluster distribution phase. Moreover, during the source file formatting process, each line is indexed for tracking the reference samples.

However, how many samples should form an RDD element? How many values should be placed on a row of the file? Let's consider that an electrocardiogram typically oscillates between -20mv and 20mv, the calculation of the Menard algorithm threshold may not take into account these variations using a signal large portion. Therefore, it may not correctly detect heartbeat peaks. The proposed solution was to implement a version of the algorithm with an adaptive threshold, which is calculated differently for each sample block.

Thus, our implementation uses a set of samples with a duration equal to 10 seconds. To this end, if we indicate with f s the sampling frequency of the ECG signal, all the file lines (except the last one) have n = ( f s * 10) + 4, where 4 is due to the abovementioned overlap.

The only information required for calculating the QRS complex is represented by the detected peak index because, multiplying it by the sampling frequency reciprocal, it is useful to trace the beat time. Moreover, we had to determine which peak signals above the threshold may be considered a heartbeat. Indeed, these values are more than one around a QRS complex. In order to simplify it, we chose the first value above the threshold. The figure 1.2 shows the peak signals of an ECG derivative. In order to distribute the RDD to the cluster's nodes and create a elements list on the driver, it is necessary to use the collect() method. It is the first action performed by the application. Indeed, until now, we have only talked about transformations. Therefore, the saveAsTextFile() method examines all the peaks' RDD trasformations in order to save it on a file.

What if the threshold values of a ECG signal section were between two blocks (or between two nodes)? Both the first index above the threshold of the first block and the first index above the threshold of the second block would be selected as peaks. The proposed solution requires that application knows the values found, and recognizes the extremely close peaks.

Experiments

The testbed for performing our experiments was configured into a three nodes (1 master, 2 slaves) docker distributed environment with the following hardware specifications: Quad-Core and RAM 8 GB. Each node was configured with Ubuntu 14.04, OpenJDK 7, Spark 1.6.1 and Scala 2.11.8. Moreover, the Apache Spark framework used its scheduling process, without relying on third party cluster manager, such as YARN. Specifically, using a 5GB input file, Spark distributes the workload in 157 tasks among cluster's nodes.

The test included a hour ECG signal with sampling rate equal to 360Hz. With reference to section 1.5, actions carried out by the Spark application are collect and saveAs-TextFile. In this regard, we show the collect tests outcomes in the figure 1.4. The temporal outcomes are quite similar, as highlighted by the small confidence interval. The collect average time value is about 23 seconds. Now consider the case of the saveAsTextFile action, shown in the figure 1.5. Again, the input size increasing causes a nonlinear increasing of the action execution time. Specifically, the average execution time is about 5.6 seconds. In this specific context, the collect benefits more from parallelization than saveAsTextFile. The analyses carried out are related to a specific ECG signal. Clearly, each ECG differs from others in terms of peaks and abnormalities, therefore these outcomes are not considered indicative for generic ECG signal.

Conclusion and Future Work

This scientific work has addressed the problem of the ECG signals distributed processing. Specifically, the algorithm implemented for the determination of heartbeats and arrhythmias required a preprocessing phase. Each Big Data framework bases its computing philosophy on task independence, wherefore this context is not in the ideal conditions for exploiting distributed processing. To this end, a local files preprocessing must be made. Thus, large files could represent the bottleneck of the entire application.

On the other hand, the performance offered by this computing paradigm is definitely important. As a conseguence, solved the problem of local preprocessing of the ECG signals, the application would only get benefits from processing on a cluster. For this purpose, an idea might be to use an ad hoc device for recording the electrocardiogram. Specifically, if we suppose to make a device that during the recording of the ECG signal introduces the overlapping required for the algorithm, any limitation due to the nature of the data itself would be eliminated.

From the algorithm point of view, the ECG signal analysis was performed based on the heart rhythm obtained by calculating the R-R intervals. Indeed, more complex operations could be implemented by making elaborations based on the shape of the waves that make up a heartbeat. Thus, exploiting the compute parallelization, it would be possible to implement computationally highly costly algorithms by obtaining relevant performance by processing on a cluster.

Finally, Spark Streaming could be used to perform continuous and Real Time processing. In this regard, an ad-hoc device for sending electrocardiogram sections should be implemented, allowing continuous monitoring of the patient's health status.

Fig. 1 . 1 .

 11 Fig. 1.1. The heart cycle [The Mammalian Heart & Cardiac Cycle]

Fig. 1 . 2 .

 12 Fig. 1.2. ECG outcomes [hyperphysics.phy-astr.gsu.edu]

Fig. 1 . 3 .

 13 Fig. 1.3. ECG derivative and threshold

Fig. 1 . 4 .

 14 Fig. 1.4. collect action for 5 GB file. 20 proofs average and confidence interval equal to 95%

Fig. 1 . 5 .

 15 Fig. 1.5. saveAsTextFile action for 5 GB file. 20 proofs average and confidence interval equal to 95%

ACKNOWLEDGMENT

This work has been supported by Cloud for Europe (C4E) Tender: REALIZATION OF A RESEARCH AND DEVELOPMENT PROJECT (PRE-COMMERCIAL PROCURE-MENT) ON "CLOUD FOR EUROPE", Italy-Rome: Research and development services and related consultancy services Contract notice: 2014/S 241-424518. Directive: 2004/18/EC. (http://www.cloudforeurope.eu/). Authors would like to thank Fabio Pandolfo for his valuable technical support in this scientific work.


Max Plauth

Lena Feinbube

Andreas Polze

A Performance Survey of Lightweight Virtualization Techniques

The increasing prevalence of the microservice paradigm creates a new demand for low-overhead virtualization techniques. Complementing containerization, unikernels are emerging as alternative approaches. With both techniques undergoing rapid improvements, the current landscape of lightweight virtualization approaches presents a confusing scenery, complicating the task of choosing a suited technology for an intended purpose. This work provides a comprehensive performance comparison covering containers, unikernels, whole-system virtualization, native hardware, and combinations thereof. Representing common workloads in microservice-based applications, we assess application performance using HTTP servers and a key-value store. With the microservice deployment paradigm in mind, we evaluate further characteristics such as startup time, image size, network latency, and memory footprint.

Introduction

With the increasing pervasiveness of the cloud computing paradigm for all sorts of applications, low-overhead virtualization techniques are becoming indispensable. In particular, the microservice architectural paradigm, where small encapsulated services are developed, operated and maintained by separate teams, require easy-to-use and disposable machine images. Ideally, such infrastructure should allow for fast provisioning and efficient operation.

Approaches to lightweight virtualization roughly fall into the categories of container virtualization and unikernels. Both have been gaining notable momentum recently (see [START_REF] Felter | An updated performance comparison of virtual machines and Linux containers[END_REF][START_REF] Madhavapeddy | Unikernels: The Rise of the Virtual Library Operating System[END_REF] and Fig. 1). As more and more virtualization techniques are being introduced and discussed, making a choice between them is getting harder. Published performance measurements thus far either have a strong focus on throughput and execution time [START_REF] Beserra | Performance Analysis of LXC for HPC Environments[END_REF][START_REF] Di Tommaso | The impact of Docker containers on the performance of genomic pipelines[END_REF][START_REF] Regola | Recommendations for Virtualization Technologies in High Performance Computing[END_REF][START_REF] Xavier | Performance Evaluation of Container-Based Virtualization for High Performance Computing Environments[END_REF] -not analyzing startup latency and other system metrics in depth -or focus on highlighting the strengths of one particular approach without comparing it to a broad range of alternative unikernels and container technologies [3,[START_REF] Di Tommaso | The impact of Docker containers on the performance of genomic pipelines[END_REF][START_REF] Felter | An updated performance comparison of virtual machines and Linux containers[END_REF][START_REF] Kivity | OSv-Optimizing the Operating System for Virtual Machines[END_REF][START_REF] Madhavapeddy | Jitsu: Just-In-Time Summoning of Unikernels[END_REF][START_REF] Regola | Recommendations for Virtualization Technologies in High Performance Computing[END_REF].

We close this gap by presenting an extensive performance analysis of lightweight virtualization strategies, which takes into account a broad spectrum both of investigated technologies and measured metrics. Our evaluation includes Fig. 1. The relevance of Docker and unikernels in the research community is indicated by the number of results on Google Scholar (as of May 15, 2017). containers (Docker, LXD), unikernels (Rumprun, OSv and MirageOS ), wholesystem virtualization, native hardware, and certain combinations thereof. While previous work has laid a strong focus on high performance computing (HPC) applications (see Section 3), our goal is to evaluate metrics that are applicable to cloud applications. For this purpose, we measure application throughput performance using HTTP servers and a key-value store. Additionally, we provide further metrics, such as startup time, image size, network latency, and memory footprint. To facilitate full repeatability of our results, all test setups used throughout this paper have been made available online 1 .

The remainder of the paper is organized as follows: Section 2 provides background about the employed virtualization approaches. Section 3 reviews related work that deals with quantifying the performance impact of lightweight virtualization approaches. Afterwards, Section 4 refines the scope of this work. Section 5 then documents the benchmark procedure yielding the results presented in Section 6. Finally, Section 7 concludes this work with final remarks.

Background

"Traditional", whole-system virtualization introduces performance and memory overhead, incurred by the hypervisor or virtual machine manager (VMM). This problem has been addressed by introducing paravirtualization (PV) and hardware-assisted virtualization (HVM). Still, the additional layer of indirection necessitates further context switches, which hurt I/O performance. [START_REF] Felter | An updated performance comparison of virtual machines and Linux containers[END_REF] Even though techniques such as kernel samepage merging (KSM) [START_REF] Arcangeli | Increasing memory density by using KSM[END_REF] have managed to reduce memory demands, they do not provide an ultimate remedy as they dilute the level of isolation among virtual machines [START_REF] Irazoqui | Wait a minute! A fast, Cross-VM attack on AES[END_REF].

This work focuses on lightweight virtualization approaches, which, addressing both issues, have gained notable momentum both in the research community and in industry. Fig. 2 illustrates how these approaches aim at supporting the deployment of applications or operating system images while eluding the overhead incurred by running a full-blown operating system on top of a hypervisor. With containers and unikernels constituting the two major families of lightweight virtualization approaches, the main characteristics and two representatives of each family are introduced hereafter.

Container (OS-Level Virtualization)

Containers are based on the observation that the entire kernel induces overly much resource overhead for merely isolating and packaging small applications.

Here, we distinguish two classes of container virtualization approaches: application and OS-oriented containers. For application-oriented containers, single applications constitute the units of deployment. For OS-oriented containers, the entire user space of the operating system is reproduced. Currently, with LXD, the latter approach is becoming more prominent again, as it allows for the creation of virtual machine (VM)-like behavior without the overhead of a hypervisor. In the following paragraphs, we discuss the the containerization technologies under investigation Docker Among the application-oriented containers, the open source project Docker [START_REF] Inc | Docker[END_REF] currently is the most popular approach. It relies on Linux kernel features, such as namespaces and control groups, to isolate independent containers running on the same instance of the operating system. A Docker container encapsulates an application as well as its software dependencies; it can be run on different Linux machines with the Docker engine.

Apart from providing basic isolation and closer-to-native performance than whole-system virtualization, Docker containerization has the advantages that pre-built Docker containers can be shared easily, and that the technology can be integrated into various popular Infrastructure as a Service (IaaS) solutions such as Amazon web services (AWS).

LXD The Linux-based container solution LXD [START_REF]LXD[END_REF] builds up upon the LXC (Linux container) [4] interface to Linux containerization features. LXD uses the LXC library for providing low-overhead operating system containers. In addition to advanced container creation and management features, LXD offers integration into the OpenStack Nova compute component [START_REF]The OpenStack project: Nova[END_REF].

Unikernel (Hypervisor Virtualization)

Unikernels are a new take on the library operating system concept, providing merely a thin layer of protection and multiplexing facilities for hardware resources whereas hardware support is left to employed libraries and the application itself. Whereas library operating systems (e.g., Exokernel [START_REF] Engler | Exokernel: An Operating System Architecture for Application-level Resource Management[END_REF]) had to struggle with having to support real hardware, unikernels avoid this burden by targeting only virtual hardware interfaces provided by hypervisors or VMMs [START_REF] Madhavapeddy | Unikernels: Library operating systems for the cloud[END_REF]. With the absence of many abstraction mechanisms present in traditional operating systems, the unikernel community claims to achieve a higher degree of wholesystem optimization while reducing startup times and the VM footprint [START_REF] Madhavapeddy | Jitsu: Just-In-Time Summoning of Unikernels[END_REF][START_REF] Madhavapeddy | Unikernels: The Rise of the Virtual Library Operating System[END_REF].

Rumprun The Rumprun unikernel is based on the rump kernel project, which is a strongly modularized version of the NetBSD kernel that was built to demonstrate the anykernel concept [START_REF] Kantee | Flexible Operating System Internals: The Design and Implementation of the Anykernel and Rump Kernels[END_REF]. With the goal of simplified driver development in mind, the anykernel concept boils down to enabling a combination of monolithic kernels, where drivers are executed in the kernel, and microkernel-oriented user space drivers that can be executed on top of a rump kernel. One of the major features of the Rumprun unikernel is that it supports running existing and unmodified POSIX software [START_REF] Kantee | The Rise and Fall of the Operating System[END_REF], as long as it does not require calls to fork() or exec().

OSv The OSv unikernel has been designed specifically to replace generalpurpose operating systems such as Linux in cloud-based VMs. Similarly to Rumprun, OSv supports running existing and unmodified POSIX software, as long as certain limitations are considered [START_REF] Kivity | OSv-Optimizing the Operating System for Virtual Machines[END_REF]. However, OSv provides additional APIs for exploiting capabilities of the underlying hypervisor, such as a zero copy API intended to replace the socket API to provide more efficient means of communication among OSv -based VMs.

MirageOS Being developed from scratch, the MirageOS unikernel resembles a puristic, clean-slated approach. MirageOS builds up on top of the Mini-OS kernel from the Xen project and only supports software written in the OCaml programming language [START_REF] Madhavapeddy | Unikernels: The Rise of the Virtual Library Operating System[END_REF]. Denying any compatibility with existing POSIXcompatible software, the static type system and the strong runtime safety capabilities of OCaml lead to a high level of software robustness [START_REF] Madhavapeddy | Unikernels: Library operating systems for the cloud[END_REF].

An overview of publications about performance measurements of lightweight virtualization techniques from the last few years are presented in Table 1. Previous research has measured selected performance properties of lightweight virtualization techniques, mostly in comparison with a traditional whole-system virtualization approach. However, we are not aware of any comprehensive analysis of up-to-date container versus unikernel technologies.

Felter et al. [START_REF] Felter | An updated performance comparison of virtual machines and Linux containers[END_REF] have presented a comprehensive performance comparison between Docker containers and the KVM hypervisor [START_REF]KVM project[END_REF]. Their results from various compute-intensive as well as I/O-intensive programs indicate that "Docker equals or exceeds KVM performance in every case tested". For I/O-intensive workloads, both technologies introduce significant overhead, while the CPU and memory performance is hardly affected. Mao et al. [22] have studied the startup time of virtual machines for the major cloud providers Amazon EC2, Windows Azure, and Rackspace. Among different influencing factors, the image size was shown to have a significant impact on the startup performance. Kivity et al. [START_REF] Kivity | OSv-Optimizing the Operating System for Virtual Machines[END_REF] focus on the performance of OSv in comparison to whole-system virtualization with KVM. Both micro-and macro-benchmarks indicate that OSv offers better throughput, especially for memory-intensive workloads. Here, we present an extensive performance evaluation of containers (Docker, LXD), unikernels (Rumprun, OSv and MirageOS ), and whole-system virtualization. Related work has focused on subsets of the approaches we consider, but we are not aware of any comprehensive analysis of up-to-date container versus unikernel technologies. This paper extends our work published in [START_REF] Plauth | A Performance Evaluation of Lightweight Approaches to Virtualization[END_REF], providing commensurable network stack parameters for all tested approaches and measurements for additional properties such as startup time, image size, and network latency. Furthermore, Xen and MirageOS have been included as additional hypervisor and unikernel approaches. Startup time is a relevant metric in scenarios, where the infrastructure is booted on demand to process certain requests. Requirements regarding the infrastructure and runtime environment are getting more ad hoc, may change spontaneously, and call for rapid just-in-time deployment and reactive approaches. Such scenarios are becoming more common with the microservice development pattern.

Our research questions are the following:

-How fast are containers, unikernels, and whole-system virtualization when running different workloads? Are the results from related work confirmed in our test cases? -What is the most suitable virtualization technology for on-demand provisioning scenarios? -What is the impact of the virtualization technology on general system properties such as image size, network latency and memory footprint?

Benchmark Procedure

This section provides a description of the benchmark methodologies applied within this work. All tests were performed on an HPE ProLiant m710p server cartridge [START_REF]HPE ProLiant m710p Server Cartridge QuickSpecs[END_REF] with the detailed specifications denoted in Table 2. Where applicable, all approaches were evaluated using Xen, KVM and native hardware to evaluate the performance impact of the employed virtualization approach. For container-based approaches, we also distinguish between native and virtualized hosts, where the latter represent the common practice for deploying containers on top of IaaS-based virtual machines. All configuration files, custom benchmarking utilities as well as modifications to existing utilities are provided online 1 .

General Properties

Startup Time To avoid potential confounding variables, startup time is measured irrespectively from the application type. Referring to the test procedure suggested by Nickoloff [START_REF] Nickoloff | Evaluating Container Platforms at Scale[END_REF], our test set-up is composed of a minimal application which sends a UDP packet containing a single character to a predefined host Image Size In practice, image size strongly influences startup time [22], as images have to be transported over potentially slow networks. Hence, the eventual image sizes are reported for all examined technologies. To avoid skewed readouts caused by sparse image files, the actual disk utilization is retrieved using the du command line utility.

Network Latency Since network latency may be a decisive factor in latencysensitive use cases such as network function virtualization (NFV) [START_REF] Martins | ClickOS and the Art of Network Function Virtualization[END_REF], the network round-trip time is measured between a dedicated host and the test object using the ping command line utility.

Memory Footprint Reducing the memory footprint is one of the main objectives of lightweight virtualization approaches. For native and LXD-based execution, memory consumption was measured using the htop command line utility.

In the case of Docker, the docker ps command line facility was used to retrieve memory consumption measurements. As the memory footprint of VMs and unikernels is defined statically at the time of their instantiation, VM-sizing must be chosen carefully. Hence, we identified the least amount of memory that did not degrade performance by testing different values in steps of 8 MiB.

Application Performance

Representing common workloads of cloud-hosted applications, we picked HTTP servers and key-value stores as exemplary applications. As these I/O-intensive use cases involve a large number of both concurrent clients and requests, the network stack considerably contributes to the overall application performance. Hence, in order to eliminate an unfavorable default configuration of the network stack as a confounding variable, we modified the configuration on Linux, Rumprun and OSv. Since many best practices guides cover the subject of tuning network performance on Linux, we employed the recommendations from [START_REF] Veal | Performance Scalability of a Multi-Core Web Server[END_REF], resulting in the configuration denoted in Table 3. Based on this model, we modified the configuration parameters of both Rumprun and OSv to correspond to the Linux-based settings [START_REF] Schwarzer | Evaluierung von Unikernel-Betriebssystemen für Cloud-Computing[END_REF]. The resulting configuration for Rumprun is specified in Table 4, and the corresponding configuration for OSv is documented in Table 5. Currently, there is no mechanism in Rumprun to permanently modify the values of the ulimit parameter. As a workaround, the Rumprun sysproxy facility has be activated by passing the parameter -e RUMPRUN SYSPROXY=tcp://0:12345 to the rumprun command-line utility upon start. Using the rumpctrl utility, the configuration values of the ulimit parameter have to be changed remotely, as exemplified in Listing 1.1.

1 export RUMP_SERVER=tcp://[IP]:12345 2 . rumpctrl.sh 3 sysctl -w proc.0.rlimit.descriptors.soft=200000 4 sysctl -w proc.0.rlimit.descriptors.hard=200000 5 sysctl -w proc.1.rlimit.descriptors.soft=200000 6 sysctl -w proc.1.rlimit.descriptors.hard=200000 7 sysctl -w proc.2.rlimit.descriptors.hard=200000 8 sysctl -w proc.2.rlimit.descriptors.soft=200000 9 rumpctrl_unload

Listing 1.1. The ulimit values of Rumprun have to be changed remotely using the sysproxy facility and the associated rumpctrl utility. Static HTTP Server We use the Nginx HTTP server (version 1.8.0) to evaluate the HTTP performance for static content, as it is available on all tested platforms with the exception of OSv and MirageOS. As no port of Nginx exists for MirageOS, we had to trade in the aspect of full commensurability with Nginx and use the conduit server code example [START_REF] Mirageos | Conduit Server Code Example[END_REF] in order not to exclude MirageOS from the HTTP server discipline. Regarding OSv however, we refrain from running HTTP benchmarks due to the lacking availability of an adequate HTTP server implementation.

Our measurement procedure employs the benchmarking tool weighttp [START_REF]lighty labs: weighttp[END_REF] and the abc wrapper utility [START_REF] Apachebench | [END_REF] for automated benchmark runs and varying connection count parameters. The abc utility has been slightly modified to report standard deviation values in addition to average throughput values for repeated measurements. The benchmark utility is executed on a dedicated host to avoid unsolicited interactions between the HTTP server and the benchmark utility. As static content, we use our institute website's favicon2 . We measured the HTTP performance ranging from 0 to 1000 concurrent connections, with range steps of 100 and TCP keepalive being enabled throughout all measurements.

Key-Value Store In our second application benchmark discipline, we use Redis (version 3.0.1) as a key-value store. Except for MirageOS, Redis is available on all tested platforms. In order to rule out disk performance as a potential bottleneck, we disabled any persistence mechanisms in the configuration files and operate Redis in a cache-only mode of operation. For executing performance benchmarks, we use the redis-benchmark utility, which is included in the Redis distribution. The benchmark utility is executed on a separate host to represent real-world client-server conditions more accurately and to avoid unsolicited interactions between the benchmark utility and the Redis server. We measured the performance of GET and SET operations ranging from 0 to 1000 concurrent connections, with range steps of 100 and both TCP keepalive and pipelining being enabled throughout all measurements. The CSV-formatted output of redisbenchmark was aggregated to yield average values and standard deviation using a simple python script.

Results & Discussion

Here, we provide and discuss the results obtained from the benchmark procedure elaborated in Section 5. All values are expressed as mean ± SD (n = 30).

General Properties

Startup Time The measurements presented in Fig. 3a illustrate that both unikernels and containers can achieve much faster startup times compared to whole-system virtualization using Ubuntu Linux. The distinct differences between LXD and Docker demonstrate, that a large portion of the startup time of a Linux system is not caused by the kernel itself, but that it can be traced back to the services launched upon startup. Image Size The results presented in Fig. 3b indicate that container approaches undercut the image size of whole-system virtualization roughly by an order of magnitude, whereas unikernels reduce image sizes by one (Rumprun and OSv ) or two (MirageOS ) additional orders of magnitudes compared to containers. The substantial reduction of image sizes can lead to a considerable advantage in IaaS scenarios, where image size often correlates with instantiation time [22].

Ubuntu Mirage Rumprun

Network Latency The measurements presented in Fig. 3c indicate similar response times for Rumprun, OSv, and the container-based approaches. However, the choice of the hypervisor strongly affects the round-trip time performance. Even though para-virtualized network devices were used for both Xen and KVM, the latter yields much faster round-trip times for all tested guest systems.

Application Performance

For a statistically meaningful evaluation, an ANOVA and a post-hoc comparison using the Tukey method were applied. For the hypervisor-based approaches using both Xen and KVM, the choice of the hypervisor had no statistically significant effect on application performance. Hence, only the results for KVM are plotted to avoid visual clutter.

Static HTTP Server

The ANOVA test revealed a significant impact of the lightweight virtualization technique on the HTTP server performance (p < 0.0001, F (9, 2970) = 3921). Containers introduce a significant amount of overhead compared to native execution (p < 0.0001), both in native (see Fig. 4a) and virtualized environments (see Fig. 4b). A likely cause for this overhead is that all traffic has to go through a NAT in common configurations for both container-based approaches.

On the side of unikernels, MirageOS is running out of competition, as the employed conduit server can not be compared with a heavily optimized HTTPserver such as Nginx. For Rumprun however, it is surprising to see a similar performance compared to containers. Only for 600 concurrent clients and more, slight but statistically significant performance improvements can be observed for Rumprun compared to containers (p < 0.0001). With HTTP-servers heavily relying on the performance of the operating systems network stack, it can be assumed that the Linux networking stack has undergone massive optimization efforts that the NetBSD network stack can hardly compete with. To verify this hypothesis, we performed the same HTTP benchmark procedure using NetBSD 7.0.1 in a virtual machine. Here, Rumprun performed distinctly better than NetBSD (data not shown), which indicates the potential of the unikernel-concept. With further optimizations of the network stack, Rumprun might achieve similar or even better performance than a regular Linux-based virtual machine.

In terms of memory footprint, unikernels manage to undercut the demands of a full-blown Linux instance (see Fig. 5a). However, containers still can get by with the least amount of memory. The major advantage of containers remains the possibility of dynamic memory allocation, whereas virtual machines are restricted to predefining the amount of allocated memory at the time of instantiation. Still, MirageOS demonstrates that a puristic approach can yield distinctly reduced memory footprints, even though sophisticated porting efforts are necessary.

Key-Value Store

The ANOVA test revealed a significant performance impact of the lightweight virtualization technique (p < 0.0001, F (7, 7920) = 4099). As illustrated in Fig. 6, the key-value store exhibits similar results regarding container-based approaches and whole-system virtualization: Regardless of native or virtualized deployments, containers come with a significant amount of overhead (p < 0.0001). In contrast, Rumprun and OSv offer slight but nevertheless significant performance improvements compared to Linux under many conditions. Regarding memory consumption (see 5b), containers still offer the highest degree of flexibility. While Rumprun still undercuts the memory footprint of Linux, OSv required distinctly more memory in order to withstand the benchmark.

Conclusion

Performance evaluations of lightweight virtualization techniques thus far have mostly dealt with application performance and neglected relevant system properties such as startup latency, image size, network latency and memory footprint. Furthermore, many of these studies focused on highlighting the strengths of one particular approach without comparing it to a broad range of alternative technologies. To take remedial action, we present an extensive performance evaluation of containers, unikernels, and whole-system virtualization, focusing on metrics that are applicable to cloud applications.

Regarding application throughput, most unikernels performed at least equally well as or even better than containers. We also demonstrated that containers are not spared from overhead regarding network performance, which is why virtual machines or unikernels may be preferable in cases where raw throughput matters. Even though Docker can achieve the shortest startup times considering the raw numbers, unikernels are competitive due to tiny image sizes and much shorter startup times than full virtual machines, especially in cases where the image has to be transferred to the compute host first. These are just some aspects demonstrating that, while containers have already reached a sound level of maturity, unikernels are on the verge of becoming a viable alternative. Even though we did not see unikernels outperforming a virtualized Linux instance, our brief comparison between NetBSD and Rumprun also suggested that unikernels have the potential of outperforming their full-grown operating system relatives.

Fig. 3 .

 3 Fig. 3. A logarithmic scale is used to accommodate a wide range of values. (a) Startup time in seconds as measured using the procedure documented in [25]. (b) Image size in MiB as reported by the du utility. (c) Round-trip time in milliseconds as measured from a dedicated host.

Fig. 4 .

 4 Fig. 4. Throughput of Nginx (1.8.0) was evaluated on native hardware (a) and in virtualized environments (b). For MirageOS, the conduit server was used. Throughput was measured using weightttp and the modified abc wrapper utility.

Fig. 5 .Fig. 6 .

 56 Fig. 5. The memory footprints of the static HTTP server scenario (a) and the Key-Value Store scenario (b) were measured for each virtualization technique.

Table 1 .

 1 Related work on performance measurements of lightweight virtualization approaches. Studies printed in gray indicate a HPC context.

	Docker	LXC	Open	VZ	Rump-	run	OSv	Mirage	OS	KVM	Xen	others
	Metrics	Container					Unikernel			Virtualization

Table 2 .

 2 Specifications of the test systems. a counterpart application listening for said UDP packet. The listening application is executed on the virtualization host and issues the startup command for the corresponding container or unikernel VM and measures the time until the UDP packet is received.

	Server model	HPE ProLiant m710p Server Cartridge
	Processor	Intel Xeon E3-1284L v4 (Broadwell)
	Memory	4 × 8GB PC3L-12800 (SODIMM)
	NIC	Mellanox Connect-X3 Pro (Dual 10GbE)
	Operating system	Ubuntu Linux 16.04.1 LTS

and

Table 3 .

 3 Optimized settings for the Linux network stack.

	Path	Parameter	Value
	/etc/sysctl.conf	fs.file-max	20000
	/etc/sysctl.conf	net.core.somaxconn	1024
	/etc/sysctl.conf	net.ipv4.ip local port range	1024 65535
	/etc/sysctl.conf	net.ipv4.tcp tw reuse	1
	/etc/sysctl.conf	net.ipv4.tcp keepalive time	60
	/etc/sysctl.conf	net.ipv4.tcp keepalive intvl	60
	/etc/security/limits.conf	nofile (soft/hard)	20000

Table 4 .

 4 Optimized settings for the Rumprun network stack.

	Path	Parameter	Value
	./sys/conf/param.c	MAXFILES	20000
	./sys/netinet/in.h	IPPORT ANONMIN	1024
	./sys/netinet/in.h	IPPORT ANONMAX	65535
	./sys/netinet/tcp timer.h	TCPTV KEEP INIT	30*PR SLOWHZ
	./sys/netinet/tcp timer.h	TCPTV KEEPINTV	30*PR SLOWHZ
	./sys/sys/socket.h	SOMAXCONN	1024

Table 5 .

 5 Optimized settings for the OSv network stack.

	Path	Parameter	Value
	./include/osv/file.h	FDMAX	0x30D40
	./libc/libc.cc	RLIMIT NOFILE	20000
	./bsd/sys/netinet/in.h	IPPORT EPHEMERALFIRST	1024
	./bsd/sys/netinet/in.h	IPPORT EPHEMERALLAST	65535
	./bsd/sys/netinet/in.h	IPPORT HIFIRSTAUTO	1024
	./bsd/sys/netinet/in.h	IPPORT HILASTAUTO	65535
	./bsd/sys/netinet/tcp timer.h	TCPTV KEEP INIT	60*hz
	./bsd/sys/netinet/tcp timer.h	TCPTV KEEPINTV	60*hz
	./bsd/sys/sys/socket.h	SOMAXCONN	1024
	./include/api/sys/socket.h	SOMAXCONN	1024

https://github.com/plauth/lightweight-vm-performance

http://hpi.de/favicon.ico

Acknowledgment

We would like to thank Vincent Schwarzer for engaging our interest in unikernels in the course of his master's thesis [28]. Furthermore, we thank the HPI Future SOC Lab for granting us access to the hardware resources used in this paper.

This paper has received funding from the European Union's Horizon 2020 research and innovation program 2014-2018 under grant agreement No. 644866.

Disclaimer

This paper reflects only the authors' views and the European Commission is not responsible for any use that may be made of the information it contains.


Jacob Eberhardt

Stefan Tai

On or Off the Blockchain? Insights on Off-Chaining Computation and Data

The potential for blockchains to fundamentally transform how organizations produce and capture value is huge and very real. Practical applications dealing with nearly any type of digital asset demonstrate this capacity. Blockchain-based application architectures benefit from a set of unique properties including immutability and transparency of cryptographically-secured and peer-recorded transactions, which have been agreed upon by network consensus. Blockchain-based applications, however, may also suffer from high computational and storage expenses, negatively impacting overall performance and scalability. In this paper, we report on lessons learned and insights gained from a set of experimental blockchain projects, focusing on off-chaining: How to move computation and data off-the-chain, without compromising the properties introduced and benefits gained by using blockchains in the first place.

Introduction

Blockchains are a combination of different computing and economics concepts, predominantly including peer-to-peer networks, asymmetric cryptography, consensus protocols, decentralized storage, decentralized computing and smart contracts, and incentive mechanisms. The synthesis of these concepts positions blockchains as a new technology and as a programmable platform and network at the same time. Blockchains introduce unique properties including immutability and transparency of cryptographically-secured and peer-recorded transactions, which have been agreed upon by network consensus. As such, the potential associated with blockchain to fundamentally transform how organizations produce and capture value is huge -and very real. While initially discussed especially in the financial services sector, there are practical applications today dealing with nearly any type of digital asset, ranging from asset provenance to peer-to-peer commerce. Establishing trustless interactions and business disintermediation remain major objectives when using blockchains.

Over the past two years, we have conducted a set of blockchain projects at the Information Systems Engineering research group at TU Berlin, mostly experimental projects that focus on a particular application challenge and which have been carried out in collaboration with industry partners. Further, we are conducting foundational research on blockchain technology and platforms, taking a distributed systems and data management perspective. In both settings, the question of on-chaining versus off-chaining is recurring: What exactly has to be on the chain and what can be off the chain, while retaining the overall properties and benefits associated with blockchains?

On-chain data -in the form of confirmed transactions organized in ordered blocks -and on-chain code -in the form of programs written in a generalpurpose, Turing-complete language -require validation and consensus by network peers and result in append-only changes to the blockchain as a shared datastore that cannot be reversed. Transaction validation, consensus protocols, and decentralized program execution may, however, describe a communication and execution overhead. And they simply do take time. In addition, miners (that is, nodes that validate transactions and propose new blocks) typically charge fees, thereby incurring financial costs. Overall, scalability of the blockchainbased system may suffer. Bitcoin currently has a limit of 7 transactions per second; Ethereum has a limit of about 15 transactions per second. Furthermore, anything on the (public) blockchain is not inherently anonymous, but on the contrary purposely visible; privacy and confidentiality are not guaranteed for on-chain transactions.

The objective for off-chaining data and computation is to reduce or to overcome such limitations. By moving data and computation elsewhere off the blockchain, for example, to another datastore, server, or third party, the blockchain "footprint" obviously is reduced. However, the fundamental properties of blockchains and blockchain-based applications, may be compromised to different degrees when doing so. They may even be potentially prohibitively violated when using naive off-chaining approaches. After all, the system should remain "trustless" in the sense that no explicit trust is required.

In this paper, we report on first insights gained on off-chaining computation and data. We present five off-chaining patterns and discuss the context, principle idea, and implementation for each.

Blockchains and Smart Contracts

In a nutshell, blockchains are distributed peer-to-peer systems which implement a trustless shared public append-only transaction ledger [START_REF] Tai | Not ACID, not BASE, but SALT -a transaction processing perspective on blockchains[END_REF].

Blockchains. Bitcoin, the first implementation of such a system, was proposed in 2008 by Satoshi Nakamoto [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF]. The goal which led to the creation of the Bitcoin protocol was the design of a digital currency which allows the transfer of digital value fully peer-to-peer without relying on a trusted intermediary. To implement such a decentralized cryptocurrency, the system combines transactions secured by asymmetric cryptography with a consensus algorithm to decide on the transaction order within the network. Peers in the network can validate individual transactions by checking cryptographic signatures. In addition to that, however, a global order of the transactions has to be decided on to prevent double spending of digital funds. For that, as a main innovation of the Bitcoin system, the proof-of-work consensus protocol was developed which allocates the right to add transactions to the network in proportion to the computational effort spent to secure the network. For efficiency, multiple transactions are grouped into a block. These blocks are then ordered by consensus. Each block references its predecessor, which implies a chain data structure -the blockchain.

Extending Bitcoins idea of peer-to-peer value transfer, Ethereum, a trustless computing platform, was proposed in 2014 [START_REF] Buterin | Ethereum: A next-generation smart contract and decentralized application platform[END_REF][START_REF] Wood | Ethereum: A secure decentralised generalised transaction ledger[END_REF]. Ethereum adds a turing complete and stateful programming language to the blockchain idea, which enables the execution of complex code without trusting a server or central party. Trust is replaced by validating each program execution on every peer in the network and agreeing on an outcome. Smart Contracts. These programs executed in a trustless and tamper-proof manner in the network are referred to as Smart Contracts. Note, that Smart Contracts need to be deterministic as otherwise peers could disagree on the results of valid executions. Hence, e.g., filesystem and network access are not permitted. While the term may imply a close connection to legal contracts, smart contracts have a much wider range of use cases and can be applied where automatically executed complex conditional logic is required. Hence, they can be imagined as self executing autonomous agents.

2. As computations come with a fee, the end game check should be performed as rarely as possible. Hence, like in a physical chess game, we should have a player trigger the check instead of doing it after every valid move. In other words, we should move part of the control flow to the client side. 3. We have to expect to reach scalability limits of blockchains when creating applications. This emphasizes the need for research in and development of off-chaining techniques.

Another much more complex proof-of-concept was a decentralized service marketplace which enables trustless disintermediation between providers and consumers of service APIs. Using a cryptocurrency for payments, a consumer can buy time-constrained access to a service offered on the market place without involving a marketplace intermediary. Especially service discovery, one of the main building blocks of a service marketplace, posed a big challenge within the fully decentralized design: Data storage on blockchains is extremely expensive due to full replication in the peer-to-peer network. Nonetheless, a meaningful service discovery feature requires API descriptions to be stored. Simply pointing to an off-chain reference from a smart contract, e.g., a file hosted in a cloud storage system, is no alternative to on-chain storage. This approach would introduce trust in the storage system since the data stored could change while the reference remains the same. Additionally, since all data in a blockchain is stored on every node in the network, it is publicly visible. There is no obvious way for a service provider to hide some of his service descriptions from the public.

As a direct consequence of this public visibility, there is no way to perform computations on private data on-chain without revealing it. Assume a consumer wants to prove to a provider that he has access to another provider's API. That second provider could publicly provide the hashes of all tokes that give access to his service. Then, the consumer could simply hash his private access token and show the hash to the first provider, which could in turn verify it by comparing it to the published hashes. However, for this to be trustless, the consumer would need to perform the hash operation on-chain and with that reveal his private token. Simply computing the hash off-chain would not proof anything to the provider.

Again, we derive three challenges from these findings:

1. We need to find a way to store data off the chain without giving up its manipulation-resistance. 2. As all on-chain data is publicly visible, techniques for trustless but privacypreserving off-chain storage should be developed. 3. Off-chain computations on private data which can be verified on-chain without revealing said data would augment the set of possible use cases.

In summary, off-chaining strategies are needed to address both, functional limitations of and high costs incurring from on-chain computation and storage.

Off-Chaining Patterns

We now introduce a set of off-chaining patterns identified, which can be used individually or in combination to move computation and data off the blockchain. Each pattern aims at maintaining the key properties of blockchains and includes techniques to ensure that they are not compromised to an unwanted degree.

Challenge Response Pattern

Context: A smart contract models a state machine with well-defined final states. State transitions are cheap to compute, but checking whether a given state is a final state is expensive.

Solution: Instead of checking whether a state is final or not in a smart contract on a blockchain, the same check is performed off-chain on the client side. A client can notify a smart contract when a final state has been reached. Other clients can prove claims wrong by providing a valid state transition. Using this pattern, the computation never has to be performed on-chain. Example: The end game condition for chess is too expensive to check on-chain. The players, however, can easily check the condition off-chain. Hence, instead of checking the end game condition in a smart contract, a player simply claims check mate. If the claim was false, his opponent can simply prove him wrong by submitting a valid move. If the claim was true and the opponent cannot submit a valid move, the winner is paid out. Figure 2 gives an overview of the full challenge response protocol for chess also considering draws and timeouts. For a more detailed description, we refer to [START_REF]Chess on Ethereum[END_REF][START_REF]Ethereum Chess Proof-of-Concept Implementation[END_REF].

Discussion: This pattern allows computations to be off-chained efficiently in scenarios where smart contracts act as state-machines. Since it allows for complex operations to be moved completely off-chain and with that circumvents the complexity upper-bound for on-chain transactions, it can extend possible use cases and potentially lead to cost savings. Note though, that the pattern increases the overall amount of on-chain transactions, which requires a careful calculation of costs. Also, increased availability of the parties involved in the smart contract implementing the pattern is required, since the use of timeouts is essential to ensure progress.

Implementation: This pattern does not require additional technologies besides smart contracts. For an exemplary implementation of this pattern, refer to [START_REF]Ethereum Chess Proof-of-Concept Implementation[END_REF].

Off-chain Signatures Pattern

Context: Two network participants know that they will perform a set of transactions in the future. They want to reduce the cost of these transactions or want to hide them from other network participants.

Solution: Together, the two participants specify a smart contract including a function, which applies an external state given as argument to the contract state. This function includes a signature check to ensure both participants agree with the state change. Only if valid signatures of both participants are supplied with a requested new state, the new state is applied. This contract is deployed to the blockchain and both participants optionally make a deposit.

Then, the participants perform transactions purely off-chain and peer-topeer, without involving the blockchain: One participant computes a new state, wraps it in a transaction, signs it and sends it to his counterpart. The recipient then checks the new state, signs the transaction as well in case he agrees and sends it back to the sender. This transaction, signed by both parties, can now be sent to the smart contract by a participant at any point in time. After validating both signatures, the contract updates its state accordingly.

Example: Participants A and B create a smart contract with a signaturelocked state update function and deposit 50 units of cryptocurrency each. Now, A wants to transfer 10 units to B. For that, she creates a transaction locally, which includes a new state where A and B have balances of 40 and 60. She signs it and sends it to B, who signs it as well. Now, B can use the transaction to update the on-chain balance at any point in time. However, A and B could perform further off-chain value transfers without ever settling on-chain unless one side's deposit is used up. This application of the pattern for off-chain value transfer is often referred to as payment channel.

Discussion: This pattern allows efficient off-chain transactions without introducing trust into the system. The core insight is, that the guarantee to be able to settle a transaction is as good as actually executing the transaction on-chain. Signing a new state is analogous to writing a check in a traditional financial transaction. Using off-chain transactions can lead to significant cost savings as transaction fees only apply for on-chain settlement. Furthermore, the pattern can enhance privacy and confidentiality, as all transactions but the final settlement remain hidden from the network. From a blockchain network perspective, this pattern helps to take load off the system and with that enhances scalability.

There are many other applications besides simple value transfers. As shown in figure 3, we were able to move the core parts of the chess game off-chain by using this pattern. This not only helped to lower the cost of a game, but also to remove time dependence on block intervals.

Since initial deposits to the smart contracts are required in most cases, establishing contracts with many peers can lock a considerable amount of funds. Also, malicious participants could freeze funds by denying signatures. Hence, contracts should specify timeouts which trigger automatic settlement.

Implementation: Besides on-chain smart contracts, this pattern requires a peer-to-peer communication channel to exchange signed off-chain transactions.

Fig. 3. Off-and on-chain interactions in the chess application

In the Ethereum ecosystem, for example, the Whisper Messaging Protocol [4] can be used. There are various efforts to leverage this pattern to build off-chain value transfer networks for existing blockchains: The lightning network [START_REF] Poon | The bitcoin lightning network: Scalable off-chain instant payments[END_REF] provides an implementation for the Bitcoin ecosystem, while Raiden [START_REF]Raiden Network[END_REF] targets the Ethereum network.

Content-Addressable Storage Pattern

Context: A large amount of data is associated with a smart contract. On-chain storage is too expensive.

Solution: Store the data off-chain in a content-addressable storage system and store the reference in the smart contract. Clients using the smart contract can retrieve the reference and based on that retrieve the data. Then, they can verify the data's correctness by recomputing its address from itself and comparing it to the reference stored in the smart contract.

Example: A smart contract encodes ownership of a piece of digital art. However, a piece of art would be very expensive to store on-chain due to its size. To solve this problem, the description is stored in a content-addressable storage system which stores files by their hashes. The file hash is also stored in the smart contract, serving as a reference to the artwork. Clients can then retrieve the hash of the externally stored piece of art from the contract and use it to query the storage system. The result can then simply be hashed to verify its correctness.

Fig. 4. Content-Addressable Storage Pattern

Discussion: This pattern allows the trustless outsourcing of data to an offchain storage system since a modification in the data would immediately change its address and with that invalidate its references.

By applying the pattern, an application's storage cost can be greatly reduced and files, which originally could not be stored on-chain in the first place, can now be referenced without introducing trust. Additionally, as the data retrieval is done on the client side from an external storage system, privacy features may be implemented by adding access control to that system. However, this requires careful considerations depending on the use case, since leaked data can immediately be confirmed to be authentic by recalculating its address.

While not in scope of this pattern, the required external content-addressable storage system itself has to be reliable and available. In case of unavailability or data-loss, the blockchain-based part of the application may also become unavailable.

In the future, this pattern could be extended to support trustless computation on data stored off-chain: First, content-addressed data referenced from a smart contract could be sent to the contract. Then, integrity could be verified on chain. In case of success, the smart contract could modify the data, update its reference to that new data and write it to an event. An untrusted external worker could then write that data back to the content-addressable storage system the inputs were retrieved from. While theoretically interesting, we did not yet observe this extension. Hence, it is not part of the pattern.

Implementation: As mentioned before, a content-addressable storage system is required to work in conjunction with smart contracts. Two such technologies, which address data by its hash and try to ensure availability and durability are the Interplanetary File System (IPFS) [START_REF] Benet | IPFS -content addressed, versioned, P2P file system[END_REF] and Swarm [START_REF] Trón | Swap, swear and swindle -incentive system for swarm[END_REF].

Delegated Computation Pattern

Context: a) A node participating in a blockchain network wants to prove a property of its private data without publishing it. b) A node wants to perform a computation that is too complex to be executed on-chain.

Solution: Outsource computation to an untrusted third party and, besides the result, generate a proof of correct execution. Instead of executing the computation itself, verify the proof of correct execution on-chain. Example: There is an on-chain list of hashes of ID-card information which refers to people who are allowed to call a smart contract function. Now, anyone listed can prove that he has an ID-card which authorizes him to call the contract function by hashing his card information locally and supplying the result including a proof of correctness. The proof does not require to reveal any of the information on the card.

Discussion: This pattern allows the trustless outsourcing of computation to untrusted parties. The third party, also called the prover, does not have to reveal any private inputs or intermediate results of the proof creation. The only information leaked is that the prover knows all the information necessary to correctly compute the output. For that, non-interactive zero-knowledge proofs, more specifically zero-knowledge Succinct Non-interactive ARgument of Knowledge (zkSNARKs), can be employed [START_REF] Parno | Pinocchio: Nearly practical verifiable computation[END_REF][START_REF] Bitansky | From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again[END_REF].

Unlike with regular computations on the blockchain, this pattern allows offchained computations to hide information used during execution. Hence, not having to expose information but the result of a computation greatly enhances privacy. Furthermore, the proofs can be designed in a way that the verification cost is independent of the complexity of the off-chained computation. Thus, after a complexity threshold is reached, on-chain verification of a computation is cheaper than its on-chain execution. This result can be leveraged to increase a blockchain's throughput. Even operations exceeding the on-chain complexity limits for computations may still be executed off-chain using this patterns.

The state of the art non-interactive zero-knowledge proofs require a trusted setup phase to be performed before proofs can be generated. This can, depending on the use case, introduce undesirable trust in the overall system. Additionally, the proof generation for a computation causes an overhead over its non-verifiable execution. Yet, there is neither a high level language for the convenient specification of off-chain computations nor are there tools for simple on-chain verification of proofs. Therefore, while powerful and already used in practice, this pattern is currently only applied in rather specific scenarios, e.g., in zCash, which is a Bitcoin-based blockchain which implements privacy preserving transactions [6,[START_REF] Sasson | Zerocash: Decentralized anonymous payments from bitcoin[END_REF].

Implementation: For the verification of off-chain computations from smart contracts, the underlying blockchain needs to support the operations needed to check proofs. These can either be use case specific, or universal building blocks which can be used to verify any proof. While zCash directly added the verification logic for their specific computation to their protocol, Ethereum plans to add operations to support verification of arbitrary zkSNARKs with the Ethereum Improvement Proposals 196 and 197 [START_REF]Ethereum Improvement Proposals (EIPs)[END_REF].

Low Contract Footprint Pattern

Context: Changing a smart contract's state requires an on-chain transaction. To incentivize the processing of a transaction by the network, a fee has to be paid. This fee depends on the complexity of the smart contract function called as well as its use of storage.

Solution:

To optimize fees, contracts should be designed in a way that minimizes the number and size of on-chain transactions. The following two techniques can be used to reduce the footprint.

-Do not check conditions on-chain after a state change. Let nodes perform the condition check locally and trigger an on-chain check in case of success.

-Optimize for writes, not reads. Reading from a smart contracts is a local off-chain operation and does not require an on-chain transaction. Minimize writes and store information free of redundancy. Compute derived data locally during reads.

Examples:

-In the service marketplace application, a service provider needs to make sure consumers are removed from the on-chain authorization list after the time period the consumer paid for is over. Instead of periodically triggering or linking the condition check to another contract function and risking frequent reevaluation, he tracks the access period locally and triggers the on-chain check after it has elapsed. This reduces the amount of on-chain evaluations to one. -If the service provider wants to know the number of customers currently subscribed to his service, he should not add a counter to the smart contract. He can compute the number locally at any point from the authorization list. This saves storage space and counter update operations.

Discussion: This pattern may not initially seem like an off-chaining approach, as it does not explicitly take something off the chain. However, it prevents information to be stored or processed on-chain in the first place. Hence, this may be the least obvious, but the most employed and intuitive off-chaining pattern.

Implementation: No additional components or techniques are required besides smart contracts to implement this pattern.

Summary and Outlook

In this paper we motivated the need for off-chain approaches to overcome limitations in today's blockchain implementations and even more, to extend their functionality and to reduce usage costs. After deriving key challenges based on our experiences from implementing several blockchain-based applications, we presented five off-chaining patterns for moving computation and data off the blockchain, without compromising important blockchain properties, in particular, the trustlessness property. We expect blockchain systems to further mature and improve with regards to scalability and privacy in the future by combining and implementing ideas like, for example, new consensus algorithms, sharding, or homomorphic encryption. However, we still consider off-chaining techniques to be key tools in blockchainbased application engineering as they introduce additional functionality and potentially significant cost benefits.

Fig. 1 .

 1 Fig. 1. Challenge Reponse Pattern

Fig. 2 .

 2 Fig. 2. Challenge Response Pattern applied for Chess

Fig. 5 .

 5 Fig. 5. On-chain processing vs. Delegated Computation Pattern

The Need for Off-Chaining Computation and Data Over the last two years, we gained extensive experiences during proof-of-concept implementations of blockchain-based applications prototypes. We motivate offchaining insights by discussing exemplary challenges for two of these applications. While all prototypes developed at TU Berlin have been realized on the Ethereum platform[START_REF] Buterin | Ethereum: A next-generation smart contract and decentralized application platform[END_REF], we consider our findings to be representative for all of today's public blockchain implementations.As a first application, we created a fair and manipulation-resistant chess game on the Ethereum platform[START_REF]Chess on Ethereum[END_REF].Today, online gaming relies on a trusted intermediary which runs games and ensures players obey the rules. However, this intermediary needs to be trusted to not cheat or steal funds. To eliminate that trust, we implemented the chess logic as well as data structures required to persist the game state in a smart contract. Conceptually, that already solves the problem: Players send moves to the contract, which modifies game state persisted internally for valid moves. After a valid move, the contract checks end game conditions and pays out the winner if a condition is met. Checking end game conditions, however, is computationally expensive. All potential moves have to be calculated and verified to check the check mate condition. This is not possible in a smart contract as it violates the complexity upper bound for on-chain transactions.Three things can be learned from that:1. We need to find a way to perform the end-game check off chain, on the client side, without impacting the blockchain's trustlessness property.


Christos Petsos
email: chpetsos@seerc.org

Simeon Veloudis
email: sveloudis@seerc.org

Iraklis Paraskakis
email: iparaskakis@seerc.org

Foundations for Designing, Defining, Validating and Executing Access Control Policies in Cloud Environments

Keywords: Foundation framework for Policies, Designing policies, Defining Policies Policy Governance, Access Control, Policy Governance, Ontologies, Description Logics 1

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Cloud computing enables enterprises to realise significant cost savings, whilst boosting their agility and productivity. Nevertheless, due to security and privacy concerns, many enterprises are reluctant to relinquish control of-oftentimes critical-corporate assets by migrating their data and applications to third-party cloud providers [START_REF]What's Hindering the Adoption of Cloud Computing in Europe? Cloud Security Alliance[END_REF]. One way to alleviate these concerns, hence bolster the adoption of cloud computing, is to infuse adequate access control policies into the applications through which critical assets are accessed in the cloud [START_REF] Veloudis | Defining an Ontological Framework for Modelling Policies in Cloud Environments[END_REF]. Nevertheless, the inherently dynamic nature of cloud environments calls for policies that are able to incorporate a potentially complex body of contextual knowledge pertaining to access requests [START_REF] Veloudis | An Ontological Template for Context Expressions in Attribute-Based Access Control Policies[END_REF]. As an example, consider a policy whereby a particular entity (𝑠) is allowed to read a sensitive data object (𝑜) only when: (i) 𝑜 resides in a data centre in the EU; (ii) 𝑠 resides in a specific geographical area (say the city of Athens), or the request originates from a particular subnet; (iii) the request is received during a prescribed time interval.

We argue that, for stakeholders to entrust such complex access control policies with the protection of their sensitive assets, a framework that provides assurances about the effectiveness of the policies is required [START_REF] Veloudis | Defining an Ontological Framework for Modelling Policies in Cloud Environments[END_REF]. In particular, a framework is required that assists developers in infusing effective access control policies into the applications through which sensitive assets are accessed in the cloud. Our work, conducted as part of the PaaSword project [START_REF]PaaSword project[END_REF], provides such a framework. More specifically, it offers a generic security-by-design solution-essentially a PaaS offeringthat provides assurances about the effectiveness of context-aware access control policies by facilitating their governance. To this end, it draws upon a semantic representation of policies, one that ontologically captures the various knowledge artefacts that are encoded in the policies. Such a representation disentangles the expression of policies from the actual code of the applications into which they are infused hence enabling automated reasoning about their correctness.

This paper proposes an approach to such reasoning. In particular, it proposes a set of ontologically-expressed constraints, the so-called well-formedness constraints, that articulate all those knowledge artefacts that must, may or must not be embodied in an access control policy. These constraints give rise to a higher-level ontology, one that specifies an allowable form, or structure, by which access control policies must abide. Evidently, well-formedness constraints empower stakeholders to harness the knowledge artefacts embodied in access control policies that protect their sensitive assets. In other words, they empower stakeholders to infuse into these policies their business logic and overall stance towards security. In this respect, well-formedness constraints assist developers in devising policies that are appropriate for the stakeholders' needs, hence for the assets that they protect.

The rest of this paper is structured as follows. Section 2 presents an ontological representation for access control policies and well-formedness constrains. Section 3 outlines a mechanism that reasons about the satisfaction of well-formedness constraints. Section 4 discusses related work and Section 5 outlines conclusions.

Constraining Access Control Policies

As already discussed, the dynamic nature of cloud environments calls for access control policies that are able to incorporate the contextual knowledge pertaining to access requests. Attribute-based Access Control (ABAC) policies [START_REF] Hu | Guide to Attribute Based Access Control (ABAC), Definition and Considerations[END_REF], due to their inherent generality stemming from their inherent reliance on the generic concept of an attribute, are particularly suitable for capturing such knowledge [START_REF] Veloudis | An Ontological Template for Context Expressions in Attribute-Based Access Control Policies[END_REF] and are thus adopted in our work. This section outlines an OWL-based representation for ABAC policies and well-formedness constraints; as already mentioned, the latter harness the attributes embodied in the former.

A Model for ABAC Rules and Policies

Following the XACML standard [START_REF]eXtensible Access Control Markup Language (XACML) Version 3.0[END_REF], an ABAC policy comprises one or more ABAC rules. Upon receipt of an access request, a rule-combining algorithm [START_REF]eXtensible Access Control Markup Language (XACML) Version 3.0[END_REF] is executed in order to select which one of these rules, if any, will be applied in order to arrive at a 'permit' or a 'deny' decision. It follows that, for each access request, an ABAC policy resolves to at most one of its constituent rules (a policy that does not resolve to any of its constituent rules is considered 'Not Applicable' or 'Indeterminate' [START_REF]eXtensible Access Control Markup Language (XACML) Version 3.0[END_REF]).

An ABAC rule comprises an antecedent and a consequent. The latter specifies the rule's decision, which according to the XACML standard, invariably resolves to either a 'permit' or a 'deny'. The former articulates a (pre-)condition (or 'target' in the XACML jargon) that must be satisfied in order for the rule to be enforceable. More specifically, it incorporates a set of relevant knowledge artefacts, its attributes, whose values need to be taken into account when deciding whether to permit, or deny, a request. These attributes are drawn from an underlying Context Model (CM)-an extensible ontological framework that includes interrelated concepts suitable for capturing attributes and the properties thereof. A simplified view of the CM that is used in this work, one which includes only concepts and properties considered in this paper, is depicted in Fig. 1 (for more details on the CM, the interested reader is referred to [START_REF]PaaSword Deliverable[END_REF]).

Ontologically, ABAC policies are represented as instances of the concept 𝐴𝐵𝐴𝐶𝑃𝑜𝑙𝑖𝑐𝑦, and ABAC rules as instances of the concept 𝐴𝐵𝐴𝐶𝑅𝑢𝑙𝑒; ABAC policies are associated with their constituent rules through the object property ℎ𝑎𝑠𝐴𝐵𝐴𝐶𝑅𝑢𝑙𝑒. The antecedent and consequent of an ABAC rule are represented, respectively, as instances of the concepts 𝐴𝐵𝐴𝐶𝐴𝑛𝑡 and 𝐴𝐵𝐴𝐶𝐶𝑜𝑛𝑠; an ABAC rule is associated with its antecedent and consequent via the properties ℎ𝑎𝑠𝐴𝐵𝐴𝐶𝐴𝑛𝑡 and ℎ𝑎𝑠𝐴𝐵𝐴𝐶𝐶𝑜𝑛𝑠 respectively. In addition, the following restrictions apply. Firstly, an ABAC policy is invariably associated with at least one ABAC rule; secondly, an ABAC rule is invariably associated with exactly one antecedent and exactly one consequent; thirdly, the consequent of an ABAC rule always resolves to either a 'permit' or a 'deny' decision (represented respectively by the individuals 𝑝𝑒𝑟𝑚𝑖𝑡 and 𝑑𝑒𝑛𝑦). All three restrictions are ontologically captured in terms of terminological (TBox) axioms expressed in the 𝒮ℛ𝒪ℐ𝒬 Description Logic (DL) [START_REF] Horrocks | The even more irresistible SROIQ[END_REF]. These axioms are presented in Table 1. The first demands that each ABAC policy, i.e. each instance of the concept 𝐴𝐵𝐴𝐶𝑃𝑜𝑙𝑖𝑐𝑦, is also an instance of the (abstract) class that comprises all those individuals that have at least one association through the property ℎ𝑎𝑠𝐴𝐵𝐴𝐶𝑅𝑢𝑙𝑒 with an individual from the concept 𝐴𝐵𝐴𝐶𝑅𝑢𝑙𝑒. The second demands that each ABAC rule, i.e. each instance of 𝐴𝐵𝐴𝐶𝑅𝑢𝑙𝑒, is also an instance of the class that comprises all those individuals that have exactly one association through each of the properties ℎ𝑎𝑠𝐴𝐵𝐴𝐶𝐴𝑛𝑡 and ℎ𝑎𝑠𝐴𝐵𝐴𝐶𝐶𝑜𝑛𝑠 with individuals from the concepts 𝐴𝐵𝐴𝐶𝐴𝑛𝑡 and 𝐴𝐵𝐴𝐶𝐶𝑜𝑛𝑠 respectively. Finally, the third axiom demands that the class 𝐴𝐵𝐴𝐶𝐶𝑜𝑛𝑠 comprises solely the individuals 𝑝𝑒𝑟𝑚𝑖𝑡 and 𝑑𝑒𝑛𝑦.

Well-Formedness Constraints

Well-formedness constraints specify the attributes of an ABAC rule, i.e. all those knowledge artefacts from the underlying CM that must, may or must not be embodied in the antecedent of an ABAC rule. In this respect, well-formedness constraints give rise to a higher-level ontology (HLO) that defines an allowable form, or structure, for the antecedent of an ABAC rule (see Fig. 1). The HLO not only articulates the permissible knowledge artefacts embodied in the antecedent, but goes a step further to determine the allowable cardinalities with which these artefacts may appear, as well as the allowable values that they may assume.

Fig. 1. HLO Constraints

We now briefly elaborate on the HLO constraints that have been devised for ABAC rules in the frame of the PaaSword project. These constraints are ontologically expressed in terms of 𝒮ℛ𝒪ℐ𝒬 TBox axioms which restrict the class 𝐴𝐵𝐴𝐶𝐴𝑛𝑡. It is to be noted here that these constraints are malleable in the sense that they can be altered to express alternate structures for the antecedent of ABAC rules-i.e. structures that potentially reflect more accurately the application-specific needs of an organisation adopting the PaaSword framework. This malleability is of utmost significance for stakeholders to infuse into access control policies their business logic and overall stance towards security.

The first constraint states that each ABAC rule must embody exactly one protected asset. Ontologically, this is captured through a TBox axiom that demands that the antecedent of an ABAC rule, i.e. each instance of the concept 𝐴𝐵𝐴𝐶𝐴𝑛𝑡, is associated with exactly one individual from the class 𝑂𝑏𝑗𝑒𝑐𝑡 of the CM, and that this association should be realised through the object property ℎ𝑎𝑠𝑂𝑏𝑗. Table 2 provides a formal expression of this axiom, as well as of the rest of the axioms outlined in this section. Similarly, the second axiom states that each ABAC rule must be associated, through the property ℎ𝑎𝑠𝐴𝑐𝑡, with exactly one action from the class 𝐴𝑐𝑡𝑖𝑜𝑛 (i.e. with exactly one action to be performed on the protected asset); the third axiom states that each ABAC rule must be associated with at least one subject from the class 𝑆𝑢𝑏𝑗𝑒𝑐𝑡 (i.e. with at least one entity requesting access to the protected asset), and the fourth axiom demands that each ABAC rule may refer, via the property ℎ𝑎𝑠𝐶𝐸 to at most one context expression-i.e. to at most one expression that constrains the values of the contextual attributes that pertain to an access request. Context expressions take the form of instances of the class 𝐶𝑜𝑛𝑡𝑒𝑥𝑡𝐸𝑥𝑝𝑟 (see Fig. 1) and are further discussed below. A context expression (CE) is a propositional logic expression that is attached to the antecedent of an ABAC rule and articulates the contextual conditions that must hold in order to permit, or deny, a request. These contextual conditions may refer to the subject and/or object of a request, or to the request itself. In other words, a CE captures the body of contextual knowledge that must be taken into account when deciding upon a request. Ontologically, a CE is represented as an instance of the class 𝐶𝑜𝑛𝑡𝑒𝑥𝑡𝐸𝑥𝑝𝑟 (see Fig. 1). The various attributes that it binds, i.e. its parameters, are represented as instances of the CM-in particular, as instances of the classes encompassed by the 𝐶𝑜𝑛𝑡𝑒𝑥𝑡𝐴𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒𝑠 concept. These parameters are associated with their encompassing CE through the object property ℎ𝑎𝑠𝑃𝑎𝑟𝑎𝑚 and may be combined through the usual propositional logic connectives. A CE invariably enjoys at least one association with a parameter; ontologically, this is captured by an axiom analogous to Axiom 3 of Table 2. Moreover, a CE may be defined recursively, in terms of one or more other CEs; this is captured by including the class 𝐶𝑜𝑛𝑡𝑒𝑥𝑡𝐸𝑥𝑝𝑟 in both the domain and the range of the property ℎ𝑎𝑠𝑃𝑎𝑟𝑎𝑚. Finally, a context expression is attached to the entity that it refers to through the object property 𝑟𝑒𝑓𝑒𝑟𝑠𝑇𝑜.

The HLO may encompass constraints that restrict the allowable forms that a CE can assume when attached to a particular ABAC rule. These constraints restrict the cardinalities with which certain knowledge artefacts from the class 𝐶𝑜𝑛𝑡𝑒𝑥𝑡𝐴𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒𝑠 may appear in a CE, as well as the allowable ranges of values that these artefacts may assume. As an example, consider an HLO constraint that demands that any CE attached to an ABAC rule should invariably incorporate at least one parameter that confines the whereabouts of the subject 𝑠 of a request to the physical location identified as Athens, or to the network location identified by the subnet 123.0.0.0/8. Ontologically, this constraint takes the form:

𝐶𝑜𝑛𝑡𝑒𝑥𝑡𝐸𝑥𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛 ⊑ (≤ 1𝑟𝑒𝑓𝑒𝑟𝑠𝑇𝑜. {𝑠}) ⊓ ((≤ 1ℎ𝑎𝑠𝑃𝑎𝑟𝑎𝑚. {𝐴𝑡ℎ𝑒𝑛𝑠}) ⊔ (≤ 1ℎ𝑎𝑠𝑃𝑎𝑟𝑎𝑚. {123.0.0.0/8})) (1)
3

Reasoning about the Correctness of ABAC Policies

Reasoning about the correctness of an ABAC rule, hence about the correctness of an ABAC policy that resolves to that rule, involves reasoning about the abidance of the rule by the HLO constraints. Below, we outline how this reasoning is performed by a mechanism that we have developed as part of the PaaSword project. As an example, suppose the following set of 𝒮ℛ𝒪ℐ𝒬 axioms that articulate the attribute values associated with an ABAC rule; we shall term such an axiom-set a knowledge base (KB) [START_REF] Tao | Integrity Constraints in OWL[END_REF].

ℛ ≡ {𝐴𝐵𝐴𝐶𝑅𝑢𝑙𝑒(𝑟), 𝐴𝐵𝐴𝐶𝐴𝑛𝑡(𝑎), 𝑂𝑏𝑗𝑒𝑐𝑡(𝑜), 𝑆𝑢𝑏𝑗𝑒𝑐𝑡(𝑠), 𝐶𝑜𝑛𝑡𝑒𝑥𝑡𝐸𝑥𝑝𝑟(𝑒), 𝑃ℎ𝑦𝐿𝑜𝑐𝑎𝑡𝑖𝑜𝑛(𝐴𝑡ℎ𝑒𝑛𝑠), ℎ𝑎𝑠𝐴𝐵𝐴𝐶𝐴𝑛𝑡(𝑟, 𝑎), ℎ𝑎𝑠𝐴𝐵𝐴𝐶𝐶𝑜𝑛𝑠(𝑟, 𝑝𝑒𝑟𝑚𝑖𝑡), ℎ𝑎𝑠𝑂𝑏𝑗(𝑎, 𝑜), ℎ𝑎𝑠𝑆𝑢𝑏𝑗(𝑎, 𝑠), ℎ𝑎𝑠𝐶𝐸(𝑎, 𝑒), ℎ𝑎𝑠𝑃𝑎𝑟𝑎𝑚(𝑒, 𝐴𝑡ℎ𝑒𝑛𝑠), 𝑟𝑒𝑓𝑒𝑟𝑠𝑇𝑜(𝑒, 𝑠)}

According to ℛ, the antecedent 𝑎 of the ABAC rule 𝑟 is associated with the object 𝑜, the subject 𝑠 and the context expression 𝑒; 𝑒 is further associated with the (physical) location parameter 𝐴𝑡ℎ𝑒𝑛𝑠 which refers to 𝑠. Two seminal assumptions underpinning OWL are the Open-World Assumption (OWA) and the non-Unique Name Assumption (non-UNA). Nevertheless, these assumptions render the use of OWL cumbersome when reasoning about constraint satisfaction. Consider, for example, the KB ℛ above. ℛ fails to specify the action that is to be performed upon the object 𝑜. However, according to the OWA, this does not mean that the rule 𝑟 described by ℛ does not have such an action associated with its antecedent: it merely means that this association is not specified in ℛ. In order to overcome this obstacle, we adopt the approach proposed in [START_REF] Tao | Integrity Constraints in OWL[END_REF] and dispense with the OWA and the non-UNA, effectively enabling closed-world reasoning when checking the abidance of ABAC rules by HLO constraints. This reasoning is based on an extended semantics of OWL, namely the Integrity Constraint semantics [START_REF] Tao | Integrity Constraints in OWL[END_REF]; an outline of how such reasoning is performed is in order.

Each HLO axiom is translated into a query, one that is posed to the KB under validation with the aim of discovering any individuals that violate the axiom: if the query returns an empty set of individuals, the axiom is considered to hold; otherwise, it is considered to be violated. The query is, in fact, an assertion axiom that uses variables in place of individuals and expresses the negation of the HLO axiom that it translates. As an example, consider Axiom 2 of Table 2. This axiom is translated into a query that attempts to discover in ℛ any individuals that belong to the class 𝐴𝐵𝐴𝐶𝐴𝑛𝑡 and which either enjoy no associations (through the property ℎ𝑎𝑠𝐴𝑐𝑡) with instances of the class 𝐴𝑐𝑡𝑖𝑜𝑛, or enjoy two or more such associations with distinct instances of 𝐴𝑐𝑡𝑖𝑜𝑛. Formally:

𝐴𝐵𝐴𝐶𝐴𝑛𝑡(𝑥) ∧ (not(ℎ𝑎𝑠𝐴𝑐𝑡(𝑥, 𝑦) ∧ 𝐴𝑐𝑡𝑖𝑜𝑛(𝑦)) ∨ (ℎ𝑎𝑠𝐴𝑐𝑡(𝑥, 𝑦) ∧ ℎ𝑎𝑠𝐴𝑐𝑡(𝑥, 𝑧) ∧ 𝐴𝑐𝑡𝑖𝑜𝑛(𝑦) ∧ 𝐴𝑐𝑡𝑖𝑜𝑛(𝑧) ∧ not(𝑦 = 𝑧)) (3)
These queries are termed in [START_REF] Tao | Integrity Constraints in OWL[END_REF] Distinguished Conjunctive Queries with Negation as Failure (DCQ not ). DCQ not are posed to the KB under validation as SPARQL queries [START_REF]SPARQL 1.1 Query Language W3C Recommendation 21[END_REF]. SPARQL queries are executed in the Pellet reasoner [START_REF] Sirin | Pellet: A practical OWL-DL reasoner[END_REF] (however, any other OWL reasoner could have been used instead). In [START_REF] Tao | Integrity Constraints in OWL[END_REF], a set of translation rules for turning a 𝒮ℛ𝒪ℐ𝒬 axiom into a DCQ not , hence into a SPARQL query, is presented.

Related Work

A number of approaches have been proposed for the semantic representation of policies [START_REF] Kagal | A policy language for a pervasive computing environment[END_REF][START_REF] Nejdl | Ontology-Based policy specification and management[END_REF][START_REF] Uszok | KAoS Policy Management for Semantic Web Services[END_REF]. These generally rely on OWL [START_REF]OWL 2 Web Ontology Language Primer (2 nd Edition)[END_REF] for capturing the various knowledge artefacts that underpin the definition of a policy. In [START_REF] Kagal | A policy language for a pervasive computing environment[END_REF] KaoS is presented-a generic framework offering: (i) a human interface layer for the expression of policies; (ii) a policy management layer that is capable of resolving conflicting policies; (iii) a monitoring and enforcement layer that encodes policies in a programmatic format suitable for enforcing them. KaoS lacks any mechanism for automatically checking the correctness, hence the effectiveness, of policies.

In [START_REF] Nejdl | Ontology-Based policy specification and management[END_REF] Rei is proposed: a framework for specifying, analyzing and reasoning about policies. Similar to our work, a policy comprises a list of rules that take the form of OWL properties; it also comprises a context that defines the underlying policy domain. Rei resorts to the use of constructs adopted from rule-based programming languages for the definition of policy rules. This essentially prevents Rei from exploiting the full inferencing potential of OWL as policy rules are expressed in a formalism is alien to OWL. In addition, it does not provide any mechanism for reasoning about the effectiveness of policies.

In [START_REF] Uszok | KAoS Policy Management for Semantic Web Services[END_REF] the authors propose POLICYTAB for facilitating trust negotiation in Semantic Web environments. POLICYTAB adopts ontologies for the representation of policies that guide a trust negotiation process ultimately aiming at granting, or denying, access to sensitive Web resources. These policies essentially specify the credentials that an entity must possess in order to carry out an action on a sensitive resource that is under the ownership of another entity. Nevertheless, no attempt is made to semantically model the context associated with access requests, rendering POLICYTAB inadequate for the dynamic nature of cloud environments.

Conclusions

We have presented an approach to reasoning about the correctness, hence the effectiveness, of access control policies in dynamic cloud environments. The correctness is judged on the basis of ontologically-expressed constraints, the so-called HLO constraints. The reasoning is based on an extended semantics of OWL, one that dispenses with the OWA and the non-UNA, allowing the transformation of the constraints into queries that are posed to the KBs that represent the rules under validation.

Table 1 .

 1 ABAC policy model restriction axioms

	Axiom 1 𝐴𝐵𝐴𝐶𝑃𝑜𝑙𝑖𝑐𝑦 ⊑ ≤ 1ℎ𝑎𝑠𝐴𝐵𝐴𝐶𝑅𝑢𝑙𝑒. 𝐴𝐵𝐴𝐶𝑅𝑢𝑙𝑒
	Axiom 2 𝐴𝐵𝐴𝐶𝑅𝑢𝑙𝑒 ⊑ (≥ 𝑅 𝑖 . 𝐶 𝑖 ) ⊓ (≤ 1𝑅 𝑖 . 𝐶 𝑖 )
	where 𝑖 = 1,2 and 𝑅 𝑖 ≡ ℎ𝑎𝑠𝐴𝐵𝐴𝐶𝐴𝑛𝑡, 𝐶 𝑖 ≡ 𝐴𝐵𝐴𝐶𝐴𝑛𝑡, for 𝑖 = 1
	𝑅 𝑖 ≡ ℎ𝑎𝑠𝐴𝐵𝐴𝐶𝐶𝑜𝑛𝑠, 𝐶 𝑖 ≡ 𝐴𝐵𝐴𝐶𝐶𝑜𝑛𝑠, otherwise
	Axiom 3 𝐴𝐵𝐴𝐶𝐶𝑜𝑛𝑠𝑒𝑞𝑢𝑒𝑛𝑡 ≡ {𝑝𝑒𝑟𝑚𝑖𝑡, 𝑑𝑒𝑛𝑦}

Table 2 .

 2 HLO axioms

	Axiom 1 𝐴𝐵𝐴𝐶𝐴𝑛𝑡 ⊑ (≤ 1ℎ𝑎𝑠𝑂𝑏𝑗. 𝑂𝑏𝑗𝑒𝑐𝑡) ⊓ (≥ 1ℎ𝑎𝑠𝑂𝑏𝑗. 𝑂𝑏𝑗𝑒𝑐𝑡)
	Axiom 2 𝐴𝐵𝐴𝐶𝐴𝑛𝑡 ⊑ (≤ 1ℎ𝑎𝑠𝐴𝑐𝑡. 𝐴𝑐𝑡𝑖𝑜𝑛) ⊓ (≥ 1ℎ𝑎𝑠𝐴𝑐𝑡. 𝐴𝑐𝑡𝑖𝑜𝑛)
	Axiom 3 𝐴𝐵𝐴𝐶𝐴𝑛𝑡 ⊑ ≤ 1ℎ𝑎𝑠𝑆𝑢𝑏𝑗. 𝑆𝑢𝑏𝑗𝑒𝑐𝑡
	Axiom 4 𝐴𝐵𝐴𝐶𝐴𝑛𝑡 ⊑ ≥ 1ℎ𝑎𝑠𝐶𝐸. 𝐶𝑜𝑛𝑡𝑒𝑥𝑡𝐸𝑥𝑝𝑟

Acknowledgements

The research leading to these results has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 644814.