Henner Heck

Olga Kieselmann

Nils Kopal

Arno Wacker

A Decentralized Resilient Short-term Cache for Messaging

Keywords: Overlay Networks, Storage Resilience, Censorship Resilience

Messaging applications are among the most popular internet applications and people use them worldwide on a daily basis. Their supporting infrastructure, though consisting of a multitude of servers, is typically under central control. This enables censorship and seamless user profiling. A fully decentralized infrastructure, with decentralized control and redundant data storage, can mitigate these dangers. In this paper we evaluate the basic ability of decentralized networks created by the network overlay and data storage protocol Kademlia to serve as a short-term data cache for messaging applications. Our results show, that reliable retrieval of up to 20 replicas is possible.

Introduction

Millions of people use messaging applications on a daily basis to exchange, e.g., text messages or pictures. Popular examples are WhatsApp, Snapchat, or Telegram. While technically a distributed system taking a multi-server or cloud approach, the infrastructure supporting these messaging applications is typically under central control. This implies several security and privacy issues, e.g., eavesdropping, data manipulation, profiling, or censorship. While some of these issues can be mitigated by end-to-end encryption and other measures, the danger of censorship is inherent to such a system. To prevent censorship, data storage and data transmission need to happen redundantly with multiple independent responsible parties. For this purpose we evaluate redundant 24 hour short term data storage and retrieval in a network organized by the distributed hash table and overlay network Kademlia. Our results show how resilient such a network is against censorship by evaluating how many data replicas need to be suppressed in order to prevent successful data retrieval.

The remainder of this paper is organized as follows: First, we discuss related work in Section 2 and briefly describe the Kademlia protocol in Section 3. We then present our assumptions in Section 4. In Section 5 we present our protocol modifications necessary for determining the storage resilience and introduce our evaluation terminology. Based on this, we present and discuss the results of our storage resilience measurements in Section 6. We conclude our paper in Section 7 with a brief summary and provide an outlook on future research.

Related Work

Kademlia and overlay networks in general have been studied extensively in the scientific literature. A survey about research on robust peer-to-peer networks from 2006 [START_REF] Risson | Survey of research towards robust peer-to-peer networks: search methods[END_REF] already lists several hundred references. Another survey from 2011 reaches close to a hundred references [START_REF] Urdaneta | A Survey of DHT Security Techniques[END_REF]. Despite the large amount of publications in general, the actual feasibility for redundant storage and retrieval in Kademlia has not been thoroughly evaluated. We limit our discussion of related work to existing distributed messaging systems and to literature with relevance for redundant storage and retrieval in Kademlia.

The fully distributed messenger Freenet [START_REF] Clarke | Freenet: A distributed anonymous information storage and retrieval system[END_REF] has the goal of providing censorshipresilient communication and publishing. At its core it uses a "small world" overlay network. Roos et al. [START_REF] Roos | Measuring freenet in the wild: Censorship-resilience under observation[END_REF] took measurements in a real world Freenet network. They found it suboptimal for routing and experienced long delays and low success rates for data retrieval. For Kademlia-type networks the number of nodes to contact for a successful data retrieval grows only logarithmically with the network size n [START_REF] Roos | Determining the hop count in kademlia-type systems[END_REF]. For sufficiently random node identifiers Cai et al. [START_REF] Cai | The analysis of kademlia for random ids[END_REF] proved an upper bound of O(c • log n), with c being a constant factor.

Ji-Yi et al. [START_REF] Ji-Yi | Study on redundant strategies in peer to peer cloud storage systems[END_REF] describe a p2p cloud storage system named MingCloud. They experimentally evaluate a theoretical value called system availability, ranging from 0 to 1, in connection with full copy redundancy and erasure code. The authors describe MingCloud as based on the Kademlia Algorithm, but the focus of the paper is on a comparison the full copy approach with erasure codes. Beyond the system availability, no other properties are evaluated. Fedotova et al. [START_REF] Fedotova | Kademlia for data storage and retrieval in enterprise networks[END_REF] examine Kademlia for data storage and retrieval in enterprise networks. However, their focus is the implementation of different privileges for data access, not on evaluating redundant retrieval. Park et al. [START_REF] Park | A novel hybrid p2p and cloud storage system for retrievability and privacy enhancement[END_REF] propose a p2p based cloud storage system for redundant storage and retrieval. Their focus is on reducing the required data traffic as well as preserving data privacy. They compare an encoding scheme named Fountain code to other approaches like erasure coding. While their system is p2p based, it does not use the Kademlia protocol. The Bittorrent software Vuze [START_REF] Inc | Vuze wiki[END_REF] uses a modified version of Kademlia for data storage and retrieval. To handle possibly malicious nodes, Vuze requests a value from 20 nodes during a value lookup. While this modification of the Kademlia protocol is very similar to ours, there is no further data presented on the storage resilience resulting from this approach.

Kademlia

With the Kademlia overlay network, resources (nodes and values) are identified by a numerical id with the fixed bit-length b. Each node maintains a routing table containing identifiers of other nodes, its contacts. The routing table consists of b so-called k-buckets, indexed from 0 to b -1. Each of the k-buckets can hold at most k contacts. The decision which contacts to store in a bucket depends on the node id, the bucket index, and the contact id. The distance between two identifiers is computed using the XOR metric, meaning that for two identifiers id a and id b the distance is dist(id a , id b ) = id a ⊕ id b , interpreted as an integer value. A bucket with index i is populated with those contacts id i fulfilling the condition 2 i ≤ dist(id , id i ) < 2 i+1 . The bucket with the highest index covers half of the id space, the next lower bucket a quarter of the id space, and so on. Another property of Kademlia is the request parallelism α, which is the number of contacts queried in parallel when a node tries to locate another node or a data object for a given id. The staleness limit s determines how many times in a row communication with a contact must fail, so that it is considered stale and removed from the routing table. The Kademlia authors set the default values b = 160, k = 20, α = 3, and s = 5.

Furthermore, nodes can perform the following four remote procedure calls (RPCs): Ping probes a node to check whether it is online. Store instructs a node to store an id -value pair. Find node looks up the k nodes closest to a given target id. A node selects the α contacts closest to the id from its routing table and sends a request to each of them. These nodes respond with their own list of closest contacts, which can then be used for further queries. This way, the requesting node iteratively gets closer to the target identifier. The RPC terminates when a number of k nodes have been successfully contacted, or no more progress can be made. Find value retrieves the value for a given target id. It has almost the same behavior and termination conditions as find node. The difference is, that nodes can answer by sending the requested value instead of a list of closest nodes. When this happens, find node terminates immediately.

To publish an id -value pair a node first performs the find node RPC to get a list of k successfully contacted nodes. It then sends a replica of the id -value pair to each of them via the store RPC.

Kademlia uses three different republishing mechanisms. Their purpose is to prevent id -value pairs from becoming unavailable and to store them at nodes with ids close to the id of a value. With the first republishing mechanism nodes periodically republish their stored id -value pairs every 60 minutes. This can lead to a significant amount of traffic. Also, whenever a node has only just republished an id -value pair, additional republications are unnecessary. Therefore, as an optimization, a node does not republish id -value pairs it was asked to store itself within the previous 60 minutes. The second mechanism is an opportunistic one. Whenever a node carries out the Find value RPC successfully, it often has to contact several nodes before finding one that returns the value. After getting the value, the node performs a Store RPC. Out of the previously contacted nodes not returning the value, it sends the id -value pair to the one closest to the value id. The third mechanism is also opportunistic. Whenever a node learns of another node not present in its routing table, it might send id -value pairs from its own storage to that node. The decision which pairs to send is based on the number of known nodes with ids placing them between the new node and an id -value pair.

System Model

Our system consists of a number of networked nodes connected by the Kademlia overlay network. Communication is message based and takes place directly between two nodes. The underlying network allows communication between any two nodes. Kademlia not only defines an overlay network structure, but also provides the functionality of a distributed hash table (DHT). Therefore, the nodes in our system can store data values at other nodes of the network (put operation) and retrieve values from them (get operation).

We distinguish between storing and non-storing nodes. We expect storing nodes to be servers provided by volunteers, a concept successfully realized with, e.g., the relay servers of the Tor network [START_REF] Dingledine | Tor: The second-generation onion router[END_REF]. Non-storing nodes are PCs, tablets, mobile phones, or other end devices people use for messaging. A functional and well behaved storing node stores a received id -value replica unmodified in its local storage. Furthermore, when asked for a value contained in the local storage, the node will include an unmodified id -value replica in its answer.

A network of storing nodes is at the core of the messaging system. We expect these nodes have a session length, i.e. a continuous participation in the network, of several hours or more at a time. For the non-storing nodes the session length is less relevant, but we assume that they connect to the network at least once every 24 hours. Given that many devices have a continuous connection to the internet, this does not seen unreasonable.

We further assume that an attacker exists with the goal of censoring data and preventing its retrieval from the core network. The strength of the attacker is measured by the number of id -value replicas it can successfully suppress on average per retrieval request.

Redundant Storage and Retrieval

As described in Section 3, a publishing node initially stores replicas of an idvalue pair at up to k disjunct nodes that were selected using find node. This is the put operation. The number of replicas stored during a single put operation is the replica storage count (RSC).

The original find value RPC of Kademlia terminates immediately when a node returns a replica of the requested value. However, for redundant retrieval, we need multiple replicas returned by disjunct nodes. To achieve this with Kademlia, we modified the responses and termination conditions for find value. During the value lookup a node responds not with either a contact list or a value replica, but, whenever possible, with both of them. The lookup no longer terminates on receiving the first value replica, but collects as many replicas as possible, until up to k disjunct nodes have responded. These changes potentially give us up to k value replicas returned by k disjunct nodes.

In terms of censorship we must consider the worst case in which a replica is suppressed right at the initial put operation. Suppressing a replica at that point also suppress all its subsequent replicas created by Kademlia's republishing mechanisms. We, therefore, can only consider replicas that are unique with regard to the initially stored RSC replicas. Hence, two or more replicas derived from the same initial replica, are considered a single unique replica. We call the retrieval of replicas for an id the get operation. The number of retrieved unique replicas is the unique replica return count (RRC uniq ). Since the RRC uniq is limited by the RSC and, therefore, by k, we introduce the term unique replica return ratio (RRR uniq ) to denote the ratio between the maximum stored replicas upon a put and the returned unique replicas. We define it as RRR uniq = RRCuniq k

. Accordingly, an RRR uniq of 100% corresponds to retrieving k unique replicas with a get operation.

Evaluation

In the following, we evaluate the put and get operations in a simulated Kademlia network acting as a core network of storing nodes as described in the system model in Section 4. Specifically, we evaluate on how many nodes a value is stored at upon a single put operation and how many unique replicas of this value we can retrieve afterwards with a get operation. We first describe the evaluation environment and the simulation scenarios. Then, we present our results and discuss them.

Environment and Parameters

For our simulations, we use the Java-based network simulation software PeerSim [START_REF] Montresor | Peersim: A scalable p2p simulator[END_REF]. We extended the partial Kademlia implementation from the PeerSim website [START_REF] Montresor | Peersim: A peer-to-peer simulator[END_REF] to implement the full Kademlia protocol. Additionally we wrote software components to provide functionality for network churn and data storage and retrieval.

We proceed from the fact that different parameters may affect the storage resilience in Kademlia.

Kademlia Bucket Size: The bucket size k defines how many nodes should store a value upon a put operation. Moreover, it determines how many nodes are requested for a value upon a get operation. We evaluate the implication of this parameter by setting it to different values. In our simulations, we use the values 10 to 50 in steps of five.

Network Size: We consider two differently sized networks, i.e., one with 2500 nodes and one with 5000 nodes.

Network Churn: We consider three churn scenarios, where the same number of nodes join and leave the network each minute, keeping the network at roughly the same size. The numbers are selected so that in the simulated 24 hours the number of joins/leaves are either one, two, or four times the network size. We call these low, medium, and high churn. For a network of size 2500 the means a join/leave rate of 2/2, 4/4, and 7/7, resulting in an average participation for a node of 500, 380, and 270 minutes. For a network of size 5000 the means a join/leave rate of 4/4, 7/7, and 14/14, resulting in an average participation for a node of 500, 400, and 270 minutes.

Data Traffic: For nodes to fill and update their routing tables, each node performs 10 get operations with random ids per minute throughout the whole simulation. Additionally, Kademlia requires each node to perform a so-called "bucket-refresh" every 60 minutes for maintenance purposes. For this, a node randomly generates an id from the id range of each k-bucket and performs find node RPCs for these ids.

Simulation Phases:

The initial bootstrap procedure to create the network is performed randomly in terms of time and bootstrap node selection. A new node joins the network at a random point in the simulated time that is evenly distributed between 0 and 30 minutes. The bootstrap node is randomly chosen from the nodes already present in the network. Therefore, in all simulations the network is fully setup after 30 minutes (setup phase). From minute 30 to minute 60 (stabilization phase), we allow the network to stabilize. After that, starting at minute 60, we apply churn (churn phase). The churn phase lasts 25 hours.

Measurements

During the first half hour of the churn phase we carry out 1000 put operations. We select the exact point in time, the value id, and the node performing the put operation, randomly. Each put operation is followed by get operations for the same id and with randomly selected node. These get operations take place 1 minute, 5 minutes, 30 minutes, and 1 hour after their respective put operation, and then every hour until 24 hours have passed.

For each put operation we log the replica storage count RSC. For each get operation we log the unique replica return count (RRC uniq ) and the necessary effort Eff, which is the total number of requests sent during the operation.

Our evaluation is based on three simulation runs for each parameter set. We initialized the simulator's random number generator with a different seed for each run. This results in a different network setup, different value ids, and different nodes carrying out the put and get operations, while keeping the parameter set identical. Hence, our evaluation is based on 3000 put operations and 27•3000 get operations for each combination of network size, churn, and k value.

Results

We first present the results for the replica storage count RSC. After that we show the results for unique replica recovery rate RRR uniq . We conclude our results by presenting the values of k necessary for achieving a required unique replica recovery count RRC uniq and, thereby, the number of replicas an attacker would have to suppress for successful censorship.

Replica Storage Count

For almost all put operations in all simulations the RSC was equal to its maximum value of k. Few exceptions occured due to the circumstance, that the store RPCs of a put operation take place only after the find node RPC has finished. Finding a node and storing a replica on it is not atomic. A node selected for storage might leave the network just before receiving a store RPC, reducing the RSC by one. Still, this rarely happened and the RSC reached k in the vast majority of cases despite the churn. Therefore, we assume RSC = k from here on.

Unique Replica Retrieval Rate In the evaluation of the RRR uniq only the worst retrieval result for each id -valuepair is considered. The first step is the selection of the get operation with the smallest unique replica retrieval count RRC uniq (out of 27 over a range 24 hours) for each of the 3000 put operation. We then calculate the arithmetic mean of the resulting 3000 RRC uniq values and divide it by k to get the average unique replica retrieval ratio RRR uniq Ẇe further compute the arithmetic mean of the effort Eff taken in a get operation, based on all 27•3000 get operations of a parameter set. The Figures 1 and2 show the mean RRR uniq and Ef f over k for different churn in networks of with 2500 and 5000 nodes. In total, the graphs for both network sizes look very similar, matching previous results on the scalability of Kademlia [START_REF] Heck | Evaluating connection resilience for selforganized cyber-physical systems[END_REF][START_REF] Heck | Evaluating Connection Resilience for the Overlay Network Kademlia[END_REF] indicating that Kademlia also scales well with the network size in terms of data storage and retrieval. For both network sizes the retrieval effort Ef f grows with k, which is to be expected, since k determines the number of replicas to retrieve. the effort also scales with the degree of churn. The higher the churn, the more likely it is that a node's routing table contains nodes which have already left the network. Therefore, the probability of sending requests without getting an answer, and in turn the retrieval effort, increases.

Against our expectations, the unique replica retrieval rate is not close to a flat line, but slightly increases with k in each churn scenario. For k = 10 it is at or slightly below 40% and grows by about 6% towards k = 50. Hence, an increase in k gives an increase in the unique replica retrieval count RRC uniq that is beyond linear, while the effort for retrieval is linear.

Among the churn scenarios we see that, as expected, higher churn hurts the retrieval rate. This is due to a greater loss of nodes with data on them and greater influx of nodes that initially have no data. Still, the decrease in retrieval rate is only at about 5%.

Sufficient k Besides evaluating the mean RSC and RRR uniq for different parameter sets, we also determined lower bounds for k that can provide a specific RRC uniq with very high probability. The unique replica return count RRC uniq is a decisive value for resilience against censorship. The more unique replicas one is likely to retrieve, the more replicas need to be suppressed by an attacker.

Fig. 1 .

 1 Fig. 1. RRRunique and Eff , Size 2500, 3 churn scenarios

Fig. 2 .

 2 Fig. 2. RRRunique and Eff , Size 5000, 3 churn scenarios

Acknowledgment

We thank the German Research Foundation (DFG) for their support within the project CYPHOC (WA 2828/1-1).

We, therefore, determined the values of k that are sufficient to reach a specific RRC uniq with a preset probability. We call these values k suf . The RRC uniq values in Figures 3 and4 were achieved by 100% of all get operations for each respective parameter set. This means that, within our simulations, these are guaranteed values. If, e.g., the requirement is to have an RRC uniq of at least 11 for all get operations in the network with 5000 nodes and with high churn (Figure 4), a k value of 40 is sufficient. For a required RRC uniq of 12 the sufficient value of k in the same scenario is 45. These jumps in value, visible as stairway effect in the graphs, exist due to the steps of 5 between the k values in our simulations. Therefore, our k suf between those k values might even be a bit more conservative than absolutely necessary. The RRC uniq values in Figures 5 and6 were achieved by 90% of all get operations for each respective parameter set. With the lower 90% requirement, as shown in Figure 6, the sufficient k for achieving an RRC uniq of 11 and 12 drops to 35 for both values. Also, the RRC uniq achievable with the maximum k of 50 increases from 16 to 20.

It is noticeable that with the 100% requirement, the values for k suf in the different churn scenarios, though distinguishable, are very close to each other and often overlap. With the 90% requirement overlap is almost the norm, and in Figure 5 the k suf for medium churn at the RRC uniq value 15 is even slightly higher than the k suf for high churn. Based on this, we conclude that the diffe- rence in RRC uniq for the different churn scenarios is based in only about 10% of get operations performing significantly worse with the higher churn.

In conclusion of the evaluation, highly redundant short-term data storage and retrieval with Kademlia is possible for our network scenarios. Scaling the network's storage resilience with the parameter k allows for strong assurances regarding lower resilience bounds even with churn.

Conclusion & Future Work

In this paper, we analyzed the storage resilience of the overlay network and distributed hash table Kademlia. For this we performed and evaluated a large number of simulations with different Kademlia parameters and network characteristics. We evaluated the actual redundancy of storage operations, the number of retrievable unique data replicas and as well as the retrieval effort. Beyond that we calculated lower bounds of the parameter k for achieving specific numbers of unique data replicas and, thereby, a minimum number of replicas an attacker needs to suppress for successful censorship.

In future research we will further test the storage resilience with different churn types proposed in Roos2015 [START_REF] Roos | Integrating churn into the formal analysis of routing algorithms[END_REF] and perform further simulations with additional values for k.


Tetiana Yarygina
email: tetiana.yarygina@uib.nochristian.otterstad@uib.no

Christian Otterstad

A Game of Microservices: Automated Intrusion Response

Keywords: adaptive security, self-protection, game theory, defense-in-depth, SOA, IPS, IDS, minimax

The microservice architecture is a subtype of distributed systems that has been attracting a lot of interest both in the industry and academia. Emerging research recognizes the need for a better understanding of microservice security, and, in particular, mechanisms that enable defence-in-depth and adaptive security. With the continuously growing number of possible attacks and defenses, the choice in the optimal defense strategy becomes non-trivial as well as time critical. We propose a cost-sensitive adaptable intrusion response system for microservices, which uses a game theoretic approach to automatically respond to network attacks in real time. Furthermore, we discuss both the applicable attacks and defense responses specific to microservices.

Introduction

Microservice architecture is gaining significant attention both by practitioners and in academia [START_REF] Pautasso | Microservices in practice: Reality check and service design[END_REF][START_REF] Newman | Building Microservices[END_REF]. Microservices allow for building flexible systems where the components can be written in different programming languages, use different technologies, scale independently, and can be easily updated and redeployed. Many microservice architectural principles such as modularity, loose coupling, and fail-fast are not new and stem from fundamentals of distributed systems [START_REF] Tanenbaum | Distributed Systems: Principles and Paradigms[END_REF]. Microservices are a particular implementation approach to Service-Oriented Architecture (SOA) [START_REF] Zimmermann | Microservices tenets: Agile approach to service development and deployment[END_REF]. However, the scale of microservice adoption is unprecedented and can perhaps be compared with the invention of object-oriented programming (OOP).

A key aspect of microservices is automation. With hundreds or thousands of microservices, manual updates are infeasible. Centralized logging, performance monitoring, service discovery are examples of such automation that are ubiquitously adopted. Such trends as contentious integration, DevOps culture, and need for high scalability and flexibility further increase the importance of automation in microservice networks. Yet, not all the areas of microservice operation are automated.

Self-protection and other self-* properties, such as self-configuration and selfoptimization that allow software systems to adapt to the changes in the environment, are actively researched areas [START_REF] Yuan | A systematic survey of self-protecting software systems[END_REF]. However, the problem of self-protection for microservices has received scant attention in the research literature.

Regarding microservice security, Fetzer [START_REF] Fetzer | Building critical applications using microservices[END_REF] discussed deployment of microservices inside secure containers to build critical systems. Sun et al. [START_REF] Sun | Security-as-a-service for microservices-based cloud applications[END_REF] proposed a virtual network monitoring solution that enforces policies over the network traffic in the cloud. Otterstad & Yarygina [START_REF] Otterstad | Low-level exploitation mitigation by diverse microservices[END_REF] pointed out the isolation benefits of microservices, as well as proposed the use of N-version programming for a simplified IDS. Yarygina & Bagge [START_REF] Yarygina | Overcoming security challenges in microservice architectures[END_REF] have investigated automation of secure inter-service communication and defense-in-depth principle for microservices.

Intrusion detection systems (IDSs) provide system administrators with information on malicious activity in the system. While intrusion prevention systems (IPSs) attempt to block intrusions that are detected, the handling of complex situations and choice of intrusion responses are often left to humans. Once an intrusion is detected, actions should be taken as fast as possible to stop an attack.

According to Stakhanova et al. [START_REF] Stakhanova | A taxonomy of intrusion response systems[END_REF], an ideal intrusion response system (IRS) should be automatic, proactive, adaptable, and cost-sensitive. One of the possible ways of achieving such an IRS is through security games. Game theory [START_REF] Osborne | A Course in Game Theory[END_REF] studies mathematical models of how multiple agents act when optimizing their payoffs. While the conventional game theory has a variety of applications in economics, political science, biology, it also received significant attention in the area of network security [START_REF] Roy | A survey of game theory as applied to network security[END_REF][START_REF] Zonouz | RRE: A game-theoretic intrusion response and recovery engine[END_REF][START_REF] Noureddine | A game-theoretic approach to respond to attacker lateral movement[END_REF].

There is a general lack of research in IRS for microservices. With the continuously growing number of possible attacks and defenses, the choice of the best defense strategy is complicated. A game theoretic approach potentially solves this problem. Our main contribution in this paper is the design of a cost-sensitive automatic IRS for microservices with game-theoretic foundation; we also elaborate on the response actions specific to microservice architecture.

This paper is organized as follows. Section 2 explains the game theory fundamentals and defines the game model used in this paper. In Section 3, the architecture of the proposed IRS is presented. Section 4 evaluates the proposed architecture. Section 5 concludes the paper.

Security Games: Assumptions and Solutions

We observe that the microservice architecture readily allows for employing game theory derived algorithms. This is a foundation for the system ability to respond to intrusions. This paper models the strategic interaction between an attacker and a defender as a finite dynamic zero-sum game. Different game theoretic solution concepts exist [START_REF] Osborne | A Course in Game Theory[END_REF].

Finite Dynamic Two-player Zero-sum Game

Most security games involve two counteracting parties-an attacker and a defender. While attacker's goal is to exploit the system, a defender is trying to protect the system, its resources, and data. Each player has a set of actions available to them at given time. Each action has a positive or negative reward associated with it. In the case of attacker and defender, each player's gain or loss is balanced by the losses or gains of the other player, which makes this game zero-sum. A compromised microservice node has a negative score for the defender, but a positive score for the attacker.

The attacker and defender take actions and receive rewards in turns, as seen in Figure 1. In this way, the game moves from one security state to the other. Games with more than one stage are called dynamic or extensive.

There is a limited number of states a given system can be in. Some of the states are the final states, i.e. the leaf nodes on the game graph. The security states where the attacker gains full control of the system can be seen as final states. In such case, the game is called finite.

Minimax

The goal for the defender is to choose the optimal response action in the given context. A common solution to this problem is the minimax algorithm. The minimax strategy for a defender is a strategy that minimizes the maximum payoff of an attacker, i.e. maximizes the benefit of a defender. For two-player finite zero-sum games, the minimax solution is the same as the Nash equilibrium.

In a two-player game, the minimax strategy for a defender i against an attacker -i is arg min ai∈Ai max a-i∈A-i u d (a i , a -i ), where a i is the response action taken by defender, a -i denotes the attack action taken by adversary, and u d is the utility function of defender.

Completely analyzing certain games using solely the minimax algorithm is impractical. The minimax algorithm traverses the nodes of a game tree. The number of nodes on the tree increases exponentially with the number of turns that can lead to a combinatorial explosion. The performance of the minimax algorithm can be improved using alpha-beta pruning or other pruning methods. Building on this game theoretic foundation, we propose a microservice intrusion response system. The system is cost-sensitive, in that the game allows us to chose the most effective, least costly response to an attack, rather than applying drastic measures in every situation.

The system consists of a distributed set of local monitoring processes and a central entity called the Microservice Game Engine (µGE), as depicted in Figure 2. The purpose of the system is to minimize the damage caused by an attack in real time. The µGE allows the microservice network to dynamically react to threats while taking action costs into consideration. In particular, the µGE exploits the fact that a partially compromised microservice network has not yielded total control to the attacker. A strong separation of the control flow and increased isolation are inherent benefits of microservice architectures [START_REF] Otterstad | Low-level exploitation mitigation by diverse microservices[END_REF][START_REF] Yarygina | Overcoming security challenges in microservice architectures[END_REF].

The µGE aggregates information, builds a game tree and takes automated action based on the observed input obtained from the local IDSes running on the respective microservices. In order to facilitate these actions, the µGE relies on several key components discussed below.

Network Mapping

The ability to maintain an accurate view of the microservice network at all times is a prerequisite for the µGE to respond effectively to malicious activity. The initial microservice network can be mapped in several ways. For example, each microservice can report its incoming and outgoing edges to the µGE.

After the network has been initially built by the µGE, it is ready to start playing the game in anticipation of attacks. However, when the real network changes, its representation inside the µGE should also be updated, and all computation performed thus far will be discarded. Nodes are inserted and removed from the tree as they report to the µGE.

Game Engine Topology

Deploy action µService logic Detection alerts IDS Fig. 2: An overview of the proposed architecture. The detection code in each microservice reports to the game engine, which evaluates the current state of the system and plans a response to any ongoing attack. Responses are deployed by e.g., restarting or reinstalling services, or other response actions.

Intrusion Detection and Events Reporting

Intrusion detection functionality resides in each microservice, informing the µGE of events of interest. Multiple sources of IDS information, as well as non-IDS information may be used. An IDS such as Snort [START_REF]Snort official web-site[END_REF] can detect among other things stealth port scans, operating system fingerprinting, and buffer overflows. Non-IDS information include events in the network, such as a service having stopped sending heartbeats, service registration and deregistration.

Attack actions in the game can be defined through the intrusion detection function. The set of possible attack actions is limited to the knowledge base of the particular IDS in place.

Event Evaluation Function

The evaluation function takes as its argument a node object representing a state of the microservice network. The state of this network in terms of score is then evaluated and returned as an integer. The most basic and coarse node states may be grouped into three categories. Benign: default normal state of all nodes. Under attack: an alert for the node has been raised. Compromised: a node that conducts malicious activity or is suspected of one.

The µGE can notice that events have happened over time, and/or that events are happening in multiple places of the network at the same time-each event which by itself is not enough to trigger an issue, but as an aggregated result. The aggregated result may be accumulated in a temporal and/or spatial sense. This is similar to what distributed IDSs would do, see the survey by Folino [START_REF] Folino | Ensemble based collaborative and distributed intrusion detection systems[END_REF].

The evaluation function should be able to aggregate information such that a node can be inferred to be compromised based on its behavior. E.g. if there is a port scan or API probing attempt from an internal node, this is assumed to only be possible if the node is compromised. The node may therefore be flagged as compromised even though no direct detection of an attacker present on the system was detected. If there is only one other node which could communicate with the compromised node, the evaluation function can further infer that this node is also compromised. By extension, the µGE can infer a chain of guaranteed compromised nodes and possibly compromised nodes. As an example, if there are two additional nodes which can communicate with the node, the evaluation function can trivially assume with 50% probability that either of them are compromised, assuming everything else is equal.

Decision Function

The decision function runs a minimax algorithm with specific pruning mechanisms. If there is no actual malicious action and no network related update taking place, the µGE will populate the tree representation of different possible states. For each particular node of the microservice network, based on the state of the network, there will be a list of possible actions the attacker or defender can perform. The set of possible actions is used to create new states of the same microservice network, creating new nodes, where the edges from the previous node represent the particular action taken.

Whenever any new information which results in a different state is received, the µGE stops its search, and updates the root of the tree to be that resulting state. This simulates performing the actual operation the attacker did against the real network. It is now the defender's turn. The µGE will also run the evaluation function on all the leaf nodes and compute the optimal move for the defender. We make the conjecture that the time taken to actually run this part of the algorithm is negligible and can be run post attack. The best strategy is chosen based on the available response actions discussed below.

Intrusion Response: Defender's Actions

Traditional fault tolerance techniques include rollback, rollforward, isolation, reconfiguration, and reinitialization [START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF]. Microservice based systems, however, allow more actions to be taken. In the case of an assumed compromised node, the defender may opt for the following choices.

Rollback/restart the service. This will destroy the current instance of the service and start a new one from the same configuration. If the problem persists, even older configuration of the service may be used. This allows the defender to hopefully mitigate attacks based on flawed configuration assuming it was ever correct, as well as bugs introduced in the latest version.

Diversification through recompilation or binary rewriting. Introducing randomness into the binaries executing in the microservice may be done by binary rewriting or recompilation with special compiler support [START_REF] Jackson | Compiler-Generated Software Diversity[END_REF]. An example of a freely available framework providing such support is the LLVM multicompiler.

Diversification through cloud provider. Moving a microservice to a different host in attempts to mitigate attacks that rely on host characteristics, such as exploits that target hardware or a malicious cloud provider.

Scale up and down n-variant services. The N-variant microservice system was proposed as a security measure by Otterstad&Yarygina [START_REF] Otterstad | Low-level exploitation mitigation by diverse microservices[END_REF]. This action uses the existing diversification techniques (compiler diversity/binary rewriting and cloud diversity) to spawn additional microservices, which feed their result to a governor node that compare the results for consistency. This allows nodes that have been tampered with to be detected.

Split or merge services. Requires a tool support for code auto modification that does not currently exist. An extension of this approach is to add dummy hardened services to the path. A node may be split at the function level, this may mitigate certain attacks that rely on there being a binary path of execution which enables the exploit to work, and/or the existence of certain gadgets, which will not be available after a split has been performed.

Isolation/Shutdown. Entails physical exclusion of the faulty service: stop the service permanently. This approach has a high cost associated with it and is unacceptable for the systems with high availability requirements. Noureddine et.al. [START_REF] Noureddine | A game-theoretic approach to respond to attacker lateral movement[END_REF] showed that disconnecting nodes in a response to an attack efficiently delays an attacker that is moving laterally in the simulated network.

Advantages. The controller system has two main advantages: low latency, and depth. In contrast to a human, who may need time to understand and react to the attack, the µGE can react instantly. The latency is important due to the fact that some attacks may be automated and complete a sequence of steps in the attack very quickly, which would make it critical to be able to respond promptly.

The depth is important for related reasons. The µGE can search deeper into the tree and gain a deeper insight than a casual observation from a human. Some choices may not seem intuitive as they result in a better network state deeper down in the tree. It may be possible that the attacker performs a particular attack to which the naive reaction is what allows the actual attack to proceed.

Algorithm complexity. The depth of the tree is m with b legal moves on average (the branching factor of the tree). The running time of the minimax algorithm is O(b m ), and space complexity (memory) is O(b * m). For large trees, high complexity can make the approach computationally infeasible. For the alphabeta pruning algorithm, sorting the moves by the result improves performance, such that for the perfect ordering the running time is O(b m/2 ).

Model limitations. So far, we discussed only a subset of all possible attack and defense actions. In a real world scenario there are not only more nodes, but many more operations the attacker and defender could do. This causes an explosion in the complexity of the tree, which greatly limits the depth of the search, consumes much more memory, and CPU time.

The list of attacker and defender operations is a model of the real world. Any such model will have limitations in terms of granularity. The extent to which the defender is willing to exert resources on creating an accurate representation of the real world will affect the effectiveness of the system. However, even for missing classes of attacks, they are likely to result in a state which the system will detect. Lets consider a node compromised with a zero-day exploit that went unnoticed. It is extremely unlikely the attacker has a zero-day for every node in the network. Thus, when the attacker starts to probe the rest of the network from an internal node, looking for well-known vulnerabilities, the µGE will again notice the issue and can consult its graph for the optimal course of action.

This paper assumes that the utility function and reward values are designed by experts offline. Selecting the best defense model is difficult because of a lack of quantifiable security metrics. Despite the multiple attempts to address this problem [START_REF] Simmons | ADAPT: a game inspired attack-defense and performance metric taxonomy[END_REF], putting values to parameters is still a human responsibility.

Conclusions

This paper presented the design of a cost-sensitive adaptable IRS applicable to microservice networks called µGE. The µGE collects information from the network as well as issues actions based on a search tree of possible outcomes once an attack has been detected. The proposed solution exploits the fact that the microservice network is modular by design and components can be restarted, permuted, moved, and even in some cases removed, without destroying the entire operation of the network. In general, no mitigation technique provides a guarantee an attacker cannot succeed. However, the µGE enables low latency and far lookahead which is a strong advantage for a defender.

Several open questions remain. An efficient approach to identifying and setting the values that are topical to each defender has not been presented, as this is highly subjective and specific to the assets that are important. Furthermore, for an algorithm of this type to be efficient on big networks, it is likely that a significant amount of aggressive pruning of the search tree must be performed.

Fig. 1 :

 1 Fig.1: Security game between the defender and attacker. An attacker decides which microservice to attack. The response actions deployed by the defender may or may not eradicate the attacker. If defense measures are insufficient and/or unsuccessful, the attacker will propagate laterally through the network.


Christian Berger
email: bergerch@fim.uni-passau.de

Hans P Reiser

WebBFT: Byzantine Fault Tolerance for Resilient Interactive Web Applications

Byzantine fault tolerant (BFT) applications are usually implemented with dedicated clients that interact with a set of replicas with some BFT protocol. In this paper, we explore the possibility of using web-based clients for interaction with a BFT service. Our contributions address the trustworthy deployment of client code and configuration in a browser-based execution environment (client bootstrapping), the design and implementation of a BFT client within the constraints of a browser-based JavaScript execution environment, and publish-subscribe extensions to the standard request/reply interaction model of BFT state machine model to simplify the implementation of efficient interactive web applications.

Introduction

Many client/server applications need to meet requirements regarding reliability and resilience. As the Internet advances our world to further grow together and people and devices become more and more interconnected, the role that these systems play becomes increasingly important. Many applications put high requirements on the availability and reliability of such systems.

A way to provide reliability and resilience in distributed systems is state machine replication (SMR). The state machine approach is a general method for implementing a fault-tolerant service by replicating servers and coordinating client interactions with independent server replicas [START_REF] Schneider | Implementing fault-tolerant services using the state machine approach: A tutorial[END_REF]. That way, the service remains functional even if up to a defined maximum number of replicas fail. The way in which replicas fail is described by a fault model. Byzantine fault tolerance describes the ability of a distributed system to tolerate arbitrary and malicious behavior, even involving collusion with other faulty components [START_REF] Lamport | The Byzantine generals problem[END_REF].

In recent years, many native applications have been transformed into web applications, making them easily accessible for a wide variety of client devices. Some notable examples are Google Docs1 , Pixlr2 , and ShareLatex3 . However, web applications are restricted by their execution environment [START_REF] Charland | Mobile application development: Web vs. native[END_REF], e.g., in regard of storage or computation capabilities. Current state-of the-art BFT SMR frameworks like BFT-SMaRt [START_REF] Bessani | State machine replication for the masses with BFT-SMaRt[END_REF] provide support for only native client applications. In this paper we discuss the challenges and limitations that are induced by the limited execution environment of web applications and implement a prototype of a web client which connects to a BFT service by employing a state-of-the-art replication library. The main research questions addressed by this paper are the following:

-Interface between BFT SMR framework and web client: How can a web service be equipped with BFT capabilities and how to solve challenges and limitations when designing the interface between a web client and a BFT SMR framework? -Bootstrapping and authentication: How can the web client discover the replica set, obtain the client application code and verify its integrity? How can clients verify the authenticity of the replicas? -Execution model of web services: Can we deviate from the traditional SMR request/reply programming model and implement other forms of interaction such as a publish/subscribe mechanism to match the requirements of stateof-the-art interactive web application like web group editors? -Performance of BFT web services: How do BFT web applications perform in comparison to their native counterparts?

This paper is structured as follows. Section 2 provides some background information and analyses the challenges that arise when making a client/server web application resilient to Byzantine server faults. Section 3 presents our solution of a web-enabled BFT replication framework and the design of a replicated shared online editing service based on that framework. Section 4 provides an in-depth evaluation of our framework using micro benchmarks and using a replicated shared editing service. Section 5 discusses related work on fault-tolerant web services, and Section 6 summarizes our contributions.

Problem Description

Background

Since Castro et al. [START_REF] Castro | Practical Byzantine fault tolerance and proactive recovery[END_REF] presented one of the first practically feasible solutions for coping with Byzantine faults in distributed systems, many other articles have proposed enhancements. One of the most prominent implementations of a BFT state machine replication library is the Java-based BFT-SMaRt system [START_REF] Bessani | State machine replication for the masses with BFT-SMaRt[END_REF]. It is open source and can be used to implement client-server applications on top of a robust BFT state machine replication protocol. BFT-SMaRt defines a generic client and server interface to be implemented by the application, based on a request-reply model: Client send requests using an invoke(command) method and the server implements an execute(command) method, which may change the application state and computes a result that is sent back to the client.

Challenges

In contrast to native client applications, web clients are faced with some restrictions in their execution model:

-Instead of being able to use all communication mechanisms provided by the operating system (such as creating TCP sockets), web clients are limited to use HTTP requests or WebSockets for communication. -Web applications rely on a browser-based execution environment that is running a single-threaded JavaScript application. Functions to invoke requests for execution on the replicated server need to be implemented asynchronously; the client should never block and wait for responses. -For persistently storing data, the option that web clients have is restricted to the WebStorage implementation of the browser. -The client-side bootstraping process (replica discovery, client-side code and key material deployment) is done every time the application is accessed by the client web browser, while it is typically done only once for native client applications (see Section 3.2). -Last but not least, interactive web application require an interaction model that goes beyond the traditional request/response interaction model that is regularly used by native clients. For many kinds of applications, a serverinitiated client update mechanism can be very useful.

System Model

In our architecture, a variable number of clients interact with a group of replicated servers. Our server-side implementation is based on BFT-SMaRt, which assumes an eventually synchronous system model and implements reliable authenticated channels on top of TCP connections for server-server communication. For client-server communication, our system differs from the standard BFT-SMaRt model, due to requirements of browser-based web applications. In addition, we do not expect the client to have a-priori knowledge of the replica set or public keys of the replicas. We assume that the user starts utilizing the web application by accessing the service URL in the browser without any additional knowledge. Nevertheless, we require that a solution for web clients for a BFT replicated services fulfill equivalent reliability and authentication properties.

The number of clients and replicas can change over time. A view change is required if a replica joins or leaves the system. As in BFT-SMaRt, the total number or the identity of replicas can be changed only by a trusted third party, which we call the ViewManager client. The fault model is defined by BFT-SMaRt. Faulty replicas can behave arbitrarily. As usual, we assume that arbitrary behaviour is limited to computationally feasible behaviour. In particular, we assume that a faulty node is not able to break strong cryptography and, e.g., forge signatures or MACs of other correct nodes. We always require that at most less than a third of the n c replicas in the current view c are faulty at the same time, i.e. n c > 3f always holds. We guarantee replica consistency (i.e. safety) in the presence of malicious clients. BFT-SMaRt by default uses MACs for client message authentication. While we still guarantee liveness in the sense that correct client requests will eventually be processed by the system, the system's performance may be extradited to degradation attacks if we consider the possibility of malicious clients. We investigate on the impact of such an attack in Section 4.3.

Trust Assumptions

The main focus of our design is to protect benign clients from getting incorrect service from faulty/malicious replicas. Standard BFT-SMaRt assumes that at the client side, the correct code is manually installed and a configuration file with all server details is manually distributed to all clients. In our design, we investigate possibilities on how to automate trustworthy client setup and configuration without relying on a fully manual installation. The trustworthiness of this automation depends on the following trust assumptions:

-The client's computer, its operating system, the web browser and the execution environment for JavaScript in the web browser used for executing the WebBFT client are trusted.

If an adversary is able to manipulate any of these entities, he can subvert our trustworthy code and configuration deployment mechanisms, and thus we cannot guarantee trustworthy interaction with the replicated service. -The browser has a trusted way to find the replica set.

There is a trustworthy lookup mechanism, such as a trustworthy DNS implementation available. -There is a trustworthy PKI infrastructure, which can be used to authenticate each replica belonging to a replicated web service. -The browser does not trust a single replica to deliver the correct client code, deliver the configuration or replica set information, initiate a reconfiguration of the system's current view, or respond with the correct result to a request that was invoked by the browser. Some quorum-based or equivalent mechanism makes sure that interacting with up to f malicious replicas does not cause an incorrect operation.

A trusted client environment is however not relevant for the server replicas or the safety and liveness properties of the system (we will explore the possibility of malicious clients in Section 4.3). If one of these assumptions is not met by a specific client, then that client is potentially unable to tolerate Byzantine server faults.

Solution

In this section, we present the design of an interface between the BFT-SMaRt framework and a JavaScript client that can be executed in a web browser, define extensions for interactive web applications and present a web-based shared text editor as example application. Our client software is based on Typescript, uses Angular as framework for its Model-View-Controller mechanism that allows us to update the view (HTML templates), and is designed as a state-of-theart Ajax application with methods that send requests to replicas being asynchronous. We decided to use JSON as data exchange format. A service client can be implemented by writing a JavaScript front-end application layer that uses our WebBFT interface and by providing a service replica implementation in Java that implements the ordinary BFT-SMaRt server interfaces.

Architecture

The complete, modular 3-tier architecture of our solution is shown in Figure 1.

The client application logic wraps its requests as commands in JSON format and uses an invoke() call to the underlying ServiceProxy. The ServiceProxy's invoke() methods are all asynchronous and thus non-blocking, and receive an additional ReplyListener object as parameter. The ServiceProxy registers at the CommunicationSystem as listener and implements a replyReceived() method that is triggered every time the CommunicationSystem gets an authenticated reply from a replica. After receiving a valid reply, the ServiceProxy invokes the application callback implemented by the ReplyListener object.

The ServiceProxy implements the invoke() interface, which allows the application to multicast requests to the replicas and generates sequence numbers for outgoing requests. It validates the responses from the replicas against the BFT reply quorum. We distinguish between ordered requests and unordered requests. Ordered requests are requests that may have state changing effects on the replicas (typically write requests). They need to pass the Total Order Multicast Layer of BFT-SMaRt, in which the leader proposes an order and a consensus instance is run among the replicas. Unordered requests are read-only requests. They can be passed directly to the replicas thus avoiding the ordering process and improving the system's performance. With the read-only optimization the client needs 2f + 1 matching responses to ensure linearizability [START_REF] Bessani | A guided tour on the theory and of state machine In Tutorial at the 32nd Brazilian symposium on computer networks and distributed systems[END_REF][START_REF] Herlihy | Linearizability: A correctness condition for concurrent objects[END_REF] since replicas may be in different states when they reply to unordered requests. The ServiceProxy is also responsible for implementing the reconfiguration protocol on the client side. If a validated reply indicates a higher view number than the current view of the client, this will trigger a client-side view update.

The ServiceProxy will call the CommunicationSystem to update its connections, e.g. close old connections or to establish new ones.

The client-server communication system is responsible for handling the connections to the replicas (establishing connections, closing connections), validating the MACs of the incoming replicas' responses, computing and attaching MACs to the outgoing messages as well as sending and receiving messages to/from all replicas. We provide two options for client-server communication, using simple HTTP requests and using websockets.

For the WebBFT server interface, we do not make any changes to the server interfaces of BFT-SMaRt. Developers can implement a ServiceReplica instance as they would do for plain BFT-SMaRt, with one recommendation: BFT-SMaRt uses a simple byte array for the data field for all requests and replies, and the BFT-SMaRt developers suggest to store serialized Java objects in this byte array. With WebBFT clients, it is preferable to use JSON strings for encoding application data, because this format can easily be understood by all clients (including web clients) and servers.

For server side development, we adapt the BFT-SMaRt framework, with the only significant changes made to the server's CommunicationSystem class, where we created additional protocol handlers to support HTTP and WebSocket communication in a new Netty server pipeline. This pipeline is bootstrapped parallel to the default server pipeline thus allowing web and native clients to connect to BFT-SMaRt at the same time and to be fully inter-operable. We also added functionality for parsing JSON data.

For authentication we rely on the same cryptographic primitives and protocols as BFT-SMaRt does, e.g MACs are generated with a SHA-1 HMAC function and on client side, we use a JavaScript crypto library called CryptoJS4 . We generate and validate MACs like in BFT-SMaRt.

Bootstrapping the Web Application

Bootstrapping the web applications means that the web browser needs to learn about the correct replica set of the BFT service, retrieve the correct client code, and execute it. Thus, the browser must be able to discover the replica set in a trustworthy way and the client code must be delivered in a way that guarantees that the browser can trust or validate its integrity.

The discovery of the replica set can be implemented using a BFT directory service. Basically, we could use an existing infrastructure such as the Domain Name Service (DNS). However, the DNS is not a BFT service. The issue of creating a secure BFT-DNS has already been addressed in several academic work [START_REF] Awerbuch | Group spreading: A protocol for provably secure distributed name service[END_REF][START_REF] Cachin | Secure distributed DNS[END_REF][START_REF] Yang | Using a Byzantine-fault-tolerant algorithm to provide a secure DNS[END_REF]. For example, Yang [START_REF] Yang | Using a Byzantine-fault-tolerant algorithm to provide a secure DNS[END_REF] presents a BFT-DNS based on the PBFT algorithm [START_REF] Castro | Practical Byzantine fault tolerance and proactive recovery[END_REF], in which there are at least 3f DN S + 1 replicated name servers for every BFT-DNS zone to provide correct service even if up to f DN S name servers become faulty. Using a BFT-DNS for discovering the replica set is a good solution as we avoid single point of failures or can even tolerate up to a specific number of f DN S compromised name servers. It is noteworthy that since the BFT-DNS would be a distinct service, even if we guarantee to tolerate the number of f faulty replicas for our web service, we must remember that we can still only tolerate f DN S faulty DNS name servers.

The next problem is how to deliver the client code to the browser in a trustworthy way in case that f replicas are faulty (malicious replicas): A malicious replica could deliver tampered client code that does not correctly interact with the BFT service. There are multiple solutions for delivering the client code in a trustworthy way or to check its integrity. We want to avoid the simple approach of using a trusted third party (which may represent a single point of failure) to deliver the correct client code. Thus, we take a different approach: The client code is delivered by a randomly chosen replica. If that replica is unavailable, the browser randomly chooses the next replica from the replica set (we have a list of the replicas set's IP addresses as response from a DNS query). At the same time, the browser sends a request to all other replicas to obtain the hash value of the client code. This way, we can check the client code with hash values from other replicas. Only if a BFT quorum is reached, the browser will accept the client code as trustworthy and execute it.

As the described behavior (see Figure 2) is not supported by a standard web browser, users need to install a browser plugin (extension) that adds such capability. Also, we define a new protocol handler (e.g. web-bft://app.com) so that the browser extension will only apply for BFT web apps. However, the drawback of this is that users need to install a plugin in their browsers, so we basically loose a degree of platform independence. Note that in case we restrict the fault model to non-malicious faults, we can directly use our architecture for transparently accessing a replicated service without need for a browser plugin.

Client and Replica Authentication

The client always needs to authenticate replicas, otherwise a malicious replica could impersonate other replicas and easily break the f < n/3 assumption. In BFT-SMaRt, the service developers have to choose between two ways of authentication: Using MACs or using signatures. If the system is configured to use MACs for authentication, BFT-SMaRt performs distinctly faster than it would with signatures because the symmetric cryptographic operations (computing the HMAC of a message) are faster than the asymmetric ones (computing and verifying signatures of a message). Also, in the system model of BFT-SMaRt, it is assumed that all keys are known beforehand by all system participants. However, in a productive system, the problem of sharing and distributing keys is an issue that must be addressed. Thus, we sketch our approach for authentication as follows: Every service replica is equipped with a certificate that evidences that the replica with its specific ID and internet address is a legitimate replica of the service. These certificates are signed by some certificate authority, so that a certificate chain to a root certificate installed in the user's browser exists. We can then use web protocols on top of TLS such as HTTPS or secure websockets to establish reliable and authenticated channels between browsers and replicas to prevent man-in-the-middle attacks and sniffing. However, while with TLS we can successfully secure the transport of our messages, we still need an authentication scheme for the BFT protocol layer that is above the TLS layer, which is why we implemented authentication using MACs as it is done in BFT-SMaRt.

Publish-Subscribe Model

We also provide full functionality for a publish-subscribe model that the application layer can use. However, the use of websockets is for a bi-directional channel required in that case, as we want to avoid polling over HTTP due to its high load on the replicas. Our web client interface will provide asynchronous ordered invoke() methods that are used solely for subscribe and unsubscribe purpose, e.g. invokeSubscribe(req, replyListener, event). This methods expects an additional event for which the client wants to register (e.g. a document change). The replyListener object is stored on the client side until the unsubscribe method is called and is bound to the specific event. If the client validates a quorum of matching replies (with server side generated sequence numbers) that contain the event, then it will pass the reply to the respective registered replyListener. Since subscriptions change the state of the server, an ordered invoke method is necessary.

On the server-side we will process the registration like any ordered request in the executeSingle(byte[] command) method (the server parses the command to obtain information about what type of command it is e.g. a subscription). Accordingly, the replica adds the client id to a list of subscribed clients that it maintains for every event. This list is an ordinary part of the state and needs to be respected when transferring state / installing from a snapshot by the state machines. Overriding BFT-SMaRt's default Replier allows us to build a customized reply management. This is handled in the method manageReply(req, messageContext) in which we can -depending on the event of a request -call the communication system's send method passing the reply that is associated with the request and the respective list of subscribers for an event. As we can define the behaviour depending on the request, it is also possible to only answer the requesting client (e.g. for read-only requests, subscriptions or unsubscriptions).

This allows the replicated server to publish state updates to all subscribers, thus facilitating the implementation of our real-time, interactive web application.

A BFT Interactive Group Web Text Editor

Our implementation has the purpose to study a use case that is close to a real world scenario. The group editing service is built by implementing the server interfaces of BFT-SMaRt as well as employing our web client interface so it can be accessed in the browser. We use our described publish-subscribe mechanism for publishing document changes to all connected clients and we also use a Diff, Match and Patch library that implements robust algorithms to perform operations required for synchronizing plain text [START_REF] Myers | An O(ND) difference algorithm and its variations[END_REF][START_REF] Fraser | Diff, match and patch libraries for plain text[END_REF] in combination with Differential Synchronization [START_REF] Fraser | Differential synchronization[END_REF] a method for keeping documents synchronized between server and clients. When a client invokes a write command (which contains the result of a diff operation, thus a list of changes) and the server computes and applies a patch to its document version (ergo a state change occurs), all clients that subscribed for such an event are being notified. The server distributes a list of changes to all subscribed clients (customized reply management).

Our solution differs from existing academic work regarding BFT collaborative editing [START_REF] Zhao | Byzantine fault tolerant collaborative editing[END_REF] which uses operational transformation [START_REF] Sun | Operational transformation for collaborative word processing[END_REF] in combination with a set of BFT mechanisms, e.g. solutions for state synchronization and electing a new leader that consider the Byzantine quorum. However, the main difference is that their system model suggests that a user has the role of both publisher and participant (meaning server and client role). However, in such a system with n users, there must be sufficient redundancy to tolerate f Byzantine faulty nodes. This leads to the strong assumption of requiring n > 3f users to work at the same time on a shared document. The BFT group editor we implemented has a clear separation between client and (replicated) server roles. It does thus not require a minimum number of participating clients.

Evaluation

In this section, we evaluate our implementation with throughput and latency micro-benchmarks, using the original BFT-SMaRt system as a baseline for comparison. Furthermore, we provide measurements using a group editing service as real-world application. Our experimental setup consists of a BFT configuration with four replicas (n = 4; f = 1). All replicas are hosted on different machines. A variable number of clients is distributed across several other machines. All hosts have Intel Core i7-4790 CPUs at 3.60 GHz (4 cores/8 threads), 16 GB of memory, Gentoo Base System release 2.3, Linux kernel 4.9.16 and JRE 1.8.0_121-b13, connected via a Gigabit Ethernet network. We use Firefox 57.0b3 (64-Bit) as browser to launch our web clients.

Micro-Benchmarks

Our micro-benchmarks use BFT-SMaRt's ThroughputLatencyServer implementation as simple service that only returns dummy response for each request, with configurable request and response size. We evaluate our web-based JavaScript client against BFT-SMaRt's ThroughputLatencyClient as baseline. Figure 3(a) shows the results of our latency measurements for message sizes from 0 to 16 KiB (average and standard deviation of latency observed at client side, based on 10000 requests). The latency using the web client is slightly higher than using the Java client, consistently increasing with increasing message sizes.

The additional overhead of our implementation is mainly due to translating JSON requests to Java messages, and we also suspect that the generation and validation of HMACs with the SHA1 function is implemented less efficient in JavaScript than in Java. Still, a latency increase of only 0.58 ms on average should be acceptable for BFT web clients. Figure 3(b) shows the results of our throughput measurements, using as many clients as needed to reach the maximum throughput, for 1 KiB and 5 KiB message sizes. WebBFT-SMaRt's maximum throughput is 31.8% (1 KiB) and 35.1% (5 KiB) less than that of the original BFT-SMaRt. One reason for this decrease is that while BFT-SMaRt directly exchanges byte array messages, WebBFT-SMaRt sends requests in JSON format, which need to be transformed to a byte array at server side.

In another experiment (see Figure 4(a)), we measure the correlation between latency and throughput. By increasing the number of clients, we can increase the total throughput until we reach a maximum. At the same time, adding more clients increases the per-request latency. In Figure 4(b), we use both the HTTP and the websocket variant of our web clients. The HTTP web client's latency is distinctly higher than the websocket client's for all message sizes, with larger difference for larger message sizes. The HTTP protocol imposes far more overhead in respect to headers, but to our surprise this overhead even increases with increasing message size. The additional construction of Java objects for encoding/decoding HTTP at the server side is likely to contribute to this increase. We conclude that the web clients should be used with websockets for better performance. Websockets also allow the use of a publish-subscribe mechanism over a bi-directional channel, which is simply not possible with HTTP.

Real-World Use Case

In this section, we evaluate our replication framework with a group editing service, using the following experiment with n = 4 replicas and clients on several machines: Every replica runs the service implementation of our group editing service and an HTTP server to deliver the client code. Clients are successively started every 15 seconds on machines in the same LAN by a script and automatically write on the document.

We launch either only web clients or only Java clients. The clients will send only write requests, and our publish-subscribe mechanism will notify clients about document changes automatically. A write request will with 51 % probability be a change generated by inserting an arbitrary character to the document and with 49 % be a change that deletes an arbitrary character from the document, yielding a slowly growing document. The interval between two requests is set to 50 ms, thus a single client sends up to 20 requests per second.

Latency is measured on the client side as the average of the last 100 samples of latencies for received responses to write requests. We measure the average throughput of a specific time interval as the number of write requests that were executed within this interval at the leader replica. Besides comparing BFT-SMaRt with our WebBFT version, we also add a non-replicated configuration with web clients to the comparison to investigate the performance overhead that replication brings to such real-time collaborative services.

Figure 5 shows the results of these experiments. Web clients have overall a slightly higher latency than Java clients, which is congruent with the observations we made from the micro-benchmarks. Compared to the performance of the nonreplicated group editing service, there is also a small increase in latency, which is to be expected, since the client needs to wait for several responses to fulfill a quorum.

Malicious Clients

Malicious clients can attack the system by sending requests with corrupt MACs that can be authenticated only by the leader replica. When the leader orders the request, the other replicas are unable to authenticate the request and will eventually consider the leader to be faulty and elect a new one [START_REF] Clement | BFT: The Time is now[END_REF]. Similarly, nonleader replicas may receive requests with MACs that are not authenticated by the leader. In this case, the leader will not propose this request, and other replicas that authenticate their MAC will suspect a fault leader after some timeout [START_REF] Martins | Experiences with Fault-Injection in a Byzantine Fault-Tolerant Protocol[END_REF] and invoke the leader-change sub-protocol [START_REF] Martins | Experiences with Fault-Injection in a Byzantine Fault-Tolerant Protocol[END_REF]. Leader changes can lead to a drastic throughput decrease [START_REF] Clement | BFT: The Time is now[END_REF] even if only a single malicious client is attacking. We investigate on how much damage a malicious client can actually cause using our group editing service and a f = 1, n = 4 replication configuration and web clients that are automatically writing on a document. We increase the number of web clients over time (a new client connects to the service every 15 seconds), thus increasing the throughput of the system. At a specific time (roughly at T ime = 250 seconds) we start a malicious client that carries out the MAC attack. Every point in Figure 6(b) expresses the average throughput of the system measured at replica 0 within the last second, e.g. at T ime = k seconds the average throughput of interval [k -1, k] is plotted. The latency for second k is measured at the client side as the average latency for the last 50 responses it has received at second k. Figure 6 shows our results.

The throughput of the system scatters. We observe time intervals where the throughput drops drastically, reaching almost zero. However, client requests that are being piled up in the queue lead to a temporary higher throughput once a new leader is elected followed by an interval in which no leader change occurs and the throughput is as expected (recovered phase). We observe forced leader changes roughly every two (this corresponds to the configured timeout). The latency observed at a client-side increases in our LAN from the range of a few milliseconds up to the range of a few seconds when the service is under attack. Thus, we conclude that malicious clients are indeed a problem both for throughput and latency of a replicated service. Especially high client request latencies that are caused by a leader change tarnish real-time interactive applications such as our group editor.

Related Work

The advancement of practical, high-performance frameworks for BFT SMR applications has been studied in several works e.g. by the development of PBFT [START_REF] Castro | Practical Byzantine fault tolerance and proactive recovery[END_REF], UpRight [START_REF] Clement | Upright cluster services[END_REF] or BFT-SMaRt [START_REF] Bessani | State machine replication for the masses with BFT-SMaRt[END_REF]. BFT-SMaRt made some important improvements compared to the preceding SMR libraries as it supports reconfiguration, relies on a modular architecture and uses multi-threading for the processing of messages and cryptographic signatures or MACs.

In the last decade there was also much work that focuses on increasing the reliability of web services, e.g. a web service based N-Version model called WS-FTM (Web Service-Fault Tolerance Mechanism) [START_REF] Looker | Increasing web service dependability through consensus voting[END_REF]. WS-FTM was a simple approach for implementing the classic N-Version model for web services by equipping the client with a transparent replication layer to eliminate physical faults or software implementation related faults [START_REF] Looker | Increasing web service dependability through consensus voting[END_REF]. It includes a simple consensus voter which compares the results in order to increase the reliability of the system.

Another approach was Thema [START_REF] Merideth | Thema: Byzantine-fault-tolerant middleware for web-service applications[END_REF], a BFT middleware for web service applications. Thema supports the multi tiered requirements of web services (e.g. the client may connect to a web service which itself depends on several other web services, therefore not fulfilling the classical client-server schema) and standardizes the support of web services for their clients by providing a WSDL interface and SOAP communication [START_REF] Merideth | Thema: Byzantine-fault-tolerant middleware for web-service applications[END_REF].

Moreover, building web services that have a high degree of security and dependability was studied by BFT-WS (BFT framework for Web Services), which operates on top of the standard SOAP messaging framework [START_REF] Zhao | BFT-WS: a Byzantine fault tolerance framework for web services[END_REF] and its mechanism is based on PBFT [START_REF] Castro | Practical Byzantine fault tolerance and proactive recovery[END_REF]. The authors claim that the performance of BFT-WS has only a moderate moderate runtime overhead. Like Thema, BFT-WS uses web services technologies that are antiquated. 5 The use of modern web technologies like websockets allows us to implement a publish-subscribe mechanism and thus adapt to the requirements of real-time collaborative web applications. For example, our web group editor (which notifies clients when state changes occur) can not be implemented with BFT-WS or Thema, because of the lacking support for websockets. We conclude that any new implementation approach of a BFT web service should consider the state-of-the technologies for building web services and rely on a BFT SMR that is still being maintained.

Other notable approaches include CloudBFT [START_REF] Nogueira | CloudBFT: elastic Byzantine fault tolerance[END_REF] that presents a BFT architecture that aims for scaling services in a cloud environment by exploring the possibility of grouping virtual machines into physical machines, thus offering elasticity. Moreover, Wehrman et al. proposed extensions to PBFT to support replicated clients, designed for long-running distributed applications in which replicated clients invoke operations on replicated servers [START_REF] Wehrman | Extending byzantine fault tolerance to replicated clients[END_REF].

Conclusions

We investigated on challenges and solutions for BFT web services by extending existing BFT SMR frameworks in respect to web applications. Our web client interface can be used to build any application logic on top of it by using the provided invoke methods to multicast a request to be executed by all replicas. It also supports authentication with MACs and reconfiguration as native clients do in BFT-SMaRt. Our solution for bootstrapping the web application explains how the replica set can be discovered by the use of existing infrastructure, the DNS and how delivered client code can be validated.

Experiments with micro-benchmarks show that our web client implementation achieves performance comparable fast as BFT-SMaRt's interface for native clients in terms of latency and throughput. Moreover, we concluded that the web clients should be used with websockets instead of HTTP as underlying protocol for significant better performance and also because websockets allow the use of a bi-directional channel between client and replicated server which is essential for observing state changes in real-time.

Our BFT group editor diverges from the traditional SMR programming model (a request-response cycle) by incorporating a publish-subscribe mechanism into BFT-SMaRt. We use asynchronous invoke methods on the client-side, websockets for bi-directional communication and a customized reply management on the server-side. The evaluation results of our group editor show that the replication of a web service with BFT-SMaRt is fast enough to match the requirements of real-time collaborative web applications.

Fig. 1 .

 1 Fig. 1. Overall architecture with our web client interacting with service replicas

Fig. 2 .

 2 Fig. 2. Approach for bootstrapping the application

Fig. 3 .

 3 Fig. 3. Performance measurements for a simple dummy service with variable size of requests and responses, comparing BFT-SMaRt Java clients with our web clients

Fig. 4 .

 4 Fig. 4. Further performance measurement results of the micro-benchmarks

Fig. 5 .

 5 Fig. 5. Latency comparison between non-replicated group editing service and replicated services with Java and web clients, when clients write simultaneously on the document

Fig. 6 .

 6 Fig. 6. Malicious client attacks the group editing service

Google Docs is an online office suite, see https://www.google.com/docs/about/

Pixlr is a popular online tool for photo editing, see https://pixlr.com/

ShareLatex is an online Latex editor, see https://sharelatex.com/

See https://github.com/brix/crypto-js

BFT-WS uses the Apache Axis2 framework for Java. However, state-of-the art web clients use JavaScript instead of Java in order to make them platform independent. Also, the underlying replication library PBFT is not maintained anymore and a variety of replication libraries with better performance exist, e.g. BFT-SMaRt[START_REF] Bessani | State machine replication for the masses with BFT-SMaRt[END_REF].

Acknowledgment

This research was supported by DFG through project OptScore.