Fabrizio Montesi

Dan Sebastian Thrane

Packaging Microservices

We describe a first proposal for a new packaging system for microservices based on the Jolie programming language, called the Jolie Package Manager (JPM). Its main features revolve around service interfaces, which make the functionalities that a service provides and depends on explicit. For the first time, JPM supports binding a service to an externally-provided package, and a notion of interface parametricity that can be used to develop generic service libraries that can modify the behaviour of arbitrary services. We illustrate the latter with a generic circuit breaker package.

Introduction

Microservices is an emerging paradigm where that components (even the internal ones) are autonomous and reusable services [START_REF] Dragoni | Microservices: yesterday, today, and tomorrow[END_REF]. Applications are built by composing services as black boxes, using message passing.

The nature of microservices fosters granularity, and a MicroService Architecture (MSA) typically consists of many individual services. Since services are independent and their coordination happens only through message exchanges, code reuse (the focus of this work) takes a different form than that found in standard approaches based on software packages. Typically, in other paradigms, packages are software libraries, i.e., pieces of source or compiled code that become a part of the execution of the main application (e.g., through source inclusion, or static/dynamic linking). While this approach can be used for developing an "atomic" microservice (a service that does not contain other services), it falls short of capturing the essence of the paradigm and how it is used.

There are two key aspects that we need to keep in mind when dealing with code reuse in microservices. First, a common pattern in service development is to resolve the dependency of a service simply by binding it to an externally-provided service (available somewhere else in the network), instead of importing code to be run locally. Second, if we do decide to import some code to be run locally, that code should still be run as a separate and independent "local" service. This way, if we need to change strategy later on (say, when we go from development to production) and switch from running a dependency locally to binding our service to an external provider, we can do it without changing our implementation.

Package managers for mainstream technologies were not built with MSAs in mind, so these two patterns are not natively supported. Microservice developers must instead typically resort to ad-hoc conventions to deal with these problems.

In this paper, we report on the development of a package management system for the Jolie programming language [START_REF] Montesi | Service-oriented programming with Jolie[END_REF] 1 : the Jolie Package Manager (JPM). Jolie supports microservices natively, so it is a prime case study for the development of a package system for microservices that deals with the aforementioned aspects. We illustrate how JPM supports the configuration and use of service packages. Furthermore, JPM supports a notion of interface parametricity (polymorphism), which can be used to develop services whose behaviour is determined by the interfaces of the other services that they are bound to at deployment time. Parametricity is necessary because these interfaces are known only when packages are "linked" to each other (to solve dependencies).

A Simple Example

We briefly introduce Jolie with a small e-shop example. Listing 1.1 shows a simple Shop service. It has a single checkout operation, defined in Lines 11-13. The Shop has two dependencies: the PaymentProcessor and the Warehouse, given as output ports. An output port dictactes how we can invoke another service. The output port PaymentProcessor is defined in Lines 5-8. This includes a Location attribute, which defines where the service can be contacted, a Protocol attribute, which defines the transport protocol to be used, and a list of statically defined Interfaces, which types the API of the service.

The current practice to make Jolie services configurable is based on ad-hoc conventions. For example, we may include a file named config.iol that contains some constant definitions (representing configuration parameters). Listing 1.2 shows the configuration file for the PaymentProcessor.

Listing 1.2. config.iol: Configuration for the PaymentProcessor.

1 constants { 2 P A Y M E N T _ P R O C E S S O R _ T E S T _ M O D E = false , 3 P A Y M E N T _ P R O C E S S O R _ A C C O U N T _ I D = " xxxxx -xxxxx -xxxxx " , 4
PAY MENT _PROC ESSO R_LOC = " socket :// localhost : 443 " ,

5 P A Y M E N T _ P R O C E S S O R _ P R O T O C O L = " https " 6 } 2
Here we provide a few fields for the behaviour of the service (TEST_MODE and ACCOUNT_MODE) and configuration for the input port of the service (LOC and PROTOCOL).

The main problem of this approach is that this file needs to be included as source code by the service that we are configuring. This hides what the parameters mean (Are they bindings or not? What is the resulting architecture?). It also opens to security risks: since we are importing source code, an attacker may insert arbitrary malicious code in the configuration file and it would be executed.

Packages and the Package Manager

We introduce a package abstraction to the Jolie language and provide a tool that combines packages with configurations to achieve our aims from the Introduction, the Jolie Package Manager (JPM). A package is a folder containing Jolie source code. The code of a package is read-only when used as a dependency, to enable potential updates and integrity checks when packages are installed.

JPM distributes packages following a relatively standard approach. A package in a repository is equipped with a package manifest. A manifest contains information about the package, used for indexing (e.g., name, description, purpose, etc.) and package management (e.g., dependencies and version). We omit the details of manifests and how they are used to install packages from repositories, since these are similar to those in mainstream package managers. In the remainder, we focus on features that are peculiar to JPM.

Configuration

Jolie packages are configured by configuration profiles, which we introduce here. Crucially, profiles do not need to be included as source code by packages. They are instead given in separate deployment files (written by the user of the package) that are processed by the Jolie toolchain in a controlled way, when we need to run the services given inside of the package. The syntax of profiles recalls that of the Jolie constructs that can be configured. In Listing 1.3, we show an example of a configuration profile for the PaymentProcessor, which replaces the ad-hoc sourceincluded configuration file given in Listing 1.2. This snippet shows a single profile named "pp-production". A profile provides binding information (location, protocol) for communication ports and configuration values to a particular package. A user can provide different configuration profiles, e.g., one for development and one for production, and select among them at deployment time.

We require that the configurable elements of a Jolie program are marked with a new keyword, #ext. This allows the developer to omit binding information in communication ports; the omitted field need then to be provided externally by a configuration profile. We do not allow setting the Interfaces part of a port externally, since this would prevent type checking of programs until they know their deployment setup (typing how they use ports inside of their behaviours). Thus in the PaymentProcessor its input port is defined as: #ext inputPort PaymentProcessor { Interfaces:IPaymentProcessor }.

Embedded Dependencies

In Jolie, all components are services that run independently. Sometimes, for performance or convenience, it is useful to embed a service in the same local VM (Jolie is implemented in Java). Services in the same VM still exchange messages, but they can use efficient in-memory channels, as opposed to the network.

Our new package system allows us to embed pre-configured Jolie packages in two ways. These two ways give a system administrator the freedom to choose and apply the best deployment strategy without any changes required to the services. We start by looking at the externally configurable approach.

Figure 1 shows a development configuration for the Shop. In this configuration, we embed the PaymentProcessor and its dependencies inside the Shop. Listing 1.4 depicts the desired deployment. When we state that a service should be embedded, we simply pass the name of the configuration profile to be used. outputPort FakeCCProcessor embeds " fake -processor " 7 } 8 profile " fake -processor " configures " FakeCCProcessor " { ... }

Parametric Interfaces

Proxy services delegate the computation of replies for their requests to other services. A notable example is circuit breaker [START_REF] Michael | Release It!: Design and Deploy Production-Ready Software (Pragmatic Programmers)[END_REF]. We summarise this pattern in the following (see [START_REF] Montesi | Circuit breakers, discovery, and API gateways in microservices[END_REF] for a thorough discussion in Jolie).

Circuit breakers attempt to protect against some of the problems that occur when using remote calls, such as connection problems, timeouts, and critical faults. During normal operation, a CircuitBreaker functions like a normal proxy between a Client and a TargetService. Monitoring code inside of the CircuitBreaker attempts to detect problems. If enough problems are detected, the CircuitBreaker will start failing immediately without attempting to proxy the call. After a period of time it will start allowing some calls through, and eventually transition back to the normal state and allow all calls through.

Packaging proxy services like circuit breakers raises a particular problem. Intuitively, the proxy should only accept calls for operations that are declared in the interface of the target service. However, this interface is known only at deployment time, since we may want to reuse the same circuit breaker package to protect different services. Proxy services are thus inherently parametric on the interfaces of the target services that we choose at deployment time. To address this problem, we introduce the notion of configurable interface to Jolie.

Listing 1.5. cb.ol: An externally defined interface.

# ext interface ITarget

In Listing 1.5 we define an externally configurable interface. A concrete interface is bound to it at deployment time by reading the configuration, giving the service, in this case CircuitBreaker, the information needed to correctly proxy operations. Observe that since we want Jolie services to be type-checkable without knowing their configuration (since configuration may change in different deployment setups), this means that the behaviour of the service is necessarily defined as polymorphic, i.e., it cannot assume any specific operation in the configurable interfaces (this is obtained through aggregation in Jolie, see [START_REF] Montesi | Service-oriented programming with Jolie[END_REF]).

To create a circuit breaker running in a client, we would embed the circuit breaker locally and have it bound to our external payment processor, this is shown in Listing 1.6. We can just as easily create a circuit breaker that operates server-side (intercepting incoming calls), or as a proxy in the network, by adopting different deployment files for "cb-pp".

Related Work

A common approach to simulate bindings to external services in mainstream languages is to communicate with services via stub libraries. A stub library provides an interface that resembles that of the target service, and internally delegates all work to the latter. In web architectures, these libraries can be synthesised from specifications, for example using OpenAPI [1] specifications in tools like Swagger [START_REF]Swagger website[END_REF]. Our approach applies directly to web development through Jolie [START_REF] Montesi | Process-aware web programming with Jolie[END_REF].

Seneca [START_REF]Seneca official website[END_REF] is a microservice toolkit for Node.js, where business logic is enclosed in a plugin typically distributed as a Node.js module. By including these plugins as dependencies, a server can essentially embed the logic of these plugins, similarly to JPM. Seneca uses pattern matching to determine which service should handle a particular message. This makes the bindings of a Seneca service implicit, in contrast to JPM, where bindings are explicit. A similar mechanism may nevertheless be implemented in Jolie and JPM by adopting proxy services, cf. [START_REF] Dalla Preda | Interface-based service composition with aggregation[END_REF].

Listing 1. 3 . 4 Protocol : https } 5 P

 345 pp.col: Configuration for the PaymentProcessor in JPM. 1 profile " pp -production " configures " PaymentProcessor " { 2 inputPort PaymentProcessor { 3 Location : " socket :// localhost : 443 " A Y M E N T _ P R O C E S S O R _ T E S T _ M O D E = false 6 P A Y M E N T _ P R O C E S S O R _ A C C O U N T _ I D = " xxxxx -xxxxx -xxxxx " 7 }

Fig. 1 .

 1 Fig. 1. Desired deployment configuration for our development build. The dashed region represents services inside of the same VM.

Listing 1. 4 . 2 outputPort 5 inputPort

 425 Embedding services from a configuration. 1 profile " shop -development " configures " Shop " { PaymentProcessor embeds " pp -development " 3 } 4 profile " pp -development " configures " PaymentProcessor " { PaymentProcessor { Location : " local " } 6

Listing 1. 6 . 2 outputPort 5 interface 6 outputPort

 6256 cb.col: Shop configuration with client-side circuit breaker for PaymentProcessor.1 profile " shop -production " configures " Shop " { PaymentProcessor embeds " cb -pp " 3 } 4 profile " cb -pp " configures " CircuitBreaker " { ITarget = PaymentProcessIface from " PaymentProcessor " TargetSrv { ... } 7 }

http://www.jolie-lang.org/

Acknowledgments

This work was partially supported by CRC (Choreographies for Reliable and efficient Communication software), grant no. DFF-4005-00304 from the Danish Council for Independent Research, and by the Open Data Framework project at the University of Southern Denmark.


Nils Kopal

Matthäus Wander

Christopher Konze

Henner Heck

Adaptive Cheat Detection in Decentralized Volunteer Computing with Untrusted Nodes

In volunteer computing, participants donate computational resources in exchange for credit points. Cheat detection is necessary to prevent dishonest participants from receiving credit points, without actually providing these resources. We suggest a novel, scalable approach for cheat detection in decentralized volunteer computing systems using gossip communication. Each honest participant adapts its detection effort dynamically subject to the number of active participants, which we estimate based on observed system performance. This enables minimizing the detection overhead for each participant, while still achieving a high preselected detection rate for the overall system. Systems based on majority voting usually produce at least 100% overhead, whereas our approach, e.g. requires only 50.6% overhead in a network with 1 000 participants to achieve a 99.9% detection rate. Since our approach does not require trusted entities or an active cooperation between participants, it is robust even against colluding cheaters.

Introduction

Cheating is a well-known problem in distributed systems that rely on the computers of volunteers, i.e. volunteer computing systems [START_REF] Anderson | The computational and storage potential of volunteer computing[END_REF]. In such a system, the computers of volunteers are interconnected and build a large-scale distributed system for distributed computations. We call a complete distributed computation a job and a partial computation, typically performed by a single node, a subjob. Researchers often use volunteer computing in cases where there is no funding for sufficient computational resources within their research projects. Many volunteer computing projects have a charitable background, i.e. the search for cancer medicaments, AIDS research, water research, etc. We distinguish two different classes of volunteer computing: The first class is the classic volunteer computing, which is based on a client-server approach, e.g. the Berkeley Open Infrastructure for Network Computing [START_REF] Anderson | Boinc: A system for public-resource computing and storage[END_REF] (BOINC). Here, a server manages the distribution of all subjobs. The combination of the corresponding subjob results leads to the result of the overall job. Participating nodes in the volunteer computing network request subjobs from the central server and deliver results to the central server. Clearly, if the server fails, the complete job computation stops since no new subjobs are assigned to requesting nodes. Additionally, a server requires maintenance which results in costs that have to be taken into account by researchers. The second class is decentralized volunteer computing, e.g. [START_REF] Kopal | Self-organized volunteer computing[END_REF][START_REF] Wander | Towards peer-to-peer-based cryptanalysis[END_REF]. Here, no central server exists. The participating nodes have to self-organize distribution and assignment of subjobs and distribution and storage of results.

To offer incentives to participate in volunteer computing projects, i.e. motivate people to donate their computational resources, volunteer computing systems usually maintain lists of their participating users with respect to their computational work spent [START_REF] Anderson | Boinc: A system for public-resource computing and storage[END_REF]. People who donate resources typically aim to improve their position on such lists, causing them to provide more resources.

Besides well-behaving users, there also exist cheaters in volunteer computing systems. [START_REF] Anderson | High-performance task distribution for volunteer computing[END_REF] Such a cheater delivers false or only partial correct results to gain more credit points than they deserve. Correct results are essential for researchers, which requires a verification of results coming from untrusted and potentially unreliable volunteers. Otherwise, partly false results could impair the overall job result up to the point of invalidating the joint effort of hundreds or thousands of volunteers. There exist well-known anti-cheating techniques for client-server based volunteer computing [START_REF] Domingues | Sabotage-Tolerance and Trust Management in Desktop Grid Computing[END_REF]. These include redundant computation, majority voting, and sample testing, which are performed or initiated by the central and trusted server. In a decentralized network, there is no central authority that manages the distribution of subjobs. Thus, techniques like redundant computation and majority voting cannot be easily used.

In an untrusted, decentralized network, each node needs to devote a portion of their resources to detect and correct false results. As this reduces the overall speedup of computation, only a subset of results can be selected to be verified for efficiency reasons. Sample testing suffices to detect cheaters in search problem applications with close to 100% probability [START_REF] Wander | Detecting opportunistic cheaters in volunteer computing[END_REF].

In this paper, we present a method for cheat detection in untrusted, decentralized volunteer computing networks based on sample testing. The method works on top of a gossip-based communication. It is immune to colluding cheaters, because each node performs its cheat detection independent of each other. We show that to meet a given detection rate, the overall cheat detection effort per network can be kept constant. With an increasing size of the network, this allows us to reduce the cheat detection effort per node without negatively impairing the detection rate. We thus propose to adapt the cheat detection per node dynamically subject to the size of the network, which can be estimated by each node individually by evaluating the current network workload. In sum, the contribution is a cheat detection method that dynamically adapts the verification effort to the total number of participating nodes in untrusted volunteer computing networks without the need of any additional messages.

The rest of the paper is organized as follows: First, in Section 2 we present our system model for decentralized volunteer computing. Then, in Section 3 we present our application scenario. Here, we base our model on a distributed cryptanalysis scenario. Additionally, we present our cheater classes and our cheat detection algorithm. We also present our definition of effort for computations and cheat detection. After that, in Section 4 we present our idea for an adaptive cheat detection method. In our evaluation in Section 5 we simulate the effort for cheat detection of a single computing node with fixed detection rates and effort. After that, we evaluate, on the basis of single nodes, the effort a complete network has to perform for cheat detection with fixed detection rates and effort. After that, we present an evaluation of our adaptive method. Then, in Section 6 we briefly present the related work in the field of cheat detection and prevention. We conclude our paper in Section 7 with a brief outlook on future work.

System Model

In a decentralized volunteer computing system, the knowledge of the participants is distributed using messages. Each participant can send messages directly to a certain number of other participants, which are called neighbors. Nodes disseminate knowledge by sending messages to their neighbors, which copy and forward them to their neighbors. Since such an approach leads to a high number of message transmissions, the amount of data that needs to be exchanged during a job computation has to be kept small. The basis for our gossip-based distribution is a network consisting of nodes. Each node is connected to randomly chosen neighbors. Nodes transmit the results of their subjob computations and their state of the overall job to their direct neighbors. Our distribution algorithms compute an embarrassingly parallel search problem (search job) with a result using a problem specific computation function. Such a search job can be parallelized by dividing it into independent subjobs, where each subjob can be computed by the same computation function. To get the overall result of a job, the results from all subjobs can be combined using a combination function. Furthermore, we assume that the combination function is associative, commutative, and idempotent. We assume that the size of the combination of two results equals the size of a single result. Since the jobs in our example scenario consist of several thousands, millions, or more subjobs, it is not possible to disseminate the state of each subjob. We use distribution algorithms [START_REF] Kopal | Simulating cheated results acceptance rates for gossip-based volunteer computing[END_REF][START_REF] Kopal | Self-organized volunteer computing[END_REF][START_REF] Kopal | Simulating cheated results dissemination for volunteer computing[END_REF], which divide the total computation space into subspaces. These subspaces are chosen small enough so that it can be disseminated in total. Nodes work in parallel on the same subspace. A node randomly selects a subjob, computes it, and sends the results to their neighbors. These merge all received results and forward them to their neighbors. Once the nodes finished a subspace, they move on to the next subspace until the job is complete.

Application Scenario

Our application scenario is the keysearching of a modern symmetric cipher, i.e. distributed brute-forcing an AES128 [START_REF] Daemen | The design of Rijndael: AES-the advanced encryption standard[END_REF] encrypted text and searching for the decryption key. In our application scenario, we divide the complete search space (≈ 2 54 for passwords consisting of lowercase and uppercase characters, digits, and special characters) in subjobs, each consisting of 2 20 = 1 048 576 keys. To search through a single AES128 subjob, a node decrypts the given ciphertext using every key within the range of that subjob. The goal of the cryptanalysis is to find the correct decryption key. To rate the keys, a node uses the Shannon entropy [START_REF] Shannon | Prediction and entropy of printed english[END_REF] function H as a cost function. With natural language, i.e. the original plaintext, the entropy value is mostly at its minimum with respect to all decryption keys. After performing all decryptions, a node generates a toplist of the k "best" keys of a subjob. Those keys are the ones that decrypt the given ciphertext to the plaintexts with the lowest entropy. Each node does this for different subjobs. After finishing a subjob, the nodes send their results to their neighbors. They combine the toplist of each received subjob result to create a global toplist over all subjobs.

In our scenario, a cheater would not test all keys of an AES128 subjob. The cheater has the motivation to earn credit points to achieve a high rank in a volunteer computing network without doing all of the required work, while avoiding the detection by the system's countermeasures [START_REF] Anderson | Boinc: A system for public-resource computing and storage[END_REF]. Thus, a cheater, in general, may compute only parts of a given subjob and only delivers partially (correct) results. The more of a subjob a cheater computes, the harder it is for a cheat detection algorithm to detect this cheater. This is based on the fact that the more results of a subjob are computed correctly, the less results are missing that could be detected. We refer to a cheater that only computes parts of a subjob as an opportunistic cheater. Opposed to that, a disturber submits garbage results just for the sake of vandalism. Disturbers can be easily detected with the same means as opportunists. Colluding cheaters coordinate their efforts to persist cheated subjob results in the network. In some systems, colluding cheaters have an advantage over solitary opportunistic cheaters, but this does not apply to our approach.

BOINC-based solutions use multiple computations of subjobs by different nodes and make a majority decision on the correct result. In [START_REF] Wander | Detecting opportunistic cheaters in volunteer computing[END_REF], we developed an approach for the detection of cheated results within a distributed computing scenario introduced by an opportunistic cheater. The detection is based on two different approaches: Positive verification and negative verification. With positive verification, we verify the correctness of a subjob computation and with negative verification, we try to find other (better) results, which the delivering node omitted. If either positive verification fails or negative verification succeeds, we found a cheated result and we decline it. For positive verification, we assume that we can check the results in very short times. Clearly, this is true for an AES128 subjob since the decryption using all of the keys of the subjob toplist can be done very quickly.

To compare our decentralized cheat detection mechanisms and methods with the state-of-the-art solutions (client-server-based, i.e. BOINC) we need to estimate the effort that is needed for the computations and additionally the cheat detection mechanisms. First, we define the effort for a single subjob computation as E subjob = 1. Furthermore, the effort to compute i subjobs is E node (i) = i • E subjob = i , which is i times the amount of effort needed for a single subjob. This is possible, since every subjob is, with respect to the needed computations, identical.

We define E Detect (P Detect ) as the effort needed for the computation of a detection algorithm with the detection rate P Detect . For example, an effort equal to 0.5 means, that half of the subjob has to be recomputed to perform the cheat detection. Clearly, the effort function depends on the problem that is being computed by our volunteer computing network. Thus, the computation of E Detect can not be generalized. In Section 5, we present an evaluation for the effort that is needed for the detection of cheated subjob results in a cryptanalysis scenario, i.e. keysearching for the key of a symmetric encryption algorithm.

Approach

In our approach, every node performs independently a partial cheat detection on every subjob result disseminated in the volunteer computing network. The approach needs no additional messages for executing the cheat detection. It is completely based on the assumption that every honest node provides its small part of cheat detection effort. This cheat detection effort is subject to a given fixed destination detection rate P DetectN etwork and the current workload of the network, to which our approach dynamically adapts to. We measure the workload in units of virtual nodes, which is a standard amount of processing power provided by a node. However, our approach is able to cope with heterogenous nodes providing more or less workload than a virtual node. Each node performs the following steps in our cheat detection approach for each newly received subjob result:

1. Determine the number of virtual nodes n V irtual currently connected to the network with the method introduced below. 2. Compute the amount of virtual nodes r that the node represents itself. 3. Based on the amount n V irtual compute target detection rate P Detect of node. 4. Perform cheat detection with the computed node detection rate P Detect on each newly received subjob result with effort E Detect .

Determine Workload of Network

We now present a method to infer the workload of a node and of the whole volunteer computing network, which is necessary to determine the effort for cheat detection required. Each node administrates a list L T imef rame of finished subjob results within a sliding time window T imef rame. The list L T imef rame contains the received amount of subjob results of the node, the node's neighbors and all of their neighbors, which follows from the gossip-based dissemination of job results. The node divides the amount of subjob results #(L T imef rame ) by the timeframe time T imef rame to obtain the current workload W N etwork of the network, i.e.

W N etwork = #(L T imef rame ) T imef rame . (1)
To estimate the amount of nodes n V irtual , we divide the workload W N etwork of the network by a constant virtual node workload W V irtualN ode , i.e.

n V irtual = W N etwork W V irtualN ode . (2)
Although we cannot compute the actual number of nodes or their workload, this virtual number of nodes suffices for our purposes. We assume that cheaters not only skip on result computation but also omit participation in the cheat detection process, since they have no benefit in doing so. We thus have to compensate for this amount by reducing the estimated workload by the amount of cheaters C CheaterRate that the system should be resistant against. Setting e.g. C CheaterRate = 0.05, our approach achieves the target detection rate P DetectN etwork in a network with at most 5% of all claimed results to be cheated. If the actual amount of cheaters exceeds C CheaterRate , the cheat detection still works but achieves a detection rate less than the anticipated P DetectN etwork . The compensated amount of virtual nodes is thus

n V irtual = W N etwork W V irtualN ode • (1 -C CheaterRate ). (3)
Each node now determines the number of virtual nodes r it represents with its own workload. It does so by dividing its current workload

W N ode by W V irtualN ode , i.e. r = W N ode W V irtualN ode . (4)

Perform Cheat Detection

Now that the node knows its computing power relative to the network's computing power, it computes the amount of effort it has to contribute so that the network reaches its target detection rate. Thus, it first computes the detection rate which a single virtual node has to add, i.e.

P DetectV irtualN ode = 1 -n V irtual 1 -P DetectN etwork . (5)
After that, the node computes its node target detection rate based on that with the equation

P Detect = 1 -(1 -P DetectV irtualN ode ) r . (6)
We combine the two equations to the following final single equation for the target node detection rate

P Detect = 1 -(1 -P DetectN etwork ) r n V irtual . (7)
Based on this computed local detection rate P Detect , a node computes the verification effort E(P Detect ) that it has to process, i.e. the amount that needs to be recomputed of each newly seen subjob result. This effort is also based on the type of cheater T Cheater , the network has to be resistant again. A T Cheater = 0.5 means, that the cheater only computes 50% of given subjobs. This target type of cheater is set by the user of our adaptive method. In our evaluation we empirically determine the function E(P Detect , T Cheacter ) for the 50% cheater. In other scenarios, this effort has to be either computed, if possible, or empirically determined by the user.

Evaluation

In this section, we first present our idea of two distinguished cheat detection classes: Static and adaptive. After that, we present the simulation of the effort of a single node in the static class. Then, we use the results of that simulation to evaluate the effort of a complete network based on the static class. After that, we present our method to let each node adapt its cheat detection rate and the needed mode effort with respect to the amount of nodes in the network. Doing so, we show how we keep the detection rate as well as the node effort constant.

Detection Classes

We differentiate cheat detection in two different classes: The static class, and the adaptive class. In the static class, a network or the nodes of the network perform cheat detection with a static, i.e. fixed, detection rate P Detect . Thus, a node performing cheat detection on a received result has the probability of P Detect to detect, if the result is not correct, i.e. cheated. In the next section we show, that this static detection class does not scale in a decentralized network since the increasing effort E N etwork for detection reduces the speedup to an upper limit. With the adaptive class the nodes of a network adapt their detection rates P Detect and effort E Detect according to the amount of nodes within the network. We furthermore use the simulation result of a single node to estimate the correlation between effort and detection rate in the adaptive class.

Cheat Detection in the Static Class for a Single Node

We base our simulation on the AES128 scenario presented in the last sections.

In our simulation, we let the simulator search for the 10 "best" AES128 keys in a cryptanalysis job. Thus, a simulated cheater that only searched through 50% of the keys of a subjob would only find 5 of these keys on average. Then, to simulate the detection of the cheater, a real node would first positively verify the best list, i.e. check the entropy-values of each entry. Clearly, all the entropy values within our simulation best list are correct, thus, we omitted this step in the simulation. After that, a node would randomly try to find "better" values, i.e. keys with lower entropy values. For that, we used different amounts of detection effort ranging from 0.0001% to 100%. We simulated the cheat detection performed by a single node with different cheaters with respect to the cheated amounts of computations. A cheater omits between 10% and 90% of all keys of a subjob computation. It selects the keys, for which it actually does computations randomly. The cheat detection node randomly selects a dedicated amount of AES keys out of the subjob space to find lower entropy values, i.e. doing negative verification. In Figure 1 we show the results of our simulations. For each point in the graph, we did 10 000 simulations and calculated the average value over all simulation runs. The graph shows different amounts of cheated values starting from 90% (black line) going down to 10% (purple line). A cheater with 90% means that the cheater omitted 90% of the computations. In our graph, it can be seen that with higher amounts of negative verifications, i.e. the node effort (abscissa), the detection probability, i.e. the detection rate (ordinate), also increases. With an effort value E Detect > 7% our node would detect nearly every cheated subjob. Clearly, 7% of effort, i.e. recomputation of 7% of each subjob, is way too high for a real-world usage. But since not only one node performs cheat detection, but also all n nodes do, we can decrease the effort and detection probability at every node as shown in the next sections.

Cheat Detection Effort in the Static Class of a Complete Network

If only exactly one node would perform a single detection run on each subjob, in the previous section we evaluated that we need a recomputation of nearly 7% (random selections) out of every subjob in the best case to perform cheat detection as seen as black line (90%) in Figure 1. Here, the maximum value is reached at nearly 7%. For determining the real effort of a decentralized network, we evaluated three different scenarios (A, B, and C) with different static detection probabilities P Detect (from high to low) and corresponding node efforts E N ode . We show the different detection probabilities and effort rates in Table 1.

We extracted these values out of our simulations, as shown in Section 5.2. The basis for our computations is a volunteer computing job that consists of j = 2 32 different subjobs. First, we computed the effort E Client-Server that a client-server solution, for example BOINC, would need for the cheat detection:

E Client-Server = 2 • E N ode (j) (8) = 2 • E N ode (2 32 ) (9) = 2 33 ( 10
)
This amount of computations has to be performed in total by all the clientnodes in a client-server based volunteer computing network. Clearly, the value is independent from the amount of nodes, since the distribution of subjobs to the nodes is done by the server. We then computed the amounts for our three different scenarios with variable numbers of nodes. We show the result of these computations in the Figure 2. For comparison with the client-server case, we computed the quotient Q of the client-server case effort (numerator ) and the decentralized cases (denominator ) effort. A quotient of 1 means, that the network's effort is the same as the client-server's effort. For example, the effort

E Decentralized = E N ode (j) + (n • E Detect (j)) (11) = 2 32 + (700 • 0.001271895 • 2 32 ) (12)
= 8 118 891 612.85 [START_REF] Shannon | Prediction and entropy of printed english[END_REF] We now calculate the quotient Q of the client-server case E Client-Server and the scenario A case:

Q = E Decentralized E Client-Server = 0.944691034 ≈ 94, 45% (14)
Thus, a decentralized network (with parameters as in case A) needs 94, 45% of the computations that a client-server network needs. Then, we computed the corresponding detection rate P DetectN etwork of such a network. To compute that detection rate, we used the detection rate of a single node P Detect :

P DetectN etwork = 1 -(1 -P Detect ) n (15) = 1 -(1 -0, 0122) 700 (16)
= 0.999814512 ≈ 99.98%

With scenario A the detection rate is nearly 100% -only one out of 1 000 cheated subjobs would remain undetected on average in a network. Clearly, in a real volunteer computing scenario, we assume that there would never be a thousand cheated results disseminated in the network. By increasing the effort of a single node the detection probability of the network can also be increased. We also show the different detection rates of our scenarios in Figure 3. Finally, we computed the speedup S of our scenarios. The speedup of a distributed system is the amount of parallel computed subjobs. If a network consists of n nodes the speedup is optimal if n different subjobs are processed in parallel. We computed the speedup S with the following equation

S = E N ode (j) E Decentralized • n (18)
where j is the total amount of subjobs, E Decentralized is the total effort of the decentralized network, and n is the amount of nodes in the network. We depicted the speedup graphs of our scenarios with different amounts of nodes in Figure 4. As a result of our evaluation it can be seen that with increasing the amount of nodes but keeping a constant effort E N ode for cheat detection at every node, the speedup is restricted to an upper bound. For scenario A this upper bound is ≈ 340, for B this upper bound is ≈ 1 750, and for C this upper bound is ≈ 4 750. Additionally, we added the optimal speedup (green line) to the graph. Here, the speedup S is equal to the amount of nodes n. Speedup values higher than these bounds cannot be reached with constant E Detect values.

Our Adaptive Method

In this section, we present the evaluation which we performed with a simulator that implements the static and the adaptive cheat detection. In this evaluation we combine the adaptive method presented in section 4 with the estimation of node amount of section 4.1 needed for the adaptive method to create a prototype. The simulation time is represented in 'ticks'. A simulated subjob is 'computed' by a node waiting a defined amount of ticks, i.e. 'subjob duration'.

The simulated network is defined by the amount of nodes and their neighbors, the computational power of the nodes, cheater rates, cheat detection rates, cheat detection effort, etc. For cheaters and their corresponding detection effort E Detect , we used the T Cheater = 0.5 cheater, i.e. a 50%-cheaters, as shown in Figure 1. We extracted the detection rate and effort values and created a mapping function for our simulator.

With our simulations we show that our adaptive method outperforms the static cheat detection with respect to the effort needed by the nodes for performing the cheat detection. Furthermore, our simulations show that the static class does not scale with increasing amount of peers. Additionally, we show that the adaptive method needs less effort for cheat detection than a BOINC-based system needs.

We simulated different networks with sizes between 100 and 1 000 nodes, each node having 5 neighbors. Our simulator performed a simulation of a distributed job comprising of 320 000 subjobs. For the static cheat detection class, we set the detection rate of a single node P DetectN ode to 5%, which results in an estimated P DetectN etwork of 99.4% for 100 nodes. We set the amount of cheaters in each network to 5% who cheat with 5% of their subjobs. Thus, 0.3% ≈ 800 of all subjobs disseminated within the simulation network were cheated on average. Furthermore, we set the virtual node workload for our algorithm to 0.2, thus, a virtual node finishes 0.2 subjobs in each simulation iteration. The real simulated nodes finished a subjob in 5 simulation ticks. We set the window of our algorithm to 10 ticks.

We present the results of our effort simulations in Figure 6. With the static approach, the effort increases proportionally to the number of nodes (red, dashed line). This is caused by the fact that each node performs cheat detection on every subjob result distributed in the network. The adaptive algorithm (blue, solid line) adapts dynamically to the amount of nodes in the network, keeping the effort at a rate around 162 000. This is about 50.6% of the overall amount of computed subjobs. A BOINC-based system (black line) would compute each subjob at least twice to enable majority voting, resulting in a minimum of 100% additional effort for the cheat detection. Directly compared to BOINC the quotient Q is Q = E OurM ethod E Client-Server 162 000+320 000 320,000+320,000 = 0.753125. I.e. our system needs ≈ 75% effort compared to a client-server system with majority voting needs, i.e BOINC.

In Figure 7 we depicted the cheat detection rates of the static and the adaptive methods. Additionally, we computed the detection rate of BOINC with colluding cheaters. BOINC achieves 99.7%, because there is a chance that BOINC gives the same sub job to two colliding cheaters, which results in an overlooked cheated sub job result despite redundant computation. The static method (red, dashed line) keeps a detection rate of 100%, but as already shown does not scale with respect to the effort. The adaptive method (blue, solid line) reaches a detection rate between 99.8% and 100%. The target detection rate was 99.9%, which is reached on average. Collusion among cheaters does not affect the detection rate, because each subjob result will be checked for correctness by each honest node, unlike e.g. with majority voting.

We finally present a comparison of the achieved speedup S of the static class, the adaptive class, and BOINC. We computed the speedup as shown in Section 5.3. In Figure 8 we show that the adaptive method performs best keeping the speedup at the highest rate (blue line). Close to this, we see BOINC (black line). We furthermore see, that the static class reaches a speedup limit close to 210 which confirms that the static method does not scale.

Related Work

Prior work has considered cheat detection and cheat prevention in distributed computing, which includes volunteer computing. There are attempts to secure volunteer computing and grid computing by introducing mechanisms to either validate the correctness of results received from participants or by making it hard or impossible to cheat on given jobs. In [START_REF] Golle | Uncheatable Distributed Computations[END_REF], Golle and Mironov describe their idea of uncheatable distributed computations. They show two different security schemes, a weak and a strong one, that defend against cheating participants. The weak one depends on 'magic numbers' and the strong one depends on a supervisor and so called 'ringers'. Both schemes have in common that participants have to find either these magic numbers or the ringers to get rewarded for their done work. The main difference between their solution and ours is the organization of the computations. They use the supervisor who assigns subjobs to nodes. In our scenario, we have no central management since our network is completely unstructured and decentralized. Moca et al. present in [START_REF] Moca | Distributed Results Checking for MapReduce in Volunteer Computing[END_REF] a method for distributed results checking for 'MapReduce' [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF] in volunteer computing. They use a distributed result checker based on majority voting. Furthermore, they developed a model for the error rate of 'MapReduce'. Compared to our solution, which only needs recomputation of very small parts of subjobs, their method is based on majority voting. Thus, their nodes have to redundantly compute complete subjobs. Hence, the total amount of recomputations is at minimum 2 to apply majority voting on their results. In this paper, we show that our method needs considerably less recomputations compared to their method. Zhao and Lo show their scheme 'Quiz' in [START_REF] Zhao | Result Verification and Trust-Based Scheduling in Peer-to-Peer Grids[END_REF], which inserts indistinguishable quiz tasks with verifiable results to a distributed job. They outperform the method of the replication of jobs in terms of accuracy and overhead under collusion assumptions. Compared to our solution, they need a central server that assigns the quiz tasks as well as the regular tasks to the clients. With our solution, we do not need a central server since every node in the network performs a small part of detection work. Sarmenta presents in [START_REF] Sarmenta | Sabotage-Tolerance Mechanisms for Volunteer Computing Systems[END_REF] his sabotage-tolerant mechanisms for volunteer computing. He shows a method called 'credibility-based fault-tolerance' where he estimates the conditional probability of (sub/job)-results and workers being correct, based on the results of voting, spot-checking and other techniques, and then he uses these probability estimates to direct the use of further redundancy. Compared to our solution, they use a work pool-based master-worker model where the master assigns subjobs to workers. Here, the master randomly assigns redundant subjobs to workers. Compared to majority voting based techniques, their method reduces the total amount of recomputations, but also increases the chance of non-detected cheated subjob results. Our method also reduces the needed amount of recomputation but still keeps a very high detection probability with small network and node effort.

Conclusions

We introduced a cheat detection method for decentralized, gossip-based volunteer computing networks. The method is suitable for ad-hoc computations without setting up a central server. Nodes do not need to trust each other, which makes the method robust against colluding cheaters or cheaters who decide to abuse their acquired reputation. We are targeting opportunistic cheaters, which are attempting to collect the same reward as well-behaving users, e.g. credit points. However, cheaters provide job results that are incorrect and incomplete.

The method works by sample testing each job result that is disseminated in the network. With a static cheat detection effort per node, the scalability is limited as the system approaches an upper bound on the speedup with an increasing number of participating nodes. We thus adapt the cheat detection effort subject to the workload of the network, which is determined by each node based on the number of results disseminated in the network. This allows us to achieve a given target detection rate efficiently, e.g. 99.9% with only about 50.6% recomputations of subjobs. As we have shown with our simulations, such a decentralized sample testing is more efficient than a server-coordinated majority voting like e.g. being used by BOINC. In future work, we will analyze how cheat detection results can be used to exclude cheaters from our system and reduce the detection effort by doing so. Furthermore, we will examine how such a node exclusion can be used by attackers to remove well-behaved nodes.

  05 0,1 0,15 0,2 0,25 0,3 0,35 0,4 0,45

Fig. 4 .

 4 Fig. 4. Speedup S

Fig. 5 .Fig. 6 .Fig. 7 .Fig. 8 .

 5678 Fig. 5. Cheat Detection Effort of a Single Simulated Node -50% Cheater Type

Table 1 .

 1 Different Scenarios -Detection Probability and Effort of a single Node

	Scenario Detection Probability PDetect Effort E N ode
	A (high)	1.22%	≈ 0.1271895%
	B (medium)	0.46%	≈ 0.0490371%
	C (low)	0.06%	≈ 0.0129130%


Alexander Jahl
email: jahl@vs.uni-kassel.de

Huu Harun Baraki
email: baraki@vs.uni-kassel.de

Tam Tran
email: tran@vs.uni-kassel.de

Ramaprasad Kuppili
email: rkuppili@vs.uni-kassel.de

Kurt Geihs
email: geihs@vs.uni-kassel.de

Lifting Low-Level Workflow Changes through User-Defined Graph-Rule-Based Patterns

Keywords: Graph Transformation, Graph Matching, Pattern Matching, Change Impact Analysis, Dependency Graph, Web Services, Service Evolution, Answer Set Programming

In dynamic service-oriented architectures, services and service compositions underlie constant evolution that may not only affect the own workflow but dependent services too. Subsequently, required adaptations necessitate an effective detection of the changes and their effects. Merely capturing a sequence of low-level changes and analyzing each of them demands much coordination and may lead to an incomplete picture. An abstraction that summarizes a combination of low-level changes will facilitate the detection and reduce the number of changes that shall be considered for adaptation. In this paper, we propose an abstraction that is formulated through graph-based patterns, since service compositions are workflows that can be mapped to directed labeled graphs. The characteristics and granularity of a graph pattern can be adjusted by domain experts to the respective workflow language and application case. In particular, graph-based patterns are crucial when workflows are represented in two different formats. This could be the case if there exists one representation for the execution and one for the verification. We present implementation details and a detailed example that shows the feasibility and simplicity of our solution.

Introduction

It is common wisdom that actively used software must be evolved continuously in order to maintain its utility and quality [START_REF] Lehman | Programs, life cycles, and laws of software evolution[END_REF]. Adding new features, removing obsolete features, fixing bugs, closing security holes, improving performance all require updating a software product from time to time. Certainly, this is also true for services provided via a computer network. However, services seldom work in isolation in a stand-alone fashion. They may be part of business processes where services depend on other services and may be composed of other services.

These manifold interdependencies make on-the-fly service evolution a particularly difficult and challenging problem because the evolution of one service may incur changes in other dependent services and clients. In analogy to biology, we call this service co-evolution. Our goal is to provide a general solution for coordinated decentralized service co-evolution. Such a solution is lacking. For heavily used services in business-critical application scenarios upgrade-related downtime is not acceptable in most cases, but often the reality. Hence, on-the-fly, zero downtime service co-evolution is a major objective for our research. This demands, first and foremost, an examination of the effects and consequences of each alteration in a formalized way. Current formal specification methods for Change Impact Analysis (CIA) apply logic programs, state machines, and semantic annotations. In [START_REF] Dai | Lightweight query-based analysis of workflow process dependencies[END_REF] compositions are formulated in Prolog. This enables developers to perform consistency checks through atomic Prolog queries. Ryu et al. [START_REF] Ryu | Supporting the dynamic evolution of web service protocols in service-oriented architectures[END_REF] map protocols of service compositions to finite state machines. After a change occurs, the protocol compatibility of the participating services will be tested to decide about a migration to the updated protocol version. Likewise, other works in this area also focus on updates which encompass a single removal or addition of a service or parameter, check the consistency after the update or inform affected parties [START_REF] Alam | Impact analysis and change propagation in service-oriented enterprises: A systematic review[END_REF]. However, the consideration of single update steps impedes detecting and processing complex changes like replacements, swaps, or the addition of new branches and subgraphs to the workflow. These changes are still treated as a sequence of low-level updates. Lifting a sequence of low-level changes to a complex change captures additional information that would be lost otherwise. By lifting we refer to the conversion of low-level changes to a more abstract, conceptional description of model modifications. A sequence of removals and additions of services at the same position would not be interpreted as a replacement. The detection of a complex change would allow triggering tailored actions for handling and checking them. In case of a replacement, the pre-and post-conditions of the replaced and the replacing service could be checked for compliance.

This work provides a practical solution for developers to define complex change patterns by means of a simply applicable graphical approach. The change patterns are formulated in terms of hierarchically organized graph rules. This enables identifying and categorizing changes with different granularities. Hence, nested rules are feasible that trigger actions for each level of the hierarchy, e.g. log removal and insertion and verify replacement. Just considering detected higher level changes, e.g. the replacement, would lead to a comprehensive view that compacts dealing with changes. Further applications, which will not be discussed in this work, include the storage and the communication and dissemination of changes in a flexible and dense format.

In this paper, we present our change pattern definition and detection approach. Both are implemented by means of our DiCORE: CIA (Distributed Cooperative Evolution: Change Impact Analysis) module. Additionally, we extend this module by an Answer-Set-Programming-based logic programming reasoner to verify the updated model and to draw conclusions about dependent components. Throughout the paper, a comprehensive example is used consistently to illustrate the course of action and demonstrate the practicability of our solution.

The remainder of this paper is organized as follows. Section II introduces our graph-rule-based change patterns and justifies the need for them. Thereafter, Section III presents the architecture and functionality of our first DiCORE:CIA prototype. Related work is discussed in Section IV. Finally, the main findings of this paper and future work are summarized in Section V.

Graph-rule-based Patterns

We will start with the illustration of a service workflow that is changed and extended by the responsible service provider. With the aid of this running example, the subsequent sections demonstrate the definition and viability of our graph-rule-based patterns (GPs).

Scenario

The workflow depicted in Fig. 1 is an orchestration that can be executed on a client or service provider machine. Workflows usually encompass different types of nodes which are commonly termed activities. An activity may be the invocation of a local or remote service and may also encompass user interaction. Workflow WF1 includes one remote service invocation. The getMap function of service S1 is requested. The other operations are executed locally. choosePOI and getGPScoord enable a user to select a Point of Interest and acquire its GPS coordinates. These are processed remotely by service S1 that returns a detailed map of the corresponding area. The following activities create a suitable route plan (pedestrian, car, public transport, bicycle) and display it accordingly. Now let us assume that a workflow update provides a more precise localization and an additional map type is offered. This new workflow WF2 is shown in the lower part of Fig. 1. Additionally, service S1 is replaced by service S2. The pollution map in workflow WF2 allows users to choose routes with low emission levels. Note that the workflows WF1 and WF2 in Fig. 1 are represented by a directed graph. This restricts the search area for the following graph matching approach significantly, increases its accuracy and reduces its faults. Nevertheless, it should be pointed out here that our GPs are applicable for undirected graphs, too.

Graph Comparison and Reduction

Before explaining GPs and their application in detail, our graph comparison and reduction approach is presented. The graph comparison matches nodes of two subsequent versions of a workflow to detect atomic changes, more precisely, it generates a list of added and removed nodes. The graph reduction is required to consider the addition or removal of subgraphs as the addition or removal of one node. This enables, for instance, that the replacement of a node by a subgraph is detected correctly.

Graph Comparison Subgraph matching is the challenge to find all matches of a query graph. This task is known to be an NP-complete problem. A comparison between two graphs G 1 and G 2 , where:

-G = (N, E), -N is a set of nodes, -E is a set of edges,
consists in the determination of a mapping M that associates nodes of G 1 with nodes of G 2 in compliance with some predefined constraints. The mapping M is represented by a set of pairs (m ∈ G 1 , n ∈ G 2 ), each pair representing the mapping of a node m from G 1 with a node n from G 2 . A mapping M ⊂ N 1 × N 2 is an isomorphism if M is a bijective function that preserves the branch structure of the two graphs. For comparing the two versions of a graph, we compute the minimal graph edit distance [START_REF] Fischer | Approximation of graph edit distance based on Hausdorff matching[END_REF] between them by using an A* algorithm and calculating the string edit distance (syntactical analysis) [START_REF] Lu | Efficiently Supporting Edit Distance Based String Similarity Search Using B+ -Trees[END_REF] for a structural matching of each corresponding graph node pair. Additionally, a semantic analysis [START_REF] Gomaa | A survey of text similarity approaches[END_REF] calculates a degree of similarity based on the equivalence between the words they consist of.

In our graph comparison algorithm depicted in Algo. 1, this functionality is implemented by the searchEquivalent function listed in line 2. The algorithm starts with a start node N of the source graph and returns by use of searchEquivalent the best match as equivalentN. The match precision is obtained through an invocation of getPercentFor. The matching and its similarity assessment are stored into M as a triple. The compare function is invoked recursively for neighbour nodes found through direct edges (line 7). Finally, M contains the best matches between node n ∈ N 1 of a source graph G 1 and node m ∈ N 2 of the target graph G 2 . Matches whose similarities fall below a threshold, will be discarded in a subsequent step. Applying the graph comparison method to our scenario in Fig. 1 results in a pairwise mapping of corresponding nodes of the source and the target graph. The outcome of the comparison depicted in Fig. reveals that not all nodes have compliant counterparts. These nodes are marked Green when added and Red when removed (Fig. 3). The graph matching and the marked nodes form the starting points for the application of our change patterns.

Graph Reduction Preparatory steps that summarize the addition or removal of directly connected nodes will improve the scalability of our graph matching by reducing the search space. Besides that, the definition and application of GPs will be simplified. For instance, a developer may create a replacement GP by means of a removed and inserted node at the same position. A single node that is replaced by a subgraph would be identified by this GP because the insertion of the subgraph is reduced by our approach to an insertion of one single node. The two middle columns in Fig. 4 illustrate this amalgamation. Contracted nodes and their connections will be saved as subgraphs that are analyzed in subsequent steps.

A subgraph H is defined as a subset of vertices and edges of a graph G = (N, E), with H = (N H , E H , µ, ν, L µ , L ν ) where:

-

N H ⊆ N , -E H = E ∩ (N H × N H ), -µ function matching label l ∈ L µ to node n ∈ N H , -ν function matching label l ∈ L ν to edge e ∈ E H , -L µ = L ν = {x|x = green} ⊕ {x|x = red}.

Graph-rule-based Patterns

Our GPs are formulated by the usage of graph rules that are organized hierarchically and which enable identifying changes with different granularities. The GP notation is based on the graph rule syntax of [START_REF] Grunske | Using graph transformation for practical model-driven software engineering[END_REF][START_REF] Ehrig | Graph Transformations[END_REF].

Graph Rules (GRs) are undirected labeled graphs defined as a 6-tuple R = (N, E, µ, ν, L µ , L ν ) where:

-N is a set of nodes, -E is a set of edges, µ function matching label l ∈ L µ to node n ∈ N , ν function matching label l ∈ L ν to edge e ∈ E, -L µ is a set of symbolic labels to mark nodes.

-L ν is a set of symbolic labels to mark edges.

In general, graph rules can be used to transform a graph from one domain to another. Therefore, they connect corresponding nodes and edges and mark new and deleted components. In our case, the source and target domain of our GRs GRs are formulated through a graphical representation. Fig. 5 presents an example set of GRs and their interdependencies. GR1 stands for the insertion of a single node. Further information is gained, if, for instance, subsequently GR2 and GR3 can be matched. This represents the replacement of a direct connection between a node A and C by a node B and its connections to A and C. The application of this GR set to our example scenario is illustrated in Fig. 6. After the execution of the aforementioned graph matching (Figures 2, 3 and4), GR1 is detected in the first step. This can be interpreted programmatically as an added node. In the second step, further GRs reachable from GR1 are tried to be matched. Here, GR2 is fired which indicates an insertion between two existing nodes. Finally, GR3 identifies that these two existing nodes were directly connected before and, hence, the direct connection was replaced. Fig. 7 and Fig. 8 demonstrate the described procedure or the other two identified nodes.

The colors in these GRs are part of the syntax. In our case, L µ and L ν have the same set of labels. We define L µ and L ν as follows: They indicate which elements are added, removed or remained unchanged. Elements marked Black are used to find corresponding elements in both graphs. Hence, they serve as context. Green elements were added in the target graph and do not exist in the source graph at the same position. Red elements exist in the source graph but do not exist at that position in the target graph. In the depicted examples, node names refer to the corresponding functionality, that is, same names stand for the same functionality type.

GR-based Change Patterns

GPs can be considered as a combination of GRs. A GP may stand for a specific statement. For instance, GR1 to GR3 are subsumed as an Insert GP. Formally, a GP is a directed graph that contains GRs as nodes:

-P = (N R , E) -N R is a set of R, -E is a set of edges, formulated as E ⊆ N R × N R .
GPs can build on one another so that more details and information are captured. Linking GPs means to share related GRs. Fig. 9 demonstrates this by connecting the Insert GP and Remove GP with the Replace GP. Coming back to our scenario, let us assume that a developer or user replaced an existing node D by a new node B. In Fig. 9, node B represents a subgraph. Initially, GR1 and GR4 match the added and removed nodes. These are included in the Insert GP and Remove GP. Subsequently, GR2 and GR5 identify the context nodes. GR3 will not be activated in this case since there was no direct connection between node A and C beforehand. The Replace GP is confirmed only if both GR2 and GR5 fire with the same context nodes A and C. The bidirectional arrows in the Replace GP indicate that it cannot be valid if merely one GR matches. Starting with simple rules, developers can extend them by adding GRs and GPs in a hierarchical manner to detect more complex changes. This allows, inter alia, the recognition of patterns like swaps, parallelizations and other domain specific structures. The hierarchical GRs shown in Figure 9 specify the search path for each change pattern. Starting at node GR1 or GR4, the algorithm presented in Algo. 2 checks after a successful matching if one of the following rules can be applied. In our example, that would be GR2 or GR5. If a GR matches, all relevant information like context nodes or added or removed edges are set at that point. Following GRs will use the same context information. Our match checking ap- plies exact subgraph isomorphism to resolve this kind of pattern matching. Any successful executed graph rule provides new and additional informations.

Answer Set Programming follows the Declarative Programming paradigm and has its roots in logic programming, non-monotonic reasoning, and databases. It is used for planning and diagnosis of NP-hard search problems. ASP provides the possibility of simple ASP code generation in a readable format and reasoning about temporal and structural dependencies in a workflow. A detailed explanation can be found in [START_REF] Gelfond | Knowledge representation, reasoning, and the design of intelligent agents: The answer-set programming approach[END_REF].

Our framework translates process graphs to ASP in order to verify locally the workflow after changes are performed. If a consistency violation is detected, the change is discarded and the developer is notified. If changes affect the in-or output of a workflow, they may affect clients using this workflow. Since in-and outputs of workflows are formulated in ASP too, they serve as change description for these affected clients. Our DiCORE framework is also running on client side. This allows us to receive and process ASP fragments and check for consistency on the client side. Consistency violations will cause a service replacement so that pre-and post-conditions of each activity on client side are fulfilled. Fig. 10 shows the transition diagram of a workflow including two Web service invocations. Transition diagrams can be directly translated to ASP [START_REF] Gelfond | Knowledge representation, reasoning, and the design of intelligent agents: The answer-set programming approach[END_REF]. The ASP translation of the transition diagram is given in List. 1.1. $?%+8)% +$2$@$6% ,8%8 Workflow Graph Fig. 10. Process Graph to ASP

The translation to ASP is only executed for the original workflow. Whenever changes occur in the workflow graph, they will be detected, condensed and mapped to GPs. Each GP holds a corresponding translation in ASP which is generated automatically during the GP creation phase. This ensures that ASP descriptions can be updated instead of being generated anew.

Assuming that S2 and S3 are inserted into an existing workflow, our Graph Reduction would summarize this event as an insertion of a subgraph. This simplification step is also reflected automatically in ASP (List. 1.2). It results in a shortened ASP description which reduces the search space for valid models. Eventually, the subgraph can be resolved into its original composition. 3 DiCORE:CIA

The DiCORE framework determines the kind of changes and the affected components in a business process and communicates them with dependent clients. DiCORE:CIA detects functional changes by analyzing the structure of the workflow. This module is implemented as a Java library and is part of our DiCORE framework. In combination with our ASP component (based on clingo [START_REF] Gebser | Theory solving made easy with Clingo 5[END_REF]), it supports the developer conveniently through assistance for recognizing changes and their consequences. Furthermore, a graphical editor for visualizing, customizing and extending the GPs to particular requirements is provided. The following sections present an overview of the DiCORE:CIA module architecture and explain the main features. The ASP Analyzer contains three components: (1) ASP Converter, (2) ASP Query Generator, (3) ASP Updater. The process graph serves as input for the ASP Converter which generates the ASP description needed for further analytical steps. The ASP Query Generator executes consistency checks through automatically created queries and identifies after performed changes affected nodes inside the process graph.

Related work

Workflows are always prone to different kinds of changes, such as new regulatory laws, changes in policies or strategies, or emerging technologies. Therefore, detecting, logging and notifying about functional changes in processes is a critical step in change analysis. This section will present a brief review of research work dealing with the detection and handling of functional changes.

For detecting functional changes, various works applied comparisons between processes to extract different kind of information. These, however, do not provide tools to developers to define their own patterns or change types, but consider a fixed set of possible atomic changes.

Aamas et. al [START_REF] Armas-Cervantes | Bp-diff: A tool for behavioral comparison of business process models[END_REF] propose the Bp-diff tool for a comparison of business models. The Bp-Diff tool may identify discrepancies involving pairs of tasks and provides both textual and visual feedback to help users understand each discrepancy. The textual feedback explains how a given pair of tasks is related in the given model versions. The visual feedback allows users to pinpoint the exact state where the discrepancy occurs. Similarly, Sergey et al. [START_REF] Ivanov | BPMNDiffViz: A Tool for BPMN Models Comparison[END_REF] present their tool BPMNDiffViz which compares process models represented in BPMN. The authors provide a web-based tool that finds business process discrepancies and visualizes them. However, this tool is applied only for BPMN formats and only considers atomic changes.

Further alternative approaches are based on predefined sets of change patterns. The authors in [START_REF] Weber | Change patterns and change support features-enhancing flexibility in process-aware information systems[END_REF] suggest a set of change patterns like the addition and removal of process fragments or moving or replacing fragments. Our approach encompasses these patterns and is additionally editable and extendable through our GPs.

Conclusions

This paper presents a new contribution for formulating and detecting userdefined change patterns in complex service graphs. The patterns can be structured hierarchically and allow a categorization of changes. The hierarchic structure enables to capture additional information with each GP that could be matched to a change. Furthermore, our solution allows an intuitive and graphical formulation of patterns while other existing tools completely ignore user-defined change patterns. Our DiCORE framework presents a first implementation of the GPs. It communicates workflow changes with affected parties and triggers adaptations in case of inconsistencies. Therefore, we employ logic programming by automatically generated ASP descriptions that are processed by an ASP solver. GPs are not restricted to this application scenario but can be applied in general for detection, compression, logging and communication of simple and complex changes in a graph-based description expressed as interconnected graph rules.

In a future work, a special multi-agent system shall communicate the changes and coordinate possible adaptations with affected parties. Therefore we extend our DiCORE framework and continue to promote this research area.

Fig. 1 .

 1 Fig. 1. Scenario: original workflow WF1 and revision WF2

3

 3

Algorithm 1 : 5 M

 15 Subgraph comparison 1 function compare (N, G); Input : N , start node from source graph; G, target graph Output: M , mapping result 2 equivalentN = searchEquivalent(N, G); 3 percent = getPercentFor(N, G); 4 if equivalentN then .put (N, equivalentN, percent); 6 foreach edge in N.edges do 7 nodes = edge.nodes; 8 foreach node in nodes do 9 if node != N then 10 M.putall(compare (node, G)); 11 end 12 end 13 end 14 end 15 return M ;

Fig. 2 .Fig. 3 .

 23 Fig. 2. Matching of Source graph G1 nodes and the corresponding target graph G2 nodes Fig. 3. Graph matching with marked added and deleted nodes

Fig. 4 .

 4 Fig. 4. Identify subgraph of new added nodes and contract to one node

Fig. 5 .

 5 Fig. 5. Example set of graph rules to detect low-and high-level changes

Fig. 6 .

 6 Fig. 6. Example of the application of successive and interrelated graph rules to detect the kind of change as precisely as possible

Fig. 7 .Fig. 8 .

 78 Fig. 7. Detection added node (step 1), identification neighbour nodes (step 2) Fig. 8. Detection removed node (step 1), identification neighbour nodes (step 2)

Fig. 9 .

 9 Fig. 9. GR-based change patterns Insert, Remove and Replace

Algorithm 2 :

 2 GP graph matching 1 function findMatching (G, R); Input : G, graph with included change marker; R, current rule from GP Output: A, map of all matched rules and connected G nodes 2 match = checkMatch(G, R); 3 if match then 4 A.put(R, match); 5 foreach childR in R.children do 6 A.put( findMatching(G, childR) );

  #$%&$*78. (3. #$% '*225%/*678.

Listing 1 . 1 . 4 5

 114 ASP translation 1 fluent ( inertial , type ) 2 fluent ( inertial , geo ) 3 fluent ( inertial , pol ) action ( getGeoMap ) 6 action ( g et Po ll u ti on M ap )

3. 1

 1 Architecture overviewDiCORE:CIA includes the following four packages: (1) Process Graph Converter, (2) Graph Matching, (3) Graph UI, (4) ASP Analyzer.The Process Graph Converter uses a data model, imported from one of the well-known workflow languages, e.g. UML, BPMN, BPEL, YAWL, or EPC, to generate a process graph, based on the process graph syntax in[START_REF] Bouchaala | Dat: Dependency analysis tool for service based business processes[END_REF].The Graph Matching package consists of three main components: (1) Graph Comparator, (2) Graph Reduction, (3) Pattern Matching. The Graph Comparator matches two versions of a process graph and extracts the differences. The Graph Reduction component contracts the outputs of the Graph Comparator. Finally, the Pattern Matching component applies the GR graph to match GPs.

Fig. 11 .

 11 Fig.11. ASP Viewer[START_REF] Opfer | Reasoning for Autonomous Agents in Dynamic Domains[END_REF]

Acknowledgment

This work is supported by the German Research Foundation (DFG) under the project PROSECCO, grant number 5534111. The authors would like to thank the DFG for supporting their participation in worldwide research networks.